5 papers
Compact Path Representation in DAGs via Colored Edge Pebbling
Paola Bonizzoni, Alessio Conte, Gianluca Della Vedova +3
Compactly representing a variation graph is a core problem in computational pangenomics that is usually attacked with techniques that have been originated on texts and adapted to g…
Patching leaky tunnels in BWTs
Paola Bonizzoni, Davide Cozzi, Travis Gagie +2
We extend Baier's foundationial work on tunnelling Burrows-Wheeler Transforms (BWTs) by showing how something that would be a good tunnel except for a strings that diverge from the…
Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes
Paola Bonizzoni, Younan Gao, Dominik Köppl +1
We revisit the online construction of \emph{smallest suffixient sets} and the online computation of the \emph{longest repeating suffix} (LRS). We give the first compressed-space on…
Optimal-Time Mapping in Run-Length Compressed PBWT
Paola Bonizzoni, Davide Cozzi, Younan Gao
The Positional Burrows--Wheeler Transform (PBWT) is a data structure designed for efficiently representing and querying large collections of sequences, such as haplotype panels in…
On the compressiveness of the Burrows-Wheeler transform
Hideo Bannai, Tomohiro I, Yuto Nakashima
The Burrows-Wheeler transform (BWT) is a reversible transform that converts a string into another string . The size of the run-length encoded BWT (RLBWT) can b…