Biology subjects

Hera, M. R.

Publications and source records attributed to Hera, M. R..

4 recordsLinked to original sources

bioRxiv2025

MaxGeomHash: An Algorithm for Variable-Size Random Sampling of Distinct Elements

With the surge in sequencing data generated from an ever-expanding range of biological studies, designing scalable computational techniques has become essential. One effective strategy to enable large-scale computation is to split long DNA or protein sequences into k-mers, and summarize large k-mer sets into compact random samples (a.k.a. sketches). These random samples allow for rapid estimation of similarity metrics such as Jaccard or cosine, and thus facilitate scalable computations such as fast similarity search, classification, and clustering. Popular sketching tools in bioinformatics include Mash and sourmash. Mash uses the MinHash algorithm to generate fixed-size sketches; while sourmash employs FracMinHash, which produces sketches whose size scales linearly with the total number of k-mers. Here, we introduce a novel sketching algorithm, MO_SCPLOWAXC_SCPLOWGO_SCPLOWEOMC_SCPLOWHO_SCPLOWASHC_SCPLOW, which for a specified integer parameter b [≥] 1, will produce, without prior knowledge of n (the number of k-mers) a random sample of size b lg(n/b) + [O](b). Notably, this is the first permutation-invariant and parallelizable sketching algorithm to date that can produce sub-linear sketches, to the best of our knowledge. We also introduce a variant, -MO_SCPLOWAXC_SCPLOWGO_SCPLOWEOMC_SCPLOWHO_SCPLOWASHC_SCPLOW, that produces sketches of size{Theta} (n) for a given [isin] (0, 1). We study the algorithms properties, analyze generated sample sizes, verify theoretical results empirically, provide a fast implementation, and investigate similarity estimate quality. With intermediate-sized samples between constant (MinHash) and linear (FracMinHash), MO_SCPLOWAXC_SCPLOWGO_SCPLOWEOMC_SCPLOWHO_SCPLOWASHC_SCPLOW balances efficiency (smaller samples need less storage and processing) with accuracy (larger samples yield better estimates). On genomic datasets, we demonstrate that MO_SCPLOWAXC_SCPLOWGO_SCPLOWEOMC_SCPLOWHO_SCPLOWASHC_SCPLOW sketches can be used to compute a similarity tree (proxy for a phylogenetic tree) more accurately than MinHash, and more efficiently than FracMinHash. Our C++ implementation is available at: github.com/mahmudhera/kmer-sketch. Code to reproduce the analyses and experiments is at: github.com/KoslickiLab/MaxGeomHash.

bioinformatics↗

bioRxiv2025

Leveraging FracMinHash Containment for Genomic dN/dS

