A New Parallel Method of Smith-Waterman Algorithm on a Heterogeneous Platform
Department of Computer Science, University of Science and Technology of China, Key Laboratory on High Performance Computing, Anhui Province, China
In Algorithms and Architectures for Parallel Processing, Vol. 6081 (2010), pp. 79-90
@article{chen2010new,
title={A New Parallel Method of Smith-Waterman Algorithm on a Heterogeneous Platform},
author={Chen, B. and Xu, Y. and Yang, J. and Jiang, H.},
journal={Algorithms and Architectures for Parallel Processing},
pages={79–90},
year={2010},
publisher={Springer}
}
Smith-Waterman algorithm is a classic dynamic programming algorithm to solve the problem of biological sequence alignment. However, with the rapid increment of the number of DNA and protein sequences, the originally sequential algorithm is very time consuming due to there existing the same computing task computed repeatedly on large-scale data. Today’s GPU (graphics processor unit) consists of hundreds of processors, so it has a more powerful computation capacity than the current multicore CPU. And as the programmability of GPU improved continuously, using it to do generous purpose computing is becoming very popular. In order to accelerate sequence alignment, previous researchers use the parallelism of the anti-diagonal of similarity matrix to parallelize the Smith-Waterman algorithm on GPU. In this paper, we design a new parallel algorithm which exploits the parallelism of the column of similarity matrix to parallelize the Smith-Waterman algorithm on a heterogeneous system based on CPU and GPU. The experiment result shows that our new parallel algorithm is more efficient than that of previous, which takes full advantage of the features of both the CPU and GPU and obtains approximately 37 times speedup compared with the sequential algorithm named OSEARCH implemented on Intel dual-core E2140 processor.
December 17, 2010 by hgpu
