bioRxiv Science⌕ Search

Biology subjects

Patro, R.

Publications and source records attributed to Patro, R..

At least 19 recordsLinked to original sources

Gravlax: an annotation-independent molecular evidence archive for single-cell RNA-seq

A cell-by-gene count matrix is the artifact of a single-cell RNA-seq experiment that is most often stored, shared, and reanalyzed. It is the output of a computation whose inputs are the sequenced molecules and a gene annotation, and while the molecules never change, the annotation is revised continually. Once the matrix has been produced, the evidence behind it can no longer be reinterpreted. Recovering that evidence means returning to raw reads or alignments that are large, costly to process, and frequently unavailable. We ask whether a concise representation of the molecules themselves can be extracted once and reused indefinitely, to quantify under any future annotation, to query and discover features that no annotation yet describes, and to pool evidence across cells and samples. Our starting observation is that the procedures that turn alignments into counts, gene assignment and UMI collapse, never read most of what an alignment file contains. They consume relations among molecules such as shared genomic geometry, shared placements, barcode identity, and the equality or near-equality of UMIs. We show that these relations form a statistic that is sufficient for such consumers, and we design a compact, seekable, content-authenticated archive that stores them while deferring every annotation-dependent decision to analysis time. Archives compose into content-addressed collections that route cohort queries to the molecules that can answer them without copying molecules. We implement these ideas in a tool called gravlax. Across four human 10x 3' datasets, gravlax archives require 11--18 bits per read and are 9.0--12.7x smaller than tag-preserving CRAM. Count matrices replayed from an archive deviate from direct STARsolo quantification by 0.24--0.75% of normalized UMI mass, whereas changing GENCODE v32 to v49 moves 2.12--4.64%, and quantification replay is 34--82x faster than STARsolo at matched thread budgets. A federated index over eight archives occupies 2.96% of their size, answers a 96-query junction panel 2.59x faster than the archives alone, and screens the cohort genome-wide for unannotated splice events that recur across donors in just 9 seconds. Because the molecules are retained, the archives also answer questions the matrix has discarded. An analysis of four peripheral-blood archives recovers a validated FYB1 immune-cell splicing switch, a cross-fitted fragment model appropriate for 3' chemistry reveals an eight-donor shift in NTRK2 terminal-isoform usage from astrocyte and neural-stem-cell populations to mature neurons, and pooling evidence across cells within the context of an expectation-maximization algorithm recovers 75--98% of withheld multi-gene molecule labels. Gravlax is open source, implemented in Rust, licensed under the BSD 3-clause license, and available at https://github.com/COMBINE-lab/gravlax.

bioinformatics↗

Bramble: projection of spliced genomic alignments into transcriptomic space for improved transcript quantification

Accurate transcript abundance estimation is central to many transcriptomic studies. Many current quantification methods rely on reads mapped directly to the transcriptome, but transcriptome alignment can misassign reads from unannotated transcripts to annotated isoforms, leading to biased abundance estimates. We introduce Bramble, a method that projects spliced genomic alignments into transcriptomic coordinates to produce alignments compatible with downstream transcript quantification tools. Across simulated short- and long-read RNA-seq datasets and multiple levels of reference annotation completeness, incorporating Bramble into quantification pipelines consistently improved accuracy and reduced error. These results suggest that genome-derived transcriptomic alignments can improve transcript quantification by preserving compatible alignments to annotated transcripts while filtering alignments likely originating from unannotated transcripts.

genomics↗

Scientific computing in the age of agentic AI: an exploratory field report

