Biology subjects

Nakhleh, L.

Publications and source records attributed to Nakhleh, L..

At least 19 recordsLinked to original sources

bioRxiv2026

DIMPLE: A Tree-Guided Divide-and-Conquer Framework for ILS-Aware Phylogenetic Network Inference on Large-Scale Data

Inferring evolutionary histories of species provides a foundation for comparative genomics and evolutionary analyses. Extensive evidence of reticulate evolution motivates the inference of phylogenetic networks, which represent relationships that species trees cannot capture. However, accurate reconstruction of large phylogenetic networks remains a major challenge because of the vast space of possible network topologies. Here, we propose DIMPLE, a divide-and-conquer framework for phylogenetic network inference without an explicit restriction on network level. DIMPLE uses a tree-of-blobs (TOB), which represents the tree-like relationships between regions of potential reticulation while leaving relationships within those regions unresolved. Within each unresolved region, DIMPLE partitions the set of taxa into pairwise-disjoint subsets, each containing at most a user-specified number of taxa. Multiple division runs are allowed, and subsets from different runs may overlap. DIMPLE infers a subnetwork on each subset, merges the subnetworks within each region, and uses the TOB to assemble the resulting networks into a network on the full taxon set. Experiments with true inputs demonstrate accurate merging, with improved reticulation recovery over existing methods on higher-level networks. With estimated inputs, DIMPLE achieves competitive topological accuracy and more consistently recovers hybrid ancestry than competing methods across varying levels of network complexity. Its computational requirements support analyses of hundreds of taxa. Applications to fern and gymnosperm datasets recover documented hybridization and previously reported phylogenetic conflict.

bioinformatics↗

bioRxiv2026

Kente: A Graph-based Pangenomic Approach for Horizontal Gene Transfer Detection in Microbiomes

MotivationHorizontal gene transfer (HGT) shapes bacterial evolution and microbial ecosystems, yet detecting HGT within microbiomes remains a challenge due to fragmented metagenomic assemblies, reference bias, reliance on gene boundaries, and limited ability to model structural mosaicism and patterns across genomes. MethodsWe present Kente, a novel pangenome graph-based framework designed for HGT detection that aligns metagenomic assembly contigs to a curated database of >600 genus-level bacterial pangenome graphs constructed using minigraph. Kente infers local taxonomic composition along contigs using alignment evidence and classifies candidate transfers using structured clade-transition topologies (e.g., A-B-A sandwich, open tips, and mosaic patterns). A complementary intra-genus module detects inter-species transfers within a single genus graph using segment-level clade annotations. ResultsAcross simulated intra- and inter-genus transfer scenarios, Kente achieves higher precision and comparable recall relative to existing gene-centric microbiome HGT detection approaches while reducing false positives from fragmented assemblies. Application to real human gut metagenomes (HMP2, n = 26) demonstrates Kentes ability to detect candidate cross-lineage transfer regions in complex microbial communities. Runtime profiling shows near-linear scaling with input size, enabling efficient analysis of large metagenomic assemblies. Availability and Implementationhttps://github.com/treangenlab/Kente

bioinformatics↗

bioRxiv2026

Leveraging spectrum of graph sheaf Laplacian as a genome-architecture-aware measure of microbiome diversity

MotivationMeasures of microbial diversity that can be derived directly from metagenomic sequencing data offer a valuable summary view of the underlying complex systems. Prior work has shown that both taxonomic composition and abundances that are captured by standard diversity measures (e.g., Shannon entropy), and structural variation within the metagenome due to gene duplications, losses and horizontal transfers (HGT), can correlate with the hosts health. However, there are no diversity measures available that simultaneously account for the genome architecture and taxonomic composition within the sample. Thus, in this work we propose the spectral energy of a graph sheaf Laplacian as such a measure, and justify its applicability through a simulation study and analysis of biological data. ResultsFirst, we describe a theoretical framework that allows us to combine the features of genome graphs with the taxonomic data. Then, we explore the sensitivity of the proposed diversity measure to genome rearrangements and HGT events in a simulation study. Finally, we explore applicability of our proposed measure to characterization of diversity of human gut metagenomes. We find our proposed measure to offer better discrimination between healthy controls and inflammatory bowel disease (IBD) patients samples (n = 403) in the cohorts analyzed. Availability and Implementationhttps://github.com/nsapoval/bd-gsl

bioinformatics↗

bioRxiv2026

On the consistency of duplication, loss, and deep coalescence gene tree parsimony costs under the multispecies coalescent

Gene tree parsimony (GTP) is a common approach for efficient reconciliation of multiple discordant gene tree phylogenies for the inference of a single species tree. However, despite the popularity of GTP methods due to their low computational costs, prior work has shown that some commonly employed parsimony costs are statistically inconsistent under the multispecies coalescent process. Furthermore, a fine-grained analysis of the inconsistency has indicated potentially complementary behavior of duplication and deep coalescence costs for symmetric and asymmetric species trees. In this work, we prove inconsistency of GTP estimators for all linear combinations of duplication, loss, and deep coalescence scores. We also explore empirical implications of this result by evaluating inference results of several GTP cost schemes under varying levels of incomplete lineage sorting.

bioinformatics↗

bioRxiv2025

GRNITE: Gene Regulatory Network Inference with Text Embeddings

Gene regulatory networks (GRNs) capture complex regulatory relationships that govern gene expression in cells. Inference of GRNs from single-cell RNA-seq (scRNA-seq) data has been an active topic of research in the past several years. However, despite the improvements in the data quality, the GRN inference problem remains a challenging task with many approaches showing variable performance dependent on the organism and cell type. To improve the quality of GRN inference and enable more comprehensive exploratory analyses of GRNs across various phenotypes of interest, we developed a two-stage meta-method called GRNITE. In the first step, GRNITE leverages LLM-based embeddings of plain text gene descriptions to create a prior gene interaction graph, which is then optimized with a graph neural network (GNN) to achieve a "universal" biological prior for GRN inference. In the second step, GRNITE uses a GNN to incorporate information from a GRN inferred from scRNA-seq data with any baseline inference method into our prior. The result of this two-step approach is a near-universal improvement in AUROC and recall of all evaluated methods, with minor trade-offs in precision. Furthermore, GRNITE is a lightweight meta-method, which adds a minimal amount of extra compute time on top of the original GRN inference performed. GRNITE and our pre-trained universal prior GRN are available on GitHub: https://github.com/aliaaz99/GRNITE.

bioinformatics↗

bioRxiv2025

Impact of Data Error on Phylogenetic Network Inference from Gene Trees Under the Multispecies Network Coalescent

Phylogenetic network inference has become an essential tool in evolutionary biology, offering a framework to model complex evolutionary events such as hybridization and horizontal gene transfer. However, a critical but often overlooked challenge is the presence of error in empirical datasets, including sequencing errors, misalignments, and inaccuracies in gene tree estimation. This issue is particularly pressing in the context of phylogenetic networks, which can contain an arbitrary number of parameters and are thus highly susceptible to overfitting. Errors in the input data can lead to artificially inflated network complexity, misrepresenting evolutionary history with non-biological reticulations. In this study,we systematically examine how different sources of data error influence network inference and show that many widely used methods are vulnerable to these distortions. We find that inaccuracies in gene tree estimation and sequence alignment degrade the reliability of inferred networks. These issues are exacerbated when the number of reticulations that an algorithm can infer exceeds the true number of reticulations in the phylogenetic network. Our analysis underscores the importance of accounting for data error when applying network inference methods and provides practical recommendations for minimizing its impact. By highlighting the vulnerabilities of different approaches and demonstrating how errors propagate through the inference process, we offer practical recommendations for optimizing data processing pipelines. Our findings emphasize the necessity of integrating realistic error models into species network inference methods to enhance their reliability and applicability to real-world biological datasets.

bioinformatics↗

bioRxiv2025

Intratumor Heterogeneity Through the Lens of Gene Regulatory Networks

Intratumor heterogeneity (ITH), the presence of heterogeneous genomic and transcriptomic populations in tumor and its implications for the cancer therapies has been one of the focal points of computational cancer biology in the past years. While ITH is well characterized at the genomic level, the regulatory wiring connecting clonal genotypes to transcriptional states remains largely unmapped. To understand whether the evidence for ITH at the gene regulatory level can be inferred from scRNA-seq data, we analyzed scRNA-seq datasets spanning triple-negative breast cancer, colorectal cancer, glioblastoma, and a longitudinal stage IV breast cancer cohort, inferring clone-specific gene regulatory networks (GRNs) and developing quantitative tools to compare them: a Wasserstein distance-based measure of regulatory divergence, a kth order neighborhood similarity framework distinguishing structural from functional rewiring, bootstrap-based edge confidence, and an integrated regulon classification pipeline. Our analyses demonstrate that tumor clones exhibit reproducibly distinct network architectures, and dominant clones show significantly greater regulatory divergence from normal cells than smaller clones, linking regulatory rewiring to clonal fitness. Treatment-induced remodeling exceeds clonal variation, with rewiring exhibiting structural divergence but functional convergence. Regulon analysis further resolved clone-variable, sample-specific, and broadly conserved programs, some of which containing transcription factors whose target genes independently were associated with patient survival.

bioinformatics↗

bioRxiv2025

Inferring Phylogenetic Trees of Cancer Evolution from Longitudinal Single-Cell Copy Number Profiles

Understanding evolutionary dynamics is critical for unraveling the complex progression of diseases such as cancer. Cancer evolution is inherently a temporal process driven by the accumulation of mutations and clonal expansions over time. Traditional phylogenetic methods often rely solely on static, cross-sectional data, limiting their ability to infer the timing of key evolutionary events. To address this challenge, we developed NestedBD-Long, a novel method that integrates temporal data from longitudinal sampling into phylogenetic analyses using the birthdeath evolutionary model on copy numbers. This approach allows for the direct mapping of real-world time onto inferred evolutionary trees, providing a clearer and more accurate representation of cancers evolutionary trajectory. Evaluations demonstrate that NestedBD-Long outperforms traditional approaches, with accuracy improving as the number of temporal sampling points increases. This advancement provides a powerful framework for studying tumor progression, treatment resistance, and metastatic spread by capturing the dynamics between evolutionary events and real-world timelines. NestedBD-Long is available at https://github.com/Androstane/NestedBD.

cancer biology↗

bioRxiv2025

tMHG-Finder: Tree-guided Maximal Homologous Group Finder for Bacterial Genomes

A maximal homologous group, or MHG, as a group of sequences with a shared evolutionary ancestry, shifts the focus from a genecentric view to a homology-centric view in comparative genomic studies. Each MHG is formed by identifying and grouping all homologous sequences, which ensures that evolutionary events, such as horizontal gene transfer, gene duplication and loss, or de novo sequence evolution, are encapsulated within the same MHG. However, the current MHG computation tool, MHG-Finder, faces challenges in scalability to handle large datasets and lacks the ability to provide detailed insights into intermediate MHGs involving subsets of input genomes. We present tMHG-Finder (https://github.com/yongze-yin/tMHG-Finder), a new method that improves our previous method, MHG-Finder, by utilizing a guide tree to significantly improve scalability and provide more informative biological results. We also introduce a new measure, fractionalization (available at https://github.com/yongze-yin/Fract-Calculator), to assess the accuracy of delineated MHGs compared to ground truth data. Our results show that tMHG-Finder scales linearly with the number of taxa, requiring a small fraction of the computational time of MHG-Finder. Furthermore, according to the fractionalization measure, tMHG-Finder outperforms four state-of-the-art whole-genome aligners on simulated data. Applying tMHG-Finder to a phylum of extreme-environment-resistant bacteria, we validated our results through the encapsulation of 16S rRNA sequences within MHGs. We further investigated how evolutionary rates change with phylogenetic distance and explored the functional roles of genes captured by conserved MHGs, demonstrating the broader utility of tMHG-Finder in uncovering evolutionary insights beyond MHG delineation and phylogenetic relationships.

evolutionary biology↗

bioRxiv2025

Theoretical and Empirical Performance of Pseudo-likelihood-based Bayesian Inference of Species Trees under the Multispecies Coalescent

Likelihood-based inference under the multispecies coalescent provides accurate estimates of species trees. However, maximum likelihood and Bayesian inference are both computationally very demanding. Pseudo-likelihood has been previously proposed as a computationally efficient alternative to full phylogenetic likelihood calculations in the context of maximum likelihood estimation. However, theoretical and practical aspects of pseudo-likelihood in the context of Bayesian inference have not been explored. In this work, we provide strong theoretical guarantees and an empirical evaluation of pseudo-likelihood-based Bayesian inference of species trees under the multispecies coalescent. Our contributions are threefold. First, we prove a bound on the convergence rate for species tree topology inference and a Bernstein-von Mises result for branch lengths under model misspecification. Second, we provide an empirical comparison of full- and pseudo-likelihood-based Bayesian inference on synthetic data. Finally, we demonstrate the practical scalability of pseudo-likelihood-based inference by analyzing two biological datasets.

bioinformatics↗

bioRxiv2024

A Divide-and-Conquer Approach to Large-Scale Evolutionary Analysis of Single-Cell DNA Data

Single-cell sequencing technology is producing large datasets, often containing thousands or even tens of thousands of single-cell genomic data points from an individual patient. Evolutionary analyses of these data sets help uncover and order genetic variants in the data as well as elucidate mutation trees and intra-tumor heterogeneity (ITH) in the case of cancer data sets. To enable such large-scale analyses computationally, we propose a divide-and-conquer approach that could be used to scale up computationally intensive inference methods. The approach consists of four steps: 1) partitioning the dataset into subsets, 2) constructing a rooted tree for each subset, 3) computing a representative genotype for each subset by utilizing its inferred tree, and 4) assembling the individual trees using a tree built on the representative genotypes. Besides its flexibility and enabling scalability, this approach also lends itself naturally to ITH analysis, as the clones would be the individual subsets, and the "assembly tree" could be the mutation tree that defines the clones. To demonstrate the effectiveness of our proposed approach, we conducted experiments employing a range of methods at each stage. In particular, as clustering and dimensionality reduction methods are commonly used to tame the complexity of large datasets in this area, we analyzed the performance of a variety of such methods within our approach.

