Bioinformatics Advance Access originally published online on April 21, 2006
Bioinformatics 2006 22(13):1577-1584; doi:10.1093/bioinformatics/btl147
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GAME: detecting cis-regulatory elements using a genetic algorithm
1 Genomics and Computational Biology Graduate Group, University of Pennsylvania School of Medicine Philadelphia, PA 19104, USA
2 Department of Statistics, The Wharton School, University of Pennsylvania Philadelphia, PA 19104, USA
*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 [S.T. Jensen, X.S. Liu, Q. Zhou and J.S. Liu (2004) Stat. Sci., 19, 188–204.] A simple program, BioOptimizer, was proposed in [S.T. Jensen and J.S. Liu (2004) Bioinformatics, 20, 1557–1564.] 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 eliminate 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 with 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/
Contact: zhiwei{at}mail.med.upenn.edu
Supplementary information: Supplementary data are available at Bioinformatics online.
Received on January 10, 2006; revised on March 24, 2006; accepted on April 12, 2006
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]
|
|