Indexing highly repetitive string collections, part II: Compressed indexes
G Navarro - ACM Computing Surveys (CSUR), 2021 - dl.acm.org
Two decades ago, a breakthrough in indexing string collections made it possible to
represent them within their compressed space while at the same time offering indexed …
represent them within their compressed space while at the same time offering indexed …
A survey of BWT variants for string collections
D Cenzato, Z Lipták - Bioinformatics, 2024 - academic.oup.com
Motivation In recent years, the focus of bioinformatics research has moved from individual
sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler …
sequences to collections of sequences. Given the fundamental role of the Burrows-Wheeler …
[HTML][HTML] Sensitivity of string compressors and repetitiveness measures
T Akagi, M Funakoshi, S Inenaga - Information and Computation, 2023 - Elsevier
The sensitivity of a string compression algorithm C asks how much the output size C (T) for
an input string T can increase when a single character edit operation is performed on T. This …
an input string T can increase when a single character edit operation is performed on T. This …
A survey of BWT variants for string collections
D Cenzato, Z Lipták - arXiv preprint arXiv:2202.13235, 2022 - arxiv.org
In recent years, the focus of bioinformatics research has moved from individual sequences to
collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform …
collections of sequences. Given the fundamental role of the Burrows-Wheeler Transform …
Bit catastrophes for the burrows-wheeler transform
A bit catastrophe, loosely defined, is when a change in just one character of a string causes
a significant change in the size of the compressed string. We study this phenomenon for the …
a significant change in the size of the compressed string. We study this phenomenon for the …
[HTML][HTML] On the number of equal-letter runs of the bijective Burrows-Wheeler transform
Abstract The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT
[Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is …
[Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is …
Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words
In this paper we study the number r bwt of equal-letter runs produced by the Burrows-
Wheeler transform (BWT) when it is applied to purely morphic finite words, which are words …
Wheeler transform (BWT) when it is applied to purely morphic finite words, which are words …
Iterated straight-line programs
We explore an extension to straight-line programs (SLPs) that outperforms, for some text
families, the measure δ based on substring complexity, a lower bound for most measures …
families, the measure δ based on substring complexity, a lower bound for most measures …
On the impact of morphisms on BWT-Runs
Morphisms are widely studied combinatorial objects that can be used for generating infinite
families of words. In the context of Information theory, injective morphisms are called …
families of words. In the context of Information theory, injective morphisms are called …
Indexing highly repetitive string collections
G Navarro - arXiv preprint arXiv:2004.02781, 2020 - arxiv.org
Two decades ago, a breakthrough in indexing string collections made it possible to
represent them within their compressed space while at the same time offering indexed …
represent them within their compressed space while at the same time offering indexed …