pith. sign in

arxiv: 2606.01190 · v2 · pith:YXVSSSIPnew · submitted 2026-05-31 · 💻 cs.DS

The anti-lexicographic SUS-anchor: a near-optimal k=1 sampling scheme

Ragnar Groot Koerkamp , Ragnar This is my paper

Pith reviewed 2026-06-28 16:31 UTC · model grok-4.3

classification 💻 cs.DS
keywords minimizerssampling schemessmallest unique substringsanchorsdensity boundsstreaming algorithmsk-mersanti-lexicographic order
0
0 comments X

The pith

The anti-lexicographic SUS-anchor selects k-mers at density less than 1% above the lower bound for alphabet size 4 and k=1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Low-density sampling schemes pick one k-mer from each window of w consecutive k-mers. When k is very small, minimizer schemes perform poorly and bidirectional anchors were previously the best option. The paper defines the SUS-anchor as the start of the smallest unique suffix in the window, ordered anti-lexicographically to minimize the first character while maximizing the rest. A linear-time streaming algorithm computes these anchors in O(w) space. Experiments show the resulting densities lie within 1% of the lower bound for DNA alphabets and within 10% for binary alphabets, improving on bd-anchors by a wide margin.

Core claim

The anti-lexicographic SUS-anchor identifies all suffixes in a window that do not appear elsewhere as substrings, then selects the starting position of the one that is smallest under the anti-lexicographic order. This order places strings with smaller first symbols ahead and breaks remaining ties by preferring larger subsequent symbols. For σ=4 and k=1 the scheme produces observed densities less than 1% above the density lower bound; for σ=2 the overhead is at most 10%.

What carries the argument

The anti-lexicographic SUS-anchor, which selects the start position of the smallest unique suffix under an ordering that minimizes the first character and maximizes the remaining characters.

If this is right

  • A linear-time streaming algorithm exists that reports every SUS-anchor using only O(w) working space.
  • The same construction improves density overhead from over 50% to at most 10% on binary alphabets.
  • No parameter tuning is required to reach the reported densities for the tested alphabet sizes and k=1.
  • The scheme applies directly to any string and produces a valid sampling set for every window of w k-mers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The anti-lex ordering principle may generalize to other k values or to different notions of uniqueness.
  • Near-optimal empirical performance suggests the possibility of a matching theoretical guarantee for the density in the k=1 regime.
  • The linear-time construction could be combined with existing minimizer or anchor pipelines for hybrid sampling when k varies.
  • Applications that rely on low-density k-mer sets for small k may obtain measurably smaller index sizes without loss of coverage.

Load-bearing premise

The anti-lexicographic ordering applied to smallest unique suffixes produces the claimed near-optimal densities without post-hoc parameter tuning or dataset-specific adjustments.

What would settle it

Measure the empirical density of the anti-lexicographic SUS-anchor on a long random string over alphabet size 4 for several window sizes w with k=1; if the density exceeds the lower bound by more than 1% on average, the near-optimality claim does not hold.

Figures

Figures reproduced from arXiv: 2606.01190 by Ragnar, Ragnar Groot Koerkamp.

Figure 1
Figure 1. Figure 1: Comparison of the density factor (the density multiplied by w + 1) of selection schemes for σ ∈ {2, 4, 32}, k = 1, and varying w. The lower bound is shown in red. Bd-anchors (lime/green) are shown for various r, and SUS-anchors are shown with both the lexicographic (purple) and anti-lexicographic order (blue). (The other orders are worse than anti-lexicographic.) On the right of each plot, we show scaling … view at source ↗
read the original abstract

