Computer Science – Computational Complexity
Scientific paper
2002-05-21
Computer Science
Computational Complexity
21 pages, 5 figures; an extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspec
Scientific paper
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.
Fellows Michael R.
Gramm Jens
Niedermeier Rolf
No associations
LandOfFree
Parameterized Intractability of Motif Search Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized Intractability of Motif Search Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Intractability of Motif Search Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-455145