Biology subjects

Puglisi, S. J.

Publications and source records attributed to Puglisi, S. J..

12 recordsLinked to original sources

bioRxiv2026

Extracting and Updating Compact Colored k-mer Indexes

Colored k-mer indexes record, for every k-mer of a collection of genomes, the genomes or species that contain it, and underpin pseudoalignment and sequence search against large collections. Construction of such an index is expensive, yet the collection it represents is rarely final: genomes are retracted or found to be contaminated, users need an index of a single species or clade, and new genomes keep arriving. Rebuilding the index after every such change requires the original sequences and repeats the costly construction. We show that colored indexes based on the spectral Burrows-Wheeler transform (SBWT) can instead be updated efficiently in batches, without the original sequences, and with a result equivalent to the index built from scratch. Given an SBWT and any subset of its k-mers, we first extract the SBWT of this subset directly from the input, in one linear pass and without building a new index. Removing genomes, intersection and difference all reduce to this operation. We then carry the colors through every operation, by finding from the inputs alone where the color sets of the result change, so that removing or extracting genomes, as well as the union, intersection and difference of two colored indexes, each directly yield a complete colored index. In our experiments, editing paid off for large results: removing a genome from an index of 3,682 E. coli genomes took 54 seconds instead of 13 minutes for a rebuild, and adding one took about a minute. On AllTheBacteria, with 192 billion k-mers and 12,733 species, extracting M. tuberculosis, with 180,094 genomes, took less than four hours, and set operations then traced contamination of its color, some of which the next release of AllTheBacteria still contains. Our work turns large colored k-mer indexes from static snapshots of a collection into resources that can be maintained as the collection evolves. Our implementation is available at https://github.com/LoreDepuydt/colored-sbwt-setops.

bioinformatics↗

bioRxiv2026

Fast Set Operations for Compact k-mer Sets

The k-mer spectrum of a set of sequences is the set of k-length substrings the sequences contain. This lossy representation of sequence content pervades modern genomics. Recently, the spectral Burrows-Wheeler transform (SBWT) has emerged as a space-efficient representation of k-spectra that also supports efficient k-mer lookup queries and, more generally, easy navigation of the de Bruijn graph of the k-spectrum. In this paper, we examine primitive set operations, such as intersection, union, and set difference, on SBWT-encoded k-spectra and show that these operations can be supported efficiently. Moreover, efficient merging leads directly to a new memory-efficient algorithm for SBWT construction, which was able to build the SBWT for the 661K bacterial dataset containing 88 billion distinct k-mers in 50 hours using 186 GiB of RAM and 112 GiB of disk space. Given the pervasiveness of k-mer sets in genomics and the continued rapid growth of genomic databases, our work opens the door to a wide array of future applications that manipulate and reason about genomic data by dealing directly with simultaneously compact and searchable k-mer set representations offered by the SBWT. 2012 ACM Subject ClassificationTheory of computation [->] Design and analysis of algorithms Digital Object Identifier10.4230/LIPIcs.WABI.2026. Supplementary MaterialSoftware (Source Code): https://github.com/LoreDepuydt/sbwt-set-operations FundingThis work has benefited from funding from the French State under the France 2030 program, reference ANR-21-IDES-0006. The European Metropolis of Lille and the University of Lille are also acknowledged for their funding and support of the project WILL-CHAIRES-25-001-BOSSA.

bioinformatics↗

bioRxiv2026

KaryoScope: rapid, alignment-free sequence annotation for the pangenome era

The pangenome era is producing long-read sequencing data and complete genome assemblies (1-3) at a pace that current annotation methods cannot match. Existing tools were each built for a single feature class (repeats, centromeric satellites, or genes) and falter precisely where the genome is most variable and harbours clinically important variation: the centromeres, subtelomeres, and acrocentric short arms. Here we present KaryoScope, an alignment-free method to annotate an assembly at base-pair resolution across any desired feature classes in a single pass, completing in minutes on a standard workstation. Applied to the Human Pangenome Reference Consortium Release 2 assemblies (3), KaryoScope identifies the SST1 macrosatellite as the recurrent sequence at Robertsonian translocation fusion points (4, 5), delivers the first pangenome-wide census of D4Z4 macrosatellite structural diversity at the 4q and 10q subtelomeres relevant to facioscapulohumeral muscular dystrophy (6), and reveals previously uncharacterised centromere structural polymorphism, including chromosome-specific satellite loss and megabase-scale rearrangement validated by fluorescence in situ hybridization. A pre-built KaryoScope database for the human genome is distributed alongside the tool, and additional databases can be built for any reference genome or annotation source. Together, these capabilities bring the most variable regions of the genome within reach for comparative, clinical, and pangenome-scale analysis. KaryoScope is available at https://github.com/barthel-lab/KaryoScope.

bioinformatics↗

bioRxiv2026

Hierarchical genomic feature annotation with variable-length queries

K-mer-based methods are widely used for sequence classification in metagenomics, pangenomics, and RNA-seq analysis, but existing tools face important limitations: they typically require a fixed k-mer length chosen at index construction time, handle multi-matching k-mers (whose origin in the indexed data is ambiguous) in ad-hoc ways, and some resort to lossy approximations, complicating interpretation. We present HKS, a data structure for exact hierarchical variable-length k-mer annotation. Building on the Spectral Burrows- Wheeler Transform (SBWT), a single HKS index is constructed for a specified maximum query length s, and supports queries at any length k [≤] s. HKS associates each k-mer with exactly one label from a user-defined category hierarchy, where multi-matching k-mers are resolved to their most specific common node in the hierarchy. We formalize a feature assignment framework that partitions indexed k-mers into disjoint sets according to a user-defined category hierarchy. To recover specificity lost to multi-matching and novel k-mers, we introduce a hierarchy-aware smoothing algorithm that makes use of flanking sequence context. We validate the approach by assigning each query k-mer to a specific chromosome across human genome assemblies, including the T2T-CHM13v2.0 reference as a positive control and two diploid genomes of different ancestries (HG002, NA19185). Smoothing increases overall concordance from [~]81% to [~]97%, with residual errors attributable to known biological phenomena including acrocentric short-arm recombination and subtelomeric duplications. In performance benchmarks against Kraken2, HKS provides comparable query throughput while providing exact, lossless annotation across all k-mer lengths simultaneously from a single index. A prototype implementation is available at https://github.com/jnalanko/HKS.

bioinformatics↗

bioRxiv2026

New Space-Time Tradeoffs for Subset Rank and k-mer Lookup

Given a sequence S of subsets of symbols drawn from an alphabet of size{sigma} , a subset rank query srank(i, c) asks for the number of subsets before the ith subset that contain the symbol c. It was recently shown (Alanko et al., Proc. SIAM ACDA, 2023) that subset rank queries on the spectral Burrows-Wheeler lead to efficient k-mer lookup queries, an essential and widespread task in genomic sequence analysis. In this paper we design faster subset rank data structures that use small space--less than 3 bits per k-mer. Our experiments show that this translates to new Pareto optimal SBWT-based k-mer lookup structures at the low-memory end of the space-time spectrum.

bioinformatics↗

bioRxiv2026

Construction of distinct k-mer color sets via set fingerprinting

The colored de Bruijn graph model is the currently dominant paradigm for indexing large microbial reference genome datasets. In this model, each reference genome is assigned a unique color, typically an integer id, and each k-mer is associated with a color set, which is the set of colors of the reference genomes that contain that k-mer. This data structure efficiently supports a variety of pseudoalignment algorithms, which aim to determine the set of genomes most compatible with a query sequence. In most applications, many distinct k-mers are associated with the same color set. In current indexing algorithms, color sets are typically deduplicated and compressed only at the end of index construction. As a result, the peak memory usage can greatly exceed the size of the final data structure, making index construction a bottleneck in analysis pipelines. In this work, we present a Monte Carlo algorithm that constructs the set of distinct color sets for the k-mers directly in any individually compressed form. The method performs on-the-fly deduplication via incremental fingerprinting. We provide a strong bound on the error probability of the algorithm, even if the input is chosen adversarially, assuming that a source of random bits is available at run time. We show that given an SBWT index of 65,536 S. enterica genomes, we can enumerate and compress the distinct color sets of the genomes to 40 GiB on disk in 7 hours and 17 minutes, using only 14 GiB of RAM and no temporary disk space, with an error probability of at most 2-82.

bioinformatics↗

bioRxiv2025

Sequence alignment with k-bounded matching statistics

Finding high-quality local alignments between a query sequence and sequences contained in a large genomic database is a fundamental problem in computational genomics, at the core of thousands of biological analysis pipelines. Here, we describe a novel algorithm for approximate local alignment search based on the so-called k-bounded matching statistics of the query sequence with respect to an indexed database of sequences. We compute the k-bounded matching statistics, which capture the longest common suffix lengths of consecutive k-mer matches between query and target sequences, using the spectral Burrows-Wheeler transform, a data structure that enables computationally efficient queries. We show that our method is as fast and as accurate as state-of-the-art tools in several bacterial genomics tasks. Our method is available as a set of three kbo Rust packages that provide a command-line interface, a graphical user interface that runs in a browser without server-side processing, and a core library that can be accessed by other tools.

bioinformatics↗

bioRxiv2024

Finimizers: Variable-length bounded-frequency minimizers for k-mer sets

The minimizer of a k-mer is the smallest m-mer inside the k-mer according to some order relation < of the m-mers. Minimizers are often used as keys in hash tables in indexing tasks in metagenomics and pangenomics. The main weakness of minimizer-based indexing is the possibility of very frequently occurring minimzers, which can slow query times down significantly. Popular minimizer alignment tools employ various and often wild heuristics as workarounds, typically by ignoring frequent minimizers or blacklisting commonly occurring patterns, to the detriment of other metrics (e.g., alignment recall, space usage, or code complexity). In this paper, we introduce frequency-bounded minimizers, which we call finimizers, for indexing sets of k-mers. The idea is to use an order relation < for minimizer comparison that depends on the frequency of the minimizers within the indexed k-mers. With finimizers, the length m of the m-mers is not fixed, but is allowed to vary depending on the context, so that the length can increase to bring the frequency down below a user-specified threshold t. Setting a maximum frequency solves the issue of very frequent minimizers and gives us a worstcase guarantee for the query time. We show how to implement a particular finimizer scheme efficiently using the Spectral Burrows-Wheeler Transform (SBWT) (Alanko et al., Proc. SIAM ACDA, 2023) augmented with longest common suffix information. In experiments, we explore in detail the special case in which we set t = 1. This choice simplifies the index structure and makes the scheme completely parameter-free apart from the choice of k. A prototype implementation of this scheme exhibits k-mer localization times close to, and often faster than, stateof-the-art minimizer-based schemes. The code is available at https://github.com/ElenaBiagi/Finito.

