Rotating labeling of entropy coders for synthetic DNA data storage

Today, the digital world relies on increasingly large amounts of data, stored over periods of time ranging from a few years to several centuries. With current storage media reaching its density limit and the exponential growth of digital information, the search for a new storage paradigm has become of utmost importance. One of the most promising candidates up to this date is to store information in the form of DNA molecules, which provide very dense storage (1 $EB/mm^{3}$) that is also stable over long periods if stored under the right conditions [4].

The process of DNA data storage starts by encoding data into a quaternary stream composed by the four DNA symbols or nucleotides (A, C, T, and G). The encoded data is then physically synthesised into DNA strands (oligos) that are then stored into a safe environment. When data has to be read back, the stored molecules are amplified so as to obtain many copies of each original sequence and the content is deciphered using DNA sequencers. This data is then decoded back into the form of the original binary file. However, the biochemical processes involved in the above end-to-end storage process introduce some coding constraints [1] that, if not respected, dramatically increase the probability of an error occurring (insertion, deletion and/or substitution). These constraints comprise avoiding homopolymers (i.e. use of the same symbol more than 3 consecutive times), repetition of patterns and unbalanced GC content.

Algorithms specifically designed for DNA data storage which respect the biochemical constraints generally show better reliability [2]. Although constrained coding helps reducing the apparition of errors, it does not ensure an error free coding. To tackle the problems of errors, an important number of researchers [5, 6, 7] are currently studying the development of accurate error models for synthetic DNA data storage. Furthermore, since the cost of DNA synthesis is relatively high, it is also important to take advantage of optimal compression, which can be achieved before synthesizing the sequence into DNA. To decrease the synthesis cost of image storage into DNA, several works have been using the so-called “transcoding” method which is based on classical compression protocols such as JPEG for reducing the image redundancies, then encoding each byte of the produced bitstream into DNA words. However, it is clear that such a compression schema is sub-optimal as the compression is optimised with respect to a binary code and therefore it is not adapted to the quaternary nature of DNA. To tackle the above issue, among other relevant works, in [8] the authors proposed a specific image coding algorithm, adapted to the needs of DNA data storage, that efficiently encodes images into a quaternary constrained code.

All the JPEG-inspired coding methods described here are based on [8], whose workflow is described in Fig. 1.

The principle of the novel coding solution is to avoid using the same code — set of codewords — consecutively to avoid creating patterns or homopolymers. In the case where a symbol is very frequently found in the source, due to its high probability, the entropy coder will associate a short codeword to it, which in extreme cases can lead to a codeword consisting of one nucleotide. If this symbol is repeated consecutively in the source, it will create a homopolymer. Figure 3 represents this case. If the symbol is a bit less frequent, the entropy coder will associate a codeword of length two or three to this symbol, and when a repetition of this symbol will occur, a short pattern will be created, also violating the defined biochemical constraints. A real example of these phenomenon can be found when encoding images into DNA with a JPEG-inspired algorithm at very high compression rates, like shown in Fig.2.

In order to avoid these homopolymers and repetitions of patterns, we propose to introduce variability in the generated quaternary streams by generating several equally peformant codes and alternating between them during encoding. Thus, since the symbols will not always be associated to the same codewords, we reduce the risk of creating homopolymers when very frequent symbols are heavily repeated in the source.

An entropic code $C$ is mapped to three associated entropic codes $C^{*}_{1}$, $C^{*}_{2}$ and $C^{*}_{3}$, with three mapping functions $M_{1}$, $M_{2}$ and $M_{3}$ described in Algorithms 1 and 2 and defined as: $\forall k\in[1,3],$

The code used to encode the symbols can be changed periodically. When the source is a simple sequence of symbols (i.e. non block-based), one can change the code after having encoded a fixed amount of symbols, for example every six symbols like the solution presented in Fig. 4.

