2024/05/07 by Verbeek, Hilde, Ayad, Lorraine A. K., Loukides, Grigorios +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2405.04052
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\mathinner. . i+w+k-2] is the smallest position in [i,i+w-1] where the lexicographically smallest length-k substring of S[i\mathinner. . 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≥ 2 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.