Biology subjects

Hakim, S. A.

Publications and source records attributed to Hakim, S. A..

3 recordsLinked to original sources

bioRxiv2025

Quartet-based Genome-scale Species Tree Inference using Multicopy Gene Family Trees

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.

evolutionary biology↗

bioRxiv2024

wQFM-TREE: highly accurate and scalable quartet-based species tree inference from gene trees

Summary methods are becoming increasingly popular for species tree estimation from multi-locus data in the presence of gene tree discordance. ASTRAL, a leading method in this class, solves the Maximum Quartet Support Species Tree problem within a constrained solution space constructed from the input gene trees. In contrast, alternative heuristics such as wQFM and wQMC operate by taking a set of weighted quartets as input and employ a divide-and-conquer strategy to construct the species tree. Recent studies showed wQFM to be more accurate than ASTRAL and wQMC, though its scalability is hindered by the computational demands of explicitly generating and weighting {Theta}(n4) quartets. Here, we introduce wQFM-TREE, a novel summary method that enhances wQFM by circumventing the need for explicit quartet generation and weighting, thereby enabling its application to large datasets. Unlike wQFM, wQFM-TREE can also handle polytomies. Extensive simulations under diverse and challenging model conditions, with hundreds or thousands of taxa and genes, consistently demonstrate that wQFM-TREE matches or improves upon the accuracy of ASTRAL. Specifically, wQFM-TREE outperformed ASTRAL in 25 of 27 model conditions analyzed in this study involving 200-1000 taxa, with statistically significant differences in 20 of these conditions. Moreover, we applied wQFM-TREE to re-analyze the green plant dataset from the One Thousand Plant Transcriptomes Initiative. Its remarkable accuracy and scalability position wQFM-TREE as a highly competitive alternative to leading methods in the field. Additionally, the algorithmic and combinatorial innovations introduced in this study will benefit various quartet-based computations, advancing the state-of-the-art in phylogenetic estimations.

evolutionary biology↗

bioRxiv2023

wQFM-DISCO: DISCO-enabled wQFM improves phylogenomic analyses despite the presence of paralogs

Gene trees often differ from the species trees that contain them due to various factors, including incomplete lineage sorting (ILS), gene duplication and loss (GDL), and horizontal gene transfer (HGT). Several highly accurate species tree estimation methods have been introduced to explicitly address ILS, including AS-TRAL, a widely used statistically consistent method, and wQFM, a quartet amalgamation approach that is experimentally shown to be more accurate than ASTRAL. Two recent advancements, ASTRAL-Pro and DISCO, have emerged in the field of phylogenomics to consider gene duplication and loss (GDL) events. ASTRAL-Pro introduces a refined measure of quartet similarity, accounting for both orthology and paralogy. DISCO, on the other hand, offers a general strategy to decompose multicopy gene family trees into a collection of single-copy trees, allowing the utilization of methods previously designed for species tree inference in the context of single-copy gene trees. In this study, we first introduce some variants of DISCO to examine its underlying hypotheses and present analytical results on the statistical guarantees of DISCO. In particular, we introduce DISCO-R, a variant of DISCO with a refined and improved pruning strategy that provides more accurate and robust results. We then propose wQFM-DISCO (wQFM paired with DISCO) as an adaptation of wQFM to handle multicopy gene trees resulting from GDL events. Extensive evaluation studies on a collection of simulated and real data sets demonstrate that wQFM-DISCO is significantly more accurate than ASTRAL-Pro and other competing methods.

bioinformatics↗