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 reference genomes to capture genetic diversity.
• Traditional FM-index tools struggle with memory limitations for large genome collections.
• Existing compressed indices like r-index and move structure have limitations in bidirectional search or incur high computational overhead.

Purpose of the Study:

• To introduce b-move, a novel extension of the move structure for efficient approximate pattern matching in compressed sequence data.
• To address the memory and computational challenges posed by large pan-genome datasets in bioinformatics.

Main Methods:

• Development of b-move, a bidirectional extension of the move structure.
• Implementation of lossless approximate pattern matching and locate functionality.
• Utilizing run-length compressed space for index construction.

Main Results:

• b-move achieves fast, cache-efficient, and lossless approximate pattern matching.
• Bidirectional character extensions are up to 7 times faster than the br-index.
• The b-move index for complete E. coli genomes fits within typical laptop RAM, demonstrating memory efficiency.

Conclusions:

• b-move is a practical and scalable solution for pan-genome indexing and querying.
• The C++ implementation of b-move supports efficient pattern matching and locate functionality.
• The tool is publicly available for use in bioinformatics research.