Subtree transfer operations and their induced metrics on evolutionary trees (Q5939205)

This interesting paper systematically studies three important local rearrangement processes of subtrees of evolutionary trees to determine their relationships, furthermore to investigate their combinatorial complexity. The three operations are: nearest neighbor interchange (NNI), subtree prune and regraft (SPR), tree bisection and reconnection (TBR). It is clear that NNI is a special form of SPR, and, similarly, SPR is a special form of TBR. The paper determines the size of the different neighborhoods of a tree under these operations and establishes bounds among the respective metrics. It also studies the maximum agreement forests. Finally it shows that the TBR-distance problem in general is NP-hard.