TY - GEN
T1 - Finding a Center Tree of Phylogenetic Trees via Leaf Removal
AU - Chen, Zhi-Zhong
AU - Ueta, Shohei
AU - Li, Jingyu
AU - Wang, Lusheng
PY - 2018/12
Y1 - 2018/12
N2 - Given a set T= {T1 T2,..., Tm } of phylogenetic trees with the same leaf-label set X, we wish to remove some leaves from the trees so that there is a tree T with leaf-label set X displaying all the resulting trees. Note that different leaves may be removed from different input trees. One objective is to minimize the total number of leaves removed from the trees, while the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. [2] refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d ), and show that both problems are NP-hard. They further present algorithms for the parameterized versions of both problems. In this paper, we point out that their algorithm for the parameterized version of AST-LR is flawed. We then design integer-linear programming (ILP) models for AST-LR and AST-LR-d, and discuss speedup issues when using popular ILP solvers (say, GUROBI or CPLEX) to solve the models. Our experimental results show that our ILP approach is relatively efficient.
AB - Given a set T= {T1 T2,..., Tm } of phylogenetic trees with the same leaf-label set X, we wish to remove some leaves from the trees so that there is a tree T with leaf-label set X displaying all the resulting trees. Note that different leaves may be removed from different input trees. One objective is to minimize the total number of leaves removed from the trees, while the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. [2] refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d ), and show that both problems are NP-hard. They further present algorithms for the parameterized versions of both problems. In this paper, we point out that their algorithm for the parameterized version of AST-LR is flawed. We then design integer-linear programming (ILP) models for AST-LR and AST-LR-d, and discuss speedup issues when using popular ILP solvers (say, GUROBI or CPLEX) to solve the models. Our experimental results show that our ILP approach is relatively efficient.
KW - center tree
KW - Fixed-parameter algorithm
KW - integer linear programming
KW - phylogenetic tree
UR - http://www.scopus.com/inward/record.url?scp=85062571720&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85062571720&origin=recordpage
U2 - 10.1109/BIBM.2018.8621280
DO - 10.1109/BIBM.2018.8621280
M3 - RGC 32 - Refereed conference paper (with host publication)
T3 - Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018
SP - 61
EP - 64
BT - Proceedings - 2018 IEEE International Conference on Bioinformatics and Biomedicine
PB - IEEE
T2 - 2018 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2018
Y2 - 3 December 2018 through 6 December 2018
ER -