中文摘要：

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

英文摘要：

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.