×

zbMATH — the first resource for mathematics

Combinatorics of RNA secondary structures. (English) Zbl 0918.05004
Summary: Secondary structures of polynucleotides can be viewed as a class of planar vertex-labeled graphs. We compute recursion formulae for enumerating a variety subclasses of and classes of subgraphs (structural elements) of secondary structure graphs. First-order asymptotics are derived and their dependence on the composition of the underlying nucleic acid sequences is discussed.

MSC:
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
05C30 Enumeration in graph theory
92C40 Biochemistry, molecular biology
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bender, E.A., Asymptotic methods in enumeration, SIAM rev., 16, 485-515, (1974) · Zbl 0294.05002
[2] Canfield, E.R., Remarks on an asymptotic method in combinatoric, J. combin. theory A, 37, 348-352, (1984) · Zbl 0551.05008
[3] Cupal, J.; Hofacker, I.L.; Stadler, P.F., Dynamic programming algorithm for the density of states of RNA secondary structures, (), 184-186
[4] Darboux, G., Mémoir sur l’approximation des fonctions de très grande nombres, et sur une classe étendu de développements en série, J. math. pure appl., 4, 5-56, (1878) · JFM 10.0279.01
[5] Donaghey, R.; Shapiro, L.W., Motzkin numbers, J. combin. theor. A, 23, 291-301, (1977) · Zbl 0417.05007
[6] Fontana, W.; Griesmacher, T.; Schnabl, W.; Stadler, P.F.; Schuster, P., Statistics of landscapes based on free energies, replication and degredation rate constants of RNA secondary structures, Monatsh. chem., 122, 795-819, (1991)
[7] Fontana, W.; Konings, D.A.M.; Stadler, P.F.; Schuster, P., Statistics of RNA secondary structures, Biopolymers, 33, 1389-1404, (1993)
[8] Grüner, W.; Giegerich, R.; Strothmann, D.; Reidys, C.; Weber, J.; Hofacker, I.L.; Stadler, P.F.; Schuster, P., Analysis of RNA sequence structure maps by exhaustive enumeration. I. neutral networks, Monatsh. chem., 127, 355-374, (1996)
[9] Grüner, W.; Giegerich, R.; Strothmann, D.; Reidys, C.; Weber, J.; Hofacker, I.L.; Stadler, P.F.; Schuster, P., Analysis of RNA sequence structure maps by exhaustive enumeration. II. structures of neutral networks and shape space covering, Monatsh. chem., 127, 375-389, (1996)
[10] Hofacker, I.L.; Fontana, W.; Stadler, P.F.; Bonhoeffer, S.; Tacker, M.; Schuster, P., Fast folding and comparison of RNA secondary structures, Monatsh. chemie, 125, 167-188, (1994)
[11] Hogeweg, P.; Hesper, B., Energy directed folding of RNA sequences, Nucleic acids research, 12, 67-74, (1984)
[12] Howell, J.A.; Smith, T.F.; Waterman, M.S., Computation of generating functions for biological molecules, SIAM J. appl. math., 39, 119-133, (1980) · Zbl 0445.92006
[13] Hsieh, W.N., Proportions of irreducible diagrams, Studies appl. math., 52, 277-283, (1973) · Zbl 0271.05130
[14] Kleitman, D., Proportions of irreducible diagrams, Studies appl. math., 49, 297-299, (1970) · Zbl 0198.03802
[15] Lesk, A.M., A combinatorial study of the effects of admitting non-Watson-crick base pairings and of base compositions on the helix-forming potential of polynucleotides of random sequences, J. theor. biol., 44, 7-17, (1974)
[16] Leydold, J.; Stadler, P.F., Minimal cycle bases of outerplanar graphs, Elec. J. combin., 5, R16, (1998) · Zbl 0895.05032
[17] McCaskill, J.S., The equilibrium partition function and base pair binding probabilities for RNA secondary structure, Biopolymers, 29, 1105-1119, (1990)
[18] Meir, A.; Moon, J.W., On an asymptotic method in enumeration, J. combin. theory A, 51, 77-89, (1989) · Zbl 0683.05001
[19] Nussinov, R.; Piecznik, G.; Griggs, J.R.; Kleitman, D.J., Algorithms for loop matching, SIAM J. appl. math., 35, 68-82, (1978) · Zbl 0411.92008
[20] Odlyzko, A.M., Asymptotic enumeration methods, (), 1021-1229 · Zbl 0845.05005
[21] Penner, R.C.; Waterman, M.S., Spaces of RNA secondary structures, Adv. math., 101, 31-49, (1993) · Zbl 0810.92011
[22] Régnier, M.; Tahi, F., Enumeration and asymptotics in computational biology, ()
[23] Schmitt, W.R.; Waterman, M.S., Linear trees and RNA secondary structure, Discr. appl. math., 12, 412-427, (1994)
[24] Shapiro, B.A., An algorithm for comparing multiple RNA secondary structures, Cabios, 4, 387-397, (1988)
[25] Shapiro, B.A.; Zhang, K., Comparing multiple RNA secondary structures using tree comparisons, Cabios, 6, 309-318, (1990)
[26] Stein, P.R., On a class of linked diagrams, I. enumeration, J. combin. theory A, 24, 357-366, (1978) · Zbl 0395.05002
[27] Stein, P.R.; Everett, C.J., On a class of linked diagrams. II. asymptotics, Disc. math., 22, 309-318, (1978) · Zbl 0395.05003
[28] Stein, P.R.; Waterman, M.S., On some new sequences generalizing the Catalan and Motzkin numbers, Disc. math., 26, 261-272, (1978) · Zbl 0405.10009
[29] Szegö, G., Orthogonal polynomials, () · JFM 65.0278.03
[30] Tacker, M.; Stadler, P.F.; Bornberg-Bauer, E.G.; Hofacker, I.L.; Schuster, P., Algorithm independent properties of RNA structure prediction, Eur. biophy. J., 25, 115-130, (1996)
[31] Tahi, F., Méthodes formelles d’analyse des séquences de nucléotides, ()
[32] Touchard, J., Sur une problème de configurations et sur LES fractions continues, Canad. J. math., 4, 2-25, (1952) · Zbl 0047.01801
[33] Viennot, X.G.; de Chaumont, M.V., Enumeration of RNA’s secondary structures by complexity, (), 360-365
[34] Waterman, M.S., Secondary structure of single-stranded nucleic acids, Adv. math. suppl. studies, 1, 167-212, (1978) · Zbl 0434.05007
[35] Waterman, M.S., Introduction to computational biology: maps, sequences, and genomes, (1995), Chapman & Hall London · Zbl 0831.92011
[36] Waterman, M.S.; Smith, T.F., Combinatorics of RNA hairpins and cloverleaves, Studies appl. math., 60, 91-96, (1978) · Zbl 0399.05003
[37] Waterman, M.S.; Smith, T.F., RNA secondary structure: a complete mathematical analysis, Math. biosci., 42, 257-266, (1978) · Zbl 0402.92016
[38] 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. 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.