A tile-based parallel viterbi algorithm for biological sequence alignment on GPU with CUDA

Zhihui Du, Zhaoming Yin, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

Abstract

The Viterbi algorithm is the compute-intensive kernel in Hidden Markov Model (HMM) based sequence alignment applications. In this paper, we investigate extending several parallel methods, such as the wave-front and streaming methods for the Smith-Waterman algorithm, to achieve a significant speed-up on a GPU. The wave-front method can take advantage of the computing power of the GPU but it cannot handle long sequences because of the physical GPU memory limit. On the other hand, the streaming method can process long sequences but with increased overhead due to the increased data transmission between CPU and GPU. To further improve the performance on GPU, we propose a new tile-based parallel algorithm. We take advantage of the homological segments to divide long sequences into many short pieces and each piece pair (tile) can be fully held in the GPU's memory. By reorganizing the computational kernel of the Viterbi algorithm, the basic computing unit can be divided into two parts: independent and dependent parts. All of the independent parts are executed with a balanced load in an optimized coalesced memory-accessing manner, which significantly improves the Viterbi algorithm's performance on GPU. The experimental results show that our new tile-based parallel Viterbi algorithm can outperform the wave-front and the streaming methods. Especially for the long sequence alignment problem, the best performance of tile-based algorithm is on average about an order magnitude faster than the serial Viterbi algorithm.

Original languageEnglish (US)
Title of host publicationProceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2010
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2010 - Atlanta, GA, United States
Duration: Apr 19 2010Apr 23 2010

Publication series

NameProceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2010

Other

Other2010 IEEE International Symposium on Parallel and Distributed Processing, Workshops and Phd Forum, IPDPSW 2010
Country/TerritoryUnited States
CityAtlanta, GA
Period4/19/104/23/10

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Software
  • Theoretical Computer Science

Keywords

  • GPGPU
  • Hidden Markov model
  • Viterbi algorithm

Fingerprint

Dive into the research topics of 'A tile-based parallel viterbi algorithm for biological sequence alignment on GPU with CUDA'. Together they form a unique fingerprint.

Cite this