Parameterized complexity analysis in computational biology

Many computational problems in biology involve par–ametersfor which a small range of values cover important applications.We argue that for many problems in this setting, parameterizedcomputational complexity rather than NP-completeness is theappropriate tool for studying apparent intractability. At issuein the theory of parameter–ized complexity is whethera problem can be solved in time O(n)for each fixed parametervalue, where a is a constant independent of the parameter. Inaddition to surveying this complexity framework, we describea new result for the Longest Common Subsequence problem. Inparticular, we show that the problem is hard for W[t] for allI when parameterized by the number of strings and the size ofthe alphabet. Lower bounds on the complexity of this basic combinatorialproblem imply lower bounds on more general sequence alignmentand consensus discovery problems. We also describe a numberof open problems pertaining to the parameterized complexityof problems in computational biology where small parameter valuesare important