New b-move index accelerates pan-genome pattern matching

Researchers have introduced b-move, a novel bidirectional extension of the move structure designed to enable fast, cache-efficient, lossless approximate pattern matching in run-length compressed space. Published in Algorithms for Molecular Biology, the study presents a computational tool that addresses memory limitations inherent in traditional bioinformatics pipelines. As high-quality genome sequences become increasingly available, pan-genomes are gradually replacing single consensus reference genomes to better capture genetic diversity. However, traditional tools relying on the FM-index face significant memory constraints when processing such large genome collections. The b-move index offers a practical solution by maintaining favorable memory characteristics while significantly improving search speed.

The development of b-move responds to the need for efficient indexing methods that can handle the scale of modern pan-genome data. Pan-genomes compile individuals from the same species or related species into a single index, aiming to mitigate biased results stemming from the choice of a single reference. While the FM-index is compact and fast for relatively small references, its memory use scales linearly with the total genome content. This limitation calls for new index types capable of storing and analyzing large genome collections within the memory constraints of modern workstations and laptops. Run-length compressed indices, such as the r-index and the move structure, have alleviated these memory constraints but previously focused primarily on backward search for maximal exact match finding.

Previous advancements in run-length compressed indices, including Arakawa et al.’s br-index, initiated complete approximate pattern matching using bidirectional search. However, the br-index suffered from significant computational overhead due to complex memory access patterns. These patterns stem from the intricate interplay of rank and select queries on compressed sparse bitvectors and wavelet trees, leading to multiple cache misses. Despite its favorable memory complexity, the br-index could be one order of magnitude slower than the bidirectional FM-index, hindering its adoption in practical bioinformatics tools. The b-move index is designed to close this performance gap while preserving the memory efficiency of run-length compressed approaches.

b-move achieves bidirectional character extensions up to seven times faster than the br-index, effectively narrowing the performance gap with FM-index-based alternatives. For locating occurrences, b-move performs phi and inverse phi operations up to seven times faster than the br-index. The index maintains the favorable memory characteristics of the br-index, allowing all available complete E. coli genomes on NCBI’s RefSeq collection to be compiled into an index that fits into the RAM of a typical laptop. This scalability makes b-move a practical tool for lossless approximate pattern matching against large pan-genomes, where bidirectional indexes excel when combined with search schemes.

The technical foundation of b-move relies on move tables that support constant-time LF operations. The LF operation maps the character at a specific index in the Burrows-Wheeler transform to its corresponding character in the first column of the lexicographically ordered rotations. Nishimoto and Tabei introduced the move structure as an alternative to the r-index, achieving LF operations in constant time by mapping input intervals in the BWT to output intervals in F. In b-move, these move tables are extended to support bidirectional search by incorporating an additional component representing the reverse search text. This allows the synchronization of intervals corresponding to a search pattern over the suffix array and its reverse, enabling extensions in both directions.

Locating occurrences in the search text requires the phi and inverse phi operations, which retrieve the coordinates of all occurrences for a given suffix array interval. In the b-move index, these operations are supported by dedicated move tables that achieve constant-time complexity and high cache locality. The researchers observed that unbalanced move tables for phi operations resulted in a heavily right-tailed distribution of fast forwarding steps, with a mean of 146.55 steps per operation. To mitigate this, the phi and inverse phi move tables are balanced, capping the maximum number of fast forwarding steps at four and reducing the mean to 1.49 steps. This balancing ensures that the theoretical space and time complexities remain valid while significantly improving practical performance.

Benchmarks were conducted on two primary datasets: 512 human chromosome 19 haplotypes from the 1000 Genomes Project and 3,264 Escherichia coli strains from NCBI’s Reference Sequence collection. The index construction process supports both in-memory and prefix-free parsing based methods, with the latter using significantly less memory. For the largest human pan-genome, prefix-free parsing took seven hours and 84 GB of memory, suitable for most workstations. The benchmarks utilized 100,000 Illumina reads of length 151 base pairs, randomly sampled from larger whole genome sequencing datasets. Performance was evaluated on a Red Hat Enterprise Linux 8 system using a single core of Intel Xeon Gold 6140 CPUs, with runtimes based on the median of ten runs.

In terms of character extension performance, b-move outperformed the br-index by a factor of at least nine to 11 in total search time when using full or bit-packed LF move tables. The bit-packed version incurred only a modest performance reduction of around 15% while significantly reducing RAM usage from 2.6 GB to 1.1 GB. The average execution time for the core bidirectional character extension functionality showed a speed-up of five to seven times in favor of b-move. This efficiency is attributed to the cache-friendly nature of the move tables, which involve linear memory access rather than the random access patterns characteristic of the br-index. The time for a single bidirectional character extension in the br-index decreased when allowing more mismatches due to repeated memory accesses, an effect mitigated in b-move.

For locating performance, the use of move table-based phi and inverse phi operations yielded a five to seven times speedup over the original implementations in the br-index. The average locate time required to map one suffix array interval to all corresponding occurrences maintained a 1.3 to 2 times improvement over the original approach, despite overhead from creating new occurrence objects. The bit-packed phi move tables reduced memory usage to 4.3 GB compared to 8.6 GB for the full version, offering a practical trade-off between speed and space. In scenarios where many occurrences must be located, such as in pan-genomes with numerous haplotypes, this performance difference can significantly impact overall runtime. The researchers provided both options, with the move table-based implementation as the default.

When comparing overall approximate pattern matching performance, b-move’s speed was of the same order of magnitude as Columba, a lossless read-mapper based on the bidirectional FM-index. However, b-move required orders of magnitude less memory for large, repetitive datasets. The br-index, while compact, was roughly four to eight times slower than b-move depending on the configuration. The b-move index becomes smaller than Columba beyond a specific switch point for each pan-genome, after which Columba’s size increases rapidly. This makes b-move the optimal index for scaling lossless approximate pattern matching to large pan-genomes, particularly for short reads with low error rates. The tool does not support reporting CIGAR strings, as the original text would have to be stored in memory for that purpose.

The study highlights the practical and scalable nature of b-move for pan-genome indexing and querying. The C++ implementation of b-move supports efficient lossless approximate pattern matching including locate functionality and is available under the AGPL-3.0 license. Future work includes integrating the permuted longest common prefix array into the move tables to further reduce cache misses and optimizing the reporting functionality to minimize memory and runtime overhead. The researchers also aim to integrate subsampling functionality to further reduce the memory usage of the index itself.

By combining the memory efficiency of run-length compressed indices with the speed of bidirectional search, b-move provides a robust solution for identifying all occurrences within a pre-specified error distance.

Subject of Research: Development of b-move, a bidirectional run-length compressed index for efficient pan-genome pattern matching

Article Title: b-move: faster lossless approximate pattern matching in a run-length compressed index

Article References: Depuydt, L., Renders, L., Van de Vyver, S., Veys, L., Gagie, T., & Fostier, J. (2025). b-move: faster lossless approximate pattern matching in a run-length compressed index. Algorithms for Molecular Biology, 20(1), Article 15. https://doi.org/10.1186/s13015-025-00281-x

Image Credits: AI Generated

DOI: 10.1186/s13015-025-00281-x

Keywords: pan-genome, pattern matching, bioinformatics, indexing, run-length compression, genomics, algorithms, memory efficiency, b-move, faster, lossless, approximate