Evolutionary Algorithm For Motif Discovery

With the increasing volume of biologic sequences available in public databases. Identification the transcription factor binding sites (TFBSs), which are relative short, recurring, conservative patterns in the regulatory regions of deoxyribonucleic acid (DNA) and are regard as having a specified biological meaning to regulate the transcriptional activity of genes(gene expression), by computational methods is a major challenge in bioinformatics.The bacterial foraging optimization (BFO) algorithm is a nature and biologically inspired computing method.First, we propose an efficient approach based on bacterial foraging optimization algorithm (IBFOMD) to discover conservative motifs in sequential data. We modify the original BFO via established a hybrid combination initial population, introduce Rao metric and implement transplacement mutation. we sum up IBFOMD's 6 advantages. First, we established a hybrid combination initial population which it could reduce the search space, increase the diversity of the population and speed up the constringency. Second, we introduced The Rao metric to exhibit swarm together effect in order to achieve the finding motif aim which based on BFO algorithm, and it works. Third, we implement transplacement mutation in the elimination and dispersal events step to produce a new better individual. Fourth, more than one motif may be discovered in one sequence by IBFOMD. Fifth, using the one point crossover based on Elitist Selection to conquer the trouble of local extreme which arises in the original BFO with higher probability. Finally, it performed superior than some other well-known finding motif approaches (e.g., Weeder)in terms of runtime.Second, we propose an alternative solution integrating bacterial foraging optimization algorithm and tabu search (TS) algorithm namely TS-BFO. We modify the original BFO via established a self-control multi-length chemotactic step mechanism, and introduce rao metric. We utilize it to solve motif discovery problem and compare the experimental result with existing famous DE/EDA algorithm which combines global information extracted by estimation of distribution algorithm (EDA) with differential information obtained by Differential evolution (DE) to search promising solutions. We sum up TS-BFO's 4 advantages. First, we established a self-control multi-length chemotactic step mechanism which could extend the search space, avoid local extremum and speed up the constringency. Second, we introduced The Rao metric to exhibit swarm together effect in order to achieve the finding motif aim which based on BFO algorithm, and it works. Third, using the one point crossover based on elitist selection to conquer the trouble of local extremum which arises in the original BFO with higher probability. Finally and the one of the most important point, integrating Tabu Search algorithm could abstain the duplicate individuals generates in each step, guide the search orientation, and find the global solutionThird, we modify the TS-BFO via introduce DE/EDA operator replace the Reproduction which exist on the original BFO. We called it TSBFD.The experiments on real data set selected from TRANSFAC and SCPD database have predicted meaningful motif which demonstrated that IBFOMD, TS-BFO and TSBFD are promising approaches for finding motif and enrich the technique of motif discovery.As we known that none of the computing methods could discover all the motifs concealed within the upstream sequences, however, we will try our best to improve the algorithms to discover more than the others. An elegant method to automatic ascertains the length of the motif and a better objective function which are still the problems we should take into account. We also employed the algorithms to wider range of data sets so that reveal its advantages and disadvantages.