article

RnaPredict—An Evolutionary Algorithm for RNA Secondary Structure Prediction

Authors:

Alain A. Deschenes,

Andrew G. HendriksAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 5, Issue 1

Pages 25 - 41

https://doi.org/10.1109/tcbb.2007.1054

Published: 01 January 2008 Publication History

Abstract

This paper presents two in-depth studies on RnaPredict, an evolutionary algorithm for RNA secondary structure prediction. The first study is an analysis of the performance of two thermodynamic models, INN and INN-HB. The correlation between the free energy of predicted structures and the sensitivity is analyzed for 19 RNA sequences. Although some variance is shown, there is a clear trend between a lower free energy and an increase in true positive base pairs. With increasing sequence length, this correlation generally decreases. In the second experiment, the accuracy of the predicted structures for these 19 sequences are compared against the accuracy of the structures generated by the mfold dynamic programming algorithm (DPA) and also to known structures. RnaPredict is shown to outperform the minimum free energy structures produced by mfold and has comparable performance when compared to sub-optimal structures produced by mfold.

References

[1]

P.G. Higgs, "RNA Secondary Structure: Physical and Computational Aspects," Quarterly Rev. of Biophysics, vol. 33, pp. 199-253, 2000.

[2]

K.C. Wiese and E. Glen, "A Permutation Based Genetic Algorithm for RNA Secondary Structure Prediction," Soft Computing Systems, series Frontiers in Artificial Intelligence and Applications, A. Abraham, J.R. del Solar, and M. Koppen, eds., vol. 87, chapter 4, pp. 173-182, IOS Press, 2002.

[3]

K.C. Wiese and E. Glen, "A Permutation-Based Genetic Algorithm for the RNA Folding Problem: A Critical Look at Selection Strategies, Crossover Operators and Representation Issues," BioSystems, special issue on computational intelligence in bioinformatics, vol. 72, pp. 29-41, 2003.

[4]

