On Minimizers of Minimum Density

Arseny Shur

REVIEW 2 major objections 5 minor 24 references

On Minimizers of Minimum Density

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper computes exact minimum-density minimizers for five small parameter pairs and gives a single-exponential general algorithm.

desk verdict A solid exact-algorithm paper with a genuinely new regular-language method and valuable computational results, but the asymptotic optimality proofs rely on a simplicity condition that is asserted rather than fully verified. read the letter →

arxiv 2506.05277 v1 pith:HE3PZKOJ submitted 2025-06-05 cs.DS cs.FL

Arseny Shur This is my paper

classification cs.DScs.FL MSC 68Q4568R1568Q2505C50

keywords minimizersminimumdensityuniversalhittingsetsregularlanguagesfiniteantidictionaryPerron–Frobeniustheoryk-mersamplingslidingwindow

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper attempts to settle the exact optimization problem for minimizers: given alphabet size $\sigma$, $k$-mer length $k$, and window parameter $w$, which linear order on $k$-mers minimizes the expected sampling density? The paper proves that for fixed $\sigma$ this minimizer can be found in $w\cdot 2^{\sigma^k+O(k)}$ time and modest space, replacing the previous doubly-exponential integer-programming approach, and that the average density can be computed within the same bound. Using a new connection between minimizer orders and regular languages of charged windows, the paper goes beyond fixed $w$ and identifies, for five small $(\sigma,k)$ pairs, the orders that are eventually optimal as $w\to\infty$, together with the exact minimum densities for every $w\ge 2$. A final result gives the asymptotic form of a new density lower bound for large windows, with the dominant correction term governed by the largest root of $r^k-\sigma r^{k-1}+1$. If the results hold, exact, provably optimal minimizer orders are now available for these parameter pairs at every window size, and the general optimization problem is no longer intractable in principle.

What carries the argument

The load-bearing objects are 'charged windows' — $(w+k)$-windows whose minimal $k$-mer is its prefix or its uniquely occurring suffix — because the density of a minimizer equals the fraction of charged windows among all $(w+k)$-windows. The search algorithm rests on the optimal-prefix lemma: any prefix of an optimal arrangement is itself optimal, so the optimum can be assembled subset-by-subset with a dictionary keyed by the set of $k$-mers already ranked. For the asymptotic analysis, the paper attaches to each order $\rho$ a sequence of canonical DFAs $A_{\rho,i}$ that accept all strings avoiding the first $i$ $k$-mers of $\rho$; the counts of prefix- and suffix-charged windows become walk counts in these automata, and when such an automaton is simple (one nontrivial strongly connected component, with cycle lengths having gcd 1) or flat, Perron–Frobenius theory gives the leading asymptotic term from the dominant eigenvalue $\alpha_{\rho,i}$. Lemma 10 turns differences in these asymptotic counts into strict comparisons between orders, which is what allows the eventual-optimality proofs.

What would settle it

Compute, for the candidate heads in the $\sigma=2,k=5$ and $\sigma=4,k=2$ searches, the strongly connected components of the canonical automata $A_{\rho,i}$ and the gcd of cycle lengths in each component; if any automaton has two components with equal spectral radius or a nontrivial component whose cycle lengths have gcd greater than 1, then the strict eigenvalue dominance required by Lemma 9 fails and the asymptotic comparisons used to prove Theorems 17 and 18 are unsupported.

Watch

Extended reading notes

Core claim

The central claim is that minimum-density minimizers are computable, and in several cases now known exactly. Theorem 4 establishes an algorithm that, for fixed alphabet size $\sigma$, finds an optimal order $(\rho,w)$ in $O(T\cdot 2^{\sigma^k})$ time and $O(\sigma^{k/2}\cdot 2^{\sigma^k})$ space, where $T = \min\{\sigma^{w+k}, w\sigma^{2k}\}$, i.e., $w\cdot 2^{\sigma^k+O(k)}$ time; it works by dynamic programming over subsets of $k$-mers, using the fact that every prefix of an optimal arrangement is optimal and computing each new charged-window count in $O(\min\{\sigma^w, w\sigma^k\})$ time. For the pairs $(\sigma,k) \in \{(2,2),(2,3),(2,4),(2,5),(4,2)\}$, the paper delivers the exact minimum density for all $w\ge 2$ and proves, via the regular-language method, that a specific UHS order is eventually optimal and essentially unique. Theorem 19 states the large-$w$ form of the new lower bound $\beta_1(\sigma,k,w) = \frac{1}{\sigma^k} + \frac{c_{\sigma,k}\alpha_{\sigma,k}^{w+k}+O(1)}{\sigma^{w+k}}$, where $\alpha_{\sigma,k}$ is the largest root of $r^k - \sigma r^{k-1} + 1$ and $c_{\sigma,k} > 0$, with the $O(1)$ improving to $o(1)$ for $\sigma>2$.

Load-bearing premise

The proofs of eventual optimality assume that every automaton arising in the candidate searches has a single dominant repeating component with cycle lengths not all sharing a common factor, an assertion that is stated but only partially checked for the two largest searches.

Editorial extensions

If this is right

The minimum-density problem for constant alphabet $\sigma$ is no longer doubly-exponential: it is solvable in $w\cdot 2^{\sigma^k+O(k)}$ time, making exact optimization feasible for small $k$.
For the five pairs $(2,2),(2,3),(2,4),(2,5),(4,2)$, the minimum density is now known for every window size $w\ge 2$, including the eventually optimal orders and the window sizes at which they take over (e.g., $w_\infty(2,5)=262$).
The average density of a minimizer can be computed within the same single-exponential time bound for all $w$, including the previously open case $w>k$.
The new asymptotic lower bound $\beta_1(\sigma,k,w) \approx \frac{1}{\sigma^k} + \frac{c_{\sigma,k}\alpha_{\sigma,k}^{w+k}}{\sigma^{w+k}}$ with $\alpha$ the largest root of $r^k-\sigma r^{k-1}+1$ gives the first tight large-$w$ lower bound up to $O(1)$ (or $o(1)$).
The regular-language method gives a generic way to compare minimizer orders asymptotically, so the same machinery can be applied to other $(\sigma,k)$ pairs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The subset-DP time bound suggests a natural hardness target: whether single-exponential is optimal, or whether sub-single-exponential is possible, since the search space is $(\sigma^k)!$.
The eventual-optimality results hint that every fixed $(\sigma,k)$ instance may have a unique (up to symmetry) eventually optimal lexmin head; however, the observed takeover window sizes (up to 262) suggest that the practical benefit of eventual optimality may be limited for small $k$.
The $\beta_1$ lower bound could be turned into a practical screening tool for heuristic minimizer constructions, letting researchers compare candidate densities against a tight bound without solving the full search.
The computer-search data show that optimal orders switch among different heads and tails in complex patterns — oscillations, split ranges, and an order optimal at $w=3,4,9$ but not in between — which suggests that simple parametric formulas for optimal orders may not exist.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main contribution here is real. The exact search algorithm in Theorem 4, using the prefix-optimality lemma and subset DP, is a genuine improvement over the ILP approach, and the time bound w·2^{σ^k+O(k)} is clearly stated. The computational results for (2,2) through (2,5) and (4,2), covering all w, are a concrete advance: these exact minimum densities were not known before. The regular-language framework for comparing orders asymptotically is also new, and the eventual-optimality theorems and the β1 lower bound are interesting byproducts. The scripts in Appendix B make the exact computations reproducible, which is good evidence for the main algorithmic claims.

The soft spots are mostly on the asymptotic side. The proofs of Theorems 15–18 rely on Lemma 10, which needs the canonical DFAs in question to be simple or flat. Section 4.1 asserts this holds for all automata in the study, but for the k=5 and σ=4,k=2 searches the verification is not shown in detail. This is a genuine gap: if any of those automata has multiple nontrivial SCCs or a nontrivial SCC with gcd > 1, the asymptotic formulas need extra terms, and the strict growth-rate comparisons that establish eventual optimality would need a more careful argument. I would want that filled in, but I do not think it breaks the paper — the small cases are checked by hand, and the claim is plausible and likely verifiable by a short computation.

One thing I disagree with in the reader's report: the suspected missing combinatorial factor in Theorem 5 is not a real issue. Lemma 1 does imply that ch(ρ,t) depends only on the domain of the first t−1 elements and on ρ[t], because permuting the prefix does not change the charged-window sets for later ranks. The (t−1)! factor in the summation is correct. So the average-density algorithm is fine as written.

The numerical eigenvalue comparisons are another minor weakness: the paper gives approximations like 1.4656 < 1.6180 without fully exhibiting the characteristic polynomials or the rigorous comparison procedure from Remark 20. That is a presentation issue, not a conceptual one.

This paper deserves a serious referee. The exact algorithm and the empirical results are strong enough that the asymptotic proof gaps should be addressed rather than paper rejected. I would send it to review, with the expectation of a major revision that supplies the missing simplicity checks and gives more complete certificates for the growth-rate comparisons.

Referee Report

2 major / 5 minor

Summary. The paper studies the exact minimization of minimizer density for a fixed alphabet size σ and parameters k,w. It presents an algorithm that finds a minimum-density order in O(T·2^{σ^k}) time and O(σ^{k/2}·2^{σ^k}) space with T = min{σ^{w+k}, wσ^{2k}}, improving on the previously known ILP formulation with doubly-exponential worst-case time. It also gives an algorithm for the average density. The second half of the paper develops a regular-language/automata framework (canonical DFAs for finite antidictionaries) to compare minimizer orders asymptotically as w→∞, and uses it to prove eventual optimality and essential uniqueness for (σ,k) ∈ {(2,2),(2,3),(2,4),(2,5),(4,2)}. It further proves a new lower bound for large w. Computationally, the paper reports minimum densities for all w≥2 for those five pairs, including the smallest window sizes at which the eventually optimal order becomes optimal.

Significance. If the asymptotic optimality proofs are completed, this is a substantial contribution. The exact algorithm of Theorem 4 is a genuine improvement over the doubly-exponential ILP approach, and the regular-language method for comparing minimizers at w→∞ is novel and likely to be influential. The paper provides concrete exact densities for infinite families, falsifiable predictions for w∞, and reproducible Python scripts for the exact search, which are notable strengths. The lower bound of Theorem 19 is an additional theoretical contribution. The main risk is the unverified simplicity condition for the automata used in the asymptotic comparisons, which is load-bearing for Theorems 16–18. I also checked the concern that the proof of Theorem 5 misses a combinatorial factor; that concern is not borne out, since for each fixed (t−1)-set U and u∉U, the contribution ch(π·(u),t)·(t−1)! counts exactly the (t−1)! orders with prefix domain U and t-th element u, and Lemma 1 ensures that all have the same ch(ρ,t).

major comments (2)

[Section 4.1, Lemmas 9–10; Theorems 16–18] The eventual-optimality proofs of Theorems 16–18 use Lemma 10 to exclude candidate arrangements by strict growth-rate dominance. Lemma 10 is derived from Lemma 9, whose hypotheses require the canonical DFA A_{ρ,i} to be simple (one nontrivial SCC with gcd of cycle lengths 1) or flat. The paper states in Section 4.1 that 'All instances of DFAs that appear in this study are simple or flat,' but the proofs of Theorems 16–18 do not demonstrate this for every automaton used. For example, in Theorem 17 (σ=2, k=5), iterations 2–13 compare numerical values such as α_5≈1.7902 and α_7≈1.6736 without exhibiting the SCC decomposition or cycle gcds for the A_{ρ,i} behind these numbers, and Theorem 18 (σ=4, k=2) is similar. If any of those automata fails to be simple or flat, Lemma 9 does not apply and the strict dominance used to eliminate candidates is not justified. Please add a proof, or a machine-checkable verification (e.g., a script that computes SCCs and gcds for every automaton arising in the candidate search), or state explicitly where the simplicity of each A_{ρ,i} is established.
[Theorems 16 and 17; Appendix A.4.2; Appendix B] The proofs of Theorems 16 and 17 rely on many numerical eigenvalue and coefficient comparisons (e.g., α_{π,8}≈1.5701<α_{π,16}≈1.6180 in Theorem 16, and α_{12}≈1.1939<α_{26}≈1.3247 in Theorem 17) without providing the characteristic polynomials or automata from which they were computed, and no accompanying code for these asymptotic computations is included in Appendix B. Since these inequalities are load-bearing for the exclusion steps in the iterative candidate search, please include either the automata with their characteristic polynomials or a script that reproduces all constants used in the proofs.

