Author
Atkins, R
McDiarmid, C
Journal title
ANNALS OF COMBINATORICS
DOI
10.1007/s00026-018-0410-4
Issue
1
Volume
23
Last updated
2021-11-12T07:53:24.4+00:00
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
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000460682200001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=4fd6f7d59a501f9b8bac2be37914c43e
Publication type
Journal Article
Publication date
March 2019
Please contact us with feedback and comments about this page. Created on 13 Oct 2016 - 17:14.