1 Theory of sampling schemes

$$ \newcommand{\O}{\mathcal O} \newcommand{\order}{\mathcal O} \newcommand{\Ok}{\mathcal O_k} \newcommand{\Ot}{\mathcal O_t} \newcommand{\Os}{\mathcal O_s} \newcommand{\S}{\Sigma} \newcommand{\Dk}{\mathcal D_k} \newcommand{\Dtk}{\tilde{\mathcal D}k} \newcommand{\P}{\mathbb P} \newcommand{\pr}{\mathbb P} \DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\poly}{poly} \DeclareMathOperator*{\rc}{rc} \DeclareMathOperator*{\sp}{sparsity} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\c}{\mathrm{c}} \newcommand{\boldremuval}{\mathbf{ReM}{\mathbf{u}}\mathbf{val}} \newcommand{\remuval}{\mathrm{ReM}_{\mathrm{u}}\mathrm{val}} $$

1.1 Introduction

As does nearly every paper in bioinformatics, we will start here with the remark that the amount of biological data has been and still is increasing rapidly over time. Thus, both faster and more space efficient algorithms are needed to analyse this data. One popular method for sequence analysis is to consider a sequence as its set of $k$-mers, i.e., the set of substrings of length \(k\), which often has a value up to \(31\). Then, two sequences can be compared by comparing these sets, rather than by doing a costly alignment between them. For example, when comparing two human genomes, there will likely be relocations and inversions of long segments of DNA, so that a global alignment is not the best way forward. By instead only considering $k$-mers, we only consider the local structure, so that the changes in global structure do not affect the analysis. Then one could estimate the similarity of these sets using min-hash (Broder 1997; Kille et al. 2023). Or one could seed an alignment by finding $k$-mer matches between the two sequences, as done by minimap (Li 2016).

A drawback of considering the full set of $k$-mers is that consecutive $k$-mers overlap, and thus that there is a lot of redundancy. To compress the set of $k$-mers, it would be preferable to only sample every \(k\)’th $k$-mer, so that each base is covered only exactly once. That, however, doesn’t work: if we are given two sequences, but one is shifted by one due to an inserted base at the very start, no common $k$-mers will be sampled. To fix this, we would like a locally consistent sampling method, that decides whether or not to sample a $k$-mer only based on the $k$-mer and some surrounding context. One option is to use all $k$-mers that start with an A, or to use all $k$-mers whose (lexicographic or hashed) value is sufficiently small. Indeed, this approach is sufficient for some applications.

A drawback of the methods so far is that there could be long stretches of input without any sampled $k$-mers. This can cause long gaps when seeding alignments. Also when building text indices, such as a sparse suffix array (Grabowski and Raniszewski 2017; Ayad, Loukides, and Pissis 2023) or a minimizer-space De Bruijn graph (Ekim, Berger, and Chikhi 2021), we usually need a guarantee that at least one k-mer is sampled every, say, \(w\) positions.

Sampling scheme. This brings us to local sampling schemes that satisfy a window guarantee: given a window of \(w\) $k$-mers, consisting of \(w+k-1\) characters, a sampling scheme returns one of the $k$-mers as the one to be sampled. If we now slide this window along the input, we collect the set of sampled $k$-mers. Ideally the scheme ensures that the same $k$-mer is sampled from adjacent windows, so that this set is much smaller than the total number of $k$-mers.

Given such a sampling scheme, we can build a locality sensitive hash: given a string of length \(w+k-1\), we can hash it to its sampled $k$-mer. This way, adjacent strings are likely to have the same hash, allowing for efficient indices such as LPHash and SSHash (Pibiri, Shibuya, and Limasset 2023; Pibiri 2022).

Problem statement. The goal now is to find $k$-mer sampling schemes that satisfy the \(w\) window guarantee, while overall sampling as few $k$-mers as possible.

This is formalized in the density: the expected fraction of $k$-mers sampled by a scheme. The window guarantee imposes a trivial lower bound of \(1/w\), since at least every \(w\)’th $k$-mer must be sampled.

The most common practical scheme is the random minimizer (Roberts et al. 2004; Schleimer, Wilkerson, and Aiken 2003), which hashes all $k$-mers in the window, and chooses the smallest one. This has a density of \(2/(w+1)\), roughly twice as large as the trivial lower bound.

Now, you may ask whether it’s worth the effort to at best save a factor two of memory and speed, and you would not be alone. I asked myself this same question long before becoming interested in minimizers (at RECOMB 2022):

TODO: Turn into a proposition

Why would we even care about better minimizer? We have this simple and fast random minimizer that’s only at most \(2\times\) away from optimal. Why would anyone invest time in optimizing this by maybe \(25\%\)? There are so much bigger gains possible elsewhere.

Even worse, in practice, most schemes do not (and as we will see, can not) give more than a \(20\%\) saving in density on top of the very simple random minimizer.

As we will prove in Section 2, when \(k\leq w+1\), we can never expect more than around \(25\%\) lower density than the random minimizer, and thus, existing schemes are already relatively close to optimal from a practical point of view. Given this new lower bound, maybe the answer is that, indeed, we should stop searching for further schemes.

Nevertheless, there is a lot of pretty maths to be found, both in the lower bounds, and in the many sampling schemes we will review and develop ourselves.

1.2 Overview

The remainder of this chapter is split into three parts.

First, in Section 1.3, we review the existing theory of sampling schemes. This covers, for example, local, forward, and minimizer schemes, the density of the random minimizer, and a number of theoretical results on the optimal asymptotic density of schemes as \(k\to\infty\) or \(w\to\infty\).

In Section 2, we go over existing lower bounds. We start at the original one of Schleimer, Wilkerson, and Aiken (2003), that turns out to make overly strong assumptions, and end with the new nearly tight lower bound of (Kille et al. 2024).

Then, in Section 3, we summarize and compare existing sampling schemes, and introduce two new sampling schemes: the open-closed minimizer and the general mod-minimizer (Groot Koerkamp and Pibiri 2024; Groot Koerkamp, Liu, and Pibiri 2025). The most important result is that the mod-minimizer achieves density \(1/w\) in the limit where \(k\to\infty\), and that this convergence is close to optimal.

Lastly, in Section 4, we consider the special case where \(k=1\). Here, we first introduce the bd-anchor, and then improve this into the sus-anchor with anti-lexicographic sorting. This has density very close to optimal for alphabet size \(\sigma=4\), and raises the question whether perfectly optimal selection schemes can be constructed.

Many of the existing papers on sampling schemes touch more than one of these topics, as they both develop some new theory and introduce a new sampling scheme. These results are thus split over the applicable sections.

