A*PA2: up to 20 times faster exact global alignment

MethodsWe introduce A*PA2, an exact global pairwise aligner with respect to edit distance. The goal of A*PA2 is to unify the near-linear runtime of A*PA on similar sequences with the efficiency of dynamic programming (DP) based methods. Like EO_SCPLOWDLIBC_SCPLOW, A*PA2 uses Ukkonens band doubling in combination with Myers bitpacking. A*PA2 1) extends this with SIMD (single instruction, multiple data), 2) uses large block sizes inspired by BO_SCPLOWLOCKC_SCPLOW AO_SCPLOWLIGNERC_SCPLOW, 3) avoids recomputation of states where possible as suggested before by Fickett, 4) introduces a new optimistic technique for traceback based on diagonal transition, and 5) applies the heuristics developed in A*PA and improves them using pre-pruning. ResultsThe average runtime of A*PA2 is 19x faster than the exact aligners BO_SCPLOWIC_SCPLOWWFA and EO_SCPLOWDLIBC_SCPLOW on >500 kbp long ONT reads of a human genome having 6% divergence on average. On shorter ONT reads of 11% average divergence the speedup is 5.6x (avg. length 11 kbp) and 0.81x (avg. length 800 bp). On all tested datasets, A*PA2 is competitive with or faster than approximate methods. Availabilitygithub.com/RagnarGrootKoerkamp/astar-pairwise-aligner Contactragnar.grootkoerkamp@inf.ethz.ch