A novel method for MicroRNA secondary structure prediction using a bottom-up algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A novel method for MicroRNA secondary structure prediction using a bottom-up algorithm

Full text

Pdf (167 KB)

Source

ACM Southeast Regional Conference archive
Proceedings of the 47th Annual Southeast Regional Conference table of contents

Clemson, South Carolina

SESSION: Information analysis table of contents

Article No. 46

Year of Publication: 2009

ISBN:978-1-60558-421-8

Authors

Dianwei Han	University of Kentucky, Lexington, KY
Guiliang Tang	University of Kentucky, Lexington, KY
Jun Zhang	University of Kentucky, Lexington, KY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 40, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1566445.1566508 What is a DOI?

ABSTRACT

MicroRNAs (miRNAs) are newly discovered endogenous small non-coding RNAs (21-25nt) that are thought to regulate expression of target genes by direct interaction with mRNAs. MicroRNAs have been identified through both experimental and computational methods, and microRNA secondary structure prediction is important and essential. Generally, there are two classes of methods to predict the secondary structure of RNAs. Thermodynamics-based methods have been the dominant strategy for single-stranded RNA secondary structure prediction for many years. Recently, probabilistic-based methods have emerged to replace the free energy minimization methods for modeling RNA structures. However, the accuracies of the currently best available probabilistic-based models have yet to match those of the best thermodynamics-based methods. So this situation motivates us to develop a new prediction algorithm which will focus on microRNA structure prediction with high accuracy. A new model, nucleotide cyclic motifs (NCM), was recently proposed by Major et al. to predict RNA secondary structure. We propose and implement a novel model based on a Modified NCM (MNCM) model with a physics-based scoring strategy to tackle the problem of microRNA folding. By making use of a global optimal algorithm based on the bottom-up local optimal solutions, we implement MicroRNAfold. Our experimental results show that MicroRNAfold outperforms the current leading prediction tools.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephan H Bernhart, Hakim Tafer, Ulrike Mückstein, Christoph Flamm, Peter F Stadler, Ivo L Hofacker. Partition function and base pairing probabilities of RNA heterodimers. Algorithms for Molecular Biology, 1:3(2006)
	2	Frederick R. Blattner. An efficient method for scoring base pair interactions. Nucleic Acids Research, 12:1201--1217 (1984)
	3	Chuong B. Do , Daniel A. Woods , Serafim Batzoglou, CONTRAfold, Bioinformatics, v.22 n.14, p.e90-e98, July 2006 [doi>10.1093/bioinformatics/btl246]
	4	Sean R. Eddy, Richard Durbin. RNA sequence analysis using covariance models. Nucleic Acids Research, 22(11):2079--2088 (1994)
	5	Thomas R. Fink, Donald M. Crothers. Free energy of imperfect nucleic acid helices. I. The bulge defect. J. Mol. Biol., 66:1--12 (1972)
	6	Sam Griffiths-Jones, Harpreet Kaur Saini, Stijn van Dongen, Anton J. Enright. miRBase: tools for microRNA genomics. Nucleic Acids Research, 36: D154-D158 (2008)
	7	Sam Griffiths-Jones, Russell J. Grocock, Stijn van Dongen, Alex Bateman, Anton J. Enright. miRBase: microRNA sequences, targets and gene nomenclature. Nucleic Acids Research, 34: D140-D144 (2006)
	8	Sam Griffiths-Jones. The microRNA registry. Nucleic Acids Research, 32: D109-D111 (2004)
	9	Duncan R. Groebe, Olke C. Uhlenbeck. Thermal stability of RNA hairpins containing a four-membered loop and a bulge nucleotide. Biochemistry, 28:742--747 (1989)
	10	Dianwei Han , Shuting Xu , Jun Zhang, An online condition number query system, Proceedings of the 46th Annual Southeast Regional Conference on XX, March 28-29, 2008, Auburn, Alabama [doi>10.1145/1593105.1593175]
	11	Dianwei Han , Jun Zhang, A Comparison of Two Algorithms for Predicting the Condition Number, Proceedings of the Sixth International Conference on Machine Learning and Applications, p.223-228, December 13-15, 2007 [doi>10.1109/ICMLA.2007.3]
	12	Ivo L. Hofacker, Walter Fontana, Peter F. Stadler, L. Sebastian Bonhoeffer, Manfred Tacker, Peter Schuster. Fast folding and comparison of RNA secondary structures (the Vienna RNA package). Monatsh Chem., 125:167--188 (1994)
	13	Carl E. Longfellow, Ryszard Kierzek, Douglas H. Turner. Thermodynamic and spectroscopic study of bulge loops in oligoribonucleotides. Biochemistry, 29:278--285 (1990)
	14	David H. Mathews, D. H. Turner. Prediction of RNA secondary structure by free energy minimization. Current Opinion in Structural Biology, 16:270--278 (2006)
	15	David H. Mathews, Michael Zuker. Predictive Methods Using RNA Sequences. Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, 3rd ed., edited by Andreas D. Baxevanis and B. F. Francis Ouellette, John wiley&sons, page 144--167 (2005)
	16	David H. Mathews, Jeffrey Sabina, Michael Zuker. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol., 288:911--940 (1999)
	17	Brian W. Matthews. Comparison of the predicted and observed secondary structure of T4 phage lysozyme. Biochimica Biophysica Acta, 405:442--451 (1975)
	18	John S. McCaskill. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers, 29:1105--1119 (1990)
	19	Marc Parisien, Francois Major. The MC-Fold and MC-Sym pipeline infers RNA structure from sequence data. Nature, 452:51--55 (2008)
	20	http://pseudoviewer.inha.ac.kr/
	21	Yasubumi Sakakibara, Michael Brown, Richard Hughey et al. Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research, 22(23):5112--5120 (1994)
	22	Guiliang Tang, Gad Galili, Xun Zhuang. RNAi and microRNA: Breakthrough technologies for the improvement of plant nutritional value and metabolic engineering. Metabolomics, 3:357--369 (2007)
	23	Michael S. Waterman, Thomas H. Byers. A dynamic programming algorithm to find all solutions in the neighborhood of the optimum. Mathematical Biosciences, 77:179--188 (1985)
	24	James D. Watson, Nancy H. Hopkins, Jeffrey W. Roberts, Joan Argetsinger Steitz, Alan M. Weiner. Molecular Biology of the Gene, Benjamin Cummings Inc, Menlo Park, CA, page 1--283 (1987)
	25	Tianbing Xia, David H. Mathews, Douglas H. Turner. Thermodynamics of RNA secondary structure formation. In Prebiotic Chemistry, Molecular Fossils, Nucleotides, and RNA, edited by D. G. So"ll, S. Nishimura, and P. B. Moore, Elsevier, page 21--48 (1999)
	26	Tianbing Xia, J. A. McDowell, Douglas H. Turner. Thermodynamics of nonsymmetric tandem mismatches adjacent to G-C base pairs in RNA. Biochemistry, 36:12486--12487 (1997)
	27	Michael Zuker. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Research, 31(13):3406--3415 (2003)
	28	Michael Zuker, Patrick Stiegler. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research, 9:133--148 (1981)