Biology subjects

Boucher, C.

Publications and source records attributed to Boucher, C..

At least 19 recordsLinked to original sources

bioRxiv2026

Accelerating String Comparison in RLZ Compressed Sequences via LCE Jumps

Relative Lempel-Ziv (RLZ) is an effective compression method for large, repetitive collections; however, the fundamental primitives required to elevate it from a passive archival format to a tractable representation for compressed construction have yet to be fully established. In this paper, we introduce an algorithmic framework for structurally comparing and lexicographically sorting sequences of RLZ factors. We characterize when direct factor comparisons are necessary and when they can be bypassed using RLZ specific shortcuts. We further introduce a method for extending truncated factors into right-maximal matches, enabling the recovery of matching statistics from the RLZ parse. Experimentally, RLZ sorting achieved speedups of up to 3.93x over character-based sorting. Together, these results advance the use of the RLZ format as a foundation for compressed construction.

bioinformatics↗

bioRxiv2026

Rapid-PFP: Accelerating Prefix-Free Parsing with GPU Parallelism

Prefix-Free Parsing (PFP) is widely used in genomic data processing to construct compressed indexes on massive, highly repetitive datasets. However, existing CPU implementations are constrained by sequential bottlenecks, limiting their ability to scale to large-scale modern pangenomic collections. We introduce RAPID-PFP, a redesigned implementation of the PFP algorithm that takes advantage of the massive parallelism and high memory bandwidth of modern GPUs. RAPID-PFP parallelizes trigger-string detection, phrase parsing, dictionary construction, and parse generation through custom CUDA kernels and GPU-resident data structures built using cuDF, CuPy, and Numba-CUDA. The algorithm operates entirely within GPU memory, minimizes host interaction, and dynamically adapts to available VRAM, enabling efficient processing in a range of hardware configurations. Across E. coli and Human Pangenome (HPRC) datasets, RAPID-PFP produces identical output to established CPU pipelines while delivering an order-of-magnitude acceleration. On 3,682 E. coli assemblies, RAPID-PFP reduces runtime from 552 seconds to 17 seconds compared to PFP-FL (32.1 times) and from 1,078 seconds to 17 seconds compared to PFP-ITL (62.6 times). On the complete 46-sample HPRC dataset, RAPID-PFP achieves a 33.4 time speedup and successfully processes scales that PFP-ITL cannot handle. Performance improves with dataset size, reflecting that PFP maps naturally onto thousands of CUDA cores, yielding sublinear scaling relative to CPU implementations. RAPID-PFP demonstrates that foundational compressed-indexing algorithms can be re-engineered for accelerators, enabling scalable and practical preprocessing for large-scale genomic indexing workflows.

bioinformatics↗

bioRxiv2026

Scalable machine learning improves resistance prediction and identifies novel determinants in Mycobacterium tuberculosis

Multidrug-resistant and extensively drug-resistant Mycobacterium tuberculosis (MTB) represents a growing global health crisis, characterized by limited treatment options and high mortality rates. Rapid and accurate prediction of resistance profiles is critical to guide effective therapy and curb transmission. Whole-genome sequencing (WGS) offers promise for individualized resistance profiling, yet existing computational tools remain constrained by predefined mutation catalogs and prohibitive resource requirements for large-scale analyses. Here, we present AURA, a GPU-accelerated, pangenome-scale machine learning framework for de novo resistance prediction. Trained on 12,185 globally diverse MTB isolates, AURA predicts resistance to 13 first-line, second-line, and repurposed antibiotics with high precision and identifies 59 novel resistance-associated loci, including variants in katG, pncA, rpoC, and members of the PE/PGRS gene family. By enabling model training on an unprecedented genomic scale, AURA provides new insights into the genetic architecture of resistance and establishes a scalable platform for precision-guided therapy and global surveillance of MTB.

bioinformatics↗

bioRxiv2026

Scaling Variant-Aware Multiplex Primer Design

