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

Sampling $k$ -mers is a ubiquitous task in sequence analysis algorithms. Sampling schemes such as the often-used random minimizer scheme are particularly appealing as they guarantee at least one $k$ -mer is selected out of every $w$ consecutive $k$ -mers. Sampling fewer $k$ -mers often leads to an increase in efficiency of downstream methods. Thus, developing schemes that have low density, i.e., have a small proportion of sampled $k$ -mers, is an active area of research. After over a decade of consistent efforts in both decreasing the density of practical schemes and increasing the lower bound on the best possible density, there is still a large gap between the two.

We prove a near-tight lower bound on the density of forward sampling schemes, a class of schemes that generalizes minimizer schemes. For small $w$ and $k$ , we observe that our bound is tight when $k\equiv 1$ (mod $w$ ). For large $w$ and $k$ , the bound can be approximated by $\frac{1}{w+k}\left(\frac{w+k}{w}\right)$ . Importantly, our lower bound implies that existing schemes are much closer to achieving optimal density than previously known. For example, with the current default minimap2 HiFi settings $w=19$ and $k=19$ , we show that the best known scheme for these parameters, the double decycling-set-based minimizer of Pellow et al., is at most 3% denser than optimal, compared to the previous gap of at most 50%. Furthermore, when $k\equiv 1$ (mod $w$ ) and the alphabet size $\sigma$ goes to $\infty$ , we show that mod-minimizers introduced by Groot Koerkamp and Pibiri achieve optimal density matching our lower bound.