Computing a smallest multi-labeled phylogenetic tree from rooted triplets

Sylvain Guillemot, Jesper Andreas Jansson, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n1-εfor any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O*(7n) time and O*(3n) space.
Original languageEnglish
Title of host publicationAlgorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages1205-1214
Number of pages10
DOIs
Publication statusPublished - 1 Dec 2009
Externally publishedYes
Event20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States
Duration: 16 Dec 200918 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Symposium on Algorithms and Computation, ISAAC 2009
Country/TerritoryUnited States
CityHonolulu, HI
Period16/12/0918/12/09

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this