Forbidden time travel

Characterization of time-consistent tree reconciliation maps

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

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

24 Downloads (Pure)

Resumé

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 eventlabeled 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. Significance: 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.

OriginalsprogEngelsk
Titel17th International Workshop on Algorithms in Bioinformatics, WABI 2017
RedaktørerRussel Schwartz, Knut Reinert
Udgivelses stedDagstuhl
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2017
Artikelnummer17
ISBN (Elektronisk)9783959770507
DOI
StatusUdgivet - 2017
Begivenhed17th International Workshop on Algorithms in Bioinformatics, WABI 2017 - Boston, USA
Varighed: 21. aug. 201723. aug. 2017

Konference

Konference17th International Workshop on Algorithms in Bioinformatics, WABI 2017
LandUSA
ByBoston
Periode21/08/201723/08/2017
NavnLeibniz International Proceedings in Informatics
Vol/bind88
ISSN1868-8969

Fingeraftryk

travel time
gene
gene transfer
history

Citer dette

Nøjgaard, N., Geiß, M., Merkle, D., Stadler, P. F., Wieseke, N., & Hellmuth, M. (2017). Forbidden time travel: Characterization of time-consistent tree reconciliation maps. I R. Schwartz, & K. Reinert (red.), 17th International Workshop on Algorithms in Bioinformatics, WABI 2017 [17] Dagstuhl: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, Bind. 88 https://doi.org/10.4230/LIPIcs.WABI.2017.17
Nøjgaard, Nikolai ; Geiß, Manuela ; Merkle, Daniel ; Stadler, Peter F. ; Wieseke, Nicolas ; Hellmuth, Marc. / Forbidden time travel : Characterization of time-consistent tree reconciliation maps. 17th International Workshop on Algorithms in Bioinformatics, WABI 2017. red. / Russel Schwartz ; Knut Reinert. Dagstuhl : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, Bind 88).
@inproceedings{8b85c79c12124a11ba4aed9032818a06,
title = "Forbidden time travel: Characterization of time-consistent tree reconciliation maps",
abstract = "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 eventlabeled 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. Significance: 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.",
keywords = "History of gene families, Horizontal Gene Transfer, Reconciliation Map, Time- Consistency, Tree Reconciliation",
author = "Nikolai N{\o}jgaard and Manuela Gei{\ss} and Daniel Merkle and Stadler, {Peter F.} and Nicolas Wieseke and Marc Hellmuth",
year = "2017",
doi = "10.4230/LIPIcs.WABI.2017.17",
language = "English",
editor = "Russel Schwartz and Knut Reinert",
booktitle = "17th International Workshop on Algorithms in Bioinformatics, WABI 2017",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

}

Nøjgaard, N, Geiß, M, Merkle, D, Stadler, PF, Wieseke, N & Hellmuth, M 2017, Forbidden time travel: Characterization of time-consistent tree reconciliation maps. i R Schwartz & K Reinert (red), 17th International Workshop on Algorithms in Bioinformatics, WABI 2017., 17, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Dagstuhl, Leibniz International Proceedings in Informatics, bind 88, 17th International Workshop on Algorithms in Bioinformatics, WABI 2017, Boston, USA, 21/08/2017. https://doi.org/10.4230/LIPIcs.WABI.2017.17

Forbidden time travel : Characterization of time-consistent tree reconciliation maps. / Nøjgaard, Nikolai; Geiß, Manuela; Merkle, Daniel; Stadler, Peter F.; Wieseke, Nicolas; Hellmuth, Marc.

17th International Workshop on Algorithms in Bioinformatics, WABI 2017. red. / Russel Schwartz; Knut Reinert. Dagstuhl : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 17 (Leibniz International Proceedings in Informatics, Bind 88).

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

TY - GEN

T1 - Forbidden time travel

T2 - Characterization of time-consistent tree reconciliation maps

AU - Nøjgaard, Nikolai

AU - Geiß, Manuela

AU - Merkle, Daniel

AU - Stadler, Peter F.

AU - Wieseke, Nicolas

AU - Hellmuth, Marc

PY - 2017

Y1 - 2017

N2 - 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 eventlabeled 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. Significance: 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.

AB - 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 eventlabeled 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. Significance: 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.

KW - History of gene families

KW - Horizontal Gene Transfer

KW - Reconciliation Map

KW - Time- Consistency

KW - Tree Reconciliation

U2 - 10.4230/LIPIcs.WABI.2017.17

DO - 10.4230/LIPIcs.WABI.2017.17

M3 - Article in proceedings

BT - 17th International Workshop on Algorithms in Bioinformatics, WABI 2017

A2 - Schwartz, Russel

A2 - Reinert, Knut

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

CY - Dagstuhl

ER -

Nøjgaard N, Geiß M, Merkle D, Stadler PF, Wieseke N, Hellmuth M. Forbidden time travel: Characterization of time-consistent tree reconciliation maps. I Schwartz R, Reinert K, red., 17th International Workshop on Algorithms in Bioinformatics, WABI 2017. Dagstuhl: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. 17. (Leibniz International Proceedings in Informatics, Bind 88). https://doi.org/10.4230/LIPIcs.WABI.2017.17