AI Insight
This paper addresses the problem of inferring phylogenetic networks from least common ancestor (LCA) constraints by introducing both required and forbidden constraints. The authors develop polynomial-time algorithms to determine whether a directed acyclic graph or phylogenetic network can satisfy all required LCA-constraints while avoiding forbidden ones, characterizing three different interpretations of constraint avoidance through a closure operator based on four elementary inference rules. All algorithms have been implemented in an open-source Python package called RealLCA.
Why it matters
This work provides computational tools for reconstructing evolutionary histories when researchers have both positive evidence about ancestral relationships and explicit knowledge about relationships that should not occur. The polynomial-time algorithms and publicly available software enable practical applications in phylogenetics, allowing scientists to incorporate more nuanced biological knowledge into network inference.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
-cross
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.
Source: Inferring Phylogenetic Networks from Required and Forbidden LCA-Constraints