Motivation: Several dynamic programming algorithms for predicting RNA structures with pseudoknots have been proposed that differ dramatically from one another in the classes of structures considered. Results: Here, we use the natural topological classification of RNA structures in terms of irreducible components that are embeddable in the surfaces of fixed genus. We add to the conventional secondary structures four building blocks of genus one in order to construct certain structures of arbitrarily high genus. A corresponding unambiguous multiple context-free grammar provides an efficient dynamic programming approach for energy minimization, partition function and stochastic sampling. It admits a topology-dependent parametrization of pseudoknot penalties that increases the sensitivity and positive predictive value of predicted base pairs by 10–20% compared with earlier approaches. More general models based on building blocks of higher genus are also discussed. Availability: The source code of gfold is freely available at http://www.combinatorics.cn/cbpc/gfold.tar.gz. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.
Motivation: The RNA–RNA interaction problem (RIP) consists in finding the energetically optimal structure of two RNA molecules that bind to each other. The standard model allows secondary structures in both partners as well as additional base pairs between the two RNAs subject to certain restrictions that ensure that RIP is solvabale by a polynomial time dynamic programming algorithm. RNA–RNA binding, like RNA folding, is typically not dominated by the ground state structure. Instead, a large ensemble of alternative structures contributes to the interaction thermodynamics. Results: We present here an O(N6) time and O(N4) dynamics programming algorithm for computing the full partition function for RIP which is based on the combinatorial notion of ‘tight structures’. Albeit equivalent to recent work by H. Chitsaz and collaborators, our approach in addition provides a full-fledged computation of the base pairing probabilities, which relies on the notion of a decomposition tree for joint structures. In practise, our implementation is efficient enough to investigate, for instance, the interactions of small bacterial RNAs and their target mRNAs. Availability: The program rip is implemented in C. The source code is available for download from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.
Motivation: It has been proven that the accessibility of the target sites has a critical influence on RNA–RNA binding, in general and the specificity and efficiency of miRNAs and siRNAs, in particular. Recently, O(N6) time and O(N4) space dynamic programming (DP) algorithms have become available that compute the partition function of RNA–RNA interaction complexes, thereby providing detailed insights into their thermodynamic properties. Results: Modifications to the grammars underlying earlier approaches enables the calculation of interaction probabilities for any given interval on the target RNA. The computation of the ‘hybrid probabilities’ is complemented by a stochastic sampling algorithm that produces a Boltzmann weighted ensemble of RNA–RNA interaction structures. The sampling of k structures requires only negligible additional memory resources and runs in O(k·N3). Availability: The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html. Contact:duck@santafe.edu Supplementary information: Supplementary data are available at Bioinformatics online.
The topological filtration of interacting RNA complexes is studied, and the role is analyzed of certain diagrams called irreducible shadows, which form suitable building blocks for more general structures. We prove that, for two interacting RNAs, called interaction structures, there exist for fixed genus only finitely many irreducible shadows. This implies that, for fixed genus, there are only finitely many classes of interaction structures. In particular, the simplest case of genus zero already provides the formalism for certain types of structures that occur in nature and are not covered by other filtrations. This case of genus zero interaction structures is already of practical interest, is studied here in detail, and is found to be expressed by a multiple context-free grammar that extends the usual one for RNA secondary structures. We show that, in O(n6) time and O(n4) space complexity, this grammar for genus zero interaction structures provides not only minimum free energy solutions but also the complete partition function and base pairing probabilities.
In this article, we present the novel ab initio folding algorithm cross, which generates minimum free energy (mfe), 3-noncrossing, canonical RNA structures. Here an RNA structure is 3-noncrossing if it does not contain three or more mutually crossing arcs and canonical, if each of its stacks has size greater or equal than two. Our notion of mfe-structure is based on a specific concept of pseudoknots and respective loop-based energy parameters. The algorithm decomposes into three subroutines: first the inductive construction of motifs and their associated shadows, second the generation of the (rooted) skeleta-trees and third the saturation of the skeleta via context dependent dynamic programming routines.