Biology subjects

Aluru, S.

Publications and source records attributed to Aluru, S..

14 recordsLinked to original sources

bioRxiv2026

scSAGA: Single-cell Sampled Gromov Wasserstein Alignment for Scalable and Memory-efficient Integration of Multi-modal Single Cell Data

MotivationSeveral different methods exist for multimodal integration of single cell RNA-seq (scRNA-seq) and chromatin accessibility (scATAC-seq) data. However, these methods either suffer from quadratic memory and runtime complexity, which hinders their applicability to large datasets, or trade off geometric fidelity for efficiency, which limits performance when modalities have disjoint features. Consequently, there is no existing framework that simultaneously preserves manifold structure and scales to organism-wide multimodal single cell datasets. ResultsWe present scSAGA (Single-Cell Sampled Gromov-Wasserstein Alignment), a geometry-preserving, scalable and memory-efficient method designed for integration of paired and unpaired scRNA-seq and scATAC-seq datasets. scSAGA combines (i) sparse kNN graph geometry with on-demand geodesic distances, (ii) plan-guided sampled Gromov- Wasserstein optimization, and (iii) a matrix-free joint embedding computed with sparse iterative linear algebra. Across paired and unpaired benchmark datasets from various organisms including Human PBMC and BMMC, mouse Alzheimers brain, Zebrafish, and Arabidopsis root, scSAGA achieves significantly improved one-to-one matching accuracy and/or modality mixing relative to well-established methods such as Pamona, SCOT, Seurat, and LIGER, while also scaling to integrations exceeding one million cells with near-linear growth in runtime and memory. Furthermore, scSAGA yields stronger downstream clustering of the integrated multimodal data, resulting in more coherent clusters for cell-type identification. scSAGA is thus the first geometry-preserving, memory-efficient optimal transport framework capable of accurate and scalable single-cell multimodal integration. Code and Data AvailabilityCode is available at https://github.com/AluruLab/scSAGA. The full list of datasets is listed in the supplementary table 1.

bioinformatics↗

bioRxiv2024

SCEMENT: Scalable and Memory Efficient Integration of Large-scale Single Cell RNA-sequencing Data

MotivationIntegrative analysis of large-scale single cell data collected from diverse cell populations promises an improved understanding of complex biological systems. While several algorithms have been developed for single cell RNA-sequencing data integration, many lack scalability to handle large numbers of datasets and/or millions of cells due to their memory and run time requirements. The few tools which can handle large data do so by reducing the computational burden through strategies such as subsampling of the data or selecting a reference dataset, to improve computational efficiency and scalability. Such shortcuts however hamper accuracy of downstream analyses, especially those requiring quantitative gene expression information. ResultsWe present SCEMENT, a SCalablE and Memory-Efficient iNTegration method to overcome these limitations. Our new parallel algorithm builds upon and extends the linear regression model previously applied in ComBat, to an unsupervised sparse matrix setting to enable accurate integration of diverse and large collections of single cell RNA-sequencing data. Using tens to hundreds of real single cell RNA-seq datasets, we show that SCEMENT outperforms ComBat as well as FastIntegration and Scanorama in runtime (upto 214X faster) and memory usage (upto 17.5X less). It not only performs batch correction and integration of millions of cells in under 25 minutes, but also facilitates discovery of new rare cell-types and more robust reconstruction of gene regulatory networks with full quantitative gene expression information. Availability and implementationSource code freely available for download at https://github.com/AluruLab/scement, implemented in C++ and supported on Linux. Contactaluru@cc.gatech.edu Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2022

MCPNet : A parallel maximum capacity-based genome-scale gene network construction framework

