Inferring Phylogenetic Networks from Allowed and Forbidden LCA-Constraints
This work extends the theoretical foundation for inferring phylogenetic networks from LCA constraints by incorporating forbidden constraints, which is relevant for computational biology researchers working on evolutionary network inference.
The paper characterizes when a set of required and forbidden least common ancestor (LCA) constraints can be simultaneously realized by a phylogenetic network, and provides polynomial-time algorithms to decide existence and construct such networks.
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)$, where $R$ is a set of allowed or, equivalently, required LCA-constraints and $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$ while avoiding all constraints in $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.