TFBS identification by position- and consensus-led genetic algorithm with local filtering

Abstract

Identification of Transcription Factor Binding Site (TFBS) motifs in multiple DNA upstream sequences is important in understanding the mechanism of gene regulation. This identification problem is challenging because such motifs are usually weakly conserved due to evolutionary variation. Exhaustive search is intractable for finding long motifs because the combinatorial growth of the search space is exponential, thus heuristic methods are preferred. In this paper, we propose the Genetic Algorithm with Local Filtering (GALF) to address the problem, which combines and utilizes both position-led and consensus-led representations in present GA approaches. While position-led representation provides flexibility to move around the search space, it is likely to contain some "false positive" sites within an individual. This problem can be overcome by our local filtering operator, which employs consensus-led representation, while it needs less computation than alignments used in conventional consensus-led approaches. Thus both efficiency and accuracy can be achieved. The experimental results on real biological data show that our method can identify TFBSs more accurately and efficiently than other methods including GA-based ones, and is able to deal with relaxed motif widths with superior correctness. Copyright 2007 ACM.