Authors: Marc Hellmuth, Daniel Merkle, Martin Middendorf
Addresses: Interdisciplinary Centre for Bioinformatics, Department of Computer Science, University of Leipzig, Haertelstr. 16-18, D-04107 Leipzig, Germany; Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, D-04103 Leipzig, Germany. ' Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark. ' Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig, Johannisgasse 26, D-04103 Leipzig, Germany
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. For more than two secondary structures this is not necessarily possible. 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 Clote et al. (2005) and show an analogous NP-completeness result for the realisation problem concerning the removal of (pseudo) edges. We also present a polynomial time method for checking the realisability of extended shape graphs. Furthermore, we empirically analyse the influence of pseudo edges on the realisability for sets of random RNA sequences and for sets of aptamers.
Keywords: RNA folding; RNA design; NP-completeness; RNA secondary structures; extended shapes; aptamers; computational biology; drug design; combinatorial design; RNA sequences.
International Journal of Computational Biology and Drug Design, 2009 Vol.2 No.4, pp.371 - 384
Available online: 04 Jan 2010 *Full-text access for editors Access for subscribers Purchase this article Comment on this article