Implementing Smith-Waterman Algorithm with Two-Dimensional Cache on GPUs

Finding regions of similarity between two data streams is a computational intensive and memory consuming problem, which refers to as sequence alignment for biological sequence. Smith-Waterman algorithm is an optimal method to find the local sequence alignment. It requires a large amount of computation and memory, and is also constrained by the memory access speed when accelerated by using Graphics Processing Units (GPUs). A new method to implement Smith-Waterman algorithm with two-dimensional cache is proposed, which aims at accelerating the first stage of Smith-Waterman algorithm and coalesced writing back the corresponding results to GPU global memory. Our proposal is implemented over NVIDIA Geforce GTX295 GPU, and compared with CUDASW++ 2.0. Experimental results show that our approach outperforms CUDASW++ 2.0 in the datasets chosen from NCBI.