Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints

2026/05/05 by Patricia A. Ebert, Marc Hellmuth · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #cs.DM #q-bio.PE

paper · pdf · doi:10.48550/arxiv.2605.03827

arxiv published 2026/05/05 · arxiv created 2026/08/06 · arxiv updated 2026/08/07

Abstract

Least common ancestor (LCA) constraints encode relative-order information in directed acyclic graphs (DAGs) and give rise to a natural constraint-realization problem. Phylogenetic networks provide an important class of DAGs in which such constraints are used to represent local information about evolutionary histories. In this paper, we study the inference of DAGs and phylogenetic networks from LCA-constraints, which specify relative positions of the LCAs associated with pairs of leaves. While previous work has characterized when a set of required LCA-constraints can be realized by a DAG or phylogenetic network, it is natural to consider additional constraints that must be explicitly avoided. We therefore consider the realization problem for pairs (R,F), where R is a set of required LCA-constraints and F is a set of forbidden ones. Since there are several natural ways to formalize what it means for a DAG to avoid a forbidden LCA-constraint, we study three such variants. For each of them, we characterize exactly when there exists a DAG or a phylogenetic network that realizes all constraints in R while avoiding all constraints in F in the respective sense. Our main characterization is based on a closure operator obtained from four elementary inference rules. Based on these characterizations, we derive polynomial-time algorithms that decide the existence of such realizations and construct one whenever it exists. All algorithms developed in this paper are implemented in the freely available Python package RealLCA.

Citations

• Inferring DAGs and Phylogenetic Networks from Least Common Ancestors
• Orthology and Near-Cographs in the Context of Phylogenetic Networks
• Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
• An algorithm for reconstructing level-2 phylogenetic networks from trinets
• Trinets encode orchard phylogenetic networks
• Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs
• Reciprocal Best Match Graphs
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
• Phylogenomics with Paralogs
• Trinets encode tree-child and level-2 phylogenetic networks
• A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks
• Constructing the Simplest Possible Phylogenetic Network from Triplets
• Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks
• Constructing level-2 phylogenetic networks from triplets

Cited by

• Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors

Discussions

• Patricia A. Ebert, Marc Hellmuth: Inferring Phylogenetic Networks from Allowed and Forbidden LCA-Constraints https://arxiv.org/abs/2605.03827 https://arxiv.org/pdf/2605.03827 https://arxiv.org/html/26 [bsky, 0 points, 0 comments]

Related

• Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors
• Encoding Phylogenetic Networks with Least Common Ancestor Constraints
• Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
• Inferring DAGs and Phylogenetic Networks from Least Common Ancestors
• Classes of Explicit Phylogenetic Networks and their Biological and Mathematical Significance