# Codes with Biochemical Constraints and Single Error Correction for DNA-Based
Data Storage

Shu Liu, Chaoping Xing, Yaqian Zhang  Shu Liu is with National Key Laboratory
on Wireless Communications, University of Electronic Science and Technology of
China, Chengdu, China (shuliu@uestc.edu.cn). Chaoping Xing and Yaqian Zhang
are with School of Electronic Information and Electric Engineering, Shanghai
Jiao Tong University, Shanghai, China<EMAIL_ADDRESS>zhangyq9@sjtu.edu.cn).

###### Abstract

In DNA-based data storage, DNA codes with biochemical constraints and error
correction are designed to protect data reliability. Single-stranded DNA
sequences with secondary structure avoidance (SSA) help to avoid undesirable
secondary structures which may cause chemical inactivity. Homopolymer run-
length limit and GC-balanced limit also help to reduce the error probability
of DNA sequences during synthesizing and sequencing. In this letter, based on
a recent work [4], we construct DNA codes free of secondary structures of stem
length $\geq m$ and have homopolymer run-length $\leq\ell$ for odd $m\leq 11$
and $\ell\geq 3$ with rate $1+\log_{2}\rho_{m}-3/(2^{\ell-1}+\ell+1)$, where
$\rho_{m}$ is in Table I. In particular, when $m=3$, $\ell=4$, its rate tends
to 1.3206 bits/nt, beating a previous work by Benerjee et al.. We also
construct DNA codes with all of the above three constraints as well as single
error correction. At last, codes with GC-locally balanced constraint are
presented.

##  I Introduction

In DNA-based storage systems, data is translated to DNA sequences consisting
of four nucleotides A, T, C, G, and stored in a DNA pool. To protect data from
errors, DNA sequences are desired to be able to correct insertion, deletion
and substitution errors, and also satisfy some constraints that help to reduce
error probability [6, 11].

For DNA alphabet $\\{{\rm A,T,C,G}\\}$, the Watson-Crick complement gives
$\overline{\rm A}={\rm T}$, $\overline{\rm T}={\rm A}$, $\overline{\rm C}={\rm
G}$, $\overline{\rm G}={\rm C}$. The reverse-complement of a DNA sequence
$x_{1}x_{2}...x_{n}$ with $x_{i}\in\\{{\rm A,T,C,G}\\}$ is defined as
$\overline{x_{n}\cdots x_{2}x_{1}}$. A secondary structure of a DNA sequence
is formed by folding the sequence back upon itself, and this may lead to
chemical inactivity of the sequence. For example, in ATTCGGAA, the two
subsequences TTC, GAA are reverse-complements of each other and may bind to
each other after pairing of A with T and G with C. Thus it forms a secondary
structure with a loop and a stem of length 3. For a positive integer $m$, an
$m$-SSA (secondary structure avoidance) sequence does not contain two non-
overlapping reverse-complement consecutive subsequences of length $m$. The SSA
constraint can reduce error probability of DNA sequences when reading data
[11]. Another constraint is homopolymer run-length limit, indicating that the
maximum number of repetitive consecutive symbols in a DNA sequence should be
$\leq\ell$, which is called $\ell$-run-length limited property. Moreover, the
percentage of nucleotides G and C in the whole sequence (GC content) is
expected to be about $50\%$, called GC-balanced limit constraint.

For a quaternary DNA code $\mathcal{C}$ of length $n$, the code rate is
defined as $\log_{2}{|\mathcal{C}|}/n$ (bits/nt), which indicates the storage
overhead. A challenging problem is to construct DNA codes satisfying multiple
constraints and error correction with high code rate. In the literature,
several works [1, 13, 4] are presented to construct $m$-SSA codes for
different $m$. In particular, [4] investigated codes for $m\leq 6$, which
achieve optimal rate for $m=2,3$. The work [1] designed 3-SSA and 4-run-length
limited codes with rate 1.1609. Run-length limited and GC-balanced codes are
constructed in [15, 18, 8, 19]. The work [9] considered 3-SSA with run-length
limit and GC-balanced limit using constacyclic codes. [2] gave codes that
satisfy 3-SSA, 3-run-length limited and GC-balanced properties as well as
reverse constraint and reverse-complement constraint, with code rate 0.8617.
The works [3, 12] constructed $\ell$-run-length limited and GC-balanced codes
with GC content within the range $0.5\pm\epsilon$, called
$(\epsilon,\ell)$-constrained codes. The work [10] studied capacity-achieving
$(\epsilon,\ell)$-constrained codes.

In the scenario of error correction, we call insertion errors and deletion
errors are insertion and deletion (insdel for short) errors, and edit errors
present insertion, deletion and substitution errors. [3, 12] extended the
constrained codes to also correct single insdel/edit error. Cai et al. [5]
partitioned each codeword to local segments (partitions) of same length $s$
and gave a code design to enable error correction and almost GC balance in
each segment with code rate about $2(1-\log_{2}s/s)$ where $s=\Omega(\log n)$.
Another definition of locally balanced constraint is introduced in [7, 17] and
means that any length-$s$ subsequence of a DNA codeword of length $n$
satisfies the GC-balanced property (called GC-locally balanced).

In this letter, we consider the problem of constructing DNA codes with
multiple constraints and error correction. The main contributions are as
follows.

  * •

We present a construction of $m$-SSA and $\ell$-run-length limited DNA codes
for odd $m\leq 11$ and $\ell\geq 3$. It has code rate
$1+\log_{2}\rho_{m}-3/(2^{\ell-1}+\ell+1)$, where $\rho_{m}$ is given in Table
I. In particular, when $m=3$ and $\ell=4$, the code has rate approximately
1.3206, which performs better than the code in [1].

  * •

For any integer $\ell\geq 3$, and a small real $0<\epsilon<0.5$, we construct
3-SSA, $\ell$-run-length limited and GC-balanced codes with GC content within
$0.5\pm\epsilon$. The codes are further extended to also correct single edit
error by a concatenation technique using Hamming codes and quaternary VT codes
with rate approximately $(1-\frac{\log t}{t})(1+\log_{2}\rho)$, where $t$ is a
positive integer and $\rho$ is the largest real root of the equation
$x^{\ell+1}-\sum_{i=0}^{\ell-2}x^{i}=0$.

  * •

We give a transformation to convert GC-balanced codes to GC-locally balanced
codes. The obtained GC-locally balanced codes also maintain 3-SSA, $\ell$-run-
length limited and GC-balanced property with GC content within
$0.5\pm\epsilon$, for some $\ell\geq 3$, and $0<\epsilon<0.5$, as well as
error correction property.

The rest of the letter is organized as follows. Section II introduces some
preliminaries. Section III presents $m$-SSA and $\ell$-run-length limited DNA
codes for any odd $m\leq 11$ and $\ell\geq 3$. Section IV gives DNA codes with
multiple constraints as well as error correction. GC-locally balanced codes
are constructed in Section V.

##  II Preliminary

###  II-A Notations and definitions

