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
- scientific article; zbMATH DE number 2086391
- On the Longest Common Parameterized Subsequence
Cites work
- scientific article; zbMATH DE number 1163461 (Why is no real title available?)
- scientific article; zbMATH DE number 1499087 (Why is no real title available?)
- A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- 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
Cited in
(32)- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Domino treewidth
- On the parameterized complexity of the multi-MCT and multi-MCST problems
- Threshold dominating sets and an improved characterization of \(W[2]\)
- The complexity of multiple sequence alignment with SP-score that is a metric
- Multiple genome rearrangement by swaps and by element duplications
- On the complexity of sequence to graph alignment
- Constrained sequence alignment: A general model and the hardness results
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- Lower Bounds and Parameterized Approach for Longest Common Subsequence
- On the complexity of finding common approximate substrings.
- A parametric analysis of the state-explosion problem in model checking
- The birth and early years of parameterized complexity
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- A multiparametric view on answer set programming
- 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 SLCS Problem
- scientific article; zbMATH DE number 2086391 (Why is no real title available?)
- On the longest common parameterized subsequence
- On parameterized complexity of the multi-MCS problem
- Parameterized complexity and approximability of the longest compatible sequence problem
- The parameterized complexity of the shared center problem
- On the parameterized complexity of associative and commutative unification
- Synchronizing series-parallel deterministic finite automata with loops and related problems
- Computing the similarity of two sequences with nested arc annotations
- The complexity of irredundant sets parameterized by size
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- On the parameterized complexity of associative and commutative unification
- A polyhedral approach to sequence alignment problems
- Longest common subsequence problem for unoriented and cyclic strings
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- The parameterized complexity of the shared center problem
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)
