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

Solving Multiple Sequence Alignment Based on Ant Colony Algorithm

作　　者：陈娟[1] 陈崚[1] 

机构地区：[1]扬州大学信息工程学院计算机系,江苏扬州225009

出　　处：《计算机应用研究》2007年第1期25-30,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(60473012);国家科技攻关项目(2003BA614A-14);江苏省自然科学基金资助项目(BK2005047);南京大学软件新技术国家重点实验室开放基金资助项目

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

关 键 词：生物信息学 多重序列比对 蚁群算法 分治策略 

分 类 号：TP37[自动化与计算机技术—计算机系统结构] O141.3[自动化与计算机技术—计算机科学与技术]