For positive integers $n$ and $i<j$, denote $[n]=\\{1,...,n\\}$,
$[i,j]=\\{i,i+1,...,j\\}$ and $[i,j)=\\{i,i+1,...,j-1\\}$. Let
$\mathbb{F}_{q}$ be a finite field and $\mathbb{Z}_{q}=\\{0,1,...,q-1\\}$.
Denote $\sum_{\rm DNA}=\\{{\rm A,T,C,G}\\}$ to be the DNA alphabet. Define the
complement $\overline{\rm A}={\rm T}$, $\overline{\rm T}={\rm A}$,
$\overline{\rm C}={\rm G}$, $\overline{\rm G}={\rm C}$. Let
$\bm{x}=(x_{1},\cdots,x_{n})\in\sum_{\rm DNA}^{n}$, we say a subsequence of
$\bm{x}$ when it contains consecutive symbols of $\bm{x}$. The reverse-
complement of $\bm{x}$ is defined as ${\rm
RC}(\bm{x})=\overline{x_{n},\cdots,x_{1}}$. For some positive integer $m$, we
say $\bm{x}$ is $m$-SSA (secondary structure avoidance), if $\bm{x}$ does not
have two non-overlapping subsequences $\bm{y}$ and $\bm{y}^{\prime}$ of length
$\geq m$ such that $\bm{y}={\rm RC}(\bm{y}^{\prime})$. Define the GC weight of
$\bm{x}$ to be $\mathrm{wt}_{\mathrm{GC}}(\bm{x})=|\\{i\in[n]:x_{i}={\rm
G}~{}{\rm or}~{}{\rm C}\\}|$.

######  Definition 1.

Let $0<\epsilon<0.5$ be a small real and $n,s$ be two positive integers. Let
$\bm{x}=(x_{1},\cdots,x_{n})\in\sum_{\rm DNA}^{n}$.

  * •

GC-$\epsilon$-globally balanced. $\bm{x}$ is called GC-$\epsilon$-globally
balanced if $|\frac{\mathrm{wt}_{\mathrm{GC}}(\bm{x})}{n}-0.5|\leq\epsilon$.

  * •

GC-$(s,\epsilon)$-partition balanced. Suppose $s\mid n$ and $\bm{x}$ is
partitioned into $\frac{n}{s}$ segments of size $s$, that is,
$\bm{x}=(\bm{x}^{(1)},\cdots,\bm{x}^{(\frac{n}{s})})$, where
$\bm{x}^{(i)}=(x_{(i-1)s+1},\cdots,x_{is})$, $i\in[\frac{n}{s}]$. Then
$\bm{x}$ is called GC-$(s,\epsilon)$-partition balanced if
$|\frac{\mathrm{wt}_{\mathrm{GC}}(\bm{x}^{(i)})}{s}-0.5|\leq\epsilon$ for all
$i\in[\frac{n}{s}]$.

  * •

GC-$(s,\epsilon)$-locally balanced. Suppose $s<n$ and for $1\leq i\leq n-s+1$,
denote $\bm{x}_{i}=(x_{i},x_{i+1},\cdots,x_{i+s-1})$, then $\bm{x}$ is called
GC-$(s,\epsilon)$-locally balanced if
$|\frac{\mathrm{wt}_{\mathrm{GC}}(\bm{x}_{i})}{s}-0.5|\leq\epsilon$ for all
$i\in[n-s+1]$.

It is obvious that when $s\mid n$, a GC-$(s,\epsilon)$-locally balanced
sequence is also GC-$(s,\epsilon)$-partition balanced and
GC-$\epsilon$-globally balanced. For a binary sequence
$\bm{z}\in\mathbb{Z}_{2}^{n}$, similar definitions can be obtained by
replacing GC-weight by Hamming weight of $\bm{z}$ and removing the term “GC”.
In the following, for GC-$\epsilon$-globally balanced sequences, we usually
omit “globally”, when it is clear from the context.

######  Definition 2.

Let $\bm{x}\in\sum_{\rm DNA}^{n}$ (resp. $\mathbb{Z}_{2}^{n}$) and write
$\bm{x}=\left(a_{1}^{(n_{1})},\cdots,a_{t}^{(n_{t})}\right)$ for some positive
integers $n_{1},\cdots,n_{t}$ and $a_{1},\cdots,a_{t}\in\sum_{\rm DNA}$ (resp.
$\mathbb{Z}_{2}$) satisfying $n_{1}+\cdots+n_{t}=n$ and $a_{i}\neq a_{i+1}$
for all $1\leq i\leq t-1$. That is, $a_{i}^{(n_{i})}$ contains $n_{i}$
consecutive symbols of $a_{i}$. We call each $a_{i}^{(n_{i})}$ a run of length
$n_{i}$ for $i\in[t]$.

A code is said to be $\ell$-run-length limited if every codeword has run
length at most $\ell$ for some integer $\ell>0$.

###  II-B Varshamov-Tenengolts (VT) codes

The Varshamov-Tenengolts codes are designed for the insertion/deletion channel
and are asymptotically optimal single insdel correcting codes. In [16],
Tenengolts generalized binary VT codes to $q$-ary ones for $q>2$. Next we
review the definition of $q$-ary VT codes which will be used later. For a
$q$-ary sequence $\bm{x}=(x_{1},\cdots,x_{n})\in\mathbb{Z}_{q}^{n}$, define
the signature of $\bm{x}$ to be the binary vector
$\alpha(\bm{x})=(\alpha_{1},\cdots,\alpha_{n-1})\in\\{0,1\\}^{n-1}$, where
$\alpha_{i}=1$ if $x_{i+1}\geq x_{i}$ and $\alpha_{i}=0$ if $x_{i+1}<x_{i}$,
for $i\in[n-1]$. Define the binary VT syndrome of $\alpha(\bm{x})$ to be
$\mathrm{Syn}(\alpha(\bm{x}))=\sum_{i=1}^{n-1}i\alpha_{i}$.

######  Definition 3 ($q$-ary VT codes).

For $a\in\mathbb{Z}_{n}$ and $b\in\mathbb{Z}_{q}$, let

$\displaystyle\mathrm{T}_{a,b}(n;q)=\\{\bm{x}\in\mathbb{Z}_{q}^{n}:$
$\displaystyle\mathrm{Syn}(\alpha(\bm{x}))\equiv a\ (\mathrm{mod}\ n)$
$\displaystyle\mathrm{and}\ \sum_{i=1}^{n}x_{i}\equiv b\ (\mathrm{mod}\
q)\\},$

then $\mathrm{T}_{a,b}(n;q)$ gives a class of $q$-ary VT codes.

The $q$-ary VT codes can correct one insdel error with a linear-time decoder.
For any $n$ and $q$, there exist some $a\in\mathbb{Z}_{n}$ and
$b\in\mathbb{Z}_{q}$ s.t. $|\mathrm{T}_{a,b}(n;q)|\geq\frac{q^{n}}{qn}$ by the
pigeonhole principle. Tenengolts provided a systematic encoder with redundancy
$\log_{2}{n}+C_{q}$, where $C_{q}$ is independent of the code length $n$.

