Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees

DOI10.1137/22M150736XarXiv2112.00403OpenAlexW4387060342MaRDI QIDQ6072286FDOQ6072286

Authors: David Schaller, Marc Hellmuth, Peter F. Stadler 

Publication date: 13 October 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Horizontal gene transfer events partition a gene tree $T$ and thus, its leaf set into subsets of genes whose evolutionary history is described by speciation and duplication events alone. Indirect phylogenetic methods can be used to infer such partitions $mathcalP$ from sequence similarity or evolutionary distances without any a priory knowledge about the underlying tree $T$. In this contribution, we assume that such a partition $mathcalP$ of a set of genes $X$ is given and that, independently, an estimate $T$ of the original gene tree on $X$ has been derived. We then ask to what extent $T$ and the xenology information, i.e., $mathcalP$ can be combined to determine the horizontal transfer edges in $T$. We show that for each pair of genes $x$ and $y$ with $x,y$ being in different parts of $mathcalP$, it can be decided whether there always exists or never exists a horizontal gene transfer in $T$ along the path connecting $y$ and the most recent common ancestor of $x$ and $y$. This problem is equivalent to determining the presence or absence of the directed edge $(x,y)$ in so-called Fitch graphs; a more fine-grained version of graphs that represent the dependencies between the sets in $mathcalP$. We then consider the generalization to insufficiently resolved gene trees and show that analogous results can be obtained. We show that the classification of $(x,y)$ can be computed in constant time after linear-time preprocessing. Using simulated gene family histories, we observe empirically that the vast majority of horizontal transfer edges in the gene tree $T$ can be recovered unambiguously.

Full work available at URL: https://arxiv.org/abs/2112.00403

zbMATH Keywords

partitionlinear-time algorithmhorizontal gene transferxenologyFitch graphgene families

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) General biology and biomathematics (92B05)

Cites Work

• Title not available (Why is that?)
• Lowest common ancestors in trees and directed acyclic graphs
• The level ancestor problem simplified
• Finding level-ancestors in trees
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Orthology relations, symbolic ultrametrics, and cographs
• Compatibility of partitions with trees, hierarchies, and split systems
• Reconstructing gene trees from Fitch's xenology relation
• Forbidden time travel: characterization of time-consistent tree reconciliation maps
• A short note on undirected Fitch graphs
• Best match graphs
• Complete characterization of incorrect orthology assignments in best match graphs
• Indirect identification of horizontal gene transfer
• Alternative characterizations of Fitch's xenology relation
• Complexity of modification problems for best match graphs
• Best match graphs with binary trees
• Least resolved trees for two-colored best match graphs

Cited In (1)

• Computing and Combinatorics

This page was built for publication: Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072286)