Bioinformatics Vol. 16 no. 8 2000
Pages 699-706
© 2000 Oxford University Press
Original Paper |
Six-fold speed-up of Smith–Waterman sequence database searches using parallel processing on common microprocessors
1 Institute of Medical Microbiology, University of Oslo, The National Hospital, NO-0027 Oslo, Norway
Received on February 18, 2000
; revised on March 22, 2000
; accepted on March 23, 2000
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 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.
Availability: Online searches with the software are available at http://dna.uio.no/search/
Contact: torbjorn.rognes{at}labmed.uio.no
To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. L. Miller, L. J. Jensen, F. Diella, C. Jorgensen, M. Tinti, L. Li, M. Hsiung, S. A. Parker, J. Bordeaux, T. Sicheritz-Ponten, et al. Linear Motif Atlas for Phosphorylation-Dependent Signaling Sci. Signal., September 2, 2008; 1(35): ra2 - ra2. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. Tan, L. Xu, Z. Dai, S. Feng, and N. Sun Regular Paper: A Study of Architectural Optimization Methods in Bioinformatics Applications International Journal of High Performance Computing Applications, August 1, 2007; 21(3): 371 - 384. [Abstract] [PDF]
|
|
|
|
 |
|
 M. Farrar Striped Smith-Waterman speeds database searches six times over other SIMD implementations Bioinformatics, January 15, 2007; 23(2): 156 - 161. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Huang, D. M. Umbach, and L. Li Accurate anchoring alignment of divergent sequences Bioinformatics, January 1, 2006; 22(1): 29 - 34. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. Rattei, R. Arnold, P. Tischler, D. Lindner, V. Stumpflen, and H. W. Mewes SIMAP: the similarity matrix of proteins Nucleic Acids Res., January 1, 2006; 34(suppl_1): D252 - D256. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. E. Saebo, S. M. Andersen, J. Myrseth, J. K. Laerdahl, and T. Rognes PARALIGN: rapid and sensitive sequence similarity searches powered by parallel computing technology Nucleic Acids Res., July 1, 2005; 33(suppl_2): W535 - W539. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Itoh, S. Goto, T. Akutsu, and M. Kanehisa Fast and accurate database homology search using upper bounds of local alignment scores Bioinformatics, April 1, 2005; 21(7): 912 - 921. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Rognes ParAlign: a parallel sequence alignment algorithm for rapid and sensitive database searches Nucleic Acids Res., April 1, 2001; 29(7): 1647 - 1652. [Abstract] [Full Text] [PDF]
|
|