Combining Orthology and Xenology Data in a Common Phylogenetic Tree

Marc Hellmuth, Mira Miche, Nikolai Nøjgaard, David Schaller, Peter F. Stadler

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


In mathematical phylogenetics, types of events in a gene tree T are formalized by vertex labels t(v) and set-valued edge labels λ(e). The orthology and paralogy relations between genes are a special case of a map δ on the pairs of leaves of T defined by δ(x, y) = q if the last common ancestor lca (x, y) of x and y is labeled by an event type q, e.g., speciation or duplication. Similarly, a map ε with m∈ ε(x, y) if m∈ λ(e) for at least one edge e along the path from lca (x, y) to y generalizes xenology, i.e., horizontal gene transfer. We show that a pair of maps (δ, ε) derives from a tree (T, t, λ) in this manner if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree (T δ, t δ) that explains δ and the (unique) least-resolved edge labeled tree (T ε, λ ε) that explains ε (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.

Original languageEnglish
Title of host publicationAdvances in Bioinformatics and Computational Biology - 14th Brazilian Symposium on Bioinformatics, BSB 2021, Proceedings : 14th Brazilian Symposium on Bioinformatics, BSB 2021, Virtual Event, November 22–26, 2021, Proceedings
EditorsPeter F. Stadler, Maria Emilia M. T. Walter, Maribel Hernandez-Rosales, Marcelo M. Brigido
Publication date2021
ISBN (Print)9783030918132
ISBN (Electronic)9783030918149
Publication statusPublished - 2021
Event14th Brazilian Symposium on Bioinformatics, Virtual -
Duration: 22. Nov 202126. Nov 2021


Conference14th Brazilian Symposium on Bioinformatics, Virtual
SeriesLecture Notes in Computer Science


  • Binary relations
  • Consistency
  • Fitch map
  • Mathematical phylogenetics
  • Rooted trees
  • Symbolic ultrametric


Dive into the research topics of 'Combining Orthology and Xenology Data in a Common Phylogenetic Tree'. Together they form a unique fingerprint.

Cite this