Academic Journal
Reconciling Multiple Genes Trees via Segmental Duplications and Losses
| العنوان: | Reconciling Multiple Genes Trees via Segmental Duplications and Losses |
|---|---|
| المؤلفون: | Dondi, Riccardo, Lafond, Manuel, Scornavacca, Celine |
| المساهمون: | Riccardo Dondi and Manuel Lafond and Celine Scornavacca |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2018 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | Gene trees/species tree reconciliation, phylogenetics, computational complexity, fixed-parameter algorithms |
| الوصف: | Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently. However, it is well-known that the evolution of gene families is interconnected. In this paper, we extend a previous approach to reconcile a set of gene trees with a species tree based on segmental macro-evolutionary events, where segmental duplication events and losses are associated with cost delta and lambda, respectively. We show that the problem is polynomial-time solvable when delta <= lambda (via LCA-mapping), while if delta > lambda the problem is NP-hard, even when lambda = 0 and a single gene tree is given, solving a long standing open problem on the complexity of the reconciliation problem. On the positive side, we give a fixed-parameter algorithm for the problem, where the parameters are delta/lambda and the number d of segmental duplications, of time complexity O(ceil[delta/lambda]^d * n * delta/lambda). Finally, we demonstrate the usefulness of this algorithm on two previously studied real datasets: we first show that our method can be used to confirm or refute hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.5 |
| DOI: | 10.4230/LIPIcs.WABI.2018.5 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.WABI.2018.5 https://nbn-resolving.org/urn:nbn:de:0030-drops-93079 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.5 |
| Rights: | https://creativecommons.org/licenses/by/3.0/legalcode |
| رقم الانضمام: | edsbas.8AC9D17B |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.WABI.2018.5 |
|---|