Revisiting O ( n log log n ) O(n\log\log n) Chaining for Anchored Edit Distance
Nicola Rizzo, Ragnar Groot Koerkamp · 2026
Read Revisiting O ( n log log n ) O(n\log\log n) Chaining for Anchored Edit Distance by Nicola Rizzo, Ragnar Groot Koerkamp (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03929.txt.
Introduction
Rizzo and Groot Koerkamp revisit colinear chaining, a core step in sequence alignment. Chaining links matching fragments between two sequences at low gap cost. Read mappers use it to compare genomes at scale. Early fast methods banned fragment overlaps. Modern mapping needs overlaps, though, for better sensitivity. A recent cost model tied chaining to anchored edit distance but ran slower.
The pair cut that cost to O(n log log n) time with linear space. They merge an old gap-cost method with an old overlap-cost method. They also build llchain, a simpler O(n log n) tool. It scales to millions of fragments, they report. On three million anchors, llchain ran about ten times faster than rivals. It also beat rivals on reads matched to the human genome.
Catalog record
| CREATOR | Nicola Rizzo, Ragnar Groot Koerkamp |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Revisiting O ( n log log n ) O(n\log\log n) Chaining for Anchored Edit Distance Nicola Rizzo, Ragnar Groot Koerkamp Abstract 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 ) O(n\log\log n) time algorithms by Eppstein et al. (J. ACM, 1992) chained n n fragments between two sequences T T and Q Q while minimizing a gap cost based on the diagonal distance Δ diag \Delta_{\text{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 | \Delta_{\text{diag}}=|\Delta_{T}-\Delta_{Q}| overlap cost with the classic L ∞ = max ( Δ T , Δ Q ) L_{\infty}=\max(\Delta_{T},\Delta_{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 3 n ) O(n\log^{3}n) -time algorithm for anchored edit distance to O ( n log log n ) O(n\log\log n) time in O ( n ) 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 ) 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 × 10\times faster than other methods on instances with 3 000 000 anchors, and over 3 × 3\times faster on MEMs between HiFi reads and a reference human genome. \crefname algocfalg.algs. \Crefname algocfAlgorithmAlgorithms University of Helsinki, [email protected]://orcid.org/0000-0002-2035-6309 Karlsruhe Institute of Technology, [email protected]://orcid.org/0000-0002-2091-1237 The authors wish to thank the Finnish Computing Competence Infrastructure (FCCI) for supporting this project with computational and data storage resources. \crefname observationobservationobservations \Crefname observationObservationObservations ccs Theory of computation Design and analysis of algorithms ccs Theory of computation Sorting and searching ccs Applied computing Genomics keywords Colinear chaining, Anchored edit distance, Sequence alignment, Predecessor structure † † runningauthor: N. Rizzo and R. Groot Koerkamp † † copyright: Nicola Rizzo and Ragnar Groot Koerkamp † † supplement: Software: https://github.com/nrizzo/llchain 1 Introduction Colinear chaining, known throughout the decades as Wilbur–Lipman sequence comparison , global fragment chaining , sparse dynamic programming , and just chaining is a fundamental technique for approximate alignment that dates back to the 1980s [ 42 , 43 , 17 , 31 ] . Chaining techniques have been widely adopted in different sub-fields of computational genomics: whole-genome alignment tools [ 30 ] ; sequence aligners [ 22 , 23 , 15 ] ; read mappers employing the seed-chain-extend strategy [ 39 ] ; and even assembly evaluation [ 7 , 26 ] . While the general chaining problem statement is consistent in the literature—to find the highest-scoring ordered subset of the input fragments that is consistent with an alignment—the exact formulation and algorithms change depending on the application, and it can be difficult to compare the different results. In particular, the behaviour of chaining is mainly affected by fragment score, gap cost, and overlap cost. Popular aligners use a heuristic chaining cost based on the diagonal distance and allow overlaps [ 23 , 35 , 19 ] , whereas some methods chain without overlaps and consider a function of the gaps in the two sequences [ 1 , 32 ] , in one case obtaining a lower bound on the cost of the optimal alignment [ 15 ] . Instead, we consider the anchored edit distance [ 3 , 24 , 20 ] , which gives an upper bound on the true edit distance. In this model, a number of anchors or fragments are given, which are exact matches between the two input sequences. Then, the anchored edit distance is the minimum cost of a global alignment where only the matches supported by an anchor are free. Definition 1 (Anchored edit distance) . Given two strings T and Q and a set of n exactly matching anchors (or fragments ) a_{i}=(t_{s},t_{e},q_{s},q_{e}) with T[t_{s},t_{e})=Q[q_{s},q_{e}) , the anchored edit distance is the cost of a global alignment of T and Q that minimizes the total number of insertions, deletions, substitutions, and matches not supported by an anchor . Jain et al. [ 20 ] show that the anchored edit distance can be found by computing a minimum-cost chain using an O(n\log^{3}n) algorithm, and Rizzo et al. [ 37 ] simplified the chaining cost as follows. Theorem 2 (Equivalence to chaining) . The anchored edit distance equals the minimum-cost chain of fragments under the following colinear chaining cost between the end E=(t_{e},q_{e}) of one anchor a and the start S^{\prime}=(t^{\prime}_{s},q^{\prime}_{s}) of the next anchor a^{\prime} : \connect(a,a^{\prime}):=\max(L_{\infty}(E,S^{\prime}),\Delta_{\text{diag}}(E,S^{\prime})), where \displaystyle L_{\infty}((t,q),(t^{\prime},q^{\prime})) \displaystyle:=\max(\Delta_{T},\Delta_{Q})=\max(t^{\prime}-t,q^{\prime}-q)\text{\hskip 10.22217ptis the maximum gap, and} \displaystyle\Delta_{\text{diag}}((t,q),(t^{\prime},q^{\prime})) \displaystyle:=|\Delta_{T}-\Delta_{Q}|=|\diag(t,q)-\diag(t^{\prime},q^{\prime})|\text{\hskip 10.22217ptis the diagonal distance}. Contributions. Our main contribution is to connect the anchored edit distance to previously studied chaining problems, resulting in an O(n\log\log n) theoretical algorithm working in O(n) space. Our method works by combining the L_{\infty} gap-cost computation in O(n\log\log n) time of Eppstein et al. [ 13 ] and Chao and Miller [ 9 ] with the \Delta_{\text{diag}} overlap cost computation of Baker and Giancarlo [ 3 ] . The O(n\log\log n) time complexity is obtained by using a fast integer sorting algorithm as well as predecessor structures. A simplified O(n\log n) time implementation, llchain , performs up to 10\times faster ( 3\times on average) than the existing heuristics for anchored edit distance, when chaining the MEMs between HiFi reads and a human genome. 2 Related work To provide the needed historical context to our work and to help the reader navigate the literature, we start with a review of the most important results on pairwise chaining focusing on the time complexity in the number of input anchors, summarized in \Cref tab:chaining. The original chaining formulations by Wilbur and Lipman [ 43 ] considered as input exact-match fragments between two sequences T and Q , to be selected and connected together in an order that is consistent with an alignment (i.e. a chain ) while maximizing the number of matched bases minus a constant cost for each gap [ 42 ] , or maximizing weighted matches minus an arbitrary gap cost g(\Delta_{T},\Delta_{Q}) [ 43 ] , where \Delta_{Q} and \Delta_{T} are the length of the gap in T and Q (see \Cref fig:distances). They provided an O(n^{2}) time algorithm. In 1992, the first efficient sub-quadratic-time algorithms were developed by Eppstein et al. [ 13 , 14 ] to maximize the number of matched bases minus gap costs computed as f(\Delta_{\text{diag}}) , a one-dimensional function in the diagonal distance between consecutive fragments, and they run in O(n\log\log n) or O(n\log n) time,