Abstract
We present a novel hardware implementation of the double affine Smith-Waterman (DASW) algorithm, which uses dynamic programming to compare and align genomic sequences such as DNA and proteins. We implement DASW on a commodity graphics card, taking advantage of the general purpose programmability of the graphics processing unit to leverage its cheap parallel processing power. The results demonstrate that our system’s performance is competitive with current optimized software packages.
Chapter PDF
Similar content being viewed by others
Keywords
- Dynamic Programming
- Graphic Processing Unit
- Texture Memory
- Genomic Sequence Comparison
- Dynamic Programming Table
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Brenner, S.E., Chothia, C., Hubbard, T.J.P.: Assessing sequence comparison methods with reliable structurally identified distant evolutionary relationships. Proc. National Academy of Science 95, 6073–6078 (1998)
Gotoh, O.: An improved algorithm for matching biological sequences. Journal of Molecular Biology 162, 705–708 (1982)
Smith, T., Waterman, M.: Identification of common molecular subsequences. Journal of Molecular Biology 147, 195–197 (1981)
ClearSpeed: AdvanceTM Board (2006), http://www.clearspeed.com/index.html
Horn, R., Houston, M., Hanrahan, P.: ClawHMMer: A streaming HMMer-search implementation. In: Proc. Supercomputing (2005)
Rognes, T., Seeberg, E.: Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics 16, 699–706 (2000)
Henikoff, S., Henikoff, J.: Amino acid substitution matrices from protein blocks. Proc. National Academy of Science 89, 10915–10919 (1992)
Pearson, W.: Effective protein sequence comparison. Meth. Enzymol. 266, 227–258 (1996)
Pearson, W., Lipman, D.: Improved tools for biological sequence comparison. Proc. National Academy of Science 85, 2444–2448 (1988)
Green, P.: SWAT Optimization (2006), http://www.phrap.org/phredphrap/general.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, Y., Huang, W., Johnson, J., Vaidya, S. (2006). GPU Accelerated Smith-Waterman. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds) Computational Science – ICCS 2006. ICCS 2006. Lecture Notes in Computer Science, vol 3994. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11758549_29
Download citation
DOI: https://doi.org/10.1007/11758549_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34385-1
Online ISBN: 978-3-540-34386-8
eBook Packages: Computer ScienceComputer Science (R0)