Name
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 and , respectively. We show that the problem is polynomial-time solvable when (via LCA-mapping), while if the problem is NP-hard, even when 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 and the number of segmental duplications, of time complexity . 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.WABI.2018.5 | workshop on algorithms in bioinformatics |
Keywords | DocType | Volume |
Fixed-parameter tractability,Gene trees,NP-hardness,Phylogenetics,Reconciliation,Segmental duplications,Species trees,Whole genome duplications | Conference | abs/1806.03988 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Riccardo Dondi | 1 | 89 | 18.42 |
| Manuel Lafond | 2 | 3 | 1.41 |
| Celine Scornavacca | 3 | 26 | 3.73 |