Research On Motif Discovery Method Based On Immune Genetic Algorithm

Motif discovery in biological sequences is a hot issue in bioinformatics and a fundametal computational problem with important applicaitons in understanding gene regulation. As the motif with very short length, non-hundred percent conservative, and the complexity of biological data, the identification of motifs through computational methods is still a major challenge. Because of its relative superiority to the traditional optimization algorithm, evolutionary algorithm has recently been more widely applied to the motif discovery problem, and becomes an important direction of development.The lack of premature convergence and random roaming limits GA's application. People find that biological immune system can keep the diversity well, and inhibit premature convergence and random roaming. Therefore, we can effectively improve and enhance the performance of genetic algorithm by using the immune theory.Considering the lack of population diversity maintain with genetic algorithm and the advantages of biological immune system, we introduce concentration regulation into genetic algorithm and propose an immune genetic algorithm based on concentration mechanism and apply to motif discovery. We define new formuals of antibody affinity and antibody concentration according to the definition of motif discovery problem and the representation of motifs. Based on the election operator of GA, we introduce a concentration regulation operator to inhibit the reproduce of high concentration antibodys. The proposed method can effectively maintain the population diversity and inhibit premature convergence phenomenon. Experimental results show that the method could find motifs in relative long sequences and multiple motifs in a single run.In order to inhibit the degradation during evolution, we introdce the regulation of vaccine and propose an motif discovery method based on immune vaccine. The Population degradation could be well inhibited by extracting the vaccine, vaccination and immunization choice, so the convergence could be speed up. Experimental results show that the motif discovery ability has been further improved.