Skip to main content
SpringerLink
Log in

Fast folding and comparison of RNA secondary structures

Schnelle Faltung und Vergleich von Sekundärstrukturen von RNA

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

Summary

Computer codes for computation and comparison of RNA secondary structures, the Vienna RNA package, are presented, that are based on dynamic programming algorithms and aim at predictions of structures with minimum free energies as well as at computations of the equilibrium partition functions and base pairing probabilities.

An efficient heuristic for the inverse folding problem of RNA is introduced. In addition we present compact and efficient programs for the comparison of RNA secondary structures based on tree editing and alignment.

All computer codes are written in ANSI C. They include implementations of modified algorithms on parallel computers with distributed memory. Performance analysis carried out on an Intel Hypercube shows that parallel computing becomes gradually more and more efficient the longer the sequences are.

Zusammenfassung

Die im Vienna RNA package enthaltenen Computer Programme für die Berechnung und den Vergleich von RNA Sekundärstrukturen werden präsentiert. Ihren Kern bilden Algorithmen zur Vorhersage von Strukturen minimaler Energie sowie zur Berechnung von Zustandssumme und Basenpaarungswahrscheinlichkeiten mittels dynamischer Programmierung.

Ein effizienter heuristischer Algorithmus für das inverse Faltungsproblem wird vorgestellt. Darüberhinaus präsentieren wir kompakte und effiziente Programme zum Vergleich von RNA Sekundärstrukturen durch Baum-Editierung und Alignierung.

Alle Programme sind in ANSI C geschrieben, darunter auch eine Implementation des Faltungs-algorithmus für Parallelrechner mit verteiltem Speicher. Wie Tests auf einem Intel Hypercube zeigen, wird das Parallelrechnen umso effizienter je länger die Sequenzen sind.

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. Cech T. R., Bass B. L. (1986) Annu. Rev. Biochem.55: 599–629

    Google Scholar 

  2. Symons R. H. (1992) Small catalytic RNAs. Annu. Rev. Biochem.61: 641–671

    Google Scholar 

  3. Beaudry A. A., Joyce G. F. (1992) Science257: 635–641

    Google Scholar 

  4. Ellington A. D., Szostak J. W. (1990) Nature346: 818–822

    Google Scholar 

  5. Fontana W., Griesmacher T., Schnabl W., Stadler P. F., Schuster P. (1991) Mh. Chem.122: 795–819

    Google Scholar 

  6. Fontana W., Stadler P. F., Bornberg-Bauer E., Griesmacher T., Hofacker I. L., Tacker M., Tarazona P., Weinberger E. D., Schuster P. (1993a) Phys. Rev. E47: 2083–2099

    Google Scholar 

  7. Fontana W., Konings D. A. M., Stadler P. F., Schuster, P. (1993b) Biopolymers33: 1389–1404

    Google Scholar 

  8. Eigen M., Winkler-Oswatitsch R., Dress A. (1988) Proc. Natl. Acad. Sci. USA85: 5913–5917

    Google Scholar 

  9. Bandelt H.-J., Dress A. W. M. (1992) Adv. Math.92: 47–105

    Google Scholar 

  10. Zuker M., Stiegler P. (1981) Nucleic Acids Res.9: 133–148

    Google Scholar 

  11. Zuker M., Sankoff D. (1984) Bull. Math. Biol.46: 591–621

    Google Scholar 

  12. McCaskill J. S. (1990) Biopolymers29: 1105–1119

    Google Scholar 

  13. Waterman M. S. (1978) Advances in Mathematics Suppl. Studies. Vol. 1. New York: Academic Press, pp. 167–212

    Google Scholar 

  14. Waterman M. S., Smith T. F. (1978) Math. Biosc.42: 257–266

    Google Scholar 

  15. Nussinov R., Jocobson A. B. (1980) Proc. Natl. Acad. Sci. USA77: 6309–6313

    Google Scholar 

  16. Nussinov R., Pieczenik G., Griggs J. R., Kleitman D. J. (1978) SIAM J. Appl. Math.35: 68–82

    Google Scholar 

  17. Martinz H. M. (1984) Nucleic Acids Res.12: 323–334

    Google Scholar 

  18. Schuster P., Fontana W., Stadler P. F., Hofacker I. L. (1993) Preprint

  19. Tacker M., Fontana W., Stadler P. F., Schuster P. (1993) Preprint

  20. Fontana W., Schuster P. (1987) Biophys. Chem.26: 123–147

    Google Scholar 

  21. Fontana W., Schnabl W., Schuster P. (1989) Phys. Rev. A40: 3301–3321

    Google Scholar 

  22. Freier S. M., Kierzek R., Jaeger J. A., Sugimoto N., Caruthers M. H., Neilson T., Turner D. H. (1986) Proc. Natl. Acad. Sci. USA83: 9373–9377

    Google Scholar 

  23. Jaeger J. A., Turner D. H., Zuker M. (1989) Proc. Natl. Acad. Sci. USA86: 7706–7710

    Google Scholar 

  24. Zuker M. (1989) Science244: 48–52

    Google Scholar 

  25. Shapiro B. (1988) CABIOS4: 387–393

    Google Scholar 

  26. Shapiro B., Zhang K. (1990) CABIOS6: 309–318

    Google Scholar 

  27. Tai K. (1979) J. ACM26: 422–433

    Google Scholar 

  28. Sankoff D., Kruskal J. B. (1983) London: Addison Wesley

  29. Hogeweg P., Hesper B. (1984) Nucleic Acids Res.12: 67–74

    Google Scholar 

  30. Konings D. A. M. (1989) Proefschrift, Rijksuniversiteit te Utrecht

  31. Konings D. A. M., Hogeweg P. (1989) J. Mol. Biol.207: 597–614

    Google Scholar 

  32. Bonhoeffer S., McCaskill J. S., Stadler P. F., Schuster P. (1993) Eur. Biophys. J.22: 13–24

    Google Scholar 

  33. Waterman M. S. (1984) Bull. Math. Biol.46: 473–500

    Google Scholar 

  34. Jacobson A. B. (1991) J. Mol. Biol.221: 557–570

    Google Scholar 

  35. Eigen M., Gardiner W. (1984) Pure Appl. Chem.56: 967–978

    Google Scholar 

  36. Kauffman S. A. (1992) J. Theor. Biol.157: 1–7

    Google Scholar 

  37. Hofacker I. L., Schuster P., Stadler P. F. (1993) Preprint

Download references

Author information

Authors and Affiliations

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

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

  2. Institut für Molekulare Biotechnologie, D-07745, Jena, Federal Republic of Germany

    P. Schuster

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

    W. Fontana, P. F. Stadler & P. Schuster

  4. Department of Zoology, University of Oxford, South Parks Road, OX1 3PS, Oxford, UK

    L. S. Bonhoeffer

Authors
  1. I. L. Hofacker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. W. Fontana
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. F. Stadler
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. L. S. Bonhoeffer
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. M. Tacker
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. 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

Hofacker, I.L., Fontana, W., Stadler, P.F. et al. Fast folding and comparison of RNA secondary structures. Monatsh Chem 125, 167–188 (1994). https://doi.org/10.1007/BF00818163

Download citation

  • Received:

  • Accepted:

  • Issue Date:

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

Keywords

Search

Navigation