MotivationRobust primer design is essential for reliable multiplex PCR in diverse and evolving pathogen, microbial, and host genomes. Traditional methods optimized for a single reference often fail on emerging variants, leading to reduced efficiency. Variant-aware design seeks primers that remain effective across diverse targets, but this introduces two key challenges: identifying robust candidates and selecting an optimal subset of primers. Although there are methods for the first challenge, namely the Primer Design Region (PDR) optimization problem, existing approaches lack optimality guarantees. ResultsWe introduce a near-linear algorithm with provable guarantees for efficient PDR optimization. Complementing this, we introduce a reference-free risk model based on Gini impurity that provides a stable, biologically interpretable measure of site-specific variation and yields PDRs that are robust to sequence diversity across datasets without ad hoc smoothing. For the second challenge related to thermodynamic stability, we optimize predicted {Delta}G and cast subset selection as a k-partite maximum-weight clique problem (NP-hard). We then design an efficient local-search heuristic with linear time updates. Together, these advances yield a principled, scalable framework for variant-aware primer design. Across Foot-and-Mouth Disease virus and Zika virus datasets, {Delta}-PRO produces more compact and robust PDR sets and multiplex panels with reduced predicted dimerization compared to existing tools, demonstrating the practical gains of principled and scalable variant-aware primer design for high-throughput multiplex PCR assays. AvailabilityThe proposed methods are implemented in a software package. Our implementation and results are publicly available at https://github.com/yhhan19/variant-aware-primer-design. Supplementary informationSupplementary materials are available online.

bioinformatics↗

bioRxiv2025

Vir2vec: A Genome-Wide Viral Embedding

Genomic language models (gLMs) are powerful numerical surrogates for DNA, but existing architectures focus primarily on human DNA or limited viral sets, and no dedicated benchmark exists for viral genome understanding. Here we introduce Vir2vec (from 17M to 422M parameters), decoder-only gLMs continually pretrained on a curated pan-viral corpus of 565,747 complete genomes across 295 species. We also present the viral Genome Understanding Evaluation (vGUE), a benchmark probing viral representations across broad organism discrimination, evolutionary signatures, intra-genus separation, variant subtyping, and host tropism. Evaluated as frozen feature extractors under nested cross-validation, Vir2vec achieves top balanced accuracy across 5 of 7 vGUE tasks, outperforming human-trained (MistralDNA), viral-specific (ModernBERTvirus), and broad biological foundation (Evo1) model. Furthermore, Vir2vec displays robust zero-shot generalization to unseen viral families. Finally, we introduce an argmax-routed SHAP explainability framework that projects feature attributions directly onto single-codon coordinates, correctly isolating key receptor-binding domain mutations driving mouse host adaptation. Vir2vec and vGUE provide a foundation for viral surveillance and discovery pipelines.

bioinformatics↗

bioRxiv2025

RAmpSim: A Thermodynamic Simulator for Hybridization Capturein Metagenomic Sequencing

Hybridization (bait) capture combined with long-read sequencing enables targeted profiling within complex metagenomes but introduces systematic biases from bait multiplicity, sequence composition, and species abundance that existing simulators ignore. We present RAmpSim, a fast simulator that models bait-target hybridization and fragment capture using a thermodynamic nearest-neighbor energy model and Boltzmann-weighted sampling of binding sites. Fragments are generated through multinomial sampling parameterized by bait concentration, binding energy, and genomic abundance before being passed to existing long-read simulators for modeling platform-specific errors. Implemented in Rust, RAmpSim reproduces empirical within-genome coverage and cross-species enrichment patterns observed in capture-based metagenomic datasets. Compared to uniform-coverage baselines, RAmpSims simulated coverage distributions are up to an order of magnitude closer to real data with respect to earth movers distance. Classification analysis reveals high recall in classifying high coverage regions between simulated and experimental distributions while outperforming a uniform baseline. Supporting accurate benchmarking and bait-set evaluation, RAmpSim provides an interpretable, efficient framework for simulating capture-based metagenomic sequencing. Code Availabilityhttps://github.com/az002/RAmpSim.git

bioinformatics↗

bioRxiv2025

Scalable PBWT Queries with Minimum-Length SMEMConstraints

