Parallelized pairwise sequence alignment using CUDA on multiple GPUs
Sungbo Jung · BMC Bioinformatics · 2009
Background Recently, rapid growth of the technology of the Graphics Processing Unit (GPU) has led to a surge of interest in using the GPU for general purpose applications. We can utilize the GPU in computation as a massive parallel coprocessor because the GPU consists of multiple cores. The GPU is also an affordable, user-programmable, and attractive commodity. In bioinformatics, finding the similarities in protein and DNA sequence databases has become a fundamental procedure. The Smith-Waterman algorithm based on dynamic programming is one of the methods used to search for all of the possible local alignments between two sequences, enabling us to find the optimal local alignments. However, dynamic programming requires a sequential calculation due to data dependency. Also required are a high number of computation steps proportional to the product of the lengths of the two sequences.