Orthologous genes, the copies that arise when an ancestral species splits into two descendants, are the workhorses of comparative genomics. Because they are generally assumed to perform more similar functions than gene copies created by duplication or horizontal transfer, researchers lean on them to transfer functional knowledge from one organism to another, to support genetic diagnostics and even to guide drug design. Since the concept was first defined in the early 1970s, inferring which gene pairs are orthologs has been an active field, and two main strategies have emerged: tree-based reconciliation methods and graph-based inference methods.
Graph-based methods such as OrthoMCL, ProteinOrtho, OMA and eggNOG build an orthology graph directly from pairwise sequence comparisons, bypassing the need for explicit gene and species phylogenies. In such a graph, each vertex is a gene and an edge joins two vertices when the corresponding genes are estimated to be orthologs. Extensive benchmarking has shown that these tools perform at least as well as tree-based alternatives, and they are often more computationally efficient. But a fundamental question shadows every inferred graph: does it correspond to any biologically plausible evolutionary history at all?
Under a strictly tree-like model of evolution, the answer has long been known. An orthology graph is biologically feasible if and only if it is a cograph, a graph that contains no induced path on four vertices, often abbreviated P4. The corresponding cotree then represents a partially resolved version of the underlying gene tree. Real-world data, however, frequently violate this property, whether because of noise, errors in the inference methods, or because evolution itself follows a network-like rather than a tree-like process, driven by events such as hybridization at the species level or gene fusion at the genetic level.
A new study published in Algorithms for Molecular Biology by Anna Lindeberg, Guillaume E. Scholz, Nicolas Wieseke and Marc Hellmuth tackles exactly this gap. The authors ask what constraints a particular class of phylogenetic networks imposes on the orthology graph it can explain, extending earlier work on trees and galled trees to the broader class of level-k networks, with special attention to the prominent subclass of level-1 networks. A level-k network is a directed acyclic graph in which each biconnected block contains at most k hybrid vertices, the points where reticulate events such as hybridization enter the history. A level-0 network is simply a tree.
The first result is striking in its generality: any orthology graph whatsoever can be explained by a sufficiently complex level-k network. The researchers prove that for every graph G on a set X of genes, there exists a 0/1-labeled phylogenetic network whose level k is smaller than the number of genes and which has on the order of |X| squared vertices, where an edge between two genes exists precisely when the least common ancestor of the pair carries the label 1, meaning speciation. In this sense, every inferred set of orthologous gene pairs can, in principle, be represented within some network-based evolutionary scenario. But the authors caution that such a scenario may be excessively complex and biologically implausible, because networks with arbitrarily high level lack biologically meaningful constraints.
The picture changes dramatically at level 1, where each block of the network contains at most one hybrid vertex. Level-1 networks are, in an intuitive sense, close to being tree-like while still allowing occasional non-tree-like events, and they turn out to impose genuine structure on the graphs they can explain. To characterize that structure, the team employed modular decomposition, a classical graph-theoretical technique in which every graph admits a unique decomposition into so-called strong modules that form a hierarchy representable as a labeled tree. Cographs are precisely the graphs whose modular decomposition tree uses only the labels 0 and 1, corresponding to parallel and series composition; any graph containing an induced P4 forces the appearance of a third label, prime.
The pivotal concept is the primitive graph, a graph with at least four vertices whose only modules are the trivial ones, namely the whole vertex set and the singletons. Primitive graphs sit at the opposite pole from cographs, which are exactly the graphs that can be built through a series of joins and disjoint unions. The central theorem states that a primitive graph can be explained by a level-1 network if and only if it is a near-cograph, meaning that there exists a single vertex whose removal turns the graph into a cograph. Equivalently, a graph is a near-cograph if and only if it contains a vertex that lies on every induced P4 it possesses. This result enables the authors to establish multiple characterizations of general level-1 explainable graphs: a graph is level-1 explainable if and only if every induced subgraph is, if and only if the quotient graph of every non-trivial prime module is a near-cograph, if and only if every primitive induced subgraph is a near-cograph, and if and only if it can be constructed from single-vertex graphs and primitive near-cographs by a finite sequence of disjoint unions, joins and vertex substitutions.
These characterizations come with an algorithmic payoff. The authors present a linear-time algorithm, running in time proportional to the number of vertices plus edges, that decides whether a given graph can be explained by a labeled level-1 network and, when the answer is yes, constructs such a network. The procedure first computes the modular decomposition tree, then checks whether the quotient graph of each prime module is a near-cograph, using an existing linear-time cograph recognition routine and a targeted search for a vertex whose deletion destroys all induced P4s. For each passing quotient, the algorithm builds a level-1 network by extending the cotree of the resulting cograph with one hybrid vertex, and finally assembles the full explanation by replacing each prime vertex in the decomposition tree with its corresponding network.
The analysis also connects level-1 explainable graphs to classical graph classes in unexpected ways. The authors show that these graphs are closed under the substitution operation, in which a vertex of one graph is replaced by an entire second graph whose vertices inherit exactly the neighbors of the substituted vertex. They prove that level-1 explainable graphs contain no induced cycles of length five or more and no complements of such cycles, which makes them weakly chordal and therefore perfect, meaning that in every induced subgraph the chromatic number equals the size of the largest clique. They further show that the twin-width of any level-1 explainable graph is at most 2, where twin-width is a recently introduced parameter measuring a graph’s distance from being a cograph, and that this bound is tight, with examples attaining twin-width exactly 2. Since perfect graphs and graphs of bounded twin-width possess powerful algorithmic properties, the authors suggest that graphs explained by level-1 networks may be of interest well beyond orthology inference.
The work leaves open questions that the authors flag for future research. Finding a minimum-size set of vertices whose removal turns a graph into a cograph is known to be NP-hard, and it remains open whether finding the smallest level k for which a graph is level-k explainable is hard as well. The computational complexity of editing an inferred orthology graph into a level-1 explainable one, by adding or removing edges, is also unresolved. The authors propose that modular decomposition can serve as a toolbox for characterizing orthology graphs explainable by network types beyond level 1, though even the natural generalization to level-2 networks appears non-trivial, since additional hybridization events introduce significantly greater structural complexity. Another open thread concerns how best matches, the closest sequence relatives of a gene, relate to orthology in network-based scenarios, a question that has been studied extensively under tree-like assumptions but not yet in the network setting.
Subject of Research: Mathematical characterization of orthology graphs that can be explained by phylogenetic networks instead of trees.
Article Title: Orthology and near-cographs in the context of phylogenetic networks
Article References: Lindeberg, A., Scholz, G. E., Wieseke, N., & Hellmuth, M. (2025). Orthology and near-cographs in the context of phylogenetic networks. Algorithms for Molecular Biology, 20(1), Article 19. https://doi.org/10.1186/s13015-025-00285-7
Image Credits: AI Generated
DOI: 10.1186/s13015-025-00285-7
Keywords: orthology, phylogenetic networks, cographs, near-cographs, modular decomposition, level-1 networks, graph theory, comparative genomics, twin-width, perfect graphs, hybridization, algorithms
News Source: Juliet Wilcox. (November 5, 2026). Gene Family Trees Give Way to Networks as Mathematicians Map Orthology’s Hidden Limits. Scienmag.
