Algorithms for building consensus MUL-trees

Yun Cui; Jesper Andreas Jansson; Wing Kin Sung

doi:10.1007/978-3-642-25591-5_76

Algorithms for building consensus MUL-trees

Yun Cui, Jesper Andreas Jansson, Wing Kin Sung

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

1 Citation (Scopus)

Abstract

A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott et al. [9,10] recently introduced the problem of inferring a so-called consensus MUL-tree from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study strict and majority rule consensus MUL-trees, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the singular majority rule consensus MUL-tree is unique and can be constructed efficiently.

Original language	English
Title of host publication	Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Pages	744-753
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-25591-5_76
Publication status	Published - 26 Dec 2011
Externally published	Yes
Event	22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan Duration: 5 Dec 2011 → 8 Dec 2011

Publication series

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

Conference

Conference	22nd International Symposium on Algorithms and Computation, ISAAC 2011
Country/Territory	Japan
City	Yokohama
Period	5/12/11 → 8/12/11

ASJC Scopus subject areas

General Computer Science
Theoretical Computer Science

More information

10.1007/978-3-642-25591-5_76

Cite this

Cui, Y., Jansson, J. A., & Sung, W. K. (2011). Algorithms for building consensus MUL-trees. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings (pp. 744-753). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS). https://doi.org/10.1007/978-3-642-25591-5_76

@inproceedings{7a44cd72d4724c0fbf17d3eedd422bc3,

title = "Algorithms for building consensus MUL-trees",

abstract = "A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott et al. [9,10] recently introduced the problem of inferring a so-called consensus MUL-tree from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study strict and majority rule consensus MUL-trees, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the singular majority rule consensus MUL-tree is unique and can be constructed efficiently.",

author = "Yun Cui and Jansson, {Jesper Andreas} and Sung, {Wing Kin}",

year = "2011",

month = dec,

day = "26",

doi = "10.1007/978-3-642-25591-5_76",

language = "English",

isbn = "9783642255908",

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

pages = "744--753",

booktitle = "Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings",

note = "22nd International Symposium on Algorithms and Computation, ISAAC 2011 ; Conference date: 05-12-2011 Through 08-12-2011",

}

Cui, Y, Jansson, JA & Sung, WK 2011, Algorithms for building consensus MUL-trees. in Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7074 LNCS, pp. 744-753, 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, 5/12/11. https://doi.org/10.1007/978-3-642-25591-5_76

Algorithms for building consensus MUL-trees. / Cui, Yun; Jansson, Jesper Andreas; Sung, Wing Kin.
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 744-753 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS).

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

TY - GEN

T1 - Algorithms for building consensus MUL-trees

AU - Cui, Yun

AU - Jansson, Jesper Andreas

AU - Sung, Wing Kin

PY - 2011/12/26

Y1 - 2011/12/26

N2 - A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott et al. [9,10] recently introduced the problem of inferring a so-called consensus MUL-tree from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study strict and majority rule consensus MUL-trees, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the singular majority rule consensus MUL-tree is unique and can be constructed efficiently.

AB - A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott et al. [9,10] recently introduced the problem of inferring a so-called consensus MUL-tree from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study strict and majority rule consensus MUL-trees, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the singular majority rule consensus MUL-tree is unique and can be constructed efficiently.

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

U2 - 10.1007/978-3-642-25591-5_76

DO - 10.1007/978-3-642-25591-5_76

M3 - Conference article published in proceeding or book

SN - 9783642255908

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

SP - 744

EP - 753

BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings

T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011

Y2 - 5 December 2011 through 8 December 2011

ER -

Algorithms for building consensus MUL-trees

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this