# zbMATH — the first resource for mathematics

Extremal distances for subtree transfer operations in binary trees. (English) Zbl 1414.05074
Summary: Three standard subtree transfer operations for binary trees, used in particular for phylogenetic trees, are: tree bisection and reconnection (TBR), subtree prune and regraft (SPR), and rooted subtree prune and regraft (rSPR). We show that for a pair of leaf-labelled binary trees with $$n$$ leaves, the maximum number of such moves required to transform one into the other is $$n-\Theta (\sqrt{n})$$, extending a result of Y. Ding et al. [J. Comb. Theory, Ser. A 118, No. 7, 2059–2065 (2011; Zbl 1231.05072)], and this holds also if one of the trees is fixed arbitrarily. If the pair is chosen uniformly at random, then the expected number of moves required is $$n-\Theta (n^{2/3})$$. These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees.

##### MSC:
 05C05 Trees 05C12 Distance in graphs 05C35 Extremal problems in graph theory 05C76 Graph operations (line graphs, products, etc.) 92D15 Problems related to evolution
Full Text:
##### References:
  Aldous, D.: Probability distributions on cladograms. In: Aldous, D., Pemantle, R. (eds.) Random Discrete Structures, IMA Vol. Math. Appl., Vol. 76, 1-18. Springer, New York (1996) · Zbl 0841.92015  Allen, B., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Combin. 5(1), 1-15 (2001) · Zbl 0978.05023  Bernstein, D.I., Ho, L.S.T., Long, C., Steel, M., St. John, K., Sullivant, S.: Bounds on the expected size of the maximum agreement subtree. SIAM J. Discrete Math. 29(4), 2065-2074 (2015) · Zbl 1323.05033  Bordewich, M.; Semple, C., On the computational complexity of the rooted subtree prune and regraft distance, Ann. Combin., 8, 409-423, (2005) · Zbl 1059.05035  Bryant, D., McKenzie, A., Steel, M.: The size of a maximum agreement subtree for random binary trees. In: Janowitz, M.F., Lapointe, F.-J., McMorris, F.R., Mirkin, B., Roberts, F.S. (eds.) BioConsensus, Discrete Math. Theoret. Comput. Sci., Vol. 61, 55-65. American Mathematical Society, Providence, RI (2003) · Zbl 1026.92030  Ding, Y., Grünewald, S., Humphries, P.J.: On agreement forests. J. Combin. Theory Ser. A 118(7), 2059-2065 (2011) · Zbl 1231.05072  Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, 463-470 (1935) · Zbl 0012.27010  Hein, J.: Reconstructing evolution of sequences subject to recombination using parsimony. Math. Biosci. 98(2), 185-200 (1990) · Zbl 0692.92014  Hein, J., Jiang, T., Wang, L., Zhang, K.: On the complexity of comparing evolutionary trees. Discrete Appl. Math. 71(1-3), 153-169 (1996) · Zbl 0876.92020  Humphreys, PJ; Semple, C., Note on the hybridization number and subtree distance in phylogenetics, App. Math. Lett., 22, 611-615, (2009) · Zbl 1162.92029  Martin, D.M., Thatte, B.D.: The maximum agreement subtree problem. Discreat Appl. Math. 161(13-14), 1805-1817 (2013) · Zbl 1286.05029  McDiarmid, C.: On the method of bounded differences. In: Siemons, J. (ed.) Surveys in Combinatorics, London Mathematical Society Lecture Note Series, Vol. 141, pp. 148-188. Cambridge University Press, Cambridge (1989) · Zbl 0712.05012  Penny, D., Steel, M.: Distributions of tree comparison metrics—some new results. Systematic Biol. 42(2), 126-141 (1993)  Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)  Zhu, S.; Steel, M., Does random tree puzzle produce Yule-Harding trees in the many-taxon limit?, Math. Biosci., 243, 109-116, (2013) · Zbl 1310.92040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.