Technical Summary: HiDAC – A Hierarchical Dictionary-Aided Compression Framework for Genomic Sequences

1. Problem Statement

The rapid expansion of genomic data generated by Next-Generation Sequencing (NGS) has created significant challenges in storage, transmission, and analysis. While conventional lossless compression tools (e.g., Gzip, Bzip2) exist, they are optimized for general text and fail to exploit the specific characteristics of DNA sequences, such as the small four-letter alphabet and the prevalence of repetitive patterns.

Existing DNA-specific compression methods generally fall into three categories, each with limitations:

• Statistical Methods: Rely on probabilistic models (e.g., Markov chains) but often struggle with long-range dependencies and nested repeats, requiring high computational resources.
• Reference-Based Methods: Encode differences relative to a known reference genome. While effective for related genomes, they fail for metagenomic samples or divergent organisms where a suitable reference is unavailable.
• Dictionary-Based Methods: Replace recurring substrings with tokens. However, most existing approaches use greedy strategies that miss nested/hierarchical repeats and require rebuilding dictionaries for every new dataset. Crucially, the compressed output of these methods is typically opaque; analytical tasks (e.g., substring search, frequency analysis) require full decompression, negating the benefits of compression during downstream analysis.

The paper identifies a gap for a method that offers high compression efficiency while enabling compressed-domain analysis, allowing operations to be performed directly on the semi-compressed (tokenized) representation without full decompression.

2. Methodology

HiDAC (Hierarchical Dictionary-Aided Compression) is a two-stage framework designed to identify optimal recurring patterns and encode them efficiently.

2.1 Preprocessing

The input DNA sequence is cleaned by removing headers, whitespace, and invalid characters. Valid nucleotides (A, T, G, C) are converted to uppercase. Non-standard characters are recorded as metadata (location, character, run length) to ensure lossless reconstruction.

2.2 Hierarchical Dictionary Creation

The core innovation is an iterative, cost-guided substitution strategy that builds a nested dictionary:

1. Initialization: The algorithm identifies the most frequent 2-mer (pair of bases). In case of a tie, Shannon entropy is used to select the pattern with higher information content.
2. Iterative Substitution: The selected pattern is replaced by a unique non-base token. This token is stored in a dictionary and can participate in the formation of longer, composite patterns in subsequent iterations.
3. Cost Function: A custom cost function determines whether a substitution is beneficial. It evaluates the net reduction in sequence length and the balance of token frequencies.
   • For patterns containing only bases, a simple frequency check is used.
   • For composite patterns (containing existing tokens), the algorithm calculates OriginalCost (total nucleotide content represented by current tokens) and NewCost (content after substitution). A substitution is accepted only if NewCost > θ1 * OriginalCost, preventing vocabulary bloat from marginal gains.
   • An additional efficiency check ensures that the average number of nucleotides encoded per token improves after substitution.
4. Termination: The process repeats until a maximum number of iterations is reached or no further beneficial candidates exist.

2.3 Multi-Pattern Matching and Replacement

Once the dictionary is constructed, the Aho-Corasick algorithm is employed for efficient pattern matching:

• Automaton Construction: A trie is built from all dictionary patterns, augmented with failure links and output links to handle overlapping matches in linear time.
• Greedy Replacement: The input sequence is scanned. At each position, if multiple patterns match, the algorithm selects the longest match; if lengths are equal, it selects the most frequent pattern. This "greedy" approach ensures maximal compression per step.
• The sequence is transformed into a stream of tokens and unmatched literal bases.

2.4 Entropy Coding

The tokenized sequence is further compressed using context-modelled arithmetic coding:

• Context Modeling: An order-1 context model estimates the probability of a token based on its immediate predecessor.
• Smoothing: Laplace smoothing is applied to handle unseen transitions, preventing zero probabilities.
• Encoding: The sequence is encoded into a bitstream. The final output file contains the compressed bitstream, the hierarchical dictionary (as an integer grammar), and metadata for lossless reconstruction.

2.5 Compressed-Domain Analysis

HiDAC supports direct analysis on the tokenized stream without full decompression:

• Token Filtering: If a query pattern's first character does not exist within a token's expansion, that token is skipped entirely.
• Deferred Expansion: Only tokens potentially containing the query are expanded.
• Automaton Matching: A Knuth-Morris-Pratt (KMP) automaton is used to match the query against the expanded bases of the remaining tokens. This allows frequency counting and pattern search to operate on a significantly smaller dataset.

3. Key Contributions

• Hierarchical Dictionary Construction: Unlike standard dictionary methods that process sequences sequentially, HiDAC builds a nested hierarchy where tokens can represent other tokens, capturing complex structural regularities.
• Cost-Guided Selection: The introduction of a cost function (NewCost vs. OriginalCost) ensures that dictionary expansion is strictly controlled to maximize compression gain and maintain token frequency balance.
• Compressed-Domain Usability: The framework enables analytical operations (pattern search, frequency counting) directly on the tokenized representation, eliminating the need for full decompression.
• Reusability: The dictionary is constructed once from a reference and can be applied to other sequences within the same genomic class, reducing preprocessing overhead for large datasets.

4. Experimental Results

The method was evaluated on five diverse datasets, including Escherichia coli, Mycobacterium tuberculosis, human genomes, and a benchmark set of 15 species.

• Compression Performance:
  • HiDAC achieved file size reductions (Space Saved) of approximately 76% for bacterial datasets (DS 1 and DS 2) and 76.38% for human chromosomes (DS 3).
  • It consistently outperformed general-purpose compressors (gzip, bzip2, zstd, lzma, brotli) and specialized genomic compressors like NAF.
  • In comparisons with HMG (a state-of-the-art MDL-based compressor), HiDAC demonstrated more consistent performance across diverse genome types, with a tighter interquartile range in compression ratios.
• Dictionary Generalization:
  • A unified dictionary constructed from 90% of human chromosomes successfully compressed the entire genome, capturing both local and global recurring motifs.
  • Analysis of learned tokens revealed that the method reliably identifies biologically significant patterns, such as dinucleotides (e.g., TT, AA) and trinucleotides (e.g., TAA, ATG), across different species.
• Compressed-Domain Analysis Speed:
  • Substring frequency analysis performed directly on the tokenized representation was 2.6–2.8× faster than on the original sequence.
  • This speedup was consistent across query lengths (13–466 bases) and across genomes of varying sizes and repeat structures (e.g., Drosophila miranda and Human Chromosome 4).

5. Significance and Claims

The authors claim that HiDAC addresses the dual challenge of storage efficiency and analytical accessibility in genomic data.

• Efficiency: The method provides superior or competitive compression ratios compared to existing state-of-the-art tools, effectively reducing storage and transmission costs.
• Analytical Capability: By enabling operations on semi-compressed data, HiDAC reduces the computational overhead associated with genomic analysis. The paper demonstrates that the tokenized representation is not merely a storage format but a functional structure for faster downstream tasks.
• Robustness: The framework shows strong generalization capabilities, performing well across diverse species and genome sizes without requiring a specific reference genome for every new dataset (once a representative dictionary is established).

The paper concludes that while further refinements in cost functions and context modeling are possible, the current framework effectively balances compression performance with the ability to perform computation directly on compressed genomic data.