143 citations · 479 across the 107 of their papers we have counts for
7 papers · 1 filter
Compressed Spaced Suffix Arrays
Travis Gagie, Giovanni Manzini, Daniel Valenzuela
Spaced seeds are important tools for similarity search in bioinformatics, and using several seeds together often significantly improves their performance. With existing approaches,…
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…
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…
Heaviest Induced Ancestors and Longest Common Substrings
Travis Gagie, Paweł Gawrychowski, Yakov Nekrich
Suppose we have two trees on the same set of leaves, in which nodes are weighted such that children are heavier than their parents. We say a node from the first tree and a node fro…
Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
Ferdinando Cicalese, Travis Gagie, Emanuele Giaquinta +4
We consider how to index strings, trees and graphs for jumbled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing…
New Algorithms for Position Heaps
Travis Gagie, Wing-Kai Hon, Tsung-Han Ku
We present several results about position heaps, a relatively new alternative to suffix trees and suffix arrays. First, we show that, if we limit the maximum length of patterns to…