Regularizing and Normalizing DAGs and Phylogenetic Networks

Hellmuth, Marc, Lindeberg, Anna and Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 (2026) Regularizing and Normalizing DAGs and Phylogenetic Networks. Journal of Mathematical Biology, 88 (11). ISSN 0303-6812

[thumbnail of s11538-026-01783-4]
Preview
PDF (s11538-026-01783-4) - Published Version
Available under License Creative Commons Attribution.

Download (849kB) | Preview

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.

Item Type: Article
Uncontrolled Keywords: phylogenetic network,cluster,regular network,least common ancestors,normal network,general neuroscience,immunology,general mathematics,general biochemistry,genetics and molecular biology,pharmacology,general environmental science,general agricultural and biological sciences,computational theory and mathematics,das not required, no data associated with output ,/dk/atira/pure/subjectarea/asjc/2800/2800
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Norwich Epidemiology Centre
Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Faculty of Science > Research Groups > Computational Biology
Related URLs:
Depositing User: LivePure Connector
Date Deposited: 13 Nov 2026 12:40
Last Modified: 17 Nov 2026 09:45
URI: https://ueaeprints.uea.ac.uk/id/eprint/105108
DOI: 10.1007/s11538-026-01783-4

Downloads

Downloads per month over past year

Actions (login required)

View Item View Item