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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Cech T. R., Bass B. L. (1986) Annu. Rev. Biochem.55: 599–629
Symons R. H. (1992) Small catalytic RNAs. Annu. Rev. Biochem.61: 641–671
Beaudry A. A., Joyce G. F. (1992) Science257: 635–641
Ellington A. D., Szostak J. W. (1990) Nature346: 818–822
Fontana W., Griesmacher T., Schnabl W., Stadler P. F., Schuster P. (1991) Mh. Chem.122: 795–819
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
Fontana W., Konings D. A. M., Stadler P. F., Schuster, P. (1993b) Biopolymers33: 1389–1404
Eigen M., Winkler-Oswatitsch R., Dress A. (1988) Proc. Natl. Acad. Sci. USA85: 5913–5917
Bandelt H.-J., Dress A. W. M. (1992) Adv. Math.92: 47–105
Zuker M., Stiegler P. (1981) Nucleic Acids Res.9: 133–148
Zuker M., Sankoff D. (1984) Bull. Math. Biol.46: 591–621
McCaskill J. S. (1990) Biopolymers29: 1105–1119
Waterman M. S. (1978) Advances in Mathematics Suppl. Studies. Vol. 1. New York: Academic Press, pp. 167–212
Waterman M. S., Smith T. F. (1978) Math. Biosc.42: 257–266
Nussinov R., Jocobson A. B. (1980) Proc. Natl. Acad. Sci. USA77: 6309–6313
Nussinov R., Pieczenik G., Griggs J. R., Kleitman D. J. (1978) SIAM J. Appl. Math.35: 68–82
Martinz H. M. (1984) Nucleic Acids Res.12: 323–334
Schuster P., Fontana W., Stadler P. F., Hofacker I. L. (1993) Preprint
Tacker M., Fontana W., Stadler P. F., Schuster P. (1993) Preprint
Fontana W., Schuster P. (1987) Biophys. Chem.26: 123–147
Fontana W., Schnabl W., Schuster P. (1989) Phys. Rev. A40: 3301–3321
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
Jaeger J. A., Turner D. H., Zuker M. (1989) Proc. Natl. Acad. Sci. USA86: 7706–7710
Zuker M. (1989) Science244: 48–52
Shapiro B. (1988) CABIOS4: 387–393
Shapiro B., Zhang K. (1990) CABIOS6: 309–318
Tai K. (1979) J. ACM26: 422–433
Sankoff D., Kruskal J. B. (1983) London: Addison Wesley
Hogeweg P., Hesper B. (1984) Nucleic Acids Res.12: 67–74
Konings D. A. M. (1989) Proefschrift, Rijksuniversiteit te Utrecht
Konings D. A. M., Hogeweg P. (1989) J. Mol. Biol.207: 597–614
Bonhoeffer S., McCaskill J. S., Stadler P. F., Schuster P. (1993) Eur. Biophys. J.22: 13–24
Waterman M. S. (1984) Bull. Math. Biol.46: 473–500
Jacobson A. B. (1991) J. Mol. Biol.221: 557–570
Eigen M., Gardiner W. (1984) Pure Appl. Chem.56: 967–978
Kauffman S. A. (1992) J. Theor. Biol.157: 1–7
Hofacker I. L., Schuster P., Stadler P. F. (1993) Preprint
Author information
Authors and Affiliations
Rights 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
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00818163