Nucleic Acids Research, 2003, Vol. 31, No. 24 7280-7301
© 2003 Oxford University Press
Article |
A statistical sampling algorithm for RNA secondary structure prediction
Bioinformatics Center, Wadsworth Center, New York State Department of Health, 150 New Scotland Avenue, Albany, NY 12208, USA
*To whom correspondence should be addressed. Tel: +1 518 486 1719; Fax: +1 518 473 2900; Email: yding{at}wadsworth.org
An RNA molecule, particularly a long-chain mRNA, may exist as a population of structures. Further more, multiple structures have been demonstrated to play important functional roles. Thus, a representation of the ensemble of probable structures is of interest. We present a statistical algorithm to sample rigorously and exactly from the Boltzmann ensemble of secondary structures. The forward step of the algorithm computes the equilibrium partition functions of RNA secondary structures with recent thermodynamic parameters. Using conditional probabilities computed with the partition functions in a recursive sampling process, the backward step of the algorithm quickly generates a statistically representative sample of structures. With cubic run time for the forward step, quadratic run time in the worst case for the sampling step, and quadratic storage, the algorithm is efficient for broad applicability. We demonstrate that, by classifying sampled structures, the algorithm enables a statistical delineation and representation of the Boltzmann ensemble. Applications of the algorithm show that alternative biological structures are revealed through sampling. Statistical sampling provides a means to estimate the probability of any structural motif, with or without constraints. For example, the algorithm enables probability profiling of single-stranded regions in RNA secondary structure. Probability profiling for specific loop types is also illustrated. By overlaying probability profiles, a mutual accessibility plot can be displayed for predicting RNA:RNA interactions. Boltzmann probability-weighted density of states and free energy distributions of sampled structures can be readily computed. We show that a sample of moderate size from the ensemble of an enormous number of possible structures is sufficient to guarantee statistical reproducibility in the estimates of typical sampling statistics. Our applications suggest that the sampling algorithm may be well suited to prediction of mRNA structure and target accessibility. The algorithm is applicable to the rational design of small interfering RNAs (siRNAs), antisense oligonucleotides, and trans-cleaving ribozymes in gene knock-down studies.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  T. T. Tran, F. Zhou, S. Marshburn, M. Stead, S. R. Kushner, and Y. Xu De novo computational prediction of non-coding RNA genes in prokaryotic genomes Bioinformatics, November 15, 2009; 25(22): 2897 - 2905. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Z. J. Lu, J. W. Gloor, and D. H. Mathews Improved RNA secondary structure prediction by maximizing expected pair accuracy RNA, October 1, 2009; 15(10): 1805 - 1813. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Nakamura A Novel Virtual Spectrometry: Visualized Regulatory Motifs on ADM, rPol{beta} and CD83 mRNAs in Human-friendly Manners J. Biochem., August 1, 2009; 146(2): 251 - 261. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. O. Harmanci, G. Sharma, and D. H. Mathews Stochastic sampling of the RNA structural alignment space Nucleic Acids Res., July 1, 2009; 37(12): 4063 - 4075. [Abstract] [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]
|
|
|
|
 |
|
 K. Rezvani, Y. Teng, Y. Pan, J. A. Dani, J. Lindstrom, E. A. Garcia Gras, J. M. McIntosh, and M. De Biasi UBXD4, a UBX-Containing Protein, Regulates the Cell Surface Number and Stability of {alpha}3-Containing Nicotinic Acetylcholine Receptors J. Neurosci., May 27, 2009; 29(21): 6883 - 6896. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Zhou, J. Zhang, C. Wang, J. R. Bliesath, Q. He, D. Yu, Z. Li-He, and F. Wong-Staal A method for detecting and preventing negative RNA interference in preparation of lentiviral vectors for siRNA delivery RNA, April 1, 2009; 15(4): 732 - 740. [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]
|
|
|
|
 |
