The parameterized complexity of sequence alignment and consensus
From MaRDI portal
Publication:1367540
DOI10.1016/0304-3975(94)00251-DzbMath0888.68060OpenAlexW2115667895WikidataQ57360127 ScholiaQ57360127MaRDI QIDQ1367540
Rodney G. Downey, Harold T. Wareham, Hans L. Bodlaender, Michael R. Fellows
Publication date: 29 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00251-d
Related Items
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems ⋮ Computing the similarity of two sequences with nested arc annotations ⋮ Polynomial algorithms for protein similarity search for restricted mRNA structures ⋮ The Birth and Early Years of Parameterized Complexity ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling] ⋮ On the Parameterized Complexity of Associative and Commutative Unification ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ On the parameterized complexity of the multi-MCT and multi-MCST problems ⋮ Domino treewidth ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ On the complexity of finding common approximate substrings. ⋮ The complexity of irredundant sets parameterized by size ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ On the parameterized complexity of associative and commutative unification ⋮ On parameterized complexity of the multi-MCS problem ⋮ Threshold dominating sets and an improved characterization of \(W[2\)] ⋮ A multiparametric view on answer set programming ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems
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
