Gentrius: identifying equally scoring trees in phylogenomics with incomplete data

Abstract Phylogenetic trees are routinely built from huge and yet incomplete multi-locus datasets often leading to phylogenetic terraces – topologically distinct equally scoring trees, which induce the same set of per locus subtrees. As typical tree inference software outputs only a single tree, identifying all trees with identical score challenges phylogenomics. Generating all trees from a terrace requires constructing a so-called stand for the corresponding set of induced locus subtrees. Here, we introduce Gentrius – an efficient algorithm that tackles this problem for unrooted trees. Despite stand generation being computationally intractable, we showed on simulated and biological datasets that Gentrius generates stands with millions of trees in feasible time. Depending on the distribution of missing data across species and loci and the inferred phylogeny, the number of equally optimal terrace trees varies tremendously. The strict consensus tree computed from them displays all the branches unaffected by the pattern of missing data. Thus, Gentrius provides an important systematic assessment of phylogenetic trees inferred from incomplete data. Furthermore, Gentrius can aid theoretical research by fostering understanding of tree space structure imposed by missing data. One-Sentence Summary Gentrius - the algorithm to generate a complete stand, i.e. all binary unrooted trees compatible with the same set of subtrees.