Buneman graphs, partial splits and subtree distances

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

Preview

PDF (1-s2.0-S0166218X25001118-main) - Published Version Available under License Creative Commons Attribution Non-commercial. Download (599kB) | Preview

Abstract

In phylogenetics and other areas of classification, the Buneman graph is commonly used to represent a collection of bipartitions or 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 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 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 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
Uncontrolled Keywords:	network representation,partial split,subtree distance,applied mathematics,discrete mathematics and combinatorics ,/dk/atira/pure/subjectarea/asjc/2600/2604
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
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	24 Feb 2025 16:30
Last Modified:	28 Mar 2025 13:13
URI:	https://ueaeprints.uea.ac.uk/id/eprint/98578
DOI:	10.1016/j.dam.2025.02.035

Downloads

Actions (login required)

View Item