Polynomial algorithms for protein similarity search for restricted mRNA structures

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 [R. Backofen, N.S. Narayanaswamy, F. Swidan, On the complexity of protein similarity search under mRNA structure constraints, in: Proceedings of the Annual Symposium of Theoretical Aspects of Computer Science, in: LNCS, vol. 2285, Springer, 2002, pp. 274–286] 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 [G. Blin, G. Fertin, D. Hermelin, S. Vialette, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, in: Proceedings of Graph-Theoretical Concepts in Computer Science, in: LNCS, vol. 3787, Springer, 2005, pp. 271–282] 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 much 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, P4-sparse graphs, and distance hereditary graphs. Further we conclude that the problem of comparing two solutions for MRSO is hard for the class , which is defined as the set of problems which can be solved in polynomial time with a number of parallel queries to an oracle in NP.