"Distances Between Phylogenetic Trees: A Survey" by Feng Shi, Qilong Feng et al.

Home > TSINGHUA-SCIENCE-AND-TECHNOLOGY > Vol. 18 (2013) > Iss. 5

Article Title

Distances Between Phylogenetic Trees: A Survey

Authors

Feng Shi, School of Information Science and Engineering, Central South University, Changsha 410083, China
Qilong Feng, School of Information Science and Engineering, Central South University, Changsha 410083, China
Jianer Chen, School of Information Science and Engineering, Central South University, Changsha 410083, China Department of Computer Science and Engineering, Texas A&M University, College Station, Texas 77843-3112, USA
Lusheng Wang, Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong, China
Jianxin Wang, School of Information Science and Engineering, Central South University, Changsha 410083, China

Keywords

phylogenetic tree, tree bisection and reconnection, subtree prune and regraft, fixed-parameter algorithm, approximation algorithm

Abstract

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.