计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (32): 159-162.

• 数据库、信号与信息处理 • 上一篇    下一篇

构建系统发生树后缀表示的蚁群算法

张宏彬1,郭 静1,王 超1,陈 崚2,3   

  1. 1.扬州工业职业技术学院 电子信息工程系,江苏 扬州 225127
    2.扬州大学 信息工程学院,江苏 扬州 225009
    3.南京大学 软件新技术国家重点实验室,南京 210093
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-11-11 发布日期:2011-11-11

Phylogenetic tree constructing algorithm based on suffix representation

ZHANG Hongbin1,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:1900-01-01 Revised:1900-01-01 Online:2011-11-11 Published:2011-11-11

摘要: 提出一种基于后缀表示的构建系统发生树的蚁群算法(SR-PTC),该算法用蚂蚁访问物种集合以形成一个对应最优系统发生树的后缀表示序列。为构成一个合法的系统发生树的后缀表示,蚂蚁对内部结点的选择要受到限制,分别为叶结点和内部结点设置两个不同的选择概率,并用赌轮盘选择方法来决定两种结点的选择。另外,在信息素更新时,加入当前树的评价值来影响蚂蚁的运动方向。实验结果表明,此方法能得到较为准确的拓扑结构,在物种数目较小时可以较快地得到结果。

关键词: 系统发生树, 蚁群算法, 后缀表示, 遍历, 信息素

Abstract: A phylogenetic tree construction method based on suffix representation(SR-PTC)is presented.In this algorithm,ants search in the collection containing species and the internal nodes,and construct a suffix representation sequence which corresponding to a phylogenetic tree.In this method,ants select different nodes with different probability and form a phylogenetic tree represented by suffix representation.Furthermore,the pheromone on each edge is updated according to the fitness value of the phylogenetic tree.Experimental results show that this method can obtain high accuracy results,high convergence speed.

Key words: phylogenetic tree, ant colony algorithm, suffix representation, traverse, pheromone