TY - GEN

T1 - Computing a smallest multi-labeled phylogenetic tree from rooted triplets

AU - Guillemot, Sylvain

AU - Jansson, Jesper Andreas

AU - Sung, Wing Kin

PY - 2009/12/1

Y1 - 2009/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=75649108941&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10631-6_121

DO - 10.1007/978-3-642-10631-6_121

M3 - Conference article published in proceeding or book

SN - 3642106307

SN - 9783642106309

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1205

EP - 1214

BT - Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings

T2 - 20th International Symposium on Algorithms and Computation, ISAAC 2009

Y2 - 16 December 2009 through 18 December 2009

ER -