Title :
Ant Colony Optimization Methodfor Multiple Sequence Alignment
Author :
Chen, Ling ; Liu, Wei ; Chen, Juan
Author_Institution :
Yangzhou Univ., Yangzhou
Abstract :
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.
Keywords :
biology computing; molecular biophysics; molecular configurations; optimisation; probability; proteins; BAliBASE database; ProAnt; ant colony optimization; bioinformatics; molecular biology; multiple sequence alignment; posterior probability; probabilistic consistency updating; protein; Ant colony optimization; Bioinformatics; Cybernetics; Databases; Evolution (biology); Iterative algorithms; Machine learning; Probability; Proteins; Sequences; Ant colony optimization; Bioinformatics; Multiple sequences alignment;
Conference_Titel :
Machine Learning and Cybernetics, 2007 International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
978-1-4244-0973-0
Electronic_ISBN :
978-1-4244-0973-0
DOI :
10.1109/ICMLC.2007.4370272