Previous reviews. This chapter is written from a relatively theoretical perspective, and focuses on the design of low-density sampling schemes. The review Zheng, Marçais, and Kingsford (2023) takes a more practical approach and compares applications, implementations, and metrics other than just the density. It limits itself to minimizers, rather than more general local or forward schemes. A second review, Ndiaye et al. (2024), focuses specifically on applications, and details how minimizers are used in various tools and domains of bioinformatics.

1.3 Theory of sampling schemes

The theory of minimizer schemes started with two independent papers proposing roughly the same idea: winnowing (Schleimer, Wilkerson, and Aiken 2003) in 2003 and minimizers Roberts et al. (2004) in 2004. At the core, the presented ideas are very similar: to deterministically sample a $k$-mer out of each window of w consecutive $k$-mers by choosing the ‘‘smallest’’ one, according to either a random of lexicographic order. The window guarantee is a core property of minimizers: it guarantees that consecutive minimizers are never too far away from each other. Further, these schemes are local: whether a $k$-mer is sampled as a minimizer only depends on a small surrounding context of \(w-1\) characters, and not on any external context. This enables the use of minimizers for locality sensitive hashing (Pibiri, Shibuya, and Limasset 2023; Pibiri 2022), since the minimizer is a deterministic key (hash) that is often shared between adjacent windows.

While the winnowing paper was published first, the ‘minimizer’ terminology is the one that appears to be used most these days. Apart from terminology, also notations tend to differ between different papers. Here we fix things as follows.

1.4 Notation

Throughout this chapter, we use the following notation. For \(n\in \mathbb N\), we write \([n]:=\{0, \dots, n-1\}\). The alphabet is \(\S = [\sigma]\) and has size \(\sigma =2^{O(1)}\), so that each character can be represented with a constant number of bits. For all evaluations we will use the size-4 DNA alphabet, but for examples we usually use the plain ABC..XYZ alphabet. Given a string \(S\in \S^*\), we write \(S[i..j)\) for the sub-string starting at the \(i\)’th character, up to (and not including) the \(j\)’th character, where both \(i\) and \(j\) are $0$-based indices. A $k$-mer is any (sub)string of length \(k\).

In the context of minimizer schemes, we have a window guarantee \(w\) indicating that at least one every \(w\) $k$-mers must be sampled. A window is a string containing exactly \(w\) $k$-mers, and hence consists of \(\ell:=w+k-1\) characters. We will later also use contexts, which are sequences containing two windows and thus of length \(w+k\).

1.5 Types of sampling schemes

In practice, we usually require \(w\geq 2\) and \(k\geq 1\), as some theorems break down at either \(w=1\) or \(k=0\). When \(k \geq w\), such a scheme ensures that every single character in the input is covered by at least one sampled $k$-mer.

Forward scheme have the property that as the window \(W\) slides through an input string \(S\), the position in \(S\) of the sampled $k$-mer never decreases.

Minimizer schemes are always forward, and thus we have the following hierarchy

\[ \textrm{minimizer schemes} \subseteq \textrm{forward schemes} \subseteq \textrm{local schemes}. \]

There are two particularly common minimizer schemes, the lexicographic minimizer (Roberts et al. 2004) and the random minimizer (Schleimer, Wilkerson, and Aiken 2003).

Following Zheng, Kingsford, and Marçais (2021a), we also define a selection scheme, as opposed to a sampling scheme. Note though that this distinction is not usually made in other literature.

We will consistently use select when \(k=1\), and sample when \(k\) is arbitrary. When \(k=1\), we also call the sampled position an anchor, following bd-anchors (Loukides, Pissis, and Sweering 2023). Note that a minimizer selection scheme is not considered, as sampling the smallest character can not have density below \(1/\sigma\).

Since all our schemes must sample at least one $k$-mer from every \(w\) consecutive positions, they naturally have a lower bound on density of \(1/w\).

As we will see, for sufficiently large \(k\) the density of the random minimizer is \(2/(w+1) + o(1/w)\). There is also the notion of density factor (Marçais et al. 2017), which is defined as \((w+1)\cdot d(f)\). Thus, random minimizers have a density factor of \(2\). While this is convenient, we refrain from using density factors here, because it would be more natural to relate the density to the lower bound of \(1/w\) instead, and use \(w\cdot d(f)\). Specifically, as defined, the density factor can never reach the natural lower bound of \(1\), because \((w+1)\cdot \frac 1w = 1+1/w > 1\).

Now that we have defined the density, the natural question to ask is:

Since the classes of forward and local schemes are larger, they can possibly achieve lower densities, but by how much? The ideal is to answer some of these questions by proving a lower bound and providing a scheme that has density equal to this lower bound, ideally for all parameters, but otherwise for a subset. We can also ask what happens when \(w\to \infty\) (for \(k\) fixed), or when \(k\to\infty\) (for \(w\) fixed)? And can how does this depend on the alphabet size? Or maybe we can not quite make schemes that exactly match the lower bound, but we can make schemes that are within \(1\%\) of the lower bound, or that are asymptotically a factor \(1+o(1)\) away.

There are also different parameter regimes to consider: small \(k=1\) or \(k<\log_\sigma(w)\), slightly larger \(k\leq 10\), and more practical \(k\) up to \(\approx 30\), or even larger \(k\) in theory. Similarly, we can consider small \(w\leq 10\), but also \(w\approx 1000\) is used in practice. The alphabet size will usually be \(\sigma=4\), but also this can vary and can be \(\sigma=256\) for ASCII input.

If we do find (near) optimal schemes, we would like these to be pure in some way: ideally we can provide a simple analysis of their density, as opposed to only being able to compute it without any additional understanding. This somewhat rules out solutions found by brute force approaches, as they often do not provide insight into why they work well. This motivates the following definition.

1.6 Computing the density

The density of a sampling scheme is defined as the expected particular density on an infinitely long string. In practice, we can approximate it closely by simply computing the particular density on a sufficiently long random string of, for example, 10 million characters.

When \(\sigma^{w+k}\), the following theorem forms the basis for computing the density of schemes exactly (Lemma 4 Marçais et al. 2017; Zheng, Kingsford, and Marçais 2020):

For a local scheme, a context has length \(2w+k-1\) instead (Section 3.1 Zheng, Kingsford, and Marçais 2021a; Section 3.2 Kille et al. 2024), and is charged when the last window samples a $k$-mer not sampled by any of the previous contained windows. This larger context is necessary because a local scheme can jump backwards. In practice, this

As a small variant on this, in Schleimer, Wilkerson, and Aiken (2003), a window is charged when it is the first window to sample a $k$-mer.

We can also approximate the density by sampling sufficiently many random contexts. A somewhat more efficient method is to use a De Bruijn sequence instead. A De Bruijn sequence of order \(c\) is any circular sequence of length \(\sigma^c\) that contains every sequence of length \(c\) exactly once (De Bruijn 1946). We have the following theorem, again by (Lemma 4 Marçais et al. 2017):

