ESS-Color Algorithm Compresses Biological Sequence Graphs to Cut Storage Overhead

Computer scientists have developed an algorithmic framework named ESS-color to compress colored de Bruijn graphs directly to disk, addressing a growing data storage bottleneck in biological sequence analysis. In modern genomics, large collections of biological sequences are routinely converted into collections of fixed-length substrings of length k, known as k-mers. When working with collections of sequencing experiments or assembled genomes, researchers frequently represent the aggregated data as a colored de Bruijn graph. In this graph structure, all unique k-mers from across datasets form a unified set, and each k-mer is linked to a specific color class that records the exact datasets in which that sequence appears. This structure serves as the computational foundation for vital genomic tasks, such as tracking antimicrobial resistance evolution, estimating RNA transcript expression levels, inferring evolutionary phylogenies, and searching large sequence databases. However, as sequence databases expand into petabyte scales, transferring and storing these graphs on local infrastructure or commercial cloud services introduces severe resource constraints, frequently limiting the scope of analyses smaller laboratories can execute.

While software engineers have previously introduced numerous indexing data structures capable of querying colored de Bruijn graphs quickly, those indexing tools must maintain substantial space overhead to support fast query operations. In contrast, pure disk compression algorithms do not require query capabilities on the compressed files and can prioritize minimizing raw storage space, yet they have received very little research attention. Prior approaches to the storage problem have suffered from severe structural limitations. The simplest alternative involves compressing each color dataset entirely independently using single-set tools, but because genomic datasets share extensive sequences across related strains or biological samples, independent compression fails to capitalize on widespread sequence redundancy. Other specialized compression options have faced significant operational trade-offs, such as restricting calculations to only three specific k-mer sizes or functioning primarily as modified indexing mechanisms that require generic secondary compression utilities to achieve practical disk reduction.

To overcome these challenges, the investigators built ESS-color by synthesizing concepts from spectrum-preserving string sets and k-mer compression formats with customized color-encoding strategies. When provided with input sequences in KFF format or FASTA collections processed via the KMC counting tool, the algorithm first unites all distinct k-mers across the samples into a single set. This unified sequence collection is compressed using an established tool known as ESS-basic to yield a representation called a union ESS. When decompressed, this union ESS deterministically generates a spectrum-preserving string set, denoted as S, which consists of compact sequences called simplitigs. Within each simplitig, every included k-mer appears exactly once. Furthermore, the deterministic ordering of k-mers within the simplitigs establishes a consistent sequential structure for organizing the corresponding color information across the entire database.

The central algorithmic mechanism of ESS-color lies in how it constructs and compresses the color matrix that accompanies the ordered k-mers. A naive representation of this color matrix requires one binary bit per dataset for every single k-mer, which becomes highly inefficient because the number of distinct color patterns observed in practical experiments is vastly smaller than the theoretical maximum of two raised to the power of the dataset count. To exploit this property, ESS-color scans the color matrix to identify all unique color combinations and their frequencies, subsequently applying Huffman coding to assign variable-length global identifiers where frequent color classes receive shorter bit representations. The global dictionary is then compactly archived to disk through three coordinated components: a Delta file listing color vectors encoded via Hamming distances relative to preceding vectors, a boundary bitvector indicating where each class begins, and a plain text file recording class frequencies.

Beyond global class identification, the compression algorithm analyzes the simplitigs individually to exploit local continuity along sequence paths. Because adjacent k-mers within a simplitig share biological sequence overlaps, they frequently belong to identical or very similar sets of datasets. ESS-color scans each simplitig from left to right to build an encoding bitvector, choosing among four distinct operational representations. When a k-mer possesses the exact same color class as both its predecessor and successor, the algorithm skips it entirely without appending data. For k-mers ending a consecutive sequence of identical color classes, the algorithm writes a run length broken into a quotient and remainder relative to a chosen parameter, with the researchers finding that a default divisor of 16 delivered optimal results across testing.

