research
∙
08/18/2023
Wheeler maps
Motivated by challenges in pangenomic read alignment, we propose a gener...
share
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) ...
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...
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...
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...
research
∙
01/13/2023
Computing matching statistics on Wheeler DFAs
Matching statistics were introduced to solve the approximate string matc...
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...
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...
research
∙
11/23/2022
Space-efficient RLZ-to-LZ77 conversion
Consider a text T [1..n] prefixed by a reference sequence R = T [1..ℓ]. ...
research
∙
11/14/2022
Augmented Thresholds for MONI
MONI (Rossi et al., 2022) can store a pangenomic dataset T in small spac...
research
∙
10/04/2022
Rectangular Ruler Wrapping
In 1985 Hopcroft, Joseph and Whitesides introduced the problem of foldin...
research
∙
09/19/2022
MARIA: Multiple-alignment r-index with aggregation
There now exist compact indexes that can efficiently list all the occurr...
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...
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...
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...
research
∙
03/28/2022
Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices
As nowadays Machine Learning (ML) techniques are generating huge data co...
research
∙
02/10/2022
MONI can find k-MEMs
Maximal exact matches (MEMs) have been widely used in bioinformatics at ...
research
∙
12/08/2021
RLBWT Tricks
Experts would probably have guessed that compressed sparse bitvectors we...
research
∙
09/29/2021
Ruler Wrapping
We propose a natural variation of the Hopcroft, Joseph and Whitesides' (...
research
∙
09/07/2021
Simple Worst-Case Optimal Adaptive Prefix-Free Coding
Gagie and Nekrich (2009) gave an algorithm for adaptive prefix-free codi...
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...
research
∙
03/29/2021
A Fast and Small Subsampled R-index
The r-index (Gagie et al., JACM 2020) represented a breakthrough in comp...
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...
research
∙
11/11/2020
PHONI: Streamed Matching Statistics with Multi-Genome References
Computing the matching statistics of patterns with respect to a text is ...
research
∙
06/21/2020
PFP Data Structures
Prefix-free parsing (PFP) was introduced by Boucher et al. (2019) as a p...
research
∙
11/20/2019
Faster Dynamic Compressed d-ary Relations
The k^2-tree is a successful compact representation of binary relations ...
research
∙
10/16/2019
Tree-Shape Grammars for Random Access
Shape grammars are well known in the graphics and design communities but...
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...
research
∙
06/03/2019
Rpair: Rescaling RePair with Rsync
Data compression is a powerful tool for managing massive but repetitive ...
research
∙
01/29/2019
Simulating the DNA String Graph in Succinct Space
Converting a set of sequencing reads into a lossless compact data struct...
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...
research
∙
11/06/2018
Tunneling on Wheeler Graphs
The Burrows-Wheeler Transform (BWT) is an important technique both in da...
research
∙
10/12/2018
Relative compression of trajectories
We present RCT, a new compact data structure to represent trajectories o...
research
∙
09/19/2018
The Read-Optimized Burrows-Wheeler Transform
The advent of high-throughput sequencing has resulted in massive genomic...
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...
research
∙
06/05/2018
Tree Path Majority Data Structures
We present the first solution to τ-majorities on tree paths. Given a tre...
research
∙
05/14/2018
Assembling Omnitigs using Hidden-Order de Bruijn Graphs
De novo DNA assembly is a fundamental task in Bioinformatics, and findin...
research
∙
03/29/2018
Prefix-Free Parsing for Building Big BWTs
High-throughput sequencing technologies have led to explosive growth of ...
research
∙
03/04/2018
Two-Dimensional Block Trees
The Block Tree (BT) is a novel compact data structure designed to compre...
research
∙
02/28/2018
Fast Lempel-Ziv Decompression in Linear Space
We consider the problem of decompressing the Lempel-Ziv 77 representatio...
research
∙
02/16/2018
Online LZ77 Parsing and Matching Statistics with RLBWTs
Lempel-Ziv 1977 (LZ77) parsing, matching statistics and the Burrows-Whee...
research
∙
11/20/2017
