2014/05/09 by Katharina T. Huber, Huber, Katharina T., Vincent Moulton +5 · 1 citation
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · #5C05 92D15 #Combinatorics (math.CO) #FOS: Biological sciences #FOS: Mathematics #Genetic diversity and population structure #Plant Diversity and Evolution #Plant and animal studies #Quantitative Methods (q-bio.QM)
paper · pdf · doi:10.48550/arxiv.1405.2225
openalex publication_date 2014/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In evolutionary biology, biologists often face the problem of constructing a phylogenetic tree on a set X of species from a multiset Π 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 ΣΠ consisting of all those bipartitions \A,X-A\ with A a part of some partition in Π. 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 Σ of bipartitions corresponding to a phylogenetic tree on X, in this paper we introduce and study the set P(Σ) consisting of those multisets of partitions Π of X with ΣΠ=Σ. More specifically, we characterize when P(Σ) is non-empty, and also identify some partitions in P(Σ) that are of maximum and minimum size. We also show that it is NP-complete to decide when P(Σ) is non-empty in case Σ 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 Π to the multiset ΣΠ, we will obtain new insights into the use of median networks and, more generally, split-networks to visualize sets of partitions.