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 Neiiquests algorithm (SN) and Studier and Kepler´s algorithm (SK). 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.4 GHz, RAM: 256 MB and OS: Windows 2000 Professional).