loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
On the Complexity of uSPR Distance
July-September 2010 (vol. 7 no. 3)
pp. 572-576
ASCII Text
x 
 
Maria Luisa Bonet, Katherine St. John, "On the Complexity of uSPR Distance," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 7, no. 3, pp. 572-576, July-September, 2010.
 
 
BibTex
x
 
@article{ 10.1109/TCBB.2008.132,
author = {Maria Luisa Bonet and Katherine St. John},
title = {On the Complexity of uSPR Distance},
journal ={IEEE/ACM Transactions on Computational Biology and Bioinformatics},
volume = {7},
number = {3},
issn = {1545-5963},
year = {2010},
pages = {572-576},
doi = {http://doi.ieeecomputersociety.org/10.1109/TCBB.2008.132},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics
TI - On the Complexity of uSPR Distance
IS - 3
SN - 1545-5963
SP572
EP576
EPD - 572-576
A1 - Maria Luisa Bonet,
A1 - Katherine St. John,
PY - 2010
KW - Phylogeny
KW - analysis of algorithms
KW - fixed parameter tractability.
VL - 7
JA - IEEE/ACM Transactions on Computational Biology and Bioinformatics
ER -
 
Maria Luisa Bonet, Universitat Politècnica de Catalunya (UPC), Barcelona
Katherine St. John, City University of New York (CUNY), Bronx
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 [9] on the preservation of uSPR distance under chain reduction, improving on lower bounds of Hickey et al. [7].

[1] B.L. Allen and M. Steel, "Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees," Annals of Combinatorics, vol. 5, no. 1, pp. 1-15, 2001.
[2] M.L. Bonet, K.St. John, R. Mahindru, and N. Amenta, "Approximating Subtree Distances between Phylogenies," J. Computational Biology, vol. 13, no. 8, pp. 1419-1434, 2006.
[3] M. Bordewich, C. McCartin, and C. Semple, "A 3-Approximation Algorithm for the Subtree Distance between Phylogenies," J. Discrete Algorithms, vol. 6, no. 3, pp. 458-471, 2008.
[4] M. Bordewich and C. Semple, "On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance," Annals of Combintorics, vol. 8, pp. 409-423, 2004.
[5] M. Hallett and C. McCartin, "A Faster FPT Algorithm for the Maximum Agreement Forest Problem," Theory of Computing Systems, vol. 41, no. 3, pp. 539-550, 2007.
[6] J. Hein, T. Jiang, L. Wang, and K. Zhang, "On the Complexity of Comparing Evolutionary Trees," Discrete Applied Math., vol. 71, nos. 1-3, pp. 153-169, 1996.
[7] G. Hickey, F. Dehne, A. Rau-Chaplin, and C. Blouin, "SPR Distance Computation for Unrooted Trees," Evolutionary Bioinformatics, vol. 4, pp. 17-27, 2008.
[8] C. McCartin, personal comm., 2008.
[9] M. Steel, "SPR Conjecture," www.math.canterbury.ac.nz/~m.steel/ research reward2.pdf, 2002.
[10] D.L. Swofford, G.J. Olsen, P.J. Waddell, and D.M. Hillis, "Phylogenetic Inference," Molecular Systematics, second ed., pp. 407-514, Sinauer, 1996.

Index Terms:
Phylogeny, analysis of algorithms, fixed parameter tractability.
Citation:
Maria Luisa Bonet, Katherine St. John, "On the Complexity of uSPR Distance," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 7, no. 3, pp. 572-576, July-Sept. 2010, doi:10.1109/TCBB.2008.132
Usage of this product signifies your acceptance of the Terms of Use.