The parameterized complexity of sequence alignment and consensus
From MaRDI portal
Publication:1367540
DOI10.1016/0304-3975(94)00251-DzbMATH Open0888.68060DBLPjournals/tcs/BodlaenderDFW95OpenAlexW2115667895WikidataQ57360127 ScholiaQ57360127MaRDI QIDQ1367540FDOQ1367540
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
Recommendations
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Lower Bounds and Parameterized Approach for Longest Common Subsequence
- On the parameterized intractability of motif search problems
- scientific article; zbMATH DE number 2086391
- On the Longest Common Parameterized Subsequence
Cites Work
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
- The Complexity of Some Problems on Subsequences and Supersequences
- Title not available (Why is that?)
- Efficient methods for multiple sequence alignment with guaranteed error bounds
- Searching subsequences
- A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
- Matching Sequences under Deletion/Insertion Constraints
- Title not available (Why is that?)
- Multiple Alignment, Communication Cost, and Graph Matching
- The computation of consensus patterns in \(DNA\) sequences
Cited In (29)
- Domino treewidth
- On the complexity of sequence to graph alignment
- On the parameterized complexity of associative and commutative unification
- Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
- Parameterized complexity and approximability of the longest compatible sequence problem
- A multiparametric view on answer set programming
- Threshold dominating sets and an improved characterization of \(W[2]\)
- The Birth and Early Years of Parameterized Complexity
- Computing the similarity of two sequences with nested arc annotations
- A parametric analysis of the state-explosion problem in model checking
- On parameterized complexity of the multi-MCS problem
- On the Parameterized Complexity of Associative and Commutative Unification
- The complexity of multiple sequence alignment with SP-score that is a metric
- On the parameterized complexity of the multi-MCT and multi-MCST problems
- A polyhedral approach to sequence alignment problems
- Longest common subsequence problem for unoriented and cyclic strings
- Multiple genome rearrangement by swaps and by element duplications
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Parameterized Complexity and Approximability of the SLCS Problem
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Title not available (Why is that?)
- Lower Bounds and Parameterized Approach for Longest Common Subsequence
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- Constrained sequence alignment: A general model and the hardness results
- On the complexity of finding common approximate substrings.
- The complexity of irredundant sets parameterized by size
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
This page was built for publication: The parameterized complexity of sequence alignment and consensus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1367540)
