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

DOI10.1137/22M150736XMaRDI QIDQ6072286zbMATH OpenOpenAlexFDO

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)

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)

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.

Cites work

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

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)