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

• 作者: 陈娟 陈崚
• 来源期刊: 计算机应用研究
• 关键词: 生物信息学 多重序列比对 蚁群算法 分治策略
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 研究探讨
• 页码范围: 25-30
• 页数: 6页
• 分类号: TP37|O141.3
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2007.01.007

摘要

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