5 papers · 1 filter
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…
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…
Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
Tuukka Norri, Bastien Cazaux, Dmitry Kosolobov +1
Given a threshold and a set of haplotype sequences, each having length , the minimum segmentation problem for founder reconstruction…
The Compressed Overlap Index
Rodrigo Canovas, Bastien Cazaux, Eric Rivals
For analysing text algorithms, for computing superstrings, or for testing random number generators, one needs to compute all overlaps between any pairs of words in a given set. The…