The complexity of deriving multi-labeled trees from bipartitions

Huber, Katharina T., Lott, Martin, Moulton, Vincent ORCID: and Spillner, Andreas (2008) The complexity of deriving multi-labeled trees from bipartitions. Journal of Computational Biology, 15 (6). pp. 639-651. ISSN 1557-8666

Full text not available from this repository. (Request a copy)


Recently, multi-labeled trees have been used to help unravel the evolutionary origins of polyploid species. A multi-labeled tree is the same as a phylogenetic tree except that more than one leaf may be labeled by a single species, so that the leaf set of a multi-labeled tree can be regarded as a multiset. In contrast to phylogenetic trees, which can be efficiently encoded in terms of certain bipartitions of their leaf sets, we show that it is NP-hard to decide whether a collection of bipartitions of a multiset can be represented by a multi-labeled tree. Even so, we also show that it is possible to generalize to multi-labeled trees a well-known condition that characterizes when a collection of bipartitions encodes a phylogenetic tree. Using this generalization, we obtain a fixed-parameter algorithm for the above decision problem in terms of a parameter associated to the given multiset.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 09 Mar 2011 09:40
Last Modified: 22 Apr 2023 01:04
DOI: 10.1089/cmb.2008.0088

Actions (login required)

View Item View Item