##  III Code constructions with secondary structure avoidance and run-length
limit

Given some $m>0$, we adopt the notion of TC-m-dominant in [4] as follows. A
DNA sequence $\bm{x}$ is called TC-$m$-dominant, if for every subsequence of
length $m$, the sum of appearances of T and C is larger than $m/2$. Similarly,
a binary sequence is called “0”-$m$-dominant, if for every subsequence of
length $m$, the sum of appearances of the symbol “0” is larger than $m/2$. Let
$S_{\rm TC}(m,n)\subseteq\sum_{\rm DNA}^{n}$ be the set of TC-$m$-dominant DNA
sequences of length $n$ and $S_{0}(m,n)\subseteq\mathbb{Z}_{2}^{n}$ be the set
of “0”-$m$-dominant binary sequences of length $n$. [4] has investigated
$S_{\rm TC}(m,n)$ and $S_{0}(m,n)$ for odd $m\leq 11$ using recursive
construction as well as a brute-force algorithm. It is also illustrated in [4]
that a TC-$m$-dominant sequence must be an $m$-SSA sequence.

######  Lemma 1.

[4] Wnen $m$ is odd, a TC-$m$-dominant sequence must be an $m$-SSA sequence.
Thus a code $\mathcal{C}$ consisting of all TC-$m$-dominant sequences of
length $n$ is an $m$-SSA code.

######  Lemma 2.

[4] For odd $m\leq 11$, $|S_{0}(m,n)|$ is approximately $\rho_{m}^{n}$, where
$\rho_{m}$ is given in Table I.

TABLE I: The Value of $\rho_{m}$ $m$ | 3 | 5 | 7 | 9 | 11
---|---|---|---|---|---
$\rho_{m}$ | 1.5515 | 1.6980 | 1.7698 | 1.8131 | 1.8423

In the following, we present $m$-SSA and $\ell$-run-length limited codes for
odd $m\leq 11$ and $\ell\geq 3$ using $S_{0}(m,n)$ in [4]. Define a map $\tau$
from DNA alphabet to binary pairs as follows.

$\tau({\rm T})=00,~{}~{}\tau({\rm C})=01,~{}~{}\tau({\rm
A})=10,~{}~{}\tau({\rm G})=11.$ (1)

For any $\bm{c}=(c_{1},c_{2},\cdots,c_{n})\in\sum_{\rm DNA}^{n}$, define
$\tau(\bm{c})=(\tau(c_{1}),\tau(c_{2}),\cdots,\tau(c_{n}))\in\mathbb{Z}_{2}^{2n}$.
For any two binary sequences $\bm{x}=(x_{1},x_{2},\cdots,x_{n})$ and
$\bm{y}=(y_{1},y_{2},\cdots,y_{n})$ of length $n$, define
$\bm{x}||\bm{y}=(x_{1}y_{1},x_{2}y_{2},\cdots,x_{n}y_{n})\in\mathbb{Z}_{2}^{2n}$.

By the definition of map $\tau$ and Lemma 1, we can directly get the following
Lemma.

######  Lemma 3.

Let $\bm{c}=(c_{1},c_{2},\cdots,c_{n})\in\mathbb{Z}_{2}^{n}$ be
“0”-$m$-dominant, and $\bm{d}=(d_{1},d_{2},\cdots,d_{n})\in\mathbb{Z}_{2}^{n}$
be $\ell$-run-length limited, then $\tau^{-1}(\bm{c}||\bm{d})$ is $m$-SSA and
$\ell$-run-length limited.

Recall the work [12] presented an RLL encoder to transform any sequence in
$\mathbb{Z}_{q}^{n-1}$ to an $\ell$-run-length limited sequence by introducing
one redundant symbol on condition that $n\leq 2^{\ell-1}+\ell-1$, using the
sequence replacement technique. Next we give the following encoding algorithm.

Let $m,\ell,n,t$ be positive integers with odd $m\leq 11$, $\ell\geq 3$ and
$n\leq 2^{\ell-1}+\ell-1$.

Algorithm 1 Construction $I$ for DNA codes

1:$\bm{x}\in S_{0}(m,(n+2)t)$ and $\bm{y}\in\mathbb{Z}_{2}^{(n-1)t}$.

2:$\bm{c}\in\sum_{\rm DNA}^{(n+2)t}$.

3:Let $\bm{y}=(\bm{y}_{1},\bm{y}_{2},\cdots,\bm{y}_{t})$ with
$|\bm{y}_{i}|=n-1$ for $i\in[t]$.

4:Encode each $\bm{y}_{i}$ to be a $\ell$-run-length limited sequence
$\bm{y}^{\prime}_{i}\in\mathbb{Z}_{2}^{n}$ by the RLL encoder in [12]. Denote
$\bm{y}^{\prime}_{i}=(y^{\prime}_{i,1},y^{\prime}_{i,2},\cdots,y^{\prime}_{i,n})$
for $i\in[t]$.

5:For $i\in[t]$, set $z_{i,1}=\mathbb{Z}_{2}\setminus\\{y^{\prime}_{i,1}\\}$
and $z_{i,2}=\mathbb{Z}_{2}\setminus\\{y^{\prime}_{i,n}\\}$.

6:Update each $\bm{y}^{\prime}_{i}$ to be $z_{i,1}\bm{y}^{\prime}_{i}z_{i,2}$
and set
$\bm{y}^{\prime\prime}=(\bm{y}^{\prime}_{1},\bm{y}^{\prime}_{2},\cdots,\bm{y}^{\prime}_{t})\in\mathbb{Z}_{2}^{(n+2)t}$.

7:Output $\bm{c}=\tau^{-1}(\bm{x}||\bm{y}^{\prime\prime})$.

One can directly obtain a decoder according to the inverse process of
Algorithm 1 and the RLL decoder given in [12]. Moreover, in step $3$ of
Algorithm 1, the updated sequences $\bm{y}^{\prime}_{i},i\in[t]$ and
$\bm{y}^{\prime\prime}$ are still $\ell$-run-length limited, since $\ell\geq
3$. Thus the output codeword $\bm{c}$ is $m$-SSA and $\ell$-run-length limited
by Lemma 3.

######  Remark 1.

The DNA code $\mathcal{C}$ obtained by Algorithm 1 has length $(n+2)t$,
cardinality $2^{(n-1)t}|S_{0}(m,(n+2)t)|$. It has rate $\approx
1+\log_{2}\rho_{m}-3/(2^{\ell-1}+\ell+1)$ when $n=2^{\ell-1}+\ell-1$ and $t$
tends to infinity. In particular, when $m=3$, $\ell=4$, $n=11$, the code rate
tends to $\frac{10}{13}+\log_{2}\rho_{3}\approx 1.3206$. Note the work [1]
gave $3$-SSA and $4$-run-length limited DNA codes with rate 1.1609.

