Inferring incomplete lineage sorting, duplications, transfers and losses with reconciliations

• Published in: Journal of theoretical biology 2017-11, Vol.432, p.1-13
• Main Authors: Chan, Yao-ban, Ranwez, Vincent, Scornavacca, Céline
• Format: Article
• Language: English
• Subjects: Algorithms; Bioinformatics; Computer Science; Gene Duplication; Gene transfer; Gene Transfer, Horizontal; Haploidy; Incomplete lineage sorting; Models, Genetic; Parsimony; Phylogeny; Reconciliation
• ISSN: 0022-5193; 1095-8541
• DOI: 10.1016/j.jtbi.2017.08.008

•A new formal model of reconciliations between a gene and species tree is proposed.•This model includes duplications, losses, transfers, and incomplete lineage sorting.•A practical algorithm to find the most optimal reconciliation is developed.•A formal proof of the correctness of this algorithm is given.•A detailed comparison is made between this algorithm and similar methods. Gene trees and species trees can be discordant due to several processes. Standard models of reconciliations consider macro-evolutionary events at the gene level: duplications, losses and transfers of genes. However, another common source of gene tree-species tree discordance is incomplete lineage sorting (ILS), whereby gene divergences corresponding to speciations occur “out of order”. However, ILS is seldom considered in reconciliation models. In this paper, we devise a unified formal IDTL reconciliation model which includes all the above mentioned processes. We show how to properly cost ILS under this model, and then give a fixed-parameter tractable (FPT) algorithm which calculates the most parsimonious IDTL reconciliation, with guaranteed time-consistency of transfer events. Provided that the number of branches in contiguous regions of the species tree in which ILS is allowed is bounded by a constant, this algorithm is linear in the number of genes and quadratic in the number of species. This provides a formal foundation to the inference of ILS in a reconciliation framework.