Encoding level-3 semi-directed phylogenetic networks by quarnets and quinnets
Abstract
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 entering a reticulation vertex are directed. A common strategy for inferring such a network is to first infer the subnetwork it induces on each set of k≥ 3 of its leaves, called a k-net, and then to assemble these pieces. This can only succeed if the k-nets determine the network, in which case that network is said to be encoded by its k-nets. Semi-directed networks of level-1 and 2, those whose biconnected components contain at most one, respectively two, reticulations, are known to be encoded by their $4$-nets, or quarnets, whereas level-3 networks are not. Even so, in this paper we show that level-3 semi-directed networks are encoded by their $5$-nets, or quinnets, and we characterize the limitation of quarnets exactly: we show that a single previously reported counterexample captures the only obstruction, every other level-3 network being encoded by its quarnets. Our proofs rest on a collection of encoding results for individual structural features of a network, which we establish for networks of arbitrary level and which are of independent interest.
Related
- Best Matches in Phylogenetic Networks
- 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
BibTeX
@misc{holtgrefe2026encoding,
title = {{Encoding level-3 semi-directed phylogenetic networks by quarnets and quinnets}},
author = {Niels Holtgrefe and Katharina T. Huber and Leo van Iersel and Vincent Moulton},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07855},
eprint = {2610.07855},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07855},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Encoding level-3 semi-directed phylogenetic networks by quarnets and quinnets
AU - Niels Holtgrefe
AU - Katharina T. Huber
AU - Leo van Iersel
AU - Vincent Moulton
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.07855
UR - https://arxiv.org/abs/2610.07855
AB - 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 entering a reticulation vertex are directed. A common strategy for inferring such a network is to first infer the subnetwork it induces on each set of k≥ 3 of its leaves, called a k-net, and then to assemble these pieces. This can only succeed if the k-nets determine the network, in which case that network is said to be encoded by its k-nets. Semi-directed networks of level-1 and 2, those whose biconnected components contain at most one, respectively two, reticulations, are known to be encoded by their $4$-nets, or quarnets, whereas level-3 networks are not. Even so, in this paper we show that level-3 semi-directed networks are encoded by their $5$-nets, or quinnets, and we characterize the limitation of quarnets exactly: we show that a single previously reported counterexample captures the only obstruction, every other level-3 network being encoded by its quarnets. Our proofs rest on a collection of encoding results for individual structural features of a network, which we establish for networks of arbitrary level and which are of independent interest.
ER -