A practical method for exact computation of subtree prune and regraft distance

Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR ((r)SPR) operations needed to transform one rooted binary tree to another is called the (r)SPR distance between the two trees. Computing the (r)SPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the (r)SPR distance for relatively large trees with large (r)SPR distance.