创建neighbor-joining进化树的快速算法(英文)

作     者：陈宁涛 王能超 施保昌 Chen Ningtao;Wang Nengchao;Shi Baochang

作者机构：华中科技大学计算机科学与技术学院武汉430074 华中科技大学并行计算研究所武汉430074 

基　　金：TheNationalNaturalScienceFoundationofChina(No.60473015) 

出 版 物：《Journal of Southeast University(English Edition)》 (东南大学学报（英文版）)

年 卷 期：2006年第22卷第2期

页      码：176-179页

摘      要：为了改善Saitou和Nei提出的neighbor-joining进化树算法(SN)及Studier和Keppler的改进算法(SK),降低计算的时间复杂度,设计了一种快速算法.该算法涉及3种技术第一,引入一个线性数组A[N],用于存储距离矩阵每一行的值,以减少许多重复计算;第二,A[i]的值在算法开始时全部计算,在迭代步中间只进行更新3个变化的值;第三,设计了一个紧凑的公式用于计算OTUs之间的边长,并对该公式进行了证明.实验结果表明随着节点数的增多,该算法比SN算法快几十倍到上百倍,比SK算法快2倍以上;在一台桌面计算机上,该算法能在3min左右创建具有2000个节点的进化树.以空间换时间,减少最内层循环的计算量是设计多重循环算法的基本思路.

主 题 词：进化树 邻接法 快速算法 进化多序列比对 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1003-7985.2006.02.007

馆 藏 号：203809030...