65 citations · 333 across the 44 of their papers we have counts for
5 papers · 1 filter
AliBI: An Alignment-Based Index for Genomic Datasets
Hector Ferrada, Travis Gagie, Tommi Hirvola +1
With current hardware and software, a standard computer can now hold in RAM an index for approximate pattern matching on about half a dozen human genomes. Sequencing technologies h…
Lempel-Ziv Parsing in External Memory
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
For decades, computing the LZ factorization (or LZ77 parsing) of a string has been a requisite and computationally intensive step in many diverse applications, including text index…
Hybrid Indexes for Repetitive Datasets
H. Ferrada, T. Gagie, T. Hirvola +1
Advances in DNA sequencing mean databases of thousands of human genomes will soon be commonplace. In this paper we introduce a simple technique for reducing the size of conventiona…
Order Preserving Matching
Jinil Kim, Peter Eades, Rudolf Fleischer +5
We introduce a new string matching problem called order-preserving matching on numeric strings where a pattern matches a text if the text contains a substring whose relative orders…
Lightweight Lempel-Ziv Parsing
Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi
We introduce a new approach to LZ77 factorization that uses O(n/d) words of working space and O(dn) time for any d >= 1 (for polylogarithmic alphabet sizes). We also describe caref…