Minimizer papers

This post is simply a list of brief comments on many papers related to minimizers, and forms the basis of /posts/minimizers/.

1 Overview Link to heading

2 Introduction Link to heading

• Lots of DNA data
• Most algorithms deal with k-mers.
• k-mers overlap, and hence considering all of them is redundant.
• Thus: sample a subset of the kmers.
• Must be ’locally consistent’ and deterministic to be useful.
• Enter random minimizers.
• Parameter $w$: guarantee that at least one k-mer is sampled out of every window of $w$ k-mers.
• Density $d$: (expected) overall fraction of sampled k-mers.
• Obviously, $d\ge 1/w$
• For random mini, $d=2/(w+1)$.
• Lower density => fewer k-mers, smaller indices, faster algorithms.
• Question: How small density can we get for given $k$ and $w$?

Previous reviews Link to heading

• Zheng, Marçais, and Kingsford (2023)
• Ndiaye et al. (2024)

3 Theory of sampling schemes Link to heading

• Broder (1997)

  • Take the $s$ kmers with smallest $s$ hashes, then estimate jaccard similarity based on this.

• Schleimer, Wilkerson, and Aiken (2003)

  • $k$: noise threshold
  • $\ell$: guarantee threshold
  • winnowing: Definition 1: Select minimum hash in each window.
  • Charged contexts to prove a $2/(w+1)$ density, assuming no duplicate hashes (and $k$-mers)
  • local algorithm: Function on k-mer hashes, rather than on window itself: $S(h_i,\dots ,h_{i+w-1})$.
  • Local algorithms have density at least $(1.5+1/2w)/(w+1)$.
  • Conjecture that $2/(w+1)$ is optimal.
  • Robust Winnowing: smarter tie-breaking: same as previous window in case of tie if possible, otherwise rightmost.
  • ’threshold’ $t=w+k-1$
  • order via hash

• Roberts et al. (2004)

  • interior minimizers: Length $w+k-1$ in common, then share minimizer
  • Same heuristic argument for $2/(w+1)$ density, assuming distinct kmers.
  • $w\le k$ guarantees no gaps (uncovered characters) between minimizers
  • end minimizers: minimizers of a prefix/suffix of the string of length $<\ell$.
  • lexicographic ordering is bad on consecutive zeros.
  • ‘Alternating’ order: even positions have reversed order.
  • Increase chance of ‘rare’ k-mers being minimizers.
  • Reverse complement-stable minimizers: $ord(kmer)=min(kmer,rev-kmer)$.
  • Some heuristic argument that sensitivity goes as $k+w/2$.
  • $k<{\log }_{\sigma }(N)$ may have bad sensitivity.

• Marçais et al. (2017)

  • Main goal is to disprove the $2/(w+1)$ conjectured lower bound.
  • States that Schleimer, Wilkerson, and Aiken (2003) defines a local scheme as only having access to the sequence within a window, but actually, it only has access to the hashes.
  • UHS to obtain ordering with lower density than lex or random.
  • DOCKS goes below $1.8/(w+1)$, so the conjecture doesn’t hold.
  • Random order has density slightly below $2/(w+1)$.
  • Defines density factor $d_f=d\cdot (w+1)$.11

    I am not a fan of this, since the lower bound is $1/w$, no scheme can actually achieve density factor $1$. Calibrating the scale to the (somewhat arbirary) random minimizer, instead of to the theoretical lower bound does not really make sense to me. 

  • UHS sparsity $SP(U)$: the fraction of contexts containing exactly one k-mer from the $U$.
    • $d=2/(w+1)\cdot (1-SP(U))$
  • The density of a minimizer scheme can be computed on a De Bruin sequence of order $k+w$.
  • The density of a local scheme can be less than $2/(w+1)$.
  • Does not refute the $(1.5+1/2w)/(w+1)$ lower bound.