In recent years, there has been a renewed interest in the search for low density minimizer schemes. These schemes take a window of $w$ consecutive $k$-mers, and sample one of them: the smallest under some specific order. Schemes such as the mod-minimizer provide a low density (fraction of sampled $k$-mers) when $k \gg w$, while schemes such as the greedy minimizer work well for explicit small parameters roughly in the regime $k \leq 2w$, for $k$ and $w$ up to $15$ or so. When $k < \log_\sigma w$ is very small, minimizer schemes cannot do well, and more general sampling schemes are needed that can be richer than just comparing $k$-mers. Bidirectional-string anchors (bd-anchors) form one such scheme. Inspired by bd-anchors, we introduce the smallest unique substring or SUS-anchor: Given a window, this considers all suffixes that do not occur as a substring elsewhere in the window. It then samples the start position of the smallest suffix according to the new anti-lexicographic order that minimizes the first character and maximizes the remaining characters. We give a linear-time and $O(w)$ space streaming algorithm to compute all SUS-anchors of a string. For alphabet size $\sigma=4$ and $k=1$, the anti-lexicographic SUS-anchor empirically has density $<1\%$ away from the density lower bound, significantly improving over bd-anchors that are often $>15\%$ above it. For alphabet size $\sigma=2$, the density is at most $10\%$ above the lower bound, which again improves over the $>50\%$ overhead of bd-anchors.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper introduces the SUS-anchor sampling scheme for k=1, which selects the starting position of the smallest unique suffix (SUS) within each window of w k-mers according to a new anti-lexicographic order (minimizing the first character while maximizing the remainder). It presents a linear-time streaming algorithm using O(w) space and reports empirical densities for σ=4 and σ=2 that are within 1% and 10% of a density lower bound, respectively, outperforming bd-anchors.

Significance. If the empirical margins hold with a fixed, a-priori ordering, the result would be a meaningful advance for the small-k regime where standard minimizers fail, offering a practical streaming method with densities close to optimal. The algorithm itself is parameter-free once the order is fixed and constitutes a clear algorithmic contribution.

major comments (2)
  1. [Abstract] Abstract, performance claims paragraph: the claim that the anti-lexicographic SUS-anchor achieves density <1% above the lower bound for σ=4 (and ≤10% for σ=2) is load-bearing for the central contribution, yet the manuscript supplies no a-priori justification or proof that this specific ordering is optimal independent of the test strings; if the order was selected by evaluating multiple candidates on the same data used for the reported densities, the near-optimality result is no longer evidence for a fixed scheme.
  2. [Abstract] Abstract and experimental section (wherever the lower-bound computation and datasets are described): the density margins are stated without any description of the strings used, the method for computing the lower bound, or verification that the reported figures are not the result of post-selection on the same instances, which directly affects whether the <1% gap can be taken as evidence of near-optimality.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for highlighting the need for greater clarity on the fixed nature of our ordering and the experimental details. We agree these points strengthen the manuscript and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract, performance claims paragraph: the claim that the anti-lexicographic SUS-anchor achieves density <1% above the lower bound for σ=4 (and ≤10% for σ=2) is load-bearing for the central contribution, yet the manuscript supplies no a-priori justification or proof that this specific ordering is optimal independent of the test strings; if the order was selected by evaluating multiple candidates on the same data used for the reported densities, the near-optimality result is no longer evidence for a fixed scheme.

    Authors: The anti-lexicographic order is a fixed, a-priori definition: it selects the suffix that minimizes the first character and, in case of ties, maximizes the remaining characters. This ordering was proposed based on theoretical intuition from bidirectional anchors and is independent of any test data. No post-selection among candidate orderings occurred. We will revise the abstract to explicitly state that the ordering is fixed and a priori, and add a brief justification in the methods section. revision: yes

  2. Referee: [Abstract] Abstract and experimental section (wherever the lower-bound computation and datasets are described): the density margins are stated without any description of the strings used, the method for computing the lower bound, or verification that the reported figures are not the result of post-selection on the same instances, which directly affects whether the <1% gap can be taken as evidence of near-optimality.

    Authors: We agree the manuscript lacks sufficient detail on these points. The experiments use randomly generated strings over the given alphabets; the lower bound is obtained via dynamic programming that computes the minimal possible density achievable by any k=1 sampling scheme on a window. We will expand the experimental section with a dedicated paragraph describing the datasets, the exact lower-bound algorithm, and an explicit statement that the anti-lexicographic order was fixed before any experiments were run. This addresses the post-selection concern directly. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical densities measured against external lower bound after explicit definition of ordering and algorithm.

full rationale

The paper defines the anti-lexicographic SUS-anchor explicitly (minimizes first character, maximizes remaining) and provides a streaming algorithm. It then reports measured densities on test strings compared to an independently stated lower bound. No equations, self-citations, or fitted parameters are present in the supplied text that would reduce the reported <1% gap (for σ=4, k=1) to a construction or post-hoc selection. The central claim remains a direct empirical comparison rather than a self-referential derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work introduces a new ordering and sampling rule but rests on standard string-algorithm assumptions; no free parameters, invented entities, or ad-hoc axioms are visible from the abstract.

