Overcoming High Nanopore Basecaller Error Rates for DNA Storage Via Basecaller-Decoder Integration and Convolutional Codes

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

TL;DR

This paper tackles the challenge of high error rates in nanopore DNA sequencing, a promising technology for DNA data storage. They introduce a novel approach that integrates the basecalling process with error correction decoding, allowing the system to leverage more detailed information from the sequencing signal. This integration leads to a significant reduction in data reading costs while maintaining comparable writing costs.

What Problem Does This Paper Address?

DNA offers an incredibly dense and durable medium for long-term data storage, far surpassing current technologies. Nanopore sequencing, with its portability and high throughput, is a natural fit for reading data from DNA. However, nanopore sequencing is plagued by high error rates, particularly insertions and deletions, in the basecalled reads. Current methods combat this by using consensus from many reads, which is computationally expensive and drives up reading costs. This paper aims to reduce these costs by improving the accuracy of the data retrieval process itself, rather than relying solely on massive redundancy.

Methods

The core innovation is the basecaller-decoder integration. Instead of decoding the final, error-prone basecalled sequence, the authors integrate a convolutional code decoder directly with the deep learning-based basecaller (specifically, the Flappie basecaller). This allows the decoder to access and utilize "soft information" – intermediate probabilities generated by the basecaller's neural network – which are more informative than the final basecalled bases.

The system uses a convolutional code as the inner error correction code. These codes are well-suited for sequential data like DNA sequences and integrate naturally with the Viterbi algorithm, a standard decoding technique. The integration involves creating a combined state that includes the state of the basecaller, the state of the convolutional code, and the position within the codeword. This allows the Viterbi algorithm to find the most likely path through a combined trellis, effectively correcting errors while leveraging the basecaller's insights.

For outer error correction and handling lost sequences, they employ Reed-Solomon codes. Additionally, an 8-bit cyclic redundancy check (CRC) is used to detect errors within sequences before outer code decoding, enabling a form of list decoding for the convolutional code.

Datasets

The experiments were conducted using a synthesized DNA pool containing approximately 11 KB of data. This data was derived from various texts, including the UN declaration of human rights, the Gettysburg Address, the "I Have a Dream" speech, and song lyrics. The input data was compressed and encrypted to ensure it appeared random and to avoid issues with homopolymers during synthesis and sequencing. The synthesized oligos were sequenced using an Oxford Nanopore MinION sequencer (R9.4.1 pore).

Key Insights and Ideas

  • Soft Information is Key: The most significant insight is that by tapping into the intermediate "soft" outputs of the basecaller, rather than just the final basecalled sequence, we can achieve much better error correction. This soft information captures nuances of the raw signal that are lost in the final basecalling step.
  • End-to-End Optimization: Integrating the basecaller and the error correction decoder allows for a more holistic optimization of the data retrieval pipeline. The decoder can exploit the specific error characteristics of the basecaller, leading to better performance than applying a generic decoder to the output.
  • Convolutional Codes as a Natural Fit: The sequential nature of both nanopore sequencing and convolutional codes makes them a synergistic pairing for this integrated approach.
  • Tradeoffs in DNA Storage: The paper highlights the fundamental tradeoff between writing cost (how much DNA is synthesized per bit of data) and reading cost (how much DNA needs to be sequenced per bit of data). Their method significantly improves this tradeoff for nanopore sequencing.

Key Results

The proposed basecaller-decoder integration approach achieved a 3x lower reading cost compared to previous state-of-the-art methods for nanopore DNA storage, while maintaining comparable writing costs. This improvement is significant, especially considering the inherently higher error rates of nanopore sequencing compared to Illumina sequencing. The authors also note that their approach brings the read/write cost tradeoff for nanopore DNA storage closer to that of Illumina-based systems.

Limitations and Future Work

The authors acknowledge that the convolutional code decoding is computationally intensive, with a time and space complexity of O(2<sup>m</sup>L), where 'm' is the code memory and 'L' is the list size. For their implementation, decoding a single read took approximately 270 seconds with significant RAM consumption.

Future work includes:

  • Optimizing convolutional code parameters and fine-tuning basecaller neural network parameters.
  • Improving computational efficiency through approximate decoding techniques.
  • Exploring hybrid approaches that combine their integrated method with consensus-based techniques.
  • Extending the basecaller-decoder integration concept to other error correction codes beyond convolutional codes.
  • Applying this hybrid ML-and-coding approach to other communication and storage problems.

Summary updated

Abstract

ABSTRACT As magnetization and semiconductor based storage technologies approach their limits, bio-molecules, such as DNA, have been identified as promising media for future storage systems, due to their high storage density (petabytes/gram) and long-term durability (thousands of years). Furthermore, nanopore DNA sequencing enables high-throughput sequencing using devices as small as a USB thumb drive and thus is ideally suited for DNA storage applications. Due to the high insertion/deletion error rates associated with basecalled nanopore reads, current approaches rely heavily on consensus among multiple reads and thus incur very high reading costs. We propose a novel approach which overcomes the high error rates in basecalled sequences by integrating a Viterbi error correction decoder with the basecaller, enabling the decoder to exploit the soft information available in the deep learning based basecaller pipeline. Using convolutional codes for error correction, we experimentally observed 3x lower reading costs than the state-of-the-art techniques at comparable writing costs. The code, data and Supplementary Material is available at https://github.com/shubhamchandak94/nanopore_dna_storage .
BibTeX
@misc{chandak2019overcoming,
  author = {Shubham Chandak and Joachim Neu and Kedar Tatwawadi and Jay Mardia and Billy T. Lau and Matthew Kubit and Reyna Hulett and Peter B. Griffin and Mary Wootters and Tsachy Weissman and Hanlee P. Ji},
  title = {{Overcoming High Nanopore Basecaller Error Rates for DNA Storage Via Basecaller-Decoder Integration and Convolutional Codes}},
  year = {2019},
  doi = {10.1101/2019.12.20.871939},
  howpublished = {bioRxiv},
}
Figure