A Caltech Library Service

Topology of RNA-RNA Interaction Structures

Andersen, Jørgen E. and Huang, Fenix W. D. and Penner, Robert C. and Reidys, Christian M. (2012) Topology of RNA-RNA Interaction Structures. Journal of Computational Biology, 19 (7). pp. 928-943. ISSN 1066-5277.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2012 Mary Ann Liebert. Published in Volume: 19 Issue 7: July 17, 2012. Online Ahead of Print: June 25, 2012. No competing financial interests exist.
Subject Keywords:algorithms, irreducible shadow, partition function, RNA interaction structure, topological genus
Issue or Number:7
Record Number:CaltechAUTHORS:20120817-112349939
Persistent URL:
Official Citation:Topology of RNA-RNA Interaction Structures Jørgen E. Andersen, Fenix W.D. Huang, Robert C. Penner, and Christian M. Reidys. Journal of Computational Biology. July 2012, 19(7): 928-943. doi:10.1089/cmb.2011.0308.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:33294
Deposited By: Ruth Sustaita
Deposited On:17 Aug 2012 18:44
Last Modified:03 Oct 2019 04:08

Repository Staff Only: item control page