创建neighbor-joining进化树的快速算法

• 作者: 施保昌 王能超 陈宁涛
• 来源期刊: 东南大学学报(英文版)
• 学科: 工学
• 关键词: 进化树 邻接法 快速算法 进化多序列比对
• 年，卷（期）: 2006,（2）
• 页码范围: 176-179
• 页数: 4页
• 分类号: TP3
• 字数: 660字
• 语种: 英文
• DOI: 10.3969/j.issn.1003-7985.2006.02.007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王能超	华中科技大学并行计算研究所	58	640	17.0	23.0
2	施保昌	华中科技大学并行计算研究所	60	509	12.0	19.0
3	陈宁涛	华中科技大学计算机科学与技术学院	6	74	4.0	6.0