2026-07-24T02:23:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20654 2024-08-26T09:36:46Z ddc:004 open_access

b-move: Faster Bidirectional Character Extensions in a Run-Length Compressed Index Depuydt, Lore Renders, Luca Van de Vyver, Simon Veys, Lennart Gagie, Travis Fostier, Jan Pan-genomics FM-index r-index Move Structure Bidirectional Search Approximate Pattern Matching Lossless Alignment Cache Efficiency 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. We introduce b-move, a novel bidirectional extension of the move structure, enabling fast, cache-efficient bidirectional character extensions in run-length compressed space. It achieves bidirectional character extensions up to 8 times faster than the br-index, closing the performance gap with FM-index-based alternatives, while maintaining the br-index’s favorable memory characteristics. For example, all available complete E. coli genomes on NCBI’s RefSeq collection can be compiled into a b-move index that fits into the RAM of a typical laptop. Thus, b-move proves practical and scalable for pan-genome indexing and querying. We provide a C++ implementation of b-move, supporting efficient lossless approximate pattern matching including locate functionality, available at https://github.com/biointec/b-move under the AGPL-3.0 license. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lore Depuydt and Luca Renders and Simon Van de Vyver and Lennart Veys and Travis Gagie and Jan Fostier 2024 Is Part Of LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2024.10 urn:nbn:de:0030-drops-206546 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode