Polynomial algorithms for protein similarity search for restricted mRNA structures
From MaRDI portal
Publication:2380067
Abstract: In this paper we consider the problem of computing an mRNA sequence of maximal similarity for a given mRNA of secondary structure constraints, introduced by Backofen et al. in [BNS02] denoted as the MRSO problem. The problem is known to be NP-complete for planar associated implied structure graphs of vertex degree at most 3. In [BFHV05] a first polynomial dynamic programming algorithms for MRSO on implied structure graphs with maximum vertex degree 3 of bounded cut-width is shown. We give a simple but more general polynomial dynamic programming solution for the MRSO problem for associated implied structure graphs of bounded clique-width. Our result implies that MRSO is polynomial for graphs of bounded tree-width, co-graphs, -sparse graphs, and distance hereditary graphs. Further we conclude that the problem of comparing two solutions for MRSO is hard for the class of problems which can be solved in polynomial time with a number of parallel queries to an oracle in NP.
Recommendations
- SOFSEM 2004: Theory and Practice of Computer Science
- On the complexity of protein similarity search under mRNA structure constraints
- An approximation algorithm for a protein similarity search problem
- Graph-Theoretic Concepts in Computer Science
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
Cites work
- _2p-completeness: A classical approach for new results
- A Linear Recognition Algorithm for Cographs
- Approximating clique-width and branch-width
- Clique-width minimization is NP-hard
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
- Edge dominating set and colorings on graphs with fixed clique-width
- Graph Classes: A Survey
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- More complicated questions about maxima and minima, and some closures of NP
- On the clique-width of graph with few \(P_{4}\)'s
- On the clique-width of some perfect graph classes
- On the complexity of protein similarity search under mRNA structure constraints
- On the Relationship Between Clique-Width and Treewidth
- Parameterized complexity
- Polynomial time recognition of clique-width 3 graphs (extended abstract)
- SOFSEM 2004: Theory and Practice of Computer Science
- Some simplified NP-complete graph problems
- The parameterized complexity of sequence alignment and consensus
- The Rectilinear Steiner Tree Problem is NP-Complete
- Upper bounds to the clique width of graphs
- Vertex disjoint paths on clique-width bounded graphs
Cited in
(6)- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- On the complexity of protein similarity search under mRNA structure constraints
- An approximation algorithm for a protein similarity search problem
- Graph-Theoretic Concepts in Computer Science
- SOFSEM 2004: Theory and Practice of Computer Science
- Directed NLC-width
This page was built for publication: Polynomial algorithms for protein similarity search for restricted mRNA structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380067)