The Application Of Ant Colony Algorithm To Biological Sequence Alignment

Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained through sequence alignment one can infers the structure, function and evolutionary relationship of genes.Ant colony algorithm is a novel simulated evolutionary algorithm, which is used to solve the optimization problems through simulating the way of ants finding the shortest path for food. This algorithm has been applied successfully to combinatorial optimization problems such as traveling salesman problem.In this paper, ant colony algorithm is applied to sequence alignment based on the study of the development of sequence alignment. A new algorithm for sequence alignment based on ant colony algorithm is put forward and is improved for adapting to its new application. This new algorithm is applied to DNA sequence alignment and protein sequence alignment in the experiment. The results of experiment demonstrate that the new approach is reasonable and efficient.According to the limitation of running into local optimum in ant colony algorithm, an improved algorithm, which is based on adaptively adjusting the increase of the routes' pheromone according to the solutions that artificial ants have found, is proposed. This method will not easily fall in the local optimum. Thus it can expand the search space and increase the probability of converging at the global optimum. The results of experiment show that the improved algorithm can achieve better performance than the basic ant colony algorithm does in sequence alignment.