minor comments (5)

[Appendix C] In the table for (σ,k)=(2,4), the row for w≥56 lists (0011,0001,1100,0100,1110,1011,1010,1111,0000), which does not match the order ρ=(0011,0001,1100,0100,1110,1011,0000,0101,1111) from Theorem 16; please check whether this is a typo or a different but equivalent optimal order.
[Theorem 5] The statement of Theorem 5 gives time O(w2^{σ^k+2k}), while the proof yields O(wσ^k2^{σ^k}); for general fixed σ this is O(w2^{σ^k+O(k)}) rather than necessarily +2k. Please reconcile the notation.
[Section 5] The sentence 'the average density is 1+o(1)/σ^k' should read '(1+o(1))/σ^k', as the expression as written is ambiguous.
[Section 4.2] The definition of W_{ρ,i} contains the fragment '⋃_{j=1}^{i+1+1+1} P_{ρ,j}' with an apparent typo in the upper limit; it should presumably be '⋃_{j=1}^{i+1} P_{ρ,j} ∪ ⋃_{j=1}^{i} S_{ρ,j}'.
[Appendix C] Several rows of the tables appear to have lost boldface markup, producing strings such as '001001001' where an individual k-mer is intended (e.g., the row '8+' for (2,3) should presumably be (011,001,101,000,110,111)); please regenerate the tables so that the entries are readable.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the optimality and asymptotic-comparison derivations are self-contained, with only non-load-bearing self-citations.

full rationale

The derivation chain is self-contained. Density is reduced to charged-window counts ch(pi), and the exact search of Theorem 4 directly minimizes ch(pi) over arrangements; Theorem 5 sums the same quantities to obtain average density. The asymptotic comparison machinery is built from standard Perron-Frobenius theory (Lemma 7), a regularity analysis of charged-window languages (Lemma 8), and Lemma 9, which explicitly states its simplicity/flatness hypothesis as a condition rather than assuming the target result. Lemma 10 then compares growth rates with stated constants, and the eventual-optimality proofs apply it to specific automata with computed indices and coefficients. No fitted parameter is renamed as a prediction, and no uniqueness theorem from the author's prior work is invoked to forbid alternatives. The lower bound beta_1 is defined as a minimum over orders of B(rho,n), and Theorem 19 derives its asymptotic form from the characteristic polynomial r^k - sigma r^(k-1) + 1 of the canonical antidictionary automaton, using external Guibas-Odlyzko results and Rouche's theorem; it does not presuppose the eventual-optimality theorems. Self-citations to [5], [6], [20], [21], and [22] supply background, a computational lemma that is also fully proved in Appendix A.1, and a growth-comparison technique with a proof sketch in Remark 20; none of these citations inject the paper's conclusions as premises. The one notable weakness is non-circular: Section 4.1 asserts that all automata arising in the searches are simple or flat, and the proofs of Theorems 16-18 depend on this for the strict growth-rate comparisons via Lemma 10, yet the assertion is not fully demonstrated for the k=5 and sigma=4,k=2 searches. This is a completeness or correctness gap, not a case of the derivation reducing to its own inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters and no new physical or mathematical entities. It relies on standard results in automata theory and Perron-Frobenius theory, plus the domain-specific charged-window characterization from the minimizer literature. The main unstated assumption is the simplicity of the automata that appear in the asymptotic analysis.

assumptions (4)

