DNA Multiple Sequence Alignment Method Based on Genetic Algorithm

In order to solve the problems of both the alignment sequences number limitation and time-consuming which genetic algorithm will encounter in multiple sequence alignment,the authors propose a DNA multiple sequence alignment method based on genetic algorithm (GAMA).Aimed at the characteristics of DNA multiple sequence alignment,they point out that the traditional crossover operation will dramatically aggravate the computation burden of GA,and they adopt two new kinds of genetic operators (Indel&Undiv operators) in GAMA instead of the crossover and mutation operators used in normal GA.The BLAST similarity score matrix and an absolute alignment block weighed fitness evaluation function are adopted.The characters and gaps composed matrix,which is convenient for genetic operation as well as individual evaluation,are also adopted to coding the chromosome of population.There are only a few genetic operators in the scheme of this paper,of which the scheduling mechanism is also simple.This paper present an example of applying GAMA to DNA multiple-sequence alignment,the experiment results validate the feasibility of this algorithm.