Proposals for the tree

The tree topology is perturbed every ten cycles with either the nearest neighbor interchange (NNI) proposal shown in figure 2.7 or the subtree pruning and re-grafting (SPR) proposal (Swofford et al., 1996) shown in figure 2.8.

Figure 2.7: The nearest neighbor interchange algorithm (Jow et al., 2002)

Figure 2.8: The subtree pruning and regrafting algorithm (Jow et al., 2002)

Each cycle a randomly chosen branch length is modified with a figure $\delta$ drawn from a normal distribution centred at zero. When the branch length becomes negative special rules which can lead to a topology change are applied (Jow et al., 2002). If the branch is an internal branch then one of the two nearest neighbor topologies is proposed with each having equal probability; this is the Nearest Neighbour Interchange described above. The new internal branch length is set to $y = \vert x+\delta\vert$ (see figure  2.9). If the branch is a terminal branch, we cannot apply the NNI algorithm and we simply use a reflecting boundary. The new proposed length is $y = \vert x+\delta\vert$.

Figure 2.9: The continuous change algorithm when $x+\delta < 0$ (Jow et al., 2002)

The acceptance rate for the SPR and the NNI proposals are usually quite low. The ``local'' NNI proposal, induced by a branch length modification, has a better acceptance rate.