Computing SPR Distances for Unrooted Trees
Author Information
Author(s): Glenn Hickey, Frank Dehne, Andew Rau-Chaplin, Christian Blouin
Primary Institution: Carleton University
Hypothesis
Can we efficiently compute the subtree prune and regraft (SPR) distance for unrooted phylogenetic trees?
Conclusion
The study presents an efficient heuristic algorithm for computing the SPR distance between unrooted trees, demonstrating its NP-Hardness and effectiveness on real datasets.
Supporting Evidence
- The algorithm computes the exact SPR distance for the majority of trees in a study of lateral gene transfer.
- The study shows that unrooted SPR distance computation is NP-Hard.
- Experiments indicate that the running time behaves similarly to fixed parameter tractability algorithms.
Takeaway
This study helps scientists compare the evolutionary histories of different genes by calculating how many changes occurred between tree structures, even when the trees don't have a clear starting point.
Methodology
The authors developed a heuristic algorithm to compute the SPR distance and benchmarked it on synthetic datasets and real data from prokaryotic genomes.
Limitations
The algorithm's performance may vary based on the structure of the trees and the presence of common subtrees.
Participant Demographics
The study analyzed trees from 144 sequenced prokaryotic genomes.
Want to read the original?
Access the complete publication on the publisher's website