Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (4): 1027-1032.DOI: 10.11772/j.issn.1001-9081.2016.04.1027

Previous Articles     Next Articles

Simulated annealing algorithm for solving the two-species small phylogeny problem

WU Jingli1,2,3, LI Xiancheng2   

  1. 1. Guangxi Key Laboratory of Multi-source Information Mining and Security(Guangxi Normal University), Guilin Guangxi 541004, China;
    2. College of Computer Science and Information Technology, Guangxi Normal University, Guilin Guangxi 541004, China;
    3. Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing, Guilin Guangxi 541004, China
  • Received:2015-08-31 Revised:2015-11-11 Online:2016-04-10 Published:2016-04-08
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61363035, 61502111), Guangxi Natural Science Foundation (2015GXNSFAA139288, 2013GXNSFBA019263), "Bagui Scholar" Project Special Funds, Research Fund of Guangxi Key Laboratory of Multi-source Information Mining & Security (14-A-03-02, 15-A-03-02).


吴璟莉1,2,3, 李先成2   

  1. 1. 广西多源信息挖掘与安全重点实验室(广西师范大学), 广西 桂林 541004;
    2. 广西师范大学 计算机科学与信息工程学院, 广西 桂林 541004;
    3. 广西区域多源信息集成与智能处理协同创新中心, 广西 桂林 541004
  • 通讯作者: 吴璟莉
  • 作者简介:吴璟莉(1978-),女,广西桂林人,教授,博士,CCF会员,主要研究方向:生物信息学、进化算法; 李先成(1988-),男,广西来宾人,硕士研究生,主要研究方向:生物信息学、进化算法。
  • 基金资助:
    国家自然科学基金资助项目(61363035, 61502111);广西自然科学基金资助项目(2015GXNSFAA139288, 2013GXNSFBA019263);"八桂学者"工程专项;广西多源信息挖掘与安全重点实验室系统性研究基金资助项目(14-A-03-02, 15-A-03-02)。

Abstract: In order to solve the two-species Small Phylogeny Problem (SPP) in the duplication-loss model, a simulated annealing algorithm named SA2SP was devised for the duplication-loss alignment problem. An alignment algorithm was introduced to construct the initial solution; a labeling algorithm was used to construct the object function and obtain the evolution cost; and three intelligent neighborhood functions were introduced to generate neighborhood solutions by using the evolutionary characteristics of gene sequences. The ribosomal RiboNucleic Acid (rRNA) and transfer Ribonucleic Acid (tRNA) of four real bacterium were used to test the performance of SA2SP and Pseudo-Boolean Linear Programming (PBLP) algorithm. The experimental results show that the SA2SP algorithm has smaller evolution cost, and it is an effective method for solving the two-species SPP in the duplication-loss model.

Key words: Small Phylogeny Problem (SPP), Simulated Annealing (SA), neighborhood function, gene

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

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

CLC Number: