In recent years, pseudoalignment as a means for mapping reads to databases of reference genomes has become a widely-used method in studies of bacterial pathogenesis. A popular pseudoalignment criterion is thresholded union, in which a read is said to pseudoalign to a reference if the reference contains more than a percentage t of the read’s k-mers. Several pseudoalignment indexing tools that implement this and other pseudoalignment criteria are now available, including Bifrost, Themisto, and Fulgor. In this paper, we describe a scheme for single-species bacterial pseudoalignment that, instead of k-mers, uses shortest unique finimizers (Alanko et al., IEEE/ACM TCBB, 2025) as features for determining pseudoalignment. We show that this scheme, which we call Finimap, leads to a significantly lower false-positive rate than other recent "approximate pseudoalignment" methods Kaminari and Raptor, and is also faster.

Since their emergence some two decades ago, indexes based on the Burrows-Wheeler transform (BWT) have been intensely studied and today find wide use in genomics, where they form the basis of software tools for read alignment and \(k\)-mer lookup—routine tasks in modern data-intensive bioinformatics pipelines.

The minimizer of a $k$-mer is the smallest $m$-mer inside the $k$-mer according to some total order $< $ 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 minimizers, 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 worst-case 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, state-of-the-art minimizer-based schemes.

The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007] and on the Lyndon factorization of the input string. In the original paper, the compression achieved with the BBWT was shown to be competitive with that of the BWT, and it has been gaining interest in recent years. In this work, we present the first study of the number r B of runs of the BBWT, which is a measure of its compression power. We exhibit an infinite family of strings on which r B of the string and of its reverse differ by a multiplicative factor of Θ ( log ⁡ n ) , where n is the length of the string. We also give several theoretical results on the BBWT, including a characterization of binary strings for which the BBWT has two runs. Finally, we present experimental results and statistics on r B ( s ) and r B ( s rev ) , as well as on the number of Lyndon factors in the Lyndon factorization of s and s rev .