cancer biology↗

bioRxiv2022

The impact of model misspecification on phylogenetic network inference

1The development of statistical methods to infer species phylogenies with reticulations (species networks) has led to many discoveries of gene flow between distinct species. These methods typically assume only incomplete lineage sorting and introgression. Given that phylogenetic networks can be arbitrarily complex, these methods might compensate for model misspecification by increasing the number of dimensions beyond the true value. Herein, we explore the effect of potential model misspecification, including the negligence of gene tree estimation error (GTEE) and assumption of a single substitution rate for all genomic loci, on the accuracy of phylogenetic network inference using both simulated and biological data. In particular, we assess the accuracy of estimated phylogenetic networks as well as test statistics for determining whether a network is the correct evolutionary history, as opposed to the simpler model that is a tree. We found that while GTEE negatively impacts the performance of test statistics to determine the "tree-ness" of the evolutionary history of a data set, running those tests on triplets of taxa and correcting for multiple testing significantly ameliorates the problem. We also found that accounting for substitution rate heterogeneity improves the reliability of full Bayesian inference methods of phylogenetic networks, whereas summary statistic methods are robust to GTEE and rate heterogeneity, though currently require manual inspection to determine the network complexity.

evolutionary biology↗

bioRxiv2022

Comparing Inference under the MSC versus the MSC-with-Recombination

Accurate inference of population parameters plays a pivotal role in unravelling the evolutionary histories. While recombination has been universally accepted as a fundamental process in the evolution of sexually reproducing organisms, it remains challenging to model it exactly. Thus, existing coalescent-based approaches make different assumptions or approximations to facilitate phylogenetic inference, which can potentially bring about biases in estimates of evolutionary parameters when recombination is present. In this article, we evaluate the performance of population parameters estimation using three classes of methods: StarBEAST2, SNAPP, and diCal2. We performed whole-genome simulations in which recombination rates, mutation rates, and levels of ILS were varied. We show that StarBEAST2 using short or medium-sized loci is robust to realistic rates of recombination, which is in agreement with previous studies. SNAPP, as expected, is generally unaffected by recombination events. Most surprisingly, diCal2, a method that is designed to explicitly account for recombination, performs considerably worse than other methods under comparison.

evolutionary biology↗

bioRxiv2022

MaCroDNA: Accurate integration of single-cell DNA and RNA data for a deeper understanding of tumor heterogeneity

Cancers develop and progress as mutations accumulate, and with the advent of single-cell DNA and RNA sequencing, researchers can observe these mutations, their transcriptomic effects, and predict proteomic changes with remarkable temporal and spatial precision. However, to connect genomic mutations with their transcriptomic and proteomic consequences, cells with either only DNA data or only RNA data must be mapped to a common domain. For this purpose, we present MaCroDNA, a novel method which uses maximum weighted bipartite matching of per-gene read counts from single-cell DNA and RNA-seq data. Using ground truth information from colorectal cancer data, we demonstrate the overwhelming advantage of MaCroDNA over existing methods in accuracy and speed. Exemplifying the utility of single-cell data integration in cancer research, we propose, based on results derived using MaCroDNA, that genomic mutations of large effect size increasingly contribute to differential expression between cells as Barretts esophagus progresses to esophageal cancer.

cancer biology↗

