A grammar compressor for collections of reads with applications to the construction of the BWT
This work addresses the need for efficient storage and querying of genomic data for bioinformatics researchers, though it is incremental as it builds on existing grammar and compression methods.
The authors tackled the problem of performing genomic analyses requiring complex string queries in succinct space by developing a grammar compressor for DNA sequencing reads that can compute the Burrows-Wheeler Transform (BWT) directly, achieving on average 12% extra compression compared to other grammars and competitive space reduction with LZ-based methods.
We describe a grammar for DNA sequencing reads from which we can compute the BWT directly. Our motivation is to perform in succinct space genomic analyses that require complex string queries not yet supported by repetition-based self-indexes. Our approach is to store the set of reads as a grammar, but when required, compute its BWT to carry out the analysis by using self-indexes. Our experiments in real data showed that the space reduction we achieve with our compressor is competitive with LZ-based methods and better than entropy-based approaches. Compared to other popular grammars, in this kind of data, we achieve, on average, 12\% of extra compression and require less working space and time.