On The Parameterized Intractability Of Motif Search Problems* |
| |
Authors: | Michael R. Fellows Jens Gramm† Rolf Niedermeier‡ |
| |
Affiliation: | 1. Department of Computer Science and Software Engineering, University of Newcastle, University Drive, Callaghan 2308, Australia 2. Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen, Sand 13, D-72076, Tübingen, Germany 3. Institut für Informatik, Universit?t Jena, Ernst-Abbe-Platz 1–4, D-07740, Jena, Germany
|
| |
Abstract: | We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•nc) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter 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, althoughb othp roblems 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 arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4. |
| |
Keywords: | 03D15 68Q17 68Q25 |
本文献已被 SpringerLink 等数据库收录! |
|