{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:45:30Z","timestamp":1762505130847},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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\u2013204.] A simple program, BioOptimizer, was proposed in [S.T. Jensen and J.S. Liu (2004) Bioinformatics, 20, 1557\u20131564.] 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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability: \u00a0<\/jats:p>\n               <jats:p>Contact: \u00a0zhiwei@mail.med.upenn.edu<\/jats:p>\n               <jats:p>Supplementary information: Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl147","type":"journal-article","created":{"date-parts":[[2006,4,22]],"date-time":"2006-04-22T00:27:33Z","timestamp":1145665653000},"page":"1577-1584","source":"Crossref","is-referenced-by-count":76,"title":["GAME: detecting <i>cis<\/i>-regulatory elements using a genetic algorithm"],"prefix":"10.1093","volume":"22","author":[{"given":"Zhi","family":"Wei","sequence":"first","affiliation":[{"name":"Genomics and Computational Biology Graduate Group, University of Pennsylvania School of Medicine 1 \u00a0 1 \u00a0 \u00a0 Philadelphia, PA 19104, USA"}]},{"given":"Shane T.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Department of Statistics, The Wharton School, University of Pennsylvania 2 \u00a0 2 \u00a0 \u00a0 Philadelphia, PA 19104, USA"}]}],"member":"286","published-online":{"date-parts":[[2006,4,21]]},"reference":[{"key":"2023012408323555200_b1","first-page":"28","article-title":"Fitting a mixture model by expectation maximization to discover motifs in biopolymers","author":"Bailey","year":"1994"},{"key":"2023012408323555200_b2","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1073\/pnas.231608898","article-title":"Exploiting transcription factor binding site clustering to identify cis-regulatory modules involved in pattern formation in the Drosophila genome","volume":"99","author":"Berman","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408323555200_b3","doi-asserted-by":"crossref","first-page":"D63","DOI":"10.1093\/nar\/gkj116","article-title":"ABS: a database of annotated regulatory binding sites from orthologous promoters","volume":"34","author":"Blanco","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012408323555200_b4","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1101\/gr.849004","article-title":"WebLogo: A sequence logo generator","volume":"14","author":"Crooks","year":"2004","journal-title":"Genome Res."},{"key":"2023012408323555200_b5","article-title":"An analysis of the behavior of a class of genetic adaptive systems","author":"De Jong","year":"1975"},{"key":"2023012408323555200_b6","first-page":"124","article-title":"Using genetic algorithms to solve NP-complete problems","author":"De Jong","year":"1989"},{"key":"2023012408323555200_b7","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1093\/nar\/gkh169","article-title":"Finding functional sequence elements by multiple local alignment","volume":"32","author":"Frith","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012408323555200_b8","volume-title":"Genetic Algorithms in Search, Optimisation and Machine Learning","author":"Goldberg","year":"1989"},{"key":"2023012408323555200_b9","first-page":"24","article-title":"Do not worry, be messy","author":"Goldberg","year":"1991"},{"key":"2023012408323555200_b10","doi-asserted-by":"crossref","first-page":"7079","DOI":"10.1073\/pnas.0408743102","article-title":"De novo cis-regulatory module elicitation for eukaryotic genomes","volume":"102","author":"Gupta","year":"2005","journal-title":"PNAS"},{"key":"2023012408323555200_b11","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1093\/bioinformatics\/15.7.563","article-title":"Identifying DNA and protein patterns with statistically significant alignments of multiple sequences","volume":"15","author":"Hertz","year":"1999","journal-title":"Bioinformatics"},{"key":"2023012408323555200_b12","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1214\/088342304000000107","article-title":"Computational discovery of gene regulatory binding motifs: a Bayesian perspective","volume":"19","author":"Jensen","year":"2004","journal-title":"Stat. Sci."},{"key":"2023012408323555200_b13","doi-asserted-by":"crossref","first-page":"1557","DOI":"10.1093\/bioinformatics\/bth127","article-title":"BioOptimizer: a Bayesian scoring function approach to motif discovery","volume":"20","author":"Jensen","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012408323555200_b14","doi-asserted-by":"crossref","first-page":"3832","DOI":"10.1093\/bioinformatics\/bti628","article-title":"Combining phylogenetic motif discovery and motif clustering to predict co-regulated genes","volume":"21","author":"Jensen","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012408323555200_b15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1006\/jmbi.2001.4650","article-title":"Computer-assisted identification of cell cycle-related genes: new targets for E2F transcription factors","volume":"309","author":"Kel","year":"2001","journal-title":"J. Mol. Biol."},{"key":"2023012408323555200_b16","doi-asserted-by":"crossref","first-page":"2905","DOI":"10.1093\/nar\/29.14.2905","article-title":"Estrogen receptor interaction with estrogen response elements","volume":"29","author":"Klinge","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023012408323555200_b17","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1214\/aoms\/1177729694","article-title":"On information and sufficiency","volume":"22","author":"Kullback","year":"1951","journal-title":"Ann. Math. Stat."},{"key":"2023012408323555200_b18","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/prot.340070105","article-title":"An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences","volume":"7","author":"Lawrence","year":"1990","journal-title":"Proteins"},{"key":"2023012408323555200_b19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1038\/nature01763","article-title":"Transcription regulation and animal diversity","volume":"424","author":"Levine","year":"2003","journal-title":"Nature"},{"key":"2023012408323555200_b20","doi-asserted-by":"crossref","DOI":"10.1109\/BIBE.2004.1317378","article-title":"FMGA: Finding motifs by Genetic algorithm","author":"Liu","year":"2004","journal-title":"Fourth IEEE Symposium on Bioinformatics and Bioengineering (BIBE\u201904)"},{"key":"2023012408323555200_b21","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1080\/01621459.1994.10476829","article-title":"The collapsed Gibbs sampler in Bayesian computations with applications to a gene regulation problem","volume":"94","author":"Liu","year":"1994","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012408323555200_b22","doi-asserted-by":"crossref","first-page":"1156","DOI":"10.1080\/01621459.1995.10476622","article-title":"Bayesian models for multiple local sequence alignment and Gibbs sampling strategies","volume":"90","author":"Liu","year":"1995","journal-title":"J. Am. Stat. Assoc."},{"key":"2023012408323555200_b23","first-page":"127","article-title":"BioProspector: discovering conserved DNA motifs in upstream regulatory regions of co-expressed genes","volume":"6","author":"Liu","year":"2001","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012408323555200_b24","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1038\/nbt717","article-title":"An algorithm for finding protein-DNA interaction sites with applications to chromatin immunoprecipitation microarray experiments","volume":"20","author":"Liu","year":"2002","journal-title":"Nat. Biotechnol."},{"key":"2023012408323555200_b25","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1093\/nar\/29.3.774","article-title":"Phylogenetic footprinting of transcription factor binding sites in proteobacterial genomes","volume":"29","author":"McCue","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"2023012408323555200_b26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03315-9","volume-title":"Genetic Algorithms + Data Structures = Evolution Programs","author":"Michalewicz","year":"1996","edition":"3rd ed"},{"key":"2023012408323555200_b27","doi-asserted-by":"crossref","first-page":"1618","DOI":"10.1002\/pro.5560040820","article-title":"Gibbs motif sampling: detection of bacterial outer membrane protein repeats","volume":"4","author":"Neuwald","year":"1995","journal-title":"Protein Sci."},{"key":"2023012408323555200_b28","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1038\/nbt1098-939","article-title":"Finding DNA regulatory motifs within unaligned non-coding sequences clustered by whole-genome mRNA quantitation","volume":"16","author":"Roth","year":"1998","journal-title":"Nat. Biotechnol."},{"key":"2023012408323555200_b29","doi-asserted-by":"crossref","first-page":"6097","DOI":"10.1093\/nar\/18.20.6097","article-title":"Sequence logos: a new way to display consensus sequences","volume":"18","author":"Schneider","year":"1990","journal-title":"Nucleic Acids Res."},{"key":"2023012408323555200_b30","first-page":"11596","article-title":"Motif discovery in upstream sequences of coordinately expressed genes","volume":"3","author":"Stine","year":"2003","journal-title":"Evol. Comput., CEC \u201903"},{"key":"2023012408323555200_b31","doi-asserted-by":"crossref","first-page":"1183","DOI":"10.1073\/pnas.86.4.1183","article-title":"Identifying protein-binding sites from unaligned DNA fragments","volume":"86","author":"Stormo","year":"1989","journal-title":"Proc. Natl Acad. Sci."},{"key":"2023012408323555200_b32","first-page":"114","article-title":"Performance standards and evaluations in IR test collections: cluster-based retrieval models","volume":"33","author":"Shaw","year":"1997","journal-title":"Inf. Process. Manage."},{"key":"2023012408323555200_b33","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1093\/bioinformatics\/bth006","article-title":"Modeling within-motif dependence for transcription factor binding site predictions","volume":"6","author":"Zhou","year":"2004","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/13\/1577\/48838104\/bioinformatics_22_13_1577.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/13\/1577\/48838104\/bioinformatics_22_13_1577.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T08:50:10Z","timestamp":1674550210000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/13\/1577\/193995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4,21]]},"references-count":33,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2006,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl147","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,7,1]]},"published":{"date-parts":[[2006,4,21]]}}}