Revisiting O(n log log n) Chaining for Anchored Edit Distance

Colinear chaining is a classical heuristic for sequence alignment: it enables scalable genome comparison and is a main component of many state-of-the-art read mappers based on seed-chain-extend. The earliest O(n log log n) and O(n log n) time algorithms by Eppstein et al. (J. ACM, 1992) chained n fragments between two sequences T and Q while minimizing a gap cost based on the diagonal distance Δ_diag between consecutive fragments. They also forbid fragment overlaps, which are essential in current chaining formulations: in long-read mapping, overlaps improve sensitivity and avoid restrictions on the fragment class considered. Jain, Gibney, and Thankachan (J. Comput. Biol. 2022) recently combined a Δ_diag = |Δ_T-Δ_Q| overlap cost with the classic L_∞ = max(Δ_T, Δ_Q) gap cost that takes the maximum between the horizontal and vertical gap between the fragments and they proved that chaining under this cost model is equivalent to the anchored edit distance. We improve the existing O(n log³ n)-time algorithm for anchored edit distance to O(n log log n) time in O(n) space, by combining the gap-cost computation of Chao and Miller (Algorithmica, 1995) with the overlap-cost computation of Baker and Giancarlo (ESA, 1998). By developing llchain, a simpler O(n log n)-time implementation of our method, we show how chaining algorithms that might have been recently overlooked by the bioinformatics community scale competitively to millions of fragments and large genomes. On average, llchain is 10× faster than other methods on instances with 3 000 000 anchors, and over 2.3× faster on MEMs between HiFi reads and a reference human genome.