License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2017.17
URN: urn:nbn:de:0030-drops-76362
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7636/
Go to the corresponding LIPIcs Volume Portal


Nojgaard, Nikolai ; Geiß, Manuela ; Merkle, Daniel ; Stadler, Peter F. ; Wieseke, Nicolas ; Hellmuth, Marc

Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps

pdf-format:
LIPIcs-WABI-2017-17.pdf (0.5 MB)


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 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.

BibTeX - Entry

@InProceedings{nojgaard_et_al:LIPIcs:2017:7636,
  author =	{Nikolai Nojgaard and Manuela Gei{\ss} and Daniel Merkle and Peter F. Stadler and Nicolas Wieseke and Marc Hellmuth},
  title =	{{Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Russell Schwartz and Knut Reinert},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7636},
  URN =		{urn:nbn:de:0030-drops-76362},
  doi =		{10.4230/LIPIcs.WABI.2017.17},
  annote =	{Keywords: Tree Reconciliation, Horizontal Gene Transfer, Reconciliation Map, Time-Consistency, History of gene families}
}

Keywords: Tree Reconciliation, Horizontal Gene Transfer, Reconciliation Map, Time-Consistency, History of gene families
Seminar: 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)
Issue Date: 2017
Date of publication: 03.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI