The Burrows–Wheeler Transform (BWT) is a reversible transformation on which are based several text compressors and many other tools used in Bioinformatics and Computational Biology. The BWT is not actually a compressor, but a transformation that performs a context-dependent permutation of the letters of the input text that often create runs of equal letters (clusters) longer than the ones in the original text, usually referred to as the “clustering effect” of BWT. In particular, from a combinatorial point of view, great attention has been given to the case in which the BWT produces the fewest number of clusters (cf. [5,16,21,23],). In this paper we are concerned about the cases when the clustering effect of the BWT is not achieved. For this purpose we introduce a complexity measure that counts the number of equal-letter runs of a word. This measure highlights that there exist many words for which BWT gives an “un-clustering effect”, that is BWT produce a great number of short clusters. More in general we show that the application of BWT to any word at worst doubles the number of equal-letter runs. Moreover, we prove that this bound is tight by exhibiting some families of words where such upper bound is always reached. We also prove that for binary words the case in which the BWT produces the maximal number of clusters is related to the very well known Artin's conjecture on primitive roots. The study of some combinatorial properties underlying this transformation could be useful for improving indexing and compression strategies.

Mantaci, S., Restivo, A., Rosone, G., Sciortino, M., Versari, L. (2017). Measuring the clustering effect of BWT via RLE. THEORETICAL COMPUTER SCIENCE, 698, 79-87 [10.1016/j.tcs.2017.07.015].

Measuring the clustering effect of BWT via RLE

Mantaci, Sabrina;Sciortino, Marinella
;
2017-01-01

Abstract

The Burrows–Wheeler Transform (BWT) is a reversible transformation on which are based several text compressors and many other tools used in Bioinformatics and Computational Biology. The BWT is not actually a compressor, but a transformation that performs a context-dependent permutation of the letters of the input text that often create runs of equal letters (clusters) longer than the ones in the original text, usually referred to as the “clustering effect” of BWT. In particular, from a combinatorial point of view, great attention has been given to the case in which the BWT produces the fewest number of clusters (cf. [5,16,21,23],). In this paper we are concerned about the cases when the clustering effect of the BWT is not achieved. For this purpose we introduce a complexity measure that counts the number of equal-letter runs of a word. This measure highlights that there exist many words for which BWT gives an “un-clustering effect”, that is BWT produce a great number of short clusters. More in general we show that the application of BWT to any word at worst doubles the number of equal-letter runs. Moreover, we prove that this bound is tight by exhibiting some families of words where such upper bound is always reached. We also prove that for binary words the case in which the BWT produces the maximal number of clusters is related to the very well known Artin's conjecture on primitive roots. The study of some combinatorial properties underlying this transformation could be useful for improving indexing and compression strategies.
2017
Mantaci, S., Restivo, A., Rosone, G., Sciortino, M., Versari, L. (2017). Measuring the clustering effect of BWT via RLE. THEORETICAL COMPUTER SCIENCE, 698, 79-87 [10.1016/j.tcs.2017.07.015].
File in questo prodotto:
File Dimensione Formato  
TCS 2017.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 341.6 kB
Formato Adobe PDF
341.6 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
MRRSV_TCS2017 - revised2 postprint.pdf

accesso aperto

Tipologia: Post-print
Dimensione 311.15 kB
Formato Adobe PDF
311.15 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/259706
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 12
social impact