Cargando…

PFP-FM: An Accelerated FM-index

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 [1] observed in 2007 that word-based indexes often use fewer random accesses than character-based indexes, and thus sup...

Descripción completa

Detalles Bibliográficos
Autores principales: Hong, Aaron, Oliva, Marco, Köppl, Dominik, Bannai, Hideo, Boucher, Christina, Gagie, Travis
Formato: Online Artículo Texto
Lenguaje:English
Publicado: American Journal Experts 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10635359/
https://www.ncbi.nlm.nih.gov/pubmed/37961504
http://dx.doi.org/10.21203/rs.3.rs-3487536/v1
_version_ 1785146332234645504
author Hong, Aaron
Oliva, Marco
Köppl, Dominik
Bannai, Hideo
Boucher, Christina
Gagie, Travis
author_facet Hong, Aaron
Oliva, Marco
Köppl, Dominik
Bannai, Hideo
Boucher, Christina
Gagie, Travis
author_sort Hong, Aaron
collection PubMed
description 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 [1] 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. [2] 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 is consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it seems 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.
format Online
Article
Text
id pubmed-10635359
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher American Journal Experts
record_format MEDLINE/PubMed
spelling pubmed-106353592023-11-13 PFP-FM: An Accelerated FM-index Hong, Aaron Oliva, Marco Köppl, Dominik Bannai, Hideo Boucher, Christina Gagie, Travis Res Sq Article 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 [1] 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. [2] 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 is consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it seems 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. American Journal Experts 2023-10-30 /pmc/articles/PMC10635359/ /pubmed/37961504 http://dx.doi.org/10.21203/rs.3.rs-3487536/v1 Text en https://creativecommons.org/licenses/by/4.0/This work is licensed under a Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/) , which allows reusers to distribute, remix, adapt, and build upon the material in any medium or format, so long as attribution is given to the creator. The license allows for commercial use.
spellingShingle Article
Hong, Aaron
Oliva, Marco
Köppl, Dominik
Bannai, Hideo
Boucher, Christina
Gagie, Travis
PFP-FM: An Accelerated FM-index
title PFP-FM: An Accelerated FM-index
title_full PFP-FM: An Accelerated FM-index
title_fullStr PFP-FM: An Accelerated FM-index
title_full_unstemmed PFP-FM: An Accelerated FM-index
title_short PFP-FM: An Accelerated FM-index
title_sort pfp-fm: an accelerated fm-index
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10635359/
https://www.ncbi.nlm.nih.gov/pubmed/37961504
http://dx.doi.org/10.21203/rs.3.rs-3487536/v1
work_keys_str_mv AT hongaaron pfpfmanacceleratedfmindex
AT olivamarco pfpfmanacceleratedfmindex
AT koppldominik pfpfmanacceleratedfmindex
AT bannaihideo pfpfmanacceleratedfmindex
AT boucherchristina pfpfmanacceleratedfmindex
AT gagietravis pfpfmanacceleratedfmindex