Search Results

Minimizers are sampling schemes ubiquitous in high-throughput sequencing analysis. Given an alphabet of size σ, a minimizer is defined by two positive integers k and w, and a linear order ρ on k-mers. A sequence is processed by a sliding window algorithm that chooses, in each window of length w+k-1, its minimal k-mer with respect to ρ. A key characteristic of a minimizer is its density, defined as the expected frequency of chosen k-mers among all k-mers in a random infinite σ-ary sequence. Minimizers of lower density are preferred as they produce smaller samples, which lead to reduced runtime and memory usage in downstream applications. Recently developed methods generate minimizers with optimal and near-optimal densities, but these methods require explicit storage of k-mer ranks in Ω(2^k) space. Methods generating constant-space minimizers with low densities also exist, and some are asymptotically optimal as k → ∞. However, in the non-asymptotic regime, no known class of minimizers had been proven to guarantee, on expectation, a lower density compared to a random minimizer. In this paper, we introduce a class of 10-minimizers, which has promising properties. First, we prove that for every k > 1 and every w ≥ k-2, a random 10-minimizer has, on expectation, lower density than a random minimizer, under essentially the same simplifying assumption. This is the first provable guarantee for a class of minimizers in the non-asymptotic regime. Second, we present spacers, which are particular 10-minimizers combining three desirable properties: constant space usage, low density, and short k-mer key-retrieval time. In terms of density, spacers are competitive to the best known constant-space minimizers; in certain (k,w) regimes they achieve the lowest density among all known minimizers. Notably, we are the first to benchmark minimizers by the time spent for k-mer key retrieval, which is the most fundamental operation in many minimizers-based methods. We propose this benchmark as a standard objective for evaluating new minimizer schemes. Our empirical results show that spacers retrieve k-mer keys in competitive time - a few seconds per genome-size sequence - for all practical values of k and w. We expect 10-minimizers to improve minimizers-based methods, especially those using large window sizes.