Subtree-Pruning-Regrafting (SPR)

For any tree searching method, exhaustive search, where all possible topologies are considered is unfeasible for even a small number of taxa. Subtree Pruning And Regrafting is a tree topology search heuristic which reduces the number of topologies searched by performing the following operations on the tree.
     First, a subtree of the current best tree is selected and detached (pruned). Second, the detached subtree is regrafted onto another branch of the remaining tree, in such a way that a new topology is created and then likelihood of the new topology is calculated. This procedure is repeated for all regrafting positions that produce new topologies using the pruned subtree. The procedure is also repeated for each subtree (within the designated search level) and if the topology with best likelihood among those scored gives sufficient improvement over the current best tree, that topology becomes the current best tree. This is repeated until no significant further likelihood improvements are obtained.
     A single pass of the SPR algorithm examines O(N2) new trees, where N is the number of leaves in the original tree. This is because, for each subtree there are O(N) possible regraftings, and there are O(N) possible subtrees to consider. In contrast, NNI examines O(N) topologies at each pass of the algorithm.