MotivationGene regulatory network (GRN) reconstruction from gene expression profiles is a compute- and data-intensive problem. Numerous methods based on diverse approaches including mutual information, random forests, Bayesian networks, correlation measures, as well as their transforms and filters such as data processing inequality, have been proposed. However, an effective GRN reconstruction method that performs well in all three aspects of computational efficiency, data size scalability, and output quality remains elusive. Simple techniques such as Pearson correlation are fast to compute but ignore indirect interactions, while more robust methods such as Bayesian networks are prohibitively time consuming to apply to tens of thousands of genes. ResultsWe developed MCP Score, a novel maximum-capacity-path based metric to quantify the relative strengths of direct and indirect gene-gene interactions. We further present MCPNet, an efficient, parallelized GRN reconstruction software based on MCP Score, to reconstruct networks in unsupervised and semi-supervised manners. Using synthetic and real S. cervisiae datasets as well as real A. thaliana datasets, we demonstrate that MCPNet produces better quality networks as measured by AUPR, is significantly faster than all other GRN inference software, and also scales well to tens of thousands of genes and hundreds of CPU cores. Thus, MCPNet represents a new GRN inferencing tool that simultaneously achieves quality, performance, and scalability requirements. AvailabilitySource code freely available for download at https://doi.org/10.5281/zenodo.6499748 and https://github.com/AluruLab/MCPNet, implemented in C++ and supported on Linux. Contactaluru@cc.gatech.edu Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2021

Fast alignment and preprocessing of chromatin profiles with Chromap

We present Chromap, an ultrafast method for aligning and preprocessing high throughput chromatin profiles. Chromap is comparable to BWA-MEM and Bowtie2 in alignment accuracy and is over 10 times faster than traditional workflows on bulk ChIP-seq / Hi-C profiles and than 10x Genomics CellRanger v2.0.0 pipeline on single-cell ATAC-seq profiles.

bioinformatics↗

bioRxiv2021

A variant selection framework for genome graphs

MotivationVariation graph representations are projected to either replace or supplement conventional single genome references due to their ability to capture population genetic diversity and reduce reference bias. Vast catalogues of genetic variants for many species now exist, and it is natural to ask which among these are crucial to circumvent reference bias during read mapping. ResultsIn this work, we propose a novel mathematical framework for variant selection, by casting it in terms of minimizing variation graph size subject to preserving paths of length with at most{delta} differences. This framework leads to a rich set of problems based on the types of variants (SNPs, indels), and whether the goal is to minimize the number of positions at which variants are listed or to minimize the total number of variants listed. We classify the computational complexity of these problems and provide efficient algorithms along with their software implementation when feasible. We empirically evaluate the magnitude of graph reduction achieved in human chromosome variation graphs using multiple and{delta} parameter values corresponding to short and long-read resequencing characteristics. When our algorithm is run with parameter settings amenable to long-read mapping ( = 10 kbp,{delta} = 1000), 99.99% SNPs and 73% indel structural variants can be safely excluded from human chromosome 1 variation graph. The graph size reduction can benefit downstream pan-genome analysis. Implementationhttps://github.com/at-cg/VF Contactchirag@iisc.ac.in, neda.tavakoli@gatech.edu, aluru@cc.gatech.edu

bioinformatics↗

bioRxiv2020

GRNUlar: Gene Regulatory Network reconstruction using Unrolled algorithm from Single Cell RNA-Sequencing data

MotivationGene regulatory networks (GRNs) are graphs that specify the interactions between transcription factors (TFs) and their target genes. Understanding these interactions is crucial for studying the mechanisms in cell differentiation, growth and development. Computational methods are needed to infer these networks from measured data. Although the availability of single cell RNA-Sequencing (scRNA-Seq) data provides unprecedented scale and resolution of gene-expression data, the inference of GRNs remains a challenge, mainly due to the complexity of the regulatory relationships and the noise in the data. ResultsWe propose GRNUlar, a novel deep learning architecture based on the unrolled algorithms idea for GRN inference from scRNA-Seq data. Like some existing methods which use prior information of which genes are TFs, GRNUlar also incorporates this TF information using a sparse multi-task deep learning architecture. We also demonstrate the application of a recently developed unrolled architecture GLAD to recover undirected GRNs in the absence of TF information. These unrolled architectures require supervision to train, for which we leverage the existing synthetic data simulators which generate scRNA-Seq data guided by a GRN. We show that unrolled algorithms outperform the state-of-the-art methods on synthetic data as well as real datasets in both the settings of TF information being absent or available. AvailabilityGithub link to GRNUlar - https://github.com/Harshs27/GRNUlar Contacthshrivastava3@gatech.edu

