The parameterized complexity of sequence alignment and consensus
From MaRDI portal
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
- On the parameterized intractability of CLOSEST SUBSTRING and related problems
- On the Longest Common Parameterized Subsequence
Cites work
- A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Consensus rules for molecular sequences: Open problems
- Efficient methods for multiple sequence alignment with guaranteed error bounds
- Matching Sequences under Deletion/Insertion Constraints
- Multiple Alignment, Communication Cost, and Graph Matching
- Searching subsequences
- Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
- The Complexity of Some Problems on Subsequences and Supersequences
- The computation of consensus patterns in \(DNA\) sequences
- The parameterized complexity of some problems in logic and linguistics
Cited in
(34)- On parameterized complexity of the multi-MCS problem
- On the longest common parameterized subsequence
- Threshold dominating sets and an improved characterization of \(W[2]\)
- On the complexity of finding common approximate substrings.
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- A polyhedral approach to sequence alignment problems
- 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
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- The complexity of irredundant sets parameterized by size
- A multiparametric view on answer set programming
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- On the complexity of sequence to graph alignment
- Multiple genome rearrangement by swaps and by element duplications
- Constrained sequence alignment: A general model and the hardness results
- A parametric analysis of the state-explosion problem in model checking
- The parameterized complexity of the shared center problem
- The birth and early years of parameterized complexity
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- On the parameterized complexity of associative and commutative unification
- Parameterized Complexity and Approximability of the SLCS Problem
- Lower Bounds and Parameterized Approach for Longest Common Subsequence
- Parameterized complexity and approximability of the longest compatible sequence problem
- On the parameterized intractability of CLOSEST SUBSTRING and related problems
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- The parameterized complexity of the shared center problem
- The complexity of multiple sequence alignment with SP-score that is a metric
- Domino treewidth
- On the parameterized complexity of the multi-MCT and multi-MCST problems
- Finding diverse strings and longest common subsequences in a graph
- Space-efficient parameterized algorithms on graphs of low shrubdepth
- On the parameterized complexity of associative and commutative unification
- Longest common subsequence problem for unoriented and cyclic strings
- Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
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)