Another approach, that follows from the first, is by considering cycles of length \(c\), rather than just strings of length \(c\).

1.7 The density of random minimizers

As a warm-up, we will compute the density of the random minimizer. We mostly follow the presentation of Zheng, Kingsford, and Marçais (2020).

We start by analysing when a context is charged (Lemma 1 Zheng, Kingsford, and Marçais 2020).

Before computing the actual density, we need to bound the probability that a window contains two identical $k$-mers (Lemma 9 Zheng, Kingsford, and Marçais 2020).

In practice, \(k > (2+\varepsilon) \log_\sigma( c)\) seems to be sufficient, but this has not been proven yet. Even stronger, for most applications of the lemma, \(k>(1+\varepsilon)\log_\sigma( c)\) appears sufficient.

This leads us to the density of the random minimizer (Theorem 3 Zheng, Kingsford, and Marçais 2020), which is a more refined version of the simple density of \(2/(w+1)\) computed in both Schleimer, Wilkerson, and Aiken (2003) and Roberts et al. (2004).

Using a more precise analysis, it can be shown that for sufficiently large \(k\), the random minimizer has, in fact, a density slightly below \(2/(w+1)\). In Marçais et al. (2017) this is shown using universal hitting sets. In (Theorem 4 2025), it is shown that the density of the random minimizer is less than \(2\) for all sufficiently large \(k\geq w\geq w_0\), where \(w_0\) is a constant that may depend on the alphabet size \(\sigma\).

It was originally conjectured that the density of \(2/(w+1)\) is the best one can do (Schleimer, Wilkerson, and Aiken 2003), but this has been refuted by newer methods, starting with DOCKS (Orenstein et al. 2017; Marçais et al. 2017). (Although it must be remarked that the original conjecture is for a more restricted class of ‘’local’’ schemes than as defined here.)

1.8 Universal hitting sets

Universal hitting sets are an alternative way to generate minimizer schemes. They were first introduced by (Orenstein et al. 2016, 2017).

Universal hitting sets are an example of a context-free scheme (Edgar 2021), where each $k$-mer is sampled only if it is part of the UHS:

There is a tight correspondence between universal hitting sets and minimizer schemes (Section 3.3 Marçais et al. 2017; Section 2.1.5 Marçais, DeBlasio, and Kingsford 2018; Zheng, Kingsford, and Marçais 2021a):

The density of a compatible minimizer scheme is closely related to the size of the universal hitting set (Lemma 1 Marçais, DeBlasio, and Kingsford 2018).

From this, it follows that creating smaller universal hitting sets typically leads to better minimizer schemes.

Lastly, Marçais et al. (2017) introduces the sparsity of a universal hitting set \(U\) as the fraction of contexts of \(w+k\) characters that contain exactly one $k$-mer from \(U\). Then, the density of a corresponding minimizer scheme can be computed as \((1-\sp(U))\cdot \frac{2}{w+1}\).

Minimum decycling set. Where a universal hitting set is a set of $k$-mers such that every length \(w+k-1\) window contains a $k$-mer in the UHS, a minimum decycling set (MDS) is a smallest set of $k$-mers that hits every infinitely long string. Equivalently, if we take the complete De Bruijn graph of order \(k\) and remove all nodes in the MDS from it, this should leave a graph without cycles. It can be seen that the number of pure cycles (corresponding to the rotations of some string of length \(k\)) in the De Bruijn graph is a lower bound on the size of an MDS, and indeed this lower bound can be reached.

Mykkeltveit MDS. One construction of an MDS is by Mykkeltveit (Mykkeltveit 1972). To construct this set \(\Dk\), $k$-mers are first embedded into the complex plane via a character-weighted sum of the \(k\) \(k\)’th roots of unity \(\omega_k\): a $k$-mer \(K\) is mapped to \(x=\sum_i K_i\cdot\omega_k^i\). This way, shifting a $k$-mer by one position corresponds to a rotation, followed by the addition or subtraction of a real number. Based on this, \(\Dk\) consists of those $k$-mers whose embedding \(x\) corresponds to the first clockwise rotation with positive imaginary part, i.e., such that \(\pi-2\pi/k\leq \arg(x)<\pi\).

1.9 Asymptotic results

In Table 1, we summarize a few theoretical results on the asymptotic density of minimizer, forward, and local schemes as \(k\to\infty\) or \(w\to\infty\). Some of these results will be covered more in-depth later.

TODO: Use more precise lower bound for \(k\to\infty\): \(\ceil{(w+k)/w}/(w+k)\)?

When \(k\to\infty\), both the rot-minimizer (Marçais, DeBlasio, and Kingsford 2018) and the new mod-minimizer (section 3.5) achieve optimal density \(1/w\).

Slightly simplified, the rot-minimizer ranks $k$-mers by the sum of the characters in positions \(0\pmod w\), so that for \(w=2\), it would sum every other character of the $k$-mer. Then, it samples the $k$-mer for which this sum is maximal.

When \(w\to\infty\), minimizer schemes have a big limitation. Since they only consider the $k$-mers, when \(w\gg \sigma^k\), almost every window will contain the smallest $k$-mer. Thus, we obtain (theorem 2 2018):

This implies that as \(w\to\infty\), fixed-\(k\) minimizer schemes can never reach the optimal density of \(1/w\). On the other hand, this lower bound does not hold for forward and local schemes. For forward schemes, we can use the lower bound of (Theorem 1 Kille et al. 2024) to get \(2/(w+k)\) (see section 2.4). For local schemes, Remark 7 applies and with \(k’ = \max(k,3)\) we get the bound \(1.5/(w+\max(k-2, 1))\).

From the other side, Proposition 7 of Marçais, DeBlasio, and Kingsford (2018) shows that:

Later, this was improved to (Theorem 2 Zheng, Kingsford, and Marçais 2021a):

But this is still not optimal: reduced bd-anchors (Lemma 6 Loukides, Pissis, and Sweering 2023) (see section 4.1) are a local scheme with \(k=1\) and density \(O(1/w)\).

We further improve on this using sus-anchors (section 4.2), which is a forward scheme with density \((2+o(1))/(w+1)\) as \(w\to\infty\). (TODO)

While it may seem from Table 1 that local schemes are not better than forward schemes, there are parameters for which local schemes achieve strictly better density (Marçais, DeBlasio, and Kingsford 2018; Kille et al. 2024). Unfortunately, there currently is not good theory of local schemes, and these improved schemes were found by solving an integer linear program (ILP) for small parameters. Lower bounds on local scheme density for small \(k\) and \(w\) are also not nearly as tight as for forward schemes.

