Generating Minimum-Density Minimizers

Abstract Minimizers are sampling schemes which are ubiquitous in high-throughput sequencing analysis. Assuming a fixed alphabet of size σ , a minimizer is defined by two positive integers k, 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, which is the expected frequency of chosen k -mers among all k -mers in a random infinite σ -ary sequence. Minimizers of smaller density are preferred as they produce smaller samples, leading to reduced runtime and memory usage in downstream applications. While the hardness of finding a minimizer of minimum density for given input parameters ( σ, k, w ) is unknown, this problem has a huge search space of ( σ k )! and no algorithm, apart from a trivial brute-force search, is known. In this paper, we tackle the minimum density problem for minimizers. As a first step, we formulate this problem as an ILP of size Θ( σ 2 k + wσ w + k ) and learn from experiments that an ILP solver terminates with an optimal solution only for very small k and w . We then present our main method, called OptMini, which computes an optimal minimizer in time, and is thus capable of processing large w values. In our experiments, OptMini works much faster than the runtime bound predicts, thanks to several additional tricks we implemented to shrink the search space without harming optimality. We use OptMini to compute minimum-density minimizers for ( σ, k ) ∈ { (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (4, 2)} over w ∈ [2..3 σ k ], with the exception of certain w -ranges for k = 6. Finally, we derive conclusions and insights regarding the density values as a function of w , patterns in optimal minimizer orders, and the relation between minimum-density minimizers and minimum-size universal hitting sets.