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

在所有多重序列比对算法中,渐进比对方法由于简单的算法和高效的计算在生物信息学中得到了广泛的应用。但是渐进方法最大的缺点是在早期阶段形成的错误不能在后期的计算中纠正过来。针对这个问题,我们设计了ProAnt比对算法,即渐进方法和蚁群算法相结合来求解多重序列比对问题。首先,对输入的多个序列进行预处理,用蚁群算法和概率一致性更新计算出所有字符对在最终比对中出现的概率,称为“后验概率”,计算后验概率是为了预防早期错误的发生。然后我们将后验概率作为字符对之间的匹配得分,用渐进方法得到最终的比对结果。用BAliBASE数据库对算法进行测试,实验结果显示,该算法能够在保持合理的运算时间的前提下显著改善渐进比对方法的正确性。

Combining Ant Colony Optimization and Progressive Method for 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 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.