Biology subjects

Berger, B.

Publications and source records attributed to Berger, B..

66 records · Page 4Linked to original sources

bioRxiv2020

A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets

As the volume of next generation sequencing data increases, an urgent need for algorithms to efficiently process the data arises. Universal hitting sets (UHS) were recently introduced as an alternative to the central idea of minimizers in sequence analysis with the hopes that they could more efficiently address common tasks such as computing hash functions for read overlap, sparse suffix arrays, and Bloom filters. A UHS is a set of k-mers that hit every sequence of length L, and can thus serve as indices to L-long sequences. Unfortunately, methods for computing small UHSs are not yet practical for real-world sequencing instances due to their serial and deterministic nature, which leads to long runtimes and high memory demands when handling typical values of k (e.g. k > 13). To address this bottleneck, we present two algorithmic innovations to significantly decrease runtime while keeping memory usage low: (i) we leverage advanced theoretical and architectural techniques to parallelize and decrease memory usage in calculating k-mer hitting numbers; and (ii) we build upon techniques from randomized Set Cover to select universal k-mers much faster. We implemented these innovations in PASHA, the first randomized parallel algorithm for generating near-optimal UHSs, which newly handles k > 13. We demonstrate empirically that PASHA produces sets only slightly larger than those of serial deterministic algorithms; moreover, the set size is provably guaranteed to be within a small factor of the optimal size. PASHAs runtime and memory-usage improvements are orders of magnitude faster than the current best algorithms. We expect our newly-practical construction of UHSs to be adopted in many high-throughput sequence analysis pipelines.

bioinformatics↗

bioRxiv2019

Topaz-Denoise: general deep denoising models for cryoEM

Cryo-electron microscopy (cryoEM) is becoming the preferred method for resolving protein structures. Low signal-to-noise (SNR) in cryoEM images reduces the confidence and throughput of structure determination during several steps of data processing, resulting in impediments such as missing particle orientations. Denoising cryoEM images can not only improve downstream analysis but also accelerate the time-consuming data collection process by allowing lower electron dose micrographs to be used for analysis. Here, we present Topaz-Denoise, a deep learning method for reliably and rapidly increasing the SNR of cryoEM images and cryoET tomograms. By training on a dataset composed of thousands of micrographs collected across a wide range of imaging conditions, we are able to learn models capturing the complexity of the cryoEM image formation process. The general model we present is able to denoise new datasets without additional training. Denoising with this model improves micrograph interpretability, enabling us to solve the first 3D single particle closed and partially open structures of clustered protocadherin, an elongated particle with previously-elusive views. We then show for the first time that low dose collection, enabled by Topaz-Denoise, improves downstream analysis in addition to reducing data collection time. We also present the first general 3D denoising model for cryoET. Topaz-Denoise and pre-trained general models are now included in Topaz. We expect that Topaz-Denoise will be of broad utility to the cryoEM community for improving micrograph and tomogram interpretability and accelerating analysis.

bioinformatics↗

bioRxiv2019

Schema: A general framework for integrating heterogeneous single-cell modalities

A complete understanding of biological processes requires synthesizing information across heterogeneous modalities, such as age, disease status, or gene/protein expression. Until recently, single-cell profiling experiments could measure only a single modality, leading to analysis focused on integrating information across separate experiments. However, researchers can now measure multiple modalities simultaneously in a single experiment, providing a new data paradigm that enables biological discovery but also requires new conceptual and analytic models. We therefore present Schema, an algorithm that leverages a principled metric learning strategy to synthesize multimodal information from the same experiment. To demonstrate the flexibility and power of our approach, we use Schema to infer cell types by integrating gene expression and chromatin accessibility data, perform differential gene expression analysis while accounting for batch effects and developmental age, estimate evolutionary pressure on peptide sequences, and synthesize spliced and unspliced mRNA data to infer cell differentiation. Schema can synthesize arbitrarily many modalities and capture sophisticated relationships between them, is computationally efficient, and provides a valuable conceptual model for exploring and understanding complex biology.

