Skip to content

Best Matches in Phylogenetic Networks

Sep 2026 · arXiv.org · Vol abs/2609.21700 · 0 citations · 10 references
Biology Computer Science

TL;DR

BMGs of rooted networks are characterized as those vertex-colored digraphs that are properly colored and satisfy an easy-to-check condition that is called the sicor-in-hub property.

Abstract

Best match graphs (BMGs) were introduced in mathematical phylogenetics to describe the concept of closest relatives for related genes (leaves of rooted tree) in different organisms (defining leaf colors). We generalize this concept here to leaf-colored rooted networks, where least common ancestors are in general neither unique nor comparable. We characterize BMGs of rooted networks as those vertex-colored digraphs that are properly colored and satisfy an easy-to-check condition that we call the sicor-in-hub property. BMGs can be recognized in linear time and an explaining network can be constructed in quadratic time. Analogous results are obtained for reciprocal best match graphs (RBMGs), where an edge $\{x,y\}$ corresponds to pairs of vertices with different color that are mutually closest relatives.

View source

Similar papers

Preprint Oct 2026

The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks

Tree-based networks are a broad graph class in phylogenetics which posit a model of evolution composed of tree-like processes and hybridization events. Hence, for any non-tree-based phylogenetic network, it is meaningful to study the magnitude of violation of the tree-based model assumptions. For rooted networks, we in...

M. Frohn, Takatora Suzuki · 0 citations
Sep 2026

A rooted tree framework for linear time ultrabubble detection

Pangenomics uses graphs to show genetic differences within or between species. In these graphs, a path can represent one genome, while regions with different paths show genetic variation. Biedged graphs use black edges for sequences and grey edges for links between them. Snarls are minimal subgraphs of a biedged graph...

A. Zisis, P. Sætrom · 0 citations
Preprint Sep 2026

Exact Counts of Binary Phylogenetic Networks with Four Reticulations

Phylogenetic networks provide a flexible framework for representing reticulate evolutionary processes, such as hybridization, introgression, recombination, and horizontal gene transfer. However, their combinatorial complexity makes even basic enumeration problems difficult. Building on our previous work for networks wi...

Hao Yu, Lou-Xin Zhang · 1 citation · ⚡1
Preprint Oct 2026

Encoding level-3 semi-directed phylogenetic networks by quarnets and quinnets

Phylogenetic networks generalize phylogenetic trees as models of evolutionary history, allowing lineages to merge as well as to diverge. For many types of genetic data the root position of such a network cannot be recovered, so that only a semi-directed network can be inferred: a mixed graph in which only the edges ent...

N. Holtgrefe, K. Huber, L. van Iersel et al. · 0 citations
Preprint Sep 2026

Characterisations of Planar Galled Networks

Rooted phylogenetic networks are widely used to represent the evolution of species that have undergone reticulate processes. However, these networks can be highly non-planar, making them more difficult to visualise and interpret than evolutionary trees. In this paper, we investigate planarity properties of galled netwo...

Hexuan Liu, Tao-Yang Wu, Guan Yu · 0 citations
#edge computing Open access Oct 2026

Tree Rearrangement Graphs Admit Paths of Decreasing Robinson-Foulds Distance

Tree rearrangements such as Nearest Neighbor Interchange (NNI) and Subtree Prune and Regraft (SPR) are commonly used to explore phylogenetic treespace. Computing distances based on them, however, is often intractable, so the efficiently computable Robinson-Foulds (RF) distance is used in practice. We investigate how th...

Lena Collienne, F. Matsen · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.