zbMATH — the first resource for mathematics

The rainbow spectrum of RNA secondary structures. (English) Zbl 1394.92098
Summary: In this paper, we analyze the length spectrum of rainbows in RNA secondary structures. A rainbow in a secondary structure is a maximal arc with respect to the partial order induced by nesting. We show that there is a significant gap in this length spectrum. We shall prove that there asymptotically almost surely exists a unique longest rainbow of length at least \(n-O(n^{1/2})\) and that with high probability any other rainbow has finite length. We show that the distribution of the length of the longest rainbow converges to a discrete limit law and that, for finite \(k\), the distribution of rainbows of length \(k\) becomes for large \(n\) a negative binomial distribution. We then put the results of this paper into context, comparing the analytical results with those observed in RNA minimum free energy structures, biological RNA structures and relate our findings to the sparsification of folding algorithms.

92D20 Protein sequences, DNA sequences
05A15 Exact enumeration problems, generating functions
Full Text: DOI arXiv
[1] Backofen, R; Tsur, D; Zakov, S; Ziv-Ukelson, M, Sparse RNA folding: time and space efficient algorithms, J Discrete Algorithms, 9, 12-31, (2011) · Zbl 1216.92033
[2] Barrett, C; Li, T; Reidys, C, RNA secondary structures having a compatible sequence of certain nucleotide ratios, J Comput Biol, 23, 857-873, (2016)
[3] Barrett, C; Huang, F; Reidys, C, Sequence-structure relations of biopolymers, Bioinformatics, 33, 382-389, (2017)
[4] Berman, H; Westbrook, J; Feng, Z; etal., The protein data bank, Nucl Acids Res, 28, 235-242, (2000)
[5] Byun, Y; Han, K, Pseudoviewer3: generating planar drawings of large-scale RNA structures with pseudoknots, Bioinformatics, 25, 1435-1437, (2009)
[6] Cannone, J; Subramanian, S; Schnare, M; etal., The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other rnas, BMC Bioinform, 3, 2, (2002)
[7] Clote, P; Ponty, Y; Steyaert, J, Expected distance between terminal nucleotides of RNA secondary structures, J Math Biol, 65, 581-599, (2012) · Zbl 1304.05073
[8] Eddy, S, Non-coding RNA genes and the modern RNA world, Nat Rev Genet, 2, 919-929, (2001)
[9] Flajolet P, Sedgewick R (2009) Analytic combinatorics. Cambridge University Press, New York · Zbl 1165.05001
[10] Graham R, Knuth D, Patashnik O (1994) Concrete mathematics: a foundation for computer science. Addison-Wesley Professional, Reading · Zbl 0836.00001
[11] Han, H; Reidys, C, The \(5^{′ }\)-\(3^{′ }\) distance of RNA secondary structures, J Comput Biol, 19, 868-878, (2012)
[12] Hofacker, I; Fontana, W; Stadler, P; Bonhoeffer, L; Tacker, M; Schuster, P, Fast folding and comparison of RNA secondary structures, Chem Mon, 125, 167-188, (1994)
[13] Hofacker, I; Schuster, P; Stadler, P, Combinatorics of RNA secondary structures, Discrete Appl Math, 88, 207-237, (1998) · Zbl 0918.05004
[14] Howell, J; Smith, T; Waterman, M, Computation of generating functions for biological molecules, SIAM J Appl Math, 39, 119-133, (1980) · Zbl 0445.92006
[15] Huang, F; Reidys, C, On the combinatorics of sparsification, Algorithms Mol Biol, 7, 1-15, (2012)
[16] Hunter, C; Sanders, J, The nature of \(π \)-\(π \) interactions, J Am Chem Soc, 112, 5525-5534, (1990)
[17] Jin, E; Reidys, C, Irreducibility in RNA structures, Bull Math Biol, 72, 375-399, (2010) · Zbl 1185.92042
[18] Jin, E; Reidys, C, On the decomposition of \(k\)-noncrossing RNA structures, Adv Appl Math, 44, 53-70, (2010) · Zbl 1180.05011
[19] Kim, S; Sussman, J; Suddath, F; etal., The general structure of transfer RNA molecules, Proc Natl Acad Sci USA, 71, 4970-4974, (1974)
[20] Kruger, K; Grabowski, P; Zaug, A; Sands, J; Gottschling, D; Cech, T, Self-splicing RNA: autoexcision and autocyclization of the ribosomal RNA intervening sequence of tetrahymena, Cell, 31, 147-157, (1982)
[21] Lorenz R, Bernhart S, Höner zu Siederdissen C, Tafer H, Flamm C, Stadler P, Hofacker I (2011) ViennaRNA Package 2.0. Algorithms Mol Biol 6:26
[22] McCarthy, B; Holland, J, Denatured DNA as a direct template for in vitro protein synthesis, Pro Natl Acad Sci USA, 54, 880-886, (1965)
[23] Penner, R; Waterman, M, Spaces of RNA secondary structures, Adv Math, 217, 31-49, (1993) · Zbl 0810.92011
[24] Robart, A; Chan, R; Peters, J; Rajashankar, K; Toor, N, Crystal structure of a eukaryotic group II intron lariat, Nature, 514, 193-197, (2014)
[25] Robertus, J; Ladner, J; Finch, J; Rhodes, D; Brown, R; Clark, B; Klug, A, Structure of yeast phenylalanine trna at 3 \(\mathring{A}\) resolution, Nature, 250, 546-551, (1974)
[26] Salari, R; Möhl, M; Will, S; Sahinalp, S; Backofen, R; Berger, B (ed.), Time and space efficient RNA-RNA interaction prediction via sparse folding, 473-490, (2010), Berlin, Heidelberg
[27] Schmitt, W; Waterman, M, Linear trees and RNA secondary structure, Discrete Appl Math, 51, 317-323, (1994) · Zbl 0799.92006
[28] Smith, T; Waterman, M, RNA secondary structure, Math Biol, 42, 31-49, (1978) · Zbl 0402.92016
[29] Šponer, J; Leszczynski, J; Hobza, P, Electronic properties, hydrogen bonding, stacking, and cation binding of DNA and RNA bases, Biopolymers, 61, 3-31, (2001)
[30] Šponer, J; Sponer, J; Mládek, A; Jurečka, P; Banáš, P; Otyepka, M, Nature and magnitude of aromatic base stacking in DNA and RNA: quantum chemistry, molecular mechanics, and experiment, Biopolymers, 99, 978-988, (2013)
[31] Stein, P; Waterman, M, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math, 26, 261-272, (1979) · Zbl 0405.10009
[32] Waterman, M; Rota, GC (ed.), Secondary structure of single-stranded nucleic acids, No. 1, 167-212, (1978), New York · Zbl 0434.05007
[33] Waterman, M, Combinatorics of RNA hairpins and cloverleaves, Stud Appl Math, 60, 91-98, (1979) · Zbl 0399.05003
[34] Waterman, M; Smith, T, Rapid dynamic programming algorithms for RNA secondary structure, Adv Appl Math, 7, 455-464, (1986) · Zbl 0607.92012
[35] Wexler, Y; Zilberstein, C; Ziv-Ukelson, M, A study of accessible motifs and RNA folding complexity, J Comput Biol, 14, 856-872, (2007) · Zbl 1302.92103
[36] Woese, C; Magrum, L; Gupta, R; Siegel, R; Stahl, D; Kop, J; Crawford, N; Brosius, J; Gutell, R; Hogan, J; Noller, H, Secondary structure model for bacterial 16S ribosomal RNA: phylogenetic, enzymatic and chemical evidence, Nucl Acids Res, 8, 2275-2293, (1980)
[37] Yoffe, A; Prinsen, P; Gelbart, W; Ben-Shaul, A, The ends of a large RNA molecule are necessarily close, Nucl Acids Res, 39, 292-299, (2011)
[38] Zuker, M, On finding all suboptimal foldings of an RNA molecule, Science, 244, 48-52, (1989) · Zbl 1226.92029
[39] Zuker, M; Sankoff, D, RNA secondary structures and their prediction, Bull Math Biol, 46, 591-621, (1984) · Zbl 0548.92007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.