Journal
2021 DATA COMPRESSION CONFERENCE (DCC 2021)
Volume -, Issue -, Pages 83-92Publisher
IEEE COMPUTER SOC
DOI: 10.1109/DCC50243.2021.00016
Keywords
-
Categories
Funding
- ANID Basal Funds [FB0001, 21171332]
Ask authors/readers for more resources
This study presents a grammar for DNA sequencing reads that allows for direct computation of the BWT, enabling genomic analyses in succinct space that require complex string queries. Experimental results show that the space reduction achieved by the compressor is competitive with LZ-based methods and superior to entropy-based approaches, offering an average of 12% additional compression and requiring less working space and time compared to other popular grammars in this type of data.
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% extra compression and require less working space and time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available