65 citations · 333 across the 44 of their papers we have counts for
7 papers · 1 filter
Searching and Indexing Genomic Databases via Kernelization
Travis Gagie, Simon J. Puglisi
The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advant…
Queries on LZ-Bounded Encodings
Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski +4
We describe a data structure that stores a string in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries ar…
Misassembly Detection using Paired-End Sequence Reads and Optical Mapping Data
Martin D. Muggli, Simon J. Puglisi, Roy Ronen +1
A crucial problem in genome assembly is the discovery and correction of misassembly errors in draft genomes. We develop a method that will enhance the quality of draft genomes by i…
Variable-Order de Bruijn Graphs
Christina Boucher, Alex Bowe, Travis Gagie +2
The de Bruijn graph of a set of strings is a key data structure in genome assembly that represents overlaps between all the -length substrings of . Construction and…
Document Counting in Practice
Travis Gagie, Aleksi Hartikainen, Juha Kärkkäinen +3
We address the problem of counting the number of strings in a collection where a given pattern appears, which has applications in information retrieval and data mining. Existing so…
Rank, select and access in grammar-compressed strings
Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei
Given a string of length on a fixed alphabet of symbols, a grammar compressor produces a context-free grammar of size that generates and only . In this p…