Minimizers sampling is one of the most widely-used mechanisms for sampling strings [Roberts et al., Bioinformatics 2004]. Let S = S[1] . . . S[n] be a string over a totally ordered alphabet Σ. Further let w ≥ 2 and k ≥ 1 be two integers. The minimizer of S[i . . i + w + k − 2] is the smallest position in [i, i + w − 1] where the lexicographically smallest length-k substring of S[i . . i + w + k − 2] starts. The set of minimizers over all i ∈ [1, n − w − k + 2] is the set Mw,k(S) of the minimizers of S. We consider the following basic problem: Given S, w, and k, can we efficiently compute a total order on Σ that minimizes |Mw,k(S)|? We show that this is unlikely by proving that the problem is NP-hard for any w ≥ 3 and k ≥ 1. Our result provides theoretical justification as to why there exist no exact algorithms for minimizing the minimizers samples, while there exists a plethora of heuristics for the same purpose.

, , ,
doi.org/10.4230/LIPIcs.CPM.2024.28
Leibniz International Proceedings in Informatics (LIPIcs)
35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Verbeek, H., Ayad, L., Loukides, G., & Pissis, S. (2024). Minimizing the minimizers via alphabet reordering. In Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024 (pp. 28:1–28:13). doi:10.4230/LIPIcs.CPM.2024.28