Properties of Maxentropic DNA Synthesis Codes † Authors: Kees Schouhamer Immink, Jos H. Weber, Kui Cai Published: 2024 ABSTRACT Low-weight codes have been proposed for efficiently synthesizing deoxyribonucleic acid (DNA) for massive data storage, where a multiple of DNA strands are synthesized in parallel. We report on the redundancy and information rate of maxentropic low-weight codes for asymptotically large codeword length. We compare the performance of low-complexity nibble replacement (NR) codes, which are designed to minimize the synthesis time, with the performance of maxentropic low-weight codes. Finally, the asymptotic redundancy and information rate of codes with a runlength limitation are investigated. 1. Introduction The pioneering experiments conducted by Church et al. [1] demonstrated the feasibility to store data in synthetic deoxyribonucleic acid (DNA), promising a huge data capacity, nil dissipation during storage, and very long-term stability. Natural DNA consists of four types of nucleotides: adenine (‘A’), cytosine (‘C’), guanine (‘G’), and thymine (‘T’). Codes are used for translating user data into sequences of digits in the quaternary alphabet {A, C, G, T} that are suitable for the synthesis of DNA strands. Prior art studies have focused on error-correcting codes for restoring various kinds of defects in DNA [2,3,4] or constrained codes that avoid the generation of vexatious DNA sequences that are prone to error; see, for example, Refs. [5,6,7,8]. The synthesis of DNA strands is a relative expensive part of the storage chain. In array-based synthesis, multiple DNA strands are synthesized in parallel [9] by adding in each cycle a single nucleotide to a subset of the DNA strands. Lenz et al. [10], Makarychev et al. [11], Elishco and Huleihel [12], Immink et al. [13], and Nguyen et al. [14] presented and analyzed coding techniques for efficiently synthesizing multiple parallel strands so that overall synthesis time can be shortened. Of specific interest in minimizing the synthesis time are sets (codes) of words of low weight, which are dealt with in the next subsection. 1.1. Low-Weight Codes Although our main interest is in the quaternary DNA case, we will consider q-ary sequences for generality. For clerical convenience, we assume that the alphabet used is {1,…,q}, where q>1 is a positive integer. For the DNA case, we represent the quaternary alphabet {A, C, G, T} by {1,…,4}. Let a=(a1,…,an), ai∈{1,…,q}, be a sequence of n symbols, called word of length n. The symbol sum (1)w(a)=∑i=1nai is termed the weight of the word a. Clearly, n≤w(a)≤qn. A constant-weight code of length n, denoted by Sn(w), consists of all words of weight w, that is, (2)Sn(w)={a∈{1,…,q}n:w(a)=w}. The size of Sn(w), denoted by |Sn(w)|, is found as the coefficient of zw of the generating function [15] (3)∑i=1qzin. For synthesizing multiple words into physical sequences in parallel, we assume the sequences are generated by adding symbols in cycles. In each cycle in the synthesis process, one particular symbol from {1,…,q} is added to the sequences of the words waiting for that symbol. Throughout this paper, we assume the symbol adding in the subsequent cycles is in the order 1,2,…,q,1,2,…,q,1,2,…, which has been shown to be optimal; see [10,12]. In order to allow any word from {1,…,q}n to be synthesized, qn cycles are needed. By restricting the set of words used for representing data, the number of required synthesis cycles can be reduced, as explained next. Let the low-weight code ∪w=ntSn(w) be the union of the sets of words of weight w≤t, where the integer t, n≤t≤qn denotes the maximum weight of the codewords. As explained in [10,13], low-weight codewords y can be bijectively mapped to words x=(x1,…,xn), xi∈{1,…,q}, by (4)xi=xi−1+yi mod q, with x0=q, such that the words x have a synthesis time of at most t cycles. Let the low-weight code be denoted as Yn(γ), where γ=t/n, and the associated set of words x as Xn(γ). From the synthesis perspective, we are interested in properties of the codes Xn(γ), but because of the bijective mapping we can also study the low-weight codes Yn(γ). 1.2. Redundancy and Information Rate The redundancy (in bits per symbol) of a low-weight code Yn(γ) is defined by (5)ρn(γ)=log2(q)−Rn(γ), where (6)Rn(γ)=1nlog2|Yn(γ)|. Lenz et al. [10] also introduced the information rate (in bits per cycle) of a low-weight code Yn(γ) as (7)Wn(γ)=1nγlog2|Yn(w)|=1γRn(γ). Of course, ρn(γ) and Wn(γ) are also the redundancy and information rate, respectively, of Xn(γ). Note that Wn(γ) is a measure for the synthesis efficiency of the codewords of Xn(γ). Using (3), we can straightforwardly compute ρn(γ) and Wn(γ) versus γ. Figure 1 and Figure 2 show the results for n=16, 32, 64, and q=4. The curves suggest that ρn(γ) and Wn(γ) have a lower bound and upper bound, respectively, for asymptotic large n. A major goal of this paper is to determine these bounds. 1.3. Contributions and Overview of the Paper Besides introducing the framework as just described, Lenz et al. [10] also conducted a brief performance analysis of DNA synthesis codes, mainly based on tools from the theory of cost-constrained channels. Constructions of efficient DNA synthesis codes were further explored in [13]. Here, in this paper, Section 2 deals with an extensive asymptotic analysis, with a focus on the trade-off between redundancy and information rate. The results are derived using Jaynes’ maximum entropy principle. In Section 3, we compare the obtained theoretical optima with the performance of practical nibble replacement codes. Finally, we extend the analysis to codes with a runlength constraint in Section 4 and conclude the paper in Section 5. 2. Asymptotic Analysis of Low-Weight Codes In order to evaluate the sizes of large low-weight codes, we use the following approach. Let Cn(w) be the set of compositions c=(n1,…,nq) of n, where ni are nonnegative integers such that ∑i=1qni=n subject to the constraint ∑i=1qini=w. The number of q-ary words of length n with ni symbols equal to i, 1≤i≤q, denoted by Nc, equals (8)Nc=n!n1!…nq!. The constant-weight code size, |Sn(w)|, is found by summing Nc for all possible compositions c∈Cn(w) so that (9)|Sn(w)|=∑c∈Cn(w)Nc. 2.1. Asymptotic Analysis of Rn(γ) We are specifically interested in Rn(γ) for asymptotically large n. So, let n→∞ and ni→∞ for all i, while keeping pi=ni/n, 1≤i≤q, the distribution of the symbol values, fixed. It then follows (see Wallis argument in Section 11.4 of [16]), using Stirling’s approximation, that (10)1nlog2Nc→Hc, and thus (11)1nlog2|Sn(w)|→maxc∈Cn(w)Hc, where (12)Hc=−∑i=1qpilog2pi. In a similar vein, we find (13)Rn(γ)→maxn≤w≤γn1nlog2|Sn(w)|→maxn≤w≤γnmaxc∈Cn(w)Hc. Since 1nlog2|Sn(w)| is monotonically increasing with w, n≤w≤γn, if 1≤γ≤(q+1)/2, with a maximum log2(q) at w=n(q+1)/2, we infer (14)Rn(γ)→maxc∈Cn(γn)Hc,1≤γ<(q+1)/2,log2(q),(q+1)/2≤γ≤q. The problem of determining R∞(γ)=limn→∞Rn(γ), and thus the asymptotic redundancy ρ∞(γ)=log2(q)−R∞(γ) and the asymptotic information rate W∞(γ)=1γR∞(γ), is now a matter of finding, for asymptotically large n, a c in Cn(γn) that maximizes Hc. The composition c=(n1,…,nq) in Cn(γn) is characterized by (15)∑i=1qni=n and ∑i=1qini=γn, which can be conveniently rewritten as (16)∑i=1qpi=1 and ∑i=1qipi=γ. In the next subsection, we maximize Hc by a judicious choice of the distribution of the symbol values, pi, under these conditions. 2.2. Principle of Maximum Entropy We change the above setting of finite-length codewords and now assume a stationary information source that transmits symbols of (integer) magnitude i, i∈{1,…,q}, with probability distribution p=(p1,…,pq), where pi∈R and ∑pi=1. The information content per symbol sent, or entropy, denoted by H, defined by Shannon [17], is (17)H=−∑i=1qpilog2pi. Although the variable Hc in (12) and Shannon’s entropy H share the same expression in p, the background of the expressions is different [16]. Note that in (12), the pi’s are rational numbers, while in (17) the pi’s are assumed to be real numbers. We are interested in maximizing the entropy H. Define (18)H^(γ)=maxp1,…,pqH, 1≤γ≤q, where the maximization over the pi is under the conditions (16). Jaynes [18] concluded that the entropy, H, is maximized subject to these constraints by the maxentropic probability distribution (19)p^i=2α−βi,1≤i≤q, where the parameters α and β, α,β∈R, satisfy the conditions (20)α=−log2∑i=1q2−βi and (21)∑i=1qi2α−βi=γ. After substituting (19) to (21) into (17), we find (22)H^(γ)=βγ−α. For the case q=2, we may easily find that p1+p2=1 and p1+2p2=γ, so that p1=2−γ, p2=γ−1, and (23)H^(γ)=−(2−γ)log2(2−γ)−(γ−1)log2(γ−1), 1≤γ≤2. For q>2, no simple closed-form expression could be found, and we use numerical methods for solving (20) and (21). 2.3. Asymptotic Redundancy and Information Rate From (14), we obtain (24)R∞(γ)=H^(γ),1≤γ<(q+1)/2,log2(q),(q+1)/2≤γ≤q. As a result, the asymptotic redundancy is (25)ρ∞(γ)=log2(q)−H^(γ),1≤γ<(q+1)/2,0,(q+1)/2≤γ≤q. Figure 3 depicts, for q=2,4, and 6, the relationship between the asymptotic redundancy ρ∞(γ) and γ. The asymptotic information rate, W∞(γ), equals (26)W∞(γ)=H^(γ)/γ,1≤γ<(q+1)/2,log2(q)/γ,(q+1)/2≤γ≤q. Figure 4 shows W∞(γ) versus γ for q=2,4, and 6. The maximum asymptotic information rate, denoted by W^∞=maxγW∞(γ), can be found after an analysis of (22). We write (22), using (20) and (21), as a function of β and conclude that the largest (real) root of (27)∑i=1q2−iβ=1, denoted by β^, maximizes W∞(γ). We obtain, see (20), α=0 and hence, see (22), we infer that (28)H^∞=H^(γ^)=β^γ^, where (29)γ^=∑i=1qi2−β^i, and (30)W^∞=β^. Note that Equation (27) is equivalent to the characteristic equation ∑i=1qz−i=1 of a binary source under the constraint that the maximum runlength is q [19]. The capacity of binary sequences with a maximum runlength constraint of q equals log2(z^), where z^ is largest (real) root of the characteristic equation [17]. Hence, the maximum asymptotic information rate W^∞=β^ of q-ary low-weight codes is equal to this capacity. Numerical values of the latter have been listed for selected values of q in [19]. Since the capacity approaches unity for increasing values of q, the same holds for the information rate W^∞, which is achieved for γ^→2. In other words, for large values of n and q, the maximum information rate is achieved by setting the maximum weight of the low-weight code equal to (roughly) 2n. The corresponding redundancy is log2(q)−γ^β^→log2(q)−2. For any q, the asymptotic redundancy can be lowered from log2(q)−γ^β^ to zero by increasing γ from γ^ to (q+1)/2, which implies that the asymptotic information rate decreases from β^ to 2log2(q)/(q+1). This trade-off between redundancy and information rate is further explored for the case q=4 in the next subsection. 2.4. Case Study for q=4 In this subsection, we consider the case q=4, which is of particular interest since it is the alphabet size for DNA synthesis codes. For q=4, we find using numerical methods that W^∞=β^=0.947, γ^=1.766, and H^∞=1.672. The probability distribution at maximum entropy is p^= (0.519, 0.269, 0.140, 0.072). Figure 5 shows the parametric representation of W∞(γ) versus ρ∞(γ) with γ as a parameter for the case q=4. The curve is a typical price/performance curve, where we may observe that a higher W∞(γ) comes with a higher penalty in redundancy ρ∞(γ). It is the difficult task of a system designer to trade the costs and benefits of the conflicting parameters. Note that in the range γ≥5/2 we have ρ∞(γ)=0, a zero-redundant system, while in the range γ<γ^ we may achieve the same information rate W∞(γ) with a smaller redundancy. For example, we may notice that we can achieve W∞(γ)=0.8 for zero redundancy cost or for roughly 0.9. In practice, we prefer the smaller redundancy alternative so that in this range of practical interest, we have 4/5≤W∞(γ)≤W^∞=0.947 and 0≤ρ∞(γ)≤2−H^∞=0.328. Figure 6 displays W∞(γ) versus ρ∞(γ) in the range of practical interest γ^≤γ<5/2. 3. Comparison with Implemented Codes In this section, we compare the performance of implemented codes with that of maxentropic low-weight codes. In [13], various code implementations have been assessed. Here, we focus on the nibble replacement (NR) algorithm [13,20], which is an efficient method for encoding/decoding with small complexity and redundancy. In the NR format, an n-symbol strand is divided into L subwords of length m, so that n=Lm. Let tm be the maximum allowed cycle count of an m-symbol q-ary word, then the maximum cycle count of the n-symbol q-ary word is t=Ltm. Let (31)M=∑w=mtm|Sm(w)| denote the number of low-weight m-symbol codewords. Define mh=⌈log2M⌉ and (32)L=2mh−12mh−M. The NR algorithm translates Lmh−1 source bits into L mh-bit words. Each mh-bit word is translated, using a look-up table, into a q-ary m-symbol word that satisfies the tm-cycle count constraint. The NR encoding method requires data storage of L mh-bit words, the execution of the encoding algorithm [13], and a look-up table for translating an mh-bit wide word into a word of m q-ary symbols so that very large, n-symbol wide, look-up tables are avoided. The overall redundancy per symbol, ρ(t), and information rate, W(t), of the n-symbol word are (33)ρ(t)=L(log2(q)m−mh)+1n and (34)W(t)=Lmh−1t. Table 1 shows numerical results selected from Table I in [13]. The scattered points (black circles) in Figure 6 are found by plotting the redundancy, ρ(t), and information rate, W(t), of the NR codes shown in Table 1. 4. Runlength Limitation It is known that homopolymer runs, i.e., adjacent repetitions of the same nucleotide, make DNA-based data storage more error prone [12]. Therefore, it could be advantageous to use strands in which long runs are avoided. Of course, this comes at the expense of an increased redundancy. In this section, we perform an asymptotic analysis of codes aiming at (i) small redundancy, (ii) high information rate, and (iii) small maximum runlength. These are conflicting goals resulting into trade-off considerations. Again, we start by investigating q-ary codes and then focus on the q=4 case. We say that a code is r-RLL (runlength limited) if within any codeword any run of identical symbols is of length at most r, where 1≤r≤n. When r=n, there is actually no constraint with respect to the runlength. Here, we focus on the other extreme, r=1; i.e., we consider codewords in which any two adjacent symbols are different. We investigate the asymptotic redundancy and information rate of q-ary 1-RLL codes. The same notation as before is used, where we indicate with a tilde that the r=1 constraint is in place. Let X˜n(γ) denote the q-ary code consisting of all 1-RLL sequences that can be synthesized in at most t=γn cycles. The codewords y˜=(y˜1,…,y˜n) of the associated low-weight code Y˜n(γ) are obtained from the codewords x˜=(x˜1,…,x˜n) of X˜n(γ) by the bijective mapping (35)y˜i=x˜i−x˜i−1 mod q with x˜0=q. Note that due to the 1-RLL property of x˜, it holds that x˜i≠x˜i−1 and thus y˜i≠q for all 2≤i≤n. Hence, Y˜n(γ)=∪w=nγnS˜n(w), where (36)S˜n(w)={y˜∈{1,…,q}n:w(y˜)=w∧y˜i≠q∀i≥2} and the range for γ is in this case 1≤γ≤q−1+1/n, since the maximum number of cycles is (q−1)n+1 rather than qn due to the runlength constraint. Similarly to what we did before, we next evaluate (37)R˜n(γ)=1nlog2|Y˜n(γ)|. Since the symbol distribution (p˜1,…,p˜q) satisfies, for any codeword in the low-weight code, (38)p˜q≤1n→0 as n→∞, we can conclude that the value of R˜∞(γ) in the q-ary case is equal to the value of R∞(γ) in the (q−1)-ary case. Hence, it easily follows that The asymptotic redundancy ρ˜∞(γ) in the q-ary 1-RLL case equals log2(q/(q−1)) plus the asymptotic redundancy ρ∞(γ) in the (q−1)-ary case without runlength restriction; The asymptotic redundancy ρ˜∞(γ) in the q-ary 1-RLL case equals log2(q/(q−1)) plus the asymptotic redundancy ρ∞(γ) in the (q−1)-ary case without runlength restriction; The asymptotic information rate W˜∞(γ) in the q-ary 1-RLL case equals the asymptotic information rate W∞(γ) in the (q−1)-ary case without runlength restriction. The asymptotic information rate W˜∞(γ) in the q-ary 1-RLL case equals the asymptotic information rate W∞(γ) in the (q−1)-ary case without runlength restriction. As an illustration, we consider the case q=4. By applying the results from (25) and (26) for q=3, we find ρ˜∞(γ) and W˜∞(γ) for q=4. These 1-RLL results are compared to the corresponding results without runlength limitation from Section 2 in Figure 7, Figure 8 and Figure 9. Results for r-RLL codes, 1