Nucleic Acids Research, 1981, Vol. 9, No. 1 133-148
© 1981
MOLECULAR BIOLOGY |
Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information
Division of Biological Sciences, National Research Council of Canada Ottawa K1A 0R6, Canada
Received November 5, 1980.
This paper presents a new computer method for folding an RNA molecule that finds a conformation of minimum free energy using published values of stacking and destabilizing energies. It is based on a dynamic programming algorithm from applied mathematics, and is much more efficient, faster, and can fold larger molecules than procedures which have appeared up to now in the biological literature. Its power is demonstrated in the folding of a 459 nucleotide immunoglobulin 
1 heavy chain messenger RNA fragment. We go beyond the basic method to show how to incorporate additional information into the algorithm. This includes data on chemical reactivity and enzyme susceptibility. We illustrate this with the folding of two large fragments from the 16S ribosomal RNA of Escherichia coli.
$NRCC number 18755
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. M. Landau, H. Lokstein, H. V. Scheller, V. Lainez, S. Maldonado, and A. R. Prina A Cytoplasmically Inherited Barley Mutant Is Defective in Photosystem I Assembly Due to a Temperature-Sensitive Defect in ycf3 Splicing Plant Physiology, December 1, 2009; 151(4): 1802 - 1811. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. H. Bernhart and I. L. Hofacker From consensus structure prediction to RNA gene finding Brief Funct Genomic Proteomic, November 1, 2009; 8(6): 461 - 471. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 I. A. Drinnenberg, D. E. Weinberg, K. T. Xie, J. P. Mower, K. H. Wolfe, G. R. Fink, and D. P. Bartel RNAi in Budding Yeast Science, October 23, 2009; 326(5952): 544 - 550. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. W. D. Huang, J. Qin, C. M. Reidys, and P. F. Stadler Partition function and base pairing probabilities for RNA-RNA interaction prediction Bioinformatics, October 15, 2009; 25(20): 2646 - 2654. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y.-C. Hsieh, N. E. Skacel, N. Bansal, K. W. Scotto, D. Banerjee, J. R. Bertino, and E. E. Abali Species-Specific Differences in Translational Regulation of Dihydrofolate Reductase Mol. Pharmacol., October 1, 2009; 76(4): 723 - 733. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. J. Schroeder Advances in RNA Structure Prediction from Sequence: New Tools for Generating Hypotheses about Viral RNA Structure-Function Relationships J. Virol., July 1, 2009; 83(13): 6326 - 6334. [Full Text] [PDF]
|
|
|
|
 |
