Modeling evolutionary fitness for DNA motif discovery

ABSTRACT

The motif discovery problem consists of finding over-represented patterns in a collection of sequences. Its difficulty stems partly from the large number of possibilities to define both the motif space to be searched and the notion of over-representation. Since the size of the search space is generally exponential in the motif length, many heuristic methods, including evolutionary algorithms, have been developed. However, comparatively little attention has been devoted to the adequate evaluation of motif quality, especially when comparing motifs of different lengths. We propose an evolution strategy to solve the motif discovery problem based on a new fitness function that simultaneously takes into account (1) the number of motif occurrences, (2) the motif length, and (3) its information content. Experimental results show that the proposed method succeeds in uncovering the correct motif positions and length with high accuracy.

REFERENCES

• 1: T. L. Bailey and C. Elkan. Fitting a mixture model by expectation maximization to discover motifs in biopolymer. In ISMB' 94, pages 28--36, 1994.
• 2: Hans-Georg Beyer , Hans-Paul Schwefel, Evolution strategies –A comprehensive introduction, Natural Computing: an international journal, v.1 n.1, p.3-52, May 2002 [doi>10.1023/A:1015059928466]
• 3: Tak-Ming Chan , Kwong-Sak Leung , Kin-Hong Lee, TFBS identification based on genetic algorithm with combined representations and adaptive post-processing, Bioinformatics, v.24 n.3, p.341-349, February 2008 [doi>10.1093/bioinformatics/btm606]
• 4: Clare Bates Congdon , Joseph C. Aman , Gerardo M. Nava , H. Rex Gaskins , Carolyn J. Mattingly, An Evaluation of Information Content as a Metric for the Inference of Putative Conserved Noncoding Regions in DNA Sequences Using a Genetic Algorithms Approach, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.1, p.1-14, January 2008 [doi>10.1109/TCBB.2007.1059]
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: François Fauteux , Mathieu Blanchette , Martina V. Strömvik, Seeder, Bioinformatics, v.24 n.20, p.2303-2307, October 2008 [doi>10.1093/bioinformatics/btn444]
• 7: G. B. Fogel, D. G. Weekes, G. Varga, E. R. Dow, H. B. Harlow, J. E. Onyia, and C. Su. Discovery of sequence motifs related to coexpression of genes using evolutionary computation. Nucleic Acids Res, 32(13): 3826--3835, 2004.
• 8: Eugene Fratkin , Brian T. Naughton , Douglas L. Brutlag , Serafim Batzoglou, MotifCut, Bioinformatics, v.22 n.14, p.e150-e157, July 2006 [doi>10.1093/bioinformatics/btl243]
• 9: S. T. Jensen, X. S. Liu, Q. Zhou, and J. S. Liu. Computational discovery of gene regulatory binding motifs: a Bayesian perspective. Statistical Science, 19(1):188---204, 2004.
• 10: J. Kalinowski et al. The complete Corynebacterium glutamicum ATCC 13032 genome sequence and its impact on the production of l-aspartate-derived amino acids and vitamins. Journal of Biotechnology, 104(1-3):5--25, 2003.
• 11: M. Kaya. Motif discovery using multi-objective genetic algorithm in biosequences. Advances in Intelligent Data Analysis VII, 4723:320--331, 2007.
• 12: T. A. Kohl, J. Baumbach, B. Jungwirth, A. Pühler, and A. Tauch. The GlxR regulon of the amino acid producer Corynebacterium glutamicum: In silico and in vitro detection of DNA binding sites of a global transcription regulator. Journal of Biotechnology, 135(4): 340--350, 2008.
• 13: Michael Lones , Andy Tyrrell, Regulatory Motif Discovery Using a Population Clustering Evolutionary Algorithm, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.3, p.403-414, July 2007 [doi>10.1109/tcbb.2007.1044]
• 14: Michael A. Lones , Andy M. Tyrrell, The evolutionary computation approach to motif discovery in biological sequences, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102258]
• 15: Topon Kumar Paul , Hitoshi Iba, Identification of weak motifs in multiple biological sequences using genetic algorithm, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144044]
• 16: G. Pavesi, P. Mereghetti, G. Mauri, and G. Pesole. Weeder Web: discovery of transcription factor binding sites in a set of sequences from co-regulated genes. Nucleic Acids Res, 32(Web Server Issue):W199--W203, 2004.
• 17: S. Rahmann, T. Müller, and M. Vingron. On the power of profiles for transcription factor binding site detection. Statistical Applications in Genetics and Molecular Biology, 2(1):Article 7, 2003.
• 18: K. Robinson, A. McGuire, and G. Church. A comprehensive library of DNA-binding site matrices for 55 proteins applied to the complete Escherichia coli K 12 genome. Journal of Molecular Biology, 284:241--254, 1998.
• 19: A. Sandelin, W. Alkema, P. G. Engström, W. W. Wasserman, and B. Lenhard. JASPAR: an open access database for eukaryotic transcription factor binding profiles. Nucleic Acids Res, 32(1):D91--D94, 2004.
• 20: G. Sandve, O. Abul, V. Walseng, and F. Drabløs. Improved benchmarks for computational motif discovery. BMC Bioinformatics, 8(1):193, 2007.
• 21: G. Sandve and F. Drabløs. A survey of motif discovery methods in an integrated framework. Biology Direct, 1:Article 11, 2006.
• 22: T. Schneider and R. Stephens. Sequence logos: a new way to display consensus sequences. Nucleic Acids Res, 18:6097--6100, 1990.
• 23: T. Schneider, G. Stromo, L. Gold, and A. Ehrenfeucht. Information content of binding sites on nucleotide sequences. Journal of Molecular Biology, 188(3):415--431, 1986.
• 24: S. Sinha and M. Tompa. YMF: a program for discovery of novel transcription factor binding sites by statistical overrepresentation. Nucleic Acids Res, 31(13):3586--3588, 2003.
• 25: G. D. Stormo. DNA binding sites: representation and discovery. Bioinformatics, 16:16--23, 2000.
• 26: M. Tompa et al. Assessing computational tools for the discovery of transcription factor binding sites. Nature Biotechnology, 23:137--144, 2005.
• 27: Zhi Wei , Shane T. Jensen, GAME: detecting cis-regulatory elements using a genetic algorithm, Bioinformatics, v.22 n.13, p.1577-1584, July 2006 [doi>10.1093/bioinformatics/btl147]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

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

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
computational biology, dna, ea, es, evolution strategies, evolutionary algorithms, local search, motif discovery, transcription factor