1.10 Variants

There are several variations on sampling schemes that generalize in different ways.

Global schemes drop the requirement that whether a $k$-mer is sampled only depends on a local context. Examples are minhash (Broder 1997) and more general FracMinHash (Irber et al. 2022), both sampling the smallest $k$-mers of an entire string.

On strings with many repeated characters, all $k$-mers have the same hash, and hence all $k$-mers are sampled. Robust winnowing (Schleimer, Wilkerson, and Aiken 2003) prevents this by sampling the rightmost minimal $k$-mer by default, unless the minimizer of the previous window has the same hash, in which case that one is ‘‘reused’’.

Min-mers (Kille et al. 2023) are a second variant, where instead of choosing a single $k$-mer from a window, \(s\) $k$-mers are chosen instead, typically from a window that is \(s\) times longer.

Finimizers (Alanko, Biagi, and Puglisi 2024) are variable length minimizers that ensure that the frequency of the minimizers is below some threshold.

For DNA, it is often not know to which strand a give sequence belongs. Thus, any analysis should be invariant under taking the reverse complement. In this case, canonical minimizers can be used.

One way to turn any minimizer scheme into a canonical minimizer scheme is by using the order \(\Ok^{\rc}(x) = \min(\Ok(x), \Ok(\rc(x)))\) (Roberts et al. 2004; Mohamadi et al. 2016) or \(\Ok^{\rc}(x) = \Ok(x) + \Ok(\rc(x))\) (Kazemi et al. 2022; Groot Koerkamp and Martayan 2025). Still, this leaves the problem of whether to sample the leftmost or rightmost occurrence of a $k$-mer in case of ties. This can be solved using the technique of the refined minimizer (Pan and Reinert 2024; Groot Koerkamp and Martayan 2025): ensure that \(w+k-1\) is odd, and pick the strand with the highest count of GT bases. A way to encode canonical $k$-mers that saves one bit is presented in Wittler (2023). Lastly, Marçais, Elder, and Kingsford (2024) provides a way to turn context-free methods into a canonical version.

The conservation of a scheme is the expected fraction of bases covered by sampled $k$-mers Edgar (2021). In Shaw and Yu (2021), sampling schemes are generalized to $k$-mer selection methods that are allowed to sample any subset of $k$-mers from the input string, and local selection methods that return any subset of $k$-mers from a window. Both these papers focus on context-free schemes, as such $k$-mers are better preserved.

There is also the problem to minimize the particular density on a given input string. For example, some works change the order of the ACGT DNA alphabet to make C the smallest character, as it is often occurs less frequently in DNA sequences (Roberts et al. 2004). Other works in this direction are Hoang, Zheng, and Kingsford (2022), Zheng, Kingsford, and Marçais (2021b), and (Chikhi et al. 2014), the last of which presents a minimizer scheme that orders $k$-mers such that rare $k$-mers are preferred over more common ones.

2 Lower bounds

The starting point for this section is the trivial lower bound:

Naturally, all proofs of tighter lower bounds use the fact that at least one $k$-mer must be sampled every \(w\) positions. All theorems apply it in a slightly different context though.

This was first improved by Schleimer et al. (Schleimer, Wilkerson, and Aiken 2003) to approximately \(1.5/(w+1)\), although using assumptions that are too strong in practice (Section 2.1). Marçais et al. (Marçais, DeBlasio, and Kingsford 2018) give a weaker version that does hold for all forward schemes, of just above \(1.5/(w+k)\) (Section 2.2). At the core, it considers two windows spaced apart by \(w+k\) positions. The first window than has a minimizer, and with probability \(1/2\), a second additional minimizer is needed to ‘bridge the gap’ to the second window. In the appendix of Groot Koerkamp and Pibiri (2024), Groot Koerkamp and Pibiri improve this further to \(1.5/(w+k-0.5)\) by using a slightly more precise analysis (Section 2.3). Because of the similarity of these three proofs, we only provide sketches of the first two, followed by a full proof of the strongest version.

Still, these bounds appeared very far from tight, given that e.g. for \(k=1\) the best schemes do not go below \(2/(w+1)\), which is much larger than \(1.5/(w+0.5)\). For a large part, Kille and Groot Koerkamp et al. (Kille et al. 2024) resolved this by a new near-tight lower bound of \(\ceil{(w+k)/k}/(w+k)\) (Section 2.4). This bound looks at cycles of length \(w+k\), and uses that at least \(\ceil{(w+k)/k}\) minimizers must be sampled on such a cycle. They also prove a slightly improved version that is the first lower bound to be exactly tight for a subset of parameters.

We end this section with a comparison of the lower bounds to each other, and to optimal schemes found using integer linear programming (Section 2.5).

2.1 Schleimer et al.’s bound

The first improvement over the trivial lower bound was already given in the paper that first introduced minimizers (theorem 1 Schleimer, Wilkerson, and Aiken 2003):

Unfortunately, this lower-bound assumes that $k$-mers are hashed before being processed them further using a potentially ‘‘smart’’ algorithm \(S\). This class of schemes was introduced as local algorithms, and thus caused some confusion (see e.g. Marçais et al. (2017)) in that it was also believed to be a lower bound on the more general local schemes as we defined them. This inconsistency was first noticed in Marçais, DeBlasio, and Kingsford (2018), which introduces a ‘‘fixed’’ version of the theorem.

2.2 Marçais et al.’s bound

In Marçais, DeBlasio, and Kingsford (2018), the authors give a weaker variant of the theorem of Schleimer, Wilkerson, and Aiken (2003) that does hold for all forward schemes:

2.3 Improving and extending Marçais et al.’s bound

It turns out that the theorem TODO REF is slightly inefficient. In Groot Koerkamp and Pibiri (2024), we improve it. Also note that the existing proof already works for any local scheme.

This new version does not include the \(\max\left(0, \floor{\frac{k-w}{w}}\right)\) term, because it turns out that when \(k\geq w\), the full bound is anyway less than \(1/w\).

In Figure 1 we can see that this new version indeed provides a small improvement over the previous lower bound when \(k < (w+1)/2\). Nevertheless, a big gap remains between the lower bound and, say, the density of the random minimizer.

It is also clear that this proof is far from tight. It uses that an additional $k$-mer must be sampled when a full window of \(w+k-1\) characters fits between \(s_1\) and \(s_2\), while in practice an additional $k$-mer is already needed when the distance between them is larger than \(w\). However, exploiting this turns out to be difficult: we can not assume that the sampled positions in overlapping windows are independent, nor is it easy to analyse a probability such as \(\P[X \leq X’’-k]\).

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