##  IV Code constructions with multiple constraints and error correction

In this section, we firstly present a construction of 3-SSA DNA codes that is
also $\ell$-run-length limited and GC-$\epsilon$-balanced for some integer
$\ell\geq 3$ and some real $0<\epsilon<0.5$. Then we extend it to also correct
errors by using Hamming codes and quaternary VT codes.

###  IV-A Codes with multiple biochemical constraints

Recall the map $\tau$ defined in (1), we have the following Lemma.

######  Lemma 4.

Let $\bm{c}=(c_{1},c_{2},\cdots,c_{n})\in\mathbb{Z}_{2}^{n}$ be
“$0$”-$3$-dominant and $\ell$-run-length limited, and
$\bm{d}=(d_{1},d_{2},\cdots,d_{n})\in\mathbb{Z}_{2}^{n}$ be
$\epsilon$-balanced, then the DNA sequence $\tau^{-1}(\bm{c}||\bm{d})$ is
$3$-SSA, $\ell$-run-length limited and GC-$\epsilon$-balanced.

It suffices to construct the two classes of binary sequences as illustrated in
Lemma 4. We first construct binary sequences that are “0”-$3$-dominant and
$\ell$-run-length limited for $\ell\geq 3$. Define
$f(\ell,n)\subseteq\mathbb{Z}_{2}^{n}$ to be the set of binary sequences that
are “0”-$3$-dominant and $\ell$-run-length limited. Define $f_{i}(\ell,n)$ to
be the subset of $f(\ell,n)$ where each sequence contains $i$ zeros in the
first run. Then we have the following Lemma.

######  Lemma 5.

The size of $f(\ell,n)$ and $f_{0}(\ell,n)$ satisfy the following equations.

$\displaystyle|f(\ell,n)|=$
$\displaystyle\sum_{i=0}^{\ell}|f_{i}(\ell,n)|=\sum_{i=0}^{\ell}|f_{0}(\ell,n-i)|,$
$\displaystyle|f_{0}(\ell,n)|=$
$\displaystyle\sum_{i=0}^{\ell-2}|f_{0}(\ell,n-3-i)|.$

###### Proof.

Note that a “0”-$3$-dominant binary sequence has no $\ell$-runs of symbol ”1”
since $\ell\geq 3$. And $f(\ell,n)$ can be partitioned into $\ell+1$ disjoint
subsets $f_{i}(\ell,n)$, $i\in\\{0,1,\cdots,\ell\\}$ according to the number
of zeros in the first run of each sequence. Thus
$|f(\ell,n)|=\sum_{i=0}^{\ell}|f_{i}(\ell,n)|$. Next we build a bijection from
$f_{i}(\ell,n)$ to $f_{0}(\ell,n-i)$ as follows.

$\underbrace{0\cdots 0}_{i}1x_{i+2}\cdots
x_{n}~{}~{}\mapsto~{}~{}1x_{i+2}\cdots x_{n}.$

Then $|f_{i}(\ell,n)|=|f_{0}(\ell,n-i)|$ for $i=0,...,\ell$ and
$|f(\ell,n)|=\sum_{i=0}^{\ell}|f_{i}(\ell,n)|=\sum_{i=0}^{\ell}|f_{0}(\ell,n-i)|.$

On the other hand, let $\bm{x}\in f_{0}(\ell,n)$, then $\bm{x}$ has the form
$100x_{4}\cdots x_{n}$ since $\bm{x}$ is “0”-3-dominant. Moreover, the
subsequence $x_{4}\cdots x_{n}$ following “100” must be “0”-$3$-dominant and
$\ell$-run-length limited with no more than $\ell-2$ zeros in the first run.
Thus
$|f_{0}(\ell,n)|=\sum_{i=0}^{\ell-2}|f_{i}(\ell,n-3)|=\sum_{i=0}^{\ell-2}|f_{0}(\ell,n-3-i)|$.
∎

By Lemma 5, we have a recursive method to construct $f(\ell,n)$ once the
$\ell+1$ sets $f_{0}(\ell,n-i)$, $i=0,\cdots,\ell$ are determined. And
$|f(\ell,n)|\approx(\ell+1)\rho^{n}$ when $n$ is sufficiently large, where
$\rho$ is the largest real root of the equation
$x^{\ell+1}-\sum_{i=0}^{\ell-2}x^{i}=0$. To illustrate this, we give an
example.

######  Example 1.

Set $\ell=4$. We give $f_{0}(4,n)$ for $n\in\\{4,5,6,7\\}$ in Table II.

TABLE II: $f_{0}(4,n)$ for $n\in\\{4,5,6,7\\}$ $n$ | 4 | 5 | 6 | 7
---|---|---|---|---
$|f_{0}(4,n)|$ | 2 | 3 | 3 | 4
$f_{0}(4,n)$ |  1000 1001 |  10000, 10001 10010 |  100001, 100010 100100 |  1000010, 1000100 1001000, 1001001

One can recursively construct $f(4,n)$ by Lemma 5. We construct $f(4,n)$ for
$n=7,8$ in Table III.

TABLE III: $f(4,n)$ for $n=7,8$ n | 7 | 8
---|---|---
$|f(4,n)|$ | 13 | 18
$f(4,n)$ |  0000100, 0001000 0001001, 0010000 0010001, 0010010 0100001, 0100010 0100100, 1000010 1000100, 1001000 1001001 |  00001000, 00001001 00010000 00010001, 00010010, 00100001 00100010, 00100100, 01000010 01000100, 01001000, 01001001 10000100, 10001000, 10001001 10010000, 10010001, 10010010

When $n=100$, we compute that $|f(4,100)|\approx 2^{43}$. When $n$ tends to
infinity, $f_{0}(4,n)$ has cardinality approximately $\rho^{n}$ where
$\rho=1.3247$ is the largest real root of the equation $x^{5}-x^{2}-x-1=0$.
Then $|f(4,n)|\approx 5\rho^{n}$.

Given some real $0<\epsilon<0.5$, [14] showed that there exists a linear-time
encoder ${\rm ENC}_{\epsilon}$ that encodes binary data to $\epsilon$-balanced
codewords of length $n$ with only one redundant bit. Next, we use $f(\ell,n)$
and the encoder ${\rm ENC}_{\epsilon}$ to construct a DNA code.

######  Theorem 1.

Let $\epsilon$ be a small real with $0<\epsilon<0.5$. Suppose $n,\ell$ are
positive integers with $n>(1/\epsilon^{2})\log_{e}n$ and $\ell\geq 3$. Given
the construction $f(\ell,n)$ and the $\epsilon$-balance encoder ${\rm
ENC}_{\epsilon}$, define the DNA code

$\displaystyle\mathcal{C}_{\ell,\epsilon}=\\{\tau^{-1}(\bm{c}||\bm{y}):\bm{c}\in
f(\ell,n),~{}\bm{y}=$ $\displaystyle{\rm ENC}_{\epsilon}(\bm{x}),$
$\displaystyle~{}{\rm with}~{}\bm{x}\in\mathbb{Z}_{2}^{n-1}\\}.$

