4 papers · 1 filter
Optimal-Time Move Structure Construction
Nathaniel K. Brown, Ahsan Sanaullah, Shaojie Zhang +1
The move structure represents a permutation of by partitioning the domain into disjoint, contiguously permuted intervals, with being the minimum number of su…
Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
Nathaniel K. Brown, Ben Langmead
The move structure represents permutations with long contiguously permuted intervals in compressed space with optimal query time. They have become an important feature of compresse…
MIOV: Reordering MOVI for even better locality
Peter Perešíni, Nathaniel K. Brown, Travis Gagie +1
We consider how to reorder the rows of Nishimoto and Tabei's move structure such that we more often move from one row to the next in memory.
Faster Maximal Exact Matches with Lazy LCP Evaluation
Adrián Goga, Lore Depuydt, Nathaniel K. Brown +3
MONI (Rossi et al., {\it JCB} 2022) is a BWT-based compressed index for computing the matching statistics and maximal exact matches (MEMs) of a pattern (usually a DNA read) with re…