bioinformatics↗

bioRxiv2019

Validating paired-end read alignments in sequence graphs

Graph based non-linear reference structures such as variation graphs and colored de Bruijn graphs enable incorporation of full genomic diversity within a population. However, transitioning from a simple string-based reference to graphs requires addressing many computational challenges, one of which concerns accurately mapping sequencing read sets to graphs. Paired-end Illumina sequencing is a commonly used sequencing platform in genomics, where the paired-end distance constraints allow disambiguation of repeats. Many recent works have explored provably good index-based and alignment-based strategies for mapping individual reads to graphs. However, validating distance constraints efficiently over graphs is not trivial, and existing sequence to graph mappers rely on heuristics. We introduce a mathematical formulation of the problem, and provide a new algorithm to solve it exactly. We take advantage of the high sparsity of reference graphs, and use sparse matrix-matrix multiplications (SpGEMM) to build an index which can be queried efficiently by a mapping algorithm for validating the distance constraints. Effectiveness of the algorithm is demonstrated using real reference graphs, including a human MHC variation graph, and a pan-genome de-Bruijn graph built using genomes of 20 B. anthracis strains. While the one-time indexing time can vary from a few minutes to a few hours using our algorithm, answering a million distance queries takes less than a second.\n\n2012 ACM Subject ClassificationMathematics of computing [->] Paths and connectivity problems; Applied computing [->] Computational genomics

bioinformatics↗

bioRxiv2019

Accelerating Sequence Alignment to Graphs

Aligning DNA sequences to an annotated reference is a key step for genotyping in biology. Recent scientific studies have demonstrated improved inference by aligning reads to a variation graph, i.e., a reference sequence augmented with known genetic variations. Given a variation graph in the form of a directed acyclic string graph, the sequence to graph alignment problem seeks to find the best matching path in the graph for an input query sequence. Solving this problem exactly using a sequential dynamic programming algorithm takes quadratic time in terms of the graph size and query length, making it difficult to scale to high throughput DNA sequencing data. In this work, we propose the first parallel algorithm for computing sequence to graph alignments that leverages multiple cores and single-instruction multiple-data (SIMD) operations. We take advantage of the available inter-task parallelism, and provide a novel blocked approach to compute the score matrix while ensuring high memory locality. Using a 48-core Intel Xeon Skylake processor, the proposed algorithm achieves peak performance of 317 billion cell updates per second (GCUPS), and demonstrates near linear weak and strong scaling on up to 48 cores. It delivers significant performance gains compared to existing algorithms, and results in run-time reduction from multiple days to three hours for the problem of optimally aligning high coverage long (PacBio/ONT) or short (Illumina) DNA reads to an MHC human variation graph containing 10 million vertices.\n\nAvailabilityThe implementation of our algorithm is available at https://github.com/ParBLiSS/PaSGAL. Data sets used for evaluation are accessible using https://alurulab.cc.gatech.edu/PaSGAL.

bioinformatics↗

bioRxiv2019

On the Complexity of Sequence to Graph Alignment

Availability of extensive genetics data across multiple individuals and populations is driving the growing importance of graph based reference representations. Aligning sequences to graphs is a fundamental operation on several types of sequence graphs (variation graphs, assembly graphs, pan-genomes, etc.) and their biological applications. Though research on sequence to graph alignments is nascent, it can draw from related work on pattern matching in hypertext. In this paper, we study sequence to graph alignment problems under Hamming and edit distance models, and linear and affine gap penalty functions, for multiple variants of the problem that allow changes in query alone, graph alone, or in both. We prove that when changes are permitted in graphs either standalone or in conjunction with changes in the query, the sequence to graph alignment problem is [Formula]-complete under both Hamming and edit distance models for alphabets of size [≥] 2. For the case where only changes to the sequence are permitted, we present an O(|V| + m|E|) time algorithm, where m denotes the query size, and V and E denote the vertex and edge sets of the graph, respectively. Our result is generalizable to both linear and affine gap penalty functions, and improves upon the run-time complexity of existing algorithms.

