2026-08-27T21:20:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27517 2026-08-27T06:04:07Z ddc:004 open_access

Revisiting O(n log log n) Chaining for Anchored Edit Distance Rizzo, Nicola Groot Koerkamp, Ragnar Colinear chaining Anchored edit distance Sequence alignment Predecessor structure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicola Rizzo and Ragnar Groot Koerkamp 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.13 urn:nbn:de:0030-drops-275177 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode