TY - GEN
T1 - Faster Exact Computation of rSPR Distance
AU - Chen, Zhi-Zhong
AU - Wang, Lusheng
PY - 2013/6
Y1 - 2013/6
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 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.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 can be significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, Whidden et al.'s 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 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.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 can be significantly faster than the newest version (namely, v1.1.1) of the previously best software (namely, Whidden et al.'s RSPR) for rSPR distance.
KW - fixed-parameter algorithm
KW - Phylogenetic tree
KW - rSPR distance
UR - http://www.scopus.com/inward/record.url?scp=84884864035&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84884864035&origin=recordpage
U2 - 10.1007/978-3-642-38756-2_7
DO - 10.1007/978-3-642-38756-2_7
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783642387555
T3 - Lecture Notes in Computer Science
SP - 36
EP - 47
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
A2 - Fellows, Michael
A2 - Tan, Xuehou
A2 - Zhu, Binhai
T2 - 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management (FAW-AAIM 2013)
Y2 - 26 June 2013 through 28 June 2013
ER -