Ant Colony Optimization Methodfor Multiple Sequence Alignment

Among all the methods for multiple sequence alignment, progressive alignment is the most popular technique because of its simplicity and efficiency. The main drawback of progressive alignment is that the errors occurring in early stages can not be corrected in later stages. In this paper, we propose a novel algorithm called ProAnt which combines ant colony optimization and progressive alignment to improve the accuracy of alignment. To avoid the errors occurring in the early stage, the algorithm first calculates the posterior probability of all pairs of characters using ant colony optimization and probabilistic consistency updating. Then the algorithm computes the final alignment using progressive method where the matching score of character pair is replaced by their posterior probability. Experimental results on data from the BAliBASE database show that our algorithm can obtain much more accurate results and higher speed than the other progressive alignment method.