Scientific computing has become a central component of modern scientific discovery. Yet many computational tools are developed by small, specialized teams under incentives that encourage the release of rapidly prototyped tooling without commensurate attention to engineering concerns, including performance and maintainability. These gaps are particularly visible in the life sciences, where the advent of high-throughput sequencing and molecular profiling has made the production and processing of datasets routine at scales that strain reliability and cost. Recently, LLM-based agents have become increasingly capable, with publicly available systems possessing both significant domain knowledge in many scientific fields and the ability to autonomously operate over complex and specialized codebases in pursuit of well-defined goals. Together, these developments create a practical opportunity for scientific computing. Many of the persistent weaknesses of the scientific computing ecosystem stem from technical debt and a shortage of sustained engineering labor and expertise. Here, we examine coding agents as a potential way to address these weaknesses: we present an exploratory field report of eight early case studies in the application of LLM agents to scientific computing across a range of project scopes, from lightweight maintenance tasks to full performance-oriented rewrites of scientific libraries, with a focus on the life sciences. Each of these case studies is accompanied by reflections from the individual or group responsible for the work, including lessons from the process. Overall, we find that the use of coding agents in scientific computing holds great promise for accelerating scientific research and increasing the reliability of critical systems, but that outstanding concerns remain, including responsibility and ownership for such projects, and we suggest collaboration and stewardship with existing maintainers when feasible.

bioinformatics↗

seqproc: An efficient, flexible, and concise tool for sequence geometry description and transformation

Complex sequencing protocols encode technical information in read structure and require accurate, e[ff]icient preprocessing. We introduce seqproc, which compiles concise sequence-geometry descriptions into execution graphs. Across four single-cell RNA-sequencing protocols, seqproc has the lowest mean runtime at every tested thread count and uses substantially less memory than the next-fastest tool. It has the highest F1 agreement with conservative structural references on all three discriminative chemistries and ties both alternatives on the 10x length-filter control. By separating protocol description from execution, seqproc makes complex read transformations compact, reusable, and efficient.

bioinformatics↗

Highly Constrained Kinetic Models for Single-Cell Gene Expression Analysis

Advances in single-cell RNA sequencing (scRNA-seq) and high-resolution imaging techniques, such as single-molecule tracking (SMT) of RNA and transcription factors, allow researchers to quantitatively explore dynamics and variation but have never been integrated into a single coherent model. In this study, we propose a kinetic model that intakes multiple data types, including steady-state and time-resolved datasets, to simulate and fit stochastic models of gene transcription to experimental data. We find that 3-state models provide an essential improvement over the widely used 2-state model for most genes and have the property of kinetic proofreading, which we argue is advantageous in the cellular context. We further identify two dimensionless quantities derived from the rate equations which are broadly conserved across genes. Finally, we extend this model to scRNA-seq datasets to infer kinetic rates under defined perturbations and reveal biochemical insight into the mechanism of action of transcription factors.

bioinformatics↗

kache-hash: A dynamic, concurrent, and cache-efficient hash table for streaming k-mer operations

MotivationHash tables are fundamental to computational genomics, where keys are often k-mers--fixed-length substrings that exhibit a "streaming" property: consecutive k-mers share k-1 nucleotides and are processed in order. Existing static data structures exploit this locality but cannot support dynamic updates, while state-of-the-art concurrent hash tables support dynamic operations but ignore k-mer locality. ResultsWe introduce kache-hash, the first dynamic, concurrent, and resizable hash table that exploits k-mer locality. kache-hash builds on Iceberg hashing--a multi-level design achieving stability and low associativity--but replaces generic hashing with minimizer-based hashing, ensuring that consecutive k-mers map to the same buckets. This keeps frequently accessed buckets cache-resident during streaming operations. On the human genome, kache-hash achieves 1.58-2.62x higher insertion throughput than IcebergHT and up to 6.1x higher query throughput, while incurring 7.39x fewer cache misses. kache-hash scales near-linearly to 16 threads and supports dynamic resizing without sacrificing locality. Our theoretical analysis proves that streaming k-mer operations achieve [O](1/r) amortized cache misses per operation, where r is the minimizer run length, explaining the substantial performance gains over general-purpose hash tables. Availabilitykache-hash is implemented in C++20 and is available at https://github.com/jamshed/kache-hash. Contactp.pandey@northeastern.edu Supplementary informationSupplementary material are available for this manuscript.

bioinformatics↗

Optimizing sparse and skew hashing: faster k-mer dictionaries

