zbMATH — the first resource for mathematics

Subtree transfer operations and their induced metrics on evolutionary trees. (English) Zbl 0978.05023
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.

05C05 Trees
92D15 Problems related to evolution
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI