The Computational Complexity of the Unrooted Subtree Prune and Regraft Distance

Authors: 

Glenn Hickey
Frank Dehne
Andrew Rau-Chaplin
Christian Blouin

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2

Abstract: 

We show that computation of the subtree prune and regraft (SPR) distance between unrooted binary phylogenetic trees is NP-Hard and fixed parameter tractable. Similar results exist for the related tree bisection and reconnection (TBR) distance, as well as the SPR distance between rooted trees but the complexity of the unrooted SPR case has heretofore remained unknown.

Tech Report Number: 
CS-2006-06
Report Date: 
July 21, 2006
AttachmentSize
PDF icon CS-2006-06.pdf467.2 KB