Regularizing and Normalizing DAGs and Phylogenetic Networks.
- 1Faculty of Mathematics and Computer Science, Leipzig University, 04109, Leipzig, Germany.
- 2Department of Mathematics, Faculty of Science, Stockholm University, SE-10691, Stockholm, Sweden. [email protected].
- 3School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK.
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 ⊖ , 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 ⊖ -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
- Escaping the Phylogenetic Trap: Persistent Homology Enables Cross-Species Ion Channel Classification via Multimodal Graph Neural Networks
- Identifiability of Large Phylogenetic Mixtures for Many Phylogenetic Model Structures.
- DNA Barcoding and Untargeted Metabolomics Reveal Phylogenetic and Chemotaxonomic Relationships Among 11 Ferula Species from Xinjiang, China
- OrthoFinder: improved phylogenetic orthology inference with enhanced accuracy and scalability
- The complete mitochondrial genome and phylogenetic analysis of the zebra turkeyfish Dendrochirus zebra (Cuvier, 1829) (Teleostei: Perciformes).
BibTeX
@article{hellmuth2026regularizing,
title = {{Regularizing and Normalizing DAGs and Phylogenetic Networks.}},
author = {Marc Hellmuth and Anna Lindeberg and Vincent Moulton},
journal = {Bulletin of mathematical biology},
year = {2026},
month = oct,
doi = {10.1007/s11538-026-01783-4},
url = {https://europepmc.org/article/MED/42905278},
note = {CC BY},
}
RIS
TY - JOUR
TI - Regularizing and Normalizing DAGs and Phylogenetic Networks.
AU - Marc Hellmuth
AU - Anna Lindeberg
AU - Vincent Moulton
PY - 2026
DA - 2026/10/21
JO - Bulletin of mathematical biology
DO - 10.1007/s11538-026-01783-4
UR - https://europepmc.org/article/MED/42905278
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 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 ⊖ , 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 ⊖ -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.
SN - 0092-8240
SN - 1522-9602
ER -