Optimal gap-affine alignment in O(s) space

Area of Science:

• Computational biology
• Bioinformatics
• Genomics

Background:

• Pairwise sequence alignment is crucial in bioinformatics.
• Dynamic programming algorithms have quadratic time and memory limitations.
• The Wavefront Alignment Algorithm (WFA) offers O(ns) time but has high memory demands (O(s^2)).

Purpose of the Study:

• To develop a more memory-efficient gap-affine alignment algorithm.
• To address the computational impracticality of WFA for genome-scale data.

Main Methods:

• Introduction of the bidirectional WFA algorithm.
• Implementation of an algorithm with O(s) memory complexity.

Main Results:

• The bidirectional WFA achieves O(s) memory complexity while maintaining O(ns) time complexity.
• Practical implementation uses minimal memory (hundreds of MBs) for long sequences (up to 1 Mbp).
• Maintains competitive execution times for aligning noisy Oxford Nanopore Technologies reads.

Conclusions:

• The bidirectional WFA significantly improves memory efficiency for gap-affine alignments.
• This algorithm enhances scalability for genome-scale sequence analysis.
• Provides a practical solution for analyzing large sequencing datasets.