This novel encoding method relies on two important processes that will be further explained in the following sections: the generation of the different codes that can be used to encode the symbols, and the decision of which code to use. Both processes have to respect some prerequisites to make the whole encoding method a viable solution. First, the proposed coding method will improve the robustness of the encoding through tougher consideration of the biochemical constraints, without affecting the compression performance of the original coder. To ensure decodability, this decision has to be deterministic, otherwise, additional data would have to be transmitted to make sure the decoder can decode the data.

Overall, the proposed solution is very well adapted to block-based encoding methods like for example JPEG-inspired algorithms. More specifically in this work, codes are rotated after encoding a block. The order of encoding of the blocks is organized one line of blocks after another. In addition, to avoid error propagation, the code decision process is reinitialised after the encoding of a full line of blocks as shown in Fig. 7.

The codes construction process is described in Algorithms 1 and 2. The general idea is based on using an already existing codec and the associated quaternary code. From this pre-defined code, we will build three associated codes by mapping all the nucleotides in the original codewords to new ones according to a mapping rule as described in Algorithm 2. The results of the construction algorithm is a list of four codes that can be used in the novel solution. As proven by Proposition 1, the performance of the resulting coding solution is not affected by the introduction of the new coding method in comparison to the original coder.

For the proposed coding solution, it is possible to choose between four codes to encode a fragment of the source. We propose two possible decision processes to determine the order in which the different codes will be used. The first possible case is very simple: we iterate through the four possible codes one by one, and start over. The second possible decision process is a pseudo-random choice, where the encoder and the decoder have a common seed for the pseudo-random generator. Introducing variability in the coding methods will result in a less structured quaternary stream, which is beneficial for our encoding process (less patterns and homopolymers, more balanced data for the GC content).

In the case of block-based coders like the JPEG-inspired codecs, we can change the selected code every time we encode a new block. When the input of the block-based codec is an image, we can reduce the propagation of errors by reinitializing the decision process every time we start to encode a new line of blocks. Fig. 7 represents possible rotation schemes for a block-based image coding method. Every color represents the choice of a different code.

An important question to address about the proposed coder is why would we limit its usage only to variable-length coders. For example, the JPEG-inspired codecs don’t exclusively use a variable-length coder, they also use a fixed-length coder. Ideally, using this method on any type of coder would improve the quality of the quaternary stream. But since a fixed-length coder is source independent, it can be pre-generated in a way to consider the constraints much more thoroughly. In such codes, specific codewords can be eliminated being considered as slightly problematic. If we rotated the letters similarly to variable-length coders, such problematic codewords would sometimes be created, losing all the quality gathered in this pre-generated code.

For clarity, in the following sub-sections, the different methods will be named in the following logic:

JPEGDNA-${entropy coder id}-${source id}[-${rotation id}]

The entropy coder id can be HG if the method uses the Huffman/Goldman coder or SFC4 if it uses the Shannon Fano Constrained coder. The source id can be S when the source is a raw image, or T when it is a already JPEG compressed binary file. For example, JPEGDNA-HG-S is the codec that encodes a raw image where the Huffman/Goldman coder encodes the run/category. The rotation id is optionnal and can be either R or RR. The first describes a regular rotation scheme and the latter a pseudo-random rotation. Both rotations will be described in III-D. For example, the codec JPEG-DNA-HG-S-R is the equivalent of the latter but with a rotative labelling on the Huffman/Goldman coder.

As previously shown in subsection III-C, the introduction of the new coding method does not have any effect on the coding performance in comparison to the original method. However, this property has only been proven specifically for the rotating codes, and not for the codecs in which this new method is integrated. But since we only modify the variable-length coder and not the rest of the compressed stream in those JPEG-inspired coding methods, the compression rate of the general coding algorithm remains the same. The rate-distorsion curves in Fig. 8 illustrate this: the curves for the original algorithms and the modified ones are superimposed. The performance results shown in Fig. 8 have been computed on the first image of the Kodak dataset¹¹1https://r0k.us/graphics/kodak/, kodim01.