bioinformatics↗

bioRxiv2019

A comprehensive evaluation of long read error correction methods

BackgroundThird-generation single molecule sequencing technologies can sequence long reads, which is advancing the frontiers of genomics research. However, their high error rates prohibit accurate and efficient downstream analysis. This difficulty has motivated the development of many long read error correction tools, which tackle this problem through sampling redundancy and/or leveraging accurate short reads of the same biological samples. Existing studies to asses these tools use simulated data sets, and are not sufficiently comprehensive in the range of software covered or diversity of evaluation measures used.\n\nResultsIn this paper, we present a categorization and review of long read error correction methods, and provide a comprehensive evaluation of the corresponding long read error correction tools. Leveraging recent real sequencing data, we establish benchmark data sets and set up evaluation criteria for a comparative assessment which includes quality of error correction as well as run-time and memory usage. We study how trimming and long read sequencing depth affect error correction in terms of length distribution and genome coverage post-correction, and the impact of error correction performance on an important application of long reads, genome assembly. We provide guidelines for practitioners for choosing among the available error correction tools and identify directions for future research.\n\nConclusionsDespite the high error rate of long reads, the state-of-the-art correction tools can achieve high correction quality. When short reads are available, the best hybrid methods outperform non-hybrid methods in terms of correction quality and computing resource usage. When choosing tools for use, practitioners are suggested to be careful with a few correction tools that discard reads, and check the effect of error correction tools on downstream analysis. Our evaluation code is available as open-source at https://github.com/haowenz/LRECE.

bioinformatics↗

bioRxiv2018

Identification of Significant Computational Building Blocks through Comprehensive Deep Dive of NGS Secondary Analysis Methods

Rapid advancements in next generation sequencing technologies have greatly improved the throughput of sequencing and reduced the cost to under $1000 per genome propelling ambitious projects across the globe that are pursuing sequencing million or more genomes. In addition, the sequencing throughput is increasing and the cost is decreasing at a rate much faster than the Moores law. This necessitates equivalent rate of acceleration of NGS secondary analysis that assembles the reads into full genomes and identifies variants between genomes. Conventional improvement in hardware can at best help accelerate this according to the Moores law if the corresponding software is able to use the hardware efficiently. This is currently not the case for majority of the dozens of software tools used for NGS secondary analysis. Thus, to keep pace with the rate of advancement of sequencers, we need - 1) hardware that is designed taking into account the computational requirements of NGS secondary analysis and 2) software tools that use the hardware efficiently.\n\nIn this work, we take the first step towards that goal by identifying the computational requirements of NGS secondary analysis. We surveyed dozens of software tools from all the three major problems in secondary analysis - sequence mapping, de novo assembly, and variant calling - to select seven popular tools and a workflow for an in depth analysis. We performed runtime profiling of the tools using multiple real datasets to find that the majority of the runtime is dominated by just four building blocks - Smith Waterman alignment, FM-index based sequence search, Debruijn graph construction and traversal and pairwise hidden markov model algorithm. Together, these building blocks cover 80.5%-98.2% of the runtime for sequence mapping, 63.9%-99.4% of the runtime for De novo assembly, and 72%-93% of the runtime for variant calling. The beauty of this result is that by just tailoring our software and hardware for these building blocks, we can get a major performance improvement of NGS secondary analysis.

genomics↗

bioRxiv2018

A Fast Adaptive Algorithm for Computing Whole-Genome Homology Maps

