Generating minimum-density minimizers
Preprint
Abstract
Minimizers are sampling schemes which are ubiquitous in almost any 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, which lead 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, it has a huge search space of ( σ k )! and there is no known algorithm apart from a trivial brute-force search. In this paper, we tackle the minimum density problem for minimizers. We first formulate this problem as an ILP of size Θ ( wσ w + k ), which has worst-case solution time that is doubly-exponential in ( k + w ) under standard complexity assumptions. Our experiments show 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 thus is capable of processing large w values. In experiments, OptMini works much faster than the runtime predicts due to several additional tricks shrinking 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)} and w ∈ [2, 3 σ k ], with the exception of certain w -ranges for k = 6 and the single case of k = 5, w = 2. 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-size universal hitting sets and minimum-density minimizers.Keywords
Funding Information
- Israel Science Foundation (358/21)
This publication has 21 references indexed in Scilit:
- A near-tight lower bound on the density of forward sampling schemesBioinformatics, 2024
- Creating and Using Minimizer Sketches in Computational GenomicsJournal of Computational Biology, 2023
- Lower Density Selection Schemes via Small Universal Hitting Sets with Short Remaining Path LengthJournal of Computational Biology, 2021
- Improved design and analysis of practical minimizersBioinformatics, 2020
- A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets2020
- Asymptotically optimal minimizers schemesBioinformatics, 2018
- Improving the performance of minimizers and winnowing schemesBioinformatics, 2017
- Compact Universal k-mer Hitting Sets2016
- Reducing storage requirements for biological sequence comparisonBioinformatics, 2004
- A proof of Golomb's conjecture for the de Bruijn graphJournal of Combinatorial Theory, Series B, 1972