PARAMETERIZED COMPLEXITY ANALYSIS IN COMPUTATIONAL BIOLOGY

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.