b'Travis Gagie'

research

∙ 08/18/2023

Wheeler maps

Motivated by challenges in pangenomic read alignment, we propose a gener...

0 Andrej Balaz, et al. ∙

research

∙ 08/15/2023

Another virtue of wavelet forests?

A wavelet forest for a text T [1..n] over an alphabet σ takes n H_0 (T) ...

0 Christina Boucher, et al. ∙

research

∙ 06/09/2023

Space-time Trade-offs for the LCP Array of Wheeler DFAs

Recently, Conte et al. generalized the longest-common prefix (LCP) array...

0 Nicola Cotumaccio, et al. ∙

research

∙ 05/10/2023

Acceleration of FM-index Queries Through Prefix-free Parsing

FM-indexes are a crucial data structure in DNA alignment, for example, b...

0 Aaron Hong, et al. ∙

research

∙ 05/05/2023

Sum-of-Local-Effects Data Structures for Separable Graphs

It is not difficult to think of applications that can be modelled as gra...

0 Xing Lyu, et al. ∙

research

∙ 01/13/2023

Computing matching statistics on Wheeler DFAs

Matching statistics were introduced to solve the approximate string matc...

0 Alessio Conte, et al. ∙

research

∙ 12/05/2022

Space-efficient conversions from SLPs

Given a straight-line program with g rules for a text T [1..n], we can b...

0 Travis Gagie, et al. ∙

research

∙ 11/24/2022

A fast and simple O (z log n)-space index for finding approximately longest common substrings

We describe how, given a text T [1..n] and a positive constant ϵ, we can...

0 Nick Fagan, et al. ∙

research

∙ 11/23/2022

Space-efficient RLZ-to-LZ77 conversion

Consider a text T [1..n] prefixed by a reference sequence R = T [1..ℓ]. ...

0 Travis Gagie, et al. ∙

research

∙ 11/14/2022

Augmented Thresholds for MONI

MONI (Rossi et al., 2022) can store a pangenomic dataset T in small spac...

0 César Martínez-Guardiola, et al. ∙

research

∙ 10/04/2022

Rectangular Ruler Wrapping

In 1985 Hopcroft, Joseph and Whitesides introduced the problem of foldin...

0 Xing Lyu, et al. ∙

research

∙ 09/19/2022

MARIA: Multiple-alignment r-index with aggregation

There now exist compact indexes that can efficiently list all the occurr...

0 Adrian Goga, et al. ∙

research

∙ 08/21/2022

Teaching the Burrows-Wheeler Transform via the Positional Burrows-Wheeler Transform

The Burrows-Wheeler Transform (BWT) is often taught in undergraduate cou...

0 Travis Gagie, et al. ∙

research

∙ 06/13/2022

KATKA: A KRAKEN-like tool with k given at query time

We describe a new tool, KATKA, that stores a phylogenetic tree T such th...

0 Travis Gagie, et al. ∙

research

∙ 04/17/2022

An n H_k-compressed searchable partial-sums data structure for static sequences of sublogarithmic positive integers

We consider the space needed to store a searchable partial-sums data str...

0 Travis Gagie, et al. ∙

research

∙ 03/28/2022

Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices

As nowadays Machine Learning (ML) techniques are generating huge data co...

0 Paolo Ferragina, et al. ∙

research

∙ 02/10/2022

MONI can find k-MEMs

Maximal exact matches (MEMs) have been widely used in bioinformatics at ...

0 Travis Gagie, et al. ∙

research

∙ 12/08/2021

RLBWT Tricks

Experts would probably have guessed that compressed sparse bitvectors we...

0 Nathaniel K. Brown, et al. ∙

research

∙ 09/29/2021

Ruler Wrapping

We propose a natural variation of the Hopcroft, Joseph and Whitesides' (...

0 Travis Gagie, et al. ∙

research

∙ 09/07/2021

Simple Worst-Case Optimal Adaptive Prefix-Free Coding

Gagie and Nekrich (2009) gave an algorithm for adaptive prefix-free codi...

0 Travis Gagie, et al. ∙

research

∙ 05/11/2021

