Regularizing and Normalizing DAGs and Phylogenetic Networks
Abstract
Phylogenetic networks and, more generally, directed acyclic graphs (DAGs) represent hierarchical structure beyond trees, for instance in the presence of reticulate evolutionary events such as hybridization or horizontal gene transfer. A central question is which parts of such graphs are essential with respect to leaf-observable information, and which parts can be removed without changing this information. Resolving this question can lead to principled simplification methods for phylogenetic networks, such as the recent normalization approach of Francis et al. In this paper, we study this question from three related perspectives: clusters displayed by a DAG G, least common ancestors (LCAs) of subsets of its leaf set, and visibility, a path-based property of vertices. We first introduce an LCA-based simplification procedure called i-regularization. For a DAG G and i≥ 1, the DAG regi(G) retains precisely those vertices that occur as unique LCAs of leaf subsets of size at most i, removes the remaining non-leaf vertices by a graph-editing operation ominus, and then deletes shortcuts. We show that regi(G) admits a Hasse-diagram characterization in terms of the corresponding lca-clusters. We then compare LCA-based regularization with normalization. Using the same ominus-operator, we describe the cover construction underlying normalization, identify visible vertices that are nevertheless removed, and characterize when regularization and normalization coincide. Together, these results provide a unified framework for cluster-based, LCA-based, and visibility-based simplifications of DAGs and phylogenetic networks.
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{hellmuth2026regularizing,
title = {{Regularizing and Normalizing DAGs and Phylogenetic Networks}},
author = {Marc Hellmuth and Anna Lindeberg and Vincent Moulton},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.21725},
eprint = {2605.21725},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.21725},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Regularizing and Normalizing DAGs and Phylogenetic Networks
AU - Marc Hellmuth
AU - Anna Lindeberg
AU - Vincent Moulton
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2605.21725
UR - https://arxiv.org/abs/2605.21725
AB - Phylogenetic networks and, more generally, directed acyclic graphs (DAGs) represent hierarchical structure beyond trees, for instance in the presence of reticulate evolutionary events such as hybridization or horizontal gene transfer. A central question is which parts of such graphs are essential with respect to leaf-observable information, and which parts can be removed without changing this information. Resolving this question can lead to principled simplification methods for phylogenetic networks, such as the recent normalization approach of Francis et al. In this paper, we study this question from three related perspectives: clusters displayed by a DAG G, least common ancestors (LCAs) of subsets of its leaf set, and visibility, a path-based property of vertices. We first introduce an LCA-based simplification procedure called i-regularization. For a DAG G and i≥ 1, the DAG reg_i(G) retains precisely those vertices that occur as unique LCAs of leaf subsets of size at most i, removes the remaining non-leaf vertices by a graph-editing operation ominus, and then deletes shortcuts. We show that reg_i(G) admits a Hasse-diagram characterization in terms of the corresponding lca-clusters. We then compare LCA-based regularization with normalization. Using the same ominus-operator, we describe the cover construction underlying normalization, identify visible vertices that are nevertheless removed, and characterize when regularization and normalization coincide. Together, these results provide a unified framework for cluster-based, LCA-based, and visibility-based simplifications of DAGs and phylogenetic networks.
ER -