high performance computing on graphics processing units: hgpu.org

Sequence alignment is a task that calculates the degree of similarity between two sequences. Given a query sequence, finding a database sequence which is most similar to the query by sequence alignment is the first step in bioinformatics research. The first sequence alignment algorithm was proposed by Needle-man and Wunsch. They got the optimal global alignment by using dynamic programming method. Afterwards, Smith and Waterman proposed the optimal local alignment. However, the number of sequences in the database increases exponentially every year and the cost of these two algorithms is expensive in terms of running time and memory space. Thus, accelerating the sequence alignment algorithm has become the trend in recent years. In this paper, we present a fast sequence alignment method using CUDA-enabled GPU. We first redefine the recursive formula of Smith-Waterman algorithm so that one row of the matrix can be calculated in parallel. Then, we use the prefix max scan method to reduce the computation complexity for each row. In addition, only on-chip shared memory is used for reducing the penalty of memory accesses. Experimental results show that the proposed method is in average 50 times faster than implementation of Smith-Waterman based on CPU, 2~4 times faster than other GPU-based versions of Smith-Waterman algorithm.