Research Of Multiple Sequence Alignment Based On Genetic Algorithm

In the late-20th century, under human genome project's driving, the Bioinformatics has been emerged. As the most important and basic operation in the Bioinformatics, the sequence comparison arouses widespread attention. The rationale of the Bioinformatics is the evolution theory,"if the comparability between one and another sequence is enough high, then it can extrapolate that the two sequences possibly have the common evolution ancestor". Multiple sequence alignment is playing the quite vital role in expounding the important biology pattern which bases on a group of correlative sequences.Genetic Algorithm (GA) is an important global searching algorithm, which is fit for solving the large-scale question. Generally speaking, it will be have a good effect when GA is used for solving NP-problem. Compared with other traditional optimization algorithm, GA is very robust, flexible and has a quick speed. Now it has been applied in more and more areas.This thesis mainly concentrates on solving multiple sequence alignments'problem by GA. Simple genetic algorithm has a slow convergence rate and hardly gets the global optimal solution, so Hierarchic Genetic Algorithm (HGA) is used here. For solving the simple genetic algorithm's shortage, several different heredity operators are used in HGA, in order to increase the algorithm's convergence rate and avoid the local optimal problem. A new initialization method is proposed in this thesis, which can enhance algorithm stability. Finally through some experiment, it confirms that the algorithm of this thesis is feasible and effective.