domain assumption Density of a minimizer equals the fraction of charged (w+k)-windows among all windows
Used to define ch(π) and convert density minimization to charged-window minimization; taken from [24, Lemma 6].
standard math Lemma 12 from Guibas-Odlyzko: languages avoiding k-mers with the same set of periods have identical growth; aperiodic k-mers have smaller growth than periodic ones
Used in Corollary 13 to restrict cand1 and in Theorem 19 to identify the minimal growth rate.
standard math Perron-Frobenius theory and Rouché's theorem
Used in Lemma 7, Lemma 9 and Theorem 19 for asymptotic counts and root localization.
domain assumption The canonical DFAs A_{ρ,i} studied are simple or flat
Assumed to apply Lemma 9's asymptotic formulas; stated in Section 4.1 but not fully shown for all search cases.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Minimizers of Minimum Density." pith.science (2026). https://pith.science/paper/HE3PZKOJ

@misc{pith2026250605277,
  author       = {Pith},
  title        = {Pith review of: On Minimizers of Minimum Density},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HE3PZKOJ}},
  note         = {Machine review of arXiv:2506.05277}
}

abstract

Minimizers are sampling schemes with numerous applications in computational biology. Assuming a fixed alphabet of size $\sigma$, a minimizer is defined by two integers $k,w\ge2$ and a linear order $\rho$ on strings of length $k$ (also called $k$-mers). A string is processed by a sliding window algorithm that chooses, in each window of length $w+k-1$, its minimal $k$-mer with respect to $\rho$. A key characteristic of the minimizer is its density, which is the expected frequency of chosen $k$-mers among all $k$-mers in a random infinite $\sigma$-ary string. Minimizers of smaller density are preferred as they produce smaller samples with the same guarantee: each window is represented by a $k$-mer. The problem of finding a minimizer of minimum density for given input parameters $(\sigma,k,w)$ has a huge search space of $(\sigma^k)!$ and is representable by an ILP of size $\tilde\Theta(\sigma^{k+w})$, which has worst-case solution time that is doubly-exponential in $(k+w)$ under standard complexity assumptions. We solve this problem in $w\cdot 2^{\sigma^k+O(k)}$ time and provide several additional tricks reducing the practical runtime and search space. As a by-product, we describe an algorithm computing the average density of a minimizer within the same time bound. Then we propose a novel method of studying minimizers via regular languages and show how to find, via the eigenvalue/eigenvector analysis over finite automata, minimizers with the minimal density in the asymptotic case $w\to\infty$. Implementing our algorithms, we compute the minimum density minimizers for $(\sigma,k)\in\{(2,2),(2,3),(2,4),(2,5),(4,2)\}$ and \textbf{all} $w\ge 2$. The obtained densities are compared against the average density and the theoretical lower bounds, including the new bound presented in this paper.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 19 canonical work pages

[1]

Automata and forbidden words

Maxime Crochemore, Filippo Mignosi, and Antonio Restivo. Automata and forbidden words. Inf. Process. Lett. , 67(3):111--117, 1998. URL: https://doi.org/10.1016/S0020-0190(98)00104-5

work page doi:10.1016/s0020-0190(98)00104-5 1998
[2]

D. M. Cvetkovi\'c , M. Doob, and H. Sachs. Spectra of graphs. Theory and applications . Johann Ambrosius Barth, Heidelberg, third edition, 1995

work page 1995
[3]

Syncmers are more sensitive than minimizers for selecting conserved k ‑mers in biological sequences

Robert Edgar. Syncmers are more sensitive than minimizers for selecting conserved k ‑mers in biological sequences. PeerJ , 9:e10805, 02 2021. https://doi.org/10.7717/peerj.10805 doi:10.7717/peerj.10805

doi:10.7717/peerj.10805 2021
[4]

A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

Bar s Ekim, Bonnie Berger, and Yaron Orenstein. A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets. In International Conference on Research in Computational Molecular Biology , pages 37--53. Springer, 2020

work page 2020
[5]

Shay Golan and Arseny M. Shur. Expected density of random minimizers. In Rastislav Kr \' a lovic and Vera Kurkov \' a , editors, SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings, Part I , volume 15538 of Lecture Notes in Computer Scie...

work page doi:10.1007/978-3-031-82670-2 2025
[6]