In Kille et al. (2024), we prove a nearly tight lower bound on the density of forward schemes. We start with a slightly simplified version.

The full and more precise version is as follows (Theorem 1 Kille et al. 2024).

As can be seen in Figure 1, this lower bound jumps up at values \(k\equiv 1 \pmod w\). In practice, if some density \(d\) can be achieved for parameters \((w,k)\), it can also be achieved for any larger \(k’\geq k\), by simply ignoring the last \(k’-k\) characters of each window. Thus, we can ‘‘smoothen’’ the plot via the following corollary.

At this point, one might assume that a smooth ‘‘continuation’’ of this bound (that exactly goes through the ‘‘peaks’’) also holds, but this turns out to not be the case, as for example for \(\sigma=w=2\), the optimal scheme exactly follows the lower bound.

Local schemes. The lower bounds discussed so far can also be extended to local schemes by replacing \(c=w+k\) by \(c=2w+k-2\). Sadly, this does not lead to a good bound. In practice, the best local schemes appear to be only marginally better than the best forward schemes, while the currently established theory requires us to increase the context size significantly, thereby making all inequalities much more loose. Specifically, the tightness of the bound is mostly due to the rounding up in \(\frac{1}{c}\ceil{\frac{c}{k}}=\frac{1}{w+k}\ceil{\frac{w+k}{k}}\), and the more we increase \(c\), the smaller the effect of the rounding will be.

Searching optimal schemes. For small parameters \(\sigma\), \(w\), and \(k\), we can search for optimal schemes using an integer linear program (ILP) (Kille et al. 2024). In short, we define an integer variable \(x_W=f(W) \in [w]\) for every window \(W \in \sigma^{w+k-1}\), that indicates the position of the $k$-mer sampled from this window. For each context containing consecutive windows \(W\) and \(W’\), we add a boolean variable \(y_{(W, W’)}\) that indicates whether this context is charged. Additionally, we impose that \(f(W’) \geq f(W)-1\) to ensure the scheme is forward. The objective is to minimize the number of charged edges, i.e., to minimize the number of \(y\) that is true. In practice, the ILP can be sped up by imposing constraints equivalent to our lower bound: for every pure cycle of length at most \(w+k\), at least \(\ceil{(w+k)/w}\) of the contexts must be charged. This helps especially when \(k\equiv 1\pmod w\), in which case it turns out that the ILP always finds a forward scheme matching the lower bound, and hence can finish quickly.

2.5 Discussion

In Figure 1 we compare the lower bounds to optimal schemes for small parameters. First, note that the bound of Marçais et al. (grey) is only better than \(1/w\) for small \(k<(w+1)/2\). In this regime, the improved version (green) indeed gives a slight improvement. The simple version of the near-tight bound (blue) is significantly better, and closely approximates the best ILP solutions when at least one of the parameters is large enough. When all parameters are small, the improved version \(g_\sigma\) (purple) is somewhat better though. As discussed, the density can only decrease in \(k\), and indeed the monotone version \(g’_\sigma\) (red) is much better.

We see that the bound exactly matches the best forward scheme when \(k=1\) and the ILP succeeded to find a solution (third column), and more generally when \(k\equiv 1\pmod w\). Furthermore, for \(\sigma=w=2\), the lower bound is also optimal for all even \(k\). Thus, we have the following open problem.

For the remaining \(k\), specifically \(1<k<w\), there is a gap between the lower bound and the optimal schemes.

And lastly, a lot is still unknown about local schemes.

Commentary. Bryce Kille and myself independently discovered the basis of this theorem TODO REF during the summer of 2024. In hindsight, I am very surprised it took this long (over 20 years!) for this theorem to be found. Minimizers were originally defined in 2003-2004, and only in 2018 the first improvement (or fix, rather) of Schleimer et al.’s original bound was found in Marçais, DeBlasio, and Kingsford (2018). Specifically, all ingredients for the proof have been around for quite some time already:

• The density of the random minimizer is \(2/(w+1)\), which ‘‘clearly’’ states: out of every \(w+1\) consecutive $k$-mers, at least \(2\) must be sampled. We just have to put those characters into a cycle.
• The density of any forward scheme can be computed using an order \(w+k\) De Bruijn sequence, so again, it is only natural that looking at strings of length at least \(w+k\) is necessary. Cyclic strings are a simple next step.
• And also, partitioning the De Bruijn graph into cycles is something that was done before by Mykkeltveit (Mykkeltveit 1972).

3 Sampling schemes

We now turn our attention from lower bounds and towards low-density sampling schemes. We first consider various existing schemes, that we go over in three groups. In Section 3.1 we consider some simple variants of lexicographic minimizers. In Section 3.2, we consider some schemes that build on universal hitting sets, either by explicitly constructing one or by using related theory. We also include here the greedy minimizer, which is also explicitly constructed using a brute force search. Then, in Section 3.3, we cover some schemes based on syncmers.

We end with two new schemes. First, the open-closed minimizer (Groot Koerkamp, Liu, and Pibiri 2025) (Section 3.4), which extends the miniception by first preferring the smallest open syncmer, falling back to the smallest closed syncmer, and then falling back to the smallest $k$-mer overall. This simple scheme achieves near-best density for \(k\leq w\).

Second, we introduce the (extended) mod-minimizer and the open-closed mod-mini (Groot Koerkamp and Pibiri 2024; Groot Koerkamp, Liu, and Pibiri 2025). These schemes significantly improve over all other schemes when \(k>w\) and converge to density \(1/w\) as \(k\to\infty\). Additionally, we show that they have optimal density when \(k\equiv 1\pmod w\) and the alphabet is large.

3.1 Variants of lexicographic minimizers

The lexicographic minimizer is known to have relatively bad density because it is prone to sampling multiple consecutive $k$-mers when there is a run of A characters. Nevertheless, they achieve density \(O(1/w)\) as \(k=\floor{\log_\sigma(w/2)}-2\) and \(w\to\infty\) (Zheng, Kingsford, and Marçais 2020).

They can be improved by using an slightly modified order (Roberts et al. 2004):

This scheme typically avoids sampling long runs of equal characters, unless the entire window consists only of a single character.

A second variant is the ABB order (Frith, Noé, and Kucherov 2020).

This scheme has the property that distinct occurrences of the ABB... pattern are necessarily disjoint, leading to good spacing of the minimizers. This was already observed before in the context of generating non-overlapping codes (Blackburn 2015).

A drawback of the ABB order is that it throws away some information: for example AB and AC are considered equal, which is usually not idea. Thus, we also consider a version with tiebreaking, ABB+:

We also introduce a small variation on these schemes.

In this order, the smallest string is AZZZZ....

TODO: Threshold?

Evaluation

