3. NEIGHBORHOOD STRUCTURESIn this s

3. NEIGHBORHOOD STRUCTURES
In this section the applied neighborhood structures Step,
Swap, Rotate, and SPRr are described. For the unrooted
case, a good overview of Step, Rotate, and the general SPR
is given in [2]. At rst we consider the neighborhoods dealing
with single taxa.
A Step move consists of removing a taxon with its predecessor
node and reinserting them at some other branch
in the tree or as new root, see Figure 3 for an example.
In a tree containing n taxa, there are always n