Compact Euler Tours of Trees with Small Maximum Degree

We show how an Euler tour for a tree on n vertices with maximum degree d...

0 Travis Gagie, et al. ∙

research

∙ 03/29/2021

A Fast and Small Subsampled R-index

The r-index (Gagie et al., JACM 2020) represented a breakthrough in comp...

0 Dustin Cobas, et al. ∙

research

∙ 01/29/2021

r-indexing Wheeler graphs

Let G be a Wheeler graph and r be the number of runs in a Burrows-Wheele...

0 Travis Gagie, et al. ∙

research

∙ 11/11/2020

PHONI: Streamed Matching Statistics with Multi-Genome References

Computing the matching statistics of patterns with respect to a text is ...

0 Christina Boucher, et al. ∙

research

∙ 06/21/2020

PFP Data Structures

Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a p...

0 Christina Boucher, et al. ∙

research

∙ 11/20/2019

Faster Dynamic Compressed d-ary Relations

The k^2-tree is a successful compact representation of binary relations ...

0 Diego Arroyuelo, et al. ∙

research

∙ 10/16/2019

Tree-Shape Grammars for Random Access

Shape grammars are well known in the graphics and design communities but...

0 Travis Gagie, et al. ∙

research

∙ 08/04/2019

Matching reads to many genomes with the r-index

The r-index is a tool for compressed indexing of genomic databases for e...

0 Taher Mun, et al. ∙

research

∙ 06/03/2019

Rpair: Rescaling RePair with Rsync

Data compression is a powerful tool for managing massive but repetitive ...

0 Travis Gagie, et al. ∙

research

∙ 01/29/2019

Simulating the DNA String Graph in Succinct Space

Converting a set of sequencing reads into a lossless compact data struct...

0 Diego Díaz-Domínguez, et al. ∙

research

∙ 11/16/2018

Efficient Construction of a Complete Index for Pan-Genomics Read Alignment

While short read aligners, which predominantly use the FM-index, are abl...

0 Alan Kuhnle, et al. ∙

research

∙ 11/06/2018

Tunneling on Wheeler Graphs

The Burrows-Wheeler Transform (BWT) is an important technique both in da...

0 Jarno Alanko, et al. ∙

research

∙ 10/12/2018

Relative compression of trajectories

We present RCT, a new compact data structure to represent trajectories o...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 09/19/2018

The Read-Optimized Burrows-Wheeler Transform

The advent of high-throughput sequencing has resulted in massive genomic...

0 Travis Gagie, et al. ∙

research

∙ 09/08/2018

Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space

Indexing highly repetitive texts --- such as genomic databases, software...

0 Travis Gagie, et al. ∙

research

∙ 06/05/2018

Tree Path Majority Data Structures

We present the first solution to τ-majorities on tree paths. Given a tre...

0 Travis Gagie, et al. ∙

research

∙ 05/14/2018

Assembling Omnitigs using Hidden-Order de Bruijn Graphs

De novo DNA assembly is a fundamental task in Bioinformatics, and findin...

0 Diego Díaz-Domínguez, et al. ∙

research

∙ 03/29/2018

Prefix-Free Parsing for Building Big BWTs

High-throughput sequencing technologies have led to explosive growth of ...

0 Travis Gagie, et al. ∙

research

∙ 03/04/2018

Two-Dimensional Block Trees

The Block Tree (BT) is a novel compact data structure designed to compre...

0 Nieves R. Brisaboa, et al. ∙

research

∙ 02/28/2018

Fast Lempel-Ziv Decompression in Linear Space

We consider the problem of decompressing the Lempel-Ziv 77 representatio...

0 Philip Bille, et al. ∙

research

∙ 02/16/2018

Online LZ77 Parsing and Matching Statistics with RLBWTs

Lempel-Ziv 1977 (LZ77) parsing, matching statistics and the Burrows-Whee...

0 Hideo Bannai, et al. ∙

research

∙ 11/20/2017

A Separation Between Run-Length SLPs and LZ77

In this paper we give an infinite family of strings for which the length...

0 Philip Bille, et al. ∙

Travis Gagie

Featured Co-authors