Extremal Distances for Subtree Transfer Operations in Binary Trees

Author: 

Atkins, R
McDiarmid, C

Publication Date: 

March 2019

Journal: 

ANNALS OF COMBINATORICS

Last Updated: 

2019-04-26T09:56:20.76+01:00

Issue: 

1

Volume: 

23

DOI: 

10.1007/s00026-018-0410-4

page: 

1-26

abstract: 

© 2018, The Author(s). 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-Θ(n), extending a result of Ding, Grünewald, and Humphries, 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- Θ (n2 / 3). These results may be phrased in terms of agreement forests: we also give extensions for more than two binary trees.

Symplectic id: 

544845

Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article