Detecting long shared ancestry tracts in large haplotype panels is central to IBD analysis, imputation, and local ancestry inference, and can be approximated computationally by finding Set-Maximal Exact Matches (SMEMs) between sequences. The Positional Burrows-Wheeler Transform (PBWT) provides an efficient index for these panels, yet current methods often enumerate all SMEMs, producing a large number of short, uninformative matches. We introduce Positional Boyer- Moore-Li (PBML), which restricts enumeration to SMEMs occurring in at least k haplotypes and spanning at least L sites (kL-SMEMs). PBML is the first algorithm for computing KL-SMEMs on top of a single compressed run-length encoded PBWT index reusable for any (k, L) without rebuilding. On the 1000 Genomes Project, PBML achieves 4.6x faster query time than {micro}-PBWT and 2.4x over Durbins PBWT with lower memory, scaling to 15.9x over {micro}-PBWT at 16 threads. On a 10,000-haplotype panel from the Tennessee BIG Initiative, a diverse admixed cohort, PBML outperforms {micro}-PBWT by up to 4.7x in k-SMEM finding. By applying both thresholds during traversal, PBML extracts biologically informative, population-shared segments while filtering millions of short matches, a capability not available in current tools. On the BIG panel, in about 10 seconds PBML finds 2,441 long tracts at (k = 50, L = 5000) shared by an average of 60 haplotypes against 1000 queries, significantly reducing the 4.8 million unfiltered SMEMs shared on average by 2 haplotypes. These results establish PBML as a scalable tool for targeted long-range shared ancestry detection in large, diverse panels.

bioinformatics↗

bioRxiv2025

Efficient Grammar Compression via RLZ-based RePair

Among grammar-based compression techniques, RePair is a notable offline encoding scheme known for its simplicity and powerful combinatorial properties, producing compact grammars by repeatedly replacing the most frequent adjacent pairs of symbols, known as bigrams. However, RePairs memory usage scales poorly with input size, as it loads the entire text into memory. In contrast, Relative Lempel-Ziv (RLZ) parsing offers a scalable and lightweight online encoding scheme that losslessly represents a text in terms of phrases that refer to a reference string, but it often fails to expose deeper structural patterns. We introduce an algorithm that produces a RePair grammar from the RLZ parse of the input, leveraging the strengths of both methods. Our method, RLZ-RePair, performs bigram replacements systematically, preserving the integrity of the RLZ phrases throughout the RePair iterations. When the reference is well chosen, our method achieves the same grammar as standard RePair while significantly reducing both memory usage and the number of bigram replacements. In particular, we show that RLZ-RePair can reduce memory usage by more than 80% while incurring only a modest runtime increase compared to RePair. To our knowledge, RLZ-RePair is one of the first scalable methods that constructs exact RePair grammars, resulting in a grammar-based compressor that is both practical for large datasets and faithful to the theoretical elegance of RePair.

genomics↗

bioRxiv2024

devider: long-read reconstruction of many diverse haplotypes

Reconstructing haplotypes is important when sequencing a mixture of similar sequences. Long-read sequencing can connect distant alleles to disentangle similar haplotypes, but handling se-quencing errors requires specialized techniques. We present devider, an algorithm for haplotyping small sequences--such as viruses or genes--from long-read sequencing. devider uses a positional de Bruijn graph with sequence-to-graph alignment on an alphabet of informative alleles to provide a fast assembly-inspired approach compatible with various long-read sequencing technologies. On a synthetic Nanopore dataset containing seven HIV strains, devider recovered 97% of the haplotype content compared to 86% for the next best method while taking < 4 minutes and 1 GB of memory for > 8000x coverage. Benchmarking on synthetic mixtures of antimicrobial resistance (AMR) genes showed that devider recovered 83% of haplotypes, 23 percentage points higher than the next best method. On real PacBio and Nanopore datasets, devider recapitulates previously known results in seconds, disentan-gling a bacterial community with > 10 strains and an HIV-1 co-infection dataset. We used devider to investigate the within-host diversity of a long-read bovine gut metagenome enriched for AMR genes, discovering 13 distinct haplotypes for a tet(Q) tetracycline resistance gene with > 18, 000x coverage and 6 haplotypes for a CfxA2 beta-lactamase gene. We found clear recombination blocks for these AMR gene haplotypes, showcasing deviders ability to unveil ecological signals for heterogeneous mixtures.

bioinformatics↗

bioRxiv2024

Recursive RePair: Increasing the Scalability of RePair by Decreasing Memory Usage

