{"doi":"10.4230/lipics.wabi.2023.13","title":"Acceleration of FM-index Queries Through Prefix-free Parsing.","abstract":"FM-indexes are a crucial data structure in DNA alignment, for example, but searching with them usually takes at least one random access per character in the query pattern. Ferragina and Fischer [5] 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. [3] 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. The source code for PFP-FM is available at https://github.com/marco-oliva/afm.","journal":null,"year":2023,"id":415937,"datarank":0.0,"base_score":0.0,"endowment":0.0,"self_citation_contribution":0.0,"citation_network_contribution":0.0,"self_endowment_contribution":0.0,"citer_contribution":0.0,"corpus_percentile":null,"corpus_rank":null,"citation_count":0,"citer_count":0,"citers_with_citation_signal":0,"citers_with_endowment":0,"datacite_reuse_total":0,"is_dataset":false,"is_dataset_confidence":0.9459,"is_data_producer":false,"deposit_databanks":null,"is_oa":true,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":"2023-01-01","fair_score":null,"fair_percentile":null,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":496290,"name":"Marco Antônio Oliva","orcid":"0000-0003-0525-3114","position":1,"is_corresponding":false},{"id":805392,"name":"Dominik Köppl","orcid":"0000-0002-8721-4444","position":2,"is_corresponding":false},{"id":1186072,"name":"Hideo Bannai","orcid":"0000-0002-6856-5185","position":3,"is_corresponding":false},{"id":23991,"name":"Christina Boucher","orcid":"0000-0001-9509-9725","position":4,"is_corresponding":false},{"id":662070,"name":"Travis Gagie","orcid":"0000-0003-3689-327X","position":5,"is_corresponding":false},{"id":1186071,"name":"Aaron Hong","orcid":"0000-0002-1361-7216","position":0,"is_corresponding":true}],"reference_count":0,"raw_metadata":{"citation_network_status":"fetched"},"created_at":"2026-07-19T01:22:15.958504Z","pmid":"41179999","pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":null,"fair_a":null,"fair_i":null,"fair_r":null,"fair_zscore":null,"fair_rationale":null,"fair_model":null,"fair_agent_version":null,"fair_fulltext_source":null,"fair_has_llm":null,"fair_computed_at":null,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}