The Application And Research Of Ant Colony Algorithm On Sequence Alignment

Sequence alignment is a basic method to process the biology information in Bioinformatics. It compares the similarity of the bioinformatics sequence data to infer their functions, structures and evolution information. It has significant meaning for such bioinformatics researches as the gene recognition, protein function identification, second structure prediction and molecular evolution and so on. Ant colony algorithm(ACA)is a novel random search algorithm by simulating the real ants'foraging behavor in the nature.For its excelllent characteristic such as positive feedback, self-organizing and robustness, we applied ant colony algorithm to sequence alignment. The main work of this paper are as follows:Firstly, in order to avoid the stagnation behavior and accelerate the convergence rate of ant colony algorithm, this paper proposed a new hybrid behavior based ant colony pairwise alignment algorithm which expanded searching space by increasing ants'behavior models and accelerated the convergence rate by changing pheromone updating policies. Experimental results shows that both optimized global results and convergence rate are much improved compared with ant colony algorithm.Secondly, for the traditional multiple sequence alignment (MSA) model which based on letters having some deficiencices in visual effect, this paper proposed a new multiple sequences alignment algorithm based on base graph. This algorithm first bisects the DNA sequences into four graphs that only contain A,C,G,T, then the ant colony algorithm is applied to search every graph respectively, and at last combine four base graphs and get the alignment result. We build a new MSA model according to the representation of sequence. The main advantage of this method is that: we can find the content of every base and the distributions of all the bases. Besides, by this representation for multiple sequences, we can reduce the impact of other characters. By experimenting with some sequence samples , experimental results show that this method is reasonable and efficient. Furthermore we compare our aligning results with results of the most popular aligning software ClustalX and can get satisfying results.