Bioinformatics Advance Access published online on April 21, 2006
Bioinformatics, doi:10.1093/bioinformatics/btl147
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 Genomics and Computational Biology Graduate Group, University of Pennsylvania School of Medicine
* To whom correspondence should be addressed.
Motivation: Identification of a transcription factor binding sites is an important aspect of the analysis of genetic regulation. Many programs have been developed for the de novo discovery of a binding motif (collection of binding sites). Recently, a scoring function formulation was derived that allows for the comparison of discovered motifs from different programs (Jensen et al., 2004). A simple program, BioOptimizer, was proposed in (Jensen and Liu, 2004) that improved discovered motifs by optimizing a scoring function. However, BioOptimizer is a very simple algorithm that can only make local improvements upon an already discovered motif and so BioOptimizer can only be used in conjunction with other motif-finding software. Results: We introduce software, GAME, which utilizes a genetic algorithm to find optimal motifs in DNA sequences. GAME evolves motifs with high fitness from a population of randomly-generated starting motifs, which eliminates the reliance on additional motif-finding programs. In addition to using standard genetic operations, GAME also incorporates two additional operators that are specific to the motif discovery problem. We demonstrate the superior performance of GAME compared to MEME, BioProspector and BioOptimizer in simulation studies as well as several real data applications where we use an extended version of the GAME algorithm that allows the motif width to be unknown. Availability: http://mail.med.upenn.edu/~zhiwei/GAME/.
Received January 10, 2006
Revised March 24, 2006
Accepted April 12, 2006
Article
GAME: detecting cis-regulatory elements using a genetic algorithm
Zhi Wei 1 *
and
Shane T. Jensen 2
2 Department of Statistics, The Wharton School, University of Pennsylvania
Zhi Wei, E-mail: zhiwei{at}mail.med.upenn.edu
Abstract
Associate Editor: Martin Bishop
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Defrance and J. van Helden info-gibbs: a motif discovery algorithm that directly optimizes information content during sampling Bioinformatics, October 15, 2009; 25(20): 2715 - 2722. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. A. Sharov and M. S.H. Ko Exhaustive Search for Over-represented DNA Sequence Motifs with CisFinder DNA Res, October 1, 2009; 16(5): 261 - 273. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 G. B. Fogel, V. W. Porto, G. Varga, E. R. Dow, A. M. Craven, D. M. Powers, H. B. Harlow, E. W. Su, J. E. Onyia, and C. Su Evolutionary computation for discovery of composite transcription factor binding sites Nucleic Acids Res., December 1, 2008; 36(21): e142 - e142. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T.-M. Chan, K.-S. Leung, and K.-H. Lee TFBS identification based on genetic algorithm with combined representations and adaptive post-processing Bioinformatics, February 1, 2008; 24(3): 341 - 349. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Wijaya, K. Rajaraman, S.-M. Yiu, and W.-K. Sung Detection of generic spaced motifs using submotif pattern mining Bioinformatics, June 15, 2007; 23(12): 1476 - 1485. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Li, Y. Liang, and R. L. Bass GAPWM: a genetic algorithm method for optimizing a position weight matrix Bioinformatics, May 15, 2007; 23(10): 1188 - 1194. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. J. Donaldson and B. Gottgens CoMoDis: composite motif discovery in mammalian genomes Nucleic Acids Res., January 12, 2007; 35(1): e1 - e1. [Abstract] [Full Text] [PDF]
|
|