Representing partitions on trees

DOI10.1137/130906192MaRDI QIDQ2935263zbMATHOpenAlexFDO

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

Publication date 22 December 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2225

zbMATH Keywords

phylogeneticscompatibilitysplit systems\(X\)-treespartition systems

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $Sigm{a}_{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 $Sigm{a}_{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 better understanding of the mapping that takes an arbitrary partition system $Pi$ to the multiset $Sigm{a}_{Pi}$, we will obtain new insights into the use of median networks and, more generally, split-networks to visualize sets of partitions.

Recommendations

• Identifying phylogenetic trees
• A characterization for a set of partial partitions to define an \(X\)-tree
• Compatibility of partitions with trees, hierarchies, and split systems
• Convex tree realizations of partitions
• Representing non-crossing cuts by phylogenetic trees

Cited in

(11)

• On tree partitions
• Compatibility of partitions with trees, hierarchies, and split systems
• scientific article; zbMATH DE number 1163560 (Why is no real title available?)
• On different ``middle parts of a tree
• A characterization for a set of partial partitions to define an \(X\)-tree
• Representing non-crossing cuts by phylogenetic trees
• Binary space partitioning trees as an alternative representation of polytopes
• TREE STRUCTURES ON CERTAIN FAMILIES OF PARTITIONS
• Partitionability of trees
• Identifying phylogenetic trees
• Identifying an \(m\)-ary partition identity through an \(m\)-ary tree

This page was built for publication: Representing partitions on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935263)