A least common ancestor (LCA) of two leaves in a directed acyclic graph (DAG) is a vertex that is an ancestor of both leaves and has no proper descendant that is also their common ancestor. LCAs capture hierarchical relationships in rooted trees and, more generally, in DAGs. In 1981, Aho et al. introduced the problem of determining whether a set of pairwise LCA constraints on a set $X$, of the form $(i,j)<(k,l)$ with $i,j,k,l\in X$, can be realized by a rooted tree whose leaf set is $X$, such that whenever $(i,j)<(k,l)$, the LCA of $i,j$ is a descendant of that of $k,l$. They also presented a polynomial-time algorithm, BUILD, to solve this problem. However, many such constraint systems cannot be realized by any tree, prompting the question of whether they can be realized by a more general DAG. We extend Aho et al.'s framework from trees to DAGs, providing both theoretical and algorithmic foundations for reasoning about LCA constraints in this broader setting. Given a collection $R$ of LCA constraints, we define its $+$-closure $R^+$, capturing additional LCA relations implied by $R$. Using $R^+$, we construct a canonical DAG $G_R$ and prove that $R$ is DAG-realizable if and only if it is realized by $G_R$. We further adapt this construction to phylogenetic networks, defining a canonical network $N_R$ and prove that it is regular, i.e., it coincides with the Hasse diagram of its underlying set system. Finally, we show that for any DAG-realizable $R$, its classical closure - comprising all LCA constraints that hold in every DAG realizing $R$ - coincides with its $+$-closure. All constructions are computable in polynomial time, and we provide explicit algorithms for each. All algorithms developed in this paper are implemented in the freely available Python package RealLCA.

In evolutionary biology, networks are becoming increasingly used to represent evolutionary histories for species that have undergone non-treelike or reticulate evolution. Such networks are essentially directed acyclic graphs with a leaf set that corresponds to a collection of species, and in which non-leaf vertices with indegree 1 correspond to speciation events and vertices with indegree greater than 1 correspond to reticulate events such as gene transfer. Recently forest-based networks have been introduced, which are essentially (multi-rooted) networks that can be formed by adding some arcs to a collection of phylogenetic trees (or phylogenetic forest), where each arc is added in such a way that its ends always lie in two different trees in the forest. In this paper, we consider the complexity of deciding whether a given network is proper forest-based, that is, whether it can be formed by adding arcs to some underlying phylogenetic forest which contains the same number of trees as there are roots in the network. More specifically, we show that it is NP-complete to decide whether a tree-child network with m roots is proper forest-based, for each m ≥ 2 . Moreover, for binary networks the problem remains NP-complete when m ≥ 3 but becomes polynomial-time solvable for m = 2 . We also give a fixed parameter tractable (FPT) algorithm, with parameters the maximum outdegree of a vertex, the number of roots, and the number of indegree 2 vertices, for deciding if a semi-binary network is proper forest-based. A key element in proving our results is a new characterization for when a network with m roots is proper forest-based in terms of certain m -colorings. • Proper forest-based networks model evolutionary processes such as introgression. • We consider problem (P): Is a given m-rooted network N proper forest-based? • We show (P) can be solved in polynomial time if N is 2-rooted, binary tree-child. • We show (P) is NP-complete if N is m-rooted, binary tree-child with m ≥ 3. • We give an FPT algorithm for (P) in case every vertex in N has indegree at most 2.

The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T,t) whose vertices are labeled as “series” (1), “parallel” (0) or “prime”. However, full information of G is provided by its modular decomposition tree (T,t) only, if G is a cograph, i.e., G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y}∈E(G) if and only if the lowest common ancestor lcaT(x,y) of x and y has label “1”. Pseudo-cographs, or, more generally, GaTEx graphs G are graphs that can be explained by labeled galled-trees, i.e., labeled networks (N,t) that are obtained from the modular decomposition tree (T,t) of G by replacing the prime vertices in T by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time. In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set FGT of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GATEX graphs are closely related to many other well-known graph classes such as P4-sparse and P4-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GATEX graph as twin-width at most 1.

