Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Orthology and near-cographs in the context of phylogenetic networks
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0001-9664-1918
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-1620-5508
Number of Authors: 42025 (English)In: Algorithms for Molecular Biology, E-ISSN 1748-7188, Vol. 20, article id 19Article in journal (Refereed) Published
Abstract [en]

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. In this work, 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. Finally, we demonstrate the close relationship of level-1 explainable orthology graphs to the substitution operation, weakly chordal and perfect graphs, as well as graphs with twin-width at most 2.

Place, publisher, year, edition, pages
2025. Vol. 20, article id 19
Keywords [en]
Homology, Level-1 network, Linear-time algorithm, Modular decomposition, Near cograph, Perfect graph, Twin-width
National Category
Bioinformatics (Computational Biology)
Identifiers
URN: urn:nbn:se:su:diva-248256DOI: 10.1186/s13015-025-00285-7ISI: 001585586100001Scopus ID: 2-s2.0-105017895424OAI: oai:DiVA.org:su-248256DiVA, id: diva2:2008187
Available from: 2025-10-22 Created: 2025-10-22 Last updated: 2025-10-22Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Lindeberg, AnnaHellmuth, Marc

Search in DiVA

By author/editor
Lindeberg, AnnaHellmuth, Marc
By organisation
Department of Mathematics
In the same journal
Algorithms for Molecular Biology
Bioinformatics (Computational Biology)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf