Augmented Thresholds for MONI

Martínez-Guardiola, César; Brown, Nathaniel K.; Silva-Coira, Fernando; Köppl, Dominik; Gagie, Travis; Ladra, Susana

Título

Autor(es)

Martínez-Guardiola, César

Brown, Nathaniel K.

Silva-Coira, Fernando

Köppl, Dominik

Gagie, Travis

Ladra, Susana

Data

2023

Cita bibliográfica

C. Martínez-Guardiola, N. K. Brown, F. Silva-Coira, D. Köppl, T. Gagie and S. Ladra, "Augmented Thresholds for MONI," 2023 Data Compression Conference (DCC), Snowbird, UT, USA, 2023, pp. 268-277, doi: 10.1109/DCC55655.2023.00035.

É version de

https://doi.org/10.1109/DCC55655.2023.00035

Resumo

[Abstract]: MONI (Rossi et al., 2022) can store a pangenomic dataset T in small space and later, given a pattern P, quickly find the maximal exact matches (MEMs) of P with respect to T. In this paper we consider its one-pass version (Boucher et al., 2021), whose query times are dominated in our experiments by longest common extension (LCE) queries. We show how a small modification lets us avoid most of these queries which significantly speeds up MONI in practice while only slightly increasing its size.

Palabras chave

Longest common extensions
Maximal exact matches
One-pass
Query time
Speed up

Descrición

© 2023 IEEE. This version of the article has been accepted for publication, after peer review. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The Version of Record is available online at: https://doi.org/10.1109/DCC55655.2023.00035