Optimal gap-affine alignment in O(s) space

Pairwise sequence alignment remains a fundamental problem in computational biology and bioinformatics. Recent advances in genomics and sequencing technologies demand for 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 (WFA) algorithm introduced an efficient algorithm to perform exact 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. In this paper, we present the bidirectional WFA algorithm (BiWFA), the first gap-affine algorithm capable of computing optimal alignments in O(s) memory while retaining the WFA's time complexity of O(ns). In practice, our implementation never requires more than 183 MB aligning long and noisy sequences up to 1 Mbp long, while maintaining competitive execution times.