TY - JOUR
T1 - Topology of RNA-RNA Interaction Structures
AU - Andersen, Hans Jørgen
AU - Huang, Fenix Wenda
AU - Penner, Robert
AU - Reidys, Christian M
PY - 2012
Y1 - 2012
N2 - Abstract 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(n(6)) time and O(n(4)) 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.
AB - Abstract 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(n(6)) time and O(n(4)) 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.
U2 - 10.1089/cmb.2011.0308
DO - 10.1089/cmb.2011.0308
M3 - Journal article
C2 - 22731621
SN - 1066-5277
VL - 19
SP - 928
EP - 943
JO - Journal of Computational Biology
JF - Journal of Computational Biology
IS - 7
ER -