The parameterized complexity of sequence alignment and consensus

DOI10.1016/0304-3975(94)00251-DzbMath0888.68060WikidataQ57360127 ScholiaQ57360127MaRDI QIDQ1367540

Michael R. Fellows, Hans L. Bodlaender, Rodney G. Downey, Harold T. Wareham

Publication date: 29 September 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

parameterized computational complexity; longest common subsequence problem

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Threshold dominating sets and an improved characterization of \(W[2\)], The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], The complexity of irredundant sets parameterized by size

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• The computation of consensus patterns in \(DNA\) sequences
• Searching subsequences
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• Multiple Alignment, Communication Cost, and Graph Matching
• The Complexity of Some Problems on Subsequences and Supersequences
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• Matching Sequences under Deletion/Insertion Constraints