Fast lossless compression via cascading Bloom filters.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Large Next Generation Sequencing (NGS) datasets incur significant storage and transfer costs.
• Efficient lossless compression is crucial for managing NGS data while retaining future analytical capabilities.
• Existing NGS compression methods include generic algorithms and NGS-specific schemes, with reference-based methods offering better compression but requiring extensive alignment time.

Purpose of the Study:

• To develop a novel, highly efficient compression method for NGS reads.
• To significantly reduce the computational time required for compressing NGS data.
• To offer an alternative to existing reference-based and reference-free compression techniques.

Main Methods:

• A new reference-based compression approach, BARCODE, is introduced.
• BARCODE utilizes Bloom filters to encode NGS reads without prior alignment.
• Reads are hashed into Bloom filters, and decoding involves querying these filters with reference genome subsequences; a cascade of filters enhances compression.

Main Results:

• BARCODE achieves compression rates superior to reference-free methods and is significantly faster than traditional reference-based methods.
• The method demonstrates an order of magnitude improvement in speed compared to reference-based approaches.
• BARCODE offers an order of magnitude improvement in compression over reference-free methods across various sequencing coverages.

Conclusions:

• BARCODE provides a substantial reduction in compression time and improved compression efficiency for NGS data.
• The method achieves 80-90% savings in running time with only a slight increase in space in high-coverage scenarios.
• BARCODE represents a significant advancement in efficient NGS data management.