Can I read Representing Partitions on Trees on EtoBox?

Representing Partitions on Trees by Huber, Katharina T.; Moulton, Vincent; Semple, Charles; Wu, Taoyang is a scholarly article available to read on EtoBox.

What is Representing Partitions on Trees about?

In evolutionary biology, biologists often face the problem of constructing a phylogenetic tree on a set $X$ of species from a multiset $\Pi$ of partitions corresponding to various attributes of these species. One approach that is used to solve this problem is to try instead to associate a tree (or even a network) to the multiset $\Sigma_{\Pi}$ consisting of all those bipartitions $\{A,X-A\}$ with $A$ a part of some partition in $\Pi$. The rational behind this approach is that a phylogenetic tree with leaf set $X$ can be uniquely represented by the set of bipartitions of $X$ induced by its edges. Motivated by these considerations, given a multiset $\Sigma$ of bipartitions corresponding to a phylogenetic tree on $X$, in this paper we introduce and study the set $P(\Sigma)$ consisting of those multisets of partitions $\Pi$ of $X$ with $\Sigma_{\Pi}=\Sigma$. More specifically, we characterize when $P(\Sigma)$ is non-empty, and also identify some partitions in $P(\Sigma)$ that are of maximum and minimum size. We also show that it is NP-complete to decide when $P(\Sigma)$ is non-empty in case $\Sigma$ is an arbitrary multiset of bipartitions of $X$. Ultimately, we hope that by gaining a

Author

Huber, Katharina T.; Moulton, Vincent; Semple, Charles; Wu, Taoyang

Published

2014

Language

EN