Topology-based sparsification of graph annotations.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Biological sequencing data is growing exponentially, necessitating efficient storage and indexing methods.
• Labeled de Bruijn graphs are commonly used for representing large sequencing datasets.
• Current methods for storing labels on these graphs require further optimization.

Purpose of the Study:

• To introduce RowDiff, a novel technique for compacting graph labels.
• To leverage similarities in annotations of adjacent vertices for data compression.
• To provide a scalable and efficient solution for handling large-scale biological data.

Main Methods:

• RowDiff constructs compact graph labels by exploiting similarities between adjacent vertex annotations.
• The technique operates in linear time and uses space proportional to graph size.
• Construction is parallelizable and distributable, suitable for massive graphs.

Main Results:

• RowDiff combined with multi-BRWT reduced annotation footprint by 30% compared to Mantis-MST.
• RowDiff sparsification decreased individual annotation column size by an average factor of 42.
• The combined RowDiff and multi-BRWT representation was 26 times smaller than Mantis-MST.

Conclusions:

• RowDiff offers a significant advancement in compacting graph labels for biological sequencing data.
• The method is efficient, scalable, and applicable to extremely large datasets.
• RowDiff facilitates better utilization of the growing volume of genomic information for research.