Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors
Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors
复制标题
DOI：
10.1093/bioinformatics/16.8.699
复制
发表时间：
2000-08-01
期刊：
影响因子：
5.8
通讯作者：
Seeberg, E
中科院分区：
文献类型：
--
作者：
Rognes, T;Seeberg, E
动机：序列数据库搜索是生物信息学中最重要和最具挑战性的任务之一。序列搜索算法的最终选择是Smith-Waterman算法。然而，由于这种方法的计算要求的性质，启发式程序或专用硬件替代品已经开发。提高了速度已获得的成本降低灵敏度或非常昂贵的hardware.Results：史密斯-沃特曼序列比对算法，采用单指令，多数据（SIMD）技术的快速实现。此实现基于嵌入在英特尔最新微处理器中的多媒体扩展（MMX）和流SIMD扩展（SSE）技术。类似的技术也存在于其他现代微处理器中。通过优化的8路并行处理方法，在相同硬件上实现了相对于以前已知的最快Smith-Waterman实现的六倍速度。在单个Intel Pentium III 500 MHz微处理器上获得了每秒超过1.5亿个单元更新的速度：这可能是迄今为止在单个通用微处理器上实现该算法的最快速度。
Motivation: Sequence database searching is among the most important and challenging tasks in bioinformatics. The ultimate choice of sequence-search algorithm is that of Smith-Waterman. However because of the computationally demanding nature of this method, heuristic programs or special-purpose hardware 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 algorithm using Single-Instruction, Multiple-Data (SIMD) technology is presented. This implementation is based on the MultiMedia eXtensions (MMX) and Streaming SIMD Extensions (SSE) technology that is embedded in Intel's latest microprocessors. Similar technology exists also in other modem microprocessors. Six-fold speed-up relative to the fastest previously known Smith-Waterman 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 microprocessor: This is probably the fastest implementation of this algorithm on a single general-purpose microprocessor described to date.