Highly Accurate Species Tree Inference from Orthologs and Paralogs through Scalable Quartet Amalgamation

Species tree estimation from multi-copy gene family trees, including both paralogs and orthologs, is a challenging task due to gene tree discordance caused by biological processes such as incomplete lineage sorting (ILS) and gene duplication and loss (GDL). Summary methods, specially quartet-based species tree estimation methods, such as ASTRAL and quartet amalgamation-based methods in the Quartet MaxCut (QMC) and Quartet Fiduccia--Mattheyses (QFM) frameworks, have gained substantial popularity for their accuracy and statistical guarantee. However, most of the summary methods rely on single-copy gene trees and do not explicitly account for GDL, which limits their applicability to large genomic datasets containing multi-copy gene families. ASTRAL-Pro incorporates both orthology and paralogy for species tree inference under GDL by employing a refined quartet similarity measure based on the concept of speciation-driven quartets (SQs). In this study, we propose wQFM-GDL, the first successful initiative to model GDL in a quartet amalgamation-based summary method, using the SQ-based techniques effectively within the QFM framework. This required substantial algorithmic re-engineering, including the development of efficient techniques for computing the initial bipartition in QFM and novel combinatorial methods for computing refined quartet scores directly from gene family trees. In addition, we introduce a locus-aware quartet weight normalization scheme for QFM framework under GDL, which significantly increased the accuracy of our method. We extensively evaluated our method, wQFM-GDL, on benchmark simulated and empirical datasets and compared it with leading methods, including ASTRAL-Pro3, SpeciesRax, FastMulRFS, and DupLoss-2. wQFM-GDL outperforms all other methods in 134 out of 156 model conditions considered in this study, with performance differences becoming more pronounced as dataset size increases. In particular, for larger datasets with 200 and 500 taxa, wQFM-GDL significantly outperforms all the competing methods across all 72 model conditions and achieves, on average, nearly a 25% reduction in reconstruction error compared with ASTRAL-Pro3. wQFM-GDL is freely available in open-source form at https://github.com/abdur-rafi/wQFM-GDL.