Alan Joseph J. Caceres
Abstract
A nearest-neighbor-interchange (NNI)-walk is a sequence of unrooted phylogenetic trees, $(T_1, T_2, \ldots, T_k)$ where each consecutive pair of trees differs by a single NNI move. We give tight bounds on the length of the shortest NNI-walks that visit all trees in a subtree-prune-and-regraft (SPR) neighborhood of a given tree. For any unrooted, binary tree, $(T)$, on $(n)$ leaves, the shortest walk takes $(\Theta (n^2))$ additional steps more than the number of trees in the SPR neighborhood. This answers Bryant's Second Combinatorial Challenge from the Phylogenetics Challenges List, the Isaac Newton Institute, 2011, and the Penny Ante Problem List, 2009.
- B. Allen and M. Steel, "Subtree Transfer Operations and their Induced Metrics on Evolutionary Trees," Ann. Combinatorics, vol. 5, pp. 1-13, 2001.Google Scholar
Cross Ref
- M.L. Bonet, K.St. John, R. Mahindru, and N. Amenta, "Approximating Subtree Distances between Phylogenies," J. Computational Biology, vol. 13, no. 8, pp. 1419-1434, 2006.Google ScholarCross Ref
- M. Bordewich, C. McCartin, and C. Semple, "A 3-Approximation Algorithm for the Subtree Distance between Phylogenies," J. Discrete Algorithms, vol. 6, no. 3, pp. 458-471, 2008. Google ScholarDigital Library
- M. Bordewich and C. Semple, "On the Computational Complexity of the Rooted Suaft Distance," Ann. Combinatorics, vol. 8, pp. 409-423, 2004.Google ScholarCross Ref
- D. Bryant, "Annual New Zealand Phylogenetics Meeting (Kaikoura 2009) Penny Ante prize problems: A Mathematical Challenge," http:// www.math.canterbury.ac.nz/bio/events/kaikoura09/penny.shtml, 2009.Google Scholar
- D. Bryant, personal communication, 2012.Google Scholar
- A.J.J Caceres, S. Daley, J. DeJesus, M. Hintze, D. Moore, and K. St. John, "Walks in Phylogenetic Treespace," Information Processing Letters, vol. 111, pp. 600-604, 2011. Google ScholarDigital Library
- B. DasGupta, X. He, T. Jiang, M. Li, J. Tromp, and L. Zhang, "On Computing the Nearest Neighbor Interchange Distance," Proc. Workshop Discrete Problems with Medical Applications vol. 55, pp. 125-143, 2000.Google ScholarCross Ref
- L.R. Foulds and R.L. Graham, "The Steiner Problem in Phylogeny is NPComplete," Advances in Applied Math., vol. 3, no. 1, pp. 43-49, 1982.Google ScholarDigital Library
- P.A. Goloboff, J.S. Farris, and K.C. Nixon, "TNT, a Free Program for Phylogenetic Analysis," Cladistics, vol. 24, pp. 774-786, 2008.Google ScholarCross Ref
- G. Hickey, F. Dehne, A. Rau-Chaplin, and C. Blouin, "SPR Distance Computation for Unrooted Trees," Evolutionary Bioinformatics, vol. 4, pp. 17-27, 2008.Google ScholarCross Ref
- D.M. Hillis, B.K. Mable, and C. Moritz, Molecular Systematics. Sinauer Assoc., 1996.Google Scholar
- J.P. Huelsenbeck and F. Ronquist, "MrBayes: Bayesian Inference of Phylogeny," Bioinformatics, vol. 17, no. 8, pp. 754-755, 2001.Google ScholarCross Ref
- M. Li, J. Tromp, and L. Zhang, "Some Notes on the Nearest Neighbour Interchange Distance," Proc. Second Ann. Int'l Conf. Computing and Combinatorics (COCOON '96), pp. 343-351, 1996. Google ScholarDigital Library
- S. Roch, "A Short Proof that Phylogenetic Tree Reconstruction by Maximum Likelihood is Hard," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 3, no. 1, pp. 92-94, Jan. 2006. Google ScholarDigital Library
- C. Semple and M. Steel, Phylogenetics, Oxford Lecture Series in Mathematics and Its Applications, vol. 24, Oxford Univ. Press, 2003.Google Scholar
- M. Steel, "Challenges and Conjectures: ISAAC Newton Institute Phylogenetics Program 2011," http://www.newton.ac.uk/programmes/PLG/ phylogenetics_challenges.pdf, 2012.Google Scholar
- D.L. Swofford, PAUP*. Phylogenetic Analysis Using Parsimony (*and Other Methods), Version 4. Sinauer Assoc., 2002.Google Scholar
- S. Whelan, "New Approaches to Phylogenetic Tree Search and Their Application to Large Numbers of Protein Alignments." Systematic Biology, vol. 56, no. 5, pp. 727-740, 2007.Google ScholarCross Ref
Index Terms
- Walks on SPR Neighborhoods
Recommendations
Computing the Distribution of a Tree Metric
The Robinson-Foulds (RF) distance is by far the most widely used measure of dissimilarity between trees. Although the distribution of these distances has been investigated for 20 years, an algorithm that is explicitly polynomial time has yet to be ...
Seeded Tree Alignment
The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in ...
A Fast Algorithm for Computing Geodesic Distances in Tree Space
Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length ...
Comments