Best Matches in Phylogenetic Networks
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.
Related
- Exact Counts of Binary Phylogenetic Networks with Four Reticulations
- The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks
- The parental parsimony problem on binary, tree-child phylogenetic networks
- An explicit birth-death-reticulation model for studying the diversification of phylogenetic networks
- An extension of the classic Buneman theorem from phylogenetic trees to networks
BibTeX
@misc{ebert2026best,
title = {{Best Matches in Phylogenetic Networks}},
author = {Patricia A. Ebert and Peter F. Stadler and Marc Hellmuth},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21700},
eprint = {2609.21700},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21700},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Best Matches in Phylogenetic Networks
AU - Patricia A. Ebert
AU - Peter F. Stadler
AU - Marc Hellmuth
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21700
UR - https://arxiv.org/abs/2609.21700
AB - 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.
ER -