Acceleration of the Smith-Waterman Algorithm using Single and Multiple Graphics Processors

Ali Khajeh-Saeed, Stephen Poole, J. Blair Perot
University of Massachusetts Amherst, Mechanical and Industrial Engineering, Amherst, MA 01003, United States
Journal of Computational Physics, Volume 229, Issue 11, 1 June 2010, Pages 4247-4258 (20 February 2010)


   title={Acceleration of the Smith-Waterman algorithm using single and multiple graphics processors},

   author={Khajeh-Saeed, A. and Poole, S. and Blair Perot, J.},

   journal={Journal of Computational Physics},








Download Download (PDF)   View View   Source Source   



Finding regions of similarity between two very long data streams is a computationally intensive problem referred to as sequence alignment. Alignment algorithms must allow for imperfect sequence matching with different starting locations and some gaps and errors between the two data sequences. Perhaps the most well known application of sequence matching is the testing of DNA or protein sequences against genome databases. The Smith-Waterman algorithm is a method for precisely characterizing how well two sequences can be aligned and for determining the optimal alignment of those two sequences. Like many applications in computational science, the Smith-Waterman algorithm is constrained by the memory access speed and can be accelerated significantly by using graphics processors (GPUs) as the compute engine. In this work we show that effective use of the GPU requires a novel reformulation of the Smith-Waterman algorithm. The performance of this new version of the algorithm is demonstrated using the SSCA#1 (Bio-informatics) benchmark running on one GPU and on up to four GPUs executing in parallel. The results indicate that for large problems a single GPU is up to 45 times faster than a CPU for this application, and the parallel implementation shows linear speed up on up to 4 GPUs.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: