Multiple-Searching Adaptive Genetic Algorithm For Multiple Sequence Alignment

The multiple sequence alignment (MSA) is of great value to the research in bioinformatics since it supports the development of Genetic Sciences such as Expecting the functions & structures of Protein, the discovering the Evolutionary Relationships, and developing new medicine. However, MSA problem is known to be NP-hard, more still left undetermined. Obviously, MSA is among the most important and challenging task in computational biology.Algorithms are classified three species:dynamic programming method, progressive method and iterative method.In some sense, they all have some deficiencies. Nowadays,the main disadvantage of progressive domestic is the local minimum" problem and iterative algorithm is time consuming.This paper proposed a adaptive genetic algorithm for multiple sequence alignment, and probabilities of crossover and mutation were adjusted based on the entropy, furthermore,with the consideration of two point crossover algorithms and mutation at a long segments, this paper presented some new genetic operators. The experiment results showed that the algorithm presented can overcome permutation convergence and find global optima efficiently. Through making test at representative test cases of BAliBASE to prove that the algorithm is effective. And compare with the most extensive application of the multiple sequence alignment software CLUSTAL at the SPS and CS values. In dealing with the middle and long sequence, the hazy area and with N/C-terminal extension of the sequence, the SAGA algorithm is more problem-solving, with the high value of CS, the same sequences have good results.