bioRxiv2022

MoTERNN: Classifying the Mode of Cancer Evolution Using Recursive Neural Networks

With the advent of single-cell DNA sequencing, it is now possible to infer the evolutionary history of thousands of tumor cells obtained from a single patient. This evolutionary history, which takes the shape of a tree, reveals the mode of evolution of the specific cancer under study and, in turn, helps with clinical diagnosis, prognosis, and therapeutic treatment. In this study we focus on the question of determining the mode of evolution of tumor cells from their inferred evolutionary history. In particular, we employ recursive neural networks that capture tree structures to classify the evolutionary history of tumor cells into one of four modes--linear, branching, neutral, and punctuated. We trained our model, MoTERNN, using simulated data in a supervised fashion and applied it to a real phylogenetic tree obtained from single-cell DNA sequencing data. MoTERNN is implemented in Python and is publicly available at https://github.com/NakhlehLab/MoTERNN.

cancer biology↗

bioRxiv2022

"Correcting'' gene trees to be more like species trees increases topological error when incomplete lineage sorting is high

The evolutionary histories of individual loci in a genome can be estimated independently, but this approach is error-prone due to the limited amount of sequence data available for each gene, which has led to the development of a diverse array of gene tree error correction methods which reduce distance to the species tree. We investigate the performance of two representatives of these methods: TRACTION and TreeFix, in the case where incomplete lineage sorting is high. We found that gene tree error correction only increases the level of error in gene tree topologies by "correcting" them to be closer to the species tree, even when the true gene and species trees are discordant. We confirm that full Bayesian inference of the gene trees under the multispecies coalescent model is more accurate than independent inference. Gene tree correction must be considered a multi-locus task where the gene tree distribution is taken into account, rather than treating gene trees independently. Significance statementGene tree information is essential for studying elucidating gene, genome, species, and phenotypic evolution, and a wide array of phylogenetic methods have been developed for gene tree estimation. Given that gene tree estimates are often inaccurate, several methods for "correcting" gene tree estimates have been devised. Here we show that correction methods that neglect the distribution of gene trees that is induced by the species phylogeny could produce poor results, calling for the development of species phylogeny-aware gene tree correction.

evolutionary biology↗

bioRxiv2022

Phylogenetic Network Dissimilarity Measures That Take Branch Lengths Into Account

Dissimilarity measures for phylogenetic trees have long been used for analyzing inferred trees and understanding the performance of phylogenetic methods. Given their importance, a wide array of such measures have been developed, some of which are based on the tree topologies alone, and others that also take branch lengths into account. Similarly, a number of dissimilarity measures of phylogenetic networks have been developed in the last two decades. However, to the best of our knowledge, all these measures are based solely on the topologies of phylogenetic networks and ignore branch lengths. In this paper, we propose two phylogenetic network dissimilarity measures that take both topology and branch lengths into account. We demonstrate the behavior of these two measures on pairs of related networks. Furthermore, we show how these measures can be used to cluster a set of phylogenetic networks obtained by an inference method, illustrating this application on the posterior sample of phylogenetic networks. Both measures are implemented in the publicly available software package PhyloNet.

evolutionary biology↗

bioRxiv2022

NestedBD: Bayesian Inference of Phylogenetic Trees From Single-Cell DNA Copy Number Profile Data Under a Birth-Death Model

Copy number aberrations (CNAs) are ubiquitous in many types of cancer. Inferring CNAs from cancer genomic data could help shed light on the initiation, progression, and potential treatment of cancer. While such data have traditionally been available via "bulk sequencing", the more recently introduced techniques for single-cell DNA sequencing (scDNAseq) provide the type of data that makes CNA inference possible at the single-cell resolution. In this paper, we introduce a new birth-death evolutionary model of CNAs as well as a Bayesian method, NestedBD, for the inference of evolutionary trees (topologies and branch lengths with relative mutation rates) from single-cell data under this model. We assessed the accuracy of our method on both simulated and biological data and compared it to the accuracy of two standard phylogenetic tools, namely neighbor-joining and maximum parsimony (MP). We show through simulations that our method infers more accurate topologies and branch lengths. We also studied the ancestral state reconstruction accuracy with the birth-death evolutionary model and found it outperformed MP. Finally, running all three methods on a colorectal cancer data set, we observed that among all three methods, only the phylogeny inferred by NestedBD clearly separated the primary tumor cells from the metastatic ones, providing a more plausible history of the tumor cells.

cancer biology↗