|
 N. Woodford, D. W. Wareham, and on behalf of the UK Antibacterial Antisense Study Tackling antibiotic resistance: a dose of common antisense? J. Antimicrob. Chemother., February 1, 2009; 63(2): 225 - 229. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. M. Yoffe, P. Prinsen, A. Gopal, C. M. Knobler, W. M. Gelbart, and A. Ben-Shaul Predicting the sizes of large RNA molecules PNAS, October 21, 2008; 105(42): 16153 - 16158. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Diviney, A. Tuplin, M. Struthers, V. Armstrong, R. M. Elliott, P. Simmonds, and D. J. Evans A Hepatitis C Virus cis-Acting Replication Element Forms a Long-Range RNA-RNA Interaction with Upstream RNA Sequences in NS5B J. Virol., September 15, 2008; 82(18): 9008 - 9022. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Z. J. Lu and D. H. Mathews Efficient siRNA selection using hybridization thermodynamics Nucleic Acids Res., February 2, 2008; 36(2): 640 - 647. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S.-D. Hsu, C.-H. Chu, A.-P. Tsou, S.-J. Chen, H.-C. Chen, P. W.-C. Hsu, Y.-H. Wong, Y.-H. Chen, G.-H. Chen, and H.-D. Huang miRNAMap 2.0: genomic maps of microRNAs in metazoan genomes Nucleic Acids Res., January 11, 2008; 36(suppl_1): D165 - D169. [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]
|
|
|
|
|
|
Y. Shao, C. Y. Chan, A. Maliyekkel, C. E. Lawrence, I. B. Roninson, and Y. Ding Effect of target secondary structure on RNAi efficiency RNA, October 1, 2007; 13(10): 1631 - 1640. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Freyhult, V. Moulton, and P. Clote Boltzmann probability of RNA structural neighbors and riboswitch detection Bioinformatics, August 15, 2007; 23(16): 2054 - 2062. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Freyhult, V. Moulton, and P. Clote RNAbor: a web server for RNA structural neighbors Nucleic Acids Res., July 13, 2007; 35(suppl_2): W305 - W309. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. Kim, H. H. Gan, and T. Schlick A computational proposal for designing structured RNA pools for in vitro selection of RNAs RNA, April 1, 2007; 13(4): 478 - 492. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. Ladunga More complete gene silencing by fewer siRNAs: transparent optimized design and biophysical signature Nucleic Acids Res., January 28, 2007; 35(2): 433 - 440. [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]
|
|
|
|
|
|
Y. Shao, Y. Wu, C. Y. Chan, K. McDonough, and Y. Ding Rational design and rapid screening of antisense oligonucleotides for prokaryotic gene modulation Nucleic Acids Res., November 14, 2006; 34(19): 5660 - 5669. [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]
|
|
|
|
|
|
E. Kierzek, D. H. Mathews, A. Ciesielska, D. H. Turner, and R. Kierzek Nearest neighbor parameters for Watson-Crick complementary heteroduplexes formed between 2'-O-methyl RNA and RNA oligonucleotides Nucleic Acids Res., July 26, 2006; 34(13): 3609 - 3614. [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]
|
|
|
|
|
|
Y. DING Statistical and Bayesian approaches to RNA secondary structure prediction. RNA, March 1, 2006; 12(3): 323 - 331. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. Steffen, B. Voss, M. Rehmsmeier, J. Reeder, and R. Giegerich RNAshapes: an integrated RNA analysis package based on abstract shapes Bioinformatics, February 15, 2006; 22(4): 500 - 503. [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]
|
|
|
|
|
|
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]
|
|
|
|
|
|
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]
|
|
|
|
|
|
D. H. Mathews Predicting a set of minimal free energy RNA secondary structures common to two sequences Bioinformatics, May 15, 2005; 21(10): 2246 - 2253. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Santoyo, J. M. Vaquerizas, and J. Dopazo Highly specific and accurate selection of siRNAs for high-throughput functional assays Bioinformatics, April 15, 2005; 21(8): 1376 - 1382. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
V. Moulton Tracking down noncoding RNAs PNAS, February 15, 2005; 102(7): 2269 - 2270. [Full Text] [PDF]
|
|
|
|
 |
|
 E. A. Muller and D. J. Danner Tissue-specific Translation of Murine Branched-chain {alpha}-Ketoacid Dehydrogenase Kinase mRNA Is Dependent upon an Upstream Open Reading Frame in the 5'-Untranslated Region J. Biol. Chem., October 22, 2004; 279(43): 44645 - 44655. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Giegerich, B. Voss, and M. Rehmsmeier Abstract shapes of RNA Nucleic Acids Res., September 15, 2004; 32(16): 4843 - 4851. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. H. MATHEWS Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization RNA, August 1, 2004; 10(8): 1178 - 1190. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. Ding, C. Y. Chan, and C. E. Lawrence Sfold web server for statistical folding and rational design of nucleic acids Nucleic Acids Res., July 1, 2004; 32(suppl_2): W135 - W141. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. H. Mathews, M. D. Disney, J. L. Childs, S. J. Schroeder, M. Zuker, and D. H. Turner Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure PNAS, May 11, 2004; 101(19): 7287 - 7292. [Abstract] [Full Text] [PDF]
|
|