CS Paper Radar

More RLBWT Tricks

Travis Gagie

cs.DS ·submitted 2026-09-30 17:50 UTC · v2
theory

Abstract

Backward search over the run-length compressed Burrows-Wheeler transform (RLBWT) of a pangenome takes one step per character of the pattern, even when long stretches of the pattern match material that occurs many times in the collection. Two-level indexing also indexes a parse of the collection, so that a search can take one step per phrase. We parse at closed syncmers, whose phrases are prefix-free, and add blocks of continuations: when each phrase of a stretch of the pattern is the smallest phrase that follows the previous one anywhere in the collection, the search crosses the whole stretch in one step, on the BWT of a sequence of block symbols. We prove that the three BWTs stay in the same order, so the search still returns exactly the BWT interval of every match, and we bound the extra space by terms that depend on the length of the collection only through the number of distinct closed syncmers. On chromosome 19 haplotypes from the Human Pangenome Reference Consortium, finding the maximal exact matches of length at least 1000 of two haplotypes, on both strands, takes 5.5 to 5.7 seconds with 16, 32 or 64 other individuals, while backward search on a run-length compressed suffix array of the same collection takes 40 to 60 seconds and grows with the collection. We compare this with suffix-tree path decompositions (STPDs): over the parse, an STPD is no faster and needs about twice the memory; over the text it is about 1.7 times faster but needs the whole text in memory, about five times the space; and the published STPD-index, which compresses its text with relative Lempel-Ziv, is 8 to 10 times slower. Keeping a toehold through all three kinds of steps lets the search also list every occurrence of every MEM, for about 2 more seconds.

Closest papers

Nearest neighbours by meaning across the whole index.

Reportable Shortcuts with RLBWTs

cs.DS ·2026-09-06 ·Travis Gagie
similarity 0.80
Abstract

Backward search over a run-length compressed Burrows-Wheeler transform (RLBWT) takes one step per pattern character, even when long stretches of the pattern match material that recurs throughout a highly repetitive collection. We describe shortcuts: for a precomputed set of pairs $(α,β)$ of strings, a backward search that has just matched $β$ and finds $α$ immediately to its left in the pattern can cross $α$ in one step. Since a shortcut is taken only after its pair has been recognized in the pattern, the search returns a report of the shortcuts it took along with the usual BWT interval. Our motivation is pangenome graphs, where such pairs mark the places where a pattern passes through a vertex, so the report gives the path a match takes through the graph. We work out the case of a single linear reference $R$, with $β$ ranging over the length-$\ell$ windows of $R$ starting at multiples of $\ell$, and $α$ over the $2^t \ell$ characters preceding such a window. We show that the search counts correctly, that under stated conditions it crosses a stretch of the pattern matching $m$ consecutive windows of $R$ with $O(\log m + m / 2^τ)$ shortcuts, where $2^τ\ell$ is the longest shortcut, and that the shortcuts can be built efficiently from the RLBWT. On the Pizza&Chili cere collection of 37 genomes, shortcuts make backward search 2.3 to 4.2 times faster on exact patterns of length 200 to 1000, and 1.7 to 2.0 times faster with 1% of the characters substituted, for 86% more space. On 11 gigabases of genomes of seven bacterial species, they make it 1.6 to 1.9 times faster on exact patterns for 32% more space. On whole chromosome 19 haplotypes against 16 to 64 others from the Human Pangenome Reference Consortium, shortcuts in both directions make Boyer-Moore-Li search for maximal exact matches of length at least 1000 about 8 times faster.

0.26

Pangenome Optimization via Elastic Degenerate Strings

cs.DS ·2026-09-22 ·Nicola Rizzo, Sebastian Visan-Draghicescu, Nadia Pisanti, Veli Mäkinen
code/data similarity 0.66
Abstract

An Elastic Degenerate String (EDS, or ED-string) is a sequence of string sets. A pangenome, consisting of variations observed in a population along the genome sequences, can be naturally encoded as an EDS. Pattern matching and comparison problems on pangenome representations such as EDSes have been widely studied in the literature, but optimizing the pangenome properties during its construction has been largely omitted. We fill this gap by showing how methods originally developed for the related problem of founder reconstruction can be adapted to minimize, in linear time, the total cardinality of the EDS sets or the total size of the EDS strings, given suitable multiple alignments representing the input data. We provide an implementation for the minimum-cardinality criterion in a tool mincard, and conduct the first experiments on scalable pangenome optimization via EDSes. The code and experiments are available at https://github.com/algbio/eds.

0.39

Pangenome Peeling: Decomposing Weighted Adjacencies into Path-Forest Genomes

cs.DM q-bio.GN ·2026-11-06 ·Alitzel López Sánchez, Jiazhen Leng, Natasha Ivanova, Lingling Jin, David Sankoff
theory similarity 0.63
Abstract · This is an extended version of the article of the same name submitted to the RECOMB 2027 conference

One aspect of pangenome analysis that has received little attention is the recovery of the individual genomes that gave rise to a pangenome graph. While substantial effort has focused on constructing pangenomes from collections of genomes, the inverse problem remains largely unexplored: given a pangenome represented as a set of weighted adjacencies, can we reconstruct the constituent linear genomes that underlie it? Thus we introduce the pangenome peeling problem, which seeks to decompose a weighted adjacency graph into a collection of linear genomes whose combined adjacencies reproduce the observed edge weights. This problem is particularly relevant when considering ancestral pangenomes, where the graph structure may be known or inferred, but the underlying genomes are not. As a first step toward addressing this problem, we formally define pangenome peeling and derive a lower bound on the minimum number of genomes required to explain a given weighted adjacency graph. We then present two reconstruction methods: one based on the sequential addition of edges and a second based on extracting maximum-spanning-tree structures. Both methods produce genome collections that exactly explain the input adjacency data. To evaluate the recovered sets of genomes, we compare them to the set of input genomes using a maximum-weight matching framework based on the double-cut-and-join distance with indels. Here the maximum-spanning tree approach is superior, producing sets of constituent genomes close to the simulations while the sequential addition of edges approach yields constituent genomes increasingly divergent from the input as genomes sizes increase.

