Tools
Tools
Huber, Katharina T., Lott, Martin, Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435 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
Abstract
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 |
| UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
| Related URLs: | |
| Depositing User: | Vishal Gautam |
| Date Deposited: | 09 Mar 2011 09:40 |
| Last Modified: | 15 Jun 2023 23:57 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/23746 |
| DOI: | 10.1089/cmb.2008.0088 |
Actions (login required)
 |
View Item |