BIONJ
BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data. 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%. (http://mbe.oxfordjournals.org/content/14/7/685.short)
Keywords for this software
References in zbMATH (referenced in 26 articles )
Showing results 1 to 20 of 26.
Sorted by year (- Damti, Yanir; Gronau, Ilan; Moran, Shlomo; Yavneh, Irad: Comparing evolutionary distances via adaptive distance functions (2018)
- Davidson, Ruth; Rusinko, Joseph; Vernon, Zoe; Xi, Jing: Modeling the distribution of distance data in Euclidean space (2017)
- Drellich, Elizabeth; Gainer-Dewar, Andrew; Harrington, Heather A.; He, Qijun; Heitsch, Christine; Poznanović, Svetlana: Geometric combinatorics and computational molecular biology: branching polytopes for RNA sequences (2017)
- Keith, Jonathan M. (ed.): Bioinformatics. Volume I. Data, sequence analysis, and evolution (2017)
- Layer, Mark; Rhodes, John A.: Phylogenetic trees and Euclidean embeddings (2017)
- Bordewich, Magnus; Semple, Charles: Determining phylogenetic networks from inter-taxa distances (2016)
- Bordewich, M.; Tokac, N.: An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances (2016)
- Gascuel, Olivier; Steel, Mike: A `stochastic safety radius’ for distance-based tree reconstruction (2016)
- Saini, Ashish; Hou, Jingyu: Progressive clustering based method for protein function prediction (2013)
- Paradis, Emmanuel: Analysis of phylogenetics and evolution with R (2012)
- Cilibrasi, Rudi L.; Vitányi, Paul M. B.: A fast quartet tree heuristic for hierarchical clustering (2011)
- Gilks, Walter R.; Nye, Tom M. W.; Lio, Pietro: A variance-components model for distance-matrix phylogenetic reconstruction (2011)
- Levy, Dan; Pachter, Lior: The neighbor-net algorithm (2011)
- Ionescu, Tudor B.; Polaillon, Géraldine; Boulanger, Frédéric: Minimum tree cost quartet puzzling (2010)
- Brazil, M.; Thomas, D. A.; Nielsen, B. K.; Winter, P.; Wulff-Nilsen, C.; Zachariasen, M.: A novel approach to phylogenetic trees: (d)-dimensional geometric Steiner trees (2009)
- Catanzaro, Daniele: The minimum evolution problem: overview and classification (2009)
- Grünewald, S.; Moulton, V.; Spillner, A.: Consistency of the QNet algorithm for generating planar split networks from weighted quartets (2009)
- Mihaescu, Radu; Levy, Dan; Pachter, Lior: Why neighbor-joining works (2009)
- Sánchez, Robersy; Grau, Ricardo: An algebraic hypothesis about the primeval genetic code architecture (2009)
- Angelelli, Jean-Baptiste; Baudot, Anaïs; Brun, Christine; Guénoche, Alain: Two local dissimilarity measures for weighted graphs with application to protein interaction networks (2008)