Constructing Neighbor-Joining phylogenetic trees with reduced redundancy computation

摘要

A fast algorithm for constructing Neighbor-Joining phylogenetic trees has been developed. The CPU time is drastically reduced as compared with Saitou and Nei??s algorithm (SN) [4] and Studier and Kepler??s algorithm (SK) [5]. The new algorithm includes three techniques: Firstly, 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 (redundancy) computations. Secondly, the value of A[i] are computed only once at the beginning of the algorithm, and are updated by three elements in the iteration. Thirdly, a very compact formula for the sum of all the branch lengths of OTUs (Operational Taxonomic Units) i and j has been designed. The results show that our algorithm is from tens to hundreds times faster than SN and about two times faster than SK when N increases, constructing the tree with 2000 OTUs in 3 minutes on our desktop computer (CPU: Intel Celeron 2.4GHz, RAM: 256MB and OS: Windows 2000 Professional).