License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2022.29
URN: urn:nbn:de:0030-drops-161564
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16156/
Díaz-Domínguez, Diego ;
Navarro, Gonzalo
Efficient Construction of the BWT for Repetitive Text Using String Compression
Abstract
We present a new semi-external algorithm that builds the Burrows-Wheeler transform variant of Bauer et al. (a.k.a., BCR BWT) in linear expected time. Our method uses compression techniques to reduce the computational costs when the input is massive and repetitive. Concretely, we build on induced suffix sorting (ISS) and resort to run-length and grammar compression to maintain our intermediate results in compact form. Our compression format not only saves space, but it also speeds up the required computations. Our experiments show important savings in both space and computation time when the text is repetitive. On average, we are 3.7x faster than the baseline compressed approach, while maintaining a similar memory consumption. These results make our method stand out as the only one (to our knowledge) that can build the BCR BWT of a collection of 25 human genomes (75 GB) in about 7.3 hours, and using only 27 GB of working memory.
BibTeX - Entry
@InProceedings{diazdominguez_et_al:LIPIcs.CPM.2022.29,
author = {D{\'\i}az-Dom{\'\i}nguez, Diego and Navarro, Gonzalo},
title = {{Efficient Construction of the BWT for Repetitive Text Using String Compression}},
booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
pages = {29:1--29:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-234-1},
ISSN = {1868-8969},
year = {2022},
volume = {223},
editor = {Bannai, Hideo and Holub, Jan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16156},
URN = {urn:nbn:de:0030-drops-161564},
doi = {10.4230/LIPIcs.CPM.2022.29},
annote = {Keywords: BWT, string compression, repetitive text}
}
