TY  - JOUR
AU  - Shi, Feng
AU  - Feng, Qilong
AU  - Chen, Jianer
AU  - Wang, Lusheng
AU  - Wang, Jianxin
PY  - 2013
TI  - Distances Between Phylogenetic Trees: A Survey
JO  - Tsinghua Science and Technology
SN  - 1007-0214
SP  - 490
EP  - 499
VL  - 18
IS  - 5
AB  - Phylogenetic trees have been widely used in the study of evolutionary biology for representing the tree-like evolution of a collection of species. However, different data sets and different methods often lead to the construction of different phylogenetic trees for the same set of species. Therefore, comparing these trees to determine similarities or, equivalently, dissimilarities, becomes the fundamental issue. Typically, Tree Bisection and Reconnection (TBR) and Subtree Prune and Regraft (SPR) distances have been proposed to facilitate the comparison between different phylogenetic trees. In this paper, we give a survey on the aspects of computational complexity, fixed-parameter algorithms, and approximation algorithms for computing the TBR and SPR distances of phylogenetic trees.
UR  - https://doi.org/10.1109/TST.2013.6616522
DO  - 10.1109/TST.2013.6616522