Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference

ABSTRACT

Many phylogenetic algorithms search the space of possible trees using topological rearrangements and some optimality criterion. FastME is such an approach that uses the {\em balanced minimum evolution (BME)} principle, which computer studies have demonstrated to have high accuracy. FastME includes two variants: {\em balanced subtree prune and regraft (BSPR)} and {\em balanced nearest neighbor interchange (BNNI)}. These algorithms take as input a distance matrix and a putative phylogenetic tree. The tree is modified using SPR or NNI operations, respectively, to reduce the BME length relative to the distance matrix, until a tree with (locally) shortest BME length is found. Following computer simulations, it has been conjectured that BSPR and BNNI are consistent, i.e. for an input distance that is a tree-metric, they converge to the corresponding tree. We prove that the BSPR algorithm is consistent. Moreover, even if the input contains small errors relative to a tree-metric, we show that the BSPR algorithm still returns the corresponding tree. Whether BNNI is consistent remains open.

REFERENCES

• 1: B. Allen and M. Steel, "Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees," Annals of Combinatorics, vol. 5, pp. 1-13, 2001.
• 2: K. Atteson, "The Performance of the Neighbor-Joining Methods of Phylogenetic Reconstruction," Algorithmica, vol. 25, pp. 251-278, 1999.
• 3: W.J. Bruno, N.D. Socci, and A.L. Halpern, "Weighted Neighbor Joining: A Likelihood Based Approach to Distance-Based Phylogeny Reconstruction," Molecular Biology and Evolution, vol. 17, pp. 189-197, 2000.
• 4: D. Bryant, "The Splits in the Neighbourhood of a Tree," Annals of Combinatorics, vol. 8, pp. 1-11, 2004.
• 5: David Bryant , John Tsang , Paul Kearney , Ming Li, Computing the quartet distance between evolutionary trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.285-286, January 09-11, 2000, San Francisco, California, United States
• 6: R. Desper and O. Gascuel, "Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum Evolution Principle," J. Computational Biology, vol. 9, pp. 587-598, http:// atgc.lirmm.fr/fastme/, 2002.
• 7: R. Desper and O. Gascuel, "Theoretical Foundation of the Balanced Minimum Evolution Method of Phylogenetic Inference and Its Relationship to Weighted Least-Squares Tree Fitting," Molecular Biology and Evolution, vol. 21, pp. 587-598, 2004.
• 8: R. Desper and O. Gascuel, "The Minimum-Evolution Distance Based Approach to Phylogenetic Inference," Math. Evolution and Phylogeny, O. Gascuel, ed. Oxford Univ. Press, 2005.
• 9: R. Desper and O. Gascuel, "Distance-Based Phylogeny Reconstruction, (Optimal Radius; 1999, Atteson2005, Elias and Lagergren)," Encyclopedia of Algorithms, M.-Y. Kao, ed., chapter, pp. 1-99, Springer, 2008.
• 10: R. Desper, V. Lefort, H. Phan, and O. Gascuel, manuscript in preparation.
• 11: G.F. Estabrook, F.R. McMorris, and C.A. Meacham, "Comparison of Undirected Phylogenetic Trees Based on Subtrees of Four Evolutionary Units," Systematic Zoology, vol. 34, pp. 192-200, 1985.
• 12: J. Felsenstein, "PHYLIP--Phylogeny Inference Package (Version 3.2)," Cladistics, vol. 5, pp. 164-166, 1989.
• 13: J. Felsenstein, "An Alternating Least-Squares Approach to Inferring Phylogenies from Pairwise Distances," Systematic Biology , vol. 46, pp. 101-111, 1997.
• 14: J. Felsenstein, Inferring Phylogenies. Sinauer Assoc., Inc., 2004.
• 15: O. Gascuel, "BIONJ: An Improved Version of the NJ Algorithm Based on a Simple Model of Sequence Data," Molecular Biology and Evolution, vol. 14, pp. 685-695, 1997.
• 16: O. Gascuel and S. Guillemot, "Sur la Consistance et le Rayon de Sécurité du Principe d'Évolution Minimum," internal report in French (available on request), 2005.
• 17: Wim Hordijk , Olivier Gascuel, Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood, Bioinformatics, v.21 n.24, p.4338-4347, December 2005 [doi>10.1093/bioinformatics/bti713]
• 18: K.K. Kidd and L.A. Sgaramella-Zonta, "Phylogenetic Analysis: Concepts and Methods," Am. J. Human Genetics, vol. 23, pp. 235-252, 1971.
• 19: Thomas Mailund , Christian N. S. Pedersen, QDist---quartet distance between evolutionary trees, Bioinformatics, v.20 n.10, p.1636-1637, July 2004 [doi>10.1093/bioinformatics/bth097]
• 20: Y. Pauplin, "Direct Calculation of Tree Length Using a Distance Matrix," J. Molecular Evolution, vol. 51, pp. 66-85, 2000.
• 21: A. Rzhetsky and M. Nei, "Theoretical Foundation of the Minimum-Evolution Method of Phylogenetic Inference," Molecular Biology and Evolution, vol. 10, pp. 1073-1095, 1993.
• 22: D. Robinson and L. Foulds, "Comparison of Phylogenetic Trees," Math. Biosciences, vol. 53, pp. 131-147, 1981.
• 23: N. Saitou and M. Nei, "The Neighbor-Joining Method: A New Method for Reconstructing Phylogenetic Trees," Molecular Biology and Evolution, vol. 4, pp. 406-424, 1987.
• 24: P.H.A Sneath and R.R. Sokal, Numerical Taxonomy, pp. 230-234. W.K. Freeman, 1973.
• 25: C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
• 26: C. Semple and M. Steel, "Cyclic Permutations and Evolutionary Trees," Advances in Applied Math., vol. 32, pp. 669-680, 2004.
• 27: M. Steel and D. Penny, "Distributions of Tree Comparison Metrics--Some New Results," Systematic Biology, vol. 42, no. 2, pp. 126-141, 1993.
• 28: K. Strimmer and A. von Haeseler, "Quartet Puzzling: A Quartet Maximum Likelihood Method for Reconstructing Tree Topologies," Molecular Biology and Evolution, vol. 13, pp. 964-969, 1996.
• 29: D.L. Swofford, PAUP*, Phylogenetic Analysis Using Parsimony (* and Other Methods). Sinauer Assoc., Inc., 2003.
• 30: L.S. Vinh and A. von Haeseler, "Shortest Triplet Clustering: Reconstructing Large Phylogenies Using Representative Sets," BMC Bioinformatics, vol. 6, no. 92, pp. 1-14, 2005.
• 31: S.J. Willson, "Minimum Evolution Using Ordinary Least Squares Is Less Robust Than Neighbor-Joining," Bull. Math. Biology, vol. 67, pp. 261-279, 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Design, Performance

Keywords:
phylogenetic tree, subtree prune and regraft (SPR), BSPR algorithm, Nearest Neighbor Interchange (NNI), BNNI algorithm, balanced minimum evolution principle (BME), tree-length, quartet-distance, Robinson Foulds distance, consistency, safety radius, topological move