Many computational problems in biology involve parameters for which a
small range of values cover important applications. We argue that for
many problems in this setting, parameterized computational complexity
rather than NP-completeness is the appropriate tool for studying appar
ent intractability. At issue in the theory of parameterized complexity
is whether a problem can be solved in time O(n(alpha)) for each fixed
parameter value, where alpha is a constant independent of the paramet
er. In addition to surveying this complexity framework, we describe a
new result for the Longest Common Subsequence problem. In particular,
we show that the problem is hard for W[t] for all t when parameterized
by the number of strings and the size of the alphabet. Lower bounds o
n the complexity of this basic combinatorial problem imply lower bound
s on more general sequence alignment and consensus discovery problems.
We also describe a number of open problems pertaining to the paramete
rized complexity of problems in computational biology where small para
meter values are important.