|
 K. Sato, M. Hamada, K. Asai, and T. Mituyama CENTROIDFOLD: a web server for RNA secondary structure prediction Nucleic Acids Res., July 1, 2009; 37(suppl_2): W277 - W280. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Waldispuhl, S. Devadas, B. Berger, and P. Clote RNAmutants: a web server to explore the mutational landscape of RNA secondary structures Nucleic Acids Res., July 1, 2009; 37(suppl_2): W281 - W286. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Chitsaz, R. Salari, S. C. Sahinalp, and R. Backofen A partition function algorithm for interacting nucleic acid strands Bioinformatics, June 15, 2009; 25(12): i365 - i373. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Das Evolutionary Origin and Genomic Organization of Micro-RNA Genes in Immunoglobulin Lambda Variable Region Gene Family Mol. Biol. Evol., May 1, 2009; 26(5): 1179 - 1189. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Smit, R. Knight, and J. Heringa RNA structure prediction from evolutionary patterns of nucleotide composition Nucleic Acids Res., April 1, 2009; 37(5): 1378 - 1386. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Hamada, H. Kiryu, K. Sato, T. Mituyama, and K. Asai Prediction of RNA secondary structure using generalized centroid estimators Bioinformatics, February 15, 2009; 25(4): 465 - 473. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Xing, D. L. Bitzer, W. E. Alexander, M. A. Vouk, and A.-M. Stomp Identification of protein-coding sequences using the hybridization of 18S rRNA and mRNA during translation Nucleic Acids Res., February 1, 2009; 37(2): 591 - 601. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Busch, A. S. Richter, and R. Backofen IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions Bioinformatics, December 15, 2008; 24(24): 2849 - 2856. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Davis, S. M. Sagan, J. P. Pezacki, D. J. Evans, and P. Simmonds Bioinformatic and Physical Characterizations of Genome-Scale Ordered RNA Structure in Mammalian RNA Viruses J. Virol., December 1, 2008; 82(23): 11824 - 11836. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Tafer and I. L. Hofacker RNAplex: a fast tool for RNA-RNA interaction search Bioinformatics, November 15, 2008; 24(22): 2657 - 2663. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Piskol and W. Stephan Analyzing the Evolution of RNA Secondary Structures in Vertebrate Introns Using Kimura's Model of Compensatory Fitness Interactions Mol. Biol. Evol., November 1, 2008; 25(11): 2483 - 2492. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. O. dos Santos, L. C. Dore, E. Valentine, S. G. Shelat, R. C. Hardison, M. Ghosh, W. Wang, R. S. Eisenstein, F. F. Costa, and M. J. Weiss An Iron Responsive Element-like Stem-Loop Regulates {alpha}-Hemoglobin-stabilizing Protein mRNA J. Biol. Chem., October 3, 2008; 283(40): 26956 - 26964. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Theis, J. Reeder, and R. Giegerich KnotInFrame: prediction of -1 ribosomal frameshift events Nucleic Acids Res., October 1, 2008; 36(18): 6013 - 6020. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. K. Holloway, D. J. Begun, A. Siepel, and K. S. Pollard Accelerated sequence divergence of conserved genomic elements in Drosophila melanogaster Genome Res., October 1, 2008; 18(10): 1592 - 1601. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Chen, S.-M. He, D. Bu, F. Zhang, Z. Wang, R. Chen, and W. Gao FlexStem: improving predictions of RNA secondary structures with pseudoknots by reducing the search space Bioinformatics, September 15, 2008; 24(18): 1994 - 2001. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Capriotti and M. A. Marti-Renom RNA structure alignment by a unit-vector approach Bioinformatics, August 15, 2008; 24(16): i112 - i118. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. R. Gruber, R. Lorenz, S. H. Bernhart, R. Neubock, and I. L. Hofacker The Vienna RNA Websuite Nucleic Acids Res., July 1, 2008; 36(suppl_2): W70 - W74. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Torarinsson and S. Lindgreen WAR: Webserver for aligning structural RNAs Nucleic Acids Res., July 1, 2008; 36(suppl_2): W79 - W84. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Owczarzy, A. V. Tataurov, Y. Wu, J. A. Manthey, K. A. McQuisten, H. G. Almabrazi, K. F. Pedersen, Y. Lin, J. Garretson, N. O. McEntaggart, et al. IDT SciTools: a suite for analysis and design of nucleic acid oligomers Nucleic Acids Res., July 1, 2008; 36(suppl_2): W163 - W169. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Sczyrba, S. Konermann, and R. Giegerich Two interactive Bioinformatics courses at the Bielefeld University Bioinformatics Server Brief Bioinform, May 1, 2008; 9(3): 243 - 249. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. Sperschneider and A. Datta KnotSeeker: Heuristic pseudoknot detection in long RNA sequences RNA, April 1, 2008; 14(4): 630 - 640. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Lindgreen, P. P. Gardner, and A. Krogh MASTR: multiple alignment and structure prediction of non-coding RNAs using simulated annealing Bioinformatics, December 15, 2007; 23(24): 3304 - 3311. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. M. Meyer A practical guide to the art of RNA gene prediction Brief Bioinform, November 1, 2007; 8(6): 396 - 414. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. S. Andersen, A. Lind-Thomsen, B. Knudsen, S. E. Kristensen, J. H. Havgaard, E. Torarinsson, N. Larsen, C. Zwieb, P. Sestoft, J. Kjems, et al. Semiautomated improvement of RNA alignments RNA, November 1, 2007; 13(11): 1850 - 1859. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 N. Kashtan, E. Noor, and U. Alon Varying environments can speed up evolution PNAS, August 21, 2007; 104(34): 13711 - 13716. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. L. Thorne, S. C. Choi, J. Yu, P. G. Higgs, and H. Kishino Population Genetics Without Intraspecific Data Mol. Biol. Evol., August 1, 2007; 24(8): 1667 - 1677. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Reeder, P. Steffen, and R. Giegerich pknotsRG: RNA pseudoknot folding including near-optimal structures and sliding windows Nucleic Acids Res., July 13, 2007; 35(suppl_2): W320 - W324. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Aksay, R. Salari, E. Karakoc, C. Alkan, and S. C. Sahinalp taveRNA: a web suite for RNA algorithms and applications Nucleic Acids Res., July 13, 2007; 35(suppl_2): W325 - W329. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. Shu, X. Bo, Z. Zheng, and S. Wang RSRE: RNA structural robustness evaluator Nucleic Acids Res., July 13, 2007; 35(suppl_2): W314 - W319. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Itzkovitz and U. Alon The genetic code is nearly optimal for allowing additional information within protein-coding sequences Genome Res., April 1, 2007; 17(4): 405 - 412. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Bollenbach, K. Vetsigian, and R. Kishony Evolution and multilevel optimization of the genetic code Genome Res., April 1, 2007; 17(4): 401 - 404. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X.-L. Li, J. B. Andersen, H. J. Ezelle, G. M. Wilson, and B. A. Hassel Post-transcriptional Regulation of RNase-L Expression Is Mediated by the 3'-Untranslated Region of Its mRNA J. Biol. Chem., March 16, 2007; 282(11): 7950 - 7960. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. NG Kwang Loong and S. K. Mishra Unique folding of precursor microRNAs: Quantitative evidence and implications for de novo identification RNA, February 1, 2007; 13(2): 170 - 187. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Huang and H. Ali High sensitivity RNA pseudoknot prediction Nucleic Acids Res., January 28, 2007; 35(2): 656 - 663. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Lindgreen, P. P. Gardner, and A. Krogh Measuring covariation in RNA alignments: physical realism improves information measures Bioinformatics, December 15, 2006; 22(24): 2988 - 2995. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Voss Structural analysis of aligned RNAs Nucleic Acids Res., November 14, 2006; 34(19): 5471 - 5481. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Jaeger, F. Martin, J. Rudinger-Thirion, R. Giege, and G. Eriani Binding of human SLBP on the 3'-UTR of histone precursor H4-12 mRNA induces structural rearrangements that enable U7 snRNA anchoring Nucleic Acids Res., October 18, 2006; 34(17): 4987 - 4995. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J.-H. Yang, X.-C. Zhang, Z.-P. Huang, H. Zhou, M.-B. Huang, S. Zhang, Y.-Q. Chen, and L.-H. Qu snoSeeker: an advanced computational package for screening of guide and orphan snoRNA genes in the human genome Nucleic Acids Res., October 6, 2006; (2006) gkl672v3. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. D. Baird, M. Turcotte, R. G. Korneluk, and M. Holcik Searching for IRES RNA, October 1, 2006; 12(10): 1755 - 1785. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Busch and R. Backofen INFO-RNA--a fast approach to inverse RNA folding Bioinformatics, August 1, 2006; 22(15): 1823 - 1831. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Yu and J. L. Thorne Dependence among Sites in RNA Evolution Mol. Biol. Evol., August 1, 2006; 23(8): 1525 - 1537. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Tabei, K. Tsuda, T. Kin, and K. Asai SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments Bioinformatics, July 15, 2006; 22(14): 1723 - 1729. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Dezulian, M. Schaefer, R. Wiese, D. Weigel, and D. H. Huson CrossLink: visualization and exploration of sequence relationships between (micro) RNAs. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W400 - W404. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Kruger and M. Rehmsmeier RNAhybrid: microRNA target prediction easy, fast and flexible. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W451 - W454. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. V. Mukha, A. G. Chumachenko, M. J. Dykstra, T. J. Kurtti, and C. Schal Characterization of a new densovirus infecting the German cockroach, Blattella germanica J. Gen. Virol., June 1, 2006; 87(6): 1567 - 1575. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Y. Ogurtsov, S. A. Shabalina, A. S. Kondrashov, and M. A. Roytberg Analysis of internal loops within the RNA secondary structure in almost quadratic time Bioinformatics, June 1, 2006; 22(11): 1317 - 1324. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
