Accelerating the Smith-Waterman algorithm with interpair pruning and band optimization for the all-pairs comparison...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• The Smith-Waterman algorithm offers superior sensitivity for local sequence alignment compared to heuristic methods.
• Its high time complexity limits its use in all-pairs sequence comparisons crucial for phylogenetic tree construction.
• Existing methods utilize intrapair block pruning on Graphics Processing Units (GPUs) for acceleration.

Purpose of the Study:

• To accelerate the Smith-Waterman algorithm for all-pairs sequence comparisons.
• To implement interpair block pruning and band optimization for enhanced performance.
• To compare the acceleration achieved with a previous intrapair pruning method on GPUs.

Main Methods:

• Developed an interpair optimization technique for the Smith-Waterman algorithm.
• Implemented efficient block pruning by calculating a lower bound for unprocessed sequence pairs.
• Integrated the interpair optimization into SW#, a GPU-based implementation using banded algorithms.

Main Results:

• The interpair optimization method achieved significant matrix cell pruning: 88% on a single GPU and 73% on two GPUs for Bacillus anthracis genomes.
• Alignment performance reached 202 giga-cell updates per second (GCUPS) on two Tesla K40 GPUs for human chromosome 21.
• The method accelerated all-pairs comparisons of same-species sequences by 1.2 times compared to intrapair pruning.

Conclusions:

• Interpair pruning and band optimization effectively accelerate Smith-Waterman for same-species sequence comparisons.
• The method shows limitations in cross-species comparisons (e.g., human, chimpanzee, gorilla).
• The optimized Smith-Waterman algorithm is valuable for applications requiring optimal local alignment scores within species.