Optimal gap-affine alignment in O(s) space

Motivation: Pairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand faster and scalable algorithms that can cope with the ever-increasing sequence lengths. Classical pairwise alignment algorithms based on dynamic programming are strongly limited by quadratic requirements in time and memory. The recently proposed wavefront alignment algorithm (WFA) introduced an efficient algorithm to perform exact gap-affine alignment in O(ns) time, where s is the optimal score and n is the sequence length. Notwithstanding these bounds, WFA's O(s2) memory requirements become computationally impractical for genome-scale alignments, leading to a need for further improvement.Results: In this article, we present the bidirectional WFA algorithm, the first gap-affine algorithm capable of computing optimal alignments in O(s) memory while retaining WFA's time complexity of O(ns). As a result, this work improves the lowest known memory bound O(n) to compute gap-affine alignments. In practice, our implementation never requires more than a few hundred MBs aligning noisy Oxford Nanopore Technologies reads up to 1 Mbp long while maintaining competitive execution times.

Automated summary

Pairwise sequence alignment is a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies call for faster and scalable algorithms to handle longer sequences. The wavefront alignment algorithm (WFA) proposed an efficient approach to perform exact gap-affine alignment, but its memory requirements were computationally impractical for genome-scale alignments. In this study, the bidirectional WFA algorithm is introduced, which can compute optimal alignments with significantly reduced memory usage while maintaining the time complexity of WFA.