Single-Read Reconstruction for DNA Data Storage Using Transformers

In recent years, the amount of digital data created and stored by humanity is rapidly growing. Current data storage technologies are limited in their ability to support the growing demand, and thus the need for alternative storage media is rising. The durability and high information density of DNA make it an appealing medium for future data storage systems (Church, Gao, and Kosuri 2012; Goldman et al. 2013). A single gram of DNA can potentially store 100s of petabytes and expected to last and remain readable for centuries. In comparison, standard storage media such as optical discs, hard drives and magnetic tapes, only enable data lifetime of a few years with an information density which is lower by orders of magnitude (Chandak et al. 2020; Heckel et al. 2019).

DNA based storage systems are comprised of three main components. First, the input information is encoded into a set of DNA sequences (i.e. sequences over the four letter alphabet $\{A,C,G,T\}$). Next, the sequences are “transmitted” over a DNA based channel including synthesis, storage, and sequencing. Finally, the sequencing output is reconstructed and decoded. Figure 1 presents an overall view of DNA based storage. The encoding step involves adjustments to technological and biological constrains, such as adding error-correction codes to the sequences. Standard synthesis technologies generate thousands to millions of copies for every 100-200 base sequence (Heckel et al. 2019). Moreover, all the synthesized DNA molecules are stored together in a single container as an unordered set. These properties, among others, impose different limitations on the encoding step including sequence length limitation, inedxing, controlled GC content, and run-length constrains. The output of the sequencing process is a set of noisy sequences, usually referred to as reads, representing the synthetic DNA molecules. Retrieving the information from this read set involves sequence reconstruction, ordering, and decoding.

Despite the promising potential, many challenges prevent DNA based storage from becoming a viable solution, even for archival purposes. The synthesis and sequencing processes are costly and result in erroneous reads that include insertion, substitution and deletion errors (Heckel et al. 2019). Furthermore, as the number of sequenced molecules is considerably lower than the number of available molecules, only a small sample is sequenced, thus some sequences are read multiple times while others might not be read at all. Some recent work on DNA based storage systems presented end-to-end solutions including molecular implementations (Organick et al. 2018; Erlich and Zielinski 2017; Organick et al. 2020). Others tackled certain components: error correction schemes (Nguyen et al. 2021; Lenz et al. 2020) or read clustering and sequence reconstruction algorithms (Shinkar et al. 2019; Sabary et al. 2020; Chandak et al. 2019). All the algorithms suggested for the reconstruction step, which is the task of predicting the original sequences from the noisy read set, use multiple copies for reconstruction. Obtaining enough sequences with sufficient read coverage requires excess reading which entails higher costs. For more information regarding DNA data storage, common challenges, and recent work, we refer the reader to (Ceze, Nivala, and Strauss 2019).

During the past few years, Transformers (Vaswani et al. 2017) have become the most dominant architecture for many sequence-to-sequence tasks as it showed to be superior to methods that have been used before (mainly CNNs and RNNs). Although initially developed for language modelling tasks, Transformers are now widely used in other areas including audio processing (Dong, Xu, and Xu 2018) and image processing (Parmar et al. 2018). More recently Transformers also achieved significant impact on one of the cornerstones of computational biology, the problem of protein folding prediction (Jumper et al. 2021). A Transformer is a neural network with permutation equivalence composed of attention mechanisms and residual blocks. In the Transformer’s architecture, position embeddings are generally added into the embedding layer with token embedding, since Transformers cannot distinguish the input’s position.

In this work, we focus on reconstructing the original DNA sequences from only a single noisy read of each sequence. We address the problem as a sequence-to-sequence task and use an ensemble of three encoder-decoder Transformer models for the reconstruction. Our model relies solely on self-supervised learning using noise injection on reads from the decoded file that are presumed to be error free with high probability (Lewis et al. 2019). We evaluate our method on files from three different data domains, to which we simulate reads with realistic error rates. With average error rate reductions of $63\%$ (edit error), and $97\%$ (hamming error) using only a single read, our model outperforms state-of-the-art algorithms using 2-3 copies. Furthermore, the advantage of our method becomes more significant when tested over files with higher noise levels.

Our contributions: This work is the first to use a single-read for sequence reconstruction in DNA based storage. We demonstrate that our approach outperforms state-of-the-art algorithms that use two and three reads for reconstruction. Additionally, this work is the first attempt to incorporate deep learning models for sequence reconstruction in DNA based storage systems. Furthermore, our approach requires no training on external data, making it adjustable for the storage of different file types. Lastly, our approach represent a paradigm shift in sequence reconstruction as we focus on correcting the errors by learning the representation of the sequences rather than learning the error patterns.

