×

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
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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
[2] Allen, B., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Combin. 5(1), 1-15 (2001) · Zbl 0978.05023
[3] 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
[4] 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
[5] 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
[6] Ding, Y., Grünewald, S., Humphries, P.J.: On agreement forests. J. Combin. Theory Ser. A 118(7), 2059-2065 (2011) · Zbl 1231.05072
[7] Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, 463-470 (1935) · Zbl 0012.27010
[8] Hein, J.: Reconstructing evolution of sequences subject to recombination using parsimony. Math. Biosci. 98(2), 185-200 (1990) · Zbl 0692.92014
[9] 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
[10] Humphreys, PJ; Semple, C., Note on the hybridization number and subtree distance in phylogenetics, App. Math. Lett., 22, 611-615, (2009) · Zbl 1162.92029
[11] Martin, D.M., Thatte, B.D.: The maximum agreement subtree problem. Discreat Appl. Math. 161(13-14), 1805-1817 (2013) · Zbl 1286.05029
[12] 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
[13] Penny, D., Steel, M.: Distributions of tree comparison metrics—some new results. Systematic Biol. 42(2), 126-141 (1993)
[14] Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)
[15] 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.