Computing a smallest multi-labeled phylogenetic tree from rooted triplets

Sylvain Guillemot; Jesper Andreas Jansson; Wing Kin Sung

doi:10.1007/978-3-642-10631-6_121

Computing a smallest multi-labeled phylogenetic tree from rooted triplets

Sylvain Guillemot, Jesper Andreas Jansson, Wing Kin Sung

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-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 language	English
Title of host publication	Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings
Pages	1205-1214
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-10631-6_121
Publication status	Published - 1 Dec 2009
Externally published	Yes
Event	20th International Symposium on Algorithms and Computation, ISAAC 2009 - Honolulu, HI, United States Duration: 16 Dec 2009 → 18 Dec 2009

Publication series

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

Conference

Conference	20th International Symposium on Algorithms and Computation, ISAAC 2009
Country/Territory	United States
City	Honolulu, HI
Period	16/12/09 → 18/12/09

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

More information

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

Cite this

Guillemot, S., Jansson, J. A., & Sung, W. K. (2009). Computing a smallest multi-labeled phylogenetic tree from rooted triplets. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings (pp. 1205-1214). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS). https://doi.org/10.1007/978-3-642-10631-6_121

Guillemot, Sylvain ; Jansson, Jesper Andreas ; Sung, Wing Kin. / Computing a smallest multi-labeled phylogenetic tree from rooted triplets. Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. pp. 1205-1214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9381ceb56d4b43cf8636821b557b71b8,

title = "Computing a smallest multi-labeled phylogenetic tree from rooted triplets",

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.",

author = "Sylvain Guillemot and Jansson, {Jesper Andreas} and Sung, {Wing Kin}",

year = "2009",

month = dec,

day = "1",

doi = "10.1007/978-3-642-10631-6_121",

language = "English",

isbn = "3642106307",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "1205--1214",

booktitle = "Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings",

note = "20th International Symposium on Algorithms and Computation, ISAAC 2009 ; Conference date: 16-12-2009 Through 18-12-2009",

}

Guillemot, S, Jansson, JA & Sung, WK 2009, Computing a smallest multi-labeled phylogenetic tree from rooted triplets. in Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5878 LNCS, pp. 1205-1214, 20th International Symposium on Algorithms and Computation, ISAAC 2009, Honolulu, HI, United States, 16/12/09. https://doi.org/10.1007/978-3-642-10631-6_121

Computing a smallest multi-labeled phylogenetic tree from rooted triplets. / Guillemot, Sylvain; Jansson, Jesper Andreas; Sung, Wing Kin.
Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. p. 1205-1214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5878 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

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 -

Guillemot S, Jansson JA, Sung WK. Computing a smallest multi-labeled phylogenetic tree from rooted triplets. In Algorithms and Computation - 20th International Symposium, ISAAC 2009, Proceedings. 2009. p. 1205-1214. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-10631-6_121

Computing a smallest multi-labeled phylogenetic tree from rooted triplets

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this