MotivationRepresenting a set of k-mers -- strings of length k -- in small space under fast lookup queries is a fundamental requirement for several applications in Bioinformatics. A data structure based on sparse and skew hashing (SSHash) was recently proposed for this purpose [Pibiri, 2022]: it combines good space effectiveness with fast lookup and streaming queries. It is also order-preserving, i.e., consecutive k-mers (sharing a prefix-suffix overlap of length k-1) are assigned consecutive hash codes which helps compressing satellite data typically associated with k-mers, like abundances and color sets in colored De Bruijn graphs. ResultsWe study the problem of accelerating queries under the sparse and skew hashing indexing paradigm, without compromising its space effectiveness. We propose a refined data structure with less complex lookups and fewer cache misses. We give a simpler and faster algorithm for streaming lookup queries. Compared to indexes with similar capabilities and based on the Burrows-Wheeler transform, like SBWT and FMSI, SSHash is significantly faster to build and query. SSHash is competitive in space with the fast (and default) modality of SBWT when both k-mer strands are indexed. While larger than FMSI, it is also more than one order of magnitude faster to query. Availability and ImplementationThe SSHash software is available at https://github.com/jermp/sshash, and also distributed via Bioconda. A benchmark of data structures for k-mer sets is available at https://github.com/jermp/kmer_sets_benchmark. The datasets used in this article are described and available at https://zenodo.org/records/17582116. Contactgiulioermanno.pibiri@unive.it, rob@cs.umd.edu.

bioinformatics↗

mim: A lightweight auxiliary index to enable fast, parallel, gzipped FASTQ parsing

The FASTQ file format is the lingua franca of primary data distribution and processing across most of bioinformatics. Over time, the compression, storage, transmission, and decompression of gzip compressed fastq.gz files has become a substantial scalability bottleneck in the modern world of fast and massively parallel genomics tools and algorithms. In this work, we introduce mim: a lightweight, auxiliary index that enables fast, parallel, and highly-scalable parsing of compressed fastq.gz files. The creation of the mim index for a file is a one-time operation that can be performed in time comparable to that of simply decompressing and parsing the file (index creation induces [~] 20% overhead) and with minimal working memory. The mim index itself is very small, usually about [Formula]th of the size of the original compressed file, and can be easily stored along side the file or fetched from a remote location when it is needed. Further, the mim index is purely additive -- it does not modify the original gzipped FASTQ file in any way, nor require that the file be recompressed or rewritten -- and thus it does not require converting the massive back catalog of existing raw sequencing data. To demonstrate the feasibility and utility of the mim index, we benchmark construction of the mim index on a variety of existing gzipped FASTQ data, and also measure thread-scaling of mim index-assisted parallel FASTQ parsing on a simple parsing/ decompression-related task. We find that, for the one-time cost of index creation, and a small fraction of extra storage space, the mim index can massively accelerate the ingestion and parsing of gzipped FASTQ data, exhibiting near linear thread scaling in our experiments. mim is written in C++17, and is available as open source software under a BSD 3-clause license at https://github.com/COMBINE-lab/mim.

bioinformatics↗

QCatch: A framework for quality control assessment and analysis of single-cell sequencing data

MotivationSingle-cell sequencing data analysis requires robust quality control (QC) to mitigate technical artifacts and ensure reliable downstream results. While tools like alevin-fry and simpleaf (and augmented execution context for the alevin-fry), offer flexibility and computational efficiency to process single-cell data, this ecosystem will further benefit from a standardized QC reporting tailored for its outputs. ResultsWe introduce QCatch, a Python-based command-line tool that generates comprehensive and interactive HTML QC reports designed specifically for single-cell quantification results. Taking the output directory of alevin-fry or simpleaf as the input, QCatch is able to perform essential processing steps, like cell calling, and generate detailed QC reports that contain informative visualizations and statistics, including unique molecular identifier (UMI) count distributions, sequencing saturation estimates, and splicing status information, for QC assurance. Built for seamless integration into downstream analysis workflows, QCatch exports the processed results in a richly-annotated H5AD format file, a widely used data format common among many downstream single-cell data analysis tools. AvailabilityThe source code and documentation of QCatch are available on GitHub at https://github.com/COMBINE-lab/QCatch. QCatch can be installed via both Bioconda and PyPI.

bioinformatics↗

Kaminari: a resource-frugal index for approximate colored k-mer queries

