Pairwise Sequence Alignment for Very Long Sequences on GPUs

Area of Science:

• Bioinformatics
• Computational Biology
• High-Performance Computing

Background:

• Pairwise sequence alignment is fundamental in bioinformatics for understanding biological sequences.
• The Smith-Waterman algorithm is a standard dynamic programming method for local sequence alignment.
• Existing GPU implementations face challenges with very long sequences or specific parallelization strategies.

Purpose of the Study:

• To develop novel single-GPU parallelizations of the Smith-Waterman algorithm.
• To enable efficient alignment of very long biological sequences.
• To improve the computational performance of pairwise sequence alignment.

Main Methods:

• Implementation of novel parallel algorithms on a single Graphics Processing Unit (GPU).
• Adaptation of the Smith-Waterman algorithm for efficient parallel execution.
• Benchmarking against existing GPU-based sequence alignment methods.

Main Results:

• Achieved an order of magnitude reduction in runtime compared to competing GPU algorithms.
• Demonstrated the effectiveness of the developed parallelization strategies for long sequences.
• Successfully computed both alignment scores and actual alignments.

Conclusions:

• The novel single-GPU parallelizations offer significant speedups for Smith-Waterman sequence alignment.
• These algorithms are particularly advantageous for aligning very long biological sequences.
• The developed methods represent a substantial advancement in computational bioinformatics tools.