• Marçais, DeBlasio, and Kingsford (2018)

  • Properly introduces $local\supseteq forward\supseteq minimizers$.

  • Realizes that $(1.5+1/2w)/(w+1)$ lower bound is only for randomized local schemes.

  • Studies asymptotic behaviour in $k$ and $w$

  • For $k\to \mathrm{\infty }$, a minimizer scheme with density $1/w$.

  • For $w\to \mathrm{\infty }$, a $1/{\sigma }^k$ lower bound on minimizer schemes.

    • Forward schemes can achieve density $O(1/\sqrt{w})$ instead, by using $k^{\prime }={\log }_{\sigma }(\sqrt{w})$ instead.

  • A lower bound on forward schemes of $\frac{1.5+1/2w+max(0,\lfloor (k-w)/w\rfloor )}{w+k}$.

    • Proof looks at two consecutive windows and the fact that half the time, the sampled kmers leave a gap of $w$ in between, requiring an additional sampled kmer.

  • Local schemes can be strictly better than forward, found using ILP.

  • New lower bound on forward schemes.

  • For local schemes, a De Bruijn sequence of order $2w+k-2$ can be used to compute density.

  • UHS-minimizer compatibility.

  • Naive extension for UHS: going from $k$ to $k+1$ by ignoring extra characters.

  • Construction of asymptotic in $k\to \mathrm{\infty }$ scheme is complex, but comes down to roughly: for each $i\in [w]$, sum the characters in positions $i(\mathrm{mod}w)$. Take the k-mer the position $i$ for which the sum is maximal. (In the paper it’s slightly different, in that a context-free version is defined where a k-mer is ‘good’ if the sum of it’s $0(\mathrm{mod}w)$ characters is larger than the sums for the other equivalence classes, and then there is an argument that good kmers close to a UHS, and turning them into a real UHS only requires ‘few’ extra kmers.)

  • $d(k,w)$ is decreasing in $w$.

• Edgar (2021)

  • Introduces open syncmers, closed syncmers
  • context free: each kmer is independently selected or not
  • Conservation: probability that a sampled kmer is preserved under mutations.
  • context-free sampled kmers are better conserved.

• Shaw and Yu (2021)

  • Formalizes conservation: the fraction of bases covered by sampled kmers.
  • k-mer selection method: samples any kind of subset of kmers
  • $q$-local selection method: $f$ looks at a $k+q-1$-mer, and returns some subset of kmers.
  • word-based method: a ‘context free’ method where for each k-mer it is decided independently whether it is sampled or not.

• Belbasi et al. (2022)

  • The jaccard similarity based on random minimizers is biased.

• Golan and Shur (2025)

  • The random minimizer has density just below $2/(w+1)$ when $k>w$ and $w$ is sufficiently large.
  • $O(w^2)$ method to compute the exact density of random minimizer.
  • The $2/j$ and $1/j$ fractions were observed before in (Marçais et al. 2017)

• Kille et al. (2024)

  • Lower bound on density of $\frac{1}{w+k}\lceil \frac{w+k}{w}\rceil$.
  • Tighter version by counting pure cycles of all lengths.
  • Instead of $k$, can also use the bound for $k^{\prime }\ge k$ with $k\equiv 1(\mathrm{mod}w)$.

• Zheng, Kingsford, and Marçais (2021a)

  • UHS-minimizer compatibility; remaining path length $L\le \ell$
  • $d\le |U|/{\sigma }^k$.
  • Mentions decycling set of Mykkeltveit (1972)
  • Theorem 2: Forward sampling scheme with density $O(\ln (w)/w)$ (where $k$ is small/constant), and a corresponding UHS.
  • selection scheme: selects positions rather than kmers, i.e., $k=1$.
  • Assumes $w\to \mathrm{\infty }$, so anyway $k=O(1)$ or $k=1$ are kinda equivalent.
  • Theorem 1: local scheme implies $(2w-1)$-UHS, forward scheme implies $(w+1)$-UHS.
  • Theorem 3: Gives an upper and lower bound on the remaining path length of the Mykkeltveit set: it’s between $c_1\cdot w^2$ and $c_2\cdot w^3$.
  • Local schemes: $w-1$ ’looking back’ context for $2w+k-2$ total context size.
    • The charged contexts are a UHS.
  • $O(\ln (w)/w)$ forward scheme construction:
    • Definition 2 / Lemma 2: The set of words that either start with $0^d$ or do not contain $0^d$ at all is a UHS. Set $d={\log }_{\sigma }(w/\ln w)-1$. This has longest remaining path length $w-d$.
    • Then a long proof that the relative size is $O(\ln (w)/w)$.
    • (In hindsight: this is a variant of picking the smallest substring, as long as it is sufficiently small.)
  • Questions:
    • We can go from a scheme $f$ to a UHS. Can we also go back?
    • Does a perfect selection scheme exist?

• Zheng, Kingsford, and Marçais (2020)

  • For $w\to \mathrm{\infty }$, minimizer schemes can be optimal (have density $O(1/w)$) if and only if $k\ge {\log }_{\sigma }(w)-O(1)$. In fact, the lexicographic minimizer is optimal.
  • When $k\ge (3+\epsilon ){\log }_{\sigma }(w)$, the random minimizer has expected density $2/(w+1)+o(1/w)$, fixing the proof by (Schleimer, Wilkerson, and Aiken 2003).
  • When $\epsilon >0$ and $k>(3+\epsilon ){\log }_{\sigma }w$, the probability of duplicate k-mers in a window is $o(1/w)$.
    • TODO: Hypothesis: the $3$ could also be a $2$, or actually even a $1$?
  • turn charged contexts of a minimizer scheme into a $(w+k)$-UHS. (skipped)
  • Relative size of UHS is upper bound on density of compatible minimizer.

• (Chikhi et al. 2014)

  • Order k-mers by their frequency in the dataset.

3.1 Questions Link to heading

Main question: What is the lowest possible density for given $(k,w)$?

The first questions:

• What is a scheme

type:

• sampling scheme: sample k-mer
• selection scheme: sample position ($k=1$)

This question is then approached from two sides:

• Lower bounds on density for $(k,w,\sigma )$?
• Tight lower bounds for some parameters?
• Tight lower bounds, asymptotic in parameters (e.g., $\sigma \to \mathrm{\infty }$)?
• Can we make tight lower bounds for all practical parameters?
• If not, can we understand why the best schemes found (using ILP) do not reach know bounds?

And:

• What is the empirical density of existing schemes?
• Can we model existing schemes and compute their density exactly?
• Can we make near-optimal schemes (say, within $1\mathrm{\%}$ from optimal) for practical parameters?
• Can we make exactly optimal schemes, for asymptotic parameters?
• Can we make optimal schemes for practical parameters?
• Can we make ‘pure’ optimal schemes, that do not require exponential memory?
• If we can not make pure optimal schemes, can we bruteforce search for them instead?

3.2 Types of schemes Link to heading

scope:

• global (frac-sampling, mod-sampling sampling every $n$-th kmer)
• local
• forward
• minimizer

3.3 Parameter regimes Link to heading

• small $k$: $k<{\log }_{\sigma }(w)$
• large $k$: $k\gg w$ or $k\to \mathrm{\infty }$.
• ‘practical’: $4\le k\le 2w$ with $w\le 20$ or so; depends on the application.
• binary/DNA alphabet $\sigma \in \{2,4\}$.
• large/infinite alphabet, $\sigma =256$ or $\sigma \to \mathrm{\infty }$.

3.4 Different perspectives Link to heading

• charged contexts of length $w+1$.
• pure cycles of length $w+k$.
• long random strings.

3.5 UHS vs minimizer scheme Link to heading

• UHS is a minimizer scheme where everything has hash/order $0$ or $1$.

3.6 (Asymptotic) bounds Link to heading

3.7 Lower bounds Link to heading

4 Minimizer schemes Link to heading

4.1 Orders Link to heading

4.2 UHS-based and search-based schemes Link to heading

• Orenstein et al. (2016, 2017)
  • Introduces UHS
  • DOCKS finds a UHS
  • Finding optimal UHS is hard when a set of strings to be hit is given. (But here we have a DBg, which may be easier.)
  • The size of a UHS may be much smaller than the set of all possible minimizers.
  • DOCKS UHS density is close to optimal (?)
  • Step 1: Start with the Mykkeltveit embedding
  • Step 2: repeatedly find a vertex with maximal ‘hitting number’ of $\ell$-long paths going through it, and add it to the UHS (and remove it from the graph.)
  • DOCKSany: compute number of paths of any length, instead of length $\ell$.
  • DOCKSanyX: remove the top $X$ vertices at a time.
  • Applies ’naive extension’ to work for larger $k$.
  • Runs for (many) hours to compute UHS for $k=11$ already.
  • An ILP to improve UHSes found by DOCKS; improves by only a few percent at best.
  • DOCKS selects far fewer distinct kmers compared to random minimizers, and has slightly lower density.
  • Does not use a compatible minimizer order.
