TY - JOUR
T1 - Faster Exact Computation of rSPR Distance via Better Approximation
AU - Chen, Zhi-Zhong
AU - Harada, Youta
AU - Nakamura, Yuna
AU - Wang, Lusheng
PY - 2020/5
Y1 - 2020/5
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. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. Accordingly, a number of programs have been developed for solving the problem either exactly or approximately. In this paper, we develop two new programs one of which solves the problem exactly and outperforms the previous best (namely, Whidden et al.'s rSPR-v1.3.0) significantly, while the other solves the problem approximately and outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best due to Schalekamp et al. Our programs can be downloaded at http://rnc.r.dendai.ac.jp/rspr.html.
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. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. Accordingly, a number of programs have been developed for solving the problem either exactly or approximately. In this paper, we develop two new programs one of which solves the problem exactly and outperforms the previous best (namely, Whidden et al.'s rSPR-v1.3.0) significantly, while the other solves the problem approximately and outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best due to Schalekamp et al. Our programs can be downloaded at http://rnc.r.dendai.ac.jp/rspr.html.
KW - Approximation Algorithm
KW - Approximation algorithms
KW - fixed-parameter algorithm
KW - Forestry
KW - Java
KW - Phylogenetic tree
KW - Phylogeny
KW - rSPR distance
KW - Software
KW - Upper bound
KW - Vegetation
UR - http://www.scopus.com/inward/record.url?scp=85055895844&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85055895844&origin=recordpage
U2 - 10.1109/TCBB.2018.2878731
DO - 10.1109/TCBB.2018.2878731
M3 - 21_Publication in refereed journal
VL - 17
SP - 916
EP - 929
JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics
JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics
SN - 1545-5963
IS - 3
ER -