渐进方法结合蚁群算法求解多序列比对问题  

Combining Ant Colony Optimization and Progressive Method for Multiple Sequence Alignment

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

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

出　　处：《计算机工程与应用》2006年第21期38-42,共5页Computer Engineering and Applications

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

摘　　要：在所有多重序列比对算法中,渐进比对方法由于简单的算法和高效的计算在生物信息学中得到了广泛的应用。但是渐进方法最大的缺点是在早期阶段形成的错误不能在后期的计算中纠正过来。针对这个问题,我们设计了ProAnt比对算法,即渐进方法和蚁群算法相结合来求解多重序列比对问题。首先,对输入的多个序列进行预处理,用蚁群算法和概率一致性更新计算出所有字符对在最终比对中出现的概率,称为“后验概率”,计算后验概率是为了预防早期错误的发生。然后我们将后验概率作为字符对之间的匹配得分,用渐进方法得到最终的比对结果。用BAliBASE数据库对算法进行测试,实验结果显示,该算法能够在保持合理的运算时间的前提下显著改善渐进比对方法的正确性。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 occur in early stage can not be corrected in later stage.In this paper,we have proposed ProAnt algorithm which combining ant colony optimization and progressive alignment to improve the accuracy of alignment.Firstly,to avoid the errors occur in the early stage,we calculate the posterior probability of all pairs of characters using ant colony optimization and probabilistic consistency updating.Secondly,we compute the final alignment using progressive method in which the matching score of a pair of characters is replaced by posterior probability.On the BAliBASE benchmark alignment database,the algorithm demonstrates reasonable running time and significant improvement in accuracy compared to progressive alignment method.

关 键 词：多序列比对 蚁群算法 渐进比对方法 后验概率 概率一致性 

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