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

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-08 出版日期:2016-04-10
通讯作者: 吴璟莉
作者简介:吴璟莉(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-08 Published:2016-04-10
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]. 《计算机应用》唯一官方网站, 2024, 44(8): 2334-2341.
[2]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[3]	李志杰, 廖旭红, 李元香, 李青蓝. 基于基因关联分析的贝叶斯网络疾病样本分类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3449-3458.
[4]	陈都, 李圆媛, 陈彧. 基于t检验和逐步网络搜索的有向基因调控网络推断算法[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 199-205.
[5]	陈炯环, 鲍胜利, 王啸飞, 李若凡. 融合卷积与自注意力机制的基因型填补算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3534-3539.
[6]	刘延飞, 彭征, 王艺辉, 王忠. 基于改进的遗传算法的有刷直流电机PID参数整定[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1634-1641.
[7]	李宗正, 周恺卿, 欧云, 丁雷. 基于基因交换的自适应人工鱼群算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 701-707.
[8]	曹一珉, 蔡磊, 高敬阳. 基于生成对抗网络的基因数据生成方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 783-790.
[9]	陈昇, 周隽, 胡小兵, 马霁. 基于混合模拟退火算法的机场进场程序优化[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 606-615.
[10]	李昕, 贾韬. 基于组蛋白修饰数据预测基因差异性表达的深度融合模型[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3404-3412.
[11]	李智, 薛建彬. C‑V2X车联网中基于模拟退火算法的任务卸载与资源分配[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3140-3147.
[12]	湛航, 何朗, 黄樟灿, 李华峰, 张蔷, 谈庆. 改进的基于层次距离的基因表达式编程特征选择分类算法[J]. 计算机应用, 2021, 41(9): 2658-2667.
[13]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[14]	时永鹏, 张俊杰, 夏玉杰, 高雅, 张尚伟. 基于NOMA的5G超密网计算迁移与资源分配策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3319-3324.
[15]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.