In Figure 2, we compare the aforementioned variants of lexicographic minimizers. First, note that all schemes perform bad for \(k\in \{1,2\}\), since \(k^\sigma\leq 2^4=16 < 24=w\), and thus there will always be duplicate $k$-mers. As expected, the random minimizer (yellow) has density \(0.08 = 2/(24+1)\). The lexicographic order (dim blue) is significantly worse at 0.89. The alternating order (orange, 0.78) is slightly better, and the anti-lex order (green, 0.76) is slightly better again.

The ABB order (brown-red, 0.69), and especially the ABB order with tiebreaking (blue) perform much better than the random minimizer. ABB+tiebreaking even performs nearly optimal for \(3\leq k\leq 5\). This is surprising, since the idea was already introduced as a sampling and minimizer scheme in 2020 (Fig 4a Frith, Noé, and Kucherov 2020) and appeared more generally before in 2015, but somehow never was compared against by other minimizer schemes. In particular, as we will see later, this scheme outperforms most other schemes for small \(k\), and e.g. miniception (also 2020) is only slightly better for large \(k\).

3.2 UHS-inspired schemes

DOCKS. In Orenstein et al. (2016, 2017), the authors introduce an algorithm to generate small universal hitting sets. It works in two steps. It starts by using Mykkeltveit’s minimum decycling set (Mykkeltveit 1972) such that every infinitely long string contains a $k$-mer from the decycling set. Then, it repeatedly adds the $k$-mer to the UHS that is contained in the largest number of length \(\ell=w+k-1\) windows that does not yet contain a $k$-mer in the UHS. In practice, the exponential runtime in \(k\) and \(w\) is a bottleneck. A first speedup is to consider the $k$-mer contained in the largest number of paths of any length. A second method for larger \(k’ > k\), called naive extension, is to simply ignore the last \(k’-k\) characters of each $k$-mer and then use a UHS for $k$-mers. DOCKS can generate UHSes up to around \(k=13\), and for \(k=10\) and \(w=10\), it has density down to \(1.737/(w+1)\) (Marçais et al. 2017), thereby being the first scheme that breaks the conjectured \(2/(w+1)\) lower bound.

\(\boldremuval\) (DeBlasio et al. 2019) is a method that builds on DOCKS. Starting with some \((w,k-1)\) UHS generated by DOCKS, first uses naive extension to get a \((w, k)\) UHS \(U’\). Then, it tries to reduce the size of this new UHS by removing some $k$-mers. In particular, if a $k$-mer only ever occurs in windows together with another $k$-mer of \(U’\), then this $k$-mer may be removed from \(U’\). Instead of greedily dropping $k$-mers, and ILP is built to determine an optimal set of $k$-mers to drop. This process is repeated until the target \(k\) is reached, which can be up to at least \(200\), as long as \(w\leq 21\) is sufficiently small.

PASHA (Ekim, Berger, and Orenstein 2020) also builds on DOCKS and focuses on improving the construction speed. It does this by parallellizing the search for $k$-mers to add to the UHS, and by adding multiple $k$-mers at once (each with some probability) rather than only the one with the highest count of un-covered windows containing it. These optimizations enable PASHA to generate schemes up to \(k=16\), while having density comparable to DOCKS.

Decycling-based minimizer. An improvement to the brute force constructions of DOCKS, \(\remuval\), and PASHA came with a minimizer scheme based directly on minimum decycling sets (Pellow et al. 2023): In any window, prefer choosing a $k$-mer in \(\Dk\), if there is one, and break ties using a random order. They also introduce the double decycling scheme. This uses the symmetric MDS \(\Dtk\) consisting of those $k$-mers for which \(-2\pi/k\leq \arg(x)<0\). It then first prefers $k$-mers in \(\Dk\), followed by $k$-mers in \(\Dtk\), followed by $k$-mers that are in neither.

It is easy to detect whether a $k$-mer is in the MDS or not without any memory, so that this method scales to large \(k\). Surprisingly, not only is this scheme conceptually simpler, but it also has significantly lower density than DOCKS, PASHA, and miniception. Apparently, the simple greedy approach of preferring smaller $k$-mers works better than the earlier brute force searches for small universal hitting sets. Especially for \(k\) just below \(w\), its density is much better than any other scheme.

GreedyMini. Unlike the previous UHS schemes, GreedyMini (Golan et al. 2024) directly constructs a low-density minimizer scheme using a brute force approach. As we saw, the density of a minimizer scheme equals the probability that the smallest $k$-mer in a \(w+k\) long context is at the start or end. The GreedyMini builds a minimizer scheme by one-by-one selecting the next-smallest $k$-mer. It starts with the set of all \(w+k\) contexts, and finds the $k$-mer for which the number of times it appears as the first or last $k$-mer in a context, as a fraction of its total number of appearances, is lowest. It then discards all contexts this $k$-mer appears in, and repeats the process until a minimizer has been determined for all contexts. To improve the final density, slightly submoptimal choices are also tried occasionally, and a local search and random restarts are used. To keep the running time manageable, the schemes are only built for a \(\sigma=2\) binary alphabet and up to \(k\leq 20\). This is extended to larger \(k\) using naive extension and to larger alphabets by simply ignoring some of the input bits.

The resulting schemes achieve density very close to the lower bound, especially when \(k\) is around \(w\). In these regions, the greedymini has lower density than all other schemes, and it is able to find optimal schemes for some small cases when \(k\equiv 1\pmod w\). This raises the question whether it is also optimal for other \(k\), where the lower bound may not be tight yet. A drawback is that this scheme is not pure: it must explicitly store the chosen order of $k$-mers.

3.3 Syncmer-based schemes

As we saw, universal hitting sets belong to a more general class of context-free schemes that only look at individual $k$-mers to decide whether or not to sample them. A well-known category of context-free schemes are syncmers (Edgar 2021). In general, syncmer variants consider the position of the smallest $s$-mer inside a $k$-mer, for some \(1\leq s\leq k\) and according to some order \(\Os\). Here we consider two well-known variants: closed and open syncmers.

Closed syncmers satisfy a window guarantee of \(k-s\), meaning that there is at least one closed syncmer in any window of \(w\geq k-s\) consecutive $k$-mers. When the order \(\Os\) is random, closed syncmers have a density of \(2/(k-s+1)\), which is the same as that of a random minimizer when \(k>w\) and \(s=k-w\). Indeed, syncmers were designed to improve the conservation metric rather than the density. See Edgar (2021) for details.

The choice of \(v\) to be in the middle was shown to be optimal for conservation by Shaw and Yu (2021). For this \(v\), open syncmers satisfy a distance guarantee (unlike closed syncmers): two consecutive open syncmers are always at least \(\floor{(k-s)/2}+1\) positions apart.

