Abstract
RNA–RNA binding is an important phenomenon observed for many classes of non-coding RNAs and plays a crucial role in a number of regulatory processes. Recently several MFE folding algorithms for predicting the joint structure of two interacting RNA molecules have been proposed. Here joint structure means that in a diagram representation the intramolecular bonds of each partner are pseudoknot-free, that the intermolecular binding pairs are noncrossing, and that there is no so-called “zigzag” configuration. This paper presents the combinatorics of RNA interaction structures including their generating function, singularity analysis as well as explicit recurrence relations. In particular, our results imply simple asymptotic formulas for the number of joint structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alkan C, Karakoc E, Nadeau J, Sahinalp S, Zhang K (2006) RNA–RNA interaction prediction and antisense RNA target search. J Comput Biol 13: 267–282
Bachellerie J, Cavaillé J, Hüttenhofer A (2002) The expanding sno RNA world. Biochimie 84: 775–790
Banerjee D, Slack F (2002) Control of developmental timing by small temporal RNAs: a paradigm for RNA-mediated regulation of gene expression. Bioessays 24: 119–129
Benne R (1992) RNA editing in trypanosomes: the use of guide RNAs. Mol Biol Rep 16: 217–227
Chitsaz H, Salari R, Sahinalp S, Backofen R (2009) A partition function algorithm for interacting nucleic acid strands. Bioinformatics 25: i365–i373
Flajolet P, Sedgewick R (2008) Analytic combinatorics. Cambridge University Press, Cambridge
Geissmann T, Touati D (2004) Hfq, a new chaperoning role: binding to messenger RNA determines access for small RNA regulator. EMBO J 23: 396–405
Giegerich R, Meyer C (2002) Algebraic dynamic programming. In: Lecture notes in computer science, vol 2422. Springer, New York, pp 349–364
Huang F, Qin J, Stadler P, Reidys C (2009) Partition function and base pairing probabilities for RNA–RNA interaction prediction. Bioinformatics 25: 2646–2654
Huang F, Qin J, Stadler P, Reidys C (2010) Target prediction and a statistical sampling algorithm for RNA–RNA interaction. Bioinformatics 26: 175–181
** E, Reidys C (2009) Combinatorial design of pseudoknot RNA. Adv Appl Math 42: 135–151
Kugel J, Goodrich J (2007) An RNA transcriptional regulator templates its own regulatory RNA. Nat Struct Mol Biol 3: 89–90
McManus M, Sharp P (2002) Gene silencing in mammals by small interfering RNAs. Nat Rev 3: 737–747
Narberhaus F, Vogel J (2007) Sensory and regulatory RNAs in prokaryotes: a new german research focus. RNA Biol 4: 160–164
Pervouchine D (2004) IRIS: Intermolecular RNA interaction search. Proc Genome Inform 15: 92–101
Reidys C, Wang R, Zhao A (2010) Modular, k-noncrossing diagrams. Electron J Combin 17: R76
Schmitt W, Waterman M (1994) Linear trees and RNA secondary structure. Disc Appl Math 51: 317–323
Titchmarsh E (1939) The theory of functions. Oxford Uninversity Press, Oxford
Udekwu K, Darfeuille F, Vogel J, Reimegåd J, Holmqvist E, Wagner E (2005) Hfq-dependent regulation of OmpA synthesis is mediated by an antisense RNA. Genes Dev 19: 2355–2366
Waterman M, Smith T (1978) RNA secondary structure: a complete mathematical analysis. Math Biosci 42: 257–266
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Li, T.J.X., Reidys, C.M. Combinatorics of RNA–RNA interaction. J. Math. Biol. 64, 529–556 (2012). https://doi.org/10.1007/s00285-011-0423-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00285-011-0423-7