Improved robustness to gene tree incompleteness, estimation errors, and systematic homology errors with weighted TREE-QMC

Abstract

Summary methods are widely used to reconstruct species trees from gene trees while accounting for incomplete lineage sorting; however, it is increasingly recognized that their accuracy can be negatively impacted by incomplete and/or error-ridden gene trees. To address the latter, Zhang and Mirarab (2022) leverage gene tree branch lengths and support values to weight quartets within the popular summary method ASTRAL. Although these quartet weighting schemes improved the robustness of ASTRAL to gene tree estimation error, implementing the weighting schemes presented computational challenges, resulting in the authors abandoning ASTRALs original search algorithm (i.e., computing an exact solution within a constrained search space) in favor of search heuristics (i.e., hill climbing with nearest neighbor interchange moves from a starting tree constructed via randomized taxon addition). Here, we show that these quartet weighting schemes can be leveraged within the Quartet Max Cut framework of Snir and Rao (2010), with only a small increase in time complexity compared to the unweighted algorithm, which behaves more like a constant factor in our simulation study. Moreover, our new algorithm, implemented within the TREE-QMC software, was highly competitive with weighted ASTRAL, even outperforming it in terms of species tree accuracy on some challenging model conditions, such as large numbers of taxa. In comparing unweighted and weighted summary methods on two avian data sets, we found that weighting quartets by gene tree branch lengths improves their robustness to systematic homology errors and is as effective as removing the impacted taxa from individual gene trees or removing the impacted gene trees entirely. Lastly, our study revealed that TREE-QMC is highly robust to high rates of missing data and is promising as a supertree method. TREE-QMC is written in C++ and is publicly available on Github: https://github.com/molloy-lab/TREE-QMC