Striped Smith-Waterman speeds database searches six times over other SIMD implementations

Bioinformatics. 2007 Jan 15;23(2):156-61. doi: 10.1093/bioinformatics/btl582. Epub 2006 Nov 16.

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: http://farrar.michael.googlepages.com/Smith-waterman

Publication types

  • Comparative Study
  • Evaluation Study

MeSH terms

  • Algorithms*
  • Database Management Systems*
  • Databases, Genetic*
  • Information Storage and Retrieval / methods*
  • Sequence Alignment / methods*
  • Sequence Analysis / methods*
  • Time Factors