Subtree transfer operations and their induced metrics on evolutionary trees. (English) Zbl 0978.05023

Allen, Benjamin L.; Steel, Mike

Ann. Comb. 5, No. 1, 1-15 (2001).

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.

Reviewer: Péter L.Erdős (Budapest)

MSC:

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

Keywords:

evolutionary trees; phylogeny; subtree rearrangements; combinatorial complexity