MotivationThe problem of identifying the set of textual documents from a given database containing a query string has been studied in various fields of computing, e.g., in Information Retrieval, Databases, and Computational Biology. We consider the approximate version of this problem, that is, the result set is allowed to contain some false positive matches (but no false negatives), and focus on the specific case where the indexed documents are DNA strings. In this setting, state-of-the-art solutions rely on Bloom filters as a way to index all k-mers (substrings of length k) in the documents. To answer a query, the k-mers of the query string are tested for membership against the index and documents that contain at least a user-prescribed fraction of them (e.g., 75-80%) are returned. Methods and resultsHere, we explore an alternative index design based on k-mer minimizers and integer compression methods. We show that a careful implementation of this design outperforms previous solutions based on Bloom filters by a wide margin: the index has lower memory footprint and faster query times, while false positive matches have only a minor impact on the ranking of the documents reported. This trend is robust across genomic datasets of different complexity and query workloads. SoftwareThe software is implemented in C++17 and available under the MIT license at github.com/yhhshb/kaminari. Reproducibility information and additional results are provided at github.com/vicLeva/benchmarks_kaminari.

bioinformatics↗

Fast and Scalable Parallel External-Memory Construction of Colored Compacted de Bruijn Graphs with Cuttlefish 3

The exponential growth of genomic data has created an urgent need for scalable sequence analysis algorithms. De Bruijn graphs--along with their colored and compacted variants--have become essential tools in modern bioinformatics pipelines. Colored compacted de Bruijn graphs condense repetitive sequence information, significantly reducing the data burden on downstream analyses like genome assembly, metagenomic clustering, and pan-genomics. Since constructing uncompacted graphs becomes computationally prohibitive at scale, direct construction methods for colored compacted de Bruijn graphs are essential for the scalability of downstream analyses. We present Cuttlefish 3, a parallel external-memory algorithm that delivers state-of-the-art performance for constructing colored compacted de Bruijn graphs. Our approach introduces three algorithmic innovations that enable efficient scaling to massive datasets while maintaining high performance. First, we develop an optimized technique for accelerating local subgraph contractions. Second, we design a deterministic parallel algorithm based on list-ranking to efficiently merge local solutions. Third, we introduce a novel combinable hash-based method for identifying and tracking color-changing nodes, enabling rapid color-set extraction. We evaluate Cuttlefish 3 on diverse large-scale genomic datasets. In our benchmarks, Cuttlefish 3 achieves 3.29-4.09x speedup over GGCAT, the current state-of-the-art tool, while maintaining comparable memory usage. These performance gains make Cuttlefish 3 a practical solution for representing and analyzing the growing volumes of genomic data in modern bioinformatics workflows. Cuttlefish 3 is implemented in C++17 and is available at https://github.com/COMBINE-lab/cuttlefish.

bioinformatics↗

Alevin-fry-atac enables rapid and memory frugal mapping of single-cell ATAC-seq data using virtual colors for accurate genomic pseudoalignment

Ultrafast mapping of short reads via lightweight mapping techniques such as pseudoalignment has significantly accelerated transcriptomic and metagenomic analyses, often with minimal accuracy loss compared to alignment-based methods. However, applying pseudoalignment to large genomic references, like chromosomes, is challenging due to their size and repetitive sequences. We introduce a new and modified pseudoalignment scheme that partitions each reference into "virtual colors.... These are essentially overlapping bins of fixed maximal extent on the reference sequences that are treated as distinct "colors" from the perspective of the pseudoalignment algorithm. We apply this modified pseudoalignment procedure to process and map single-cell ATAC-seq data in our new tool alevin-fry-atac. We compare alevin-fry-atac to both Chromap and Cell Ranger ATAC. Alevin-fry-atac is highly scalable and, when using 32 threads, is approximately 2.8 times faster than Chromap (the second fastest approach) while using approximately one third of the memory and mapping slightly more reads. The resulting peaks and clusters generated from alevin-fry-atac show high concordance with those obtained from both Chromap and the Cell Ranger ATAC pipeline, demonstrating that virtual colorenhanced pseudoalignment directly to the genome provides a fast, memory-frugal, and accurate alternative to existing approaches for single-cell ATAC-seq processing. The development of alevin-fry-atac brings single-cell ATAC-seq processing into a unified ecosystem with single-cell RNA-seq processing (via alevin-fry) to work toward providing a truly open alternative to many of the varied capabilities of CellRanger. Furthermore, our modified pseudoalignment approach should be easily applicable and extendable to other genome-centric mapping-based tasks and modalities such as standard DNA-seq, DNase-seq, Chip-seq and Hi-C.

