2018/06/11 by Dondi, Riccardo, Lafond, Manuel, Scornavacca, Celine · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Populations and Evolution (q-bio.PE)
paper · doi:10.48550/arxiv.1806.03988
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 δ and λ, respectively. We show that the problem is polynomial-time solvable when δ≤ λ (via LCA-mapping), while if δ> λ 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 the reconciliation problem. On the positive side, we give a fixed-parameter algorithm for the problem, where the parameters are δ/λ and the number d of segmental duplications, of time complexity O(\lceil \fracδλ \rceild ⋅ n ⋅ \fracδλ). 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.