Computing a smallest multilabeled phylogenetic tree from rooted triplets

Sylvain Guillemot, Jesper Andreas Jansson, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

We investigate the computational complexity of inferring a smallest possible multilabeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. This problem has not been studied previously in the literature. We prove that even the very restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is an NP-hard problem. Furthermore, we show that the general minimization problem is difficult to approximate, although a simple polynomial-time approximation algorithm achieves an approximation ratio close to our derived inapproximability bound. Finally, we provide an exact algorithm for the problem running in exponential time and space. As a by-product, we also obtain new, strong inapproximability results for two partitioning problems on directed graphs called ACYCLIC PARTITION and ACYCLIC TREE-PARTITION.
Original languageEnglish
Article number5557851
Pages (from-to)1141-1147
Number of pages7
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume8
Issue number4
DOIs
Publication statusPublished - 2 Jun 2011
Externally publishedYes

Keywords

  • acyclic tree-partition
  • dynamic programming.
  • inapproximability
  • MUL tree
  • Phylogenetics
  • rooted triplet

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Applied Mathematics

Cite this