基于归一化编辑距离的系统进化树重构  

Phylogenetic Tree Reconstruction Based on Normalized Edit Distance

作　　者：李玉鉴[1] 王方圆[1] 

机构地区：[1]北京工业大学计算机学院,北京100022

出　　处：《北京工业大学学报》2008年第11期1211-1215,共5页Journal of Beijing University of Technology

基　　金：国家自然科学基金资助项目(60775010);北京市自然科学基金资助项目(4052005);北京市属市管高等学校'中青年骨干教师培养计划'项目PHR(IHLB)

摘　　要：为了克服传统距离法在构建进化树时需要进行多序列比对所带来的计算复杂度问题,提出了利用两两序列之间的归一化编辑距离矩阵来构造进化树的方法.通过对11种脊椎动物和20种哺乳动物的Nd5、Nd4和cytb的基因序列以及线粒体全基因组序列数据,分别计算归一化编辑距离矩阵,并使用Neighbor-Joining法,重建了一些已被多种方法验证过的进化树。In order to conquer the computational complexity problem caused by multiple sequence alignment in traditional distance methods, this paper presents a new tree-construction method, which uses a normalized edit distance matrix between pairs of sequences and the Neighbor-Joining algorithm to construct phylogenetic trees Using sequences of Nd5, Nd4, Cytb and mtDNA respectively from 11 vertebrate species and 20 mammalian species, the method can successfully generate consistent phylogenetic trees with those which have been examined by several other approaches.

关 键 词：归一化编辑距离 系统进化树 多序列比对 计算复杂性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]