• DeBlasio et al. (2019)
  • Extends UHS generated by DOCKS
  • larger $k$ up to $200$, but $L\le 21$.
  • Merges UHS with random minimizer tiebreaking.
  • Mentions sparsity
  • Starts with UHS for small $k$ and grows one-by-one to larger $k$. Full process is called reMuval.
    • First, naive extension
    • Second, an ILP to reduce the size of the new UHS and increase the number of singletons: windows containing exactly one kmer. (Since density directly correlates with sparsity.)
  • Naive extension can decrease density
  • Remove kmers from the UHS that always co-occur with another k-mer in every window.
  • ILP is on whether each kmer is retained in the UHS or not, such that every window preserves at least one element of the UHS.
  • Also does sequence-specific minimizers
• Ekim, Berger, and Orenstein (2020)
  • Improves DOCKS using randomized parallel algorithm for set-cover.
  • Faster computation of hitting numbers.
  • Scales to $k\le 16$.
• Hoang, Zheng, and Kingsford (2022)
  • Learns a total order, instead of a UHS.
  • Continuous objective, rather than discrete.
  • UHSes are ‘underspecified’ since the order withing each component is not given. Determining the permutation directly is more powerful.
  • Around $5\mathrm{\%}$ better than PASHA.
• Golan et al. (2024)
  • Unlike UHS-based methods that optimize UHS size, this directly optimizes minimizer density by minimizing the number of charged context:
    • Repeatedly pick the next kmer as smallest that is in the smallest fraction of charged contexts.
    • Then do some noise (slightly submoptimal choices), and local search with random restarts on top.
  • Builds scheme for alphabet size ${\sigma }^{\prime }=2$ and $k^{\prime }\le 20$ which is extended to $\sigma =2$ and to larger $k$ if $k>20$.
  • Achieves very low density. Open question how close to optimal.
  • Not ‘pure’: requires the memory to store the order of kmers.
• Zheng, Kingsford, and Marçais (2021b)
  • Polar set intersects each $w$-mer at most once.
  • Two kmers in a polar set are at least $(w+1)/2$ apart.
  • Lemma 4: Formula for probability that a window is charged, in terms of number of unique kmers.
  • Progressively add ’layers’ to the polar set to fill gaps.
  • Heuristic: greedily try to pick kmers that are exactly $w$ apart, by choosing a random offset $o\in [w]$, and adding all those kmers as long as they aren’t too close to already chosen kmers.
    • Up to 7 rounds in practice.
  • Filter too frequent kmers.
  • Significantly improved density over other methods.
  • Requires explicitly storing an order.

4.3 Pure schemes Link to heading

• Zheng, Kingsford, and Marçais (2020)
  • Considers all closed syncmers in a window. Picks the smallest one.
  • Parameter $k_0$ (we call it $s$): the length of the hashed ‘inner’ slices.
  • For $k>w+O({\log }_{\sigma }(w))$, has density below $1.67/w+o(1/w)$.
    • This requires a long proof.
  • First scheme with guaranteed density $<2/(w+1)$ when $k\approx w$ (instead $k\gg w$).
  • Does not require expensive heuristics for precomputation; no internal storage.
  • Charged contexts or a $(w_0,k_0)$ minimizer are the UHS of the $(w,k=w_0+k_0)$ minimizer, as long as $w\ge w_0$.
• Pellow et al. (2023)
  • MDS: a set of k-mers that hits every cycle in the DBg.
  • Mykkeltveit embedding: map each k-mer to a complex number. Take those k-mers with argument (angle) between $0$ and $2\pi /k$ as context-free hitting set.
  • Take a compatible minimizer.
  • Even better: prefer argument in $[0,2\pi /k)$, and otherwise prefer argument $[\pi ,\pi +2\pi /k)$.
  • Great density for $k$ just below $w$.
  • MDS orders outperform DOCKS and PASHA.
  • Scales to larger $k$