bioinformatics↗

bioRxiv2019

Hopper: A Mathematically Optimal Algorithm for Sketching Biological Data

Single-cell RNA-sequencing (scRNA-seq) has grown massively in scale since its inception, presenting substantial analytic and computational challenges. Even simple downstream analyses, such as dimensionality reduction and clustering, require days of runtime and hundreds of gigabytes of memory for todays largest datasets. In addition, current methods often favor common cell types, and miss salient biological features captured by small cell populations. Here we present Hopper, a single-cell toolkit that both speeds up the analysis of single-cell datasets and highlights their transcriptional diversity by intelligent subsampling, or sketching. Hopper realizes the optimal polynomial-time approximation of the Hausdorff distance between the full and downsampled dataset, ensuring that each cell is well-represented by some cell in the sample. Unlike prior sketching methods, Hopper adds points iteratively and allows for additional sampling from regions of interest, enabling fast and targeted multi-resolution analyses. In a dataset of over 1.3 million mouse brain cells, we detect a cluster of just 64 macrophages expressing inflammatory tissues (0.004% of the full dataset) from a Hopper sketch containing just 5,000 cells, and several other small but biologically interesting immune cell populations invisible to analysis of the full data. On an even larger dataset consisting of ~2 million developing mouse organ cells, we show even representation of important cell types in small sketch sizes, in contrast with prior sketching methods. By condensing transcriptional information encoded in large datasets, Hopper grants the individual user with a laptop the same analytic capabilities as large consortium.

bioinformatics↗

bioRxiv2019

Coexpression uncovers a unified single-cell transcriptomic landscape

Single-cell transcriptomic studies of diverse and complex systems are becoming ubiquitous. Algorithms now attempt to integrate patterns across these studies by removing all study-specific information, without distinguishing unwanted technical bias from relevant biological variation. Integration remains difficult when capturing biological variation that is distributed across studies, as when combining disparate temporal snapshots into a panoramic, multi-study trajectory of cellular development. Here, we show that a fundamental analytic shift to gene coexpression within clusters of cells, rather than gene expression within individual cells, balances robustness to bias with preservation of meaningful inter-study differences. We leverage this insight in Trajectorama, an algorithm which we use to unify trajectories of neuronal development and hematopoiesis across studies that each profile separate developmental stages, a highly challenging task for existing methods. Trajectorama also reveals systems-level processes relevant to disease pathogenesis within the microglial response to myelin injury. Trajectorama benefits from efficiency and scalability, processing nearly one million cells in around an hour.

bioinformatics↗

bioRxiv2019

Geometric Sketching Compactly Summarizes the Single-Cell Transcriptomic Landscape

Large-scale single-cell RNA-sequencing (scRNA-seq) studies that profile hundreds of thousands of cells are becoming increasingly common, overwhelming existing analysis pipelines. Here, we describe how to enhance and accelerate single-cell data analysis by summarizing the transcriptomic heterogeneity within a data set using a small subset of cells, which we refer to as a geometric sketch. Our sketches provide more comprehensive visualization of transcriptional diversity, capture rare cell types with high sensitivity, and accurately reveal biological cell types via clustering. Our sketch of umbilical cord blood cells uncovers a rare subpopulation of inflammatory macrophages, which we experimentally validated in vitro. The construction of our sketches is extremely fast, which enabled us to accelerate other crucial resource-intensive tasks such as scRNA-seq data integration. We anticipate that our algorithm will become an increasingly essential step when sharing and analyzing the rapidly-growing volume of scRNA-seq data and help enable the democratization of single-cell omics.

bioinformatics↗

bioRxiv2018

Carnelian: alignment-free functional binning and abundance estimation of metagenomic reads

