143 citations · 479 across the 107 of their papers we have counts for
125 papers
Taxonomic Classification with Complete Tag Arrays
Travis Gagie, Gonzalo Navarro
Taxonomic classifiers such as Kraken assign each -mer of a reference database to the lowest common ancestor (LCA) of the genomes containing it, but this works less well as datab…
Mixing FM-indexes and CSAs: backward search over an order-1 rank encoding
Travis Gagie
FM-indexes and compressed suffix arrays (CSAs) are often treated as interchangeable, but they behave differently as the alphabet grows. An FM-index step costs about one cache miss…
Compressed Set Representations based on Set Difference
Travis Gagie, Meng He, Gonzalo Navarro
We introduce a compressed representation of sets of sets that exploits how much they differ from each other. Our representation supports access, membership, predecessor and success…
Fast and Small Subsampled R-indexes
Dustin Cobas, Travis Gagie, Gonzalo Navarro
The -index represented a breakthrough in compressed indexing of repetitive text collections, outperforming its alternatives by orders of magnitude in query time. Its space usage…
Faster run-length compressed suffix arrays
Nathaniel K. Brown, Travis Gagie, Giovanni Manzini +2
We first review how we can store a run-length compressed suffix array (RLCSA) for a text of length over an alphabet of size whose Burrows-Wheeler Transform (BWT) consis…
How to Find Long Maximal Exact Matches and Ignore Short Ones
Travis Gagie
Finding maximal exact matches (MEMs) between strings is an important task in bioinformatics, but it is becoming increasingly challenging as geneticists switch to pangenomic referen…