  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.
