Dynamic compression schemes for graph coloring.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• High-throughput DNA sequencing generates vast amounts of data, posing storage and querying challenges.
• Existing data representations like assembly graphs lack efficient indexing and contextual information.

Purpose of the Study:

• To develop novel compression strategies for graph coloring in assembly graphs.
• To improve the queryability and accessibility of large-scale biomedical sequencing data.

Main Methods:

• A lossless compression scheme using wavelet tries.
• A highly accurate lossy compression scheme utilizing Bloom filters.
• Development of construction and merge procedures for both methods.

Main Results:

• Achieved memory reductions of up to three orders of magnitude by employing lossy compression and topological information.
• Developed methods that retain coloring information even with graph topology additions.
• Demonstrated efficient parallelization and dynamic usability through modular color representation.

Conclusions:

• The proposed compression approaches significantly reduce memory requirements for assembly graphs.
• These methods enhance the scalability and dynamic use of sequencing data for biomedical research.
• Open-source implementations and datasets are publicly available for community use.