MotivationWhole-genome alignment is an important problem in genomics for comparing different species, mapping draft assemblies to reference genomes, and identifying repeats. However, for large plant and animal genomes, this task remains compute and memory intensive.\n\nResultsWe introduce an approximate algorithm for computing local alignment boundaries between long DNA sequences. Given a minimum alignment length and an identity threshold, our algorithm computes the desired alignment boundaries and identity estimates using kmer-based statistics, and maintains sufficient probabilistic guarantees on the output sensitivity. Further, to prioritize higher scoring alignment intervals, we develop a plane-sweep based filtering technique which is theoretically optimal and practically efficient. Implementation of these ideas resulted in a fast and accurate assembly-to-genome and genome-to-genome mapper. As a result, we were able to map an error-corrected whole-genome NA12878 human assembly to the hg38 human reference genome in about one minute total execution time and < 4 GB memory using 8 CPU threads, achieving more than an order of magnitude improvement in both runtime and memory over competing methods. Recall accuracy of computed alignment boundaries was consistently found to be > 97% on multiple datasets. Finally, we performed a sensitive self-alignment of the human genome to compute all duplications of length [≥] 1 Kbp and [≥] 90% identity. The reported output achieves good recall and covers 5% more bases than the current UCSC genome browsers segmental duplication annotation.\n\nAvailabilityhttps://github.com/marbl/MashMap\n\nContactadam.phillippy@nih.gov, aluru@cc.gatech.edu

bioinformatics↗

bioRxiv2017

High-throughput ANI Analysis of 90K Prokaryotic Genomes Reveals Clear Species Boundaries

A fundamental question in microbiology is whether there is a continuum of genetic diversity among genomes or clear species boundaries prevail instead. Answering this question requires robust measurement of whole-genome relatedness among thousands of genomes and from diverge phylogenetic lineages. Whole-genome similarity metrics such as Average Nucleotide Identity (ANI) can provide the resolution needed for this task, overcoming several limitations of traditional techniques used for the same purposes. Although the number of genomes currently available may be adequate, the associated bioinformatics tools for analysis are lagging behind these developments and cannot scale to large datasets. Here, we present a new method, FastANI, to compute ANI using alignment-free approximate sequence mapping. Our analyses demonstrate that FastANI produces an accurate ANI estimate and is up to three orders of magnitude faster when compared to an alignment (e.g., BLAST)-based approach. We leverage FastANI to compute pairwise ANI values among all prokaryotic genomes available in the NCBI database. Our results reveal a clear genetic discontinuity among the database genomes, with 99.8% of the total 8 billion genome pairs analyzed showing either >95% intra-species ANI or <83% inter-species ANI values. We further show that this discontinuity is recovered with or without the most frequently represented species in the database and is robust to historic additions in the public genome databases. Therefore, 95% ANI represents an accurate threshold for demarcating almost all currently named prokaryotic species, and wide species boundaries may exist for prokaryotes.

bioinformatics↗

bioRxiv2017

A fast approximate algorithm for mapping long reads to large reference databases

Emerging single-molecule sequencing technologies from Pacific Biosciences and Oxford Nanopore have revived interest in long read mapping algorithms. Alignment-based seed-and-extend methods demonstrate good accuracy, but face limited scalability, while faster alignment-free methods typically trade decreased precision for efficiency. In this paper, we combine a fast approximate read mapping algorithm based on minimizers with a novel MinHash identity estimation technique to achieve both scalability and precision. In contrast to prior methods, we develop a mathematical framework that defines the types of mapping targets we uncover, establish probabilistic estimates of p-value and sensitivity, and demonstrate tolerance for alignment error rates up to 20%. With this framework, our algorithm automatically adapts to different minimum length and identity requirements and provides both positional and identity estimates for each mapping reported. For mapping human PacBio reads to the hg38 reference, our method is 290x faster than BWA-MEM with a lower memory footprint and recall rate of 96%. We further demonstrate the scalability of our method by mapping noisy PacBio reads (each [≥] 5 kbp in length) to the complete NCBI RefSeq database containing 838 Gbp of sequence and > 60, 000 genomes.

bioinformatics↗