Forbidden time travel: characterization of time-consistent tree reconciliation maps

DOI10.4230/LIPICS.WABI.2017.17zbMATH Open1443.92122arXiv1705.02179OpenAlexW2964144002MaRDI QIDQ5111818FDOQ5111818

Daniel Merkle, Nicolas Wieseke, Peter F. Stadler, Manuela Geiß, Nikolai Nøjgaard, Marc Hellmuth

Publication date: 27 May 2020

Abstract: In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to event-labeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V(S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems.

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

Recommendations

• Gene tree reconciliation including transfers with replacement is NP-hard and FPT
• Exploring the space of gene/species reconciliations with transfers
• Gene tree species tree reconciliation with gene conversion
• A linear-time algorithm for reconciliation of non-binary gene tree and binary species tree
• Inferring incomplete lineage sorting, duplications, transfers and losses with reconciliations

zbMATH Keywords

time-consistencytree reconciliationhorizontal gene transferhistory of gene familiesreconciliation map

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Problems related to evolution (92D15)

Cites Work

• Jungles: A new solution to the host/parasite phylogeny reconciliation problem
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Orthology relations, symbolic ultrametrics, and cographs
• On Symbolic Ultrametrics, Cotree Representations, and Cograph Edge Decompositions and Partitions
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations

Cited In (4)

• Reconstructing gene trees from Fitch's xenology relation
• Complete characterization of incorrect orthology assignments in best match graphs
• Indirect identification of horizontal gene transfer
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees

This page was built for publication: Forbidden time travel: characterization of time-consistent tree reconciliation maps

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