Cited By
View all- Font JManrique DRíos J(2010)Evolutionary construction and adaptation of intelligent systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.04.07037:12(7711-7720)Online publication date: 1-Dec-2010
Finding a Common Motif of RNA Sequences Using Genetic Programming: The GeRNAMo System
Pages 596 - 610
Abstract
We focus on finding a consensus motif of a set of homologous or functionally related RNA molecules. Recent approaches to this problem have been limited to simple motifs, require sequence alignment, and make prior assumptions concerning the data set. We use genetic programming to predict RNA consensus motifs based solely on the data set. Our system -- dubbed GeRNAMo (Genetic programming of RNA Motifs) -- predicts the most common motifs without sequence alignment and is capable of dealing with any motif size. Our program only requires the maximum number of stems in the motif, and if prior knowledge is available the user can specify other attributes of the motif (e.g., the range of the motif's minimum and maximum sizes), thereby increasing both sensitivity and speed. We describe several experiments using either ferritin iron response element (IRE); signal recognition particle (SRP); or microRNA sequences, showing that the most common motif is found repeatedly, and that our system offers substantial advantages over previous methods.
References
[1]
W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone, Genetic Programming – An Introduction: On the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann, 1997.
[2]
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.
[3]
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.
[4]
R. Durbin, S.R. Eddy, A. Krogh, and G. Mitchison, Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge Univ. Press, 1998.
[5]
S. Eddy and R. Durbin, “RNA Sequence Analysis Using Covariance Models,” Nucleic Acids Research, vol. 22, pp. 2079-2088, 1994.
[6]
S.R. Eddy, “Computational Genomics of Noncoding RNA Genes,” Cell, vol. 13, pp. 137-140, 2002.
[7]
S.R. Eddy, “How Do RNA Folding Algorithms Work?” Nature Biotechnology, vol. 22, pp. 1457-14588, 2004.
[8]
I. Titov et al., “A Fast Genetic Algorithm for RNA Secondary Structure Analysis,” Russian Chemistry Bull., vol. 51, pp. 1135-1144, 2002.
[9]
D.B. Fogel, Evolutionary Computation: Toward a New Philosophy of Machine Intelligence. IEEE Press, 2000.
[10]
G.B. Fogel, “The Application of Evolutionary Computation to Selected Problems in Molecular Biology,” Proc. Sixth Int'l Conf. Evolutionary Programming, pp. 23-33, 1997.
[11]
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.
[12]
G.B. Fogel, D.G. Weekes, R. Sampath, and D.J. Ecker, “Parameter Optimization of an Evolutionary Algorithm for RNA Structure Discovery,” Proc. 2004 IEEE Congress Evolutionary Computation, pp.607-613, June 2004.
[13]
Z. Gdaniec, H. Sierzputowska-Gracz, and E.C. Theil, “Iron Regulatory Element and Internal Loop/Bulge Structure for Ferritin mRNA Studied by Cobalt(iii) Hexamine Binding, Molecular Modeling and nmr Spectroscopy,” Biochemistry, vol. 37, pp.1505-1512, 1998.
[14]
J. Gorodkin, L.J. Heyer, and G.D. Stormo, “Finding the Most Significant Common Sequence and Structure Motifs in a Set of RNA Sequences,” Nucleic Acids Research, vol. 25, pp. 3724-3732, 1997.
[15]
J. Gorodkin, S.L. Stricklin, and G.D. Stormo, “Discovering Common Stem-Loop Motifs in Unaligned RNA Sequences,” Nucleic Acids Research, vol. 29, pp. 2135-2144, 2001.
[16]
S. Griffiths-Jones, “The microRNA Registry,” Nucleic Acids Research, vol. 32, pp. D109-D111, 2004.
[17]
S. Griffiths-Jones, R.J. Grocock, S. can Dongen, A. Bateman, and A.J. Enright, “miRBase: microRNA Sequences, Targets and Gene Nomenclature,” Nucleic Acids Research, vol. 34, pp. D140-D144, 2006.
[18]
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.
[19]
A.P. Gultyaev, F.H.D van Batenburg, and C.W.A. Pleij, “Dynamic Competition between Alternative Structures in Viroid RNAs Simulated by an RNA Folding Algorithm,” J. Molecular Biology, vol. 276, pp. 43-55, 1998.
[20]
R.R. Gutell, J.C. Lee, and J.J. Cannone, “The Accuracy of Ribosomal RNA Comparative Structure Models,” Current Opinion in Structural Biology, vol. 12, pp. 301-310, 2002.
[21]
I.L. Hofacker, “Vienna RNA Secondary Structure Server,” Nucleic Acids Research, vol. 31, no. 13, pp. 3429-3431, 2004.
[22]
I.L. Hofacker, M. Fekete, C. Flamm, M.A. Huynen, S. Rauscher, P.E. Stolorz, and P.F. Stadler, “Automatic Detection of Conserved RNA Structure Elements in Complete RNA Virus Genomes,” Nucleic Acids Research, vol. 26, pp. 3825-3836, 1998.
[23]
I.L. Hofacker, W. Fontana, P.F. Stadler, L.S. Bonhoeffer, M. Tacker, and P. Schuster, “Fast Folding and Comparison of RNA Secondary Structures,” Monatshefte Fur Chemie, vol. 125, pp. 167-188, 1994.
[24]
Y.J. Hu, “Prediction of Consensus Structural Motifs in a Family of Coregulated RNA Sequences,” Nucleic Acids Research, vol. 30, no. 17, pp. 3886-3893, 2002.
[25]
Y.J. Hu, “GPRM: A Genetic Programming Approach to Finding Common RNA Secondary Structure Elements,” Nucleic Acids Research, vol. 31, no. 13, pp. 3446-3449, 2003.
[26]
Y. Ji, X. Xu, and G.D. Stormo, “A Graph Theoretical Approach for Predicting Common RNA Secondary Structure Motifs Including Pseudoknots in Unaligned Sequences,” Bioinformatics, vol. 20, pp.1591-1602, 2004.
[27]
J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.
[28]
J.R. Koza, M.A. Keane, M.J. Streeter, W. Mydlowec, J. Yu, and G. Lanza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic, 2003.
[29]
E.A. Lesnik, G.B. Fogel, D. Weekes, T.J. Henderson, H.B. Levene, R. Sampath, and D.J. Ecker, “Identification of Conserved Regulatory RNA Structures in Prokaryotic Metabolic Pathway Genes,” Biosystems, vol. 80, pp. 145-154, 2005.
[30]
S. Luke, ECJ: A Java-Based Evolutionary Computation and Genetic Programming Research System, http://www.cs.umd.edu/projects/plus/ec/ecj/, 2007.
[31]
T. Macke, D. Ecker, R. Gutell, D. Gautheret, D.A. Case, and R. Sampath, “RNAMotif—A New RNA Secondary Structure Definition and Discovery Algorithm,” Nucleic Acids Research, vol. 29, pp.4724-4735, 2001.
[32]
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.
[33]
D.J. Montana, “Strongly Typed Genetic Programming,” Evolutionary Computation, vol. 3, no. 2, pp. 199-230, 1995.
[34]
R. Nussinov and A. Jacobson, “Fast Algorithm for Predicting the Secondary Structure of Single Stranded RNA,” Proc. Nat'l Academy of Sciences USA, vol. 77, no. 11, pp. 6309-6313, 1980.
[35]
G. Pavesi, G. Mauri, M. Stefani, and G. Pesole, “RNAProfile: An Algorithm for Finding Conserved Secondary Structure Motifs in Unaligned RNA Sequences,” Nucleic Acids Research, vol. 32, no. 10, pp. 3258-3269, 2004.
[36]
Sanger MIRbase, http://microrna.sanger.ac.uk/sequences/index.shtml, 2007.
[37]
D. Sankoff, “Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems,” SIAM J. Applied Math., vol. 45, pp. 810-825, 1985.
[38]
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.
[39]
B.A. Shapiro and J. Navetta, “A Massively Parallel Genetic Algorithm for RNA Secondary Structure Prediction,” J. Supercomputing, vol. 8, pp. 195-207, 1994.
[40]
B.A. Shapiro, J.C. Wu, D. Bengali, and M.J. Potts, “The Massively Parallel Genetic Algorithm for RNA Folding: MIMD Implementation and Population Variation,” Bioinformatics, vol. 17, pp. 137-148, 2001.
[41]
S. Siebert and R. Backofen, “Marna: Multiple Alignment and Consensus Structure Prediction of RNAs Based on Sequence Structure Comparisons,” Bioinformatics, vol. 21, pp. 3352-3359, 2005.
[42]
M. Sipper, Machine Nature: The Coming Age of Bio-Inspired Computing. McGraw-Hill, 2002.
[43]
E.C. Theil, “The Iron Responsive Element (IRE) Family of mRNA Regulators. Regulation of Iron Transport and Uptake Compared in Animals, Plants and Microorganisms,” Metal Ions in Biological Systems, vol. 35, pp. 403-434, 1998.
[44]
K.C. Wiese and A. Hendriks, “Comparison of p-rnapredict and mfold Algorithms for RNA Secondary Structure Prediction,” Bioinformatics, vol. 22, pp. 934-942, 2006.
[45]
C. Witwer, S. Rauscher, I.L. Hofacker, and P.F. Stadler, “Conserved RNA Secondary Structures in Picornaviridae Genomes,” Nucleic Acids Research, vol. 29, pp. 5079-5089, 2001.
[46]
S. Wuchty, W. Fontana, I.L. Hofacker, and P. Schuster, “Complete Suboptimal Folding of RNA and the Stability of Secondary Structures,” Biopolymers, vol. 49, pp. 145-165, 1999.
[47]
Z. Yao, Z. Weinberg, and W.L. Ruzzo, “Cmfinder a Covariance Model Based RNA Motif Finding Algorithm,” Bioinformatics, vol. 22, pp. 445-452, 2006.
[48]
M. Zuker, “On Finding All Suboptimal Foldings of an RNA Molecule,” Science, vol. 244, pp. 48-52, 1989.
[49]
M. Zuker, “Mfold Web Server for Nucleic Acid Folding and Hybridization Prediction,” Nucleic Acids Research, vol. 31, no. 13, pp. 3406-3415, 2003.
Index Terms
- Finding a Common Motif of RNA Sequences Using Genetic Programming: The GeRNAMo System
Recommendations
CMfinder---a covariance model based RNA motif finding algorithm
Motivation: The recent discoveries of large numbers of non-coding RNAs and computational advances in genome-scale RNA search create a need for tools for automatic, high quality identification and characterization of conserved RNA motifs that can be ...
A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences
Motivation: RNA structure motifs contained in mRNAs have been found to play important roles in regulating gene expression. However, identification of novel RNA regulatory motifs using computational methods has not been widely explored. Effective ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 October 2007
Published in TCBB Volume 4, Issue 4
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 750Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
Cited By
View all- Font JManrique DRíos J(2010)Evolutionary construction and adaptation of intelligent systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2010.04.07037:12(7711-7720)Online publication date: 1-Dec-2010
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in