• Groot Koerkamp and Pibiri (2024)
  • For $k>w$, look at $t=kmodw$-mers instead. If the smallest $t$-mer is at position $x$, sample the $k$-mer at position $xmodw$.
  • Asymptotic optimal density as $w\to \mathrm{\infty }$.
  • Close to optimal for large alphabet when $k\equiv 1(\mathrm{mod}w)$.
• Groot Koerkamp, Liu, and Pibiri (2025)
  • Extend miniception to open syncmers, and open followed by closed syncmers.
  • Extend modmini to wrap any other sampling scheme.
  • Simple and very efficient scheme, for any $k$.
  • Greedymini has lower density, but is more complex.

4.4 Other variants Link to heading

• Kille et al. (2023)
  • Sample the smallest $s$ k-mers from each $s\cdot w$ consecutive k-mers.
• Irber et al. (2022)
  • Sample all kmers with hash below $max\cdot f$.
• (Chikhi et al. 2014)
  • Frequency aware minimizers TODO
• Alanko, Biagi, and Puglisi (2024)
  • frequency bounded minimizers, with frequency below $t$
  • Prefers rare kmers as minimizers
  • variable length scheme.
  • Shortest unique finimizers
  • Uses SBWT to work around ’non-local’ property.
  • Useful for SSHash-like indices.
  • Defines DSPSS: Disjoint spectrum preserving string set.
  • For each kmer, find the shortest contained substring that occurs at most $t$ times in the DBg of the input.
  • (TODO: I’m getting a bit lost on the technicalities with the SBWT.)

Selection schemes Link to heading

These have $k=1$

• Loukides and Pissis (2021; Loukides, Pissis, and Sweering 2023)
  • In each window, sample the position that starts the lexicographically smallest rotation.
  • Avoid sampling the last $r\approx {\log }_{\sigma }(w)$ positions, as they cause ‘unstable’ anchors.

Canonical minimizers Link to heading

• Pan and Reinert (2024)
  • Choose the strandedness via higher CG-content.
• Wittler (2023)
  • TODO
• Marçais, Elder, and Kingsford (2024)
  • TODO

4.5 Non-overlapping string sets Link to heading

• Levenshtein (1970)
  • Shows a bound on max number of non-overlapping words of $$\frac{1}{k}{\left(\frac{k-1}{k}\right)}^{k-1}{\sigma }^k$$
• Blackburn (2015)
  • divide alphabet into two parts. Then patterns abbbb and e.g. aab?b?b?b are non-overlapping. (b: any non-a character)
  • For DNA, optimal solution (max number of pairwise non-overlapping words) for $k=2$ is [AG][CT], while for $k\in \{3,4,5,6\}$, an optimal solution is given by A[CTG]+.
  • Re-prove upper bound on number of non-overlapping words ${\sigma }^k/(2k-1)$.
  • Re-prove upper bound of Levenshtein above.
  • Show existing scheme with size $$\frac{\sigma -1}{e\sigma }\frac{{\sigma }^k}{k}$$
  • New scheme: not $0$ and $>0$, but arbitrary partition. And prefix is in some set $S$, while suffix is $S$-free.
    • When $k$ divides $\sigma$, choose $|I|=\sigma /k$ and $|J|=\sigma -\sigma /k$, and consider strings IIIIIIJ. These are optimal.
    • The set $S$ is needed to avoid rounding errors when $\sigma$ is small.
    • Conjecture: a suffix of JJ or longer is never optimal.
• Frith, Noé, and Kucherov (2020)
  • minimally overlapping words are anti-clustered, hence good for sensitivity.
  • cg-order: alternate small and large characters, as (Roberts et al. 2004)
  • abb-order: compare first character normal, the rest by t=g=c<a.
• Stanovnik, Moškon, and Mraz (2024)
  • ILP to solve the problem for more $(k,\sigma )$ pairs.
• Frith, Shaw, and Spouge (2023)
  • Test various word-sets for their sparsity and specificity.
• Champarnaud, Hansel, and Perrin (2004)