The Combination Of Genetic Algorithm And Ant Algorithm And The Application In Biology Sequence Alignment

Sequence Alignment is one of the common business and also one of the most important methods to process the biology information. Sequence Alignment compares the similarity of the bioinformatics sequence data to infer their functions, structures and evolution information, and it's the foundation of such bioinformatics research as the gene identification, molecule evolution and life origin.Genetic Algorithm (GA) is an excellent algorithm of random global optimization, based on the based on natural selection theory and natural genetic mechanism, embodying the "competition for survival, the survival of the fittest, survival of the fittest" mechanism for competition. It simulated the system model of natural evolution mechanism to achieve the goal of optimizing specific parameters in the in an artificial system. Global convergence is the main characteristic of GA.Based on the research of the real-life behavior of ants in finding paths from the colony to food in nature, Ant Colony Algorithm is a random search algorithm by simulating the real process of ants' collaboration. Algorithm works by a number of individual ants to construct solution paths Solution together, through leaving the information element on the paths of solution exchanging of information element to improve the quality of solutions, thus achieving the purpose of improving the quality of solutions. Ant algorithm's main characteristics are the positive feedback and the implicit parallelism.In this paper, I researched the traditional ant algorithm and the genetic algorithm, and present a new type of GAAA algorithm through combining the two. The algorithm effectively uses of the ant algorithm positive feedback characteristics and the genetic algorithm global convergence properties, so it can find the optimal solution quickly and efficiently. Applied to solve the genetic algorithm biology sequence alignment problem, GAAA shows its feasibility and effectiveness through comparing with the classical algorithm in program. The main research work in this paper is as follows.1. A study of the infrastructure of Bioinformatics Sequence comparison and analysis of common sequence alignment algorithm.2. Research the ant algorithms and genetic algorithms: establish sequence alignment models respectively based on the ant colony algorithm and the genetic algorithm, and present two corresponding sequence alignment algorithms based on ant colony sequence alignment algorithm (AA_SA) and genetic algorithm sequence alignment algorithm (GA_ SA).3. Presents a new algorithm -- Ant and genetic algorithm (GAAA), which combines strongpoint of both the ant algorithm with positive feedback characteristics and the genetic algorithm global convergence properties. And applied GAAA to solve the problems of biology information sequence alignment and engineered the sequence alignment model based on GAAA and presents a GAAA algorithm description (GAAA_SA) of solving the sequence alignment problems.4. Implement DNA sequence alignment system, and does simulated experiment research with ant colony genetic algorithm, genetic algorithm and Ant Algorithm. The results show GAAA convergence rate is higher, and it is of better convergence properties, and GAAA can achieve global optimal solution within less iteration than the other two.