SWPS3 - Fast multi-threaded vectorized Smith-Waterman for IBM Cell/B.E. and ×86/SSE2

被引：50

作者：

Szalkowski A. ^{[1
,2
]}

Ledergerber C. ^{[1
]}

Krähenbühl P. ^{[1
]}

Dessimoz C. ^{[1
,2
]}

机构：

[1] Department of Computer Science, ETH Zürich, Zurich

[2] Swiss Institute of Bioinformatics, Lausanne

来源：

BMC Research Notes | / 1卷 / 1期

关键词：

Query Sequence; Work Thread; Streaming SIMD Extension; Profile Segment; Synergistic Processing Element;

D O I：

10.1186/1756-0500-1-107

中图分类号：

学科分类号：

摘要：

Background. We present swps3, a vectorized implementation of the Smith-Waterman local alignment algorithm optimized for both the Cell/BE and ×86 architectures. The paper describes swps3 and compares its performances with several other implementations. Findings. Our benchmarking results show that swps3 is currently the fastest implementation of a vectorized Smith-Waterman on the Cell/BE, outperforming the only other known implementation by a factor of at least 4: on a Playstation 3, it achieves up to 8.0 billion cell-updates per second (GCUPS). Using the SSE2 instruction set, a quad-core Intel Pentium can reach 15.7 GCUPS. We also show that swps3 on this CPU is faster than a recent GPU implementation. Finally, we note that under some circumstances, alignments are computed at roughly the same speed as BLAST, a heuristic method. Conclusion. The Cell/BE can be a powerful platform to align biological sequences. Besides, the performance gap between exact and heuristic methods has almost disappeared, especially for long protein sequences. © 2008 Szalkowski et al; licensee BioMed Central Ltd.

引用

共 14 条

[1]

Smith T.F., Waterman M.S., Identification of common molecular subsequences, Journal of Molecular Biology, 147, pp. 195-197, (1981)

[2]

Gotoh O., An improved algorithm for matching biological sequences, J Mol Biol, 162, pp. 705-708, (1982)

[3]

Wozniak A., Using video-oriented instructions to speed up sequence comparison, Computer Applications in the Biosciences, 13, 2, pp. 145-150, (1997)

[4]

Rognes T., Seeberg E., Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors, Bioinformatics, 16, 8, pp. 699-706, (2000)

[5]

Farrar M., Striped Smith-Waterman speeds database searches six times over other SIMD implementations, Bioinformatics, 23, 2, pp. 156-161, (2007)

[6]

Sachdeva V., Kistler M., Speight E., Tzeng T.-H.K., Exploring the viability of the cell broadband engine for bioinformatics applications, Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007

[7]

Abstracts and CD-ROM, (2007)

[8]

Lipman P., Improved Tools for Biological Sequence Comparison, Proc Natl Acad Sci, 85, pp. 24444-24448, (1988)

[9]

Manavski S.A., Valle G., CUDA Compatible GPU Cards As Efficient Hardware Accelerators for Smith-Waterman Sequence Alignment, (2008)

[10]

Gish W., WU-BLAST, (1996)

← 1 2 →