The DNA channel takes a binary input message $\mathbf{m}$ and encodes it into a sequence of DNA codewords which is broken into $n$ sub-sequences of length $l$ each, $\mathbf{x_{1}},\mathbf{x_{2}},...\mathbf{x_{n}}$ where $\mathbf{x_{i}}\in\Sigma^{l}$ and $\Sigma=\{A,C,G,T\}$. For each $l$-bases sequence $\mathbf{x}$, $t>0$ independent copies are transmitted through a Deletion-Insertion-Substitution (DIS) channel yielding $\mathbf{y_{1}},\mathbf{y_{2}},...\mathbf{y_{t}}$. These, in turn are being decoded back to receive the binary output message $\hat{\mathbf{m}}$.

A general DNA reconstruction algorithm is a mapping $R:\left(\Sigma^{*}\right)^{t}\rightarrow\Sigma^{*}$ which receives $\mathbf{y_{1}},\mathbf{y_{2}},...\mathbf{y_{t}}$ and produces $\hat{\mathbf{x}}$. The goal in a DNA reconstruction problem is to minimize either the edit distance or the Hamming distance between the original sequence $\mathbf{x}$ and the inferred sequence $\hat{\mathbf{x}}$, $d_{e}(\hat{\mathbf{x}},\mathbf{x})$ and $d_{H}(\hat{\mathbf{x}},\mathbf{x})$ respectively (See definitions below).

In this work we tackle the case for which $t=1$. For that purpose we generalize the problem definition by taking into account the entire message transmitted through the DNA channel. Formally, a reconstruction algorithm will be a mapping $R:\left(\Sigma^{*}\right)^{n}\rightarrow\left(\Sigma^{l}\right)^{n}$. That is, given a single noisy copy $\mathbf{y}$ for every sequence $\mathbf{x}$ we infer $\hat{\mathbf{x}}$. Moreover, the algorithm is aware of the overall encoding process of $\mathbf{m}$ to $\left(\mathbf{x}\right)^{n}$ and can also enforce constraints on this encoding. This is sometimes referred to as coded reconstruction. The purpose remains to minimize either $d_{e}(\hat{\mathbf{x}},\mathbf{x})$ or $d_{H}(\hat{\mathbf{x}},\mathbf{x})$.

In this section we describe our model. Essentially, it is a sequence-to-sequence model that performs error correction by mapping a corrupted sequence to the original one.

In this section we describe the end-to-end pipeline of our proposed Single-Read Reconstruction (SRR) scheme. The input to the pipeline is a given data file which undergoes encoding to DNA. After retrieval of the erroneous data sequences, we inject synthetic noise to a subset of “quality” sequences, thus creating a training dataset for self-supervised learning which is tailor-made for the file. We use 3 trained models to predict and reconstruct the original data file. As presented in Figure 3, our process is described in 3 main stages: Stage 1: Encoding to DNA and retrieval of noisy reads. Stage 2: Self-supervised training by synthetic noise injection. Stage 3: Data reconstruction using model prediction.

To evaluate the performance of our reconstruction method, we performed three experiments with different types of data files. The first is a 948KB text file consisting of Darwin’s “On the Origin of Species” book (Darwin 1909). The second is a 3076KB text file containing the original code-script of the Apollo 11¹¹1Downloaded from https://github.com/chrislgarry/Apollo-11 on September 1, 2021. This serves as a more complex case as the semantic structure of a code-script file is harder to identify than that of a text file from the English language. The third data file is a 4688KB color $1600\times 1000$ image file of “Torres del paine”²²2Image downloaded from https://www.travelandleisure.com on September 1, 2021. The text and code-script files are UTF-8 encoded, and the image is encoded in the standard 8-bit color map bmp encoding. Namely, each pixel is represented by 3-bytes, one byte per color channel. We read the image file in $5\times 5$ pixel squares.

In all experiments, we assigned a codeword of 4 DNA bases to every byte of information, and encoded the data to DNA sequences of length $l=100$, each consisting of 25 encoded bytes. The encoding resulted in 38,183, 125,977, 192,000 DNA sequences representing the Darwin, Apollo, and Torres files respectively. We simulated 1,2, and 3 noisy reads for each sequence using a simulator from (Chaykin et al. 2021) that introduces deletion, insertion and substitution errors according to the DIS channel.