Increasing availability of genomic data demands algorithmic approaches that can efficiently and accurately conduct downstream genomic analyses. These analyses, such as evaluating selection pressures within and across genomes, can reveal developmental and environmental pressures. One such commonly used metric to measure evolutionary pressures is based on the ratio of non-synonymous and synonomous substitution rates, dN/dS. Conventionally, the dN/dS ratio is used to infer selection pressures employing alignments to estimate total non-synonymous and synonymous substitution rates along protein-coding genes. However, this process can be time consuming and not scalable for larger datasets. Recently, a fast, approximate similarity measure, FracMinHash containment, was introduced and related to average nucleotide identity. In this work, we show how FracMinHash containment can be used to quickly estimate dN/dS enabling alignment-free estimations at a genomic level. Through simulated and real world experiments, our results indicate that employing FracMinHash containment to estimate dN/dS is scalable, enabling pairwise dN/dS estimations for 85,205 genomes within 5 hours. Furthermore, our approach is comparable to traditional dN/dS methods, representing sequences subject to positive and negative selection across various mutation rates. Moreover, we used this model to evaluate signatures of selection between Archaeal and Bacterial genomes, identifying a previously unreported metabolic island between Methanobrevibacter sp. RGIG2411 and Candidatus Saccharibacteria bacterium RGIG2249. We present, FracMinHash dN/dS, a novel alignment-free approach for estimating dN/dS at a genome level that is accurate and scalable beyond gene-level estimations while demonstrating comparability to conventional alignment-based dN/dS methods. Leveraging the alignment-free similarity estimation, FracMinHash containment, pairwise dN/dS estimations are facilitated within milliseconds, making it suitable for large-scale evolutionary analyses across diverse taxa. It supports comparative genomics, evolutionary inference, and functional interpretation across both synthetic, and complex biological datasets. Availability and implementationA version of the implementation is available at https://github.com/KoslickiLab/dnds-using-fmh.git. The reproduction of figures, data, and analysis can be found at https://github.com/KoslickiLab/dnds-using-fmh_reproducibles.git. Contactdmk333@psu.edu Supplementary informationSupplementary data are available at PLOS Computational Biology online. Author summaryUnderstanding how evolution shapes genomes helps us learn about the pressures organisms face in their environments. Scientists traditionally measure this by comparing genetic changes that alter proteins versus those that dont, a ratio that reveals whether natural selection is preserving or changing genes. However, this conventional approach requires computationally intensive sequence alignments, making it impractical for analyzing the massive genomic datasets now available. We developed a faster, alignment-free method to estimate evolutionary pressure across entire genomes. Our approach uses a computational technique called FracMinHash that compresses genomic information while preserving meaningful patterns. We tested our method on both simulated and real-world data, including over 85,000 microbial genomes, completing the analysis in just five hours whereas traditional methods would take days or weeks for the same analysis. The results were comparable to traditional methods and correctly identified genes under different types of selection. Using this approach, we discovered a previously unreported shared genetic region between an archaeal and bacterial species from the goat gut microbiome, suggesting ancient gene transfer between these distant branches of life. Our method makes large-scale evolutionary analysis practical for diverse applications, from tracking microbial strains to understanding adaptation in complex microbial communities, potentially accelerating discoveries in comparative genomics and evolutionary biology.

bioinformatics↗

bioRxiv2022

Lightweight compositional analysis of metagenomes with FracMinHash and minimum metagenome covers

The identification of reference genomes and taxonomic labels from metagenome data underlies many microbiome studies. Here we describe two algorithms for compositional analysis of metagenome sequencing data. We first investigate the FracMinHash sketching technique, a derivative of modulo hash that supports Jaccard containment estimation between sets of different sizes. We implement FracMinHash in the sourmash software, evaluate its accuracy, and demonstrate large-scale containment searches of metagenomes using 700,000 microbial reference genomes. We next frame shotgun metagenome compositional analysis as the problem of finding a minimum collection of reference genomes that "cover" the known k-mers in a metagenome, a minimum set cover problem. We implement a greedy approximate solution using FracMinHash sketches, and evaluate its accuracy for taxonomic assignment using a CAMI community benchmark. Finally, we show that the minimum metagenome cover can be used to guide the selection of reference genomes for read mapping. sourmash is available as open source software under the BSD 3-Clause license at github.com/dib-lab/sourmash/.

bioinformatics↗

bioRxiv2019

kRISP-meR: A Reference-free Guide-RNA Design Tool for CRISPR/Cas9

Genome editing using the CRISPR/Cas9 system requires designing guide RNAs (sgRNA) that are efficient and specific. Guide RNAs are usually designed using reference genomes which limits their use in organisms with no or incomplete reference genomes. Here, we present kRISP-meR, a reference free method to design sgRNAs for CRISPR/Cas9 system. kRISP-meR takes as input a target region and sequenced reads from the organism to be edited and generates sgRNAs that are likely to minimize off-target effects. Our analysis indicates that kRISP-meR is able to identify majority of the guides identified by a widely used sgRNA designing tool, without any knowledge of the reference, while retaining specificity.

bioinformatics↗