143 citations · 479 across the 107 of their papers we have counts for
11 papers · 1 filter
A fast and simple -space index for finding approximately longest common substrings
Nick Fagan, Jorge Hermo González, Travis Gagie
We describe how, given a text and a positive constant , we can build a simple -space index, where is the number of phrases in the LZ77 parse of ,…
Space-efficient RLZ-to-LZ77 conversion
Travis Gagie
Consider a text prefixed by a reference sequence . We show how, given and the -phrase relative Lempel-Ziv parse of with respec…
Space-efficient conversions from SLPs
Travis Gagie, Adrián Goga, Artur Jeż +1
We give algorithms that, given a straight-line program (SLP) with rules that generates (only) a text , builds within space the Lempel-Ziv (LZ) parse of (of…
Augmented Thresholds for MONI
César Martínez-Guardiola, Nathaniel K. Brown, Fernando Silva-Coira +3
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 thi…
Ruler Rolling
Xing Lyu, Travis Gagie, Meng He
At CCCG '21 O'Rourke proposed a variant of Hopcroft, Josephs and Whitesides' (1985) NP-complete problem {\sc Ruler Folding}, which he called {\sc Ruler Wrapping} and for which all…
MARIA: Multiple-alignment -index with aggregation
Adrián Goga, Andrej Baláž, Alessia Petescia +1
There now exist compact indexes that can efficiently list all the occurrences of a pattern in a dataset consisting of thousands of genomes, or even all the occurrences of all the p…