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