b-move: faster bidirectional character extensions in a run-length compressed index

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Pan-genome analysis requires efficient indexing of large, diverse genome collections, moving beyond single reference genomes.
• Traditional FM-index tools struggle with memory limitations for large-scale pan-genome data.
• Existing compressed indices like r-index and move structures offer memory efficiency but are limited in search capabilities, while br-index has high computational overhead.

Purpose of the Study:

• To develop a novel data structure for efficient pan-genome indexing and querying.
• To overcome memory and performance limitations of existing bioinformatics indexing tools for large genome collections.

Main Methods:

• Introduction of b-move, a bidirectional extension of the move structure for run-length compressed sequence data.
• Implementation of b-move in C++ to support fast, cache-efficient bidirectional character extensions.
• Evaluation of b-move's performance and memory usage against existing indexing methods.

Main Results:

• b-move achieves bidirectional character extensions up to 8 times faster than the br-index.
• The new index matches the memory efficiency of the br-index, enabling large pan-genome indexing on standard hardware (e.g., E. coli genomes on a laptop).
• b-move closes the performance gap with FM-index-based methods while retaining superior memory characteristics.

Conclusions:

• b-move offers a practical and scalable solution for pan-genome indexing and querying.
• The data structure enables efficient approximate pattern matching and locate functionality in compressed sequence data.
• The C++ implementation is publicly available, facilitating its adoption in bioinformatics research.