2026-07-23T04:26:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18639 2024-03-06T11:02:20Z ddc:004 open_access

Acceleration of FM-Index Queries Through Prefix-Free Parsing Hong, Aaron Oliva, Marco Köppl, Dominik Bannai, Hideo Boucher, Christina Gagie, Travis FM-index pangenomics scalability word-based indexing random access FM-indexes are a crucial data structure in DNA alignment, but searching with them usually takes at least one random access per character in the query pattern. Ferragina and Fischer [Ferragina and Fischer, 2007] observed in 2007 that word-based indexes often use fewer random accesses than character-based indexes, and thus support faster searches. Since DNA lacks natural word-boundaries, however, it is necessary to parse it somehow before applying word-based FM-indexing. Last year, Deng et al. [Deng et al., 2022] proposed parsing genomic data by induced suffix sorting, and showed the resulting word-based FM-indexes support faster counting queries than standard FM-indexes when patterns are a few thousand characters or longer. In this paper we show that using prefix-free parsing - which takes parameters that let us tune the average length of the phrases - instead of induced suffix sorting, gives a significant speedup for patterns of only a few hundred characters. We implement our method and demonstrate it is between 3 and 18 times faster than competing methods on queries to GRCh38. And was consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it is very clear that our method accelerates the performance of count over all state-of-the-art methods with a minor increase in the memory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aaron Hong and Marco Oliva and Dominik Köppl and Hideo Bannai and Christina Boucher and Travis Gagie 2023 Is Part Of LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2023.13 urn:nbn:de:0030-drops-186390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.13 eng https://creativecommons.org/licenses/by/4.0/legalcode