Premium
GSWABE: faster GPU‐accelerated sequence alignment with optimal alignment retrieval for short DNA sequences
Author(s) -
Liu Yongchao,
Schmidt Bertil
Publication year - 2014
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3371
Subject(s) - cuda , computer science , parallel computing , speedup , simd , smith–waterman algorithm , pairwise comparison , graphics processing unit , general purpose computing on graphics processing units , graphics , multiple sequence alignment , gpu cluster , dynamic programming , sequence (biology) , alignment free sequence analysis , algorithm , computational science , sequence alignment , computer graphics (images) , artificial intelligence , biochemistry , chemistry , genetics , biology , peptide sequence , gene
Summary In this paper, we present GSWABE, a graphics processing unit (GPU)‐accelerated pairwise sequence alignment algorithm for a collection of short DNA sequences. This algorithm supports all‐to‐all pairwise global, semi‐global and local alignment, and retrieves optimal alignments on Compute Unified Device Architecture (CUDA)‐enabled GPUs. All of the three alignment types are based on dynamic programming and share almost the same computational pattern. Thus, we have investigated a general tile‐based approach to facilitating fast alignment by deeply exploring the powerful compute capability of CUDA‐enabled GPUs. The performance of GSWABE has been evaluated on a Kepler‐based Tesla K40 GPU using a variety of short DNA sequence datasets. The results show that our algorithm can yield a performance of up to 59.1 billions cell updates per second (GCUPS), 58.5 GCUPS and 50.3 GCUPS for global, semi‐global and local alignment, respectively. Furthermore, on the same system GSWABE runs up to 156.0 times faster than the Streaming SIMD Extensions (SSE)‐based SSW library and up to 102.4 times faster than the CUDA‐based MSA‐CUDA (the first stage) in terms of local alignment. Compared with the CUDA‐based gpu‐pairAlign, GSWABE demonstrates stable and consistent speedups with a maximum speedup of 11.2, 10.7, and 10.6 for global, semi‐global, and local alignment, respectively. Copyright © 2014 John Wiley & Sons, Ltd.