0.16

Revisiting (Bijective) Burrows-Wheeler Transform Space-Time Trade-Off Constructions

cs.DS ·2026-11-02 ·Dominik Köppl, Tomohiro I
similarity 0.59
Abstract

The bijective Burrows-Wheeler transform (BBWT) replaces the delimiter of the ordinary BWT by a Lyndon factorization and sorts factor conjugates in $ω$-order. It admits quadratic-time constant-workspace algorithms and linear-time linear-space algorithms. We extend the small-space BWT trade-off of Crochemore et al. [JDA,'15] to the BBWT and accelerate both constructions. For $τ\in [3..n]$, let $σ_τ\le\min(σ,τ+1)$ be the maximum construction-batch alphabet size. We construct either transform in $ O\!\left( \frac{n^2}τ \frac{\logτ}{\log\logτ} \right) $ time and $O(τσ_τ)$ additional space, assuming $τσ_τ=O(n)$. This improves the transferred $O((n^2/τ)\logτ)$ bound by a $\log\logτ$ factor. If $σ_τ\in w^{O(1)}$, where $w\inΩ(\log n)$ is the word size, the time improves to $ O\!\left( \frac{n^2}τ + \frac{n\logτ}{\log\logτ} \right). $ For inversion, the same bounds hold with the global alphabet size $σ$ in place of $σ_τ$.

0.21

NP-Hardness and a Fixed-Parameter Algorithm for Translocation Distance

cs.DS ·2026-09-16 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
theory similarity 0.59
Abstract

In this paper we study the genome rearrangements done by translocation events. Genome rearrangements were used to measure evolutionary distance between organisms since 1936 (Dobzhansky and Sturtevant). The chromosomes are represented as strings of DNA and the \emph{translocation operation} is defined as the exchange of prefixes between two strings. This operation results in the creation of two new strings (chromosomes) that can then be utilized in subsequent translocations. A translocation is referred to as \emph{contiguous} if the new strings are produced in a single copy, so each of them can be used in only one subsequent operation. When the words produced by a translocation operation are considered to have an infinite number of copies, the translocation is referred to as \emph{non-contiguous}. If the exchanged prefixes are of equal length, the translocation is called \emph{uniform}. Otherwise, the translocation is termed \emph{non-uniform}. The \emph{translocation distance} between two sets of strings, termed the input set and the target set, represents the minimum number of translocations necessary to obtain all the strings in the target set via translocation operations. We prove that both the non-uniform contiguous and the non-uniform non-contiguous translocation distance problems are NP-hard over arbitrary finite alphabets, where the alphabet is part of the input. For the case in which the target set consists of a single string, we give a fixed-parameter tractable algorithm parameterized by the length of the target string.

0.42

Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing

cs.DS ·2026-10-24 ·Florian Kurpicz, Maximilian Paris
similarity 0.56
Abstract

The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about $20$ bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts but 2.0 to 3.2 times slower on five of six non-repetitive ones, i.e., it provides a trade-off between required device memory and throughput.

0.20

Boyer-Moore Variants for Indeterminate String Matching and Experimental Evaluation

cs.DS ·2026-09-23 ·Neerja Mhaskar, Nivetha Raj Pappuraj
similarity 0.56
Abstract · 17 pages, 3 Figures, 1 Table

We study exact pattern matching on indeterminate strings, where a text or pattern position may represent a set of symbols rather than a single letter. Focusing on Boyer-Moore-style methods, we present new bad-character rules (BC Rules I-IV) and a new good-suffix procedure, computed by Fast_GSR_Indet_Shift, which avoids the per alignment recomputation used in BM_Indet [12] by shifting with a single preprocessed position-indexed table. We conduct a systematic experimental evaluation of sixteen algorithms, including classical bad-character adaptations (e.g., Horspool, Sunday, and Zhu-Takaoka) and hybrids that combine these bad-character rules with Fast_GSR_Indet_Shift. Across synthetic scaling experiments and a case study on the E. coli K-12 MG1655 genome, the Fast_BM_Indet hybrids consistently outperform BM_Indet and KMP_Indet [12], in some settings by up to two orders of magnitude. We also find that Zhu-Takaoka is the strongest bad-character-only adaptation on small alphabets and genomic data, while the Fast_BM_Indet variant using BC Rule I offers comparable performance, making it attractive for larger alphabets. We conclude with practical guidance on choosing among these variants for indeterminate string applications.

0.35

An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance

cs.DS ·2026-09-21 ·Maria Constantin, Adrian Miclăuş, Alexandru Popa
similarity 0.55
Abstract

Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every string produced during the computation remains available for reuse. Given an initial set of strings $A$ and a target set $B$, the objective is to produce all strings in $B$ using as few translocations as possible. We present the first polynomial-time approximation algorithm for this problem. For a single target string of length $n$, we obtain an $O(\log n)$-approximation, and we extend the result to arbitrary finite target sets with an $O(\log N)$-approximation, where $N$ is the total length of the targets not already present in the initial set. This resolves the approximability question for the non-uniform non-contiguous case left open by Constantin and Popa (TCS 2025).

0.08