Exact global alignment using A* with chaining seed heuristic and match pruning

MotivationSequence alignment has been at the core of computational biology for half a century. Still, it is an open problem to design a practical algorithm for exact alignment of a pair of related sequences in linear-like time (Medvedev, 2022b). MethodsWe solve exact global pairwise alignment with respect to edit distance by using the A* shortest path algorithm. In order to efficiently align long sequences with high divergence, we extend the recently proposed seed heuristic (Ivanov et al., 2022) with match chaining, gap costs, and inexact matches. We additionally integrate the novel match pruning technique and diagonal transition (Ukkonen, 1985) to improve the A* search. We prove the correctness of our algorithm, implement it in the A*PA aligner, and justify our extensions intuitively and empirically. ResultsOn random sequences of divergence d=4% and length n, the empirical runtime of A*PA scales near-linearly with length (best fit n1.06, n[≤]107 bp). A similar scaling remains up to d=12% (best fit n1.24, n[≤]107 bp). For n=107 bp and d=4%, A*PA reaches >500x speedup compared to the leading exact aligners EDLIB and BIWFA. The performance of A*PA is highly influenced by long gaps. On long (n>500 kbp) ONT reads of a human sample it efficiently aligns sequences with d<10%, leading to 3x median speedup compared to EDLIB and BIWFA. When the sequences come from different human samples, A*PA performs 1.7x faster than EDLIB and BIWFA. Availabilitygithub.com/RagnarGrootKoerkamp/astar-pairwise-aligner Contactragnar.grootkoerkamp@inf.ethz.ch, pesho@inf.ethz.ch