License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2017.8
URN: urn:nbn:de:0030-drops-76565
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7656/
El-Mabrouk, Nadia ;
Ouangraoua, Aïda
A General Framework for Gene Tree Correction Based on Duplication-Loss Reconciliation
Abstract
Due to the key role played by gene trees and species phylogenies in biological studies, it is essential to have as much confidence as possible on the available trees. As phylogenetic tools are error-prone, it is a common task to use a correction method for improving an initial tree. Various correction methods exist. In this paper we focus on those based on the Duplication-Loss reconciliation model. The polytomy resolution approach consists in contracting weakly supported branches and then refining the obtained non-binary tree in a way minimizing a reconciliation distance with the given species tree. On the other hand, the supertree approach takes as input a set of separated subtrees, either obtained for separared orthology groups or by removing the upper branches of an initial tree to a certain level, and amalgamating them in an optimal way preserving the topology of the initial trees. The two classes of problems have always been considered as two separate fields, based on apparently different models. In this paper we give a unifying view showing that these two classes of problems are in fact special cases of a more general problem that we call LabelGTC, whose input includes a 0-1 edge-labelled gene tree to be corrected. Considering a tree as a set of triplets, we also formulate the TripletGTC Problem whose input includes a set of gene triplets that should be preserved in the corrected tree. These two general models allow to unify, understand and compare the principles of the duplication-loss reconciliation-based tree correction approaches. We show that LabelGTC is a special case of TripletGTC. We then develop appropriate algorithms allowing to handle these two general correction problems.
BibTeX - Entry
@InProceedings{elmabrouk_et_al:LIPIcs:2017:7656,
author = {Nadia El-Mabrouk and Aida Ouangraoua},
title = {{A General Framework for Gene Tree Correction Based on Duplication-Loss Reconciliation}},
booktitle = {17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
pages = {8:1--8:14},
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/7656},
URN = {urn:nbn:de:0030-drops-76565},
doi = {10.4230/LIPIcs.WABI.2017.8},
annote = {Keywords: Gene tree correction, Supertree, Polytomy, Reconciliation, Phylogeny}
}
|
Keywords: |
|
Gene tree correction, Supertree, Polytomy, Reconciliation, Phylogeny |
|
Collection: |
|
17th International Workshop on Algorithms in Bioinformatics (WABI 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
