The parameterized complexity of sequence alignment and consensus

@article{citeulike:1809559, abstract = {The problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as 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 a number of other sequence alignment and consensus problems. An issue in the theory of parameterized complexity is whether a problem which takes input (x, k) can be solved in time f(k) [middle dot] n[alpha] where [alpha] is 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 covers important applications -- a situation which certainly holds for many problems in biological sequence analysis. Our main results show that: 1. (1) The (LCS) parameterized by the number of sequences to be analyzed is hard for W[t] for all t. 2. (2) The LCS problem, parameterized by the length of the common subsequence, belongs to W[P] and is hard for W[2]. 3. (3) The LCS problem 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 fixed size, problems (2) and (3) are fixed-parameter tractable. We conjecture that (1) remains hard.}, author = {Bodlaender, Hans L. and Downey, Rodney G. and Fellows, Michael R. and Wareham, Harold T. }, citeulike-article-id = {1809559}, doi = {http://dx.doi.org/10.1016/0304-3975(94)00251-D}, journal = {Theoretical Computer Science}, keywords = {algorithms, complexity, parameterized}, month = {August}, number = {1-2}, pages = {31--54}, posted-at = {2007-10-23 09:01:27}, priority = {2}, title = {The parameterized complexity of sequence alignment and consensus}, url = {http://dx.doi.org/10.1016/0304-3975(94)00251-D}, volume = {147}, year = {1995} }

TY - JOUR ID - citeulike:1809559 L3 - citeulike-article-id:1809559 TI - The parameterized complexity of sequence alignment and consensus JF - Theoretical Computer Science VL - 147 IS - 1-2 SP - 31 EP - 54 N2 - The problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as 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 a number of other sequence alignment and consensus problems. An issue in the theory of parameterized complexity is whether a problem which takes input (x, k) can be solved in time f(k) [middle dot] n[alpha] where [alpha] is 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 covers important applications -- a situation which certainly holds for many problems in biological sequence analysis. Our main results show that: 1. (1) The (LCS) parameterized by the number of sequences to be analyzed is hard for W[t] for all t. 2. (2) The LCS problem, parameterized by the length of the common subsequence, belongs to W[P] and is hard for W[2]. 3. (3) The LCS problem 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 fixed size, problems (2) and (3) are fixed-parameter tractable. We conjecture that (1) remains hard. KW - algorithms KW - complexity KW - parameterized AU - Bodlaender, Hans AU - Downey, Rodney AU - Fellows, Michael AU - Wareham, Harold PY - 1995/08/07/ UR - http://dx.doi.org/10.1016/0304-3975(94)00251-D ER -