[1] Chen Ningtao, Wang Nengchao, Shi Baochang,. Fast algorithm for constructing neighbor-joining phylogenetic trees [J]. Journal of Southeast University (English Edition), 2006, 22 (2): 176-179. [doi:10.3969/j.issn.1003-7985.2006.02.007]

Copy

Fast algorithm for constructing neighbor-joining phylogenetic trees()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

22

Issue:

2006 2

Page:

176-179

Research Field:

Computer Science and Engineering

Publishing date:

2006-06-30

Info

Title:

Fast algorithm for constructing neighbor-joining phylogenetic trees

Author(s):

Chen Ningtao¹;  Wang Nengchao²;  Shi Baochang²

¹ School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
² Parallel Computing Institute, Huazhong University of Science and Technology, Wuhan 430074, China

Keywords:

phylogenetic tree;  neighbor-joining method;  fast algorithm;  progressive multiple alignment

PACS:

TP301.6

DOI:

10.3969/j.issn.1003-7985.2006.02.007

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 inner-most loop are the basic solutions for algorithms with many loops.

References:

[1] Yang C, Khuri S.PTC:an interactive tool for phylogenetic tree construction [A]. In:IEEE Proceedings of the Com-putational Systems Bioinformatics[C].California:Stanford University, 2003, 8:476-477.
[2] Foulds L R, Graham R L.The sterner problem in phylogeny is NP-complete [J].Advances Appl Math, 1982, 3:43-49.
[3] Day W.Computational complexity of inferring phylogenies from dissimilarity matrices [J].Bull Math Biol, 1987, 49(4):461-467.
[4] Saitou N, Nei M.The neighbor-joining method:a new method for reconstructing phylogenetic trees [J].Mol Biol Evol, 1987, 4(4):406-425.
[5] Studier J A, Keppler K J.A note on the neighbor-joining algorithm of Saitou and Nei [J].Mol Biol Evol, 1988, 5(6):729-731.
[6] Saitou N, Imanishi T.Relative efficiencies of the Fitch-Margoliash, maximum-parsimony, maximum-likelihood, minimum-evolution, and neighbor-joining methods of phylogenetic tree construction in obtaining the correct tree [J].Mol Biol Evol, 1989, 6(5):514-525.
[7] Thompson J D, Higgins D G, Gibson T J.CLUSTAL W:improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice [J].Nucleic Acids Res, 1994, 22(22):4673-4680.
[8] Notredame C, Higgins D G, Heringa J.T-Coffee:a novel method for fast and accurate multiple sequence alignment [J].J Mol Biol, 2000, 302(1):205-217.
[9] Katoh K, Misawa K, Kuma K, et al.MAFFT:a novel method for rapid multiple sequence alignment based on fast Fourier transform [J].Nucleic Acids Res, 2002, 30(14):3059-3066.
[10] Edgar R C.MUSCLE:multiple sequence alignment with high accuracy and high throughput [J].Nucleic Acids Res, 2004, 32(5):1792-1797.
[11] Sneath P H A, Sokal R R.Numerical taxonomy [M].San Francisco:Freeman, 1973.
[12] Edgar R C.Local homology recognition and distance measures in linear time using compressed amino acid alphabets [J].Nucleic Acids Res, 2004, 32(1):380-385.

Memo

Memo:

Biographies: Chen Ningtao(1976—), male, graduate;Shi Baochang(corresponding author), male, doctor, professor, sbchust0382@sina.com.

Common functions