The RePair compression algorithm produces a context-free grammar by iteratively substituting the most frequently occurring pair of consecutive symbols with a new symbol until all consecutive pairs of symbols appear only once in the compressed text. It is widely used in the settings of bioinformatics, machine learning, and information retrieval where random access to the original input text is needed. For example, in pangenomics, RePair is used for random access to a population of genomes. BigRePair improves the scalability of the original RePair algorithm by using Prefix-Free Parsing (PFP) to preprocess the text prior to building the RePair grammar. Despite the efficiency of PFP on repetitive text, there is a scalability issue with the size of the parse which causes a memory bottleneck in BigRePair. In this paper, we design and implement recursive RePair (denoted as Re2Pair), which builds the RePair grammar using recursive PFP. Our novel algorithm faces the challenge of constructing the RePair grammar without direct access to the parse of text, relying solely on the dictionary of the text and the parse and dictionary of the parse of the text. We compare Re2Pair to BigRePair using SARS-CoV-2 haplotypes and haplotypes from the 1000 Genomes Project. We show that our method Re2Pair achieves over a 40% peak memory reduction and a speed up ranging between 12% to 79% compared to BigRePair when compressing the largest input texts in all experiments. Re2Pair is made publicly available under the GNU public license here: https://github.com/jkim210/Recursive-RePair 2012 ACM Subject ClassificationTheory of computation [->] Formal languages and automata theory

genomics↗

bioRxiv2024

Cliffy: robust 16S rRNA classification based on a compressed LCA index

Taxonomic sequence classification is a computational problem central to the study of metagenomics and evolution. Advances in compressed indexing with the r-index enable full-text pattern matching against large sequence collections. But the data structures that link pattern sequences to their clades of origin still do not scale well to large collections. Previous work proposed the document array profiles, which use[O] (rd) words of space where r is the number of maximal-equal letter runs in the Burrows-Wheeler transform and d is the number of distinct genomes. The linear dependence on d is limiting, since real taxonomies can easily contain 10,000s of leaves or more. We propose a method called cliff compression that reduces this size by a large factor, over 250x when indexing the SILVA 16S rRNA gene database. This method uses {Theta}(r log d) words of space in expectation under a random model we propose here. We implemented these ideas in an open source tool called Cliffy that performs efficient taxonomic classification of sequencing reads with respect to a compressed taxonomic index. When applied to simulated 16S rRNA reads, Cliffys read-level accuracy is higher than Kraken2s by 11-18%. Clade abundances are also more accurately predicted by Cliffy compared to Kraken2 and Bracken. Overall, Cliffy is a fast and space-economical extension to compressed full-text indexes, enabling them to perform fast and accurate taxonomic classification queries. 2012 ACM Subject ClassificationApplied computing[->] Computational genomics

bioinformatics↗

bioRxiv2024

OCTOPUS: Disk-based, Multiplatform, Mobile-friendly Metagenomics Classifier

Portable genomic sequencers such as Oxford Nanopores MinION enable real-time applications in clinical and environmental health. However, there is a bottleneck in the downstream analytics when bioinformatics pipelines are unavailable, e.g., when cloud processing is unreachable due to absence of Internet connection, or only low-end computing devices can be carried on site. Here we present a platform-friendly software for portable metagenomic analysis of Nanopore data, the Oligomer-based Classifier of Taxonomic Operational and Pan-genome Units via Singletons (OCTOPUS). OCTOPUS is written in Java, reimplements several features of the popular Kraken2 and KrakenUniq software, with original components for improving metagenomics classification on incomplete/sampled reference databases, making it ideal for running on smartphones or tablets. OCTOPUS obtains sensitivity and precision comparable to Kraken2, while dramatically decreasing (4-to 16-fold) the false positive rate, and yielding high correlation on real-word data. OCTOPUS is available along with customized databases at https://github.com/DataIntellSystLab/OCTOPUS and https://github.com/Ruiz-HCI-Lab/OctopusMobile.

molecular biology↗

bioRxiv2023

Scalable De Novo Classification of Antibiotic Resistance of Mycobacterium Tuberculosis

