Faster exact computation of rSPR distance

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

11 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)605-635
Journal / PublicationJournal of Combinatorial Optimization
Volume29
Issue number3
Online published8 Dec 2013
Publication statusPublished - Apr 2015

Abstract

Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose, and many algorithms and software tools have been developed for computing the rSPR distance of two given phylogenetic trees. The previously fastest exact algorithm for this problem runs in (2.415dn) time, where n and d are the number of leaves and the rSPR distance of the input trees, respectively. In this paper, we present a faster exact algorithm which runs in O (2.344dn) time. Our experiments show that the new algorithm is significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, rSPR) for RSPR distance.

Research Area(s)

  • Fixed-parameter algorithm, Phylogenetic tree, rSPR distance

Citation Format(s)

Faster exact computation of rSPR distance. / Chen, Zhi-Zhong; Fan, Ying; Wang, Lusheng.

In: Journal of Combinatorial Optimization, Vol. 29, No. 3, 04.2015, p. 605-635.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review