Buneman graphs, partial splits and subtree distances

Bryant, David, Huber, Katharina, Moulton, Vincent and Spillner, Andreas (2025) Buneman graphs, partial splits and subtree distances. Discrete Applied Mathematics. ISSN 0166-218X (In Press)

PDF (buneman) - Accepted Version Restricted to Repository staff only until 31 December 2099. Available under License Creative Commons Attribution Non-commercial. Request a copy

Abstract

In phylogenetics and other areas of classification, the \emph{Buneman graph} is commonly used to represent a collection of bipartitions or \emph{splits} of a (finite) set $X$ in order to display evolutionary relationships. The set $X$ usually corresponds to a set of taxa (or species), and the splits are usually derived from molecular sequence data associated to the taxa. One issue with this approach is that missing molecular data can lead to bipartitions of subsets of $X$ or \emph{partial splits}, instead of splits of the full set $X$. In this paper, we show that the definition of the Buneman graph can be naturally extended to collections of partial splits of a set $X$. Just as with splits, we show that the graph so obtained is an $X$-labeled median graph but, in contrast to the usual Buneman graph, the elements in $X$ are represented by convex subsets of the vertex set of the graph instead of single vertices. We also show that the Buneman graph for a collection of partial splits is closely related to subtree distances. In particular, for a collection $\mathcal S$ of weighted partial splits that satisfies a certain pairwise compatibility condition, we show that the corresponding edge-weighted Buneman graph is the unique minimal tree that represents the subtree distance $d$ corresponding to $\mathcal S$. Moreover, we show that in this special situation the Buneman graph can also be considered as a type of configuration space for the set of all tree-metrics that minimally extend the subtree distance $d$.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Depositing User:	LivePure Connector
Date Deposited:	24 Feb 2025 16:30
Last Modified:	24 Feb 2025 16:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/98578
DOI:	issn:0166-218X

Actions (login required)

View Item