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 λ, respectively. We show that the problem is polynomial-time solvable when δ ≤ λ (via LCA-mapping), while if $$δ > lambda $$ δ > λ the problem is NP-hard, even when λ = 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 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.
(2019). Reconciling multiple genes trees via segmental duplications and losses [journal article - articolo]. In ALGORITHMS FOR MOLECULAR BIOLOGY. Retrieved from http://hdl.handle.net/10446/150285
Reconciling multiple genes trees via segmental duplications and losses
Dondi, Riccardo;
2019-01-01
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 λ, respectively. We show that the problem is polynomial-time solvable when δ ≤ λ (via LCA-mapping), while if $$δ > lambda $$ δ > λ the problem is NP-hard, even when λ = 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 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.File | Dimensione del file | Formato | |
---|---|---|---|
AlgoMolBiol2019.pdf
accesso aperto
Versione:
publisher's version - versione editoriale
Licenza:
Creative commons
Dimensione del file
2.54 MB
Formato
Adobe PDF
|
2.54 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo