Finding a Common Motif of RNA Sequences Using Genetic Programming: The GeRNAMo System

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: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 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: David B. Fogel, Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, Piscataway, NJ, 1995
• 10: Gary B. Fogel, The Application of Evolutionary Computation to Selected Problems in Molecular Biology, Proceedings of the 6th International Conference on Evolutionary Programming VI, p.23-34, April 13-16, 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: Yongmei Ji , Xing Xu , Gary D. Stormo, A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences, Bioinformatics, v.20 n.10, p.1591-1602, July 2004 [doi>10.1093/bioinformatics/bth131]
• 27: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 28: John R. Koza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers, Norwell, MA, 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: David J. Montana, Strongly typed genetic programming, Evolutionary Computation, v.3 n.2, p.199-230, Summer 1995 [doi>10.1162/evco.1995.3.2.199]
• 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: Bruce A. Shapiro , Joseph Navetta, A massively parallel genetic algorithm for RNA secondary structure prediction, The Journal of Supercomputing, v.8 n.3, p.195-207, Nov. 1994 [doi>10.1007/BF01204728]
• 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: Sven Siebert , Rolf Backofen, MARNA: multiple alignment and consensus structure prediction of RNAs based on sequence structure comparisons, Bioinformatics, v.21 n.16, p.3352-3359, August 2005 [doi>10.1093/bioinformatics/bti550]
• 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: Kay C. Wiese , Andrew Hendriks, Comparison of P-RnaPredict and mfold---algorithms for RNA secondary structure prediction, Bioinformatics, v.22 n.8, p.934-942, April 2006 [doi>10.1093/bioinformatics/btl043]
• 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: Zizhen Yao , Zasha Weinberg , Walter L. Ruzzo, CMfinder---a covariance model based RNA motif finding algorithm, Bioinformatics, v.22 n.4, p.445-452, February 2006 [doi>10.1093/bioinformatics/btk008]
• 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

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching; Sequencing and scheduling

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Design