Striped Smith–Waterman speeds database searches six times over other SIMD implementations
Top Cited Papers
Open Access
- 16 November 2006
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 23 (2) , 156-161
- https://doi.org/10.1093/bioinformatics/btl582
Abstract
Motivation: The only algorithm guaranteed to find the optimal local alignment is the Smith–Waterman. It is also one of the slowest due to the number of computations required for the search. To speed up the algorithm, Single-Instruction Multiple-Data (SIMD) instructions have been used to parallelize the algorithm at the instruction level. Results: A faster implementation of the Smith–Waterman algorithm is presented. This algorithm achieved 2–8 times performance improvement over other SIMD based Smith–Waterman implementations. On a 2.0 GHz Xeon Core 2 Duo processor, speeds of >3.0 billion cell updates/s were achieved. Availability:Author Webpage Contact:farrar.michael@gmail.comKeywords
This publication has 15 references indexed in Scilit:
- Identification of common molecular subsequencesPublished by Elsevier ,2004
- An improved algorithm for matching biological sequencesPublished by Elsevier ,2004
- GenBankNucleic Acids Research, 2000
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997
- Prediction of the exon-intron structure by a dynamic programming approachBiosystems, 1993
- Amino acid substitution matrices from protein blocks.Proceedings of the National Academy of Sciences, 1992
- On Finding All Suboptimal Foldings of an RNA MoleculeScience, 1989
- Improved tools for biological sequence comparison.Proceedings of the National Academy of Sciences, 1988
- Profile analysis: detection of distantly related proteins.Proceedings of the National Academy of Sciences, 1987
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970