| 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 co-processor because the GPU consists of multiple cores. In bioinformatics, finding the similarities in protein and DNA sequence databases has become a fundamental procedure. The Smith-Waterman algorithm based on the 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, the dynamic programming requires a sequential calculation due to data dependency. Also required is a high number of computation steps proportional to the product of the lengths of the two sequences.;The computation is conducted on an NVIDIA GeForce 8800GT installed in a 3.0 GHz Intel Pentium D computer equipped with 2 GB RAM, running Microsoft Windows XP Professional. The results show that the parallelized Smith-Waterman with the wavefront algorithm on the GPU achieves from 1.5 to 3.7 times speed-up than the sequential Smith-Waterman on the CPU. Therefore, the GPU is shown to be sufficiently advanced to be used as an efficient high computing accelerator for a bioinformatics application.;The approach of the present study is to implement the Smith-Waterman algorithm using the huge computational power of the GeForce 8800 series, based on NVIDIA's G80 architecture, to develop high performance solutions for local sequence alignment. To program the G80 hardware, the parallelized Smith-Waterman with the wavefront algorithm is implemented in NVIDIA CUDA, an extended C language. Except the first row and the first column, every cell in the sequence matrix depends on previous calculations of the neighbor cells. However, all the cells in an anti-diagonal can be independently calculated. Thus we can parallelize the Smith-Waterman algorithm by using multiple streaming processors to calculate an anti-diagonal. |
