DocumentCode :
1027953
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
Volume :
7
Issue :
3
fYear :
2010
Firstpage :
572
Lastpage :
576
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;
fLanguage :
English
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1545-5963
Type :
jour
DOI :
10.1109/TCBB.2008.132
Filename :
4711039
Link To Document :
بازگشت