######  Remark 2.

$\mathcal{C}_{\ell,\epsilon}\subseteq\sum_{\rm DNA}^{n}$ is 3-SSA, $\ell$-run-
length limited and GC-$\epsilon$-balanced. Moreover,
$\mathcal{C}_{\ell,\epsilon}$ has cardinality $2^{n-1}|f(\ell,n)|$ and rate
$\frac{n-1}{n}+\frac{1}{n}\log_{2}|f(\ell,n)|\approx 1+\log_{2}\rho$ when $n$
is sufficiently large, where $\rho$ is the largest real root of the equation
$x^{\ell+1}-\sum_{i=0}^{\ell-2}x^{i}=0$. Particularly, when
$\ell=4,\epsilon=0.1$, $\mathcal{C}_{4,0.1}$ has rate approximately
$1+\log_{2}\rho\approx 1.4057$.

###  IV-B Constrained codes with error correction

We modify the code $\mathcal{C}_{\ell,\epsilon}$ such that it can correct
errors.

Construction II. Given $\ell\geq 3$ and $0<\epsilon<0.5$, the code
construction includes the following two steps.

  * •

Extending step. Let
$\bm{y}=(y_{1},y_{2},\cdots,y_{n})\in\mathcal{C}_{\ell,\epsilon}$, where
$\mathcal{C}_{\ell,\epsilon}$ is given in Theorem 1. Set
$\bm{z}_{1}(\bm{y})={\rm TC}$ if $y_{1}\neq{\rm C}$, otherwise set
$\bm{z}_{1}(\bm{y})={\rm CT}$. Similarly, set $\bm{z}_{2}(\bm{y})={\rm TC}$ if
$y_{n}\neq{\rm T}$, otherwise set $\bm{z}_{2}(\bm{y})={\rm CT}$. Define
$S=\\{\bm{z}_{1}(\bm{y})\bm{y}\bm{z}_{2}(\bm{y}):\bm{y}\in\mathcal{C}_{\ell,\epsilon}\\}\subseteq\sum_{\rm
DNA}^{n+4}$.

  * •

Concatenation step. Let $q$ be a prime power with $q\leq|S|$, and $r$ be a
positive integer. Let ${\rm Ham}(r;q)$ be the $[t=\frac{q^{r}-1}{q-1},t-r,3]$
Hamming code over $\mathbb{F}_{q}$. Let $\pi$ be an injective map from
$\mathbb{F}_{q}$ to the set $S$, then

$\mathcal{C}_{e}=\\{(\pi(c_{1}),\pi(c_{2}),...,\pi(c_{t})):(c_{1},...,c_{t})\in{\rm
Ham}(r;q)\\}$

######  Theorem 2.

Denote $N=(n+4)t$. The code $\mathcal{C}_{e}\subseteq\sum_{\rm DNA}^{N}$ in
Construction II is $3$-SSA, $\ell$-run-length limited and
GC-$\epsilon$-balanced for some $\ell\geq 3$ and $0<\epsilon<0.5$, and can
correct one substitution error. Moreover, $\mathcal{C}_{e}$ has rate
$\frac{t}{N}(1-\frac{r}{t})\log_{2}q$. When $q$ is close to
$|S|=|\mathcal{C}_{\ell,\epsilon}|$, then it has rate approximately
$(1-\frac{r}{t})(1+\log_{2}\rho)$, where $\rho$ is the largest real root of
the equation $x^{\ell+1}-\sum_{i=0}^{\ell-2}x^{i}=0$.

###### Proof.

Let $(\pi(c_{1}),...,\pi(c_{t}))\in\mathcal{C}_{e}$ with some
$(c_{1},...,c_{t})\in{\rm Ham}(r;q)$. We first prove
$(\pi(c_{1}),...,\pi(c_{t}))$ is $3$-SSA, $\ell$-run-length limited and
GC-$\epsilon$-balanced. By the construction, $\pi(c_{i})\in S$ for $i\in[t]$.
Since every codeword $\bm{y}$ in $\mathcal{C}_{\ell,\epsilon}$ is
TC-$3$-dominant, $\ell$-run-length limited and GC-$\epsilon$-balanced, it is
easy to verify $\bm{z}_{1}(\bm{y})\bm{y}\bm{z}_{2}(\bm{y})\in S$ is also
TC-$3$-dominant, $\ell$-run-length limited and GC-$\epsilon$-balanced by the
definition of $\bm{z}_{1}(\bm{y}),\bm{z}_{2}(\bm{y})$, and the fact that
$\ell\geq 3$. Moreover, the concatenated codeword
$(\pi(c_{1}),...,\pi(c_{t}))$ still retains these properties. On the other
hand, it is easy to see that $\mathcal{C}_{e}$ has Hamming distance $\geq 3$,
thus can correct one substitution error. The code rate can be computed since
$|\mathcal{C}_{e}|=q^{t-r}$, where $t=\frac{q^{r}-1}{q-1}$. ∎

With a correspondence A $\rightarrow$ 0, T $\rightarrow$ 1, C $\rightarrow$ 2,
G $\rightarrow$ 3, one can map a DNA code $\mathcal{C}$ to an isomorphic code
over $\mathbb{Z}_{4}$, which we still call $\mathcal{C}$ if there is no
ambiguity on the alphabet. Next we show the existence of a DNA code that has
constraints in Section IV-A and can also correct one edit error.

Construction III. Suppose $\ell\geq 3$ and $0<\epsilon<0.5$. Let
$\mathcal{C}_{e}$ be constructed in Construction II and denote by $N=(n+4)t$
the code length of $\mathcal{C}_{e}$. For a pair
$(a,b)\in\mathbb{Z}_{N}\times\mathbb{Z}_{4}$, let

$\displaystyle\mathcal{C}_{a,b}=\mathcal{C}_{e}\cap\mathrm{T}_{a,b}(N;4)=\\{\bm{c}\in\mathcal{C}_{e}:$
$\displaystyle\mathrm{Syn}(\alpha(\bm{c}))\equiv a\ (\mathrm{mod}\ N);\
\sum_{i=1}^{N}c_{i}\equiv b\ (\mathrm{mod}\ 4)\\},$

then there exists some $(a_{0},b_{0})\in\mathbb{Z}_{N}\times\mathbb{Z}_{4}$
such that $|\mathcal{C}_{a_{0},b_{0}}|\geq\frac{|\mathcal{C}_{e}|}{4N}$ by the
Pigeon Hole principle. That is, there exists a DNA code
$\mathcal{C}_{a_{0},b_{0}}$ with code rate $R_{e}-\frac{2+\log_{2}N}{N}$,
where $R_{e}$ is the rate of $\mathcal{C}_{e}$.

Note that the DNA code given in Construction III is a subcode of both
$\mathcal{C}_{e}$ and a quaternary VT code, thus retains the constrained
property and error correcting property of both codes.

