Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
On the Design of RNA Sequences for Realizing Extended Shapes
Marc Hellmuth, Daniel Merkle, Martin Middendorf
Download
Status: Published
Bioinformatics, Systems Biology and Intelligent Computing, IJCBS '09. 167-173 (2009)
Abstract
It is known that for two given secondary structures (defined by position of base pairings) an RNA string can easily be found that can fold into both structures. But for more than two secondary structures this is not necessarily possible. Moreover, when four or more secondary structures are given the problem to determine the least number of positions, such that after the removal of all incident base pairs, a compatible RNA sequence can be found, is known to be NP-complete (cite{real_shapes}). In this paper we introduce pseudo edges that are used to forbid that certain base pairs can bind and therefore can be used to define the properties of possible RNA secondary structures. We study the complexity of the problem to design an RNA sequence that can fold into different secondary structures each of them is described by a set of required and forbidden base pairs. We refine the NP-completeness results of cite{real_shapes} and show an analoguous NP-completeness result for the realization problem concerning the removal of (pseudo) edges. We also present a polynomial time method for checking the realizability of extended shape graphs. Furthermore, we empirically analyze the influence of pseudo edges on the realizability for sets of random RNA sequences and for sets of aptamers.
Keywords
RNA folding, RNA Design, NP-completeness, Secondary Structure, Aptamer
Note
DOI: 10.1109/IJCBS.2009.73