Polynomial algorithms for protein similarity search for restricted mRNA structures

Details Polynomial algorithms for protein similarity search for restricted mRNA structures Polynomial algorithms for protein similarity search for restricted mRNA structures

2007-04-26

arxiv.org/abs/0704.3496v1

Computer Science

Data Structures and Algorithms

10 Pages

Scientific paper

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, $P_4$-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.

Affiliated with

Also associated with

No associations

Rating

Polynomial algorithms for protein similarity search for restricted mRNA structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial algorithms for protein similarity search for restricted mRNA structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial algorithms for protein similarity search for restricted mRNA structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-372885