Title: Orthology and Near-Cographs in the Context of Phylogenetic Networks Show Chinese title

Title: 直系同源和近似Cograph在系统发育网络背景下的研究

Abstract: Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of orthology estimates without prior knowledge of the underlying gene or species trees. This results in orthology graphs, where each vertex represents a gene, and an edge exists between two vertices if the corresponding genes are estimated to be orthologs. Orthology graphs inferred under a tree-like evolutionary model must be cographs. However, real-world data often deviate from this property, either due to noise in the data, errors in inference methods or, simply, because evolution follows a network-like rather than a tree-like process. The latter, in particular, raises the question of whether and how orthology graphs can be derived from or, equivalently, are explained by phylogenetic networks. Here, we study the constraints imposed on orthology graphs when the underlying evolutionary history follows a phylogenetic network instead of a tree. We show that any orthology graph can be represented by a sufficiently complex level-k network. However, such networks lack biologically meaningful constraints. In contrast, level-1 networks provide a simpler explanation, and we establish characterizations for level-1 explainable orthology graphs, i.e., those derived from level-1 evolutionary histories. To this end, we employ modular decomposition, a classical technique for studying graph structures. Specifically, an arbitrary graph is level-1 explainable if and only if each primitive subgraph is a near-cograph (a graph in which the removal of a single vertex results in a cograph). Additionally, we present a linear-time algorithm to recognize level-1 explainable orthology graphs and to construct a level-1 network that explains them, if such a network exists. Show Chinese abstract

Abstract: 同源基因是通过物种形成产生的，在比较基因组学和功能推断中起着关键作用。特别是基于图的方法可以在不需要事先了解基础基因或物种树的情况下推断同源性估计。这导致了同源图，其中每个顶点代表一个基因，如果对应的基因被估计为同源，则两个顶点之间存在边。在树状进化模型下推断的同源图必须是共图。然而，现实数据常常偏离这一特性，可能是由于数据中的噪声、推断方法的错误，或者仅仅是由于进化遵循网络状而非树状过程。后者尤其引发了关于同源图是否能从或等价地被系统发育网络解释的问题。在这里，我们研究了当基础进化历史遵循系统发育网络而不是树时对同源图施加的约束。我们证明，任何同源图都可以由足够复杂的层次-k网络表示。然而，这样的网络缺乏生物学上有意义的约束。相反，层次-1网络提供了一个更简单的解释，我们建立了层次-1可解释同源图的特征，即那些来源于层次-1进化历史的同源图。为此，我们采用了模块分解，这是一种研究图结构的经典技术。具体来说，任意图是层次-1可解释的当且仅当每个原始子图是一个近共图（删除一个顶点后变成共图的图）。此外，我们提出了一种线性时间算法来识别层次-1可解释的同源图并构造一个可以解释它们的层次-1网络，如果这样的网络存在的话。