求解两物种小系统发育问题的模拟退火算法

来源：计算机应用杂志2016年第4期北京时间：

作者：吴璟莉, 李先成

单位：1. 广西多源信息挖掘与安全重点实验室(广西师范大学), 广西 桂林 541004;2. 广西师范大学 计算机科学与信息工程学院, 广西 桂林 541004;3. 广西区域多源信息集成与智能处理协同创新中心, 广西 桂林 541004

摘要：针对复制-丢失比对问题模型,提出求解复制-丢失演化模型下两物种小系统发育问题(SPP)的模拟退火算法(SA2SP)。SA2SP引入比对算法用于构造问题初始解;引入标记算法用于构建问题解的目标函数,以得到问题解的进化代价;同时还引入3种智能邻域函数,利用基因序列的进化特性,指导性地产生邻域解。利用4种真实菌属的核糖体核糖核酸(rRNA)和转运核糖核酸(tRNA)基因数据对算法的性能进行测试,实验结果表明, SA2SP能够获得较伪布尔线性规划(PBLP)求解算法更小的进化代价,是求解复制-丢失演化模型下两物种小系统发育问题的一种有效方法。

关键词：小系统发育问题,模拟退火,邻域函数,基因

基金资助：国家自然科学基金资助项目(61363035, 61502111);广西自然科学基金资助项目(2015GXNSFAA139288, 2013GXNSFBA019263);"八桂学者"工程专项;广西多源信息挖掘与安全重点实验室系统性研究基金资助项目(14-A-03-02, 15-A-03-02)。