Parameterized Intractability of Motif Search Problems
<|reference_start|>Parameterized Intractability of Motif Search Problems: We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)\cdot n^{c}) for any function f of k and constant c independent of k. The problem can therefore be expected to be intractable, in any practical sense, for k>=3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem of similar significance in computational biology.<|reference_end|>
@article{fellows2002parameterized,
    title={Parameterized Intractability of Motif Search Problems},
    author={Michael R. Fellows, Jens Gramm and Rolf Niedermeier},
    journal={arXiv preprint arXiv:cs/0205056},
    year={2002},
    number={WSI-2002-2},
    archivePrefix={arXiv},
    eprint={cs/0205056},
    primaryClass={cs.CC}
}