Miniception is a minimizer scheme that builds on top of closed syncmers (Zheng, Kingsford, and Marçais 2020). The name stands for ‘‘minimizer inception’’, in that it first uses an order \(\Os\) and then an order \(\Ok\).

Because of the window guarantee of closed syncmers, miniception always samples a closed syncmer when \(w\geq k-s\). When \(k\) is sufficiently larger than \(w\) and \(s = k-w+1\), it is shown that miniception has density bounded by \(1.67/w + o(1/w)\). In practice, we usually use \(s = k-w\) when \(k\) is large enough. Unlike UHS-based schemes, miniception does not require large memory, and it is the first such scheme that improves the \(2/(w+1)\) density when \(k\approx w\).

3.4 Open-closed minimizer

As we saw, Miniception samples the smallest $k$-mer that is a closed syncmer. The open-closed minimizer is a natural extension of this (Groot Koerkamp, Liu, and Pibiri 2025):

The rationale behind this method is that open syncmers have a distance lower bound (Edgar 2021), i.e., any two open syncmers are at least \(\floor{(k-s)/2}+1\) positions apart. This is in contrast to closed syncmers, that do not obey a similar guarantee (but instead have an upper bound on the distance between them). As it turns out, by looking at Figure 3, the distance lower bound of open syncmers (O, brown) gives rise to lower densities than the upper bound of closed syncmers (C=miniception, green).

In Groot Koerkamp, Liu, and Pibiri (2025), we give a polynomial algorithm to compute the exact density of the open-closed minimizer scheme, assuming that no duplicate $k$-mers occur. At a high level, this works by considering the position of the smallest $s$-mer in the window, and then recursing on the prefix or suffix before/after it, until an $s$-mer is found that is sufficiently far from the boundaries to induce an open syncmer.

Evaluation

In Figure 3, we compare all pure schemes seen so far. We see that miniception (green) performs slightly better than the ABB+tiebreak order when \(k\) is sufficiently large. The decycling-set based orders (grey and black) significantly outperform the miniception, especially for \(k\) just below \(w\). Surprisingly, just changing the closed syncmers of miniception for open syncmers (O, brown) yields a better scheme, although not as good as decycling. The combination (OC, purple) does reach the same density as double decycling, and improves over it for \(w\leq k\leq 2w\). Interestingly, the O and OC curves look similar to the decycling and double decycling curves, but slightly shifted to the right. The right shift is caused by looking at syncmers where the inner minimizer has length \(s=4\). If we were to use a large alphabet with \(s=1\), this difference mostly disappears.

3.5 Mod-minimizer

So far, all the schemes we have seen in this section work well up to around \(k\approx w\), but then fail to further decrease in density as \(k\) grows to infinity. The rot-minimizer (Marçais, DeBlasio, and Kingsford 2018) does converge to density \(1/w\), but in its original form it only does so very slowly.

Here we present the mod-minimizer (Groot Koerkamp and Pibiri 2024; Groot Koerkamp, Liu, and Pibiri 2025), which turns out to converge to \(1/w\) nearly as fast as the lower bound TODO REF.

We start with a slightly more general definition.

As it turns out, this scheme is only forward for some choices of \(t\) (Lemma 8 Groot Koerkamp and Pibiri 2024).

In Figure 4, it can be seen that mod-sampling has local minima in the density when \(t\equiv k\pmod w\) (Lemma 12 Groot Koerkamp and Pibiri 2024), thus, we restrict our attention to this case only.

Furthermore, we can show that for \(t\equiv k \pmod w\), mod-sampling is not only forward, but also a minimizer scheme (Lemma 13 Groot Koerkamp and Pibiri 2024):

This now allows us to define the mod-minimizer.

It turns out this definition can be extended to wrap any sampling scheme, rather than just random minimizers (Groot Koerkamp, Liu, and Pibiri 2025).

Naturally, the extended mod-minimizer can be applied to the open-closed minimizer, to obtain the oc-mod-mini.

Theoretical density

When we restrict \(f\) to be a minimizer scheme specifically, we can compute the density of the extended mod-minimizer (Theorem 1 Groot Koerkamp, Liu, and Pibiri 2025).

Before we compute the density of the mod-minimizer, we first re-state Lemma 9 of (Groot Koerkamp and Pibiri 2024), which is a slightly modified version of Lemma 9 of (Zheng, Kingsford, and Marçais 2020) that we saw earlier in Section 1.7. The proof is nearly identical.

From the above two results, we obtain the density of the random mod-minimizer (Corollary 17 Groot Koerkamp and Pibiri 2024; Theorem 2 Groot Koerkamp, Liu, and Pibiri 2025).

Evaluation

In Figure 5, we compare the mod-minimizer version of the best schemes so far against their normal density. We use \(r=4\) as the lower bound on \(t\), so that repeated $t$-mers are rare in practice. We clearly see that the mod-minimizer schemes roughly follow the red lower bound, and indeed have density that converges to \(1/w\) as \(k\) increases. Between \(k=w+1\) and \(k=2w+1\), the graphs look roughly similar to the area between \(k=1\) and \(k=w+1\): ABB with tiebreaking is best when \(k\) is small (up to around \(w/2\)), and hence also when \(t\) is small (again up to around \(w/2\)). For larger \(k\) and \(t\), we see that double decycling has minimal density.

Like the OC-minimizer, the mod-minimizer requires \(t\geq 4\) to avoid duplicate $k$-mers. This causes the graphs to jump down at \(k=w+4\), rather than at \(k=w+1\). When the alphabet is large, \(t=1\) suffices, and the graphs of the mod-minimizer touch lower bound when \(k\equiv 1\pmod w\).

3.6 Discussion

Looking at Figure 5, there are still some regions where we do not yet have near-optimal sampling schemes. First, when \(k \leq 2\), all schemes have poor density, as minimizer schemes can not do well when \(k\leq \log_\sigma(w)\). In the next section, we will investigate forward schemes that do achieve good density for such small \(k\).

Secondly, when \(k=w+1\) or slightly smaller, the current schemes do not achieve optimal density, while we expect such schemes to exist based on the ILP results for small parameters. Indeed, the greedy minimizer (not shown, TODO) appears to be near-optimal for k close to \(w\). Nevertheless, for roughly \(w/6 < k < \frac 23 w\), no schemes are close to the lower bound. Specifically at \(k = w/3\), the ‘‘deepest’’ point of the lower bound,

4 Selection schemes

As we saw for the sampling schemes so far, they do not do well for very small \(k\). Indeed, they are all minimizer schemes, and these can not achieve density below \(1/\sigma^k\). Here, we explore the \(k=1\) case, where the window size is \(\ell=w+k-1=w\). We first introduce bidirectional anchors (Loukides and Pissis 2021) in 4.1, and then we improve these into smallest-unique-substring anchors 4.2, which is unpublished work of myself.

