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

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Optimization

Background:

• The Smith-Waterman algorithm is a fundamental tool for local sequence alignment in bioinformatics.
• Existing implementations often face performance limitations on modern hardware architectures.
• Optimizing alignment algorithms is crucial for analyzing large biological datasets.

Purpose of the Study:

• To introduce swps3, a highly optimized, vectorized implementation of the Smith-Waterman algorithm.
• To evaluate the performance of swps3 on Cell/BE and x86 architectures.
• To compare swps3 against other Smith-Waterman implementations and heuristic methods.

Main Methods:

• Vectorized implementation of the Smith-Waterman algorithm.
• Optimization for Cell/BE and x86 processor architectures.
• Benchmarking against existing software and hardware accelerators (GPU).

Main Results:

• swps3 achieves up to 8.0 billion cell-updates per second (GCUPS) on a Playstation 3 (Cell/BE).
• On an Intel Pentium CPU with SSE2, swps3 reaches 15.7 GCUPS, outperforming GPU implementations.
• Performance approaches that of heuristic methods like BLAST for long protein sequences.

Conclusions:

• The Cell/BE architecture is highly effective for accelerating biological sequence alignment.
• The performance gap between exact (Smith-Waterman) and heuristic (BLAST) alignment methods has narrowed considerably.
• swps3 offers a significant performance improvement for local sequence alignment tasks.