Iterative dictionary construction for compression of large DNA data sets.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Genomic data repositories contain vast amounts of individual and reference sequences.
• These sequences often share long identical or near-identical nucleotide strings.
• Current compression algorithms fail to detect these long-range repetitions due to sequential processing and data volume.

Purpose of the Study:

• To develop and explore a novel dictionary construction method for improved repeat identification in large DNA datasets.
• To adapt an existing disk-based method for efficient compression of genomic collections.
• To enable effective compression of large-scale genomic data while allowing random access.

Main Methods:

• An order-insensitive, disk-based dictionary construction approach was adapted.
• The method, COMRAD (Compression of Repeated DNA), identifies exact repeated content within and across sequence collections.
• Data compression is achieved through multiple passes, optimizing for large datasets.

Main Results:

• COMRAD effectively identifies exact repeated content in large DNA datasets.
• The method compresses large datasets within reasonable time and space constraints.
• Demonstrated significant compression ratios, e.g., 39 S. cerevisiae genomes compressed to 0.25 bits per base.
• Allows random access to individual sequences and subsequences without decompressing the entire dataset.

Conclusions:

• COMRAD offers superior compression capabilities for very large genomic datasets compared to existing methods.
• The approach is competitive for smaller datasets and provides efficient random access functionality.
• COMRAD addresses the challenge of compressing repetitive elements in genomic data collections effectively.