Generating minimum-density minimizers

Minimizers are sampling schemes which are ubiquitous in high-throughput sequencing analysis. Assuming a fixed alphabet of size {sigma}, a minimizer is defined by two positive integers k, w and a linear order {rho} 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 {rho}. 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 {sigma}-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 ({sigma}, k, w) is unknown, this problem has a huge search space of ({sigma}^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 {Theta}({sigma}^(2k) + w * {sigma}^(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 [OM], which computes an optimal minimizer in w * 2^({sigma}^k + O(k)) time, and is thus capable of processing large w values. In our experiments, [OM] 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 [OM] to compute minimum-density minimizers for ({sigma}, k) [isin] {(2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (4, 2)} over w [isin] [2..3{sigma}^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.