Terraces in Species Tree Inference from Gene Trees

Abstract

A terrace in a phylogenetic tree space is a region where all trees contain the same set of subtrees, due to certain patterns of missing data among the taxa sampled, resulting in an identical optimality score for a given data set. This was first investigated in the context of phylogenetic tree estimation from sequence alignments using maximum likelihood (ML) and maximum parsimony (MP). The concept of terraces was later extended to the species tree inference problem from a collection of gene trees, where a set of equally optimal species trees was referred to as a "pseudo" species tree terrace. Pseudo terraces do not consider the topological proximity of the trees in terms of the induced subtrees resulting from certain patterns of missing data. In this study, we mathematically characterize species tree terraces and investigate the mathematical properties and conditions that lead multiple species trees to induce/display an identical set of locus-specific subtrees owing to missing data. We report that species tree terraces are agnostic to gene tree topologies and the discordance therein. Therefore, we introduce and characterize a special type of gene tree topology-aware terrace which we call "peak terrace", and investigate conditions on the patterns of missing data that give rise to peak terraces. In addition to the theoretical and analytical results, we empirically investigated different challenges as well as various opportunities pertaining to the multiplicity of equally good species trees in terraced landscapes. Based on an extensive experimental study involving both simulated and real biological datasets, we present the prevalence of species tree terraces and the resulting ambiguity created for tree search algorithms. Remarkably, our findings indicate that the identification of terraces and the trees within them can substantially enhance the accuracy of summary methods. Furthermore, we demonstrate that reasonably accurate branch support can be computed by leveraging trees sourced from these terraces.