Navigation Banner
 
  HyPhy Documentation: Standard Analyses: Methods: Subtree Pruning And Regrafting

    Subtree Pruning And Regrafting is a tree topology search strategy which attempts to improve the likelihood of a given tree by performing the following operations on the tree.
     First, select a subtree of the given tree. Next, we detach the selected subtree and attempt to regraft it onto another branch of the remaining tree, in such a way that a new tree is formed. For example, in the figures below, we select the subtree with leaves 1 and 2 from the original six leaf tree. That leaves us with a 4 leaf tree which has 5 branches. We regraft the (1,2) subtree to four of those (we omit one, because grafting the (1,2) subtree to it would result in the same tree that we started with) to obtain new trees. The procedure is usually repeated for each possible subtree and receiving branch, until no further likelihood improvements can be obtained.
     A single pass of the SPR algorithm examines $O(N^2)$ 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.

Figure 1.
Original Tree.
Figure 2.
Graft (1,2) onto 6.
Figure 3.
Graft (1,2) onto 5.
Figure 4.
Graft (1,2) onto
the internal branch
joining 5 and 6.
Figure 5.
Graft (1,2) onto 4.

 
Sergei L. Kosakovsky Pond and Spencer V. Muse, 1997-2002