Calculating the Unrooted Subtree Prune-and-Regraft Distance.

Research paper by Chris C Whidden, Frederick F Matsen

Indexed on: 12 Jul '18Published on: 12 Jul '18Published in: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM


The subtree prune-and-regraft (SPR) distance metric is a fundamental way of comparing evolutionary trees. It has wide-ranging applications, such as to study lateral genetic transfer, viral recombination, and Markov chain Monte Carlo phylogenetic inference. Although the rooted version of SPR distance can be computed relatively efficiently between rooted trees using fixed-parameter-tractable maximum agreement forest (MAF) algorithms, no MAF formulation is known for the unrooted case. Correspondingly, previous algorithms are unable to compute unrooted SPR distances larger than 7.