BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data - PubMed

BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data

O Gascuel. Mol Biol Evol. 1997 Jul.

Abstract

We propose an improved version of the neighbor-joining (NJ) algorithm of Saitou and Nei. This new algorithm, BIONJ, follows the same agglomerative scheme as NJ, which consists of iteratively picking a pair of taxa, creating a new mode which represents the cluster of these taxa, and reducing the distance matrix by replacing both taxa by this node. Moreover, BIONJ uses a simple first-order model of the variances and covariances of evolutionary distance estimates. This model is well adapted when these estimates are obtained from aligned sequences. At each step it permits the selection, from the class of admissible reductions, of the reduction which minimizes the variance of the new distance matrix. In this way, we obtain better estimates to choose the pair of taxa to be agglomerated during the next steps. Moreover, in comparison with NJ's estimates, these estimates become better and better as the algorithm proceeds. BIONJ retains the good properties of NJ--especially its low run time. Computer simulations have been performed with 12-taxon model trees to determine BIONJ's efficiency. When the substitution rates are low (maximum pairwise divergence approximately 0.1 substitutions per site) or when they are constant among lineages, BIONJ is only slightly better than NJ. When the substitution rates are higher and vary among lineages,BIONJ clearly has better topological accuracy. In the latter case, for the model trees and the conditions of evolution tested, the topological error reduction is on the average around 20%. With highly-varying-rate trees and with high substitution rates (maximum pairwise divergence approximately 1.0 substitutions per site), the error reduction may even rise above 50%, while the probability of finding the correct tree may be augmented by as much as 15%.

Similar articles

• Fast NJ-like algorithms to deal with incomplete distance matrices.

  Criscuolo A, Gascuel O. Criscuolo A, et al. BMC Bioinformatics. 2008 Mar 26;9:166. doi: 10.1186/1471-2105-9-166. BMC Bioinformatics. 2008. PMID: 18366787 Free PMC article.

• Improvement of distance-based phylogenetic methods by a local maximum likelihood approach using triplets.

  Ranwez V, Gascuel O. Ranwez V, et al. Mol Biol Evol. 2002 Nov;19(11):1952-63. doi: 10.1093/oxfordjournals.molbev.a004019. Mol Biol Evol. 2002. PMID: 12411604

• Getting a tree fast: Neighbor Joining, FastME, and distance-based methods.

  Desper R, Gascuel O. Desper R, et al. Curr Protoc Bioinformatics. 2006 Oct;Chapter 6:Unit 6.3. doi: 10.1002/0471250953.bi0603s15. Curr Protoc Bioinformatics. 2006. PMID: 18428768

• A stepwise algorithm for finding minimum evolution trees.

  Kumar S. Kumar S. Mol Biol Evol. 1996 Apr;13(4):584-93. doi: 10.1093/oxfordjournals.molbev.a025618. Mol Biol Evol. 1996. PMID: 8882501

• Neighbor-joining revealed.

  Gascuel O, Steel M. Gascuel O, et al. Mol Biol Evol. 2006 Nov;23(11):1997-2000. doi: 10.1093/molbev/msl072. Epub 2006 Jul 28. Mol Biol Evol. 2006. PMID: 16877499 Review.

Cited by

• Harnessing machine learning to guide phylogenetic-tree search algorithms.

  Azouri D, Abadi S, Mansour Y, Mayrose I, Pupko T. Azouri D, et al. Nat Commun. 2021 Mar 31;12(1):1983. doi: 10.1038/s41467-021-22073-8. Nat Commun. 2021. PMID: 33790270 Free PMC article.

• Intracellular amorphous Ca-carbonate and magnetite biomineralization by a magnetotactic bacterium affiliated to the Alphaproteobacteria.

  Monteil CL, Benzerara K, Menguy N, Bidaud CC, Michot-Achdjian E, Bolzoni R, Mathon FP, Coutaud M, Alonso B, Garau C, Jézéquel D, Viollier E, Ginet N, Floriani M, Swaraj S, Sachse M, Busigny V, Duprat E, Guyot F, Lefevre CT. Monteil CL, et al. ISME J. 2021 Jan;15(1):1-18. doi: 10.1038/s41396-020-00747-3. Epub 2020 Aug 24. ISME J. 2021. PMID: 32839547 Free PMC article.

• Whole genome sequence analysis of equid gammaherpesvirus -2 field isolates reveals high levels of genomic diversity and recombination.

  Onasanya AE, El-Hage C, Diaz-Méndez A, Vaz PK, Legione AR, Browning GF, Devlin JM, Hartley CA. Onasanya AE, et al. BMC Genomics. 2022 Aug 30;23(1):622. doi: 10.1186/s12864-022-08789-x. BMC Genomics. 2022. PMID: 36042397 Free PMC article.

• Strain Structure and Dynamics Revealed by Targeted Deep Sequencing of the Honey Bee Gut Microbiome.

  Bobay LM, Wissel EF, Raymann K. Bobay LM, et al. mSphere. 2020 Aug 26;5(4):e00694-20. doi: 10.1128/mSphere.00694-20. mSphere. 2020. PMID: 32848005 Free PMC article.

• Characterization of the calcium binding protein family in zebrafish.

  Di Donato V, Auer TO, Duroure K, Del Bene F. Di Donato V, et al. PLoS One. 2013;8(1):e53299. doi: 10.1371/journal.pone.0053299. Epub 2013 Jan 16. PLoS One. 2013. PMID: 23341937 Free PMC article.

MeSH terms

LinkOut - more resources

• Full Text Sources

  • Silverchair Information Systems

• Other Literature Sources

  • The Lens - Patent Citations Database