SPR Distance Computation for Unrooted Trees

• DOI: 10.4137/ebo.s419
• Publication Date: 2017-11-09T10:59:42Z
• Authors: Glenn Hickey; Frank Dehne; Andrew Rau-Chaplin; Christian Blouin
• Keywords: Benchmark (surveying); Tree (set theory)

The subtree prune and regraft distance ( d SPR ) between phylogenetic trees is important both as a general means of comparing tree topologies well measure lateral gene transfer (LGT). Although there has been extensive study on the computation similar metrics rooted trees, much less known about distances for unrooted which often arise in practice when root unresolved. We show that NP-Hard verify techniques from related work can cannot be applied. then present an efficient heuristic algorithm this problem benchmark it variety synthetic datasets. Our computes exact tree, element only with respect to algorithm's time. method version fixed parameter tractability (FPT) approach our experiments indicate running time behaves FPT algorithms. For real data sets, was able quickly compute majority were part LGT 144 prokaryotic genomes. analysis its performance, especially searching reduction rules, applicable computing many measures.