We reconstructed the original sequence from a single noisy read using our Single-Read Reconstruction Algorithm (SRR) and compared the result to the reconstruction results of running the Hybrid Reconstruction Algorithm (HRA) from Sabary et al. and their variation of the Divider Bitwise ajority Alignment Algorithm (DBMA) by Gopalan et al. using one, two, and three reads. The implementations of HRA and DBMA are taken from (Chaykin et al. 2021; Sabary et al. 2020). Since both HRA and DBMA failed to run on the complete data files, the comparison is presented on a sample of 5,000 sequences from each file. For all algorithms, we evaluated success rates, edit error rates, Hamming error rates, and edit error distributions. For the noise injection step of the SRR algorithm we used error schemes representing standard DNA based storage conditions. Details of the experimental setting are available in the Technical Appendix.

In this paper, we proposed a novel approach for utilizing deep learning Transformers to perform single-read reconstruction for DNA based storage. We modeled the error correction process as a sequence-to-sequence task and designed an encoder-decoder model to correct deletion, insertion, and substitution errors. Our approach is based on self-supervised training using only the decoded file with injected noise to produce training samples. We demonstrated our approach by encoding three file types and performing single-read reconstruction on simulated noisy data with different noise levels. Our single-read reconstruction algorithm achieves better performance than the current state-of-the-art reconstruction algorithms operating on two reads and in some measures also three reads.

This is the first example of single-read reconstruction for DNA based storage. Traditional algorithms treat the reconstruction problem of each sequence independently and are thus limited when operating on single-read sequences. Our approach is the first, to our knowledge, to offer a reconstruction algorithm that is both holistic (i.e. reconstructs all sequences simultaneously) and context-aware. Our suggested approach is thus able to successfully reconstruct single-read sequences.

The common approach for using machine learning models for sequence reconstruction relies heavily on the availability of high-quality labeled data. This is used to try and learn the error pattern to allow the prediction of the original sequences. Dataset generation of synthetic DNA libraries requires extensive investments and labor and thus these datasets are scarce. Moreover, DNA synthesis and sequencing technologies, as well as the subsequent molecular biology procedures, produce diverse error patterns that are affected from various exogenous factors making the learning task implausible. On the contrary, our model relies solely on self-supervised learning using noise injection on samples that are presumed to be error free. Our model does not require any external samples for training, making it applicable for use on diverse data files.

While we use a certain error distribution for noise injection, it does not need to represent the same error distribution as the decoded data file. This is demonstrated in the noise level experiment where our model outperformed the two and three reads reconstruction algorithms on data with noise levels much higher than those used for noise injection. We are able to achieve these results because our reconstruction model does not learn the error pattern in the data but rather it learns the underlying structure of the data file in hand. Learning the underlying structure of the decoded file requires the identification of error-free reads that are assumed to be a representing sample of the original file. We use our knowledge of the error model (i.e. errors are the result of some DIS channel) and a limited amount of redundant information added to the file in the encoding step (i.e. the set of valid codewords in the file and the designed length $l$) to generate a set of reads that are error-free with high probability.

The possibility of obtaining a high quality set of probably-correct reads that adequately represent the input file is affected by three factors: file size, noise level, and the number of valid codewords in the file. Larger files allow for a larger and more diverse training set which is crucial for model training. Alternatively, high noise levels and larger sets of valid codewords result in a limited training set. An extreme case of the latter is demonstrated in the image encoding experiment as the set of valid codewords contains all 256 options. This makes the distinction between correct and erroneous reads impossible and results in lower success rate and higher error rates compared to the text file experiments. Exploring ways to improve the construction of this read set is a major focus for future studies.

While most DNA based storage systems aim for an average read coverage of 10 reads or more, some sequences will inevitably be represented by only a single read. Salvaging those poorly represented sequences to extract more information will allow for the reduction of the overall coverage required for a successful decoding and the use of error correction schemes with less redundancy. Moreover, single-read reconstruction can be combined with standard multi-read reconstruction algorithms. For instance, after reconstructing each read using a single-read reconstruction model, reads can be clustered and used to reconstruct the sequence with higher confidence.

In the past decade, the use of deep learning (DL) models has revolutionized many fields, including Computer Vision, Natural Language Processing, Cyber security, and others. Often, the introduction of DL models required rethinking central dogmas and traditional methodologies. DNA data storage is a fast growing field which gained a lot of attention in the past few years. However, despite its promise, the field seems to be limited in scale. This work represents a first step towards the incorporation of DL models in the DNA encoding-decoding pipelines. Similar to other domains, this may require a paradigm shift in the field. Replacing the traditional reconstruction algorithms and error correction schemes, that are focused on understanding the error patterns on the single sequence level, by a holistic, context-aware approach that tries to reconstruct the entire data file by modeling its underlying structure is a step in that direction.