Greedymini: Generating low-density DNA minimizers

Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein, and Arseny Shur. Greedymini: Generating low-density DNA minimizers. bioRxiv , 2025. URL: https://www.biorxiv.org/content/early/2025/02/03/2024.10.28.620726

work page 2025
[7]

The mod-minimizer: A simple and efficient sampling algorithm for long k-mers

Ragnar Groot Koerkamp and Giulio Ermanno Pibiri. The mod-minimizer: A simple and efficient sampling algorithm for long k-mers. In Solon P. Pissis and Wing - Kin Sung, editors, 24th International Workshop on Algorithms in Bioinformatics, WABI 2024 , volume 312 of LIPIcs , pages 11:1--11:23. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024. http...

doi:10.4230/lipics.wabi.2024.11 2024
[8]

L. J. Guibas and A. M. Odlyzko. Maximal prefix-synchronized codes. SIAM J. Applied Math. , 35:401--418, 1978

work page 1978

Show all 24 references

[9]

L. J. Guibas and A. M. Odlyzko. String overlaps, pattern matching, and nontransitive games. J. Comb. Theory A , 30:183--208, 1981

1981
[10]

A near-tight lower bound on the density of forward sampling schemes

Bryce Kille, Ragnar Groot Koerkamp, Drake McAdams, Alan Liu, and Todd J Treangen. A near-tight lower bound on the density of forward sampling schemes. Bioinformatics , 41(1):btae736, 12 2024. URL: https://doi.org/10.1093/bioinformatics/btae736

2024 doi
[11]

Improving the performance of minimizers and winnowing schemes

Guillaume Mar c ais, David Pellow, Daniel Bork, Yaron Orenstein, Ron Shamir, and Carl Kingsford. Improving the performance of minimizers and winnowing schemes. Bioinformatics , 33(14):i110--i117, 2017

2017
[12]

Asymptotically optimal minimizers schemes

Guillaume Marçais, Dan DeBlasio, and Carl Kingsford. Asymptotically optimal minimizers schemes. Bioinformatics , 34(13):i13--i22, 06 2018. https://doi.org/10.1093/bioinformatics/bty258 doi:10.1093/bioinformatics/bty258

2018 doi
[13]

When less is more: sketching with minimizers in genomics

Malick Ndiaye, Silvia Prieto-Ba \ n os, Lucy M Fitzgerald, Ali Yazdizadeh Kharrazi, Sergey Oreshkov, Christophe Dessimoz, Fritz J Sedlazeck, Natasha Glover, and Sina Majidian. When less is more: sketching with minimizers in genomics. Genome Biology , 25(1):270, 2024

2024
[14]

Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing

Yaron Orenstein, David Pellow, Guillaume Mar c ais, Ron Shamir, and Car Kingsford. Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing. PLoS Computational Biology , 13(10):e1005777, 2017

2017
[15]

Efficient minimizer orders for large values of k using minimum decycling sets

David Pellow, Lianrong Pu, Bari s Ekim, Lior Kotlar, Bonnie Berger, Ron Shamir, and Yaron Orenstein. Efficient minimizer orders for large values of k using minimum decycling sets. Genome Research , 33(7):1154--1161, 2023

2023
[16]

Hunt, Stephen M

Michael Roberts, Wayne Hayes, Brian R. Hunt, Stephen M. Mount, and James A. Yorke. Reducing storage requirements for biological sequence comparison . Bioinformatics , 20(18):3363--3369, 07 2004. https://doi.org/10.1093/bioinformatics/bth408 doi:10.1093/bioinformatics/bth408

2004 doi
[17]

Effective sequence similarity detection with strobemers

Kristoffer Sahlin. Effective sequence similarity detection with strobemers. Genome Research , 31(11):2080--2094, 2021. https://doi.org/10.1101/gr.275648.121 doi:10.1101/gr.275648.121

2021 doi
[18]

Salomaa and M

A. Salomaa and M. Soittola. Automata-theoretic aspects of formal power series . Texts and Monographs in Computer Science. Springer-Verlag, New York, 1978

1978
[19]

Wilkerson, and Alex Aiken

