Distances Between Phylogenetic Trees: A Survey  

作　　者：Feng Shi Qilong Feng Jianer Chen Lusheng Wang Jianxin Wang 

机构地区：[1]School of Information Science and Engineering, Central South University [2]Department of Computer Science and Engineering, Texas A&M University, College Station [3]Department of Computer Science, City University of Hong Kong

出　　处：《Tsinghua Science and Technology》2013年第5期490-499,共10页清华大学学报（自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China (Nos.61103033,61173051, 61232001,and 70921001)

摘　　要：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.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.

关 键 词：phylogenetic tree tree bisection and reconnection subtree prune and regraft fixed-parameter algorithm approximation algorithm 

分 类 号：Q75[生物学—分子生物学] TP301.6[自动化与计算机技术—计算机系统结构]