Minimizing the minimizers via alphabet reordering

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.

• View at Publisher

Free Full Text ( Final Version , 1mb )