Research On Sequence Alignment Based On Ant Colony Algorithm

Bioinformatics is the science of using computer technology to store, retrieve and analyze biological information in the field of life sciences. Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained from sequence alignment, one can infers the structure, function and evolutionary relationship of genes.Ant colony algorithm(ACA) is a novel bionic evolutionary algorithm. As a global searching approach, ACA has some characteristic, such as positive feedback, distributing,paralleling, self-organizing, etc,and from it was introduced, it has been used to solve all kinds of complex optimization problem.This thesis mainly focuses on the study of double sequence alignment and multiple sequence alignment based on ant colony algorithm. First,ant colony double sequence alignment algorithm is analyzed,a model of ant colony double sequence alignment is designed. An intelligent ant colony algorithm based on a new approach to alter pheromone is presented. This new algorithm uses the history optimization information to update pheromone,avoids prematurity and accelerates the convergence of algorithm in later period.The results demonstrate that this new approach is reasonable and efficient. Then, based on basic ant colony multiple sequence alignment algorithm, a model of ant colony multiple sequence alignment is designed, a round-trip searching ant colony algorithm for multiple sequence alignment is proposed. Some changes have done in the algorithm including the renewal mode of the pheromone, the select means of the characters, the search strategy of ants on the trip between ant nest and food, the random distributing of the ants beginning sequence. The results show that stagnation behavior of basic ant colony mutiple sequence alignment algorithm are avoided and a good ability of searching better solution in the last runs of the improved algorithm.