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

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Pan-genomes are increasingly used over single reference genomes to represent genetic diversity.
• Traditional FM-index tools struggle with memory limitations for large pan-genome datasets.
• Existing compressed indices like r-index and move structures offer memory efficiency but limited search capabilities; br-index has high computational overhead.

Purpose of the Study:

• To develop a novel indexing structure for efficient pan-genome querying.
• To enable fast, cache-efficient, and lossless approximate pattern matching in compressed sequence data.

Main Methods:

• Introduction of b-move, a bidirectional extension of the move structure.
• Implementation of bidirectional character extensions and efficient occurrence locating operations ($\varphi$ and ${\varphi }^{-1}$).

Main Results:

• b-move achieves up to 7x faster bidirectional character extensions compared to the br-index.
• The structure significantly improves performance for locating pattern occurrences.
• The b-move index for all E. coli genomes fits within a typical laptop's RAM, demonstrating memory efficiency.

Conclusions:

• b-move is a practical and scalable solution for pan-genome indexing and querying.
• A C++ implementation of b-move is available, supporting efficient approximate pattern matching and locate functionality.