On the complexity of uSPR distance

IEEE/ACM Trans Comput Biol Bioinform. 2010 Jul-Sep;7(3):572-6. doi: 10.1109/TCBB.2008.132.

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.

Publication types

  • Research Support, Non-U.S. Gov't
  • Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

  • Algorithms
  • Computational Biology / methods*
  • Evolution, Molecular
  • Models, Genetic
  • Models, Theoretical
  • Phylogeny*