Skip to main content
SpringerLink
Log in

Analysis of RNA sequence structure maps by exhaustive enumeration I. Neutral networks

Analyse der Beziehungen zwischen RNA-Sequenzen und Sekundärstrukturen durch vollständige Faltung, 1. Mitt. Faltung, Neutrale Netzwerke

  • Anorganische Und Physikalische Chemie
  • Published:
Monatshefte für Chemie / Chemical Monthly Aims and scope Submit manuscript

Summary

Global relations between RNA sequences and secondary structures are understood as mappings from sequence space into shape space. These mappings are investigated by exhaustive folding of allGC andAU sequences with chain lengths up to 30. The computed structural data are evaluated through exhaustive enumeration and used as an exact reference for testing analytical results derived from mathematical models and sampling based on statistical methods. Several new concepts of RNA sequence to secondary structure mappings are investigated, among them that ofneutral networks (being sets of sequences folding into the same structure). Exhaustive enumeration allows to test several previously suggested relations: the number of (minimum free energy) secondary structures as a function of the chain length as well as the frequency distribution of structures at constant chain length (commonly resulting in generalized forms ofZipf's law).

Zusammenfassung

Die globalen Benziehungen zwischen RNA-Sequenzen und Sekundärstrukturen werden als Abbildungen aus einem Raum aller Sequenzen in einen Raum aller Strukturen aufgefaßt. Diese Abbildungen werden durch Falten aller binären Sequenzen desGC-undAU-Alphabets mit Kettenlängen bis zun=30 untersucht. Die berechneten Strukturdaten werden durch vollständiges Abzählen ausgewertet und als eine exakte Referenz zum Überprüfen analytischer Resultate aus mathematischen Modellen sowie zum Testen statistisch erhobener Proben verwendet. Einige neuartige Konzepte zur Beschreibung der Beziehungen zwischen Sequenzen und Strukturen werden eingehend untersucht, unter ihnen der Begriff derneutralen Netzwerke. Ein neutrales Netzwerk besteht aus allen Sequenzen, die eine bestimmte Struktur ausbilden. Vollständiges Abzählen ermöglicht beispielsweise die Bestimmung aller Strukturen minimaler freier Energie in Abhängigkeit von der Kettenlänge ebenso wie die Bestimmung der Häufigkeitsverteilungen der Strukturen bei konstanten Kettenlängen. Die letzteren folgen einer verallgemeinerten FormZipfschen Gesetzes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Schuster P (1995) J Biotechnol41: 239–257

    Google Scholar 

  2. Fontana W, Konings DAM, Stadler PF, Schuster P (1993) Biopolymers33: 1389–1404

    Google Scholar 

  3. Fontana W, Griesmacher T, Schnabl W, Stadler PF, Schuster P (1991) Monatsh Chem122: 795–819

    Google Scholar 

  4. Hofacker IL, Fontana W, Stadler PF, Bonhoeffer S, Tacker M, Schuster P (1994) Monatsh Chem125: 167–188

    Google Scholar 

  5. Schuster P, Fontana W, Stadler PF, Hofacker IL (1994) Proc Roy Soc (London) B255: 279–284

    Google Scholar 

  6. Wright S (1932) In: Jones DF (ed) Int Proceedings of the Sixth International Congress on Genetics, vol 1, pp 356–366

  7. Eigen M, McCaskill J, Schuster P (1989) Adv Chem Phys75: 149–263

    Google Scholar 

  8. Weinberger ED (1990) Biol Cybern63: 325–336

    Google Scholar 

  9. Fontana W, Stadler PF, Bornberg-Bauer EG, Griesmacher T, Hofacker IL, Tacker M, Tarazona P, Weinberger ED, Schuster P (1993) Phys Rev E47: 2083–2099

    Google Scholar 

  10. Schuster P, Stadler PF (1994) Comput Chem18: 295–314

    Google Scholar 

  11. Reidys C, Stadler PF, Schuster P (1995) Bull Math Biol (submitted; SFI-Preprint Series No. 95-07-058)

  12. Grüner W, Giegerich R, Strothmann D, Reidys C, Weber J, Hofacker IL, Stadler PF, Schuster P (1996) Monatsh Chem127: 375–389

    Google Scholar 

  13. Sankoff D, Morin A-M, Cedergren RJ (1978) Can J Biochem56: 440–443

    Google Scholar 

  14. Cech TR (1988) Gene73: 259–271

    Google Scholar 

  15. Konings DAM, Hogeweg P (1989) J Mol Biol207: 597–614

    Google Scholar 

  16. Le S-Y, Zuker M (1990) J Mol Biol216: 729–741

    Google Scholar 

  17. Zuker M, Sankoff D (1984) Bull Math Biol46: 591–621

    Google Scholar 

  18. Zuker M (1989) In: Waterman MS (ed) Mathematical Methods for DNA Sequences. CRC Press, Boca Raton, FL, pp 159–184

    Google Scholar 

  19. Martinez HM (1984) Nucl Acid Res12: 323–335

    Google Scholar 

  20. Tacker M (1993) Robust Properties of RNA Secondary Structures. Thesis, University of Vienna

  21. McCaskill JS (1990) Biopolymers29: 1105–1119

    Google Scholar 

  22. Nussinov R, Piecznik G, Griggs JR, Kleitman DJ (1978) SIAM J Appl Math35: 68–82

    Google Scholar 

  23. Mironov AA, Dyakonova LP, Kister AE (1985) J Biomol Struct Dyn2: 953

    Google Scholar 

  24. Mironov AA, Kister AE (1986) J Biomol Struct Dyn4: 1–9

    Google Scholar 

  25. Zuker M, mfold-2.0. ftp://snark.wustl.edu/pub/mfold-sgi-2.2.tar.Z. (Public Domain Software)

  26. Hofacker IL, Fontana W, Stadler PF, Bonhoeffer LS, Tacker M, Schuster P. Vienna RNA Package ftp://ftp.itc.univie.ac.at/pub/RNA/ViennaRNA-1.03. (Public Domain Software)

  27. Salser W (1977) Cold Spring Harbour Symp Quant Biol42: 985

    Google Scholar 

  28. Freier SM, Kierzek R, Jaeger JA, Sugimoto N, Caruthers MH, Neilson T, Turner DH (1986) Proc Natl Acad Sci USA83: 9373–9377

    Google Scholar 

  29. Jaeger JA, Turner DH, Zuker M (1989) Proc Natl Acad Sci USA Biochemistry86: 7706–7710

    Google Scholar 

  30. Tacker M, Stadler PF, Bornberg-Bauer EG, Hofacker IL, Schuster P (1995) (in preparation)

  31. Fontana W, Schuster P (1987) Biophys Chem26: 123–147

    Google Scholar 

  32. Konings DAM (1990) (private communication)

  33. Hogeweg P, Hesper B (1984) Nucl Acid Res12: 67–74

    Google Scholar 

  34. Shapiro BA, Zhang K (1990) CABIOS6: 309–318

    Google Scholar 

  35. Sakakibara Y, Brown M, Underwood RC, Saira Mian I, Haussler D (1993) Stochastic Contextfree Grammars for Modeling RNA. Report, UC Santa Cruz

  36. Sakakibara Y, Brown M, Hughey R, Mian IS, Sjölander K, Underwood RC, Haussler D (1993) The Application of Stochastic Context-free Grammars to Folding, Aligning and Modeling Homologous RNA Sequences. Report, UC Santa Cruz

  37. Hamming RW (1950) Bell Syst Tech J29: 147–160

    Google Scholar 

  38. Eschenmoser A (1993) Pure Appl Chem65: 1179–1188

    Google Scholar 

  39. Sant Lucia Jr. J, Kierzek R, Turner DH (1990) Biochemistry29: 8813–8819

    Google Scholar 

  40. Tinoco Jr. I, Chastain M, Chen X (1994) Clin Chem40: 646

    Google Scholar 

  41. Pley HW, Flaherty KM, McKay DB (1994) Nature372: 68–74

    Google Scholar 

  42. Pley HW, Flaherty KM, McKay DB (1994) Nature372: 111–113

    Google Scholar 

  43. Waterman MS (1978) Studies on Foundations and Combinatorics, Advances in Mathematics Supplementary Studies, Academic Press, New York,1: 167–212

    Google Scholar 

  44. Hofacker IL, Schuster P, Stadler PF (1993) SIAM J Disc Math (submitted)

  45. Zipf GK (1949) Human Behaviour and the Principle of Least Effort. Addison-Wesley, Reading, MA

    Google Scholar 

  46. Chen YS (1989) Int J Gen Syst15: 232

    Google Scholar 

  47. Mandelbrot BB (1983) The Fractal Geometry of Nature. Freeman & Co., New York

    Google Scholar 

Download references

Author information

Author notes

  1. P. Schuster

    Present address: Institut für Molekulare Biotechnologie, Beutenbergstraße 11, PF 100 813, D-07708, Jena, Germany

Authors and Affiliations

  1. Institut für Molekulare Biotechnologie, D-07708, Jena, Germany

    W. Grüner, C. Reidys, J. Weber & P. Schuster

  2. Technische Fakultät, Univ. Bielefeld, D-33501, Bielefeld, Germany

    R. Giegerich & D. Strothmann

  3. Institut für Theoretische Chemie, Universität Wien, A-1090, Wien, Austria

    I. L. Hofacker, P. F. Stadler & P. Schuster

  4. Santa Fe Institute, 87501, Santa Fe, NM, USA

    P. F. Stadler & P. Schuster

Authors
  1. W. Grüner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Giegerich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D. Strothmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. C. Reidys
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. J. Weber
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. I. L. Hofacker
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. P. F. Stadler
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. P. Schuster
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Grüner, W., Giegerich, R., Strothmann, D. et al. Analysis of RNA sequence structure maps by exhaustive enumeration I. Neutral networks. Monatsh Chem 127, 355–374 (1996). https://doi.org/10.1007/BF00810881

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00810881

Keywords

Search

Navigation