SEE PROFILE

The Longest common subsequence problem is examined from the point of view of parameterized computational complexity. There are several ways in which param-eters enter the problem: the number of sequences to be analyzed, the length of the common subsequence, and the size of the alphabet. Lower bounds on the complexity of this basic problem imply lower bounds on more general sequence alignment and consensus problems. At issue in the theory of parameterized complexity is whether a problem can be solved in time O(nα) for each fixed parameter value k, where α is a constant independent of k (termed fixed-parameter tractability). It can be argued that this is the appropriate asymptotic model of feasible computability for problems for which a small range of parameter values cover important applications — a situation which certainly holds for many problems in sequence analysis. Our main results show that: (1) The Longest Common Subsequence (LCS) parameterized by the number of sequences to be analyzed is hard for W [t] for all t. (2) The LCS problem problem, parameterized by the length of the common subsequence, belongs to W [P] and is har