We develop a robust machine learning classifier using both linear and nonlinear models (i.e., LASSO logistic regression (LR) and random forests (RF)) to predict the phenotypic resistance of Mycobacterium tuberculosis (MTB) for a broad range of antibiotic drugs. We use data from the CRyPTIC consortium to train our classifier, which consists of whole genome sequencing and antibiotic susceptibility testing (AST) phenotypic data for 13 different antibiotics. To train our model, we assemble the sequence data into genomic contigs, identify all unique 31-mers in the set of contigs, and build a feature matrix M, where M [i, j] is equal to the number of times the i-th 31-mer occurs in the j-th genome. Due to the size of this feature matrix (over 350 million unique 31-mers), we build and use a sparse matrix representation. Our method, which we refer to as MTB++, leverages compact data structures and iterative methods to allow for the screening of all the 31-mers in the development of both LASSO LR and RF. MTB++ is able to achieve high discrimination (F-1 greater than 80%) for the first-line antibiotics. Moreover, MTB++ had the highest F-1 score in all but three classes and was the most comprehensive since it had a F-1 score greater than 75% in all but four (rare) antibiotic drugs. We use our feature selection to contextualize the 31-mers that are used for the prediction of phenotypic resistance, leading to some insights about sequence similarity to genes in MEGARes. Lastly, we give an estimate of the amount of data that is needed in order to provide accurate predictions.

bioinformatics↗

bioRxiv2023

ONeSAMP 3.0: Effective Population Size via SNP Data for One Population Sample

O_LIThe genetic effective size (Ne) is arguably one of the most important characteristics of a population as it impacts the rate of loss of genetic diversity. Genetic estimators of (Ne) increasingly popular tools in population and conservation genetic studies. Yet there are very few methods that can estimate the Ne from data from a single population and without extensive information about the genetics of the population, such as a linkage map, or a reference genome of the species of interest. C_LIO_LIWe present ONeSAMP 3.0, an algorithm for estimating Ne from single nucleotide polymorphism (SNP) data collected from a single population sample using Approximate Bayesian Computation and local linear regression. C_LIO_LIWe demonstrate the utility of this approach using simulated Wright-Fisher populations, and empirical data from five endangered Channel Island fox (Urocyon littoralis) populations to evaluate the performance of ONeSAMP 3.0 compared to a commonly used Ne estimator. Our results show that ONeSAMP 3.0 is robust to the number of individual samples and number of loci included in and appears accurate even if the range of true Ne values is large. C_LIO_LIThis method is broadly applicable to natural populations and is flexible enough that future versions could easily include summary statistics appropriate for a suite of biological and sampling conditions. ONeSAMP 3.0 is publicly available under the GNU license at https://github.com/AaronHong1024/ONeSAMP_3 and also available with Bioconda (https://bioconda.github.io/index.html). C_LI

bioinformatics↗

bioRxiv2023

μ-PBWT: Enabling the Storage and Use of UK Biobank Data on a Commodity Laptop

MotivationThe positional Burrows-Wheeler Transform (PBWT) has been introduced as a key data structure for indexing haplotype sequences with the main purpose of finding maximal haplotype matches in h sequences containing w variation sites in [Formula]-time with a significant improvement over classical quadratic time approaches. However the original PBWT data structure does not allow queries over the modern biobank panels of haplotypes consisting of several millions of haplotypes, as they must be kept entirely in memory. ResultsIn this paper, we present a method for constructing the run-length encoded PBWT for memory efficient haplotype matching. We implement our method, which we refer to as -PBWT, and evaluate it on datasets of 1000 Genome Project and UK Biobank data. Our experiments demonstrate that the -PBWT reduces the memory usage up to a factor of 25 compared to the best current PBWT-based indexing. In particular, -PBWT produces an index that stores high-coverage whole genome sequencing data of chromosome 20 in half the space of its BCF file. In addition, -PBWT is able to index a dataset with 2 million haplotypes and 2.3 million sites in 4 GB of space, which can be uploaded in 20 seconds on a commodity laptop. -PBWT is an adaptation of techniques for the run-length compressed BWT for the PBWT (RLPBWT) and it is based on keeping in memory only a small representation of the RLPBWT that still allows the efficient computation of set maximal matches (SMEMs) over the original panel. AvailabilityOur implementation is open source and available at https://github.com/dlcgold/muPBWT. The binary is available at https://bioconda.github.io/recipes/mupbwt/README.html ContactPaola Bonizzoni paola.bonizzoni@unimib.it

bioinformatics↗

bioRxiv2023

Building a Pangenome Alignment Index via Recursive Prefix-Free Parsing