Saul Schleimer, Daniel S. Wilkerson, and Alex Aiken. Winnowing: local algorithms for document fingerprinting. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data , SIGMOD '03, page 76–85, New York, NY, USA, 2003. Association for Computing Machi...

2003
[20]

A. M. Shur. Calculating parameters and behaviour types of combinatorial complexity of regular languages. Proc. Inst. Mathematics and Mechanics of Ural Branch of Russian Academy of Sciences , 16(2):270--287, 2010. In Russian. URL: https://www.mathnet.ru/eng/timm568

2010
[21]

Arseny M. Shur. Growth rates of complexity of power-free languages. Theor. Comput. Sci. , 411(34-36):3209--3223, 2010. URL: https://doi.org/10.1016/j.tcs.2010.05.017

2010 doi
[22]

Arseny M. Shur. Languages with a finite antidictionary: Growth-preserving transformations and available orders of growth. In Marie - Pierre B \' e al and Olivier Carton, editors, Developments in Language Theory - 17th International Conference, DLT 2013 , volume 7907 of Lecture...

2013 doi
[23]

Improved design and analysis of practical minimizers

Hongyu Zheng, Carl Kingsford, and Guillaume Mar c ais. Improved design and analysis of practical minimizers. Bioinformatics , 36(Supplement\_1):i119--i127, 2020

2020
[24]

Creating and using minimizer sketches in computational genomics

Hongyu Zheng, Guillaume Mar c ais, and Carl Kingsford. Creating and using minimizer sketches in computational genomics. Journal of Computational Biology , 30(12):1251--1276, 2023

2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Automata and forbidden words

Maxime Crochemore, Filippo Mignosi, and Antonio Restivo. Automata and forbidden words. Inf. Process. Lett. , 67(3):111--117, 1998. URL: https://doi.org/10.1016/S0020-0190(98)00104-5

work page doi:10.1016/s0020-0190(98)00104-5 1998

[2] [2]

D. M. Cvetkovi\'c , M. Doob, and H. Sachs. Spectra of graphs. Theory and applications . Johann Ambrosius Barth, Heidelberg, third edition, 1995

work page 1995

[3] [3]

Syncmers are more sensitive than minimizers for selecting conserved k ‑mers in biological sequences

Robert Edgar. Syncmers are more sensitive than minimizers for selecting conserved k ‑mers in biological sequences. PeerJ , 9:e10805, 02 2021. https://doi.org/10.7717/peerj.10805 doi:10.7717/peerj.10805

doi:10.7717/peerj.10805 2021

[4] [4]

A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

Bar s Ekim, Bonnie Berger, and Yaron Orenstein. A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets. In International Conference on Research in Computational Molecular Biology , pages 37--53. Springer, 2020

work page 2020

[5] [5]

Shay Golan and Arseny M. Shur. Expected density of random minimizers. In Rastislav Kr \' a lovic and Vera Kurkov \' a , editors, SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings, Part I , volume 15538 of Lecture Notes in Computer Scie...

work page doi:10.1007/978-3-031-82670-2 2025

[6] [6]

Greedymini: Generating low-density DNA minimizers

Shay Golan, Ido Tziony, Matan Kraus, Yaron Orenstein, and Arseny Shur. Greedymini: Generating low-density DNA minimizers. bioRxiv , 2025. URL: https://www.biorxiv.org/content/early/2025/02/03/2024.10.28.620726

work page 2025

[7] [7]

The mod-minimizer: A simple and efficient sampling algorithm for long k-mers

Ragnar Groot Koerkamp and Giulio Ermanno Pibiri. The mod-minimizer: A simple and efficient sampling algorithm for long k-mers. In Solon P. Pissis and Wing - Kin Sung, editors, 24th International Workshop on Algorithms in Bioinformatics, WABI 2024 , volume 312 of LIPIcs , pages 11:1--11:23. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024. http...

doi:10.4230/lipics.wabi.2024.11 2024

[8] [8]

L. J. Guibas and A. M. Odlyzko. Maximal prefix-synchronized codes. SIAM J. Applied Math. , 35:401--418, 1978

work page 1978