Computing a Consensus Phylogeny via Leaf Removal

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)175-188
Journal / PublicationJournal of Computational Biology
Volume27
Issue number2
Online published23 Oct 2019
Publication statusPublished - Feb 2020

Abstract

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 the labels of leaves removed from one input tree may be different from those of leaves removed from another input tree. One objective is to minimize the total number of leaves removed from the trees, whereas the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d), and they show that both problems are NP-hard, where NP is the class of problems solvable in non-deterministic polynomial time. They further present algorithms for the parameterized versions of both problems. In this article, we point out that their algorithm for the parameterized version of AST-LR is flawed and present a new algorithm. Since neither Chauve et al.'s algorithm for AST-LR-d nor our new algorithm for AST-LR looks practical, we further design integer-linear programming (ILP for short) models for AST-LR and AST-LR-d, and we 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 quite efficient.

Research Area(s)

  • center tree, fixed-parameter algorithm, integer linear programming, phylogenetic tree

Citation Format(s)

Computing a Consensus Phylogeny via Leaf Removal. / CHEN, Zhi-Zhong; UETA, Shohei; LI, Jingyu; WANG, Lusheng.

In: Journal of Computational Biology, Vol. 27, No. 2, 02.2020, p. 175-188.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review