On the Complexity of uSPR Distance

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Maria Luisa Bonet Articles by Katherine St. John

PrePrint

ISSN: 1545-5963

	ASCII Text	x
	Maria Luisa Bonet, Katherine St. John, "On the Complexity of uSPR Distance," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 99, no. 1, pp. , , 5555.

	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 = {99}, number = {1}, issn = {1545-5963}, year = {5555}, 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 - 1 SN - 1545-5963 SP EP EPD - A1 - Maria Luisa Bonet, A1 - Katherine St. John, PY - 5555 KW - phylogeny KW - analysis of algorithms KW - fixed parameter tractability VL - 99 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, Bronx

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TCBB.2008.132

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.

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, 02 Dec. 2008. IEEE computer Society Digital Library. IEEE Computer Society, <http://doi.ieeecomputersociety.org/10.1109/TCBB.2008.132>

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.