Rognes T, Seeberg E
Institute of Medical Microbiology, University of Oslo, The National Hospital, NO-0027 Oslo, Norway.
Bioinformatics. 2000 Aug;16(8):699-706. doi: 10.1093/bioinformatics/16.8.699.
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.
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 modern 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.
序列数据库搜索是生物信息学中最重要且最具挑战性的任务之一。序列搜索算法的最终选择是史密斯-沃特曼算法。然而，由于该方法对计算要求很高，因此已开发出启发式程序或专用硬件替代方案。在降低灵敏度或使用非常昂贵的硬件的代价下，实现了速度的提升。
提出了一种使用单指令多数据（SIMD）技术的史密斯-沃特曼序列比对算法的快速实现。此实现基于英特尔最新微处理器中嵌入的多媒体扩展（MMX）和流SIMD扩展（SSE）技术。其他现代微处理器中也存在类似技术。通过优化的八路并行处理方法，相对于此前在相同硬件上已知的最快的史密斯-沃特曼实现，速度提高了六倍。在单个英特尔奔腾III 500 MHz微处理器上，每秒可实现超过1.5亿个单元格更新的速度。这可能是迄今为止在单个通用微处理器上对该算法的最快实现。
