The LONGEST COMMON SUBSEQUENCE problem is examined from the point of v
iew of parameterized computational complexity. There are several diffe
rent ways in which parameters enter the problem, such as the number of
sequences to be analyzed, the length of the common subsequence, and t
he size of the alphabet. Lower bounds on the complexity of this basic
problem imply lower bounds on a number of other sequence alignment and
consensus problems. An issue in the theory of parameterized complexit
y is whether a problem which takes input (x, k) can be solved in time
f(k). n(alpha) where alpha is independent of k (termed fixed-parameter
tractability). It can be argued that this is the appropriate asymptot
ic model of feasible computability for problems for which a small rang
e of parameter values covers important applications - a situation whic
h certainly holds for many problems in biological sequence analysis, O
ur main results show that: (1) The LONGEST COMMON SUBSEQUENCE (LCS) pa
rameterized by the number of sequences to be analyzed is hard for W[t]
for all t. (2) The LCS problem, parameterized by the length of the co
mmon subsequence, belongs to W[P] and is hard for W[2]. (3) The LCS pr
oblem parameterized both by the number of sequences and the length of
the common subsequence, is complete for W[1]. All of the above results
are obtained for unrestricted alphabet sizes. For alphabets of a fixe
d size, problems (2) and (3) are fixed-parameter tractable. We conject
ure that (1) remains hard.