Representing partitions on trees

DOI10.1137/130906192zbMATH Open1305.05191arXiv1405.2225OpenAlexW2963641169MaRDI QIDQ2935263FDOQ2935263

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)

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.

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

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

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)

Cited In (10)

• Identifying phylogenetic trees
• On different ``middle parts of a tree
• On tree partitions
• A characterization for a set of partial partitions to define an \(X\)-tree
• Identifying an \(m\)-ary partition identity through an \(m\)-ary tree
• Compatibility of partitions with trees, hierarchies, and split systems
• Title not available (Why is that?)
• Binary space partitioning trees as an alternative representation of polytopes
• Partitionability of trees
• TREE STRUCTURES ON CERTAIN FAMILIES OF PARTITIONS

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)