Finding a Center Tree of Phylogenetic Trees via Leaf Removal

摘要

Given a set T = {T₁, T₂, . . . , T_m} 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 ASTLR-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.