Central and local limit theorems for RNA structures. (English) Zbl 1397.92532
Summary: A \(k\)-noncrossing RNA pseudoknot structure is a graph over \(\{1,\dots,n\}\) without 1-arcs, i.e. arcs of the form \((i,i+1)\) and in which there exists no \(k\)-set of mutually intersecting arcs. In particular, RNA secondary structures are 2-noncrossing RNA structures. In this paper we prove a central and a local limit theorem for the distribution of the number of 3-noncrossing RNA structures over \(n\) nucleotides with exactly \(h\) bonds. Our analysis employs the generating function of \(k\)-noncrossing RNA pseudoknot structures and the asymptotics for the coefficients. The results of this paper explain the findings on the number of arcs of RNA secondary structures obtained by molecular folding algorithms and are of relevance for prediction algorithms of \(k\)-noncrossing RNA structures.
MSC:
| 92D20 | Protein sequences, DNA sequences |
Keywords:
\(k\)-noncrossing RNA structure; pseudoknot; generating function; singularity; central limit theorem; local limit theoremOnline Encyclopedia of Integer Sequences:
Number of 3-noncrossing RNA structures, i.e., the number of 3-noncrossing partial matchings over n vertices and without arcs of length 1.References:
| [1] | Mapping RNA form and function. Science 2, 2005.; Mapping RNA form and function. Science 2, 2005. |
| [2] | Bender, E.A., Central and local limit theorem applied to asymptotic enumeration, J. combin. theory A, 15, 91-111, (1973) · Zbl 0242.05006 |
| [3] | Chamorro, M.; Parkin, N.; Varmus, H.E., An RNA pseudoknot and an optimal heptameric shift site are required for highly efficient ribosomal frameshifting on a retroviral messenger RNA, Proc. natl acad. sci. USA, 89, 713-717, (1991) |
| [4] | Chen, J.; Blasco, M.; Greider, C., Secondary structure of vertebrate telomerase RNP, Cell, 100, 503-514, (2000) |
| [5] | Chen, W.Y.C.; Deng, E.Y.P.; Du, R.R.X.; Stanley, R.P.; Yan, C.H., Crossings and nestings of matchings and partitions, Trans. am. math. soc., 359, 1555-1575, (2007) · Zbl 1108.05012 |
| [6] | Flajolet, P.; Fill, J.A.; Kapur, N., Singularity analysis, Hadamard products, and tree recurrences, J. comput. appl. math., 174, 271-313, (2005) · Zbl 1056.05011 |
| [7] | Gao, Z.; Richmond, L.B., Central and local limit theorems applied to asymptotic enumeration, J. appl. comput. anal., 41, 177-186, (1992) · Zbl 0755.05004 |
| [8] | Gessel, I.M.; Zeilberger, D., Random walk in a Weyl chamber, Proc. am. math. soc., 115, 27-31, (1992) · Zbl 0792.05148 |
| [9] | Hofacker, I.L.; Schuster, P.; Stadler, P.F., Combinatorics of RNA secondary structures, Discr. appl. math., 88, 207-237, (1998) · Zbl 0918.05004 |
| [10] | Hwang, H.K., Large deviations of combinatorial distributions. II. local limit theorems, Ann. appl. probab., 8, 1, 163-181, (1998) · Zbl 0954.60020 |
| [11] | Jin, E.Y., Qin, J., Reidys, C.M., 2007. Combinatorics of RNA structures with pseudoknots. Bull. Math. Biol. in press.; Jin, E.Y., Qin, J., Reidys, C.M., 2007. Combinatorics of RNA structures with pseudoknots. Bull. Math. Biol. in press. · Zbl 1281.92055 |
| [12] | Jin, E.Y., Reidys, C.M., 2007. Asymptotics of rna structures with pseudoknots. Bull. Math. Biol., accepted.; Jin, E.Y., Reidys, C.M., 2007. Asymptotics of rna structures with pseudoknots. Bull. Math. Biol., accepted. · Zbl 1152.92007 |
| [13] | Konings, D.A.M.; Gutell, R.R., A comparison of thermodynamic foldings with comparatively derived structures of 16s and 16s-like rrnas, RNA, 1, 559-574, (1995) |
| [14] | Lindström, B., On the vector representation of induced matroids, Bull. London math. soc., 5, 85-90, (1973) · Zbl 0262.05018 |
| [15] | Loria, A.; Pan, T., Domain structure of the ribozyme from eubacterial ribonuclease p, RNA, 2, 551-563, (1996) |
| [16] | McCaskill, J.S., The equilibrium partition function and base pair binding probabilities for RNA secondary structure, Biopolymers, 29, 1105-1119, (1990) |
| [17] | Odlyzko, A.M., Handbook of combinatorics, (1995), Elsevier Amsterdam, (Chapter 22) |
| [18] | Schmitt, W.R.; Waterman, M.S., Linear trees and RNA secondary structure, Discr. appl. math., 51, 317-323, (1994) · Zbl 0799.92006 |
| [19] | Tacker, M.; Fontana, W.; Stadler, P.F.; Schuster, P., Statistics of RNA melting kinetics, Eur. biophys. J., 23, 29-38, (1994) |
| [20] | Tacker, M.; Stadler, P.F.; Bauer, E.G.; Hofacker, I.L.; Schuster, P., Algorithm independent properties of RNA secondary structure predictions, Eur. biophys. J., 25, 115-130, (1996) |
| [21] | Tuerk, C.; MacDougal, S.; Gold, L., RNA pseudoknots that inhibit human immunodeficiency virus type 1 reverse transcriptase, Proc. natl acad. sci. USA, 89, 6988-6992, (1992) |
| [22] | van Batenburg, F.H.D.; Gultyaev, A.P.; Pleij, C.W.A., Pseudobase: structural information on RNA pseudoknots, Nucleic acids res., 29, 1, 194-195, (2001) |
| [23] | Waterman, M.S., Secondary structure of single-stranded nucleic acids, Adv. math. I, 1, Suppl., 167-212, (1978) · Zbl 0434.05007 |
| [24] | Waterman, M.S.; Smith, T.F., Rapid dynamic programming algorithms for RNA secondary structure, Adv. appl. math., 7, 455-464, (1986) · Zbl 0607.92012 |
| [25] | Westhof, E.; Jaeger, L., RNA pseudoknots, Current opinion struct. biol., 2, 327-333, (1992) |
| [26] | Zuker, M.; Sankoff, D., RNA secondary structures and their prediction, Bull. math. biol., 46, 4, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
