GPU implementation of the fast Smith-Waterman algorithm using BPBC technique

Takahiro Nishimura, Jacir L. Bordim, Yasuaki Ito, Koji Nakano


The main purpose of this work is to propose a GPU implementation for the Smith-Waterman algorithm using Bit- wise Parallel Bulk Computation (BPBC). The Smith-Waterman algorithm is based on a dynamic Programming approach that obtains the optimal local alignment between two sequences. The idea of this work is to perform the computation of the Smith-Waterman algorithm with bit-level parallelization using the the BPBC technique. We implemented the proposed BPBC technique for the Smith-Waterman algorithm on the GPU and evaluated the performance. Experimental results show that the GPU implementation runs 8.54 times faster than the multi-core CPU implementation.


Smith-Waterman; GPU; CUDA; bitwise operations; bulk computation

Full Text:



  • There are currently no refbacks.