Biology subjects

Molloy, E. K.

Publications and source records attributed to Molloy, E. K..

10 recordsLinked to original sources

bioRxiv2026

Scalable localization of clustering instability for spatial transcriptomics

Standard spatial transcriptomics workflows rely on clustering methods to define regions of interest for downstream analyses, such as differential expression and pathway enrichment. Although researchers are presented with a single partition, most clustering methods are stochastic, meaning their output depends on random algorithmic choices, typically controlled by a seed; thus, repeating the analysis changing only the seed can yield a different result. Spatial transcriptomics data may be especially sensitive to algorithmic perturbations due to high dimensionality, sparsity, and mixed expression profiles at tissue boundaries and transitional zones; however, the extent of seed-dependent variation and its downstream impact have yet to be systematically evaluated. To bridge this gap, we present InSTability, a framework that localizes disagreement among partitions at the observation level. InSTability is built on (1) an interpretable, per-spot score that quantifies the variability of a spot's cluster assignment across partitions, and (2) an algorithm with time complexity linear in the number of spots for a specified number of runs for computing the instability score at all spots. Together, these advances enable spatially-resolved clustering instability maps for large, high-resolution datasets. Applying InSTability to repeated runs of seven established methods (BayesSpace, GraphST, Leiden, Louvain, SEDR, STAGATE, and SpiceMix) on 18 benchmark samples reveals that clustering instability varies across tissue sections, with shared spatial patterns emerging among different methods applied to the same sample. Furthermore, clustering instability correlates with poor agreement against reference annotations and propagates downstream into differential expression analyses, resulting in inconsistent gene sets across seeds. Thus, InSTability can strengthen spatial transcriptomics studies by highlighting regions where clustering is seed-sensitive and further validation is warranted. InSTability is open-source and available at https://github.com/molloy-lab/InSTability.

bioinformatics↗

bioRxiv2024

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

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

bioinformatics↗

bioRxiv2023

On the use of quartets for reconstructing cell lineage trees under an unbiased error and missingness model

Cancer progression and treatment can be informed by reconstructing its evolutionary history from tumor cells. However, traditional methods assume the input data are error-free and the output tree is fully resolved. These assumptions are challenged in tumor phylogenetics because single-cell sequencing produces sparse, error-ridden data and because tumors evolve clonally. Here, we find that methods based on quartets (four-leaf, unrooted trees) withstand these barriers. We consider a popular tumor phylogenetics model, in which mutations arise on a (highly unresolved) tree and then (unbiased) errors and missing values are introduced. Quartets are implied by mutations present in two cells and absent from two cells. Our main result is that the most probable quartet identifies the unrooted model tree on four cells. This motivates seeking a tree such that the number of quartets shared between it and the input mutations is maximized. We prove an optimal solution is a consistent estimator of the unrooted cell lineage tree; this guarantee includes the case where the model tree is highly unresolved, with error defined as the number of false negative branches. Lastly, we outline how quartet-based methods might be employed when there are copy number aberrations and other challenges specific to tumor phylogenetics.

evolutionary biology↗

bioRxiv2021

Inferring population structure in biobank-scale genomic data

Inferring the structure of human populations from genetic variation data is a key task in population and medical genomic studies. While a number of methods for population structure inference have been proposed, current methods are impractical to run on biobank-scale genomic datasets containing millions of individuals and genetic variants. We introduce SCOPE, a method for population structure inference that is orders of magnitude faster than existing methods while achieving comparable accuracy. SCOPE infers population structure in about a day on a dataset containing one million individuals and variants as well as on the UK Biobank dataset containing 488,363 individuals and 569,346 variants. Furthermore, SCOPE can leverage allele frequencies from previous studies to improve the interpretability of population structure estimates.

bioinformatics↗

bioRxiv2021

Advancing admixture graph estimation via maximum likelihood network orientation

MotivationAdmixture, the interbreeding between previously distinct populations, is a pervasive force in evolution. The evolutionary history of populations in the presence of admixture can be modeled by augmenting phylogenetic trees with additional nodes that represent admixture events. While enabling a more faithful representation of evolutionary history, admixture graphs present formidable inferential challenges, and there is an increasing need for methods that are accurate, fully automated, and computationally efficient. One key challenge arises from the size of the space of admixture graphs. Given that exhaustively evaluating all admixture graphs can be prohibitively expensive, heuristics have been developed to enable efficient search over this space. One heuristic, implemented in the popular method TreeMix, consists of adding edges to a starting tree while optimizing a suitable objective function. ResultsHere, we present a demographic model (with one admixed population incident to a leaf) where TreeMix and any other starting-tree-based maximum likelihood heuristic using its likelihood function is guaranteed to get stuck in a local optimum and return an incorrect network topology. To address this issue, we propose a new search strategy that we term maximum likelihood network orientation (MLNO). We augment TreeMix with an exhaustive search for a MLNO, referring to this approach as OrientA-Graph. In evaluations including previously published admixture graphs, OrientAGraph outperformed TreeMix on 4/8 models (there are no differences in the other cases). Overall, OrientAGraph found graphs with higher likelihood scores and topological accuracy while remaining computationally efficient. Lastly, our study reveals several directions for improving maximum likelihood admixture graph estimation. AvailabilityOrientAGraph is available under the GNU General Public License v3.0 on Github (https://github.com/sriramlab/OrientAGraph).

evolutionary biology↗

bioRxiv2020

ILS-Aware Analyses of Retroelement Insertions in the Anomaly Zone

A potential shortcoming of concatenation methods for species tree estimation is their failure to account for incomplete lineage sorting. Coalescent methods address this problem but make various assumptions that, if violated, can result in worse performance than concatenation. Given the challenges of analyzing DNA sequences with both concatenation and coalescent methods, retroelement insertions (RIs) have emerged as powerful phylogenomic markers for species tree estimation. Here, we show that two recently proposed quartet-based methods, SDPquartets and ASTRAL BP, are statistically consistent estimators of the unrooted species tree topology under the coalescent when RIs follow a neutral infinite-sites model of mutation and the expected number of new RIs per generation is constant across the species tree. The accuracy of these (and other) methods for inferring species trees from RIs has yet to be assessed on simulated data sets, where the true species tree topology is known. Therefore, we evaluated eight methods given RIs simulated from four model species trees, all of which have short branches and at least three of which are in the anomaly zone. In our simulation study, ASTRAL BP and SDPquartets always recovered the correct species tree topology when given a sufficiently large number of RIs, as predicted. A distance-based method (ASTRID BP) and Dollo parsimony also performed well in recovering the species tree topology. In contrast, unordered, polymorphism, and Camin-Sokal parsimony typically fail to recover the correct species tree topology in anomaly zone situations with more than four ingroup taxa. Of the methods studied, only ASTRAL BP automatically estimates internal branch lengths (in coalescent units) and support values (i.e. local posterior probabilities). We examined the accuracy of branch length estimation, finding that estimated lengths were accurate for short branches but upwardly biased otherwise. This led us to derive the maximum likelihood (branch length) estimate for when RIs are given as input instead of binary gene trees; this corrected formula produced accurate estimates of branch lengths in our simulation study, provided that a sufficiently large number of RIs were given as input. Lastly, we evaluated the impact of data quantity on species tree estimation by repeating the above experiments with input sizes varying from 100 to 100 000 parsimony-informative RIs. We found that, when given just 1 000 parsimony-informative RIs as input, ASTRAL BP successfully reconstructed major clades (i.e clades separated by branches > 0.3 CUs) with high support and identified rapid radiations (i.e. shorter connected branches), although not their precise branching order. The local posterior probability was effective for controlling false positive branches in these scenarios.

evolutionary biology↗

bioRxiv2020

Advancing Divide-and-Conquer Phylogeny Estimation

One of the Grand Challenges in Science is the construction of the Tree of Life, an evolutionary tree containing several million species, spanning all life on earth. However, the construction of the Tree of Life is enormously computationally challenging, as all the current most accurate methods are either heuristics for NP-hard optimization problems or Bayesian MCMC methods that sample from tree space. One of the most promising approaches for improving scalability and accuracy for phylogeny estimation uses divide-and-conquer: a set of species is divided into overlapping subsets, trees are constructed on the subsets, and then merged together using a "supertree method". Here, we present Exact-RFS-2, the first polynomial-time algorithm to find an optimal supertree of two trees, using the Robinson-Foulds Supertree (RFS) criterion (a major approach in supertree estimation that is related to maximum likelihood supertrees), and we prove that finding the RFS of three input trees is NP-hard. We also present GreedyRFS (a greedy heuristic that operates by repeatedly using Exact-RFS-2 on pairs of trees, until all the trees are merged into a single supertree). We evaluate Exact-RFS-2 and GreedyRFS, and show that they have better accuracy than the current leading heuristic for RFS. Exact-RFS-2 and GreedyRFS are available in open source form on Github at github.com/yuxilin51/GreedyRFS.

bioinformatics↗

bioRxiv2019

FastMulRFS: Statistically consistent polynomial time species tree estimation under gene duplication

MotivationSpecies tree estimation is a basic part of biological research but can be challenging because of gene duplication and loss (GDL), which results in genes that can appear more than once in a given genome. All common approaches in phylogenomic studies either reduce available data or are error-prone, and thus, scalable methods that do not discard data and have high accuracy on large heterogeneous datasets are needed. ResultsWe present FastMulRFS, a polynomial-time method for estimating species trees without knowledge of orthology. We prove that FastMulRFS is statistically consistent under a generic model of GDL when adversarial GDL does not occur. Our extensive simulation study shows that FastMulRFS matches the accuracy of MulRF (which tries to solve the same optimization problem) and has better accuracy than prior methods, including ASTRAL-multi (the only method to date that has been proven statistically consistent under GDL), while being much faster than both methods. AvailabilityFastMulRFS is available on Github (https://github.com/ekmolloy/fastmulrfs).

evolutionary biology↗

bioRxiv2019

Polynomial-Time Statistical Estimation of Species Trees under Gene Duplication and Loss

Phylogenomics--the estimation of species trees from multilocus datasets--is a common step in many biological studies. However, this estimation is challenged by the fact that genes can evolve under processes, including incomplete lineage sorting (ILS) and gene duplication and loss (GDL), that make their trees different from the species tree. In this paper, we address the challenge of estimating the species tree under GDL. We show that species trees are identifiable under a standard stochastic model for GDL, and that the polynomial-time algorithm ASTRAL-multi, a recent development in the ASTRAL suite of methods, is statistically consistent under this GDL model. We also provide a simulation study evaluating ASTRAL-multi for species tree estimation under GDL. All scripts and datasets used in this study are available on the Illinois Data Bank: https://doi.org/10.13012/B2IDB-2626814_V1.

evolutionary biology↗

bioRxiv2018

Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge

BackgroundDivide-and-conquer methods, which divide the species set into over-lapping subsets, construct a tree on each subset, and then combine the subset trees using a supertree method, provide a key algorithmic framework for boosting the scalability of phylogeny estimation methods to large datasets. Yet the use of supertree methods, which typically attempt to solve NP-hard optimization problems, limits the scalability of such approaches.\n\nResultsIn this paper, we introduce a divide-and-conquer approach that does not require supertree estimation: we divide the species set into pairwise disjoint subsets, construct a tree on each subset using a base method, and then combine the subset trees using a distance matrix. For this merger step, we present a new method, called NJMerge, which is a polynomial-time extension of Neighbor Joining (NJ); thus, NJMerge can be viewed either as a method for improving traditional NJ or as a method for scaling the base method to larger datasets. We prove that NJMerge can be used to create divide-and-conquer pipelines that are statistically consistent under some models of evolution. We also report the results of an extensive simulation study evaluating NJMerge on multi-locus datasets with up to 1000 species. We found that NJMerge sometimes improved the accuracy of traditional NJ and substantially reduced the running time of three popular species tree methods (ASTRAL-III, SVDquartets, and \"concatenation\" using RAxML) without sacrificing accuracy. Finally, although NJMerge can fail to return a tree, in our experiments, NJMerge failed on only 11 out of 2560 test cases.\n\nConclusionsTheoretical and empirical results suggest that NJMerge is a valuable technique for large-scale phylogeny estimation, especially when computational resources are limited. NJMerge is freely available on Github (http://github.com/ekmolloy/njmerge).

evolutionary biology↗