Use this link to cite:

http://hdl.handle.net/2183/35636

Augmented Thresholds for MONI

Thumbnail Image

Files

MartinezGuardiola_Cesar_2023_Augmented_Thresholds_for_MONI.pdf (568.96 KB)

Identifiers

URI: http://hdl.handle.net/2183/35636
DOI: 10.1109/DCC55655.2023.00035

Publication date

2023

Authors

Martínez-Guardiola, César
Brown, Nathaniel K.
Köppl, Dominik
Gagie, Travis

Advisors

Other responsabilities

Journal Title

Bibliographic citation

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.

Type of academic work

Academic degree

Abstract

[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.

Description

© 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

Keywords

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

Editor version

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

Rights

© 2023 IEEE.

Collections

Investigación (FIC)