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

By Adam M. Szalkowski, Christian Ledergerber, Philipp Krahenbuhl, Christophe Dessimoz. 2008

132 citations recorded by the source corpus.

BackgroundWe 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.FindingsOur 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.ConclusionThe 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.

Subfields: Computer Vision and Pattern Recognition, Hardware and Architecture, Molecular Biology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Torbjørn Rognes

In Hardware and Architecture

In Molecular Biology

Citations in the corpus

Faster Smith-Waterman database searches with inter-sequence SIMD parallelisation (2011, methodology): “SWPS3 by Szalkowski et al [12]. used the Farrar approach and claimed speeds on the PS3 of up to 8 GCUPS.”
SSW Library: An SIMD Smith-Waterman C/C++ Library for Use in Genomic Applications (2012, background): “It extends the Striped SW and SWPS3’s SIMD implementations to provide the mapping location and detailed alignment information (traceback), without performance penalty.”
OMA standalone: orthology inference among public and custom genomes and transcriptomes (2018, methodology): “To fully exploit parallelism, alignments are performed using single instruction multiple data (SIMD) instructions (Szalkowski et al., 2008) on multiple cores.”
CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units (2009, methodology): “Our CUDASW++ implementations provide better performance guarantees for protein sequence database searches compared to SWPS3 [10], CBESW [12], SW-CUDA [14] and NCBI-BLAST (version 2.2.19) [5].”