2026-07-22T01:33:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7636 2024-03-12T11:58:14Z ddc:004 open_access

Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps Nojgaard, Nikolai Geiß, Manuela Merkle, Daniel Stadler, Peter F. Wieseke, Nicolas Hellmuth, Marc Tree Reconciliation Horizontal Gene Transfer Reconciliation Map Time-Consistency History of gene families Motivation: 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. Results: 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 algorithms are implemented in C++ using the boost graph library and are freely available at https://github.com/Nojgaard/tc-recon. Significance: The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with hor- izontal 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikolai Nojgaard and Manuela Geiß and Daniel Merkle and Peter F. Stadler and Nicolas Wieseke and Marc Hellmuth 2017 Is Part Of LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2017.17 urn:nbn:de:0030-drops-76362 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.17 eng https://creativecommons.org/licenses/by/3.0/legalcode