Title :
On the Complexity of uSPR Distance
Author :
Bonet, Maria Luisa ; John, Katherine St
Author_Institution :
Lenguajes y Sist. Informaticos (LSI), Univ. Politec. de Catalunya (UPC), Barcelona, Spain
Abstract :
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..
Keywords :
biology computing; botany; chain reduction; regraft; subtree prune; uSPR distance; unrooted trees; Phylogeny; analysis of algorithms; fixed parameter tractability; fixed parameter tractability.; phylogeny; Algorithms; Computational Biology; Evolution, Molecular; Models, Genetic; Models, Theoretical; Phylogeny;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2008.132
