Optimal compressed representation of high throughput sequence data via light assembly

Antonio A. Ginart, Joseph Hui, Kaiyuan Zhu, Ibrahim Numanagić, Thomas A. Courtade, S. Cenk Şahinalp, David TseNature Communications 2018 · DOI

Abstract

The most effective genomic data compression methods either assemble reads into contigs, or replace them with their alignment positions on a reference genome. Such methods require significant computational resources, but faster alternatives that avoid using explicit or de novo-constructed references fail to match their performance. Here, we introduce a new reference-free compressed representation for genomic data based on light de novo assembly of reads, where each read is represented as a node in a (compact) trie. We show how to efficiently build such tries to compactly represent reads and demonstrate that among all methods using this representation (including all de novo assembly based methods), our method achieves the shortest possible output. We also provide an lower bound on the compression rate achievable on uniformly sampled genomic read data, which is approximated by our method well. Our method significantly improves the compression performance of alternatives without compromising speed.

Introduction

High-throughput sequencing (HTS) generates staggering amounts of genomic data, creating a massive storage and transmission bottleneck. Existing compression methods generally fall into two camps: reference-based methods, which align reads to a known genome, and reference-free methods, which use techniques like read reordering or implicit assembly. While reference-based methods are highly efficient, they are computationally expensive and require a pre-existing reference. Conversely, reference-free approaches are faster but typically fail to reach high compression ratios.

This paper introduces Assembltrie, a reference-free genomic data compression method that bridges this gap. By utilizing "light de novo assembly" to represent DNA reads as nodes in a compact, bottom-up trie, Assembltrie achieves combinatorial optimality for this representation. The authors demonstrate that this approach significantly outperforms existing tools—improving compression ratios by 10–50%—while remaining competitive in speed and approaching theoretical information-theoretic limits.

Methodology: Light Assembly and Cycle-Rooted Tries

The core innovation of Assembltrie is a data structure called a cycle-rooted trie. Instead of fully assembling reads into long "contigs," which is computationally intensive, Assembltrie performs a "light" assembly. It represents each read as a node in a forest of tries.

Unlike standard tries organized top-down, Assembltrie uses a bottom-up approach. Each read (node $v$) has a link only to its "parent" (node $u$), where the parent is the read that shares the maximum possible suffix-prefix overlap with it. The algorithm iteratively builds this forest by greedily finding the best parent for every new read to maximize overlap. The authors mathematically prove that this greedy approach is combinatorially optimal, meaning it produces the smallest possible representation (fewest symbols and pointers) for this specific trie-based structure.

The construction process involves searching for potential parents and children using hash tables, followed by greedy strand correction to account for DNA's double-stranded nature.

Since DNA is double-stranded, the tool includes a heuristic to check both the read and its reverse complement to find the best overlap. This "forest" representation allows for mathematical proofs of optimality while keeping computation manageable.

Experimental Results

The authors evaluated Assembltrie using a diverse range of datasets, including microbial (P. aeruginosa, S. cerevisiae), human (gut microbiome, full genome), and plant (T. cacao) data. They also tested simulated E. coli datasets with varying read lengths, coverage, and error rates to compare against theoretical entropy bounds.

Assembltrie improved compression ratios by 10–50% compared to leading reference-free tools like Orcom and Mince. Notably, on simulated E. coli data, Assembltrie was the only tool to produce results close to the theoretical entropy $H(R)$. Competitors like Orcom were found to be 2.1x to 2.6x less efficient on the same data.

Assembltrie (blue) significantly outperforms Orcom (magenta) and closely tracks the theoretical entropy approximation (green dashed line) as sequencing error rates increase.

Furthermore, while compression speed remains competitive with Orcom, Assembltrie’s decompression is significantly faster—up to 3.5x faster in some cases. The tool performs particularly well on low-coverage data, where the efficiency gap between Assembltrie and its competitors is most pronounced.

Discussion and Future Work

Despite its performance, Assembltrie has a high memory footprint, as it must maintain all processed reads and hash tables in RAM ($\Omega(NL)$ memory). Compression performance also degrades as sequencing error rates increase because the algorithm relies on exact $K$-mer matches for initial overlap searches.

Future directions include improving strand correction heuristics or limiting the "branching factor" in tries to reduce memory usage at the cost of some compression efficiency. Overall, Assembltrie demonstrates that reference-level compression can be achieved without a reference genome by efficiently exploiting read overlaps and approaching the physical limits of information density.

Summary updated

Abstract

The most effective genomic data compression methods either assemble reads into contigs, or replace them with their alignment positions on a reference genome. Such methods require significant computational resources, but faster alternatives that avoid using explicit or de novo-constructed references fail to match their performance. Here, we introduce a new reference-free compressed representation for genomic data based on light de novo assembly of reads, where each read is represented as a node in a (compact) trie. We show how to efficiently build such tries to compactly represent reads and demonstrate that among all methods using this representation (including all de novo assembly based methods), our method achieves the shortest possible output. We also provide an lower bound on the compression rate achievable on uniformly sampled genomic read data, which is approximated by our method well. Our method significantly improves the compression performance of alternatives without compromising speed.
BibTeX
@inproceedings{ginart2018optimal,
  author = {Antonio A. Ginart and Joseph Hui and Kaiyuan Zhu and Ibrahim Numanagić and Thomas A. Courtade and S. Cenk Şahinalp and David Tse},
  title = {{Optimal compressed representation of high throughput sequence data via light assembly}},
  booktitle = {Nature Communications},
  year = {2018},
  doi = {10.1038/s41467-017-02480-6},
}
Figure