bioinformatics↗

A replicable and modular benchmark for long-read transcript quantification methods

We provide a replicable benchmark for long-read transcript quantification, and evaluate the performance of some recently-introduced tools on several synthetic long-read RNA-seq datasets. This benchmark is designed to allow the results to be easily replicated by other researchers, and the structure of the underlying Snakemake workflow is modular to make the addition of new tools or new data sets relatively easy. In analyzing previously assessed simulations, we find discrepancies with recently-published results. We also demonstrate that the robustness of certain approaches hinge critically on the quality and "cleanness" of the simulated data. AvailabilityThe Snakemake scripts for the benchmark are available at https://github.com/COMBINE-lab/lr_quant_benchmarks, the data used as input for the benchmarks (reference sequences, annotations, and simulated reads) are available at https://doi.org/10.5281/zenodo.13130623.

bioinformatics↗

Where the patterns are: repetition-aware compression for colored de Bruijn graphs

We describe lossless compressed data structures for the colored de Bruijn graph (or, c-dBG). Given a collection of reference sequences, a c-dBG can be essentially regarded as a map from k-mers to their color sets. The color set of a k-mer is the set of all identifiers, or colors, of the references that contain the k-mer. While these maps find countless applications in computational biology (e.g., basic query, reading mapping, abundance estimation, etc.), their memory usage represents a serious challenge for large-scale sequence indexing. Our solutions leverage on the intrinsic repetitiveness of the color sets when indexing large collections of related genomes. Hence, the described algorithms factorize the color sets into patterns that repeat across the entire collection and represent these patterns once, instead of redundantly replicating their representation as would happen if the sets were encoded as atomic lists of integers. Experimental results across a range of datasets and query workloads show that these representations substantially improve over the space effectiveness of the best previous solutions (sometimes, even dramatically, yielding indexes that are smaller by an order of magnitude). Despite the space reduction, these indexes only moderately impact the efficiency of the queries compared to the fastest indexes. SoftwareThe implementation of the indexes used for all experiments in this work is written in C++17 and is available at https://github.com/jermp/fulgor.

bioinformatics↗

Oarfish: Enhanced probabilistic modeling leads to improved accuracy in long read transcriptome quantification

MotivationLong read sequencing technology is becoming an increasingly indispensable tool in genomic and transcriptomic analysis. In transcriptomics in particular, long reads offer the possibility of sequencing full-length isoforms, which can vastly simplify the identification of novel transcripts and transcript quantification. However, despite this promise, the focus of much long read method development to date has been on transcript identification, with comparatively little attention paid to quantification. Yet, due to differences in the underlying protocols and technologies, lower throughput (i.e. fewer reads sequenced per sample compared to short read technologies), as well as technical artifacts, long read quantification remains a challenge, motivating the continued development and assessment of quantification methods tailored to this increasingly prevalent type of data. ResultsWe introduce a new method and software tool for long read transcript quantification called oarfish. Our model incorporates a novel and innovative coverage score, which affects the conditional probability of fragment assignment in the underlying probabilistic model. We demonstrate that by accounting for this coverage information, oarfish is able to produce more accurate quantification estimates than existing long read quantification methods, particularly when one considers the primary isoforms present in a particular cell line or tissue type. Availability and ImplementationOarfish is implemented in the Rust programming language, and is made available as free and open-source software under the BSD 3-clause license. The source code is available at https://www.github.com/COMBINE-lab/oarfish.

bioinformatics↗

Forseti: A mechanistic and predictive model of the splicing status of scRNA-seq reads

