Reconciling multiple genes trees via segmental duplications and losses
Abstract 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 prev...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2019-03-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13015-019-0139-6 |
| _version_ | 1818260454486573056 |
|---|---|
| author | Riccardo Dondi Manuel Lafond Celine Scornavacca |
| author_facet | Riccardo Dondi Manuel Lafond Celine Scornavacca |
| author_sort | Riccardo Dondi |
| collection | DOAJ |
| description | Abstract 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 \le \lambda $$ δ≤λ (via LCA-mapping), while if $$\delta > \lambda $$ δ>λ the problem is NP-hard, even when $$\lambda = 0$$ λ=0 and a single gene tree is given, solving a long standing open problem on the complexity of multi-gene reconciliation. 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\left(\lceil \frac{\delta }{\lambda } \rceil ^{d} \cdot n \cdot \frac{\delta }{\lambda }\right)$$ O⌈δλ⌉d·n·δλ . 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 raise doubt on hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes. |
| first_indexed | 2024-12-12T18:31:35Z |
| format | Article |
| id | doaj.art-31a08a5b3c734f34827359d93878babb |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-12-12T18:31:35Z |
| publishDate | 2019-03-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-31a08a5b3c734f34827359d93878babb2022-12-22T00:15:53ZengBMCAlgorithms for Molecular Biology1748-71882019-03-0114111910.1186/s13015-019-0139-6Reconciling multiple genes trees via segmental duplications and lossesRiccardo Dondi0Manuel Lafond1Celine Scornavacca2Dipartimento di Filosofia, Lettere, Comunicazione, Università degli Studi di BergamoDepartment of Computer Science, Universitè de SherbrookeISEM, CNRS, IRD, EPHE, Universit de MontpellierAbstract 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 \le \lambda $$ δ≤λ (via LCA-mapping), while if $$\delta > \lambda $$ δ>λ the problem is NP-hard, even when $$\lambda = 0$$ λ=0 and a single gene tree is given, solving a long standing open problem on the complexity of multi-gene reconciliation. 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\left(\lceil \frac{\delta }{\lambda } \rceil ^{d} \cdot n \cdot \frac{\delta }{\lambda }\right)$$ O⌈δλ⌉d·n·δλ . 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 raise doubt on hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes.http://link.springer.com/article/10.1186/s13015-019-0139-6PhylogeneticsGene treesSpecies treesReconciliationSegmental duplicationsFixed-parameter tractability |
| spellingShingle | Riccardo Dondi Manuel Lafond Celine Scornavacca Reconciling multiple genes trees via segmental duplications and losses Algorithms for Molecular Biology Phylogenetics Gene trees Species trees Reconciliation Segmental duplications Fixed-parameter tractability |
| title | Reconciling multiple genes trees via segmental duplications and losses |
| title_full | Reconciling multiple genes trees via segmental duplications and losses |
| title_fullStr | Reconciling multiple genes trees via segmental duplications and losses |
| title_full_unstemmed | Reconciling multiple genes trees via segmental duplications and losses |
| title_short | Reconciling multiple genes trees via segmental duplications and losses |
| title_sort | reconciling multiple genes trees via segmental duplications and losses |
| topic | Phylogenetics Gene trees Species trees Reconciliation Segmental duplications Fixed-parameter tractability |
| url | http://link.springer.com/article/10.1186/s13015-019-0139-6 |
| work_keys_str_mv | AT riccardodondi reconcilingmultiplegenestreesviasegmentalduplicationsandlosses AT manuellafond reconcilingmultiplegenestreesviasegmentalduplicationsandlosses AT celinescornavacca reconcilingmultiplegenestreesviasegmentalduplicationsandlosses |