An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases
Interdisciplinary Centre for Mathematical and Computational Modelling, University of Warsaw, Warsaw, Poland
In IPDPS ’09: Proceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing (2009), pp. 1-8.
@conference{ligowski2009efficient,
title={An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases},
author={Ligowski, L. and Rudnicki, W.},
booktitle={Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on},
pages={1–8},
year={2009},
organization={IEEE}
}
The Smith Waterman algorithm for sequence alignment is one of the main tools of bioinformatics. It is used for sequence similarity searches and alignment of similar sequences. The high end Graphical Processing Unit (GPU), used for processing graphics on desktop computers, deliver computational capabilities exceeding those of CPUs by an order of magnitude. Recently these capabilities became accessible for general purpose computations thanks to CUDA programming environment on Nvidia GPUs and ATI Stream Computing environment on ATI GPUs. Here we present an efficient implementation of the Smith Waterman algorithm on the Nvidia GPU. The algorithm achieves more than 3.5 times higher per core performance than previously published implementation of the Smith Waterman algorithm on GPU, reaching more than 70% of theoretical hardware performance. The differences between current and earlier approaches are described showing the example for writing efficient code on GPU.
October 28, 2010 by hgpu