K.C. Wiese, A. Deschenes, and E. Glen, "Permutation Based RNA Secondary Structure Prediction via a Genetic Algorithm," Proc. 2003 Congress Evolutionary Computation (CEC '03), pp. 335-342, Dec. 2003.

[5]

V. Juan and C. Wilson, "RNA Secondary Structure Prediction Based on Free Energy and Phylogenetic Analysis," J. Molecular Biology, vol. 289, pp. 935-947, 1999.

[6]

J. Ruan, G.D. Stormo, and W. Zhang, "An Iterated Loop Matching Approach to the Prediction of RNA Secondary Structures with Pseudoknots," Bioinformatics, vol. 20, no. 1, pp. 58-66, 2004.

Digital Library

[7]

B. Knudsen and J.J. Hein, "RNA Secondary Structure Prediction Using Stochastic Context-Free Grammars and Evolutionary History," Bioinformatics, vol. 15, no. 6, pp. 446-454, 1999.

[8]

T. Bäck, Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford Univ. Press, 1996.

Digital Library

[9]

B.A. Shapiro and J. Navetta, "A Massively-Parallel Genetic Algorithm for RNA Secondary Structure Prediction," J. Supercomputing , vol. 8, pp. 195-207, 1994.

Digital Library

[10]

B.A. Shapiro and J.C. Wu, "An Annealing Mutation Operator in the Genetic Algorithms for RNA Folding," Computer Applications in the Biosciences, vol. 12, no. 3, pp. 171-180, 1996.

[11]

F.H.D. van Batenburg, A.P. Gultyaev, and C.W.A. Pleij, "An APL-Programmed Genetic Algorithm for the Prediction of RNA Secondary Structure," J. Theoretical Biology, vol. 174, pp. 269-280, 1995.

[12]

A.P. Gultyaev, F.H.D. van Batenburg, and C.W.A. Pleij, "The Computer-Simulation of RNA Folding Pathways Using a Genetic Algorithm," J. Molecular Biology, vol. 250, pp. 37-51, 1995.

[13]

G. Benedetti and S. Morosetti, "A Genetic Algorithm to Search for Optimal and Suboptimal RNA Secondary Structures," Biophysical Chemistry, vol. 55, pp. 253-259, 1995.

[14]

B.A. Shapiro, D. Bengali, and W. Kasprzak, "Determination of RNA Folding Pathway Functional Intermediates Using a Massively Parallel Genetic Algorithm," Proc. ACM SIGKDD Workshop Data Mining in Bioinformatics (BIOKDD '01), p. 1, citeseer.ist.psu.edu/shapiro01determination.html, 2001.

[15]

B.A. Shapiro, D. Bengali, W. Kasprzak, and J.C. Wu, "RNA Folding Pathway Functional Intermediates: Their Prediction and Analysis," J. Molecular Biology, vol. 312, pp. 27-44, 2001.

[16]

J.H. Chen, S.Y. Le, and J.V. Maizel, "Prediction of Common Secondary Structures of RNAs: A Genetic Algorithm Approach," Nucleic Acids Research, vol. 28, pp. 991-999, 2000.

[17]

K.M. Currey and B.A. Shapiro, "Secondary Structure Computer Prediction of the Poliovirus 5' Non-Coding Region Is Improved by a Genetic Algorithm," Computer Applications in the Biosciences, vol. 13, no. 1, pp. 1-12, 1997.

[18]

S.J. Chen and K.A. Dill, "RNA Folding Energy Landscapes," Proc. Nat'l. Academy of Sciences, vol. 97, pp. 646-651, 2000.

[19]

I.I. Titov, D.G. Vorobiev, V.A. Ivanisenko, and N.A. Kolchanov, "A Fast Genetic Algorithm for RNA Secondary Structure Analysis," Russian Chemical Bull. vol. 51, no. 7, pp. 1135-1144, 2002.

[20]

G.B. Fogel, V.W. Porto, D.G. Weekes, D.B. Fogel, R.H. Griffey, J.A. McNeil, E. Lesnik, D.J. Ecker, and R. Sampath, "Discovery of RNA Structural Elements Using Evolutionary Computation," Nucleic Acids Research, vol. 30, no. 23, pp. 5310-5317, 2002.

[21]

K. Wiese and S.D. Goodwin, "Keep-Best Reproduction: A Local Family Competition Selection Strategy and the Environment It Flourishes In," Constraints, vol. 6, no. 4, pp. 399-422, 2001.

Digital Library

[22]

A. Deschenes and K.C. Wiese, "Using Stacking-Energies (INN and INN-HB) for Improving the Accuracy of RNA Secondary Structure Prediction with an Evolutionary Algorithm--A Comparison to Known Structures," Proc. 2004 IEEE Congress Evolutionary Computation, vol. 1, pp. 598-606, June 2004.

[23]

A. Deschenes, K.C. Wiese, and J. Poonian, "Comparison of Dynamic Programming and Evolutionary Algorithms for RNA Secondary Structure Prediction," Proc. 2004 IEEE Symp. Computational Intelligence in Bioinformatics and Computational Biology (CIBCB '04), pp. 214-222, Oct. 2004.

[24]

K.C. Wiese and A. Hendriks, "Comparison of P-RnaPredic and mfold--Algorithms for RNA Secondary Structure Prediction," Bioinformatics, vol. 22, no. 8, pp. 934-942, 2006.

Digital Library

[25]

D.H. Mathews, "Revolutions in RNA Secondary Structure Prediction," J. Molecular Biology, vol. 359, pp. 526-532, 2006.

[26]

Y. Ding and C.E. Lawrence, "A Statistical Sampling Algorithm for RNA Secondary Structure Prediction," Nucleic Acids Research, vol. 31, no. 24, pp. 7280-7301, 2003.

[27]

J. Reeder, M. Höchsmann, M. Rehmsmeier, B. Voss, and R. Giegerich, "Beyond Mfold: Recent Advances in RNA Bioinformatics," J. Biotechnology, vol. 124, pp. 41-55, 2006.

[28]

R. Nussinov, G. Pieczenik, J.R. Griggs, and D.J. Kleitman, "Algorithms for Loop Matchings," SIAM J. Applied Math., vol. 35, pp. 68-82, 1978.

Digital Library

[29]

M. Zuker, "Mfold Web Server for Nucleic Acid Folding and Hybridization Prediction," Nucleic Acids Research, vol. 31, no. 13, pp. 3406-3415, 2003.

[30]

M. Zuker and P. Stiegler, "Optimal Computer Folding of Large RNA Sequences Using Thermodynamics and Auxiliary Information," Nucleic Acids Research, vol. 9, pp. 133-148, 1981.

[31]

M. Zuker, "On Finding All Suboptimal Foldings of an RNA Molecule," Science, vol. 244, pp. 48-52, 1989.

[32]

M. Zuker, "Prediction of RNA Secondary Structure by Energy Minimization," Computer Analysis of Sequence Data, A.M. Griffin and H.G. Griffin, eds., pp. 267-294, Humana Press, July 1994.

[33]

M. Zuker, D.H. Mathews, and D.H. Turner, "Algorithms and Thermodynamics for RNA Secondary Structure Prediction: A Practical Guide," RNA Biochemistry and Biotechnology, series NATO ASI Series, J. Barciszewski and B. Clark, eds., Kluwer Academic Publishers, 1999.

[34]

M. Zuker, "Calculating Nucleic Acid Secondary Structure," Current Opinion in Structural Biology, vol. 10, pp. 303-310, 2000.

[35]

J.A. Jaeger, D.H. Turner, and M. Zuker, "Improved Predictions of Secondary Structures for RNA," Biochemistry, vol. 86, pp. 7706- 7710, Oct. 1989.

[36]

M. Zuker, J.A. Jaeger, and D.H. Turner, "A Comparison of Optimal and Suboptimal RNA Secondary Structures Predicted by Free Energy Minimization with Structures Determined by Phylogenetic Comparison," Nucleic Acids Research, vol. 19, no. 10, pp. 2707-2714, 1991.

[37]

D.H. Mathews, T.C. Andre, J. Kim, D.H. Turner, and M. Zuker, "An Updated Recursive Algorithm for RNA Secondary Structure Prediction with Improved Free Energy Parameters," Am. Chemical Soc., N.B. Leontis and J. SantaLucia Jr., eds., chapter 15, pp. 246- 257, Am. Chemical Soc., 1998.

[38]

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," Proc. Nat'l Academy of Sciences, vol. 101, pp. 7287-7292, 2004.

[39]

S.M. Freier, R. Kierzek, J.A. Jaeger, N. Sugimoto, M.H. Caruthers, T. Neilson, and D.H. Turner, "Improved Free-Energy Parameters for Predictions of RNA Duplex Stability," Proc. Nat'l Academy of Sciences, vol. 83, pp. 9373-9377, 1986.

[40]

M.J. Serra and D.H. Turner, "Predicting Thermodynamic Properties of RNA," Methods in Enzymology, vol. 259, pp. 242-261, 1995.

[41]

T. Xia, J. John SantaLucia, M.E. Burkard, R. Kierzek, S.J. Schroeder, X. Jiao, C. Cox, and D.H. Turner, "Thermodynamic Parameters for an Expanded Nearest-Neighbor Model for Formation of RNA Duplexes with Watson-Crick Base Pairs," Biochemistry, vol. 37, pp. 14719-14735, 1998.

[42]

P.N. Borer, B. Dengler, I.T. Jr., and O.C. Uhlenbeck, "Stability of Ribonucleic Acid Double-Stranded Helices," J. Molecular Biology, vol. 86, pp. 843-853, 1974.

[43]

S.M. Freier, B.J. Burger, D. Alkema, T. Neilson, and D.H. Turner, "Effects of 3' Dangling End Stacking on the Stability of GGCC and CCGG Double Helixes," Biochemistry, vol. 22, no. 26, pp. 6198- 6206, 1983.

[44]

R. Kierzek, M.H. Caruthers, C.E. Longfellow, D. Swinton, D.H. Turner, and S.M. Freier, "Polymer-Supported RNA Synthesis and Its Application to Test the Nearest Neighbor Model for Duplex Stability," Biochemistry, vol. 25, pp. 7840-7846, June 1986.

[45]

D.H. Mathews, J. Sabina, M. Zuker, and D.H. Turner, "Expanded Sequence Dependence of Thermodynamic Parameters Improves Prediction of RNA Secondary Structure," J. Molecular Biology, vol. 288, pp. 911-940, 1999.

[46]

N. Sugimoto, R. Kierzek, S.M. Freier, and D.H. Turner, "Energetics of Internal GU Mismatches in Ribooligonucleotide Helixes," Biochemistry, vol. 25, no. 19, pp. 5755-5759, 1986.

[47]

L. He, R. Kierzek, J. SantaLucia Jr., A.E. Walter, and D.H. Runer, "Nearest-Neighbor Parameters for GU Mismatches: GU/UG is Destabilizing in the Contexts CGUG/GUGC, UGUA/AUGU but Stabillizing in GGUC/CUGG," Biochemistry, vol. 30, pp. 11124- 11132, 1991.

[48]

M. Wu, J.A. McDowell, and D.H. Turner, "A Periodic Table of Symmetric Tandem Mismatches in RNA," Biochemistry, vol. 34, pp. 3204-3211, 1995.

[49]

T. Xia, J.A. McDowell, and D.H. Turner, "Thermodynamics of Nonsymmetric Tandem Mismatches Adjacent to GC Base Pairs in RNA," Biochemistry, vol. 36, pp. 12486-12497, 1997.

[50]

A. Deschenes, "A Genetic Algorithm for RNA Secondary Structure Prediction Using Stacking Energy Thermodynamic Models," master's thesis, Simon Fraser Univ., 2005.

[51]

I.M. Oliver, D.J. Smith, and J.R.C. Holland, "A Study of Permutation Crossover Operators on the Traveling Salesman Problem," Proc. Second Int'l Conf. Genetic Algorithms (ICGA '87), pp. 224-230, 1987.

Digital Library

[52]

G. Syswerda, "Schedule Optimization Using Genetic Algorithms," Handbook of Genetic Algorithms, L. Davis, ed., Van Nostrand Reinhold, 1991.

[53]

D.E. Goldberg and R. Lingle, Jr, "Alleles, Loci and the Travelling Salesman Problem," Proc. First Int'l Conf. Genetic Algorithms, J. Grefenstette, ed., pp. 154-159, 1985.

Digital Library

[54]

J.J. Cannone, S. Subramanian, M.N. Schnare, J.R. Collett, L.M. D'Souza, Y. Du, B. Feng, N. Lin, L.V. Madabusi, K.M. Müller, N. Pande, Z. Shang, N. Yu, and R.R. Gutell, "The Comparative RNA Web (CRW) Site: An Online Database of Comparative Sequence and Structure Information for Ribosomal, Intron and Other RNAs," BMC Bioinformatics, vol. 3, 2002.

[55]

N.A. Weiss, Elementary Statistics. Addison-Wesley, 1999.

[56]

P. Baldi, S. Brunak, Y. Chauvin, C.A.F. Andersen, and H. Nielsen, "Assessing the Accuracy of Prediction Algorithms for Classification: An Overview," Bioinformatics, vol. 16, no. 5, pp. 412-424, 2000.

[57]

K.C. Wiese, E. Glen, and A. Vasudevan, "jViz.Rna--A Java Tool for RNA Secondary Structure Visualization," IEEE Trans. Nano-Bioscience , vol. 4, no. 3, pp. 212-218, 2005.

Cited By

Yu ZLi FZhang K(2022)Evolution Strategy based Evolutionary Algorithm for RNA Secondary Structure PredictionProceedings of the 2022 6th International Conference on Machine Learning and Soft Computing10.1145/3523150.3523159(56-60)Online publication date: 15-Jan-2022
https://dl.acm.org/doi/10.1145/3523150.3523159
Lu WChen XZhang YWu HShen JZhou NDing Y(2021)Research on RNA Secondary Structure Prediction Based on MLPIntelligent Computing Theories and Application10.1007/978-3-030-84532-2_30(336-344)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84532-2_30
Kabir RIslam R(2019)Chemical reaction optimization for RNA structure predictionApplied Intelligence10.1007/s10489-018-1281-449:2(352-375)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10489-018-1281-4
Show More Cited By

Recommendations

Evolutionary rate variation and RNA secondary structure prediction

Predicting RNA secondary structure using evolutionary history can be carried out by using an alignment of related RNA sequences with conserved structure. Accurately determining evolutionary substitution rates for base pairs and single stranded ...
RNA Secondary Structure Prediction Based on Long Short-Term Memory Model
Intelligent Computing Theories and Application
Abstract
RNA secondary structure prediction is an important issue in structural bioinformatics. The difficulty of RNA secondary structure prediction with pseudoknot is increased due to complex structure of the pseudoknot. Traditional machine learning ...
Comparison of P-RnaPredict and mfold---algorithms for RNA secondary structure prediction

Motivation: Ribonucleic acid is vital in numerous stages of protein synthesis; it also possesses important functional and structural roles within the cell. The function of an RNA molecule within a particular organic system is principally determined ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 5, Issue 1

January 2008

159 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2008

Published in TCBB Volume 5, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
501
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yu ZLi FZhang K(2022)Evolution Strategy based Evolutionary Algorithm for RNA Secondary Structure PredictionProceedings of the 2022 6th International Conference on Machine Learning and Soft Computing10.1145/3523150.3523159(56-60)Online publication date: 15-Jan-2022
https://dl.acm.org/doi/10.1145/3523150.3523159
Lu WChen XZhang YWu HShen JZhou NDing Y(2021)Research on RNA Secondary Structure Prediction Based on MLPIntelligent Computing Theories and Application10.1007/978-3-030-84532-2_30(336-344)Online publication date: 12-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84532-2_30
Kabir RIslam R(2019)Chemical reaction optimization for RNA structure predictionApplied Intelligence10.1007/s10489-018-1281-449:2(352-375)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10489-018-1281-4
Kai ZYulin L(2018)A Novel Efficient Simulated Annealing Algorithm for the RNA Secondary Structure Predicting with PseudoknotsIntelligent Computing Theories and Application10.1007/978-3-319-95933-7_44(365-370)Online publication date: 15-Aug-2018
https://dl.acm.org/doi/10.1007/978-3-319-95933-7_44
Barrios Rolanía DFont JManrique D(2015)Bacterially inspired evolution of intelligent systems under constantly changing environmentsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-014-1319-419:4(1071-1083)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00500-014-1319-4
Subpaiboonkit SThammarongtham CCutler RChaijaruwanich J(2013)RNA secondary structure prediction using conditional random fields modelInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2013.0531957:2(118-134)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1504/IJDMB.2013.053195
Shabash BWiese KAlba E(2013)pEvoSATProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463479(861-868)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463479
Ray SPal S(2013)RNA Secondary Structure Prediction Using Soft ComputingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.15910:1(2-17)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1109/TCBB.2012.159
RolaníA DFont JManrique D(2013)Bacterially inspired evolving system with an application to time series predictionApplied Soft Computing10.1016/j.asoc.2012.10.01213:2(1136-1146)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.10.012
Wiese KHendriks A(2009)Impact of an enhanced thermodynamic model on RnaPredict, an evolutionary algorithm for RNA secondary structure predictionProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689983(2892-2899)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689983
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents