求解多重序列比对问题的蚁群算法

Solving Multiple Sequence Alignment Based on Ant Colony Algorithm

多重序列比对是生物信息学特别是生物序列分析中一个重要的基本操作。提出求解多重序列比对问题的蚁群算法,利用人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中字符的概率,通过信息素的更新与调节相结合的策略较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力。另外在该算法的基础上,提出了基于分治策略的多序列比对蚁群求解算法,不但减少了原算法的计算时间,而且显著改善了算法所求得的解的质量。

Multiple sequence alignment is an important and fundamental problem in bioinformatics especially in the analysis of biosequences. A new ant. colony algorithm for multiple sequence alignment is presented. In the algorithm, artificial ants progressively select the matching character by the probability according to the pheromone, matching score between the characters and the deviation information of their locations. In addition, by strategies of pheromone updating, the algorithm can prevent local convergence and enhance its ability of optimization. Based on the algorithm, a more efficient algorithm for multiple sequence alignment using ant colony optimization and divide-and-conquer method is presented. Experimental results show that the algorithm can get high quality solution and reduce the running time.