Faster exact computation of rSPR distance
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 605-635 |
| Journal / Publication | Journal of Combinatorial Optimization |
| Volume | 29 |
| Issue number | 3 |
| Online published | 8 Dec 2013 |
| Publication status | Published - Apr 2015 |
Link(s)
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 O (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 journal › peer-review