MotivationShort-read single-cell RNA-sequencing (scRNA-seq) has been used to study cellular heterogeneity, cellular fate, and transcriptional dynamics. Modeling splicing dynamics in scRNA-seq data is challenging, with inherent difficulty in even the seemingly straightforward task of elucidating the splicing status of the molecules from which sequenced fragments are drawn. This difficulty arises, in part, from the limited read length and positional biases, which substantially reduce the specificity of the sequenced fragments. As a result, the splicing status of many reads in scRNA-seq is ambiguous because of a lack of definitive evidence. We are therefore in need of methods that can recover the splicing status of ambiguous reads which, in turn, can lead to more accuracy and confidence in downstream analyses. ResultsWe develop Forseti, a predictive model to probabilistically assign a splicing status to scRNA-seq reads. Our model has two key components. First, we train a binding affinity model to assign a probability that a given transcriptomic site is used in fragment generation. Second, we fit a robust fragment length distribution model that generalizes well across datasets deriving from different species and tissue types. Forseti combines these two trained models to predict the splicing status of the molecule of origin of reads by scoring putative fragments that associate each alignment of sequenced reads with proximate potential priming sites. Using both simulated and experimental data, we show that our model can precisely predict the splicing status of reads and identify the true gene origin of multi-gene mapped reads. AvailabilityForseti and the code used for producing the results are available at https://github.com/COMBINE-lab/forseti under a BSD 3-clause license.

bioinformatics↗

scCensus: Off-target scRNA-seq reads reveal meaningful biology

Single-cell RNA-sequencing (scRNA-seq) provides unprecedented insights into cellular heterogeneity. Although scRNA-seq reads from most prevalent and popular tagged-end protocols are expected to arise from the 3' end of polyadenylated RNAs, recent studies have shown that "off-target" reads can constitute a substantial portion of the read population. in this work, we introduced scCensus, a comprehensive analysis workflow for systematically evaluating and categorizing off-target reads in scRNA-seq. We applied scCensus to seven scRNA-seq datasets. Our analysis of intergenic reads shows that these off-target reads contain information about chromatin structure and can be used to identify similar cells across modalities. Our analysis of antisense reads suggests that these reads can be used to improve gene detection and capture interesting transcriptional activities like antisense transcription. Furthermore, using splice-aware quantification, we find that spliced and unspliced reads provide distinct information about cell clusters and biomarkers, suggesting the utility of integrating signals from reads with different splicing statuses. Overall, our results suggest that off-target scRNA-seq reads contain underappreciated information about various transcriptional activities. These observations about yet-unexploited information in existing scRNA-seq data will help guide and motivate the community to improve current algorithms and analysis methods, and to develop novel approaches that utilize off-target reads to extend the reach and accuracy of single-cell data analysis pipelines. Data AvailabilityThe scripts for reproducing the results are available at https://github.com/COMBINE-lab/sc-census. Supplementary files can be found at https://doi.org/10.5281/zenodo.10520670.

bioinformatics↗

Tree-based differential testing using inferentialuncertainty for RNA-Seq

Identifying differentially expressed transcripts poses a crucial yet challenging problem in transcriptomics. Substantial uncertainty is associated with the abundance estimates of certain transcripts which, if ignored, can lead to the exaggeration of false positives and, if included, may lead to reduced power. Given a set of RNA-Seq samples, TreeTerminus arranges transcripts in a hierarchical tree structure that encodes different layers of resolution for interpretation of the abundance of transcriptional groups, with uncertainty generally decreasing as one ascends the tree from the leaves. We introduce mehenDi, which utilizes the tree structure from TreeTerminus for differential testing. The nodes output by mehenDi, called the selected nodes are determined in a data-driven manner to maximize the signal that can be extracted from the data while controlling for the uncertainty associated with estimating the transcript abundances. The identified selected nodes can include transcripts and inner nodes, with no two nodes having an ancestor/descendant relationship. We evaluated our method on both simulated and experimental datasets, comparing its performance with other tree-based differential methods as well as with uncertainty-aware differential transcript/gene expression methods. Our method detects inner nodes that show a strong signal for differential expression, which would have been overlooked when analyzing the transcripts alone.

bioinformatics↗