##  V GC-$(s,\delta)$-locally balanced codes

For an arbitrary $0<\delta<0.5$ and a positive integer $s$, we give a
construction of GC-$(s,\delta)$-locally balanced code. The code also possesses
3-SSA and $\ell$-run-length limited property, and can correct one edit error.
The idea is to establish a connection between GC-locally balanced codes and
GC-globally balanced codes through GC-partition balanced codes. Then we are
able to construct GC-locally balanced codes using the codes constructed in
previous sections.

######  Lemma 6.

Let $0<\epsilon<0.5$ be a small real, and $s_{0}\in\mathbb{N}$. Suppose
$\mathcal{C}$ is a GC-$\epsilon$-globally balanced code of length $s_{0}$,
then for any $t\in\mathbb{N}$, there exists a GC-$(s_{0},\epsilon)$-partition
balanced code $\mathcal{C^{\prime}}$ of length $ts_{0}$ with cardinality
$|\mathcal{C^{\prime}}|=|\mathcal{C}|^{t}$.

###### Proof.

The proof is obvious by constructing
$\mathcal{C^{\prime}}=\\{(\bm{c}_{1},\bm{c}_{2},...,\bm{c}_{t}):\bm{c}_{i}\in\mathcal{C},~{}i\in[t]\\}.$
∎

Lemma 6 gives a method converting GC-$\epsilon$-globally balanced codes to
GC-$(s_{0},\epsilon)$-partition balanced codes. Next we continue to give a
transformation from GC-$(s_{0},\epsilon)$-partition balanced codes to
GC-$(s,\delta)$-locally balanced codes.

######  Lemma 7.

Let $0<\epsilon<0.5$ be a small real, and $n,s,s_{0}\in\mathbb{N}$ with
$s_{0}\mid n$ and $n\geq s>2s_{0}$. If $\mathcal{C}$ is a
GC-$(s_{0},\epsilon)$-partition balanced code of length $n$, then
$\mathcal{C}$ is also
GC-$(s,\delta=\frac{(s_{0}-1)(1-2\epsilon)}{s}+\epsilon)$-locally balanced.

###### Proof.

It is sufficient to prove that every codeword in $\mathcal{C}$ is
GC-$(s,\delta)$-locally balanced. Let
$\bm{c}=(c_{1},c_{2},...,c_{n})\in\mathcal{C}$, denote
$\bm{c}=(\bm{c}^{(1)},\bm{c}^{(2)},...,\bm{c}^{(\frac{n}{s_{0}})})$, where
$\bm{c}^{(i)}=(c_{(i-1)s_{0}+1},...,c_{is_{0}})$ for $i\in[\frac{n}{s_{0}}]$.
We call $\bm{c}^{(i)}$ the $i$-th partition of $\bm{c}$, $\forall
i\in[\frac{n}{s_{0}}]$. Since $\bm{c}$ is GC-$(s_{0},\epsilon)$-partition
balanced, it has for each $i\in[\frac{n}{s_{0}}]$,
$(0.5-\epsilon)s_{0}\leq\mathrm{wt}_{\mathrm{GC}}(\bm{c}^{(i)})\leq(0.5+\epsilon)s_{0}$.
Next we prove every length-$s$ substring of $\bm{c}$ is GC-$\delta$-globally
balanced so that $\bm{c}$ is GC-$(s,\delta)$-locally balanced.

For any $j\in[n-s+1]$, consider the length-$s$ substring
$\bm{c}_{j}=(c_{j},c_{j+1},...,c_{j+s-1})$ of $\bm{c}$. Since $s>2s_{0}$, then
$\bm{c}_{j}$ must cover at least one complete partition $\bm{c}^{(i)}$ of
$\bm{c}$ for some $i\in[\frac{n}{s_{0}}]$. Suppose $\bm{c}_{j}$ covers in
total $t\geq 1$ consecutive complete partitions
$\bm{c}^{(i)},...,\bm{c}^{(i+t-1)}$, then we can write
$\bm{c}_{j}=(\underline{\bm{c}^{(i-1)}},\bm{c}^{(i)},...,\bm{c}^{(i+t-1)},\underline{\bm{c}^{(i+t)}})$,
where $\underline{\bm{c}^{(i-1)}}$ is a substring of the partition
$\bm{c}^{(i-1)}$ of length $a\in[0,s_{0})$ and $\underline{\bm{c}^{(i+t)}}$ is
a substring of $\bm{c}^{(i+t)}$ of length $b\in[0,s_{0})$. Moreover, we have
$m=a+ts_{0}+b$. Then the GC-weight of $\bm{c}_{j}$ satisfies

$(0.5-\epsilon)ts_{0}\leq\mathrm{wt}_{\mathrm{GC}}(\bm{c}_{j})\leq(0.5+\epsilon)ts_{0}+a+b.$
(2)

Since $a,b\in[0,s_{0})$, it has $a+b\leq 2(s_{0}-1)$ and $ts_{0}=s-(a+b)\geq
s-2(s_{0}-1)$. The inequality (2) can be rewritten as follows.

$(0.5-\epsilon)(s-2(s_{0}-1))\leq\mathrm{wt}_{\mathrm{GC}}(\bm{c}_{j})\leq(0.5+\epsilon)s+(1-2\epsilon)(s_{0}-1).$

Then $\bm{c}_{j}$ is GC-$\delta$-globally balanced, if the following
conditions hold:

$\begin{cases}(0.5-\epsilon)(s-2(s_{0}-1))\geq(0.5-\delta)s,\\\
(0.5+\epsilon)s+(1-2\epsilon)(s_{0}-1)\leq(0.5+\delta)s.\end{cases}$

which gives $\delta\geq\frac{(s_{0}-1)(1-2\epsilon)}{s}+\epsilon$. This
completes the proof. ∎

According to Lemma 6 and Lemma 7, we can give a code construction that is GC-
locally balanced as follows.

Construction IV. Let $\ell\geq 3$ be a positive integer and $0<\epsilon<0.5$
be a small real. Suppose $s,s_{0},t$ are positive integers with $ts_{0}\geq
s>2s_{0}$. Let $\mathcal{C}_{e}\subseteq\mathbb{Z}_{4}^{s_{0}}$ be the code
constructed through Construction II in Section IV-B. Then $\mathcal{C}_{e}$
can be transformed to a
GC-$(s,\delta=\frac{(s_{0}-1)(1-2\epsilon)}{s}+\epsilon)$-locally balanced
code $\mathcal{C}_{\mathrm{local}}\subseteq\mathbb{Z}_{4}^{ts_{0}}$, using the
method in Lemma 6 and Lemma 7. Denote $N=ts_{0}$, and for a pair
$(a,b)\in\mathbb{Z}_{N}\times\mathbb{Z}_{4}$, let

