TY - JOUR
T1 - Faster exact computation of rSPR distance
AU - Chen, Zhi-Zhong
AU - Fan, Ying
AU - Wang, Lusheng
PY - 2015/4
Y1 - 2015/4
N2 - 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.
AB - 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.
KW - Fixed-parameter algorithm
KW - Phylogenetic tree
KW - rSPR distance
UR - http://www.scopus.com/inward/record.url?scp=84924223362&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84924223362&origin=recordpage
U2 - 10.1007/s10878-013-9695-8
DO - 10.1007/s10878-013-9695-8
M3 - RGC 21 - Publication in refereed journal
SN - 1382-6905
VL - 29
SP - 605
EP - 635
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 3
ER -