Abstract. A network [Formula: see text] on a finite set [Formula: see text], [Formula: see text], is a connected directed acyclic graph with leaf set [Formula: see text] in which every root in [Formula: see text] has outdegree at least 2 and no vertex in [Formula: see text] has indegree and outdegree equal to 1; [Formula: see text] is arboreal if the underlying unrooted, undirected graph of [Formula: see text] is a tree. Networks are of interest in evolutionary biology since they are used, for example, to represent the evolutionary history of a set [Formula: see text] of species whose ancestors have exchanged genes in the past. For [Formula: see text] some arbitrary set of symbols, [Formula: see text] is a symbolic arboreal map if there exists some arboreal network [Formula: see text] whose vertices with outdegree 2 or more are labeled by elements in [Formula: see text] and so that [Formula: see text], [Formula: see text], is equal to the label of the least common ancestor of [Formula: see text] and [Formula: see text] in [Formula: see text] if this exists, and [Formula: see text] otherwise. Important examples of symbolic arboreal maps include the symbolic ultrametrics, which arise in areas such as game theory, phylogenetics, and cograph theory. In this paper we show that a map [Formula: see text] is a symbolic arboreal map if and only if [Formula: see text] satisfies certain 3- and 4-point conditions and the graph with vertex set [Formula: see text] and edge set consisting of those pairs [Formula: see text] with [Formula: see text] is Ptolemaic (i.e., its shortest path distance satisfies Ptolemy’s inequality). To do this, we introduce and prove a key theorem concerning the shared ancestry graph for a network [Formula: see text] on [Formula: see text], where this is the graph with vertex set [Formula: see text] and edge set consisting of those [Formula: see text] such that [Formula: see text] and [Formula: see text] share a common ancestor in [Formula: see text]. In particular, we show that for any connected graph [Formula: see text] with vertex set [Formula: see text] and edge clique cover [Formula: see text] in which there are no two distinct sets in [Formula: see text] with one a subset of the other, there is some network with [Formula: see text] roots and leaf set [Formula: see text] whose shared ancestry graph is [Formula: see text].

SUMMARY: RNA molecules play crucial roles in various biological processes. They mediate their function mainly by interacting with other RNAs or proteins. At present, information about these interactions is distributed over different resources, often providing the data in simple tab-delimited formats that differ between the databases. There is no standardized data format that can capture the nature of all these different interactions in detail. AVAILABILITY AND IMPLEMENTATION: Here, we propose the RNA interaction format (RIF) for the detailed representation of RNA-RNA and RNA-Protein interactions and provide reference implementations in C/C++, Python, and JavaScript. RIF is released under licence GNU General Public License version 3 (GNU GPLv3) and is available on https://github.com/RNABioInfo/rna-interaction-format.

The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T,t) whose vertices are labeled as “series” (1), “parallel” (0) or “prime”. However, full information of G is provided by its modular decomposition tree (T,t) only, if G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y}∈E(G) if and only if the lowest common ancestor lcaT(x,y) of x and y has label “1”. This information, however, gets lost whenever (T,t) contains vertices with label “prime”. In this contribution, we aim at replacing “prime” vertices in (T,t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N,t). We characterize graphs that can be explained by such level-1 networks (N,t), which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules “induce” polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes. In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N,t), i.e., (N,t) contains exactly one cycle C that is rooted at the root ρN of N and where ρN has exactly two children while every vertex distinct from ρN has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N,t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that can be explained by labeled level-1 networks, namely prime polar-cats. Moreover, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph. In addition, we provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them.

MOTIVATION: Novel recombinant viruses may have important medical and evolutionary significance, as they sometimes display new traits not present in the parental strains. This is particularly concerning when the new viruses combine fragments coming from phylogenetically distinct viral types. Here, we consider the task of screening large collections of sequences for such novel recombinants. A number of methods already exist for this task. However, these methods rely on complex models and heavy computations that are not always practical for a quick scan of a large number of sequences. RESULTS: We have developed SHERPAS, a new program to detect novel recombinants and provide a first estimate of their parental composition. Our approach is based on the precomputation of a large database of 'phylogenetically-informed k-mers', an idea recently introduced in the context of phylogenetic placement in metagenomics. Our experiments show that SHERPAS is hundreds to thousands of times faster than existing software, and enables the analysis of thousands of whole genomes, or long-sequencing reads, within minutes or seconds, and with limited loss of accuracy. AVAILABILITY AND IMPLEMENTATION: The source code is freely available for download at https://github.com/phylo42/sherpas. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Reconstructing the evolutionary past of a family of genes is an important aspect of many genomic studies. To help with this, simple relations on a set of sequences called orthology relations may be employed. In addition to being interesting from a practical point of view they are also attractive from a theoretical perspective in that e. g. a characterization is known for when such a relation is representable by a certain type of phylogenetic tree. For an orthology relation inferred from real biological data it is however generally too much to hope for that it satisfies that characterization. Rather than trying to correct the data in some way or another which has its own drawbacks, as an alternative, we propose to represent an orthology relation $$\delta $$ in terms of a structure more general than a phylogenetic tree called a phylogenetic network. To compute such a network in the form of a level-1 representation for $$\delta $$ , we formalize an orthology relation in terms of the novel concept of a symbolic 3-dissimilarity which is motivated by the biological concept of a “cluster of orthologous groups”, or COG for short. For such maps which assign symbols rather that real values to elements, we introduce the novel Network-Popping algorithm which has several attractive properties. In addition, we characterize an orthology relation $$\delta $$ on some set X that has a level-1 representation in terms of eight natural properties for $$\delta $$ as well as in terms of level-1 representations of orthology relations on certain subsets of X.