TFBS identification based on genetic algorithm with combined representations and adaptive post-processing Export

@article{citeulike:2096011, abstract = {Motivation: Identification of transcription factor binding sites (TFBSs) plays an important role in deciphering the mechanisms of gene regulation. Recently, GAME, a Genetic Algorithm (GA)-based approach with iterative post-processing, has shown superior performance in TFBS identification. However, the basic GA in GAME is not elaborately designed, and may be trapped in local optima in real problems. The feature operators are only applied in the post-processing, but the final performance heavily depends on the GA output. Hence, both effectiveness and efficiency of the overall algorithm can be improved by introducing more advanced representations and novel operators in the GA, as well as designing the post-processing in an adaptive way. Results: We propose a novel framework GALF-P, consisting of Genetic Algorithm with Local Filtering (GALF) and adaptive post-processing techniques (-P), to achieve both effectiveness and efficiency for TFBS identification. GALF combines the position-led and consensus-led representations used separately in current GAs and employs a novel local filtering operator to get rid of false positives within an individual efficiently during the evolutionary process in the GA. Pre-selection is used to maintain diversity and avoid local optima. Post-processing with adaptive adding and removing is developed to handle general cases with arbitrary numbers of instances per sequence. GALF-P shows superior performance to GAME, MEME, BioProspector and BioOptimizer on synthetic datasets with difficult scenarios and real test datasets. GALF-P is also more robust and reliable when further compared with GAME, the current state-of-the-art approach. Availability: http://www.cse.cuhk.edu.hk/\~{}tmchan/GALFP/ Contact: tmchan@cse.cuhk.edu.hk Supplementary information: Supplementary data are available at Bioinformatics online. 10.1093/bioinformatics/btm606}, address = {Department of Computer Science \& Engineering, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong.}, author = {Chan, Tak-Ming and Leung, Kwong-Sak and Lee, Kin-Hong}, booktitle = {Bioinformatics}, citeulike-article-id = {2096011}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/btm606}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/24/3/341}, citeulike-linkout-2 = {http://view.ncbi.nlm.nih.gov/pubmed/18065426}, citeulike-linkout-3 = {http://www.hubmed.org/display.cgi?uids=18065426}, day = {1}, doi = {10.1093/bioinformatics/btm606}, issn = {1460-2059}, journal = {Bioinformatics}, keywords = {algorithm, genetic}, month = {February}, number = {3}, pages = {341--349}, posted-at = {2008-01-10 03:02:04}, priority = {2}, title = {TFBS identification based on genetic algorithm with combined representations and adaptive post-processing}, url = {http://dx.doi.org/10.1093/bioinformatics/btm606}, volume = {24}, year = {2008} }

TY - JOUR ID - citeulike:2096011 L3 - citeulike-article-id:2096011 N2 - Motivation: Identification of transcription factor binding sites (TFBSs) plays an important role in deciphering the mechanisms of gene regulation. Recently, GAME, a Genetic Algorithm (GA)-based approach with iterative post-processing, has shown superior performance in TFBS identification. However, the basic GA in GAME is not elaborately designed, and may be trapped in local optima in real problems. The feature operators are only applied in the post-processing, but the final performance heavily depends on the GA output. Hence, both effectiveness and efficiency of the overall algorithm can be improved by introducing more advanced representations and novel operators in the GA, as well as designing the post-processing in an adaptive way. Results: We propose a novel framework GALF-P, consisting of Genetic Algorithm with Local Filtering (GALF) and adaptive post-processing techniques (-P), to achieve both effectiveness and efficiency for TFBS identification. GALF combines the position-led and consensus-led representations used separately in current GAs and employs a novel local filtering operator to get rid of false positives within an individual efficiently during the evolutionary process in the GA. Pre-selection is used to maintain diversity and avoid local optima. Post-processing with adaptive adding and removing is developed to handle general cases with arbitrary numbers of instances per sequence. GALF-P shows superior performance to GAME, MEME, BioProspector and BioOptimizer on synthetic datasets with difficult scenarios and real test datasets. GALF-P is also more robust and reliable when further compared with GAME, the current state-of-the-art approach. Availability: http://www.cse.cuhk.edu.hk/~tmchan/GALFP/ Contact: tmchan@cse.cuhk.edu.hk Supplementary information: Supplementary data are available at Bioinformatics online. 10.1093/bioinformatics/btm606 IS - 3 JF - Bioinformatics SN - 1460-2059 AD - Department of Computer Science & Engineering, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong. EP - 349 TI - TFBS identification based on genetic algorithm with combined representations and adaptive post-processing VL - 24 T2 - Bioinformatics SP - 341 KW - algorithm KW - genetic AU - Chan, Tak-Ming AU - Leung, Kwong-Sak AU - Lee, Kin-Hong PY - 2008/02/01/ UR - http://dx.doi.org/10.1093/bioinformatics/btm606 ER -