On the complexity of uSPR distance.
We show that subtree prune and regraft (uSPR) distance on unrooted trees is fixed parameter tractable with respect to the distance. We also make progress on a conjecture of Steel on the preservation of uSPR distance under chain reduction, improving on lower bounds of Hickey et al.
Bonet
Maria Luisa
ML
Lenguajes y Sistemas Informaticos, Universitat Politècnica de Catalunya (UPC), Barcelona, Spain. bonet@lsi.upc.edu
St John
Katherine
K
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D019143:Evolution, Molecular; D008957:Models, Genetic; D008962:Models, Theoretical; D010802:Phylogeny