B-move: Faster Lossless Approximate Pattern Matching in a Run-Length Compressed Index.

ABSTRACT:

Background

Due to the increasing availability of high-quality genome sequences, pan-genomes are gradually replacing single consensus reference genomes in many bioinformatics pipelines to better capture genetic diversity. Traditional bioinformatics tools using the FM-index face memory limitations with such large genome collections. Recent advancements in run-length compressed indices like Gagie et al.'s r-index and Nishimoto and Tabei's move structure, alleviate memory constraints but focus primarily on backward search for MEM-finding. Arakawa et al.'s br-index initiates complete approximate pattern matching using bidirectional search in run-length compressed space, but with significant computational overhead due to complex memory access patterns.

Results

We introduce b-move,

SUBMITTER: Depuydt L 

PROVIDER: S-EPMC11601852 | biostudies-literature | 2024 Nov

REPOSITORIES: biostudies-literature