Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-25591-5_76
Title: Algorithms for building consensus MUL-trees
Authors: Cui, Y. 
Jansson, J.
Sung, W.-K. 
Issue Date: 2011
Source: Cui, Y.,Jansson, J.,Sung, W.-K. (2011). Algorithms for building consensus MUL-trees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7074 LNCS : 744-753. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-25591-5_76
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. © 2011 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/43297
ISBN: 9783642255908
ISSN: 03029743
DOI: 10.1007/978-3-642-25591-5_76
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 5, 2017

Page view(s)

50
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.