Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints

Patricia A. Ebert, Marc Hellmuth · 2026

Read Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints by Patricia A. Ebert, Marc Hellmuth (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03827.txt.

Introduction

Patricia A. Ebert and Marc Hellmuth study how to infer directed acyclic graphs and phylogenetic networks from constraints on least common ancestors. Such constraints encode relative-order information: for pairs of leaves, they state where their least common ancestor must sit in the evolutionary history. Earlier work characterized when required constraints alone can be realized, but not which constraints must be avoided.

Ebert and Hellmuth consider pairs of required and forbidden constraint sets. Because avoiding a forbidden constraint can be formalized in several natural ways, they study three variants. For each, they characterize exactly when a directed acyclic graph or phylogenetic network exists that realizes all required constraints while avoiding all forbidden ones. The main characterization is built on a closure operator.

Catalog record

CREATORPatricia A. Ebert, Marc Hellmuth
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03827

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints Patricia A. Ebert, Marc Hellmuth Abstract Phylogenetic networks provide a framework for representing evolutionary histories involving reticulate events such as hybridization or horizontal gene transfer. A central problem is to infer such networks from local structural information. In this paper, we study network inference from least common ancestor (LCA) constraints, which specify relative ancestral relationships between pairs of taxa. While previous work has characterized when a set of required LCA constraints can be realized by a phylogenetic network, practical applications may also involve constraints that must be explicitly avoided, for example due to biological prior knowledge. We therefore consider the realization problem for pairs ( R , F ) (R,F) , where R R is a set of required LCA-constraints and F F is a set of forbidden ones. Since there are several natural ways to formalize what it means for a network to avoid a forbidden LCA-constraint, we study three such variants. For each of them, we characterize exactly when there exists a phylogenetic network that realizes all constraints in R R while avoiding all constraints in F F in the respective sense. Based on these characterizations, we derive polynomial-time algorithms that decide the existence of such networks and construct one whenever it exists. Keywords: DAG, lowest common ancestor, forbidden relations, BUILD algorithm, evolutionary histories 1 Introduction Phylogenetic networks are commonly used to describe evolutionary histories that cannot be represented by trees. This is particularly relevant in the presence of reticulate events, such as hybridization or horizontal gene transfer, where a purely tree-like model may fail to faithfully represent the underlying evolutionary history. Since such networks are rarely observed directly, a central task in computational biology is to infer such networks from “local information” about their structure. Classical examples of such local information include small induced substructures such as triplets [ 16 , 29 , 30 , 28 , 15 , 23 ] and trinets [ 31 , 27 , 32 ] , relations derived from best matches [ 24 , 9 , 8 ] , orthology and paralogy relations [ 20 , 12 , 14 ] or constraints formulated in terms of relative positions of least common ancestors (LCAs) [ 18 , 1 ] . In all these settings, the guiding principle is that global evolutionary histories should be recovered from small, biologically interpretable pieces of evidence. Here, we follow the ideas of recovering such evolutionary histories from LCA-constraints [ 18 , 1 ] . To make this more precise, let N be a phylogenetic network on a set of taxa X , where the elements of X may, for instance, represent genes or species. A least common ancestor (LCA) of two taxa x,y\in X is a vertex v of N that is an ancestor of both x and y , and such that no proper descendant of v has this property. We write \operatorname{lca}_{N}(xy) whenever the LCA of x and y is uniquely determined in N . An LCA-constraint is then an ordered pair (ab,cd) of pairs of taxa. Generalizing the idea of Aho et al. [ 1 ] , such a constraint specifies that, in any network N “compatible” with it, the LCA \operatorname{lca}_{N}(ab) must be a strict descendant of the LCA \operatorname{lca}_{N}(cd) in N . In this case, we say that N strictly realizes the pair (ab,cd) . Thus, LCA-constraints encode relative ancestral relations: they specify that one pair of taxa shares a more recent common ancestor than another, without requiring exact divergence times, branch lengths, or a fully resolved network topology. This type of realization problem for LCA-constraints was first studied by Aho et al. [ 1 ] in the tree setting. More precisely, they considered the following question: given a collection R of LCA-constraints, can one construct a phylogenetic tree T on X that strictly realizes every constraint (ab,cd)\in R , or decide that no such tree exists? As shown in [ 1 ] , this problem can be solved in polynomial time by the now classical BUILD algorithm. The idea of realizing LCA-constraints was just recently generalized from phylogenetic trees to phylogenetic networks by Lindeberg et al. [ 18 ] . In particular, they provided a characterization of strictly realizable and, more generally, realizable relations, together with a polynomial-time algorithm that decides whether there exists a phylogenetic network realizing all constraints in R . In the affirmative case, the algorithm also constructs such a network in polynomial time. However, in many applications, one is often faced with the problem that, in addition to constraints that are supported by the data, one may also have constraints that should explicitly be avoided. For example, a particular ancestral ordering may be incompatible with prior biological knowledge, temporal information, or previously established evolutionary scenarios. Information about such forbidden configurations has already proved useful in related settings, for instance in the inference of evolutionary histories avoiding forbidden rooted triplets [ 11 ] . This motivates the study of a more expressive realization problem in which one is given not only a relation R of required LCA-constraints, but also a relation F of forbidden LCA-constraints. The task is then to determine whether there exists a phylogenetic network that realizes all constraints in R while avoiding all constraints in F . In this contribution, we provide a characterization of pairs (R,F) , for which there exists a phylogenetic network that is compatible with all constraints in R and displays none of the constraints in F . This characterization, in turn, allows us to present a polynomial-time algorithm that decides whether such a phylogenetic network exists for (R,F) and, in the affirmative case, constructs one. This paper is organized as follows. In Section 2 , we provide the basic definition needed throughout this paper. We then recall some of the established results about sets R of required LCA-constraints and their realization by DAGs or networks in Section 3 . In Section 4 , we extend these results to also deal with sets F of forbidden LCA-constraints. Finally, in Section 5 , we provide two alternative definitions of realizability of forbidden LCA-constraints and characterizations of realizable pairs of relations (R,F) under these definitions. We conclude our contribution with a short outlook in Section 7 . 2 Preliminaries Sets and Relations In what follows, X will always be a finite non-empty set. We denote with \mathcal{P}(X) the power set of X . Moreover, we let \mathcal{P}_{2}(X)\coloneqq\{\{a,b\}\mid a,b\in X\} (with a=b allowed) denote the set system consisting of all 1- and 2-element subsets of X . We will often write ab , respectively, aa for elements \{a,b\} , respectively, \{a\} in \mathcal{P}_{2}(X) . Thus, ab=ba always holds. Given a set A , a subset R\subseteq A\times A is a binary relation (on A ) . Remark 1 . As all relations considered in this work are binary, we shall simply refer to them as relations . Furthermore, we define the support \operatorname{supp}_{R} of a relation R on A as \operatorname{supp}_{R}\coloneqq\{p\in A\mid\text{ there is some }q\in A\text{ with }(p,q)\in R\text{ or }(q,p)\in R\}, that is, the subset of A that contains precisely those p\in A that are in R -relation with some q\in A . We

Read the complete text