4.1 Bidirectional anchors

Bidirectional anchors (bd-anchors) are a variant on minimizers that take the minimal lexicographic rotation instead of the minimal $k$-mer substring (Loukides and Pissis 2021):

It turns out that bd-anchors are somewhat brittle because the are not forward: for example, take the window ZABAAC, that has minimal rotation starting with AAC.... If we then shift the window by one, we may get ABAACA, of which the smallest rotation AAB... starts at the end. Shifting again to e.g. BAACAY, the smallest rotation again starts with AAC.... Thus, in the middle step, the final A was only sampled because the string happened to start with an A as well at that single step. Reduced bd-anchors solve this, although they are still not forward (Definition 2 Loukides, Pissis, and Sweering 2023).

Now, the following theorem can be proven (Lemma 6 Loukides, Pissis, and Sweering 2023).

This parameter \(r\) is slightly unfortunate: while plain bd-anchors are parameter-free, the \(r\) acts very similar to \(k-1\) for minimizer schemes. And since \(r\) is \(4\log_\sigma(2)\), in practice, the reduced bd-anchors usually just sample a length-\(r\) lexicographic minimizer. This still has the drawbacks of lexicographic sorting, while not providing the benefit of an actual parameter free scheme.

4.2 Sus-anchors

To avoid the instability of bd-anchors caused by comparing rotations, we can simply only look for the smallest suffix instead. A plain version of that would still be unstable, since in e.g. XABA, the trailing A would compare less than ABA, even though it might be followed by a Z once the window slides along. To fix this, we prefer longer suffixes over shorter suffixes in case one is a prefix of the other. This leads to the following definition.

With this new definition and input window XABA, we would sample the suffix ABA, since the trailing A suffix occurs elsewhere. The smallest unique substring is then AB, since it only occurs in XABA once and is smaller than XA and BA.

Anti-lexicographic order. One drawback of taking the lexicographic smallest substring is that suffixes of small substrings are also small. In particular, when a window starts with AAABB..., both the smallest rotation and the smallest unique suffix are the entire string AAABB..., at position \(0\). After shifting the window one position, we get AABB..., and still the bd-anchor and sus-anchor are AABB.... If no other A occurs at all, after shifting again to ABB... again both anchors sample position \(0\). Thus, neither of these anchors solves the issues associated with lexicographic sorting.

To fix this, we consider two variants of sus-anchors: with anti-lexicographic sorting (where AZZZZ... is minimal) and with ABB sorting, where the smallest string is an A followed by any non-A characters.

Both these orders avoid the issue of sampling consecutive positions in runs of As, specifically by preferring a transition from A to some other character. Further, patterns of A followed by non-A characters are pairwise disjoint, so that consecutively sampled minimizers are pushed apart from each other.

One of the reasons that this scheme can perform so well for \(k=1\) is that it is not a minimizer scheme, and thus not bound by the \(1/\sigma^k\) density lower bound. sus-anchors are always forward though, regardless of the sort order for each character.

• Remark on sampling exactly two every cycle.
• Ideally, prove density \(O(1/w)\), and answer the question of (Zheng, Kingsford, and Marçais 2021a) that yes, perfect selection schemes exist. Then also update the asymptotic table.

Evaluation

We compare bd-anchors with various \(r\) and sus-anchors with various underlying orderings in Figure 6. We see that as \(w\) grows, so does the optimal value of \(r\). Still, even with the best \(r\), bd-anchors do not get too close to the density lower bound for \(w\leq 20\).

Lexicographic sus-anchors (brown) perform around the same or slightly better than bd-anchors, but still do not hit the lower bound. We saw that the ABB order works great as a low-density minimizer scheme, and also here this improves the density. While anti-lexicographic was worse than ABB for minimizers, in this case it turns out to be better, and surprisingly, it reaches density indistinguishable from (but not quite equal to) the lower bound!

If we look at the same plot for alphabet size \(\sigma=2\), Figure 7, we see that indeed there is still some room for improvement.

4.3 Discussion

As mentioned earlier, ILP is always able to find exactly optimal schemes for small parameters when \(k=1\). The sus-anchor with anti-lexicographic sorting gets very close to optimal for \(\sigma=4\), but still has a little gap when \(\sigma=2\). Thus, the problem remains:

TODO 4.4 Discussion

To end, in Figure 8 we once more compare all sampling schemes so far. We also include a \(k>1\) variant of the sus-anchor, that simply picks the smallest-unique-substring that has length at least \(k\). Since the sus-anchor works well for small \(k\), we can use \(r=1\) for the extended mod-mini version of it. As can be seen, this is nearly optimal exactly in the small-\(k\) region where the ABB+ order was lacking. And the mod-version also works well for \(k=w+1\) and just above. The ABB+ scheme then picks up around \(\log_\sigma(w)\), and remains near-optimal until around \(w/6\). From then on, double decycling is best up to \(k=w\), after which the mod-minimizer versions work best. Looking at the plot, the biggest headroom is currently for intermediate values of \(k\). It is unclear whether this is due to the lower bound not being tight, or because better sampling schemes just have not been found yet.

We repeat the open problems that came up so far:

• Can we improve the \(g’\) lower bound for \(1<k<w\)? And generally for \(k\not\equiv 1\pmod w\).
• Can we design sampling schemes that get close to the lower bound for \(k\approx w/3\)? If not in general, then maybe if \(\sigma\to\infty\) or \(w\to\infty\)?
• Can we prove that the \(g’\) lower bound tight for \(k\equiv 1\pmod w\)? And for \(\sigma=w=2\)?
• Can we design an optimal pure selection scheme, having density exactly equal to the \(g’\) lower bound.
• How much can local schemes improve over forward schemes? Can we find a near-tight lower bound on their density? Already for \(k=1\), the current bound is only \(1.5/(w+1)\), rather than the more probably \(2/(w+1)\).

Additionally, there is the question of how much better general forward schemes are compared to minimizer schemes. Of all the schemes in Figure 8, only the sus-achor is not a minimizer scheme. So this raises the question: are minimizer schemes as good as forward schemes when \(k\) is sufficiently large?

5 Checks

• select -> samples
• Marcais -> Marçais
• symbol -> character
• Fix $k$-mer and $t$-mer and $s$-mer and plurals
• Attribute copied proofs
• Attribute used papers in the beginning
• Attribute individual figures & tables in captions
• consistent uppercase characters ABC..Z.
• theorem / lemma / prop / …
• ‘‘quotes’’
• TODO: Mention that lower bound paper has a table with bruteforce results
• TODO: Credit other coauthors of lower bound?

References