Accurate assignment of metagenomic reads to their functional roles is an important first step towards gaining insights into the relationship between the human microbiomeincluding the collective genesand disease. Existing approaches focus on binning sequencing reads into known taxonomic classes or by genes, often failing to produce results that generalize across different cohorts with the same disease. We present Carnelian, a highly precise and accurate pipeline for alignment-free functional binning and abundance estimation, which leverages the recent idea of even-coverage, low-density locality sensitive hashing. When coupled with one-against-all classifiers, reads can be binned by molecular function encoded in their gene content with higher precision and accuracy. Carnelians minutes-per-metagenome processing speed enables analysis of large-scale disease or environmental datasets to reveal disease- and environment-specific changes in microbial functionality previously poorly understood. Our pipeline newly reveals a functional dysbiosis in patient gut microbiomes, not found in earlier metagenomic studies, and identifies a distinct shift from matched healthy individuals in Type-2 Diabetes (T2D) and early-stage Parkinsons Disease (PD). We remarkably identify a set of functional markers that can differentiate between patients and healthy individuals consistently across both the datasets with high specificity.

bioinformatics↗

bioRxiv2018

Panoramic stitching of heterogeneous single-cell transcriptomic data

Researchers are generating single-cell RNA sequencing (scRNA-seq) profiles of diverse biological systems1-4 and every cell type in the human body.5 Leveraging this data to gain unprecedented insight into biology and disease will require assembling heterogeneous cell populations across multiple experiments, laboratories, and technologies. Although methods for scRNA-seq data integration exist6,7, they often naively merge data sets together even when the data sets have no cell types in common, leading to results that do not correspond to real biological patterns. Here we present Scanorama, inspired by algorithms for panorama stitching, that overcomes the limitations of existing methods to enable accurate, heterogeneous scRNA-seq data set integration. Our strategy identifies and merges the shared cell types among all pairs of data sets and is orders of magnitude faster than existing techniques. We use Scanorama to combine 105,476 cells from 26 diverse scRNA-seq experiments across 9 different technologies into a single comprehensive reference, demonstrating how Scanorama can be used to obtain a more complete picture of cellular function across a wide range of scRNA-seq experiments.

bioinformatics↗

bioRxiv2018

Neural Data Visualization for Scalable and Generalizable Single Cell Analysis

Single-cell RNA sequencing is becoming effective and accessible as emerging technologies push its scale to millions of cells and beyond. Visualizing the landscape of single cell expression has been a fundamental tool in single cell analysis. However, standard methods for visualization, such as t-stochastic neighbor embedding (t-SNE), not only lack scalability to data sets with millions of cells, but also are unable to generalize to new cells, an important ability for transferring knowledge across fast-accumulating data sets. We introduce net-SNE, which trains a neural network to learn a high quality visualization of single cells that newly generalizes to unseen data. While matching the visualization quality of t-SNE on 14 benchmark data sets of varying sizes, from hundreds to 1.3 million cells, net-SNE also effectively positions previously unseen cells, even when an entire subtype is missing from the initial data set or when the new cells are from a different sequencing experiment. Furthermore, given a \"reference\" visualization, net-SNE can vastly reduce the computational burden of visualizing millions of single cells from multiple days to just a few minutes of runtime. Our work provides a general framework for newly bootstrapping single cell analysis from existing data sets.

bioinformatics↗

bioRxiv2017

Latent variable model for aligning barcoded short-reads improves downstream analyses

