Sparse Binary Relation Representations for Genome Graph Annotation.

Area of Science:

• Bioinformatics
• Computational Biology
• Data Compression

Background:

• High-throughput DNA sequencing generates massive datasets requiring efficient storage and indexing.
• Labeled de Bruijn graphs are emerging as effective structures for representing and querying sequencing data.
• Current methods for compressing labels on these graphs are not fully explored and lack adaptability to data characteristics.

Purpose of the Study:

• To introduce a novel, adaptive compression approach for labels on de Bruijn graphs.
• To evaluate the performance of the new method against existing state-of-the-art techniques.
• To analyze how data characteristics influence compression efficiency for sequencing data.

Main Methods:

• Development of the Multi-binary relation wavelet tree (BRWT) compression method.
• Systematic analysis and evaluation of five state-of-the-art annotation compression schemes.
• Testing on both artificial and diverse real-world sequencing datasets.

Main Results:

• Achieved up to 29% improvement over the basic BRWT method.
• Demonstrated up to 68% improvement compared to current state-of-the-art de Bruijn graph label compression.
• Showcased robust performance across various real-world datasets, confirming adaptability.

Conclusions:

• The proposed Multi-binary relation wavelet tree (BRWT) offers a significant advancement in compressing labels for de Bruijn graphs.
• The method's adaptability to data sparsity and correlations leads to superior compression performance.
• This work provides valuable insights into optimizing data storage for large-scale biological sequence repositories.