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