Paper Info
Title
Generic accelerated sequence alignment in SeqAn using vectorization and multi-threading.
Abstract
Motivation: Pairwise sequence alignment is undoubtedly a central tool in many bioinformatics analyses. In this paper, we present a generically accelerated module for pairwise sequence alignments applicable for a broad range of applications. In our module, we unified the standard dynamic programming kernel used for pairwise sequence alignments and extended it with a generalized inter-sequence vectorization layout, such that many alignments can be computed simultaneously by exploiting SIMD (single instruction multiple data) instructions of modern processors. We then extended the module by adding two layers of thread-level parallelization, where we (a) distribute many independent alignments on multiple threads and (b) inherently parallelize a single alignment computation using a work stealing approach producing a dynamic wavefront progressing along the minor diagonal. Results: We evaluated our alignment vectorization and parallelization on different processors, including the newest Intel (R) Xeon (R) (Skylake) and Intel (R) Xeon Phi (TM) (KNL) processors, and use cases. The instruction set AVX512-BW (Byte and Word), available on Skylake processors, can genuinely improve the performance of vectorized alignments. We could run single alignments 1600 times faster on the Xeon Phi (TM) and 1400 times faster on the Xeon (R) than executing them with our previous sequential alignment module.
Year
DOI
Venue
2018
10.1093/bioinformatics/bty380
BIOINFORMATICS
Field
DocType
Volume
Sequence alignment,Multithreading,Data mining,Text mining,Computer science,Vectorization (mathematics)
Journal
34
Issue
ISSN
Citations 
20
1367-4803
1
PageRank 
References 
Authors
0.41
23
6
Name
Order
Citations
PageRank
René Rahn160.88
Stefan Budach230.79
Pascal Costanza335834.29
Marcel Ehrhardt410.41
Jonny Hancox510.41
Knut Reinert61020105.87