计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (16): 72-76.DOI: 10.3778/j.issn.1002-8331.2009.16.020

• 研究、探讨 • 上一篇    下一篇

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

郭 静1,王 超1,陈 崚2,3   

  1. 1.扬州工业职业技术学院 电子信息工程系,江苏 扬州 225127
    2.扬州大学 信息工程学院,江苏 扬州 225009
    3.南京大学 软件新技术国家重点实验室,南京 210093
  • 收稿日期:2009-02-16 修回日期:2009-04-03 出版日期:2009-06-01 发布日期:2009-06-01
  • 通讯作者: 郭 静

Phylogenetic tree constructing algorithm based on genetic algorithm

GUO Jing1,WANG Chao1,CHEN Ling2,3   

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

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

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

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