bioinformatics↗

bioRxiv2023

Themisto: a scalable colored k-mer index for sensitive pseudoalignment against hundreds of thousands of bacterial genomes

MotivationHuge data sets containing whole-genome sequences of bacterial strains are now commonplace and represent a rich and important resource for modern genomic epidemiology and metagenomics. In order to efficiently make use of these data sets, efficient indexing data structures -- that are both scalable and provide rapid query throughput -- are paramount. ResultsHere, we present Themisto, a scalable colored k-mer index designed for large collections of microbial reference genomes, that works for both short and long read data. Themisto indexes 179 thousand Salmonella enterica genomes in 9 hours. The resulting index takes 142 gigabytes. In comparison, the best competing tools Metagraph and Bifrost were only able to index 11 thousand genomes in the same time. In pseudoalignment, these other tools were either an order of magnitude slower than Themisto, or used an order of magnitude more memory. Themisto also offers superior pseudoalignment quality, achieving a higher recall than previous methods on Nanopore read sets. Availability and implementationThemisto is available and documented as a C++ package at https://github.com/algbio/themisto available under the GPLv2 license. Contactjarno.alanko@helsinki.fi Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2022

Genome assembly with variable order de Bruijn graphs

Choosing an order for constructing a de Bruijn graph (DBG) is a crucial step in de novo assembly, as no single value allows complete genome reconstruction. The variable-order de Bruijn graph (voDBG) addresses this limitation by combining DBGs of multiple orders in a single structure connected by contextual relationships. This representation enables new connections to be identified or ambiguities to be resolved during assembly. However, voDBGs currently lack a formal definition of contigs. In this paper, we give the first formal definition of contigs for voDBGs. We show that, for a frequency range [{ell}, h] with{ell} > h/2, nodes whose labels occur with frequency f [isin] [{ell}, h] in the reads spell sequences of the genome with high probability under uniform sampling assumptions. We call these sequences ({ell}, h)-tigs. We also present an efficient algorithm to enumerate ({ell}, h)-tigs from a voDBG that accounts for homopolymer errors. Experiments on PacBio HiFi data show that our method significantly improves contiguity compared to fixed-order DBGs while remaining considerably lighter than full genome assemblers.

bioinformatics↗

bioRxiv2022

Succinct k-mer Set Representations Using Subset Rank Queries on the Spectral Burrows-Wheeler Transform (SBWT)

The k-spectrum of a string is the set of all distinct substrings of length k occurring in the string. This is a lossy but computationally convenient representation of the information in the string, with many applications in high-throughput bioinformatics. In this work, we define the notion of the Spectral Burrows-Wheeler Transform (SBWT), which is a sequence of subsets of the alphabet of the string encoding the k-spectrum of the string. The SBWT is a distillation of the ideas found in the BOSS and Wheeler graph data structures. We explore multiple different approaches to index the SBWT for membership queries on the underlying k-spectrum. We identify subset rank queries as the essential subproblem, and propose four succinct index structures to solve it. One of the approaches essentially leads to the known BOSS data structure, while the other three offer attractive time-space trade-offs and support simpler query algorithms that rely only on fast rank queries. The most general approach involves a novel data structure we call the subset wavelet tree, which we find to be of independent interest. All of the approaches are also amendable to entropy compression, which leads to good space bounds on the sizes of the data structures. Using entropy compression, we show that the SBWT can support membership queries on the k-spectrum of a single string in O(k) time and (n + k)(log{sigma} + 1/ ln 2) + o((n + k){sigma}) bits of space, where n is the number of distinct substrings of length k in the input and{sigma} is the size of the alphabet. This improves from the time O(k log{sigma} ) achieved by the BOSS data structure. We show, via experiments on a range of genomic data sets, that the simplicity of our new indexes translates into large performance gains in practice over prior art.

bioinformatics↗

bioRxiv2019

Data structures based on k-mers for querying large collections of sequencing datasets

High-throughput sequencing datasets are usually deposited in public repositories, e.g. the European Nucleotide Archive, to ensure reproducibility. As the amount of data has reached petabyte scale, repositories do not allow to perform online sequence searches; yet such a feature would be highly useful to investigators. Towards this goal, in the last few years several computational approaches have been introduced to index and query large collections of datasets. Here we propose an accessible survey of these approaches, which are generally based on representing datasets as sets of k-mers. We review their properties, introduce a classification, and present their general intuition. We summarize their performance and highlight their current strengths and limitations.

bioinformatics↗