Improved read/write cost tradeoff in DNA-based data storage using LDPC codes

Shubham Chandak, Kedar Tatwawadi, Billy T. Lau, Jay Mardia, Matthew Kubit, Joachim Neu, Peter B. Griffin, Mary Wootters, Tsachy Weissman, Hanlee P. JibioRxiv 2019 · DOI

TL;DR

This paper tackles the challenge of efficiently storing and retrieving data using DNA, focusing on the trade-off between the cost of writing data to DNA and the cost of reading it back. They propose a novel scheme that uses a single, large LDPC code for both error and erasure correction, significantly outperforming previous methods by achieving 30-40% lower reading costs on experimental data.

What Problem Does This Paper Address?

The ever-increasing volume of digital data necessitates exploring new, high-density storage solutions. DNA offers immense storage potential (petabytes per gram) and incredible durability, making it an attractive archival medium. However, the process of encoding data into DNA sequences, synthesizing them, and then sequencing them back is inherently error-prone. Existing DNA storage approaches often use separate coding schemes for different types of errors (like substitutions, insertions, deletions, and missing sequences), which can be inefficient. Furthermore, many methods rely on short codes and read consensus, which are suboptimal from a coding theory perspective. This paper aims to bridge this gap by developing a more efficient and practical DNA storage system that optimizes the read/write cost trade-off by employing a unified coding strategy.

Methods

The core of the proposed method is a departure from the traditional "inner/outer code separation" strategy. Instead, the authors advocate for a single large block-length LDPC (Low-Density Parity-Check) code. This approach treats the entire DNA storage channel as a single entity, allowing the LDPC code to handle both substitution errors (common in sequencing) and erasures (missing sequences) simultaneously.

Key components of their method include:

  • LDPC Encoding: Binary data is first encoded using a large block-length regular LDPC code. These codes are known for their near-optimal performance in various channels, especially at high rates.
  • Binary to DNA Mapping: The encoded binary blocks are then segmented and mapped to the {A, C, G, T} DNA alphabet. They use a standard mapping and avoid restrictive homopolymer constraints, instead relying on prior data compression and encryption to improve synthesis quality without increasing writing cost.
  • Synchronization Marker: A short, fixed sequence ("AGT") is added to the center of each DNA sequence. This marker is crucial for recovering partial sequences in cases of insertions or deletions, which can disrupt the expected length of a read.
  • Addressing Index: Each DNA sequence is equipped with an error-protected addressing index (using BCH codes) to maintain the order of the encoded segments, which is lost during synthesis and sequencing.
  • Decoding Strategy: The decoding process involves first decoding the BCH-protected index. For reads with index decoding failures, they employ a heuristic to recover from single insertion/deletion errors. Then, multiple sequence alignment (MSA) is used to cluster reads by their index. The LDPC decoding itself is performed using log-likelihood ratios derived from the counts of bases at each position, rather than relying solely on a consensus sequence.

Datasets

The authors performed experiments using various file types, including:

  • Random files
  • An image file ("The Horse in Motion")
  • Text files (UN declaration of human rights, Darwin's Origin of Species, Feynman's speech "There's Plenty of Room at the Bottom")

These files were randomized through compression and encryption to avoid long repeats/homopolymers. The experimental data was obtained using array synthesis and Illumina sequencing.

Key Insights and Ideas

  • Unified Coding for Errors and Erasures: The most significant insight is that a single, large LDPC code can effectively handle both substitution errors and erasures, simplifying the system and improving efficiency compared to separate inner/outer code approaches.
  • Large Block Codes are Key: Theoretical analysis and simulations strongly suggest that large block codes, like LDPC, offer a superior read/write cost trade-off compared to strategies relying on short block codes.
  • Synchronization Markers are Crucial for Indels: The introduction of synchronization markers is a practical necessity for dealing with insertion and deletion errors, enabling partial recovery of information when sequence lengths are inconsistent.
  • Log-Likelihood Ratios for LDPC Decoding: Utilizing the counts of bases at each position to compute log-likelihood ratios for LDPC decoding is more robust than relying solely on consensus sequences, especially in the presence of significant errors.
  • Coverage Variance Matters: The experiments highlight that coverage variance (how evenly sequences are represented) significantly impacts decoding performance, particularly for codes with lower redundancy.

Key Results

  • The proposed scheme achieves 30-40% lower reading costs compared to state-of-the-art techniques on experimental data.
  • In simulations, the large block code strategy was shown to be closer to the theoretical bound and outperformed the separation strategy, offering up to 2x lower reading costs at low writing costs.
  • The synchronization marker heuristic was found to reduce reading costs by around 5% without significantly impacting writing costs.
  • The system demonstrates robustness, with simulations showing successful decoding even at 6% error rates (substitutions, deletions, insertions at 2% each) with appropriate LDPC redundancy.

Limitations and Future Work

  • Theoretical Model Simplifications: The theoretical analysis made simplifying assumptions, such as ignoring insertions and deletions and assuming ideal Poisson random sampling, which do not fully capture real-world synthesis and sequencing biases.
  • Experimental Parameter Conclusiveness: While experiments were conducted to assess the impact of parameters like the BCH code, the results were not entirely conclusive due to variations in coverage variance and error rates across experiments.
  • Future Work Suggestions:
    • Utilizing large block codes specifically optimized for the DNA storage channel.
  • Exploring "marker codes" for more systematic handling of insertions and deletions.
  • Extending the framework to other sequencing platforms like nanopore sequencing, which have higher insertion/deletion error rates.
  • Incorporating techniques to reduce the inefficiency of index error correction.
  • Efficient hardware implementation of LDPC encoding and decoding for scalability.

Summary updated

Abstract

Abstract With the amount of data being stored increasing rapidly, there is significant interest in exploring alternative storage technologies. In this context, DNA-based storage systems can offer significantly higher storage densities (petabytes/gram) and durability (thousands of years) than current technologies. Specifically, DNA has been found to be stable over extended periods of time which has been demonstrated in the analysis of organisms long since extinct. Recent advances in DNA sequencing and synthesis pipelines have made DNA-based storage a promising candidate for the storage technology of the future. Recently, there have been multiple efforts in this direction, focusing on aspects such as error correction for synthesis/sequencing errors and erasure correction for handling missing sequences. The typical approach is to use separate codes for handling errors and erasures, but there is limited understanding of the efficiency of this framework. Furthermore, the existing techniques use short block-length codes and heavily rely on read consensus, both of which are known to be suboptimal in coding theory. In this work, we study the tradeoff between the writing and reading costs involved in DNA-based storage and propose a practical scheme to achieve an improved tradeoff between these quantities. Our scheme breaks with the traditional separation framework and instead uses a single large block-length LDPC code for both erasure and error correction. We also introduce novel techniques to handle insertion and deletion errors introduced by the synthesis process. For a range of writing costs, the proposed scheme achieves 30-40% lower reading costs than state-of-the-art techniques on experimental data obtained using array synthesis and Illumina sequencing. The code, data, and Supplementary Material is available at https://github.com/shubhamchandak94/LDPC_DNA_storage .
BibTeX
@misc{chandak2019improved,
  author = {Shubham Chandak and Kedar Tatwawadi and Billy T. Lau and Jay Mardia and Matthew Kubit and Joachim Neu and Peter B. Griffin and Mary Wootters and Tsachy Weissman and Hanlee P. Ji},
  title = {{Improved read/write cost tradeoff in DNA-based data storage using LDPC codes}},
  year = {2019},
  doi = {10.1101/770032},
  howpublished = {bioRxiv},
}

Loading related content...

Figure