axioms (1)
  • domain assumption A linear-time O(w)-space streaming algorithm exists for computing all SUS-anchors
    Claimed in the abstract without proof sketch or reference.

pith-pipeline@v0.9.1-grok · 5858 in / 1270 out tokens · 40917 ms · 2026-06-28T16:31:25.353978+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

299 extracted references · 246 canonical work pages · 7 internal anchors

  1. [1]

    AStarix: Fast and Optimal Sequence-to-Graph Alignment , elocation-id =

    Ivanov, Pesho and Bichsel, Benjamin and Mustafa, Harun and Kahles, Andr. AStarix: Fast and Optimal Sequence-to-Graph Alignment , elocation-id =. doi:10.1101/2020.01.22.915496 , publisher =

    work page doi:10.1101/2020.01.22.915496 2020

  2. [2]

    RECOMB , publisher =

    AStarix: Fast and Optimal Sequence-to-Graph Alignment , year = 2020, author =. RECOMB , publisher =. doi:10.1007/978-3-030-45257-5_7 , issn =

    work page doi:10.1007/978-3-030-45257-5_7 2020

  3. [3]

    RECOMB , publisher =

    Fast and Optimal Sequence-to-Graph Alignment Guided by Seeds , year = 2022, author =. RECOMB , publisher =. doi:10.1007/978-3-031-04749-7_22 , issn =

    work page doi:10.1007/978-3-031-04749-7_22 2022

  4. [4]

    doi:10.1101/2021.11.05.467453 , publisher =

    Ivanov, Pesho and Bichsel, Benjamin and Vechev, Martin , title =. doi:10.1101/2021.11.05.467453 , publisher =

    work page doi:10.1101/2021.11.05.467453 2021

  5. [5]

    doi:10.1186/s12859-018-2014-8 , year = 2018, month = feb, publisher =

    Hajime Suzuki and Masahiro Kasahara , title =. doi:10.1186/s12859-018-2014-8 , year = 2018, month = feb, publisher =

    work page doi:10.1186/s12859-018-2014-8 2014

  6. [6]

    Bioinformatics , volume = 37, number = 4, pages =

    Marco-Sola, Santiago and Moure, Juan Carlos and Moreto, Miquel and Espinosa, Antonio , title =. Bioinformatics , volume = 37, number = 4, pages =

  7. [7]

    Bioinformatics , year = 2023, month = 08, issn =

    Liu, Daniel and Steinegger, Martin , title = ". Bioinformatics , year = 2023, month = 08, issn =

    2023

  8. [8]

    Nanopore sequencing and assembly of a human genome with ultra-long reads , journal =

    Miten Jain and Sergey Koren and Karen H Miga and Josh Quick and Arthur C Rand and Thomas A Sasani and John R Tyson and Andrew D Beggs and Alexander T Dilthey and Ian T Fiddes and Sunir Malla and Hannah Marriott and Tom Nieto and Justin O. Nanopore sequencing and assembly of a human genome with ultra-long reads , journal =. doi:10.1038/nbt.4060 , year = 20...

    work page doi:10.1038/nbt.4060 2018

  9. [9]

    doi:10.1016/0022-0000(80)90002-1 , author =

    A faster algorithm computing string edit distances , journal =. doi:10.1016/0022-0000(80)90002-1 , author =

    work page doi:10.1016/0022-0000(80)90002-1

  10. [10]

    Theoretical Computer Science , year = 2008, volume = 409, number = 3, month = dec, pages =

    Bille, Philip and Farach-Colton, Martin , title =. Theoretical Computer Science , year = 2008, volume = 409, number = 3, month = dec, pages =. doi:10.1016/j.tcs.2008.08.042 , publisher =

    work page doi:10.1016/j.tcs.2008.08.042 2008

  11. [11]

    Discrete Applied Mathematics , year = 2016, volume = 212, month = oct, pages =

    Grabowski, Szymon , title =. Discrete Applied Mathematics , year = 2016, volume = 212, month = oct, pages =. doi:10.1016/j.dam.2015.10.040 , publisher =

    work page doi:10.1016/j.dam.2015.10.040 2016

  12. [12]

    SIAM Journal on Computing , year = 2018, volume = 47, number = 3, month =

    Backurs, Arturs and Indyk, Piotr , title =. SIAM Journal on Computing , year = 2018, volume = 47, number = 3, month =. doi:10.1137/15m1053128 , publisher =

    work page doi:10.1137/15m1053128 2018

  13. [13]

    Quadratic-Time Hardness of LCS and other Sequence Similarity Measures

    Abboud, Amir and Backurs, Arturs and Williams, Virginia Vassilevska , title =. doi:10.48550/ARXIV.1501.07053 , keywords =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1501.07053

  14. [14]

    2015 IEEE 56th Annual Symposium on Foundations of Computer Science , publisher =

    Abboud, Amir and Backurs, Arturs and Williams, Virginia Vassilevska , title =. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , publisher =

    2015

  15. [15]

    and Wunsch, Christian D

    Needleman, Saul B. and Wunsch, Christian D. , title =. Journal of Molecular Biology , year = 1970, volume = 48, number = 3, month =. doi:10.1016/0022-2836(70)90057-4 , publisher =

    work page doi:10.1016/0022-2836(70)90057-4 1970

  16. [16]

    Proceedings of the National Academy of Sciences , year = 1972, volume = 69, number = 1, month =

    Sankoff, David , title =. Proceedings of the National Academy of Sciences , year = 1972, volume = 69, number = 1, month =. doi:10.1073/pnas.69.1.4 , publisher =

    work page doi:10.1073/pnas.69.1.4 1972

  17. [17]

    and Waterman, M.S

    Smith, T.F. and Waterman, M.S. , title =. Journal of Molecular Biology , year = 1981, volume = 147, number = 1, month =. doi:10.1016/0022-2836(81)90087-5 , publisher =

    work page doi:10.1016/0022-2836(81)90087-5 1981

  18. [18]

    Journal of Molecular Biology , year = 1982, volume = 162, number = 3, month =

    Gotoh, Osamu , title =. Journal of Molecular Biology , year = 1982, volume = 162, number = 3, month =. doi:10.1016/0022-2836(82)90398-9 , publisher =

    work page doi:10.1016/0022-2836(82)90398-9 1982

  19. [19]

    Bulletin of Mathematical Biology , year = 1990, volume = 52, number = 3, pages =

    Gotoh, Osamu , title =. Bulletin of Mathematical Biology , year = 1990, volume = 52, number = 3, pages =. doi:10.1016/s0092-8240(05)80216-2 , publisher =

    work page doi:10.1016/s0092-8240(05)80216-2 1990

  20. [20]

    Advances in Mathematics , year = 1976, volume = 20, number = 3, month =

    Waterman, M.S and Smith, T.F and Beyer, W.A , title =. Advances in Mathematics , year = 1976, volume = 20, number = 3, month =. doi:10.1016/0001-8708(76)90202-4 , publisher =

    work page doi:10.1016/0001-8708(76)90202-4 1976

  21. [21]

    Journal of Combinatorial Theory, Series A , year = 1974, volume = 16, number = 2, month = mar, pages =

    Sellers, Peter H , title =. Journal of Combinatorial Theory, Series A , year = 1974, volume = 16, number = 2, month = mar, pages =. doi:10.1016/0097-3165(74)90050-8 , publisher =

    work page doi:10.1016/0097-3165(74)90050-8 1974

  22. [22]

    , title =

    Sellers, Peter H. , title =. SIAM Journal on Applied Mathematics , year = 1974, volume = 26, number = 4, month =. doi:10.1137/0126070 , publisher =

    work page doi:10.1137/0126070 1974

  23. [23]

    and Erickson, Bruce W

    Altschul, Stephen F. and Erickson, Bruce W. , title =. Bulletin of Mathematical Biology , year = 1986, volume = 48, number =. doi:10.1007/bf02462326 , publisher =

    work page doi:10.1007/bf02462326 1986

  24. [24]

    , title =

    Hirschberg, Daniel S. , title =. Communications of the ACM , year = 1975, volume = 18, number = 6, month =. doi:10.1145/360825.360861 , publisher =

    work page doi:10.1145/360825.360861 1975

  25. [25]

    Lecture Notes in Computer Science , year = 1983, pages =

    Ukkonen, Esko , title =. Lecture Notes in Computer Science , year = 1983, pages =. doi:10.1007/3-540-12689-9_129 , isbn = 9783540386827, publisher =

    work page doi:10.1007/3-540-12689-9_129 1983

  26. [26]

    Information and Control , year = 1985, volume = 64, number =

    Ukkonen, Esko , title =. Information and Control , year = 1985, volume = 64, number =. doi:10.1016/s0019-9958(85)80046-2 , publisher =

    work page doi:10.1016/s0019-9958(85)80046-2 1985

  27. [27]

    Journal of Algorithms , year = 1985, volume = 6, number = 1, month =

    Ukkonen, Esko , title =. Journal of Algorithms , year = 1985, volume = 6, number = 1, month =. doi:10.1016/0196-6774(85)90023-9 , publisher =

    work page doi:10.1016/0196-6774(85)90023-9 1985

  28. [28]

    Bioinformatics , year = 1988, volume = 4, number = 1, pages =

    Myers, Gene and Miller, Webb , title =. Bioinformatics , year = 1988, volume = 4, number = 1, pages =. doi:10.1093/bioinformatics/4.1.11 , publisher =

    work page doi:10.1093/bioinformatics/4.1.11 1988

  29. [29]

    Smith, T. F. and Waterman, M. S. and Fitch, W. M. , title =. Journal of Molecular Evolution , year = 1981, volume = 18, number = 1, month =. doi:10.1007/bf01733210 , publisher =

    work page doi:10.1007/bf01733210 1981

  30. [30]

    Journal of Algorithms , year = 1989, volume = 10, number = 2, month =

    Landau, Gad M and Vishkin, Uzi , title =. Journal of Algorithms , year = 1989, volume = 10, number = 2, month =. doi:10.1016/0196-6774(89)90010-2 , publisher =

    work page doi:10.1016/0196-6774(89)90010-2 1989

  31. [31]

    Algorithmica , year = 1986, volume = 1, number =

    Myers, Gene , title =. Algorithmica , year = 1986, volume = 1, number =. doi:10.1007/bf01840446 , publisher =

    work page doi:10.1007/bf01840446 1986

  32. [32]

    and Fischer, Michael J

    Wagner, Robert A. and Fischer, Michael J. , title =. Journal of the ACM , year = 1974, volume = 21, number = 1, month =. doi:10.1145/321796.321811 , publisher =

    work page doi:10.1145/321796.321811 1974

  33. [33]

    Acta Informatica , year = 1982, volume = 18, number = 2, issn =

    Nakatsu, Narao and Kambayashi, Yahiko and Yajima, Shuzo , title =. Acta Informatica , year = 1982, volume = 18, number = 2, issn =. doi:10.1007/bf00264437 , publisher =

    work page doi:10.1007/bf00264437 1982

  34. [34]

    and Szymanski, Thomas G

    Hunt, James W. and Szymanski, Thomas G. , title =. Communications of the ACM , year = 1977, volume = 20, number = 5, month =. doi:10.1145/359581.359603 , publisher =

    work page doi:10.1145/359581.359603 1977

  35. [35]

    , title =

    Hirschberg, Daniel S. , title =. Journal of the ACM , year = 1977, volume = 24, number = 4, month =. doi:10.1145/322033.322044 , publisher =

    work page doi:10.1145/322033.322044 1977

  36. [36]

    and Paten, Benedict , title =

    Eizenga, Jordan M. and Paten, Benedict , title =. doi:10.1101/2022.01.12.476087 , publisher =

    work page doi:10.1101/2022.01.12.476087 2022

  37. [37]

    Journal of the ACM , year = 1999, volume = 46, number = 3, month =

    Myers, Gene , title =. Journal of the ACM , year = 1999, volume = 46, number = 3, month =. doi:10.1145/316542.316550 , publisher =

    work page doi:10.1145/316542.316550 1999

  38. [38]

    doi:10.1093/bioinformatics/btw753 , publisher =

    Bioinformatics , year = 2017, editor =. doi:10.1093/bioinformatics/btw753 , publisher =

    work page doi:10.1093/bioinformatics/btw753 2017

  39. [39]

    and Myers, Gene , title =

    Wu, Sun and Manber, U. and Myers, Gene , title =. Algorithmica , year = 1996, volume = 15, number = 1, month =. doi:10.1007/bf01942606 , publisher =

    work page doi:10.1007/bf01942606 1996

  40. [40]

    and Lampe, Jordan , title =

    Chang, William I. and Lampe, Jordan , title =. Lecture Notes in Computer Science , year = 1992, pages =. doi:10.1007/3-540-56024-6_14 , isbn = 9783540473572, publisher =

    work page doi:10.1007/3-540-56024-6_14 1992

  41. [41]

    ACM Computing Surveys , year = 2001, volume = 33, number = 1, month =

    Navarro, Gonzalo , title =. ACM Computing Surveys , year = 2001, volume = 33, number = 1, month =. doi:10.1145/375360.375365 , publisher =

    work page doi:10.1145/375360.375365 2001

  42. [42]

    Information Processing Letters , year = 1986, volume = 23, number = 2, month =

    Apostolico, Alberto , title =. Information Processing Letters , year = 1986, volume = 23, number = 2, month =. doi:10.1016/0020-0190(86)90044-x , publisher =

    work page doi:10.1016/0020-0190(86)90044-x 1986

  43. [43]

    Algorithms in Bioinformatics , year = 2014, pages =

    Myers, Gene , title =. Algorithms in Bioinformatics , year = 2014, pages =. doi:10.1007/978-3-662-44753-6_5 , isbn = 9783662447536, publisher =

    work page doi:10.1007/978-3-662-44753-6_5 2014

  44. [44]

    , title =

    Fickett, James W. , title =. Nucleic Acids Research , year = 1984, volume = 12, number =. doi:10.1093/nar/12.1part1.175 , publisher =

    work page doi:10.1093/nar/12.1part1.175 1984

  45. [45]

    and Stelling, P

    Gusfield, D. and Stelling, P. , title =. Computer Methods for Macromolecular Sequence Analysis , year = 1996, pages =. doi:10.1016/s0076-6879(96)66030-3 , publisher =

    work page doi:10.1016/s0076-6879(96)66030-3 1996

  46. [46]

    , title =

    Kruskal, Joseph B. , title =. SIAM Review , year = 1983, volume = 25, number = 2, month =. doi:10.1137/1025045 , publisher =

    work page doi:10.1137/1025045 1983

  47. [47]

    Longest Common Subsequence in k-length substrings

    Benson, Gary and Levy, Avivit and Shalom, Riva , title =. doi:10.48550/ARXIV.1402.2097 , keywords =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1402.2097 2097

  48. [48]

    Similarity Search and Applications 2013 , publisher =

    Longest Common Subsequence in k Length Substrings , year = 2013, author =. Similarity Search and Applications 2013 , publisher =. doi:10.1007/978-3-642-41062-8_26 , ISSN =

    work page doi:10.1007/978-3-642-41062-8_26 2013

  49. [49]

    and Levy, A

    Benson, G. and Levy, A. and Maimoni, S. and Noifeld, D. and Shalom, B.R. , title =. Theoretical Computer Science , year = 2016, volume = 638, month = jul, pages =. doi:10.1016/j.tcs.2015.11.026 , publisher =

    work page doi:10.1016/j.tcs.2015.11.026 2016

  50. [50]

    doi:10.48550/ARXIV.1407.2407 , keywords =

    Paveti\'. doi:10.48550/ARXIV.1407.2407 , keywords =

    work page doi:10.48550/arxiv.1407.2407

  51. [51]

    Information Processing Letters , volume = 114, number = 11, pages =

    Efficient algorithms for the longest common subsequence in k-length substrings , author =. Information Processing Letters , volume = 114, number = 11, pages =

  52. [52]

    Fast and simple algorithms for computing both $LCS_{k}$ and $LCS_{k+}$

    Paveti\'. Fast and simple algorithms for computing both LCS_. doi:10.48550/ARXIV.1705.07279 , journal =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1705.07279

  53. [53]

    Vintsyuk, T. K. , title =. Cybernetics , oldyear = 1972, year = 1968, volume = 4, number = 1, pages =. doi:10.1007/bf01074755 , publisher =

    work page doi:10.1007/bf01074755 1972

  54. [54]

    Arlazarov, V. L. and Dinitz, Y. A. and Kronrod, M. A. and Faradzhev, I. A. , title =. Dokl. Akad. Nauk SSSR , year = 1970, volume = 194, number = 3, pages =

    1970

  55. [55]

    and Mackworth, Alan K

    Poole, David L. and Mackworth, Alan K. , title =. doi:10.1017/9781108164085 , isbn = 9781108164085, publisher =

    work page doi:10.1017/9781108164085

  56. [56]

    doi:10.23638/DMTCS-21-1-10 , journal =

    Stable gonality is computable , author =. doi:10.23638/DMTCS-21-1-10 , journal =

    work page doi:10.23638/dmtcs-21-1-10

  57. [57]

    On rainbow-free colourings of uniform hypergraphs , journal =

    Groot Koerkamp, Ragnar and. On rainbow-free colourings of uniform hypergraphs , journal =. doi:10.1016/j.tcs.2021.06.022 , publisher =

    work page doi:10.1016/j.tcs.2021.06.022 2021

  58. [58]

    Bioinformatics , year = 2023, editor =

    Marco-Sola, Santiago and Eizenga, Jordan M and Guarracino, Andrea and Paten, Benedict and Garrison, Erik and Moreto, Miquel , title =. Bioinformatics , year = 2023, editor =. doi:10.1093/bioinformatics/btad074 , publisher =

    work page doi:10.1093/bioinformatics/btad074 2023

  59. [59]

    Artificial Intelligence , year = 1977, volume = 8, number = 1, month =

    Gelperin, David , title =. Artificial Intelligence , year = 1977, volume = 8, number = 1, month =. doi:10.1016/0004-3702(77)90005-4 , publisher =

    work page doi:10.1016/0004-3702(77)90005-4 1977

  60. [60]

    and Nilsson, Nils J

    Hart, Peter E. and Nilsson, Nils J. and Raphael, Bertram , title =. IEEE Transactions on Systems Science and Cybernetics , year = 1968, volume = 4, number = 2, pages =. doi:10.1109/tssc.1968.300136 , publisher =

    work page doi:10.1109/tssc.1968.300136 1968

  61. [61]

    Holte , editor =

    Robert C. Holte , editor =. Common Misconceptions Concerning Heuristic Search , booktitle =

  62. [62]

    and Nilsson, Nils J

    Hart, Peter E. and Nilsson, Nils J. and Raphael, Bertram , title =. ACM SIGART Bulletin , year = 1972, number = 37, month =. doi:10.1145/1056777.1056779 , publisher =

    work page doi:10.1145/1056777.1056779 1972

  63. [63]

    , author =

    The Optimality of A* Revisited. , author =. AAAI , volume = 83, pages =

  64. [64]

    Heuristics: intelligent search strategies for computer problem solving , author =

  65. [65]

    Intelligent Unmanned Ground Vehicles , year = 1997, pages =

    Stentz, Anthony , title =. Intelligent Unmanned Ground Vehicles , year = 1997, pages =. doi:10.1007/978-1-4615-6325-9_11 , isbn = 9781461563259, publisher =

    work page doi:10.1007/978-1-4615-6325-9_11 1997

  66. [66]

    Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 2 , pages =

    Stentz, Anthony , title =. Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 2 , pages =

  67. [67]

    Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems - AAMAS '05 , year = 2005, doi =

    Koenig, Sven and Likhachev, Maxim , title =. Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems - AAMAS '05 , year = 2005, doi =

    2005

  68. [68]

    Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems - AAMAS '06 , year = 2006, doi =

    Koenig, Sven and Likhachev, Maxim , title =. Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems - AAMAS '06 , year = 2006, doi =

    2006

  69. [69]

    Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1 , pages =

    Sun, Xiaoxun and Koenig, Sven and Yeoh, William , title =. Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1 , pages =

  70. [70]

    Eighteenth National Conference on Artificial Intelligence , pages =

    Koenig, Sven and Likhachev, Maxim , title =. Eighteenth National Conference on Artificial Intelligence , pages =

  71. [71]

    PLOS ONE , year = 2021, editor =

    Delahaye, Clara and Nicolas, Jacques , title =. PLOS ONE , year = 2021, editor =. doi:10.1371/journal.pone.0257521 , publisher =

    work page doi:10.1371/journal.pone.0257521 2021

  72. [72]

    , title =

    Johnson, Donald B. , title =. Journal of the ACM , year = 1977, volume = 24, number = 1, month =. doi:10.1145/321992.321993 , publisher =

    work page doi:10.1145/321992.321993 1977

  73. [73]

    and Shaw, Jim and Spouge, John L

    Frith, Martin C. and Shaw, Jim and Spouge, John L. , title =. doi:10.1101/2022.08.18.504476 , publisher =

    work page doi:10.1101/2022.08.18.504476 2022

  74. [74]

    Bioinformatics , year = 2023, editor =

    Frith, Martin C and Shaw, Jim and Spouge, John L , title =. Bioinformatics , year = 2023, editor =. doi:10.1093/bioinformatics/btad057 , publisher =

    work page doi:10.1093/bioinformatics/btad057 2023

  75. [75]

    and Heger, Andreas and Pagnamenta, Alistair T

    Bowden, Rory and Davies, Robert W. and Heger, Andreas and Pagnamenta, Alistair T. and de Cesare, Mariateresa and Oikkonen, Laura E. and Parkes, Duncan and Freeman, Colin and Dhalla, Fatima and Patel, Smita Y. and Popitsch, Niko and Ip, Camilla L. C. and Roberts, Hannah E. and Salatino, Silvia and Lockstone, Helen and Lunter, Gerton and Taylor, Jenny C. an...

    work page doi:10.1038/s41467-019-09637-5 2019

  76. [76]

    and Mikheenko, Alla and Vollger, Mitchell R

    Nurk, Sergey and Koren, Sergey and Rhie, Arang and Rautiainen, Mikko and Bzikadze, Andrey V. and Mikheenko, Alla and Vollger, Mitchell R. and Altemose, Nicolas and Uralsky, Lev and Gershman, Ariel and Aganezov, Sergey and Hoyt, Savannah J. and Diekhans, Mark and Logsdon, Glennis A. and Alonge, Michael and Antonarakis, Stylianos E. and Borchers, Matthew an...

    work page doi:10.1126/science.abj6987

  77. [77]

    and Taylor, Dylan J

    Rhie, Arang and Nurk, Sergey and Cechova, Monika and Hoyt, Savannah J. and Taylor, Dylan J. and Altemose, Nicolas and Hook, Paul W. and Koren, Sergey and Rautiainen, Mikko and Alexandrov, Ivan A. and Allen, Jamie and Asri, Mobin and Bzikadze, Andrey V. and Chen, Nae-Chyun and Chin, Chen-Shan and Diekhans, Mark and Flicek, Paul and Formenti, Giulio and Fun...

    work page doi:10.1038/s41586-023-06457-y 2023

  78. [78]

    and Monlong, Jean and Abel, Haley J

    Liao, Wen-Wei and Asri, Mobin and Ebler, Jana and Doerr, Daniel and Haukness, Marina and Hickey, Glenn and Lu, Shuangjia and Lucas, Julian K. and Monlong, Jean and Abel, Haley J. and Buonaiuto, Silvia and Chang, Xian H. and Cheng, Haoyu and Chu, Justin and Colonna, Vincenza and Eizenga, Jordan M. and Feng, Xiaowen and Fischer, Christian and Fulton, Robert...

    work page doi:10.1038/s41586-023-05896-x 2023

  79. [79]

    BMC Bioinformatics , year = 2009, volume = 10, number =

    Papamichail, Dimitris and Papamichail, Georgios , title =. BMC Bioinformatics , year = 2009, volume = 10, number =. doi:10.1186/1471-2105-10-s1-s10 , publisher =

    work page doi:10.1186/1471-2105-10-s1-s10 2009

  80. [80]

    Information Processing Letters , year = 1990, volume = 35, number = 6, month =

    Wu, Sun and Manber, Udi and Myers, Gene and Miller, Webb , title =. Information Processing Letters , year = 1990, volume = 35, number = 6, month =. doi:10.1016/0020-0190(90)90035-v , publisher =

    work page doi:10.1016/0020-0190(90)90035-v 1990

Showing first 80 references.