Recent years have seen the emergence of several \"third-generation\" sequencing platforms, each of which aims to address shortcomings of standard next-generation short-read sequencing by producing data that capture long-range information, thereby allowing us to access regions of the genome that are inaccessible with short-reads alone. These technologies either produce physically longer reads typically with higher error rates or instead capture long-range information at low error rates by virtue of read \"barcodes\" as in 10x Genomics Chromium platform. As with virtually all sequencing data, sequence alignment for third-generation sequencing data is the foundation on which all downstream analyses are based. Here we introduce a latent variable model for improving barcoded read alignment, thereby enabling improved downstream genotyping and phasing. We demonstrate the feasibility of this approach through developing EMerAld-- or EMA for short-- and testing it on the barcoded short-reads produced by 10xs sequencing technologies. EMA not only produces more accurate alignments, but unlike other methods also assigns interpretable probabilities to the alignments it generates. We show that genotypes called from EMAs alignments contain over 30% fewer false positives than those called from Lariats (the current 10x alignment tool), with a fewer number of false negatives, on datasets of NA12878 and NA24385 as compared to NIST GIAB gold standard variant calls. Moreover, we demonstrate that EMA is able to effectively resolve alignments in regions containing nearby homologous elements-- a particularly challenging problem in read mapping-- through the introduction of a novel statistical binning optimization framework, which allows us to find variants in the pharmacogenomically important CYP2D region that go undetected when using Lariat or BWA. Lastly, we show that EMAs alignments improve phasing performance compared to Lariats in both NA12878 and NA24385, producing fewer switch/mismatch errors and larger phase blocks on average.\n\nEMA software and datasets used are available at http://ema.csail.mit.edu.

bioinformatics↗

bioRxiv2017

Metagenomic binning through low density hashing

Bacterial microbiomes of incredible complexity are found throughout the world, from exotic marine locations to the soil in our yards to within our very guts. With recent advances in Next-Generation Sequencing (NGS) technologies, we have vastly greater quantities of microbial genome data, but the nature of environmental samples is such that DNA from different species are mixed together. Here, we present Opal for metagenomic binning, the task of identifying the origin species of DNA sequencing reads. Our Opal method introduces low-density, even-coverage hashing to bioinformatics applications, enabling quick and accurate metagenomic binning. Our tool is up to two orders of magnitude faster than leading alignment-based methods at similar or improved accuracy, allowing computational tractability on large metagenomic datasets. Moreover, on public benchmarks, Opal is substantially more accurate than both alignment-based and alignment-free methods (e.g. on SimHC20.500, Opal achieves 95% F1-score while Kraken and CLARK achieve just 91% and 88%, respectively); this improvement is likely due to the fact that the latter methods cannot handle computationally-costly long-range dependencies, which our even-coverage, low-density fingerprints resolve. Notably, capturing these long-range dependencies drastically improves Opals ability to detect unknown species that share a genus or phylum with known bacteria. Additionally, the family of hash functions Opal uses can be generalized to other sequence analysis tasks that rely on k-mer based methods to encode long-range dependencies.

bioinformatics↗

bioRxiv2017

C. elegans exhibits coordinated oscillation in gene expression during development

BackgroundThe advent of in vivo automated single-cell lineaging and sequencing will dramatically increase our understanding of development. New integrative analysis techniques are needed to generate insights from single-cell developmental data.\n\nResultsWe applied novel meta-analysis techniques to the EPIC single-cell-resolution developmental gene expression dataset for C. elegans to show that a simple linear combination of the expression levels of the developmental genes is strongly correlated with the developmental age of the organism, irrespective of the cell division rate of different cell lineages. We uncovered a pattern of collective sinusoidal oscillation in gene activation, in multiple dominant frequencies and in multiple orthogonal axes of gene expression, pointing to the existence of a coordinated, multi-frequency global timing mechanism. We developed a novel method based on Fishers Discriminant Analysis (FDA) to identify linear gene expression weightings that are able to produce sinusoidal oscillations of any frequency and phase, adding to the evidence that oscillatory mechanisms likely play an important role in the timing of development. We cross-linked EPIC with gene ontology and anatomy ontology terms, employing FDA methods to identify previously unknown positive and negative genetic contributions to developmental processes and cell phenotypes.\n\nConclusionsThis meta-analysis demonstrates new evidence for direct linear and/or sinusoidal mechanisms regulating the timing of development. We uncovered a number of previously unknown positive and negative correlations between developmental genes and developmental processes or cell phenotypes. The presented novel analysis techniques are broadly applicable within developmental biology.

developmental biology↗