A grammar compressor for collections of reads with applications to the construction of the BWT
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.
Code (1)
Similar Papers 제목 키워드 기반
Efficient construction of the extended BWT from grammar-compressed DNA sequencing reads
We present an algorithm for building the extended BWT (eBWT) of a string collection from its grammar-compressed representation. Our technique exploits the string repetitions captured by the grammar to boost the computati…
SpreadsheetLLM: Encoding Spreadsheets for Large Language Models
Spreadsheets, with their extensive two-dimensional grids, various layouts, and diverse formatting options, present notable challenges for large language models (LLMs). In response, we introduce SpreadsheetLLM, pioneering…
In-Context LearningTable DetectionOh That Looks Familiar: A Novel Similarity Measure for Spreadsheet Template Discovery
Traditional methods for identifying structurally similar spreadsheets fail to capture the spatial layouts and type patterns defining templates. To quantify spreadsheet similarity, we introduce a hybrid distance metric th…
Fast, Small, and Simple Document Listing on Repetitive Text Collections
Document listing on string collections is the task of finding all documents where a pattern appears. It is regarded as the most fundamental document retrieval problem, and is useful in various applications. Many of the f…
Retrieval