When color transitions occur between neighboring k-mers within a simplitig, the tool determines whether the Hamming distance between the two consecutive color vectors is sufficiently small, specifically either one or two differing colors. If this condition is met, ESS-color encodes only the small class difference by listing the specific indices where the color assignments diverge, circumventing the need to record a full color identifier. For remaining instances where class transitions cannot be compactly expressed as small shifts or runs, the algorithm records the explicit identifier of the class. Because storing these full global identifiers can consume substantial space when classes are evenly distributed, ESS-color can optionally generate a local class table for any simplitig containing multiple recurrences of a small subset of classes, mapping compact local identifiers to the broader global identifiers.

Determining whether to deploy a local class table and what maximum Hamming difference threshold to permit involves intricate mathematical trade-offs that cannot easily be predicted prior to compression. For example, reserving metadata space to encode differences can introduce unnecessary overhead if an entire simplitig contains only one color class. To resolve this dilemma, ESS-color dynamically tests all six possible configurations of its parameters—evaluating combinations of whether a local table is active and whether the maximum class difference threshold is zero, one, or two—for every individual simplitig. It measures the resulting bit sizes after applying RRR compression and retains only the parameter configuration that consumes the absolute least disk space, recording the winning choice using three metadata bits per simplitig.

The researchers evaluated ESS-color across five diverse genomic collections designed to reflect varied biological inputs, including assembled genomes, short RNA sequencing reads, and metagenomic sequencing experiments across bacteria, fungi, and humans. Testing was carried out on an enterprise server utilizing an Intel Xeon E5-2683 v4 processor with 64 cores and 512 gigabytes of system memory, executing operations with eight processing threads in unrestricted memory mode. Across all evaluated datasets, ESS-color achieved superior compression density compared to every tested alternative tool. Competing software packages were unable to consistently come within 44 percent of the space efficiency achieved by ESS-color, with competing tools demanding at least 27 percent more space on a complex human gut microbiome dataset.

When assessing absolute compression performance, ESS-color reduced file sizes by more than 26-fold on assembled genome collections, while achieving reductions between 1.4-fold and 8.7-fold on raw sequencing read datasets relative to uncompressed representations. When compared against the baseline approach of compressing each experimental color independently via ESS-basic, ESS-color demonstrated dramatic space savings, requiring between 1.2-fold and 6.9-fold less storage. The degree of improvement was strongly correlated with biological sharing across samples. In collections where a high percentage of k-mers occurred in only a single sample, such as a 20-strain fungal assembly dataset where 93 percent of k-mers were unique to one genome, multi-color compression advantages were minimal. Conversely, on a 100-strain Escherichia coli dataset where only 30 percent of k-mers were restricted to a single color, ESS-color achieved substantial compression ratios due to widespread cross-strain sequence sharing.

Detailed component analyses showed that the majority of the final archive footprint in ESS-color is occupied by the union ESS sequence representation itself, with the remainder primarily consumed by the simplitig encoding bitvectors. Furthermore, scaling experiments evaluating 10, 100, 500, and 1,000 E. coli strains demonstrated that while sequence storage requirements remained stable between 2.2 and 2.3 bits per k-mer, color information expanded from 13 percent to 83 percent of the archive as the number of distinct color combinations multiplied. The authors noted clear operational boundaries, observing that while ESS-color achieves unmatched space reductions, its compression execution times and memory requirements are higher than indexing-oriented tools like GGCAT. Future optimizations will aim to parallelize color matrix creation and explore color-aware simplitig path selection to further accelerate compression workflows.

Subject of Research: Disk compression algorithm for colored de Bruijn graphs in biological sequence analysis

Article Title: Compression algorithm for colored de Bruijn graphs

Article References: Rahman, A., Dufresne, Y., & Medvedev, P. (2024). Compression algorithm for colored de Bruijn graphs. Algorithms for Molecular Biology, 19(1), Article 20. https://doi.org/10.1186/s13015-024-00254-6

Image Credits: AI Generated

DOI: 10.1186/s13015-024-00254-6

Keywords: colored de Bruijn graphs, genomic data compression, ESS-color, bioinformatics, k-mers, sequence analysis, spectrum-preserving string sets, simplitigs, computational biology, data structures, microbiome sequencing, RNA sequencing, disk storage, GGCAT, Huffman coding, lossless compression, computational efficiency