2026-07-23T03:27:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23914 2026-02-09T06:23:54Z ddc:004 open_access

Optimizing the Performance of the FM-Index for Large-Scale Data Ferro, Eddie Boucher, Christina FM-Index Acceleration Run-Length Encoding Suffix Array Optimization Burrows-Wheeler Transform Efficient Backward Search The FM-index is a fundamental data structure used in bioinformatics to efficiently search for strings and index genomes. However, the FM-index can pose computational challenges, particularly in the context of large-scale genomic datasets, due to the complexity of its underlying components and data encodings. In this paper, we present a comprehensive review of efficient variants of the FM-index and the encoding strategies used to improve performance. We examine hardware-accelerated techniques, such as memory-efficient data layouts and cache-aware structures, as well as software-level innovations, including algorithmic refinements and compact representations. The reviewed work demonstrates substantial gains in both speed and scalability, making methods that use the FM-index more practical for high-throughput genomic applications. By analyzing the trade-offs and design choices of these variants, we highlight how combining hardware-aware and software-centric strategies enables more efficient FM-index construction and usage across a range of bioinformatics tasks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eddie Ferro and Christina Boucher 2025 Is Part Of OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Manzini.6 urn:nbn:de:0030-drops-239140 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.6 eng https://creativecommons.org/licenses/by/4.0/legalcode