Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors

Motivation: Sequence database searching is among the most important and cha llenging tasks in bioinformatics. The ultimate choice of sequence-search al gorithm is that of Smith-Waterman. However because of the computationally d emanding nature of this method, heuristic programs or special-purpose hardw are alternatives have been developed. Increased speed has been obtained at the cost of reduced sensitivity or very expensive hardware. Results: A fast implementation of the Smith-Waterman sequence-alignment alg orithm using Single-Instruction, Multiple-Data (SIMD) technology is present ed. This implementation is based on the MultiMedia eXtensions (MMX) and Str eaming SIMD Extensions (SSE) technology that is embedded in Intel's latest microprocessors. Similar technology exists also in other modem microprocess ors. Six-fold speed-up relative to the fastest previously known Smith-Water man implementation on the same hardware was achieved by an optimized 8-way parallel processing approach. A speed of more than 150 million cell updates per second was obtained on a single Intel Pentium III 500 MHz microprocess or: This is probably the fastest implementation of this algorithm on a sing le general-purpose microprocessor described to date.