MotivationPangenomics alignment has emerged as an opportunity to reduce bias in biomedical research. Traditionally, short read aligners--such as Bowtie and BWA--were used to index a single reference genome, which was then used to find approximate alignments of reads to that genome. Unfortunately, these methods can only index a small number of genomes due to the linear-memory requirement of the algorithms used to construct the index. Although there are a couple of emerging pangenome aligners that can index a larger number of genomes more algorithmic progress is needed to build an index for all available data. ResultsEmerging pangenomic methods include VG, Giraffe, and Moni, where the first two methods build an index a variation graph from the multiple alignment of the sequences, and Moni simply indexes all the sequences in a manner that takes the repetition of the sequences into account. Moni uses a preprocessing technique called prefix-free parsing to build a dictionary and parse from the input--these, in turn, are used to build the main run-length encoded BWT, and suffix array of the input. This is accomplished in linear space in the size of the dictionary and parse. Therein lies the open problem that we tackle in this paper. Although the dictionary scales nicely (sub-linear) with the size of the input, the parse becomes orders of magnitude larger than the dictionary. To scale the construction of Moni, we need to remove the parse from the construction of the RLBWT and suffix array. We accomplish this, in this paper by applying prefix-free parsing recursively on the parse. Although conceptually simple, this leads to an algorithmic challenge of constructing the RLBWT and suffix array without access to the parse. We solve this problem, implement it, and demonstrate that this improves the construction time by a factor of 8.9 the running time and by a factor of 2.7 the memory required. AvailabilityOur implementation is open source and available at https://github.com/marco-oliva/r-pfbwt. ContactMarco Oliva at marco.oliva@ufl.edu

bioinformatics↗

bioRxiv2023

Recursive Prefix-Free Parsing for Building Big BWTs

Prefix-free parsing is useful for a wide variety of purposes including building the BWT, constructing the suffix array, and supporting compressed suffix tree operations. This linear-time algorithm uses a rolling hash to break an input string into substrings, where the resulting set of unique substrings has the property that none of the substrings suffixes (of more than a certain length) is a proper prefix of any of the other substrings suffixes. Hence, the name prefix-free parsing. This set of unique substrings is referred to as the dictionary. The parse is the ordered list of dictionary strings that defines the input string. Prior empirical results demonstrated the size of the parse is more burdensome than the size of the dictionary for large, repetitive inputs. Hence, the question arises as to how the size of the parse can scale satisfactorily with the input. Here, we describe our algorithm, recursive prefix-free parsing, which accomplishes this by computing the prefix-free parse of the parse produced by prefix-free parsing an input string. Although conceptually simple, building the BWT from the parse-of-the-parse and the dictionaries is significantly more challenging. We solve and implement this problem. Our experimental results show that recursive prefix-free parsing is extremely effective in reducing the memory needed to build the run-length encoded BWT of the input. Our implementation is open source and available at https://github.com/marco-oliva/r-pfbwt.

genomics↗

bioRxiv2022

Compressed Data Structures for Population-Scale Positional Burrows-Wheeler Transforms

AO_SCPLOWBSTRACTC_SCPLOWThe positional Burrows-Wheeler Transform (PBWT) was presented in 2014 by Durbin as a means to find all maximal haplotype matches in h sequences containing w variation sites in [O](hw)-time. This time complexity of finding maximal haplotype matches using the PBWT is a significant improvement over the naive pattern-matching algorithm that requires [O](h2w)-time. Compared to the more famous Burrows-Wheeler Transform (BWT), however, a relatively little amount of attention has been paid to the PBWT. This has resulted in less space-efficient data structures for building and storing the PBWT. Given the increasing size of available haplotype datasets, and the applicability of the PBWT to pangenomics, the time is ripe for identifying efficient data structures that can be constructed for large datasets. Here, we present a comprehensive study of the memory footprint of data structures supporting maximal haplotype matching in conjunction with the PBWT. In particular, we present several data structure components that act as building blocks for constructing six different data structures that store the PBWT in a manner that supports efficiently finding the maximal haplotype matches. We estimate the memory usage of the data structures by bounding the space usage with respect to the input size. In light of this experimental analysis, we implement the solutions that are deemed to be superior with respect to the memory usage and show the performance on haplotype datasets taken from the 1000 Genomes Project data.

bioinformatics↗