东南大学学报（英文版）2006，Vol.22Issue(2)：176-179,4.
创建neighbor-joining进化树的快速算法
Fast algorithm for constructing neighbor-joining phylogenetic trees
摘要
Abstract
To improve the performance of Saitou and Nei's algorithm (SN) and Studier and Keppler's improved algorithm (SK) for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computation, a fast algorithm is proposed. The proposed algorithm includes three techniques. First, a linear array A[N] is introduced to store the sum of every row of the distance matrix (the same as SK), which can eliminate many repeated computations. Secondly, the value of A [i] is computed only once at the beginning of the algorithm, and is updated by three elements in the iteration. Thirdly, a very compact formula for the sum of all the branch lengths of operational taxonomic units (OTUs) i and j is designed, and the correctness of the formula is proved. The experimental results show that the proposed algorithm is from tens to hundreds times faster than SN and roughly two times faster than SK when N increases, constructing a tree with 2 000 OTUs in 3 min on a current desktop computer. To earn the time with the cost of the space and reduce the computations in the innermost loop are the basic solutions for algorithms with many loops.关键词
进化树/邻接法/快速算法/进化多序列比对Key words
phylogenetic tree/neighbor-joining method/fast algorithm/progressive multiple alignment分类
信息技术与安全科学引用本文复制引用
陈宁涛,王能超,施保昌..创建neighbor-joining进化树的快速算法[J].东南大学学报（英文版）,2006,22(2):176-179,4.基金项目
The National Natural Science Foundation of China(No. 60473015). （No. 60473015）