$\displaystyle\mathcal{C}_{a,b}=\mathcal{C}_{\mathrm{local}}\cap\mathrm{T}_{a,b}(N;4)=\\{\bm{c}\in\mathcal{C}_{\mathrm{local}}:$
$\displaystyle\mathrm{Syn}(\alpha(\bm{c}))\equiv a\ (\mathrm{mod}\ N);\
\sum_{i=1}^{N}c_{i}\equiv b\ (\mathrm{mod}\ 4)\\},$

then there exists some $(a_{0},b_{0})\in\mathbb{Z}_{N}\times\mathbb{Z}_{4}$
such that
$|\mathcal{C}_{a_{0},b_{0}}|\geq\frac{|\mathcal{C}_{\mathrm{local}}|}{4N}$ by
the pigeonhole principle. Define the DNA code to be
$\mathcal{C}_{a_{0},b_{0}}$.

Recall that $\mathcal{C}_{e}$ is a concatenated code with 3-SSA, $\ell$-run-
length limited and GC-$\epsilon$-globally balanced property. $\mathcal{C}_{e}$
has Hamming distance at least 3. Then $\mathcal{C}_{\mathrm{local}}$ is also
3-SSA, $\ell$-run-length limited, and
GC-$(s,\delta=\frac{(s_{0}-1)(1-2\epsilon)}{s}+\epsilon)$-locally balanced. It
is easy to verify $\mathcal{C}_{\mathrm{local}}$ also has Hamming distance at
least 3. Thus the DNA code $\mathcal{C}_{a_{0},b_{0}}$ satisfies these
constraints and can correct one edit error. Moreover,
$\mathcal{C}_{a_{0},b_{0}}$ has code rate
$\frac{\log_{2}(|\mathcal{C}_{e}|^{t}/4ts_{0})}{ts_{0}}=R_{e}-\frac{2+\log_{2}N}{N}$,
where $R_{e}$ is the rate of $\mathcal{C}_{e}$.

######  Remark 3.

Note that codes in [5] are GC-$\epsilon$-partition balanced and can correct
single edits in each segment with a high rate $2(1-\log_{2}s/s)$, where the
segment length $s=\Omega(\log N)$. In our code, we allow $s$ to vary flexibly
with $N$ and ensure local GC balance in each consecutive subsequence of length
$s$, and also satisfy the 3-SSA and run-length limit constraint.

It’s worth noting that our method in constructing
$\mathcal{C}_{\ell,\epsilon}$ can adapt to binary encoders of [14, 17] to
directly enforce local GC-content constraint. However, it is not necessarily
locally balanced after a straightforward concatenation.

## References

  * [1] K. G. Benerjee and A. Banerjee, “On DNA codes with multiple constraints”, IEEE Commun. Lett., vol. 25, no. 2, pp. 365-368, 2021.
  * [2] K. G. Benerjee and A. Banerjee, “On homopolymers and secondary structures avoiding, reversible, reversible-complement and GC-balanced DNA codes”, IEEE Int. Symp. Inf. Theory (ISIT), 2022, pp. 204-209.
  * [3] K. Cai et al., “Correcting a single indel/edit for DNA-based data storage: linear-time encoders and order-optimality”, IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 3438-3451, 2021.
  * [4] H. Chu, C. Wang, Y. Zhang, “Improved constructions of secondary structure avoidance codes for DNA sequences”, arxiv:2304.11403, 2023.
  * [5] K. Cai, H. M. Kiah, M. Motani and T. T. Nguyen, “Coding for segmented edits with local weight constraints”, IEEE Int. Symp. Inf. Theory (ISIT), 2021, pp. 1694-1699.
  * [6] N. Goldman, P. Bertone, S.Chen et al., “Towards practical, high-capacity, low-maintenance information storage in synthesized DNA”, Nature, vol. 494, no. 7435, pp. 77-80, Feb. 2013.
  * [7] R. Gabrys, H. M. Kiah, A. Vardy et al., “Locally balanced constraints,” IEEE Int. Symp. Inf. Theory (ISIT), Los Angeles, CA, USA, Jun. 2020.
  * [8] K. A. S. Immink and K. Cai, “Properties and constructions of constrained codes for DNA-based data storage”, IEEE Access, vol. 8, pp. 49523-49531, 2020.
  * [9] N. Kumar, S. Siddhiprada Bhoi, A. Kumar Singh, “A study of primer design with $w$-constacyclic shift over $\mathbb{F}_{4}$”, TheoreticalComputer Science, vol. 960, no. C, 2023.
  * [10] Y. Liu, X. He and X. Tang, “Capacity-achieving constrained codes with GC-content and runlength limits for DNA storage”, IEEE Int. Symp. Inf. Theory (ISIT), Espoo, Finland, 2022, pp. 198-203.
  * [11] A. Marathe, A. E. Condon, and R. M. Corn, “On combinatorial DNA word design”, J. Comput. Biol., vol. 8, no. 3, pp. 201-219, Jul. 2004.
  * [12] T. T. Nguyen, K. Cai, K. A. S. Immink and H. M. Kiah, “Capacity-approaching constrained codes with error correction for DNA-based data storage”, IEEE Trans. Inf. Theory, vol. 67, no. 8, pp. 5602-5613, 2021.
  * [13] T. T. Nguyen, K. Cai, H. M. Kiah, D. T. Dao, and K. A. S. Immink, “On the design of codes for DNA computing: secondary structure avoidance codes”, arxiv:2302.13714, 2023.
  * [14] T. T. Nguyen, K. Cai, and K. A. S. Immink, “Binary subblock energy-constrained codes: Knuth’s balancing and sequence replacement techniques”, IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2020, pp. 37-41.
  * [15] W. Song, K. Cai, M. Zhang, and C. Yuen,“Codes with run-length and GC-content constraints for DNA-based data storage,” IEEE Commun. Lett., vol. 22, no. 10, pp. 2004-2007, Oct. 2018.
  * [16] G. Tenengolts, “Nonbinary codes, correcting single deletion or insertion”, IEEE Trans. Inf. Theory, vol. 30, no. 5, pp. 766-769, Sep. 1984.
  * [17] C. Wang, Z. Lu, Z. Lan et al., “Coding schemes for locally balanced constraints”, IEEE Int. Symp. Inf. Theory (ISIT), July, 2022.
  * [18] Y. Wang, M. Noor-A-Rahim, E. Gunawan et al., “Construction of bio-constrained code for DNA data storage”, IEEE Commun. Lett., vol. 23, no. 6, pp. 963-966, Jun. 2019.
  * [19] J. H. Weber, J. A. M. De Groot, and C. J. Van Leeuwen, “On single-error-detecting codes for dna-based data storage”, IEEE Commun. Lett., vol. 25, no. 1, pp. 41-44, Jan. 2021.


