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

doi:10.11772/j.issn.1001-9081.2016.04.1027

计算机应用 ›› 2016, Vol. 36 ›› Issue (4): 1027-1032.DOI: 10.11772/j.issn.1001-9081.2016.04.1027

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

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

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

收稿日期:2015-08-31 修回日期:2015-11-11 出版日期:2016-04-10 发布日期:2016-04-08
通讯作者: 吴璟莉
作者简介:吴璟莉(1978-),女,广西桂林人,教授,博士,CCF会员,主要研究方向:生物信息学、进化算法; 李先成(1988-),男,广西来宾人,硕士研究生,主要研究方向:生物信息学、进化算法。
基金资助:
国家自然科学基金资助项目(61363035, 61502111);广西自然科学基金资助项目(2015GXNSFAA139288, 2013GXNSFBA019263);"八桂学者"工程专项;广西多源信息挖掘与安全重点实验室系统性研究基金资助项目(14-A-03-02, 15-A-03-02)。

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

WU Jingli^1,2,3, LI Xiancheng²

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).

摘要/Abstract

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

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

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

中图分类号:

TP301.6

吴璟莉, 李先成. 求解两物种小系统发育问题的模拟退火算法[J]. 计算机应用, 2016, 36(4): 1027-1032.

WU Jingli, LI Xiancheng. Simulated annealing algorithm for solving the two-species small phylogeny problem[J]. Journal of Computer Applications, 2016, 36(4): 1027-1032.

参考文献

[1] HOLLOWAY P, SWENSON K, ARDELL D, et al. Ancestral genome organization:an alignment approach[J]. Journal of Computational Biology, 2013,20(4):280-295.
[2] ANDREOTTI S, KNUT R, CANZAR S. The duplication-loss small phylogeny problem:from cherries to trees[J]. Journal of Computational Biology, 2013,20(9):643-659.
[3] DONG H, NILSSON L, KURLAND C G. Co-variation of tRNA abundance and codon usage in escherichia coli at different growth rates[J]. Journal of Molecular Biology, 1996, 260(5):649-663.
[4] KANAYA S, YAMADA Y, KUDO Y, et al. Studies of codon usage and tRNA genes of 18 unicellular organisms and quantification of Bacillus subtilis tRNAs:gene expression level and species-specific diversity of codon usage based on multivariate analysis[J]. Gene, 1999,238(1):143-155.
[5] KOVÁC J, BREJOVÁ B, VINAR T. A new approach to the small phylogeny problem[EB/OL].[2015-02-25]. http://arxiv.org/abs/1012.0935.
[6] GUPTA A, MANUCH J, STACHO L, et al. Small phylogeny problem:character evolution trees[M]//SAHINALP S C, MUTHUKRISHNAN S, DOGRUSOZ U. Combinatorial Pattern Matching, LNCS 3109. Berlin:Springer, 2004:230-243.
[7] BLOMME T, van DEPOELE K, DE BODT S, et al. The gain and loss of genes during 600 million years of vertebrate evolution[EB/OL].[2015-02-06]. http://pmcc.web-t.cisti.nrc.ca/picrender.cgi?accid=PMC1779523&blobtype=pdf.
[8] COTTON J A, PAGE R D. Rates and patterns of gene duplication and loss in the human genome[J]. Proceedings of the Royal Society, 2005,272(1560):277-283.
[9] WAPINSKI I, PFEFFER A, FRIEDMAN N, et al. Natural history and evolutionary principles of gene duplication in fungi[J]. Nature, 2007,449(7158):54-61.
[10] DEMUTH J P, DE BIE T, STAJICH J E, et al. The evolution of mammalian gene families[J]. PloS One, 2006,1(1):E85.
[11] KEITH J M, ADAMS P, BRYANT D, et al. A simulated annealing algorithm for finding consensus sequences[J]. Bioinformatics, 2002,18(11):1494-1499.
[12] ZOLA J, TRYSTRAM D, TCHERNYKH A, et al. Parallel multiple sequence alignment with local phylogeny search by simulated annealing[C]//Proceedings of the 2006 20th International Parallel and Distributed Processing Symposium. Washington, DC:IEEE Computer Society, 2006:253.
[13] CHEN S M, LIN C H. Multiple DNA sequence alignment based on genetic simulated annealing techniques[J]. International Journal of Information and Management Sciences, 2007,18(2):97-111.
[14] SARIYER O S, GVVEN C. Sequence alignment using simulated annealing[J]. Physica A:Statistical Mechanics and its Applications, 2010,389(15):3007-3012.
[15] DONDI R, EL-MABROUK N. On the complexity of minimum labeling alignment of two genomes[EB/OL].[2015-05-22]. http://arxiv.org/abs/1206.1877v1.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	湛航, 何朗, 黄樟灿, 李华峰, 张蔷, 谈庆. 改进的基于层次距离的基因表达式编程特征选择分类算法[J]. 计算机应用, 2021, 41(9): 2658-2667.
[2]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[3]	时永鹏, 张俊杰, 夏玉杰, 高雅, 张尚伟. 基于NOMA的5G超密网计算迁移与资源分配策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3319-3324.
[4]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[5]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[6]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[7]	刘昂, 蒋近, 徐克锋. 改进蚁群和鸽群算法的机器人路径规划[J]. 计算机应用, 2020, 40(11): 3366-3372.
[8]	李功丽, 李钰, 张恩, 尹天宇. 面向用户隐私保护的高效基因比对方案[J]. 计算机应用, 2020, 40(1): 136-142.
[9]	朱杰, 张文怡, 薛菲. 基于遗传模拟退火算法的立体仓库储位优化[J]. 计算机应用, 2020, 40(1): 284-291.
[10]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[11]	林立, 孟学雷, 宋仲仲. 考虑区域协调性的城际列车开行方案优化[J]. 计算机应用, 2019, 39(2): 598-603.
[12]	李飞龙, 赵春艳, 范如梦. 基于禁忌搜索算法求解随机约束满足问题[J]. 计算机应用, 2019, 39(12): 3584-3589.
[13]	高慧云, 陆慧娟, 严珂, 叶敏超. 基于差异性和准确性的加权调和平均度量的基因表达数据选择性集成算法[J]. 计算机应用, 2018, 38(5): 1512-1516.
[14]	喻德旷, 杨谊. 肿瘤特征基因选择的互信息最值过滤原则与粒子群优化算法[J]. 计算机应用, 2018, 38(2): 421-426.
[15]	张传浩, 周桥. 节点效用最大化的服务功能链构建方法[J]. 计算机应用, 2018, 38(2): 503-508.