Efficiently Inferring Pairwise Subtree Prune-and-Regraft Adjacencies between Phylogenetic Trees

Chris Whidden, Frederick A. Matsen

We develop a time-optimal $O(m{n}^2)$-time algorithm to construct the subtree prune-regraft (SPR) graph on a collection of m phylogenetic trees with n leaves. This improves on the pr…