Phylogenetic tree constructing algorithm based on genetic algorithm

doi:10.3778/j.issn.1002-8331.2009.16.020

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (16): 72-76.DOI: 10.3778/j.issn.1002-8331.2009.16.020

• 研究、探讨 • Previous Articles Next Articles

Phylogenetic tree constructing algorithm based on genetic algorithm

GUO Jing¹,WANG Chao¹,CHEN Ling^2,3

1.Department of Electronic and Information Engineering，Yangzhou Polytechnic Institute，Yangzhou，Jiangsu 225127，China
2.College of Information Engineering，Yangzhou University，Yangzhou，Jiangsu 225009，China
3.National Key Lab of Novel Software Technology，Nanjing University，Nanjing 210093，China

Received:2009-02-16 Revised:2009-04-03 Online:2009-06-01 Published:2009-06-01
Contact: GUO Jing

基于遗传算法的系统发生树构建方法

郭静¹,王超¹,陈崚^2,3

1.扬州工业职业技术学院电子信息工程系，江苏扬州 225127
2.扬州大学信息工程学院，江苏扬州 225009
3.南京大学软件新技术国家重点实验室，南京 210093

通讯作者: 郭静

Abstract

Abstract: A method for Phylogenetic Tree Construction based on Genetic Algorithm（GA-PTC） is presented.GA-PTC first encodes the possible tree topologies into the solution space of the problem，and then searches for the optimal tree in the searching space.To coding the solutions，this paper proposes a suffix representation as the encoding strategy of genetic algorithm.To evaluate quality of the individual，this paper adopts a distance based fitness function to score solution，and selects parts of individuals according to a selection strategy called roulette wheel where the select probability is proportional to the fitness value. Experimental results show that GA-PTC can obtain higher accuracy results than UPGMA.

Key words: genetic algorithm, phylogenetic tree, suffix representation

摘要： 提出了一种基于遗传算法的系统发生树构建方法。将遗传算法应用于系统发生树的构建，首先，用后缀表示法将树的拓扑结构表示成编码的形式。其次，针对系统发生树的性质，设计了交叉和变异操作方法，确定了对个体的评价及选择策略，从而通过遗传操作，最终搜索到最优解。实验结果表明该算法可以得到与传统UPGMA算法拓扑结果一致的系统发生树，并且除了最优拓扑结构的树之外，该算法还可以输入多个具有相似质量的树。

关键词: 遗传算法, 系统发生树, 后缀表示

GUO Jing¹,WANG Chao¹,CHEN Ling^2,3. Phylogenetic tree constructing algorithm based on genetic algorithm[J]. Computer Engineering and Applications, 2009, 45(16): 72-76.

郭静¹,王超¹,陈崚^2,3. 基于遗传算法的系统发生树构建方法[J]. 计算机工程与应用, 2009, 45(16): 72-76.

[1]	LI Yuqi, LIU Zhiqian, CHENG Ningyi, WANG Yingying, ZHU Chunli. Path Planning of UAV Under Multi-constraint Conditions [J]. Computer Engineering and Applications, 2021, 57(4): 225-230.
[2]	YANG Wei, WU Yingying, WANG Ting. Research on Configuration Optimization Problems of Shuttle-Carrier Storage and Retrieval System [J]. Computer Engineering and Applications, 2021, 57(4): 258-265.
[3]	LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window [J]. Computer Engineering and Applications, 2021, 57(23): 255-262.
[4]	DU Shouxin, WU Tao. Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning [J]. Computer Engineering and Applications, 2021, 57(22): 182-189.
[5]	CAO Lijia, LIU Yang. Recent Advances in Scheduling Optimization of Automated Guided Vehicles in Manufacturing Workshops [J]. Computer Engineering and Applications, 2021, 57(21): 59-67.
[6]	CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(20): 164-171.
[7]	MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying. Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification [J]. Computer Engineering and Applications, 2021, 57(20): 287-298.
[8]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[9]	DAI Jiangtao, HAN Xiaolong. Coordinated Scheduling of Equipment in Container Terminals Considering Energy Consumption Under Different Job Status [J]. Computer Engineering and Applications, 2021, 57(19): 290-298.
[10]	FENG Xiaodong, HUANG Shirong, DAI Guan’ou, YANG Weijia, LUO Yaozhi. Research and Application of Beetle Antennae Genetic Hybrid Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 90-100.
[11]	SU Qing, LIN Huazhi, HUANG Jianfeng, LIN Zhiyi. Malicious Android Application Detection Combining CNN and Catboost Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 140-146.
[12]	JIANG Liangzhong, LEI Hang, LI Zhenhao, QIAN Weizhong, SHI Gantu. Research on Outbound Slotting Optimization Method by Using Adaptive Optimization Weights [J]. Computer Engineering and Applications, 2021, 57(15): 271-278.
[13]	HE Jiao, TAN Dailun. Three-Dimensional Terrain Path Planning Based on Sight Range and Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 279-285.
[14]	WANG Xiuli, ZHOU Peng, HOU Jingnan, WANG Shijun, LIN Xia. Research on Algorithm of Inspection Path Planning for Substation Robot [J]. Computer Engineering and Applications, 2021, 57(14): 245-250.
[15]	CHEN Yuanwen. Application of MapReduce Technology in Problem of Material Transportation and Stowage [J]. Computer Engineering and Applications, 2021, 57(12): 273-278.

Phylogenetic tree constructing algorithm based on genetic algorithm

基于遗传算法的系统发生树构建方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics