Polynomial algorithms for protein similarity search for restricted mRNA structures

DOI10.1016/J.IPL.2007.08.019MaRDI QIDQ2380067zbMATH OpenOpenAlexFDO

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0704.3496

computational biology computational complexity graph algorithms mRNA structure protein similarity search

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40)

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,

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.

Recommendations

Cites work

Cited in

(6)

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)