Subfigures (a)-(b) show the FID and IS against communication rounds of WGAN
trained over MNIST dataset under different Dirichlet distribution.}}}
\@add@centering\end{figure*} \par{\bf Implementation details.}\ Experiments
are conducted on the MNIST datasets of digits from $0$ to $9$, with $60000$
training images of size $28\times 28$. We adopt the same network architecture
of WGAN as that of DCGAN
\cite[cite]{[\@@bibref{Number}{arjovsky2017wasserstein}{}{}]}. We simulate
$M=4$ parallel workers and run ${\operatorname*{{LocalAdaSEG}}}$ with the
batch size $128$ and local iteration steps $K=500$. In the homogeneous
setting, the local data in each worker is uniformly sampled from the entire
dataset. In the heterogeneous setting, we partition the MNIST dataset into $4$
subsets using the partition methods in
\cite[cite]{[\@@bibref{Number}{lin2019don}{}{}]}. Then each worker is loaded
with a fraction of the dataset. Due to non-adaptive learning rates, LocalSGDA,
LocalSEGDA, and MB-SEGDA are hard to tune and do not achieve satisfactory
performance for training WGAN. For a better illustration, we only show the
performance of ${\operatorname*{{LocalAdaSEG}}}$, MB-UMP, MB-ASMP and Local
Adam. To measure the efficacy of the compared optimizers, we plot FID and IS
\cite[cite]{[\@@bibref{Number}{heusel2017gans}{}{}]} against the number of
iterations and communications, respectively. \par\par\par To investigate the
convergence rate of ${\operatorname*{{LocalAdaSEG}}}$ under different data
distributions, we conduct to train WGAN over MNIST dataset with different
Dirichlet distributions. In
\lx@cref{creftype~refnum}{fig:wgan_under_diff_dist}, it shows the FID and IS
of training the WGAN under the Dirichlet distribution with various parameters
$\alpha\in\\{0.1,0.3,0.6,0.9\\}$. It should be noted that when $\alpha$
increases, the data distribution trends closer to the homogeneous setting. As
can be seen from \lx@cref{creftype~refnum}{fig:wgan_under_diff_dist}, it
converges faster when the parameter $\alpha$ decreases. \par Furthermore, we
also compare ${\operatorname*{{LocalAdaSEG}}}$ with other existing optimizers
under various Dirichlet distributions which parameter
$\alpha\in\\{0.1,0.3\\}$, respectively. As can be seen from
\lx@cref{creftype~refnum}{fig:compare_wgan_under_diff_dist}, our proposed
LocalAdaSEG also achieves a faster convergence compared with exiting minimax
optimizers. \par\par\par\begin{figure*}[tp]
\centering\centering\par\begin{@subfigure}
\includegraphics[width=195.12767pt]{mnist_alpha01_FID}\end{@subfigure}
\begin{@subfigure}
\includegraphics[width=195.12767pt]{mnist_alpha01_IS}\end{@subfigure}
\par\begin{@subfigure}
\includegraphics[width=195.12767pt]{mnist_alpha03_FID}\end{@subfigure}
\begin{@subfigure}
\includegraphics[width=195.12767pt]{mnist_alpha03_IS}\end{@subfigure}
\par\@@toccaption{{\lx@tag[ ]{{9}}{\small Subfigures (a)-(b) show the FID and
IS against communication rounds of WGAN trained over MNIST dataset with
$\alpha=0.1$; (c)-(d) show the FID and IS against communication rounds of WGAN
trained over MNIST dataset with $\alpha=0.3$.}}}\@@caption{{\lx@tag[:
]{{Figure 9}}{\small Subfigures (a)-(b) show the FID and IS against
communication rounds of WGAN trained over MNIST dataset with $\alpha=0.1$;
(c)-(d) show the FID and IS against communication rounds of WGAN trained over
MNIST dataset with $\alpha=0.3$.}}}
\@add@centering\@add@centering\end{figure*}
\par\par\par\par\@@numbered@section{subsection}{toc}{BigGAN on CIFAR10}
\par{BigGAN.} Although a variety of GANs were investigated to effectively
generate images, they are still restricted to small image synthesis and the
training process remains dependent on augmentations and hyperparameters.
BigGAN is a typical network to pull together a suite of recent best practices
in training class-conditional images and scaling up the batch size and number
of model parameters. The result is the routine generation of both high-
resolution and high-fidelity natural images. Since utilizing the self-
attention module and skip connections, BigGAN can not be simply considered as
a sequential combination of layers. Here, we only describe the key module in
the BigGAN. Specifically, the generator consists of $1$ linear layer, $N$
generator blocks, and $1$ sequential layer. Each generator block can be
represented as several layers \emph{\\{BN, ReLU, SNConv, BN, ReLU, SNConv,
SNConv\\}}, where \emph{SNConv} denotes 2d convolutional layer with the
spectral norm. Similarly, The discriminator also consists of linear layers and
discriminator blocks. Each discriminator block can be listed as several layers
\emph{\\{ReLU, AvgPool, SNConv, SNConv, SNConv\\}}, where \emph{AvgPool}
denotes the average pooling. \par{CIFAR10.} The CIFAR-10 dataset consists of
60000 32x32 color images in 10 classes, with 6000 images per class. There are
50000 training images and 10000 test images. The test batch contains exactly
1000 randomly-selected images from each class. The training batches contain
the remaining images in random order, but some training batches may contain
more images from one class than another. Between them, the training batches
contain exactly 5000 images from each class. \par{Parameter Setup.} We
implement the BigGAN with the original CIFAR10 dataset, meaning that all the
images are fed into the BigGAN without cropping and rotation. The experiments
are conducted among $M=4$ parallel workers in a heterogeneous setting. It
implies that all the training images are divided into $4$ parts by using
Dirichlet distribution with parameter $\alpha=0.6$. Each work runs the
${\operatorname*{{LocalAdaSEG}}}$ with the batch size $bs=125$ and local
iteration steps $K=100$. The input noise dimension is $125$, and the channel
of the generator block and discriminator is set to $16$. To show the
performance of ${\operatorname*{{LocalAdaSEG}}}$, MB-UMP, MB-ASMP, and Local
Adam, We plot FID and IS against the communication rounds in the
\lx@cref{creftype~refnum}{fig:bigGAN_FID_IS}.
\par\par\par\lx@cref{creftype~refnum}{fig:bigGAN_FID_IS} illustrates the FID
and IS score of BigGAN over the CIFAR10 dataset. As can be seen that
${\operatorname*{{LocalAdaSEG}}}$ and Local Adam converge faster than other
optimizers. \par\begin{figure*}[tp] \centering\par\begin{@subfigure}
\includegraphics[width=195.12767pt]{BigGAN_NIID06_FID}\end{@subfigure}
\begin{@subfigure}
\includegraphics[width=195.12767pt]{BigGAN_NIID06_IS}\end{@subfigure}
\par\@@toccaption{{\lx@tag[ ]{{10}}{\small Subfigures (a)-(b) show the FID and
IS against communication rounds of BigGAN over the CIFAR10
dataset.}}}\@@caption{{\lx@tag[: ]{{Figure 10}}{\small Subfigures (a)-(b) show
the FID and IS against communication rounds of BigGAN over the CIFAR10
dataset.}}} \@add@centering\end{figure*} \par\par\lx@pp@appendix@end
\par\@add@PDF@RDFa@triples\par\end{document}$