Resolution and reconciliation of non-binary gene trees with transfers, duplications and losses

MotivationGene trees reconstructed from sequence alignments contain poorly supported branches when the phylogenetic signal in the sequences is weak. When a species tree is available, the signal of gains and losses of genes can be used to correctly resolve the unsupported parts of the gene history. Unfortunately, finding the best (i.e. most parsimonious) resolution has been shown to be NP-hard if transfers are considered as possible gene scale events, in addition to gene originations, duplications and losses.\n\nResultsWe propose an exact, parameterized algorithm solving this problem in single-exponential time, where the parameter is the number of connected branches of the gene tree that show low support from the sequence alignment or, equivalently, the maximum number of children of any node of the gene tree once the low-support branches have been collapsed. We propose a way to choose among optimal solutions based on the available information. We show the usability of this principle on several simulated and biological data sets. The results show a comparable or better quality than several other tested methods having similar goals, but with a lower running time and a guarantee on the optimality of the solution.\n\nAvailabilityOur algorithm has been integrated into the ecceTERA phylogeny package, available at http://mbb.univ-montp2.fr/MBB/download_sources/16_ecceTERA and which can be run online at http://mbb.univ-montp2.fr/MBB/subsection/softExec.php?soft=eccetera.\n\nContactceline.scornavacca@umontpellier.fr