基于蚁群优化的系统发生树构建算法  

An Ant Colony Optimization Algorithm for Constructing Phylogenetic Tree

作　　者：陈伯伦[1] 陈崚[1,2] 秦玲[3] 刘维[3] 

机构地区：[1]扬州大学信息学院,江苏扬州225009 [2]南京大学软件新技术国家重点实验室,江苏南京210093 [3]南京航空航天大学信息与科学技术学院,江苏南京210093

出　　处：《微电子学与计算机》2009年第10期17-20,共4页Microelectronics & Computer

基　　金：国家自然科学基金项目(60673060,60773103);江苏省自然科学基金项目(BK2008206);江苏省教育厅自然科学基金项目(08KJB520012);江苏省研究生科研创新计划(06-76,CX08B-098Z)

摘　　要：提出一种基于蚁群优化的系统发生树构建算法PTAC.该算法首先将基因序列集合划分为两大类,使得两个类内部的基因序列具有极大的相似性,而两个类之间则具有极大的差异性.然后,再分别对所得到的两大类进一步进行划分.重复这样的划分过程,直至每一类中只有一个基因序列为止,也就是系统发生树的叶子节点被构建完成.实验证明算法PTAC可以获得比类似方法质量更好的系统发生树,而在解决中小规模问题时,PTAC方法比ACPTHC和ACPT方法算法收敛速度更快.An ant colony optimization algorithm for constructing phylogenetic tree （PTAC） is presented. In the algo-rithm, the original gene sequences were split into two groups as the two children of the root node, such that each sequence is more similar with other ones in the same group than those in the other group, and the center sequence of the two children groups are adaptively updated. Then the same process is applied to each of the two groups recursively to construct the phylogenetic tree until there is only one gene sequence in each sub-group. Our experimental results show that PTAC can construct phylogenetic tree with higher quality than the other similar methods. PTAC has faster convergence speed than ACPTHC and ACPT on middle or small size problems.

关 键 词：生物信息学 系统发生分析 系统发生树 蚁群优化 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]