86 citations · 101 across the 7 of their papers we have counts for
10 papers
Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform
Florian Ingels, Anaïs Denis, Bastien Cazaux
The Burrows-Wheeler Transform (BWT) is a fundamental component in many data structures for text indexing and compression, widely used in areas such as bioinformatics and informatio…
A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
Sangsoo Park, Sung Gwan Park, Bastien Cazaux +2
The hierarchical overlap graph (HOG) is a graph that encodes overlaps from a given set P of n strings, as the overlap graph does. A best known algorithm constructs HOG in O(||P|| l…
Algorithms and Complexity on Indexing Founder Graphs
Massimo Equi, Tuukka Norri, Jarno Alanko +3
We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this proble…
Greedy-reduction from Shortest Linear Superstring to Shortest Circular Superstring
Bastien Cazaux, Eric Rivals
A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know a…
Linear Time Construction of Indexable Founder Block Graphs
Veli Mäkinen, Bastien Cazaux, Massimo Equi +2
We introduce a compact pangenome representation based on an optimal segmentation concept that aims to reconstruct founder sequences from a multiple sequence alignment (MSA). Such f…
Strong link between BWT and XBW via Aho-Corasick automaton and applications to Run-Length Encoding
Bastien Cazaux, Eric Rivals
The boom of genomic sequencing makes compression of set of sequences inescapable. This underlies the need for multi-string indexing data structures that helps compressing the data.…