The complexity of deriving multi-labeled trees from bipartitions
The complexity of deriving multi-labeled trees from bipartitions
复制标题
DOI：
10.1089/cmb.2008.0088
复制
发表时间：
2008-07-01
影响因子：
1.7
通讯作者：
Spillner, Andreas
中科院分区：
文献类型：
--
作者：
Huber, Katharina T.;Lott, Martin;Spillner, Andreas
最近，多标记树已被用来帮助解开多倍体物种的进化起源。多标记树与系统发育树相同，不同之处在于多个叶子可以被单个物种标记，因此多标记树的叶子集合可以被视为多集合。在系统发育树，这可以有效地编码在某些bipartisons的叶集，我们表明，这是NP-难决定是否集合的bipartisons的多集合可以表示为一个多标签树。即便如此，我们也表明，它是可以推广到多标记树的一个众所周知的条件，其特征是当一个集合的bipartitions编码的系统发育树。使用这种推广，我们得到了一个固定参数的算法，上述决策问题的参数与给定的多集。
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.