Question about RNA folding reference
Michael Zuker
zuker at ibc.wustl.edu
Tue Oct 17 20:28:16 EST 1995
Peter Reinert (a1624067 at athena.rrz.Uni-Koeln.DE) wrote:
: S. Park (separk at pollux.usc.edu) wrote:
: : Hello, I was once told that someone used dynamic programming in order to
: : solve the RNA folding problem. Could anyone tell me where that was
: : published ? Thank you very much for your time.
: : Regards,
: : Seongbin Park (separk at pollux.usc.edu)
: Here are some references:
: 1. Major, F., Turcotte, M., Gautheret, D., Lapalme, G., Fillion, E., and
: Cedergren, R.
: (1991) Science 253, 1255-1260.
: 2. Major, F., Gautheret, D., and R., C. (1993) Proc. Natl. Acad. Sci.
: (USA) 90, 9408-9412.
: 3. Gautheret, D., Major, F., and Cedergren, R. (1993) J. Mol. Biology
: 229, 1049-1064.
: Best regards,
: Peter Reinert
The references provided above by Peter Reinert are to works that use
a backtracking branch and bound algorithm to model three dimensional
RNA structure. This has nothing to do with dynamic programming, nor
are they related to predicting RNA secondary structure.
Predicting RNA secondary structure by dynamic programming algorithms
was done independently by a number of different people:
David Sankoff, Michael Waterman (he is Professor of Mathematics and
Biology at USC), Ruth Nussinov et al. and by me (Michael Zuker). The
earliest works attempted to maximize the number of base pairs. More
realistic energy rules were added later. Waterman and Byers described
a general technique to compute suboptimal solutions to dynamic
programming algorithms. Williams and Tinoco used this for the RNA
folding problem. I adopted a different technique. Papers by Roytberg
and McCaskill are very good. I have appended a bunch of references.
You may wish to contact me for further information.
__ ____ __ __
/ |/ (_)___/ / ___ ____ / / Tel: 314 362-2932, Fax: 362-0234 /
/ /|_/ / / __/ _ \/ _ `/ -_) / E-mail: zuker at snark.wustl.edu /
/_/ /_/_/\__/_//_/\_,_/\__/_/ URL: http://ibc.wustl.edu/~zuker /
____ __ __________________________________________________/
/_ / __ __/ /_____ ____ / Institute for Biomedical Computing/
/ /_/ // / '_/ -_) __/ / Washington University, CBox 8036 /
/___/\_,_/_/\_\\__/_/ / 700 S. Euclid Avenue /
_________________________/ St. Louis, MO 63110 _ _ _ _ _ _ _ /
RNA Folding References:
Early works (not complete)
D. Sankoff (1976) Evolution of secondary structure of 5S ribosomal
RNA, Paper presented at Tenth Numerical Taxonomy Conference, Lawrence,
Kansas.
M.S. Waterman (1978) Secondary structure of single-stranded nucleic
acids, Studies in Foundations and Combinatorics, Advances in Mathe-
matics, Supplementary Studies 1, 167-212.
R. Nussinov, G. Pieczenik, J.R. Griggs, and D.J. Kleitman (1978) Al-
gorithm for loop matchings, SIAM J. Appl. Math. 35, 68-82.
R. Nussinov and A. Jacobson (1980) Fast algorithm for predicting the
secondary structure of single-stranded RNA, Proc. Natl. Acad. Sci.
USA, Biochemistry 77, 6309-6313.
M. Zuker and P. Stiegler (1981) Optimal computer folding of large RNA
sequences using thermodynamics and auxiliary information, Nucleic
Acids Research 9, 133-148.
--------------------------------------------------------------------------
Loop dependent algorithms described in detail:
D. Sankoff, J.B. Kruskal, S. Mainville, and R.J. Cedergren (1984) Fast
algorithms to determine RNA secondary structures containing multiple
loops, (In) "Time warps, string edits, and macromolecules: the theory
and practice of sequence comparison", D. Sankoff, J.B. Kruskal, Eds.,
Addison-Wesley, Reading, 93-120.
M. Zuker and D. Sankoff (1984) RNA secondary structures and their
prediction, Bull. of Mathematical Biology 46, 591-621.
--------------------------------------------------------------------------
Waterman describes how to predict suboptimal solutions to dynamic
programming problems. Williams and Tinoco implement this. I take a
different approach.
Waterman, M.S. 1983. Sequence alignments in the neigh-
borhood of the optimum with general application to dynamic program-
ming. Proc. Natl. Acad. Sci. USA., 80, 3123-3124.
Waterman, M.S., & Byers, T.H. 1985. A dy-
namic programming algorithm to find all solutions in a neighborhood of
the optimum. Math. Biosci., 77, 179-188.
Williams, A.L., & Tinoco, I.Jr. 1986. A dynamic
programming algorithm for finding alternate RNA secondary structures.
Nucleic Acids Res., 14, 299-315.
--------------------------------------------------------------------------
M. Zuker (1989) The use of dynamic programming algorithms in RNA
secondary structure prediction, in "Mathematical Methods for DNA
Sequences", M. S. Waterman ed., CRC Press, Inc., 159-184.
- rehash of older work, some description of my approach to suboptimal
folding; base-pair dependent and loop-dependent energy rules
described explicitly
D.H. Turner, N. Sugimoto and S.M. Freier (1988) RNA structure pre-
diction. Annu. Rev. Biophys. Biophys. Chem. 17, 167-192.
- good article by Doug Turner, easy for a novice to understand
----------------------------------------------------------------------------
M. Zuker (1989) On finding all suboptimal foldings of an RNA molecule,
Science 244, 48-52.
J.A. Jaeger, D.H. Turner and M. Zuker (1990) Predicting optimal
and suboptimal secondary structure for RNA, in "Molecular Evolu-
tion: Computer Analysis of Protein and Nucleic Acid Sequences", R.
F. Doolittle ed., Methods in Enzymology 183, 281-306.
- description of my suboptimal folding algorithm
----------------------------------------------------------------------
Finkelstein, A.V., & Roytberg, M.A. 1993.
Computation of biopolymers: a general approach to different problems.
Biosystems, 30, 1-19.
McCaskill, J.S. 1990. The equilibrium partition function
and base pair binding probabilities for RNA secondary structure. Biopoly-
mers, 29, 1105-19.
- Both articles are superb. The first deals with a unified framework
for using dynamic programming on biopolymers. McCaskill uses dynamic
programming to compute partition functions for the RNA secondary
structure problem.
----------------------------------------------------------------------
M. Zuker (1989) Computer prediction of RNA structure, in "RNA Pro-
cessing", J. E. Dahlberg and J. N. Abelson eds., Methods in Enzymology
180, 262-288.
Zuker, M. 1994. Prediction of RNA Secondary Strcture by En-
ergy Minimization. Computer Analysis of Sequence Data, Part II, A.M.
Griffin & H.G Griffin, Eds., vol. 25. Totowa, NJ: CRC Press, Inc. Chap-
ter 23, pages 267-294.
- "how-to" articles; the first on older RNA folding algorithms; the
second on my newer suboptimal algorithm
More information about the Comp-bio
mailing list