U. Muckstein, H. Tafer, J. Hackermuller, S. H. Bernhart, P. F. Stadler, and I. L. Hofacker Thermodynamics of RNA-RNA binding Bioinformatics, May 15, 2006; 22(10): 1177 - 1182. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. L. Hofacker and P. F. Stadler Memory efficient folding algorithms for circular RNA secondary structures Bioinformatics, May 15, 2006; 22(10): 1172 - 1176. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Borenstein and E. Ruppin Direct evolution of genetic robustness in microRNA PNAS, April 25, 2006; 103(17): 6593 - 6598. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. C. Wiese and A. Hendriks Comparison of P-RnaPredict and mfold--algorithms for RNA secondary structure prediction Bioinformatics, April 15, 2006; 22(8): 934 - 942. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. DING Statistical and Bayesian approaches to RNA secondary structure prediction. RNA, March 1, 2006; 12(3): 323 - 331. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. BINDEWALD and B. A. SHAPIRO RNA secondary structure prediction from sequence alignments using a network of k-nearest neighbor classifiers. RNA, March 1, 2006; 12(3): 342 - 352. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. SMIT, M. YARUS, and R. KNIGHT Natural selection is not required to explain universal compositional patterns in rRNA secondary structure categories RNA, January 1, 2006; 12(1): 1 - 14. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. R. Fortune, M. Suyemoto, and C. Altier Identification of CsrC and Characterization of Its Role in Epithelial Cell Invasion in Salmonella enterica Serovar Typhimurium Infect. Immun., January 1, 2006; 74(1): 331 - 339. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Tjaden, S. S. Goodwin, J. A. Opdyke, M. Guillier, D. X. Fu, S. Gottesman, and G. Storz Target prediction for small, noncoding RNAs in bacteria. Nucleic Acids Res., January 1, 2006; 34(9): 2791 - 2802. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. Clote, J. Waldispuhl, B. Behzadi, and J.-M. Steyaert Energy landscape of k-point mutants of an RNA molecule Bioinformatics, November 15, 2005; 21(22): 4140 - 4147. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. WOLF, M. ACHTZIGER, J. SCHULTZ, T. DANDEKAR, and T. MULLER Homology modeling revealed more than 20,000 rRNA internal transcribed spacer 2 (ITS2) secondary structures RNA, November 1, 2005; 11(11): 1616 - 1623. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Knight, H. De Sterck, R. Markel, S. Smit, A. Oshmyansky, and M. Yarus Abundance of correctly folded RNA motifs in sequence space, calculated on computational grids Nucleic Acids Res., October 19, 2005; 33(18): 5924 - 5935. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Y. Chan, C. E. Lawrence, and Y. Ding Structure clustering features on the Sfold Web server Bioinformatics, October 15, 2005; 21(20): 3926 - 3928. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. REN, B. RASTEGARI, A. CONDON, and H. H. HOOS HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots RNA, October 1, 2005; 11(10): 1494 - 1504. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. Biyani and K. Nishigaki Single-Strand Conformation Polymorphism (SSCP) of Oligodeoxyribonucleotides: An Insight into Solution Structural Dynamics of DNAs Provided by Gel Electrophoresis and Molecular Dynamics Simulations J. Biochem., October 1, 2005; 138(4): 363 - 373. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Wang, J. Zhang, F. Li, J. Gu, T. He, X. Zhang, and Y. Li MicroRNA identification based on sequence and structure alignment Bioinformatics, September 15, 2005; 21(18): 3610 - 3614. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C.-H. Huang, C. L. Lu, and H.-T. Chiu A heuristic approach for detecting RNA H-type pseudoknots Bioinformatics, September 1, 2005; 21(17): 3501 - 3508. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Reeder and R. Giegerich Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction Bioinformatics, September 1, 2005; 21(17): 3516 - 3523. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. DING, C. Y. CHAN, and C. E. LAWRENCE RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble RNA, August 1, 2005; 11(8): 1157 - 1166. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. C. Cowperthwaite, J. J. Bull, and L. A. Meyers Distributions of Beneficial Fitness Effects in RNA Genetics, August 1, 2005; 170(4): 1449 - 1457. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
V. Zeenko and D. R. Gallie Cap-independent Translation of Tobacco Etch Virus Is Conferred by an RNA Pseudoknot in the 5'-Leader J. Biol. Chem., July 22, 2005; 280(29): 26813 - 26824. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Xayaphoummine, T. Bucher, and H. Isambert Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots Nucleic Acids Res., July 1, 2005; 33(suppl_2): W605 - W610. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. CLOTE, F. FERRE, E. KRANAKIS, and D. KRIZANC Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency RNA, May 1, 2005; 11(5): 578 - 591. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. H. Havgaard, R. B. Lyngso, G. D. Stormo, and J. Gorodkin Pairwise local structural alignment of RNA sequences with sequence similarity less than 40% Bioinformatics, May 1, 2005; 21(9): 1815 - 1824. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Hayashi, H. Banno, K. Kadomatsu, Y. Takei, K. Komori, and T. Muramatsu Antisense oligodeoxyribonucleotide as to the growth factor midkine suppresses neointima formation induced by balloon injury Am J Physiol Heart Circ Physiol, May 1, 2005; 288(5): H2203 - H2209. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. P. Gardner, A. Wilm, and S. Washietl A benchmark of multiple sequence alignment programs upon structural RNAs Nucleic Acids Res., April 28, 2005; 33(8): 2433 - 2439. [Abstract] [Full Text] [PDF]
|
|