# Coding for Synthesis Defects

Ziyang Lu  Han Mao Kiah  Yiwei Zhang  Robert N. Grass  and Eitan Yaakobi
Ziyang Lu and Yiwei Zhang are with Key Laboratory of Cryptologic Technology
and Information Security of Ministry of Education, School of Cyber Science and
Technology, Shandong University, Qingdao, Shandong, 266237, China (e-mail:
<EMAIL_ADDRESS>ywzhang@sdu.edu.cn).Han Mao Kiah is with the School of
Physical and Mathematical Sciences, Nanyang Technological University,
Singapore (e-mail: hmkiah@ntu.edu.sg)Robert N. Grass is with the Department of
Chemistry and Applied Biosciences, ETH Zürich, Vladimir-Prelog-Weg 1-5, 8093
Zürich, Switzerland (e-mail: robert.grass@chem.ethz.ch)Eitan Yaakobi is with
the Department of Computer Science, Technion - Israel Institute of Technology,
Haifa 3200003, Israel (e-mail<EMAIL_ADDRESS>
###### Abstract

Motivated by DNA based data storage system, we investigate the errors that
occur when synthesizing DNA strands in parallel, where each strand is appended
one nucleotide at a time by the machine according to a template supersequence.
If there is a cycle such that the machine fails, then the strands meant to be
appended at this cycle will not be appended, and we refer to this as a
_synthesis defect_. In this paper, we present two families of codes correcting
synthesis defects, which are _$t$ -known-synthesis-defect correcting codes_
and _$t$ -synthesis-defect correcting codes_. For the first one, it is assumed
that the defective cycles are known, and each of the codeword is a quaternary
sequence. We provide constructions for this family of codes for $t=1,2$, with
redundancy $\log 4$ and $\log n+18\log 3$, respectively. For the second one,
the codeword is a set of $M$ ordered sequences, and we give constructions for
$t=1,2$ to show a strategy for constructing this family of codes. Finally, we
derive a lower bound on the redundancy for single-known-synthesis-defect
correcting codes, which assures that our construction is almost optimal.

##  I Introduction

Storing digital information on synthetic DNA strands has attracted significant
interest due to its potential for information storage, particularly its
durability and high storage density (see [1, 2] and references therein). The
storage process involves converting binary digital information into quaternary
strings (nucleotide bases) and writing these onto DNA strands using a
synthesis machine.

While numerous experiments demonstrated the feasibility of DNA storage (see
Table 1.1 in [2] for a recent survey), practical implementation for large-
scale data remains challenging primarily due to its high cost. Specifically,
DNA synthesis stands out as the most costly component in the storage model
(see [3] for a discussion on synthesis procedures). Therefore, understanding
the synthesis process is essential to enhance efficiency and reduce costs.

To minimize errors during the synthesis process, DNA strands typically contain
no more than 250 nucleotides. Consequently, the user split the encoded
quaternary strings into multiple short sequences for synthesis, storing them
in an unordered manner. Synthesis of these multiple strands is typically
array-based or performed in parallel (see for example, [3, Fig. 6]).

In this process, the synthesis machine scans a fixed template DNA sequence and
appends one nucleotide at a time according to this template supersequence.
Each synthesis cycle involves appending a nucleotide to a subset of DNA
strands requiring that specific nucleotide. Therefore, all synthesized DNA
strands must be subsequences of the fixed template supersequence. The length
of the fixed supersequence dictates the number of cycles needed for strand
generation, thereby influencing the total synthesis time. Minimizing the total
synthesis time is essential for reducing the overall cost of DNA synthesis, as
each cycle requires reagents and chemicals [4]. This results in an interesting
constrained coding problem that was initiated by Lenz et al. [5] and
subsequently studied in [6, 7, 8, 9, 10].

In this paper, we introduce a new error model that arises during this
synthesis process [11].

Specifically, if the synthesis machine fails to append a nucleotide at a
certain cycle, then we refer to this error event as a synthesis defect (see
Definition 1 for a formal definition). While synthesis defects share certain
similarities to deletions, our primary contribution in this study is to
demonstrate that by leveraging certain side information, we can dramatically
reduce the redundancy of the coding scheme. Our results are distinguished
between two scenarios: one where the defective cycles are known, and another
where the defective cycles are unknown. In the first case, we construct codes
that correct one and two synthesis defects using $\log 4$ and $\log n+O(1)$
redundant bits, respectively, where $n$ denotes the codeword length. In
contrast, if we employ a single and a two-deletion-correcting code, we require
at least $\log n$ and $2\log n$ redundant bits, respectively. Also, in this
case where the defects are known and $t=1$, we provide a matching lower bound
for the redundancy. For the second case, where the defective cycles are not
known, we consider the task of synthesizing $M$ length-$n$ words. Here, we
construct codes that correct one and two synthesis defects using roughly
$\lambda_{1}(\log n)^{2}+M\log\log n$ and $\lambda_{2}(\log n)^{2}+2M\log n$
redundant bits, respectively, for some constants $\lambda_{1}$ and
$\lambda_{2}$.

##  II Problem Formulation

Throughout this paper, we use $\Sigma=\\{1,2,3,4\\}$ to denote DNA alphabet of
size four and consider the shifted modulo operator so that $(a\bmod 4)$ always
belongs to $\Sigma$. For an integer $T$, we use $[T]$ to denote the set
$\\{1,2,\ldots,T\\}$. For a length-$n$ sequence ${\boldsymbol{x}}$, its $i$th
symbol is denoted as $x_{i}$, and we use $x_{1}x_{2}\ldots x_{n}$ or
$(x_{1},x_{2},\ldots,x_{n})$ to represent it. Denote
${\boldsymbol{x}}_{I}=x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$ as a subsequence of
${\boldsymbol{x}}$ indexed by $I$, where
$I=\\{i_{1},i_{2},\ldots,i_{k}\\}\subseteq[n]$ is a set of indices of size
$k$.

Consider synthesizing a quaternary sequence ${\boldsymbol{x}}=x_{1}x_{2}\ldots
x_{n}\in\Sigma^{n}$. In this paper, we consider the template sequence
$12341234\cdots$ and appends one nucleotide according to this sequence in each
cycle. Thus, in almost all cases, more than $n$ synthesis cycles are required
as we need to wait for the synthesis machine to append the corresponding
nucleotide.

Now, to determine the number of cycles, we perform the following computation.
First, we define the difference sequence of ${\boldsymbol{x}}$ to be ${\rm
Diff}({\boldsymbol{x}})=(x_{1},x_{2}-x_{1}\bmod 4,\ldots,x_{n}-x_{n-1}\bmod
4$). Note that the map ${\rm Diff}:\Sigma^{n}\rightarrow\Sigma^{n}$ is a one-
to-one mapping and hence it is invertible.

Next, we use $\mathsf{cycle}({\boldsymbol{x}})\in[4n]^{n}$ to denote the
synthesis cycle sequence of ${\boldsymbol{x}}$. Here, for $1\leq i\leq n$, the
$i$th symbol of ${\boldsymbol{x}}$ will be synthesized in the cycle given by
$\mathsf{cycle}({\boldsymbol{x}})_{i}=\sum_{j=1}^{i}{\rm
Diff}({\boldsymbol{x}})_{j}$. For example, if ${\boldsymbol{x}}=1241321$, then
${\rm Diff}({\boldsymbol{x}})=1121233$ and
$\mathsf{cycle}({\boldsymbol{x}})=(1,2,4,5,7,10,13)$. Observe that the
elements of $\mathsf{cycle}({\boldsymbol{x}})$ are necessarily monotonically
increasing. Hence, by a slight abuse of notation, we treat
$\mathsf{cycle}({\boldsymbol{x}})$ both as a set and as a sequence.
Specifically, sometimes, we write $\Delta\cap\mathsf{cycle}({\boldsymbol{x}})$
to mean $\Delta\cap\\{\mathsf{cycle}({\boldsymbol{x}})_{i}\\}_{i=1}^{n}$.

Finally, for a subset of synthesis cycles $\Delta\subseteq[4n]$, we let
$I({\boldsymbol{x}},\Delta)=\\{i\in[n]:\mathsf{cycle}({\boldsymbol{x}})_{i}\in\Delta\\}$
represent the indices of ${\boldsymbol{x}}$ whose synthesis cycles belong to
$\Delta$. Then, we define
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})\triangleq{\boldsymbol{x}}_{[n]\setminus
I({\boldsymbol{x}},\Delta)}$ to be the sequence obtained by deleting the
symbols whose synthesis cycles belong to $\Delta$. Let us continue our example
with ${\boldsymbol{x}}=1241321$. When $\Delta=\\{12,13\\}$, then
$I({\boldsymbol{x}},\Delta)=\\{7\\}$ and
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})=124132$.

###  II-A Problem Formulation

In this paper, we consider the scenario where a set of DNA strands is
synthesized in parallel. Similar to before, in every cycle, the machine
appends the corresponding nucleotide to the strands that need it. However, if
the machine does not append a nucleotide at cycle $i$, then we say that a
synthesis defect occurs at cycle $i$. Formally, we have the following
definition.

######  Definition 1.

Suppose that
$\mathsf{C}=({\boldsymbol{c}}_{1},{\boldsymbol{c}}_{2},\ldots,{\boldsymbol{c}}_{M})\in(\Sigma^{n})^{M}$.
For $\Delta\subseteq[4n]$, we say that $\mathsf{C}$ suffers from synthesis
defects at the cycles in $\Delta$ if for $i\in[M]$, the symbols of
${\boldsymbol{c}}_{i}$ synthesized at cycles $\Delta$ are deleted and results
in $\mathsf{SynDef}_{{\Delta}}({\boldsymbol{c}}_{i})$. Therefore, we define
$\mathsf{SynDef}_{\Delta}(\mathsf{C})\triangleq(\mathsf{SynDef}_{{\Delta}}({\boldsymbol{c}}_{1}),\ldots,\mathsf{SynDef}_{{\Delta}}({\boldsymbol{c}}_{M}))$.

For simplicity, we assume the strands are ordered and so, the identities of
the strands are known to both the sender and receiver. In practice, this means
that the strands are assigned unique indices and we assume that the indices
are received error-free.

######  Example 1.

Let $M=3$ and $n=5$. Consider the set of strands
$\mathsf{C}=({\boldsymbol{c}}_{1},{\boldsymbol{c}}_{2},{\boldsymbol{c}}_{3})$,
where

$\displaystyle{\boldsymbol{c}}_{1}$ $\displaystyle=31411$
$\displaystyle(~{}\mathsf{cycle}({\boldsymbol{c}}_{1})$
$\displaystyle=(3,5,8,9,13)~{}),$ $\displaystyle{\boldsymbol{c}}_{2}$
$\displaystyle=12213$ $\displaystyle(~{}\mathsf{cycle}({\boldsymbol{c}}_{2})$
$\displaystyle=(1,2,6,9,11)~{}),$ $\displaystyle{\boldsymbol{c}}_{3}$
$\displaystyle=14131$ $\displaystyle(~{}\mathsf{cycle}({\boldsymbol{c}}_{3})$
$\displaystyle=(1,4,5,7,9)~{})\,.$

When $\Delta=\\{1\\}$, we have that

$\mathsf{SynDef}_{\Delta}(\mathsf{C})=(31411,2213,4131)\,.$

On the other hand, when $\Delta=\\{10\\}$ or $\Delta=\\{12\\}$, we have

$\mathsf{SynDef}_{\Delta}(\mathsf{C})=(31411,12213,14131)\,.$

Observe that when synthesis defects occur in a set of strands, not all strands
are erroneous. However, those strands with symbols synthesized during
corresponding cycles will be deleted at those cycles. Furthermore, as
illustrated in this example, it is possible that
$\mathsf{SynDef}_{\Delta}(\mathsf{C})=\mathsf{C}$ and this poses an
interesting coding challenge. $\blacksquare$

Our goal in this paper is to study codes correcting synthesis defects. We
distinguish between two cases: one where we know the defective cycles; another
where the locations of defects are unknown.

Case I. In the first case, even if we know the set of defective cycles, that
is $\Delta$, it is possible that we cannot infer the erroneous positions from
$\mathsf{SynDef}_{\Delta}(\mathsf{C})$.

Let us explain using the following example.

######  Example 2.

Let $M=3$ and $n=5$. Consider the set of strands

$\mathsf{C}=(12341,12134,21231).$

When $\Delta=\\{5\\}$, we have that

$\mathsf{SynDef}_{\\{5\\}}(\mathsf{C})=(1234,1234,2231).$

Now we want to recover $\mathsf{C}$ from
$\mathsf{SynDef}_{\\{5\\}}(\mathsf{C})$ knowing that $\Delta=\\{5\\}$. For the
strand $2231$, we insert a $1$ at the fifth cycle, and we get $21231$. This
turns out to be the only option. But for the strand $1234$, there are four
possible positions to insert $1$ at the fifth cycle, which result in
$11234,12134,12314,12341$. Therefore we cannot uniquely recover $\mathsf{C}$
even if we know the locations of the defects. Furthermore, the erroneous
positions corresponding to $1234$ are 2, 3, 4, and 5. Hence, coding for
erasures is insufficient. $\blacksquare$

The above example gives rise to the following problem: how to recover
$\mathsf{C}$ with the knowledge of locations of defects? In our study of this
problem, it is enough to investigate the case where $M=1$. In other words, we
design codes for a single-strand. This is because in solving the single-strand
case, we obtain sufficient information, including the approximate deleted
locations and the values of the deleted symbols, and other strands in the set
cannot provide more information about the errors.

Hence, a $t$-known-synthesis-defect correcting code allows one to uniquely
recover a synthesized word, in the presence of $t$ synthesis defects when the
locations of defects are known.

######  Definition 2.

We say a code $\mathcal{C}\subseteq\Sigma^{n}$ is a $t$-known-synthesis-defect
correcting code ($t$-KDCC) if for every pair of distinct codewords,
${\boldsymbol{c}}_{1},{\boldsymbol{c}}_{2}\in\mathcal{C}$, and for any
$\Delta\subseteq[4n]$ with $|\Delta|=t$, we have that

$\mathsf{SynDef}_{\Delta}({\boldsymbol{c}}_{1})\neq\mathsf{SynDef}_{\Delta}({\boldsymbol{c}}_{2}).$

Case II. On the other hand, when we do not know the locations of the defects,
coding for a single strand is almost equivalent to coding for deletions.
Hence, we consider $M>1$. When the locations of the defects are unknown, we
can simply employ a deletion-correcting code for each strand. However, this
incurs a high redundancy and hence, our goal is to reduce this redundancy.

Consider Example 1 and the case where $\Delta=\\{1\\}$. Suppose
${\boldsymbol{c}}_{2}=12213$ is obtained from a single-deletion-correcting
code. Then when we receive $2213$, we are able to recover
${\boldsymbol{c}}_{2}$ and also determine $\Delta=\\{1\\}$. Then we are able
to use this information on $\Delta$ to correct the other strings. Therefore,
when the location of defects are unknown, our strategy is to divide the $M>1$
strands into two parts and employ two different coding schemes. The first
coding scheme not only allows us to correct the defects, but also provide
approximate locations of the defects. This then allows us to employ a second
coding scheme that incurs less redundancy and we describe this in detail in
Section IV. Here, we formally define a $t$-synthesis-defect correcting code.

######  Definition 3.

For a set of sequences
$\mathsf{C}=({\boldsymbol{c}}_{1},{\boldsymbol{c}}_{2},\ldots,{\boldsymbol{c}}_{M})\in(\Sigma^{n})^{M}$,
and $d\in[n]$, we define the synthesis defect ball of radius $d$ of
$\mathsf{C}$ to be the set

$\mathsf{Ball}^{\mathsf{SynDef}}_{d}(\mathsf{C})=\\{\mathsf{SynDef}_{\Delta}(\mathsf{C}):\Delta\subseteq[4n],|\Delta|\leq
d\\}.$

######  Definition 4.

A code $\mathcal{C}\subseteq(\Sigma^{n})^{M}$ is a $t$-synthesis-defect
correcting code ($t$-SDCC) if for every pair of distinct
$\mathsf{C}_{1},\mathsf{C}_{2}\in\mathcal{C}$, we have

$\mathsf{Ball}^{\mathsf{SynDef}}_{t}(\mathsf{C}_{1})\cap\mathsf{Ball}^{\mathsf{SynDef}}_{t}(\mathsf{C}_{2})=\varnothing.$

In this paper, we provide designs for these two classes of codes. We use
redundancy to evaluate a code. Specifically, we define the redundancy of a
code $\mathcal{C}\subseteq(\Sigma^{n})^{M}$ to be $2Mn-\log|\mathcal{C}|$.

###  II-B Organization

In Section III, we construct $t$-KDCCs for $t=1,2$ with redundancy $\log 4$
and $\log n+18\log 3$ respectively. Specifically, we achieve this by
constructing binary code capable of correcting $t$ deletions where each
deletion is within a small window. When the window is large, this will be an
important material for constructing SDCC. In Section IV, we first show that
using $O(\log n)$ strands is enough to cover all the $4n$ cycles. Then, by
giving single-SDCC and $2$-SDCC we show our idea for constructing $t$-SDCCs.
In Section V, we provide the lower bounds for redundancy on $1$-KDCCs, which
is at least $\log 4-o(1)$ bits of redundancy. Last, we conclude and present
some future work in Section VI.

##  III Constructions of Known-Synthesis-Defect Correcting Codes

In this section, we provide constructions of $t$-KDCCs for $t=1,2$. We show
that knowing the locations of the defects helps us narrow each of the location
of deletion into a small interval of constant length. Then, we can correct
these deletions by using binary bounded-deletion-correcting codes [12].

######  Definition 5.

For ${\boldsymbol{P}}=(P_{1},P_{2},\ldots,P_{t})\in\mathbf{Z}^{t}$ we call a
code ${\boldsymbol{P}}$-bounded $t$-deletion correcting code if it can correct
$t$ deletions where the $t$ deletions are located at $t$ given intervals of
length $P_{1},P_{2},\ldots,P_{t}$, respectively. Furthermore, we let
$P\triangleq\max\\{P_{1},\ldots,P_{t}\\}$ denote the maximum $P_{i}$ for
$1\leq i\leq t$.

Our main contribution in this section is to construct
${\boldsymbol{P}}$-bounded $t$-deletion correcting codes with different ranges
of $P$ for $t=1,2$. Before that, let us introduce a serial of useful lemmas to
show that the knowledge of defective cycles narrows down the locations of
resulting deletions.

######  Definition 6.

For $\Delta\subseteq[4n]$ we define

$B^{\Delta}({\boldsymbol{x}})=\\{{\boldsymbol{y}}\in\Sigma^{n}:\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})=\mathsf{SynDef}_{\Delta}({\boldsymbol{y}})\\}$

as all the length-$n$ words that will result in the same word after deleting
the symbols located at these cycles in $\Delta$. Besides, if $|\Delta|=1$ and
has only one element $\delta\in[4n]$, we also use the notation
$B^{\delta}({\boldsymbol{x}})$ to represent the confusable ball of
${\boldsymbol{x}}$ in case of the defect of cycle $\delta$.

For radius-$1$ confusable ball of ${\boldsymbol{x}}$, we have the following
lemmas.

######  Lemma 1.

For ${\boldsymbol{x}}\in\Sigma^{n}$, and
$\delta\in\mathsf{cycle}({\boldsymbol{x}})$, we have

$\displaystyle|B^{\delta}({\boldsymbol{x}})|=$
$\displaystyle|\\{\delta-4,\delta-3,\delta-2,\delta-1\\}\cap(\mathsf{cycle}(\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{x}}))\cup\\{0\\})|.$

###### Proof:

For every ${\boldsymbol{y}}\in B^{\delta}({\boldsymbol{x}})$, it has
$\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{y}})=\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{x}})$
by the definition of $B^{\delta}({\boldsymbol{x}})$. Thus, we can generate
$B^{\delta}({\boldsymbol{x}})$ by inserting the symbol ($\delta\bmod 4$) in
$\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{x}})$ and make sure it is at the
$\delta$ cycle.

Due to the property of the cycle sequence, any two consecutive elements in a
cycle sequence have difference at most $4$. Consequently, if we want to insert
a symbol making sure it is at the $\delta$ cycle, then it must be inserted
after the symbol synthesized at cycle $\delta-4$ or $\delta-3$ or $\delta-2$
or $\delta-1$. So, the size of $B^{\delta}({\boldsymbol{x}})$ depends on
$\\{\delta-4,\delta-3,\delta-2,\delta-1\\}$ and
$\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{x}})$. Specially, if we insert
($\delta\bmod 4$) at the beginning of
$\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{x}})$, then we actually insert it
after the cycle $0$. Hence, we conclude that
$|B^{\delta}({\boldsymbol{x}})|=|\\{\delta-4,\delta-3,\delta-2,\delta-1\\}\cap(\mathsf{cycle}(\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{x}}))\cup\\{0\\})|$.
$\blacksquare$

This leads to the following lemma, demonstrating the relationship between the
indices of deletions in ${\boldsymbol{x}}$ and those in its confusable
sequence.

######  Lemma 2.

If ${\boldsymbol{x}}\in\Sigma^{n}$ suffers from $t$ synthesis defects at
cycles in
$\Delta=\\{\delta_{1},\ldots,\delta_{t}\\}\subseteq\mathsf{cycle}({\boldsymbol{x}})$
resulting in $\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$, then for any
${\boldsymbol{y}}\in B^{\Delta}({\boldsymbol{x}})$ with
$\mathsf{cycle}({\boldsymbol{x}})_{\\{i_{1},i_{2},\ldots,i_{t}\\}}=\mathsf{cycle}({\boldsymbol{y}})_{\\{j_{1},j_{2},\ldots,j_{t}\\}}=\Delta$,
we have $|i_{k}-j_{k}|\leq 4k-1$ for $1\leq k\leq t$.

###### Proof:

For any ${\boldsymbol{y}}\in B^{\Delta}({\boldsymbol{x}})$, ${\boldsymbol{y}}$
can be obtained by inserting $t$ symbols successively into
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$ in the order
$x_{i_{1}},x_{i_{2}},\ldots,x_{i_{t}}$ and at positions
$j_{1},j_{2},\ldots,j_{t}$. By Lemma 1, there are at most $4$ positions to
insert $x_{i_{1}}$ such that it is inserted at the cycle of
$\mathsf{cycle}({\boldsymbol{x}})_{i_{1}}$, where the index is in the range
$[i_{1}-3,i_{1}+3]$, so $|i_{1}-j_{1}|\leq 3$. After inserting $x_{i_{1}}$
into $\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$, each cycle of
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})_{i}$ will increase by $4$ or keep
unchanged for $i>i_{1}$. Again there are at most $4$ positions to insert
$x_{i_{2}}$ at the cycle of $\mathsf{cycle}({\boldsymbol{x}})_{i_{2}}$. Since
the cycles may have increased by $4$, $x_{i_{2}}$ is possible to be inserted
near the symbol synthesized at $\mathsf{cycle}({\boldsymbol{x}})_{i_{2}}-4$,
so $|i_{2}-j_{2}|\leq 7$. Repeating this process, we conclude that
$|i_{k}-j_{k}|\leq 4k-1$ for $1\leq k\leq t$. $\blacksquare$

######  Example 3.

Let ${\boldsymbol{x}}$ and $\mathsf{cycle}({\boldsymbol{x}})$ be the
following, and let $\Delta=\\{5,17\\}$.

$\mathsf{cycle}({\boldsymbol{x}})$ | = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
${\boldsymbol{x}}$ | = | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2

Then, we have
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})\triangleq{\boldsymbol{x}}^{\prime}$
as follows:

$\mathsf{cycle}({\boldsymbol{x}}^{\prime})$ | = | 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
${\boldsymbol{x}}^{\prime}$ | = | 1 | 2 | 3 | 4 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 2

Now we want to insert two $1$s into
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$ such that these two $1$s are at
$5$th and $17$th cycles. We first insert a $1$ at the second position of
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$, then we get
${\boldsymbol{x}}^{\prime\prime}$ as follows:

$\mathsf{cycle}({\boldsymbol{x}}^{\prime\prime})$ | = | 1 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 22
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
${\boldsymbol{x}}^{\prime\prime}$ | = | 1 | 1 | 2 | 3 | 4 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 2

Next, to get a sequence in $B^{\Delta}({\boldsymbol{x}})$ we need to insert a
$1$ into ${\boldsymbol{x}}^{\prime\prime}$ such it is at $17$th cycle. We
insert it at the $10$th position of ${\boldsymbol{x}}^{\prime\prime}$, and we
get ${\boldsymbol{y}}\in B^{\Delta}({\boldsymbol{x}})$:

$\mathsf{cycle}({\boldsymbol{y}})$ | = | 1 | 5 | 6 | 7 | 8 | 10 | 11 | 12 | 13 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 26
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
${\boldsymbol{y}}$ | = | 1 | 1 | 2 | 3 | 4 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 2

Compare ${\boldsymbol{y}}$ with ${\boldsymbol{x}}$, and we have
$\mathsf{cycle}({\boldsymbol{x}})_{\\{5,17\\}}=\mathsf{cycle}({\boldsymbol{y}})_{\\{2,10\\}}=\\{5,17\\}=\Delta$,
which satisfies the conclusion of Lemma 2 that $|i_{k}-j_{k}|\leq 4k-1$ for
$k=1,2$. $\blacksquare$

###  III-A Reduction to binary codes

In this subsection, we show that the constructions of $t$-KDCCs can be reduced
to constructions of binary codes.

######  Definition 7 ([13]).

Let ${\boldsymbol{x}}\in\Sigma^{n}$ be a quaternary word of length $n$. Define
the signature of ${\boldsymbol{x}}$ to be the binary sequence
$\widetilde{{\boldsymbol{x}}}$ of length $n-1$ such that

$\widetilde{x}_{i}=\begin{cases}1&\quad\text{if }x_{i+1}\geq x_{i},\\\
0&\quad\text{if }x_{i+1}<x_{i},\\\ \end{cases}$

for all $1\leq i\leq n-1$.

######  Lemma 3.

If ${\boldsymbol{x}}\in\Sigma^{n}$ suffers from $t$ synthesis defects at cycle
$\Delta=\\{\delta_{1},\ldots,\delta_{t}\\}\subseteq\mathsf{cycle}({\boldsymbol{x}})$
resulting in $\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$, then with the
knowledge of $\Delta$ and $\widetilde{{\boldsymbol{x}}}$, we can recover
${\boldsymbol{x}}$ from $\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$.

###### Proof:

We prove this by giving an algorithm, where the inputs are
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}}),\Delta=\\{\delta_{1},\ldots,\delta_{t}\\}$
and $\widetilde{{\boldsymbol{x}}}$, and output is ${\boldsymbol{x}}$. First we
recover the symbol synthesized at $\delta_{1}$ cycle. By Lemma 1 and 2, there
are at most $4$ positions to insert the symbol $(\delta_{1}\bmod{4})$.
Specifically, it can only be inserted after symbols synthesized at cycles in
$\\{\delta_{1}-4,\delta_{1}-3,\delta_{1}-2,\delta_{1}-1\\}$. Let
$I=\\{i+1:\mathsf{cycle}({\boldsymbol{x}})_{i}\in\\{\delta_{1}-4,\delta_{1}-3,\delta_{1}-2,\delta_{1}-1\\}\\}$,
then $I$ is the set of indices suitable to insert $(\delta_{1}\bmod{4})$.
Furthermore, $|I|\leq 4$ and the elements in $I$ are consecutive. Since we can
know the monotonicity of ${\boldsymbol{x}}_{I}$ from
$\widetilde{{\boldsymbol{x}}}$, there is only one choice in $I$ to insert
$(\delta_{1}\bmod{4})$ keeping the monotonicity. Denote the sequence obtained
by inserting $(\delta_{1}\bmod{4})$ into
$\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$ as ${\boldsymbol{x}}^{\prime}$,
and renew the inputs as
${\boldsymbol{x}}^{\prime},\Delta=\\{\delta_{2},\ldots,\delta_{t}\\}$ and
$\widetilde{{\boldsymbol{x}}}$. After $t$ rounds of algorithm, we can get the
correct sequence ${\boldsymbol{x}}$. $\blacksquare$

The following is an algorithm we mentioned above to recover ${\boldsymbol{x}}$
with the knowledge of the defective cycles and the signature.

Input: $\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$,
$\Delta=\\{\delta_{1},\ldots,\delta_{t}\\}$ and $\widetilde{{\boldsymbol{x}}}$

Output: ${\boldsymbol{x}}$

Set $j=1$,
${\boldsymbol{x}}^{\prime}=\mathsf{SynDef}_{\Delta}({\boldsymbol{x}})$;

while  _$\Delta\neq\varnothing$_ do

$I\leftarrow\\{i+1:\mathsf{cycle}({\boldsymbol{x}})_{i}\in\\{\delta_{j}-4,\delta_{j}-3,\delta_{j}-2,\delta_{j}-1\\}\\}$;

foreach  _$i\in I$_ do

${\boldsymbol{x}}^{i}\leftarrow$ insert $(\delta_{j}\bmod 4)$ at position $i$
in ${\boldsymbol{x}}^{\prime}$;

if  _$\exists~{}i$ , such that
$\widetilde{{\boldsymbol{x}}^{i}}_{I}=\widetilde{{\boldsymbol{x}}}_{I}$_ then

${\boldsymbol{x}}^{\prime}\leftarrow{\boldsymbol{x}}^{i}$;

Remove $\delta_{j}$ from $\Delta$;

$j=j+1$;

end if

end foreach

end while

${\boldsymbol{x}}\leftarrow{\boldsymbol{x}}^{\prime}$;

return ${\boldsymbol{x}}$;

Algorithm 1 Recover ${\boldsymbol{x}}$ with the knowledge of defective cycles
and its signature

With Lemma 3 and the above algorithm, the problem of correcting $t$ synthesis
defects with the knowledge of defective cycles reduces to recovering the
signature with the information of defective cycles.

By the definition of signature, we have the following observation.

######  Observation 1 ([13]).

For ${\boldsymbol{x}}\in\Sigma^{n}$, if a deletion occurs at $x_{i}$, then
$\widetilde{x}_{i}$ or $\widetilde{x}_{i-1}$ will be deleted. Conversely, if
the index of deletion in $\widetilde{{\boldsymbol{x}}}$ is $i$, then the index
of deletion in ${\boldsymbol{x}}$ is $i$ or $i+1$.

Specifically, if $x_{i-1}\leq x_{i}\leq x_{i+1}$ or $x_{i-1}>x_{i}>x_{i+1}$,
then the deletion of $x_{i}$ will cause a deletion of $\widetilde{x}_{i}$. If
$x_{i-1}\leq x_{i}>x_{i+1}$ and $x_{i-1}>x_{i+1}$, then the deletion of
$x_{i}$ will cause a deletion of $\widetilde{x}_{i-1}$. If $x_{i-1}\leq
x_{i}>x_{i+1}$ and $x_{i-1}\leq x_{i+1}$, then the deletion of $x_{i}$ will
cause a deletion of $\widetilde{x}_{i}$. The case of $x_{i-1}>x_{i}\leq
x_{i+1}$ is similar. So we have the following corollary of Lemma 2.

######  Corollary 1.

Let ${\boldsymbol{x}}\in\Sigma^{n}$, and
$\Delta\subseteq\mathsf{cycle}({\boldsymbol{x}})$ is of size $t$. For any
${\boldsymbol{y}}\in B^{\Delta}({\boldsymbol{x}})$ with
$\widetilde{{\boldsymbol{x}}}_{n\setminus\\{i_{1},i_{2},\ldots,i_{t}\\}}=\widetilde{{\boldsymbol{y}}}_{n\setminus\\{j_{1},j_{2},\ldots,j_{t}\\}}$,
we have $|i_{k}-j_{k}|\leq 4k$ for $1\leq k\leq t$.

With this corollary, if we want to construct a $t$-KDCC, it suffices to
construct a binary ${\boldsymbol{P}}$-bounded $t$-deletion correcting code for
${\boldsymbol{P}}=(5,9,\ldots,4t+1)$.

###  III-B Constructions for $t=1$

We first construct a single-KDCC by using binary $P$-bounded $1$-deletion
correcting code with redundancy $\log 12$. Then, we show that this can be
improved by giving another construction with redundancy $\log 4$.

######  Definition 8.

For ${\boldsymbol{x}}\in\mathbb{Z}^{n}$, the VT-syndrome of ${\boldsymbol{x}}$
is defined as ${\rm VT}({\boldsymbol{x}})\triangleq\sum_{i=1}^{n}{ix_{i}}$.
Define ${\rm Sum}({\boldsymbol{x}})\triangleq\sum_{i=1}^{n}x_{i}$.

######  Construction 1 ([12, Construction 1]).

For $a\in\mathbb{Z}_{P},b\in\mathbb{Z}_{2}$, let the shifted Varshamov-
Tenengolts code be:

$\displaystyle{\rm SVT}_{a,b}(n,P)=\Big{\\{}{\boldsymbol{x}}\in\Sigma^{n}:$
$\displaystyle{\rm VT}({\boldsymbol{x}})=a\bmod P,$ $\displaystyle{\rm
Sum}({\boldsymbol{x}})=b\bmod 2\Big{\\}}$

######  Lemma 4 ([12, Lemma 4, 5]).

For $a\in\mathbb{Z}_{P},b\in\mathbb{Z}_{2}$, the shifted VT code ${\rm
SVT}_{a,b}(n,P)$ is a $P$-bounded single-deletion correcting code, and there
exist $a$ and $b$ such that the redundancy is at most $\log P+1$.

######  Construction 2.

For $a\in\mathbb{Z}_{5},b\in\mathbb{Z}_{2}$ define the code

$\mathcal{C}_{1}^{KDCC}(n;a,b)=\Big{\\{}{\boldsymbol{x}}\in\Sigma^{n}:\widetilde{{\boldsymbol{x}}}\in{\rm
SVT}_{a,b}(n,5)\Big{\\}}.$

######  Theorem 1.

For $a\in\mathbb{Z}_{5},b\in\mathbb{Z}_{2}$ the code
$\mathcal{C}_{1}^{KDCC}(n;a,b)$ is a $1$-KDCC, and there exist $a$ and $b$
such that the redundancy is at most $\log 10$.

###### Proof:

Suppose $\mathcal{C}_{1}^{KDCC}(n;a,b)$ is not a $1$-KDCC, then there exists a
${\boldsymbol{y}}\in\mathcal{C}_{1}^{KDCC}(n;a,b)$, such that
${\boldsymbol{y}}\in B^{\delta}({\boldsymbol{x}})$ for some
$\delta\in\mathsf{cycle}({\boldsymbol{x}})$. Let $i$ and $j$ be the indices
such that
${\boldsymbol{x}}_{[n]\setminus\\{i\\}}={\boldsymbol{y}}_{[n]\setminus\\{j\\}}$,
then we have $i^{\prime}\in\\{i-1,i\\},j^{\prime}\in\\{j-1,j\\}$ where
$\widetilde{{\boldsymbol{x}}}_{[n]\setminus\\{i^{\prime}\\}}=\widetilde{{\boldsymbol{y}}}_{[n]\setminus\\{j^{\prime}\\}}$.
By Lemma 2 and Corollary 1, it has to be $|i-j|\leq 3$ and
$|i^{\prime}-j^{\prime}|\leq 4$ which contradict that
$\widetilde{{\boldsymbol{x}}},\widetilde{{\boldsymbol{y}}}\in{\rm
SVT}_{a,b}(n,5)$.

Set $P=5$, we get that there exist $a$ and $b$ such that the redundancy of
$\mathcal{C}_{1}^{KDCC}(n;a,b)$ is at most $\log 5+1=\log 10$ by Lemma 4.
$\blacksquare$

The above shows an example of constructing $1$-KDCC from binary
${\boldsymbol{P}}$-bounded single-deletion correcting code In the remaining of
this subsection, we construct $1$-KDCC without using the signature.

######  Construction 3.

For $a\in\mathbb{Z}_{4}$, define the code

$\mathcal{C}_{1}^{KDCC}(n;a)=\Big{\\{}{\boldsymbol{x}}\in\Sigma^{n}:\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}=a\bmod
4\Big{\\}}.$

######  Theorem 2.

For $a\in\mathbb{Z}_{4}$ the code $\mathcal{C}_{1}^{KDCC}(n;a)$ is a $1$-KDCC
and there exists an $a$ such that the redundancy is at most $\log 4$ for some
$a\in\mathbb{Z}_{4}$.

###### Proof:

Suppose $\mathcal{C}_{1}^{KDCC}(n;a)$ is not a $1$-KDCC, then there exists a
${\boldsymbol{y}}\in\mathcal{C}_{1}^{KDCC}(n;a)$, such that
${\boldsymbol{y}}\in B^{\delta}({\boldsymbol{x}})$ for some
$\delta\in\mathsf{cycle}({\boldsymbol{x}})$. Again we let $i<j$ be the indices
such that
${\boldsymbol{x}}_{[n]\setminus\\{i\\}}={\boldsymbol{y}}_{[n]\setminus\\{j\\}}$.
By the proof of Lemma 1, if we concentrate on the different parts of
${\boldsymbol{x}}$ and ${\boldsymbol{y}}$ which are ${\boldsymbol{x}}_{[i,j]}$
and ${\boldsymbol{y}}_{[i,j]}$, then $x_{i}=y_{j}$ and $x_{k}=y_{k-1}$ for
$i+1\leq k\leq j$. Besides, $x_{i},\ldots,x_{j}$ are all different since they
are synthesized within $4$ cycles. Now we discuss in three cases, $j-i=3,2,1$.

  * •

If $j-i=1$, then we have

$\left|\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}y_{2i}\right|=\left|x_{i}-x_{j}\right|\in\\{1,2,3\\},$

a contradiction.

  * •

If $j-i=2$, then we have

$\left|\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}y_{2i}\right|=\begin{cases}|x_{i}+x_{j}-x_{i+1}-x_{i}|,\text{
if $i$ is even},\\\ |x_{i+1}-x_{j}|,\text{ if $i$ is odd}.\end{cases}$

Either $i$ is even or odd, we can get
$\left|\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}y_{2i}\right|=|x_{i+1}-x_{j}|\in\\{1,2,3\\}$,
a contradiction.

  * •

If $j-i=3$, then

$\left|\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}y_{2i}\right|=|x_{i}+x_{i+2}-x_{i+1}-x_{j}|.$

In this case,
${\boldsymbol{x}}_{[i:j]}=x_{i}x_{i+1}x_{i+2}x_{i+3}\in\\{1234,2341,3412,4123\\}$,
so $|x_{i}+x_{i+2}-x_{i+1}-x_{j}|=2$, again a contradiction.

In all cases,
$1\leq\left|\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}-\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}y_{2i}\right|\leq
3$, which contradicts
$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x_{2i}=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}y_{2i}\bmod
4$.

By the pigeonhole principle, there exists $a\in\mathbb{Z}_{4}$, such the code
$\mathcal{C}_{1}^{KDCC}(n;a)$ has size at least $\frac{4^{n}}{4}$. So the
redundancy is at most $\log 4$. $\blacksquare$

###  III-C Construction of $t=2$

In this subsection, we provide a $2$-KDCC by constructing a binary
${\boldsymbol{P}}$-bounded $2$-deletion correcting code for
${\boldsymbol{P}}=(P_{1},P_{2})$.

For ${\boldsymbol{x}}\in\\{0,1\\}^{n}$, we use $A({\boldsymbol{x}})$ to
represent the $P\times\frac{n}{P}$ array form of ${\boldsymbol{x}}$. That is,

$A({\boldsymbol{x}})=\left[\begin{array}[]{cccc}x_{1}&x_{P+1}&\cdots&x_{n-P+1}\\\
x_{2}&x_{P+2}&\cdots&x_{n-P+2}\\\ \vdots&\vdots&\ddots&\vdots\\\
x_{P}&x_{2P}&\cdots&x_{n}\end{array}\right].$

Let $A({\boldsymbol{x}})_{i}$ be the $i$th row of $A({\boldsymbol{x}})$, where
$1\leq i\leq P$.

######  Construction 4.

For $\boldsymbol{a}\in\mathbb{Z}_{3}^{P}$ and $b\in\mathbb{Z}_{3^{P}n}$, we
denote

$\displaystyle\mathcal{C}_{2}^{P}(n;\boldsymbol{a},b)$
$\displaystyle=\Big{\\{}{\boldsymbol{x}}\in\\{0,1\\}^{n}:\sum_{i=1}^{P}3^{i-1}{\rm
VT}(A({\boldsymbol{x}})_{i})=b\bmod 3^{P}n,$ $\displaystyle{\rm
Sum}(A({\boldsymbol{x}})_{i})=a_{i}\bmod 3,\text{ for }1\leq i\leq
P\Big{\\}}.$

######  Lemma 5.

For $\boldsymbol{a}\in\mathbb{Z}_{3}^{P}$ and $b\in\mathbb{Z}_{3^{P}n}$, the
code $\mathcal{C}_{2}^{P}(n;\boldsymbol{a},b)$ can correct two bursts of
erasures of length at most $P$.

###### Proof:

It is easy to see that a burst of erasures of length $P$ will cause an erasure
in every row of $A({\boldsymbol{x}})$. If the coordinates of the two bursts of
erasures overlap, or in other words, the error type is a burst of erasure of
length at most $2P-1$, then we can erase more bits such that the error is two
bursts of erasures of length $P$. Thus, every row of $A({\boldsymbol{x}})$
will has two erasures.

Suppose the erroneous word is ${\boldsymbol{x}}^{\prime}$. We can get the two
missing bits in every row by calculating ${\rm
Sum}(A({\boldsymbol{x}})_{i})-{\rm Sum}(A({\boldsymbol{x}}^{\prime})_{i})$ for
$1\leq i\leq P$. If the difference is $0$, then we know the two missing bits
are both $0$. If the difference is $2$, then we know the two missing bits are
both $1$. In these two cases, the row will be recovered correctly. If the
difference is $1$, then we know the two missing bits are $1$ and $0$, but we
do not know their order. In the following, we consider this case.

Let the indices of the two erasures in $i$th row are $k_{i}$ and $\ell_{i}$,
where $1\leq k_{i}<\ell_{i}\leq\frac{n}{P}$ for $1\leq i\leq P$. We have
$k_{i}\in\\{k_{1},k_{1}-1\\}$ and $\ell_{i}\in\\{\ell_{1},\ell_{1}-1\\}$ for
$2\leq i\leq P$. Suppose we have another codeword
${\boldsymbol{y}}\in\mathcal{C}_{2}^{P}(n;\boldsymbol{a},b)$, which results in
the same word after erasing the same coordinates. Now we consider the
difference of the first constraint between ${\boldsymbol{x}}$ and
${\boldsymbol{y}}$. Denote their difference as

$D\triangleq\sum_{i=1}^{P}3^{i-1}{\rm
VT}(A({\boldsymbol{x}})_{i})-\sum_{i=1}^{P}3^{i-1}{\rm
VT}(A({\boldsymbol{y}})_{i}).$

Since ${\boldsymbol{x}}\neq{\boldsymbol{y}}$, there must exist some
$\\{i_{1},\ldots,i_{p}\\}\subseteq[P]$, such that
$A({\boldsymbol{x}})_{i_{j}}\neq A({\boldsymbol{y}})_{i_{j}}$. As ${\rm
Sum}(A({\boldsymbol{x}})_{i_{j}})={\rm Sum}(A({\boldsymbol{y}})_{i_{j}})\bmod
3$, we have
$s_{i_{j}}=A({\boldsymbol{x}})_{i_{j},k_{i_{j}}}=1-A({\boldsymbol{y}})_{i_{j},k_{i_{j}}}=1-A({\boldsymbol{x}})_{i_{j},\ell_{i_{j}}}=A({\boldsymbol{y}})_{i_{j},\ell_{i_{j}}}$,
where $s_{i_{j}}\in\\{0,1\\}$ for $1\leq j\leq p$. Therefore,

$\displaystyle D$ $\displaystyle=\sum_{i=1}^{P}3^{i-1}{\rm
VT}(A({\boldsymbol{x}})_{i})-\sum_{i=1}^{P}3^{i-1}{\rm
VT}(A({\boldsymbol{y}})_{i})$ $\displaystyle=\sum_{j=1}^{p}3^{i_{j}-1}{\rm
VT}(A({\boldsymbol{x}})_{i_{j}})-\sum_{j=1}^{p}3^{i_{j}-1}{\rm
VT}(A({\boldsymbol{y}})_{i_{j}})$
$\displaystyle=\sum_{j=1}^{p}3^{i_{j}-1}({\rm
VT}(A({\boldsymbol{x}})_{i_{j}})-{\rm VT}(A({\boldsymbol{y}})_{i_{j}}))$
$\displaystyle=\sum_{j=1}^{p}3^{i_{j}-1}(1-2s_{i_{j}})(\ell_{i_{j}}-k_{i_{j}}).$

Since $1\leq\ell_{i_{j}}-k_{i_{j}}\leq\frac{n}{P}$, we can bound the range of
$D$:

$|D|\leq\sum_{j=1}^{p}3^{i_{j}-1}\frac{n}{P}\leq\frac{3^{P}-1}{2P}n,$

which is less than $3^{P}n$.

Now we show $D$ cannot be $0$. As $k_{i}\in\\{k_{1},k_{1}-1\\}$ and
$\ell_{i}\in\\{\ell_{1},\ell_{1}-1\\}$ for $2\leq i\leq P$, we have
$\ell_{i_{j}}-k_{i_{j}}\in\\{d-1,d,d+1\\}$ for $1\leq j\leq p$, where
$d\triangleq\ell_{i_{1}}-k_{i_{1}}$. We claim that there exists no $1\leq
u<v\leq p$ such that
$\\{\ell_{i_{u}}-k_{i_{u}},\ell_{i_{v}}-k_{i_{v}}\\}=\\{d-1,d+1\\}$. If
$\ell_{i_{u}}-k_{i_{u}}=d-1$, this means
$\ell_{i_{u}}=\ell_{1}-1,k_{i_{u}}=k_{1}$. Since $u<v$, by the array
representation it has $\ell_{i_{v}}\leq\ell_{i_{u}}$ and $k_{i_{v}}\leq
k_{i_{u}}$. The possibilities of $(\ell_{i_{v}},k_{i_{v}})$ are
$(\ell_{1}-1,k_{1})$ and $(\ell_{1}-1,k_{1}-1)$. Therefore
$\ell_{i_{v}}-k_{i_{v}}\in\\{d-1,d\\}$. If $\ell_{i_{u}}-k_{i_{u}}=d+1$, this
means $\ell_{i_{u}}=\ell_{1},k_{i_{u}}=k_{1}-1$. Similarly we can get
$\ell_{i_{v}}-k_{i_{v}}\in\\{d,d+1\\}$. The above claim shows that if there
exist a least index $1\leq j\leq p$ such that
$\ell_{i_{j}}-k_{i_{j}}=d^{\prime}\neq d$, then for all $j<j^{\prime}\leq p$,
$\ell_{i_{j^{\prime}}}-k_{i_{j^{\prime}}}\in\\{d^{\prime},d\\}$. In other
words, $\ell_{i_{j}}-k_{i_{j}}\in\\{d-1,d\\}$ or
$\ell_{i_{j}}-k_{i_{j}}\in\\{d,d+1\\}$ for $1\leq j\leq p$.

  * •

If $s_{i_{p}}=0$, then

$\displaystyle D$
$\displaystyle=\sum_{j=1}^{p}3^{i_{j}-1}(1-2s_{i_{j}})(\ell_{i_{j}}-k_{i_{j}})$
$\displaystyle\geq
3^{i_{p}-1}(\ell_{i_{p}}-k_{i_{p}})-\sum_{j=1}^{p-1}3^{i_{j}-1}(\ell_{i_{j}}-k_{i_{j}})$
$\displaystyle\geq
3^{i_{p}-1}(\ell_{i_{p}}-k_{i_{p}})-\sum_{j=1}^{p-1}3^{i_{j}-1}(\ell_{i_{p}}-k_{i_{p}}+1)$
$\displaystyle\geq
3^{i_{p}-1}(\ell_{i_{p}}-k_{i_{p}})-\frac{3^{i_{p}-1}-1}{2}(\ell_{i_{p}}-k_{i_{p}}+1)$
$\displaystyle=\frac{3^{i_{p}-1}+1}{2}(\ell_{i_{p}}-k_{i_{p}})-\frac{3^{i_{p}-1}-1}{2}$
$\displaystyle\geq\frac{3^{i_{p}-1}+1}{2}-\frac{3^{i_{p}-1}-1}{2}$
$\displaystyle=1.$

  * •

If $s_{i_{p}}=1$, then

$\displaystyle D$
$\displaystyle=\sum_{j=1}^{p}3^{i_{j}-1}(1-2s_{i_{j}})(\ell_{i_{j}}-k_{i_{j}})$
$\displaystyle\leq\sum_{j=1}^{p-1}3^{i_{j}-1}(\ell_{i_{j}}-k_{i_{j}})-3^{i_{p}-1}(\ell_{i_{p}}-k_{i_{p}})$
$\displaystyle\leq\sum_{j=1}^{p-1}3^{i_{j}-1}(\ell_{i_{p}}-k_{i_{p}}+1)-3^{i_{p}-1}(\ell_{i_{p}}-k_{i_{p}})$
$\displaystyle\leq\frac{3^{i_{p}-1}-1}{2}(\ell_{i_{p}}-k_{i_{p}}+1)-3^{i_{p}-1}(\ell_{i_{p}}-k_{i_{p}})$
$\displaystyle=-\frac{3^{i_{p}-1}+1}{2}(\ell_{i_{p}}-k_{i_{p}})+\frac{3^{i_{p}-1}-1}{2}$
$\displaystyle\leq-\frac{3^{i_{p}-1}+1}{2}+\frac{3^{i_{p}-1}-1}{2}$
$\displaystyle=-1.$

In either case, $D$ cannot be $0$, which contradicts the fact that
${\boldsymbol{x}},{\boldsymbol{y}}\in\mathcal{C}_{2}^{P}(n;{\boldsymbol{a}},b)$.
$\blacksquare$

######  Theorem 3.

For ${\boldsymbol{P}}=(P_{1},P_{2})$, $\boldsymbol{a}\in\mathbb{Z}_{3}^{P}$
and $b\in\mathbb{Z}_{3^{P}n}$, the code
$\mathcal{C}_{2}^{P}(n;\boldsymbol{a},b)$ is a binary
${\boldsymbol{P}}$-bounded two-deletion correcting code, and there exist
${\boldsymbol{a}}$ and $b$ such that it has redundancy at most $\log n+2P\log
3$.

###### Proof:

If we know the knowledge of the two intervals containing deletions, then the
bits outside these two intervals are error-free and can be put in their
correct positions. For example, if ${\boldsymbol{x}}$ deletes two bits in two
intervals $[i,i+P_{1}-1]$ and $[j,j+P_{2}-1]$ respectively, where $1\leq i\leq
j\leq n-P+1$. Let ${\boldsymbol{x}}^{\prime}$ denote the erroneous word of
${\boldsymbol{x}}$, then by setting

$\displaystyle{\boldsymbol{x}}^{\prime\prime}=~{}$ $\displaystyle
x^{\prime}_{1},\ldots,x^{\prime}_{i-1},\underbrace{?,\ldots,?}_{P_{1}},x^{\prime}_{i+P_{1}-1},\ldots,$
$\displaystyle
x^{\prime}_{j-2},\underbrace{?,\ldots,?}_{P_{2}},x^{\prime}_{j+P_{2}-2},\ldots,x^{\prime}_{n-2},$

we get a word resulted from ${\boldsymbol{x}}$ by two bursts of erasures of
length $P_{1},P_{2}$. By Lemma 5, we can recover ${\boldsymbol{x}}$ from
${\boldsymbol{x}}^{\prime\prime}$. So the code
$\mathcal{C}_{2}^{P}(n;\boldsymbol{a},b)$ can always correct two deletions if
we have the information of two intervals containing deletions.

By the pigeonhole principle, there exists
$\boldsymbol{a}\in\mathbb{Z}_{3}^{P},b\in\mathbb{Z}_{3^{P}n}$, such the code
$\mathcal{C}_{2}^{P}(n;\boldsymbol{a},b)$ has size at least

$\frac{2^{n}}{3^{P}n\cdot 3^{P}}.$

So the redundancy is at most $\log n+2P\log 3$. $\blacksquare$

Now we are ready to give the construction of $2$-KDCC. By Corollary 1, we can
set ${\boldsymbol{P}}=(5,9)$, thus $P=\max\\{5,9\\}=9$.

######  Construction 5.

For $\boldsymbol{a}\in\mathbb{Z}_{3}^{9}$, $b\in\mathbb{Z}_{3^{9}n}$ and
$P=9$, we denote

$\mathcal{C}_{2}^{KDCC}(n;{\boldsymbol{a}},b)=\Big{\\{}{\boldsymbol{x}}\in\Sigma^{n}:\widetilde{{\boldsymbol{x}}}\in\mathcal{C}_{2}^{P}(n;{\boldsymbol{a}},b)\Big{\\}}.$

######  Theorem 4.

For $\boldsymbol{a}\in\mathbb{Z}_{3}^{9}$ and $b\in\mathbb{Z}_{3^{9}n}$, the
code $\mathcal{C}_{2}^{KDCC}(n;{\boldsymbol{a}},b)$ is a $2$-KDCC, and there
exists parameters such that the redundancy is at most $\log n+18\log 3$.

###### Proof:

By Lemma 3, $\mathcal{C}_{2}^{KDCC}(n;{\boldsymbol{a}},b)$ is a $2$-KDCC, as
we can uniquely recovery each signature of the codeword which is in a
$(5,9)$-bounded $2$-deletion correcting code. Furthermore, there exists
choices of $\boldsymbol{a}\in\mathbb{Z}_{3}^{9}$ and
$b\in\mathbb{Z}_{3^{9}n}$, such that the redundancy of
$\mathcal{C}_{2}^{KDCC}(n;{\boldsymbol{a}},b)$ is at most
$2n-\log\frac{4^{n}}{3^{18}n}=\log n+18\log 3$. $\blacksquare$

We have constructed a binary ${\boldsymbol{P}}$-bounded $2$-deletion
correcting code in this subsection. But if we let $P=c\log n$ for some $c>1$,
then the redundancy of $\mathcal{C}_{2}^{P}(n;{\boldsymbol{a}},b)$ will be at
least $(2\log 3+1)\log n$. To decrease the redundancy when $P$ is large, we
further construct another binary ${\boldsymbol{P}}$-bounded $2$-deletion
correcting code with redundancy $2\log n+o(\log n)$ even when $P=O(\log n)$.
Although we do not require $P$ to be large in this section, our
${\boldsymbol{P}}$-bounded $2$-deletion correcting code for $P=O(\log n)$ will
be useful in our construction of $2$-SDCC.

The following lemma will lead to a ${\boldsymbol{P}}$-bounded $2$-deletion
correcting code, and the proof can be found in Appendix A.

######  Lemma 6.

For any integers $P_{1},P_{2}\geq 2$ and $n\geq 3$, there exists a function
${\mathcal{E}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n+r(n,P_{1},P_{2})}$,
computable in linear time, such that for any
${\boldsymbol{x}}\in\\{0,1\\}^{n}$, if ${\mathcal{E}}({\boldsymbol{x}})$
suffers two deletions at two intervals of lengths $P_{1},P_{2}$ resulting in
${\mathcal{E}}^{\prime}({\boldsymbol{x}})$, then given the information of
these two intervals and ${\mathcal{E}}^{\prime}({\boldsymbol{x}})$ we can
uniquely recover ${\boldsymbol{x}}$, where $i,j\in[n+r(n,P_{1},P_{2})]$ are
the indices of deletions, and $r(n,P_{1},P_{2})=2\log n+7\log\log
n+14\log(P_{1}+P_{2})+\log P+O(\log\log(P_{1}+P_{2}))$.

Let
$\mathcal{C}_{2}^{\boldsymbol{P}}=\\{{\boldsymbol{x}}\in\\{0,1\\}^{n}:{\boldsymbol{x}}={\mathcal{E}}({\boldsymbol{z}})_{[k]}01{\mathcal{E}}({\boldsymbol{z}})_{[k+1,n-2]},{\boldsymbol{z}}\in\\{0,1\\}^{k}\\}$,
where $k+r(k,P_{1},P_{2})=n-2$. We have the following theorem.

######  Theorem 5.

$\mathcal{C}_{2}^{\boldsymbol{P}}$ is a binary ${\boldsymbol{P}}$-bounded two-
deletion correcting code of redundancy $2\log n+7\log\log
n+14\log(P_{1}+P_{2})+\log P+O(\log\log(P_{1}+P_{2}))$.

##  IV Constructions of Synthesis-Defect Correcting Codes

In this section, we will provide $t$-SDCC for $t=1,2$. First we show that we
can localize each defect to a window of length $O(\log n)$ by letting the
signatures of $O(\log n)$ strands belong to binary $t$-deletion correcting
codes and with some period constraints. Then, it suffices to employ another
coding scheme which incurs less redundancy so that we can correct the
remaining strands.

###  IV-A Defect-Locating Strands

In this subsection, we code for a set of ordered sequences. We show that using
$O(\log n)$ strands is enough to cover all the $4n$ cycles, so we do not need
to let all $M$ strands belong to deletion-correcting code. By coding these
$O(\log n)$ strands, we can localize each defect to a window. With this, we
are prepared to provide the construction of $t$-SDCCs for $t=1,2$.

######  Definition 9.

Define a shift operation on ${\boldsymbol{x}}\in\Sigma^{n}$ with parameter
$1-\mathsf{cycle}({\boldsymbol{x}})_{1}\leq a\leq
4n-\mathsf{cycle}({\boldsymbol{x}})_{n}$ as
$S_{a}({\boldsymbol{x}})=(S_{a}({\boldsymbol{x}})_{1},\ldots,S_{a}({\boldsymbol{x}})_{n})$,
where
$\mathsf{cycle}(S_{a}({\boldsymbol{x}}))=(\mathsf{cycle}({\boldsymbol{x}})_{1}+a,\ldots,\mathsf{cycle}({\boldsymbol{x}})_{n}+a)$.

In other word, the shift operation on ${\boldsymbol{x}}$ increases each cycle
of ${\boldsymbol{x}}$ by $a$. Here, we suppose the sequence
$S_{a}({\boldsymbol{x}})$ can be synthesized from the
$\mathsf{cycle}({\boldsymbol{x}})_{1}+a$ cycle and each sequence has a
parameter $a$ that will be known only by the synthesis machine.

######  Example 4.

Let ${\boldsymbol{x}}=(1,3,2,1,1,4,3,2,3,4)$, then we know that
$\mathsf{cycle}({\boldsymbol{x}})=(1,3,6,9,13,16,19,22,23,24)$. Let $a=1$,
then $S_{1}({\boldsymbol{x}})=(2,4,3,2,2,1,4,3,4,1)$, and
$\mathsf{cycle}(S_{1}({\boldsymbol{x}}))=(2,4,7,10,14,17,20,23,24,25)$. Let
$a=6$, then $S_{1}({\boldsymbol{x}})=(3,1,4,3,3,2,1,4,1,2)$, and
$\mathsf{cycle}(S_{1}({\boldsymbol{x}}))=(7,9,12,15,19,22,25,28,29,30)$.

######  Lemma 7.

For ${\boldsymbol{x}}\in\Sigma^{n}$, we have
$\mathsf{cycle}(S_{t}({\boldsymbol{x}}))\cup\mathsf{cycle}(S_{t+1}({\boldsymbol{x}}))\cup\mathsf{cycle}(S_{t+2}({\boldsymbol{x}}))\cup\mathsf{cycle}(S_{t+3}({\boldsymbol{x}}))=\\{\mathsf{cycle}({\boldsymbol{x}})_{1}+t,\ldots,\mathsf{cycle}({\boldsymbol{x}})_{n}+t+3\\}$,
for $1-\mathsf{cycle}({\boldsymbol{x}})_{1}\leq t\leq
4n-\mathsf{cycle}({\boldsymbol{x}})_{n}-3$.

###### Proof:

By the definition of shift,
$\mathsf{cycle}(S_{t}({\boldsymbol{x}}))=(\mathsf{cycle}({\boldsymbol{x}})_{1}+t,\ldots,\mathsf{cycle}({\boldsymbol{x}})_{n}+t)$.
Thus we have

$\cup_{a=t}^{t+3}\mathsf{cycle}(S_{a}({\boldsymbol{x}}))_{i}=\\{\mathsf{cycle}({\boldsymbol{x}})_{i}+t,\ldots,\mathsf{cycle}({\boldsymbol{x}})_{i}+t+3\\},$

for $i\in[n]$. As the two elements in a cycle sequence have distance at most
$4$, we have
$\mathsf{cycle}(S_{t+3}({\boldsymbol{x}}))_{i}=\mathsf{cycle}({\boldsymbol{x}})_{i}+t+3\geq\mathsf{cycle}({\boldsymbol{x}})_{i+1}+t-1=\mathsf{cycle}(S_{t}({\boldsymbol{x}}))_{i+1}-1$,
which means
$(\cup_{a=t}^{t+3}\mathsf{cycle}(S_{a}({\boldsymbol{x}}))_{i})\bigcup(\cup_{a=t}^{t+3}\mathsf{cycle}(S_{a}({\boldsymbol{x}}))_{i+1})=\\{\mathsf{cycle}({\boldsymbol{x}})_{i}+t,\ldots,\mathsf{cycle}({\boldsymbol{x}})_{i+1}+t+3\\}$.
Therefore, we have

$\bigcup_{i=1}^{n}\cup_{a=t}^{t+3}\mathsf{cycle}(S_{a}({\boldsymbol{x}}))_{i}=\\{\mathsf{cycle}({\boldsymbol{x}})_{1}+t,\ldots,\mathsf{cycle}({\boldsymbol{x}})_{n}+t+3\\},$

which complete the proof. $\blacksquare$

######  Lemma 8.

For ${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{M_{1}}\in\mathsf{C}$ and
$t\in[1,3n+1]$, there always exist $a_{1},\ldots,a_{M_{1}}$, such that

$[t,n+t-1]\subseteq\bigcup_{i=1}^{M_{1}}\mathsf{cycle}(S_{a_{i}}({\boldsymbol{c}}_{i})),$

where $M_{1}=\frac{1}{2-\log 3}\log n+1$,
$a_{i}\in[-3,t+2]\cap[1-\mathsf{cycle}({\boldsymbol{c}}_{i})_{1},4n-\mathsf{cycle}({\boldsymbol{c}}_{i})_{n}]$,
and $1\leq t\leq 3n+1$.

###### Proof:

First of all, we choose $a_{1}=t-\mathsf{cycle}({\boldsymbol{c}}_{1})_{1}$, so
$\mathsf{cycle}(S_{a_{1}}({\boldsymbol{c}}_{1}))=\\{t,t+\mathsf{cycle}({\boldsymbol{c}}_{1})_{2}-\mathsf{cycle}({\boldsymbol{c}}_{1})_{1},\ldots,t+\mathsf{cycle}({\boldsymbol{c}}_{1})_{n}-\mathsf{cycle}({\boldsymbol{c}}_{1})_{1}\\}$.
Denote
$T_{1}=[t,n+t-1]\setminus\mathsf{cycle}(S_{a_{1}}({\boldsymbol{c}}_{1}))$.
Since every two consecutive elements in
$\mathsf{cycle}(S_{a_{1}}({\boldsymbol{c}}_{1}))$ have difference at most 4,
we have that

$|T_{1}|\leq n-\frac{1}{4}n=\frac{3}{4}n.$

Then, we choose $a_{2}$. By Lemma 7,
$\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}}({\boldsymbol{c}}_{2}))\cup\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+1}({\boldsymbol{c}}_{2}))\cup\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+2}({\boldsymbol{c}}_{2}))\cup\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+3}({\boldsymbol{c}}_{2}))=\\{t,\ldots,\mathsf{cycle}({\boldsymbol{c}}_{2})_{n}-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+t+3\\}\supset[t,n+t-1]$.
We claim that for
$a_{2}\in\\{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1},t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+1,t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+2,t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+3\\}$,
there always exists a choice, such that
$|T_{1}\cap\mathsf{cycle}(S_{a_{2}}({\boldsymbol{c}}_{2}))|\geq\frac{1}{4}|T_{1}|$.
Otherwise,
$|T_{1}\cap\mathsf{cycle}(S_{a_{2}}({\boldsymbol{c}}_{2}))|<\frac{1}{4}|T_{1}|$
for any
$a_{2}\in\\{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1},t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+1,t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+2,t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+3\\}$.
Then, we have
$|T_{1}|=|T_{1}\cap[t,n+t-1]|=|T_{1}\cap\bigcup_{i=0}^{3}(\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+i}({\boldsymbol{c}}_{2})))|=|\bigcup_{i=0}^{3}(T_{1}\cap\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+i}({\boldsymbol{c}}_{2})))|\leq\sum_{i=0}^{3}|T_{1}\cap\mathsf{cycle}(S_{t-\mathsf{cycle}({\boldsymbol{c}}_{2})_{1}+i}({\boldsymbol{c}}_{2}))|<|T_{1}|$,
which is a contradiction. Let $a_{2}$ be the one such that
$|T_{1}\cap\mathsf{cycle}(S_{a_{2}}({\boldsymbol{c}}_{2}))|\geq\frac{1}{4}|T_{1}|$.
Denote
$T_{2}=[t,n+t-1]\setminus(\mathsf{cycle}(S_{a_{1}}({\boldsymbol{c}}_{1}))\cup\mathsf{cycle}(S_{a_{2}}({\boldsymbol{c}}_{1})))$,
then we have

$|T_{2}|=|T_{1}\setminus(T_{1}\cap\mathsf{cycle}(S_{a_{2}}({\boldsymbol{c}}_{2})))|\leq\frac{3}{4}|T_{1}|\leq\frac{9}{16}n.$

Repeating this, we get $|T_{M_{1}-1}|\leq(\frac{3}{4})^{M_{1}-1}n=1$. Same as
previous, we choose $a_{M_{1}}$, such that
$|T_{M_{1}-1}\cap\mathsf{cycle}(S_{a_{M_{1}}}({\boldsymbol{c}}_{M_{1}}))|\geq
1$. So when we finish choosing $a_{1},\ldots,a_{M_{1}}$, we can make sure
$[t,n+t-1]$ is covered by $\mathsf{cycle}(S_{a_{i}}({\boldsymbol{c}}_{i}))$
for $i\in[M_{1}]$. $\blacksquare$

######  Corollary 2.

For ${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{4M_{1}}\in\mathsf{C}$,
there always exist $a_{1},\ldots,a_{4M_{1}}\in[-3,3n+1]$, such that
$[1,4n]\subseteq\bigcup_{i=1}^{4M_{1}}\mathsf{cycle}(S_{a_{i}}({\boldsymbol{c}}_{i}))$,
where $M_{1}=\frac{1}{2-\log 3}\log n+1$.

Lemma 8 and Corollary 2 show that we can use $O(\log n)$ strands to cover all
synthesis cycles. So, we can know the approximate locations of all the defects
if these $O(\log n)$ strands are corrected. To correct the quaternary strands,
our solution in this paper it to correct their signatures first. Then, the
locations of deletions in signatures will provide us the information of
defects in quaternary strands.

######  Lemma 9.

If ${\boldsymbol{x}}\in\Sigma^{n}$ suffers from a synthesis defect at cycle
$\delta_{1}\in[4n]$ and result in ${\boldsymbol{x}}^{\prime}$, then for any
${\boldsymbol{y}}\in\Sigma^{n}$ with
${\boldsymbol{y}}_{[n]\setminus\\{j\\}}={\boldsymbol{x}}^{\prime}$ and
$\widetilde{{\boldsymbol{y}}}=\widetilde{{\boldsymbol{x}}}$, we have
$|\delta_{2}-\delta_{1}|\leq 4P+4$, where $P$ is the length of the longest run
in $\widetilde{{\boldsymbol{x}}}$ and $j\in[n]$ is the index satisfying
$\mathsf{cycle}({\boldsymbol{y}})_{j}=\delta_{2}$.

###### Proof:

Suppose the synthesis defect causes a deletion at $i$th position of
${\boldsymbol{x}}$, then by Observation 1 the location of deletion in
$\widetilde{{\boldsymbol{x}}}$ is $i^{\prime}\in\\{i-1,i\\}$. Since
${\boldsymbol{y}}_{[n]\setminus\\{j\\}}={\boldsymbol{x}}_{[n]\setminus\\{i\\}}$,
${\boldsymbol{y}}$ can be obtained by inserting $y_{j}$ in
${\boldsymbol{x}}^{\prime}$. Besides, due to
$\widetilde{{\boldsymbol{y}}}=\widetilde{{\boldsymbol{x}}}$, the insertion of
$y_{j}$ must lead to an insertion at the same run with
$\widetilde{x}_{i^{\prime}}$. So, if the insertion of $y_{j}$ causes an
insertion at $j^{\prime}$th position of
$\widetilde{{\boldsymbol{x}}^{\prime}}$, then we have
$|j^{\prime}-i^{\prime}|\leq P-1$. As $j^{\prime}\in\\{j-1,j\\}$, we have
$|j-i|\leq P.$ Without loss of generality, we assume $j>i$. Furthermore,
$\mathsf{cycle}({\boldsymbol{x}})_{i+1}\in[\delta_{1}+1,\delta_{1}+4]$, so we
have
$\mathsf{cycle}({\boldsymbol{y}})_{j-1}=\mathsf{cycle}({\boldsymbol{x}}^{\prime})_{j-1}\leq\mathsf{cycle}({\boldsymbol{x}})_{j}\leq\delta_{1}+4(j-i)$,
and thus
$\mathsf{cycle}({\boldsymbol{y}})_{j}\leq\mathsf{cycle}({\boldsymbol{y}})_{j-1}+4\leq\delta_{1}+4(j-i)+4\leq\delta_{1}+4P+4$.
Therefore, we have $|\delta_{2}-\delta_{1}|\leq 4P+4$. $\blacksquare$

Notice that, even if the signature of a strand is recovered from $t$
deletions, the locations of errors may not be determined exactly. For example,
if a strand ${\boldsymbol{x}}\in\Sigma^{n}$ suffers from $t$ deletions, which
causes $t$ consecutive deletions in $\widetilde{{\boldsymbol{x}}}$, where
$\widetilde{x}_{i}=\widetilde{x}_{i+t}$ for $1\leq i\leq n-t-1$, then we
cannot know the locations of deletions since deleting any $t$ consecutive bits
from $\widetilde{{\boldsymbol{x}}}$ will result in the same one. Intuitively,
if we want to locate each of the location of error in a signature uniquely,
then we need to make sure $\widetilde{{\boldsymbol{x}}}$ cannot have period
$p$ for all $1\leq p\leq t$, which is a strict condition. In the following, we
use the regular sequence from [14, Definition 3] to handle the cases of
$t=1,2$.

######  Definition 10 ([14, Definition 3]).

A sequence ${\boldsymbol{x}}\in\\{0,1\\}^{n}$ is regular if each consecutive
substring of ${\boldsymbol{x}}$ of length $d\log n$ contains both $00$ and
$11$.

######  Lemma 10 ([14, Lemma 11]).

Denote $\mathcal{R}(n)$ the set of all regular binary sequences of length $n$
with $d=7$, then $|\mathcal{R}(n)|\geq 2^{n-1}$.

###  IV-B $1$-Synthesis-Defect Correcting Code

Next we are prepared to provide a construction of $1$-SDCC, which shows our
general strategy to construct synthesis-defect correcting code. Before that,
let us introduce the well-known Varshamov-Tenengolts (VT) codes.

######  Lemma 11 ([15]).

The Varshamov-Tenengolts (VT) code ${\rm
VT}(n;a)=\\{{\boldsymbol{x}}\in\\{0,1\\}^{n}:{\rm
VT}({\boldsymbol{x}})=a\bmod(n+1)\\}$ is a single-deletion correcting code,
and there exists $a\in\mathbb{Z}_{n+1}$ such that the redundancy of ${\rm
VT}(n;a)$ is at most $\log(n+1)$.

######  Construction 6.

For ${\boldsymbol{s}}\in\mathbb{Z}_{4}^{4M_{1}}$,
${\boldsymbol{b}}\in\mathbb{Z}_{n+1}^{4M_{1}}$,
${\boldsymbol{d}}\in\mathbb{Z}_{P+1}^{M-4M_{1}}$ and
${\boldsymbol{e}}\in\mathbb{Z}_{2}^{M-4M_{1}}$, where $P=28\log n+5$ and
$M_{1}=\frac{1}{2-\log 3}\log n+1$, we denote

$\displaystyle\mathcal{C}_{1}^{SD}=\Big{\\{}$
$\displaystyle\mathsf{C}\in(\Sigma^{n})^{M}:{\boldsymbol{c}}_{i}=S_{a_{i}}({\boldsymbol{x}}_{i}),{\rm
Sum}({\boldsymbol{x}}_{i})=s_{i}\bmod 4,$ $\displaystyle\text{ and
}\widetilde{{\boldsymbol{x}}_{i}}\in{\rm VT}(n;b_{i})\cap\mathcal{R}(n),\text{
for }i\in[4M_{1}],$ $\displaystyle\widetilde{{\boldsymbol{c}}_{i}}\in{\rm
SVT}_{d_{i-4M_{1}},e_{i-4M_{1}}}(n,P+1)\text{ for }i\in[4M_{1}+1,M]\Big{\\}},$

where $a_{i}$ is chosen based on Corollary 2 for $1\leq i\leq 4M_{1}$.

######  Theorem 6.

For ${\boldsymbol{s}}\in\mathbb{Z}_{4}^{4M_{1}}$,
${\boldsymbol{b}}\in\mathbb{Z}_{n+1}^{4M_{1}}$,
${\boldsymbol{d}}\in\mathbb{Z}_{P+1}^{M-4M_{1}}$ and
${\boldsymbol{e}}\in\mathbb{Z}_{2}^{M-4M_{1}}$, where $P=28\log n+5$, the code
$\mathcal{C}_{1}^{SD}$ is a $1$-SDCC, and there exist choices of parameters,
such that the redundancy of $\mathcal{C}_{1}^{SD}$ is at most $\frac{4}{2-\log
3}(\log n)^{2}+M(\log\log n+6)-\Omega(\log n\log\log n)$.

###### Proof:

By Corollary 2, we have
$\cup_{i=1}^{4M_{1}}\mathsf{cycle}({\boldsymbol{c}}_{i})=[4n]$. So if there is
a defective cycle, then there must be a ${\boldsymbol{c}}_{i}$ suffering from
a deletion for $i\in[4M_{1}]$. As $\widetilde{{\boldsymbol{x}}_{i}}$ belongs
to a VT code, we can recover $\widetilde{{\boldsymbol{x}}_{i}}$ from a
deletion uniquely. Besides, we know ${\rm Sum}({\boldsymbol{x}}_{i})\bmod 4$
and ${\rm Sum}({\boldsymbol{x}}^{\prime}_{i})\bmod 4$ for the erroneous
sequence ${\boldsymbol{x}}^{\prime}$, so we can calculate the value of deleted
symbol. With the symbol and the signature, we can recover ${\boldsymbol{x}}$
in the same way as non-binary VT code [13].

Due to $\widetilde{{\boldsymbol{x}}_{i}}\in\mathcal{R}(n)$, the length of a
run in $\widetilde{{\boldsymbol{x}}_{i}}$ is at most $7\log n$. By Lemma 9, we
know the defective cycle is within an interval of length $P=28\log n+5$.

Now we show how to recover ${\boldsymbol{c}}_{i}$ for $i\in[4M_{1}+1,M]$. In
the previous step, we have already located the defective cycle at a length-$P$
interval, so the deletions in the remaining
$\widetilde{{\boldsymbol{c}}_{i}}$s are within an interval of length at most
$P+1$. Since $\widetilde{{\boldsymbol{c}}_{i}}$ is in a shifted VT code ${\rm
SVT}_{d_{i-4M_{1}},e_{i-4M_{1}}}(n,P+1)$, we can recover it. As we have
already known the value of defective cycle by recovering
${\boldsymbol{c}}_{i}$ for $i\in[4M_{1}]$, we can recover
${\boldsymbol{c}}_{i}$ from $\widetilde{{\boldsymbol{c}}_{i}}$ for
$i\in[4M_{1}+1,M]$.

Now we calculate the redundancy of $\mathcal{C}_{1}^{SD}$. There are $4M_{1}$
regular sequences belonging to VT code, and the sum of symbols in each
sequence is equal to some value modular $4$. So there exists
${\boldsymbol{s}}\in\mathbb{Z}_{4}^{4M_{1}}$,
${\boldsymbol{b}}\in\mathbb{Z}_{n+1}^{4M_{1}}$, such the redundancy for this
part is at most $4M_{1}\log(n+1)+12M_{1}$. For the remaining sequences, the
redundancy for their part is at most $(M-4M_{1})\log 2(P+1)$. So the total
redundancy is at most

$\frac{4}{2-\log 3}(\log n)^{2}+M(\log\log n+6)-\Omega(\log n\log\log n).$

$\blacksquare$

The above $1$-SDCC $\mathcal{C}_{1}^{SD}$ shows a high-level idea to construct
$t$-SDCC: use $O(\log n)$ strands cover all cycles and let them belong to a
$t$-deletion correcting code with some period constraints, then let the
remaining sequences belong to some bounded deletion-correcting codes.

###  IV-C $2$-Synthesis-Defect Correcting Code

In the case of $t=1$, each strand either suffers from $1$ deletion or keeps
unchanged. However, if $t\geq 2$, each strand will suffer $t^{\prime}$
deletions for $t^{\prime}\in[0,t]$. Even when we locate these $t$ deletions to
$t$ interval, we do not know each of the remaining $M-4M_{1}$ strands suffers
from which of these $t$ deletions. So we cannot locate the approximate
locations of $t^{\prime}$ deletions for the remaining $M-4M_{1}$ strands.
Nevertheless, we can solve the case for $t=2$, which is more complicated than
the case $t=1$.

We first present a quaternary two-deletion correcting code, which is
constructed by using the signature.

######  Lemma 12 ([14, Theorem 7 and 8]).

There is a binary code $\mathcal{C}_{2}\subseteq\\{0,1\\}^{n}$ with each
codeword is regular and capable of correcting two deletions. The redundancy of
$\mathcal{C}_{2}$ is at most $4\log n+10\log\log n+O(1).$

######  Definition 11.

Define the run sequence of ${\boldsymbol{x}}\in\\{0,1\\}^{n}$ as
$R({\boldsymbol{x}})$, where $R({\boldsymbol{x}})_{1}=1$, and for $1\leq i\leq
n-1$,

$R({\boldsymbol{x}})_{i+1}=\begin{cases}R({\boldsymbol{x}})_{i}+1,&\text{ if
}x_{i+1}\neq x_{i},\\\ R({\boldsymbol{x}})_{i},&\text{ if
}x_{i+1}=x_{i}.\end{cases}$

Furthermore, let $r({\boldsymbol{x}})=R({\boldsymbol{x}})_{n}$ be the number
of run in ${\boldsymbol{x}}$.

For example, if ${\boldsymbol{x}}=10010111$, then
$R({\boldsymbol{x}})=12234555$. The following lemma comes from [16], but
complements their flaw.

######  Lemma 13 ([16, Lemma III.1]).

For any ${\boldsymbol{x}}\in\Sigma^{n}$, given the values
$\sum_{i=1}^{r(\widetilde{{\boldsymbol{x}}})}x_{i}\cdot
R(\widetilde{{\boldsymbol{x}}})_{i}(\bmod~{}4n)$ and
$\widetilde{{\boldsymbol{x}}}$, if ${\boldsymbol{x}}$ suffers from two
deletions resulting in ${\boldsymbol{x}}^{\prime}$, and the corresponding two
deleted bits in $\widetilde{{\boldsymbol{x}}}$ are not consecutive and in a
period-$2$ alternate substring of length greater than $2$, then we can
uniquely recovery ${\boldsymbol{x}}$ with the two values of deleted symbol.

With this lemma, it suffices to consider the case where two deletions in
$\widetilde{{\boldsymbol{x}}}$ are consecutive and in a period-$2$ alternate
substring. In this case, deleting any two consecutive bits in a period-$2$
alternate substring will result in the same string, so we cannot obtain the
runs where the two deletions are deleted from.

######  Lemma 14.

For ${\boldsymbol{x}}\in\Sigma^{n}$, if two deletions of ${\boldsymbol{x}}$
cause two consecutive deletions in an alternate substring of
$\widetilde{{\boldsymbol{x}}}$, then the two deletions in ${\boldsymbol{x}}$
are consecutive or separated by one position.

###### Proof:

By Observation 1, a deletion indexed at $i$ in $\widetilde{{\boldsymbol{x}}}$
implies the deletion in ${\boldsymbol{x}}$ is indexed at $i$ or $i+1$. Suppose
two consecutive deletions in $\widetilde{{\boldsymbol{x}}}$ caused by the two
deletions in ${\boldsymbol{x}}$ have indices $i$ and $i+1$ for $1\leq i\leq
n-1$, then it follows that the two deletions in ${\boldsymbol{x}}$ have
indices $i,i+1$ or $i,i+2$ or $i+1,i+2$, which completes the proof.
$\blacksquare$

######  Definition 12.

For ${\boldsymbol{x}}\in\Sigma^{n}$ and $\sigma\in\Sigma$, define
$N_{\sigma}({\boldsymbol{x}})$ the number of $\sigma$ in ${\boldsymbol{x}}$.
Furthermore, let
${\boldsymbol{x}}^{\sigma}\in[n]^{N_{\sigma}({\boldsymbol{x}})}$ denote the
sequence consists of the indices of $\sigma$.

For example, if ${\boldsymbol{x}}=122124123$, then
$N_{1}({\boldsymbol{x}})=3,N_{2}({\boldsymbol{x}})=4,N_{3}({\boldsymbol{x}})=1,N_{4}({\boldsymbol{x}})=1$
and
${\boldsymbol{x}}^{1}=147,{\boldsymbol{x}}^{2}=2358,{\boldsymbol{x}}^{3}=9,{\boldsymbol{x}}^{4}=6$.
Now we present a lemma which shows that the quaternary sequence is unique if
it consists of two symbols of given numbers, and has an alternate signature.

######  Lemma 15.

If ${\boldsymbol{x}},{\boldsymbol{y}}\in\Sigma^{n}$ satisfying that
$N_{\sigma_{1}}({\boldsymbol{x}})=N_{\sigma_{1}}({\boldsymbol{y}})>0$,
$N_{\sigma_{2}}({\boldsymbol{x}})=N_{\sigma_{2}}({\boldsymbol{y}})>0$,
$N_{\sigma_{3}}({\boldsymbol{x}})=N_{\sigma_{3}}({\boldsymbol{y}})=N_{\sigma_{4}}({\boldsymbol{x}})=N_{\sigma_{4}}({\boldsymbol{y}})=0$
for $\Sigma=\\{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4}\\}$, and
$\widetilde{{\boldsymbol{x}}}=\widetilde{{\boldsymbol{y}}}=0101\ldots$ or
$1010\ldots$, then we have ${\boldsymbol{x}}={\boldsymbol{y}}$.

###### Proof:

Without loss of generality, we suppose $\sigma_{1}<\sigma_{2}$. We prove the
case $\widetilde{{\boldsymbol{x}}}=\widetilde{{\boldsymbol{y}}}=0101\ldots$,
the other can be proved similarly. For every
$\widetilde{x}_{i}\widetilde{x}_{i+1}=01$, it must have
$x_{i}x_{i+1}=\sigma_{2}\sigma_{1}$ due to $\widetilde{x}_{i}=0$. Thus, if $n$
is even, then we have
${\boldsymbol{x}}={\boldsymbol{y}}=(\sigma_{2}\sigma_{1})^{n/2}$. If $n$ is
odd, we can determine all symbols except the last one. As
$\widetilde{x}_{n-1}=1$ and $x_{n-1}=\sigma_{1}$, the last symbol $x_{n}$
could be either $\sigma_{1}$ or $\sigma_{2}$. For the reason that
$N_{\sigma_{1}}({\boldsymbol{x}})=N_{\sigma_{1}}({\boldsymbol{y}})$ and
$N_{\sigma_{2}}({\boldsymbol{x}})=N_{\sigma_{2}}({\boldsymbol{y}})$, we must
have ${\boldsymbol{x}}={\boldsymbol{y}}$, which completes the proof.
$\blacksquare$

######  Construction 7.

For
${\boldsymbol{a}}\in\mathbb{Z}_{3}^{4},{\boldsymbol{b}}\in\mathbb{Z}_{14\log
n}^{4}$ and $c\in\mathbb{Z}_{nq}$, denote the code

$\displaystyle\mathcal{C}_{2}^{D}=\Big{\\{}{\boldsymbol{x}}\in\Sigma^{n}:\widetilde{{\boldsymbol{x}}}\in\mathcal{C}_{2},\sum_{i=1}^{r(\widetilde{{\boldsymbol{x}}})}x_{i}\cdot
R(\widetilde{{\boldsymbol{x}}})_{i}=c\bmod{4n},\text{ and}$ $\displaystyle
N_{\sigma}({\boldsymbol{x}})=a_{\sigma}\bmod 3,{\rm
Sum}({\boldsymbol{x}}^{\sigma})=b_{\sigma}\bmod{14\log n}\text{ for
}\sigma\in\Sigma\Big{\\}}.$

######  Theorem 7.

For
${\boldsymbol{a}}\in\mathbb{Z}_{3}^{4},{\boldsymbol{b}}\in\mathbb{Z}_{14\log
n}^{4}$ and $c\in\mathbb{Z}_{nq}$, the code $\mathcal{C}_{2}^{D}$ is a
quaternary two-deletion correcting code, and there are parameters such the
redundancy of $\mathcal{C}_{2}^{D}$ is at most $5\log n+14\log\log n+O(1)$.

###### Proof:

For ${\boldsymbol{x}}\in\mathcal{C}_{2}^{D}$, denote the erroneous sequence of
${\boldsymbol{x}}$ as ${\boldsymbol{x}}^{\prime}$. Since the signature
$\widetilde{{\boldsymbol{x}}}$ belongs to a binary two-deletion correcting
code $\mathcal{C}_{2}$, so we can recovery $\widetilde{{\boldsymbol{x}}}$ from
$\widetilde{{\boldsymbol{x}}^{\prime}}$. If the two deletions in
$\widetilde{{\boldsymbol{x}}}$ are not consecutive or are consecutive $00$ or
$11$, then by Lemma 13 we can recovery ${\boldsymbol{x}}$ uniquely.

On the other hand, if the two deletions in $\widetilde{{\boldsymbol{x}}}$ are
consecutive $01$ or $10$ in an alternate substring of length greater than $2$,
then we can make sure the locations of these two deletions are in an interval
of length $7\log n$ for the reason that $\widetilde{{\boldsymbol{x}}}$ is
regular. Therefore, the two deletions in ${\boldsymbol{x}}$ is within a window
of length at most $7\log n+1$.

For $\sigma\in\Sigma$, by calculating
$N_{\sigma}({\boldsymbol{x}})-N_{\sigma}({\boldsymbol{x}}^{\prime})\bmod{3}$,
the values of two deleted symbols can be obtained. If there is a
$\sigma\in\Sigma$, such
$N_{\sigma}({\boldsymbol{x}})-N_{\sigma}({\boldsymbol{x}}^{\prime})\bmod{3}=t$,
then the number of $\sigma$ deleted from ${\boldsymbol{x}}$ is $t$. We
consider the two cases whether the two deleted symbols are the same.

  * •

The two deleted symbols are $\sigma_{1}\neq\sigma_{2}$:
We prove that inserting $\sigma_{1}$ and $\sigma_{2}$ into
${\boldsymbol{x}}^{\prime}$ can only get ${\boldsymbol{x}}$ if we want to keep
${\rm Sum}({\boldsymbol{x}}^{\sigma})=b_{\sigma}\bmod{14\log n}$ for all
$\sigma\in\Sigma$. Otherwise, suppose there is another way to insert
$\sigma_{1}$ and $\sigma_{2}$ satisfying the constraints, and the resultant
sequence is denoted as ${\boldsymbol{y}}$. Let $i_{1}$ and $i_{2}$ denote the
indices of the deleted $\sigma_{1}$ and $\sigma_{2}$ in ${\boldsymbol{x}}$,
and $\\{j_{1},j_{2}\\}$ denote the set of indices of the inserted $\sigma_{1}$
and $\sigma_{2}$ in ${\boldsymbol{y}}$. Without loss of generality, we assume
$i_{1}\leq j_{1}$, $i_{1}<i_{2}$, and $j_{1}<j_{2}$. By Lemma 14, we have
$i_{2}=i_{1}+\epsilon_{1}$ and $j_{2}=j_{1}+\epsilon_{2}$, where
$\epsilon_{1},\epsilon_{2}\in\\{1,2\\}$. We claim that $j_{2}>i_{2}$.
Otherwise if $j_{2}\leq i_{2}$, then to make sure
${\boldsymbol{x}}\neq{\boldsymbol{y}}$ we must have $\epsilon_{1}=2$, and
$j_{2}=i_{2}=j_{1}+1$ or $j_{1}=i_{1}=j_{2}-1$. In the case of
$j_{2}=i_{2}=j_{1}+1$, we have
${\boldsymbol{x}}_{[i_{1},i_{2}]}=\sigma_{1}x_{i+1}\sigma_{2}$, and
${\boldsymbol{y}}_{[i_{1},i_{2}]}=x_{i+1}\sigma_{1}\sigma_{2}$ or
$x_{i+1}\sigma_{2}\sigma_{1}$. If $x_{i+1}\leq\sigma_{2}$, then
$\sigma_{1}>x_{i+1}$ by the condition that
$\widetilde{{\boldsymbol{x}}}_{[i_{1},i_{2}]}$ is alternate. So
${\boldsymbol{y}}_{[i_{1},i_{2}]}$ cannot be $x_{i+1}\sigma_{1}\sigma_{2}$ or
$x_{i+1}\sigma_{2}\sigma_{1}$, where both are contradictory to
$\widetilde{{\boldsymbol{x}}}_{[i_{1},i_{2}]}=\widetilde{{\boldsymbol{y}}}_{[i_{1},i_{2}]}$.
If $x_{i+1}>\sigma_{2}$, then $\sigma_{1}\leq x_{i+1}$, and due to
$\widetilde{{\boldsymbol{y}}}_{i_{1}}=\widetilde{{\boldsymbol{x}}}_{i_{1}}=1$
the only possible of ${\boldsymbol{y}}_{[i_{1},i_{2}]}$ will be
$x_{i+1}\sigma_{1}\sigma_{2}$, where $x_{i+1}=\sigma_{1}$. This leads to
${\boldsymbol{x}}={\boldsymbol{y}}$, again a contradiction. The case
$j_{1}=i_{1}=j_{2}-1$ can be proved similarly, so we have $j_{2}>i_{2}$. If
${\boldsymbol{x}}_{[i_{1},j_{2}]}$ consists of $\sigma_{1}$ and $\sigma_{2}$
only, then to keep $\widetilde{{\boldsymbol{x}}}_{[i_{1},j_{2}-1]}$ is an
alternate sequence it has to be ${\boldsymbol{x}}={\boldsymbol{y}}$ by Lemma
15. Thus, there must exist a
$\sigma_{3}\in\Sigma\setminus\\{\sigma_{1},\sigma_{2}\\}$ in
${\boldsymbol{x}}_{[i_{1},j_{2}]}$. Due to
${\boldsymbol{x}}_{[i_{1},j_{2}]\setminus\\{i_{1},i_{2}\\}}={\boldsymbol{y}}_{[i_{1},j_{2}]\setminus\\{j_{1},j_{2}\\}}$
and $i_{1}<i_{2}<j_{2}$, we have

$N_{\sigma_{3}}({\boldsymbol{x}}_{[i_{1},j_{2}]})\leq{\rm
Sum}({\boldsymbol{x}}^{\sigma_{3}})-{\rm
Sum}({\boldsymbol{y}}^{\sigma_{3}})\leq
2N_{\sigma_{3}}({\boldsymbol{x}}_{[i_{1},j_{2}]}),$

which is a contradiction to ${\rm Sum}({\boldsymbol{x}}^{\sigma_{3}})-{\rm
Sum}({\boldsymbol{y}}^{\sigma_{3}})=0\bmod{14\log n}$.

  * •

The two deleted symbols are both equal to $\sigma_{1}$:
Like the previous case, we prove that inserting these two $\sigma_{1}$ into
${\boldsymbol{x}}^{\prime}$ can only get ${\boldsymbol{x}}$ if we want to keep
${\rm Sum}({\boldsymbol{x}}^{\sigma})=b_{\sigma}\bmod{14\log n}$ for all
$\sigma\in\Sigma$. By Lemma 14, the two $\sigma_{1}$ inserted in
${\boldsymbol{x}}^{\prime}$ are consecutive or separated by one position.
Suppose there is another way to insert two $\sigma_{1}$ into
${\boldsymbol{x}}^{\prime}$, and the resultant sequence is
${\boldsymbol{y}}\in\mathcal{C}_{2}^{D}$. We again assume the indices of these
two $\delta_{1}$ in ${\boldsymbol{x}}$ and ${\boldsymbol{y}}$ are
$i_{1}<i_{2}$ and $j_{1}<j_{2}$, respectively. Without loss of generality, let
$i_{1}<j_{1}$. Since ${\boldsymbol{x}}\neq{\boldsymbol{y}}$, there must be a
$\sigma_{2}\in\Sigma\setminus\\{\delta_{1}\\}$ in
${\boldsymbol{x}}_{[i_{1},j_{2}]}$. We can calculate that

$N_{\sigma_{2}}({\boldsymbol{x}}_{[i_{1},j_{2}]})\leq{\rm
Sum}({\boldsymbol{x}}^{\sigma_{2}})-{\rm
Sum}({\boldsymbol{y}}^{\sigma_{2}})\leq
2N_{\sigma_{2}}({\boldsymbol{x}}_{[i_{1},j_{2}]}),$

which contradicts that ${\rm Sum}({\boldsymbol{x}}^{\sigma_{2}})\equiv{\rm
Sum}({\boldsymbol{y}}^{\sigma_{2}})\bmod{14\log n}$.

Now we have proved that we can uniquely recover ${\boldsymbol{x}}$ from two
deletions if the two deletions in $\widetilde{{\boldsymbol{x}}}$ are
consecutive $01$ or $10$ in an alternate substring. Combining with Lemma 13,
the code $\mathcal{C}_{2}^{D}$ is indeed a quaternary two-deletion correcting
code.

For the redundancy, there exist parameters, such that the size of
$\mathcal{C}_{2}^{D}$ is at least

$\frac{4^{n}}{c\cdot n^{4}\cdot(\log n)^{10}\cdot 4n\cdot 3^{4}\cdot(14\log
n)^{4}},$

where $c$ is a constant and from $\mathcal{C}_{2}$. Therefore, the redundancy
is at most $5\log n+14\log\log n+O(1)$. $\blacksquare$

######  Construction 8.

For ${\boldsymbol{c}}\in\mathbb{Z}_{14\log n}^{(M-4M_{1})\times 4}$,
${\boldsymbol{P}}=(P_{1},P_{2})$, where $P_{1},P_{2}\leq 28\log n+5$, we
denote

$\displaystyle\mathcal{C}_{2}^{SD}=$
$\displaystyle\Big{\\{}\mathsf{C}\in(\Sigma^{n})^{M}:{\boldsymbol{c}}_{i}=S_{a_{i}}({\boldsymbol{x}}_{i})\text{
for }i\in[4M_{1}]\text{ where }{\boldsymbol{x}}_{i}\in\mathcal{C}_{2}^{D},$
$\displaystyle\widetilde{{\boldsymbol{c}}_{i}}\in\mathcal{C}_{2}^{\boldsymbol{P}},\text{
and }{\rm Sum}({\boldsymbol{c}}_{i}^{j})=b_{i,j}\bmod{14\log n}$
$\displaystyle\text{for }i\in[4M_{1}+1,M],j\in\Sigma\Big{\\}},$

where for $1\leq i\leq 4M_{1}$, $a_{i}$ is chosen based on Corollary 2.

######  Lemma 16.

$\mathcal{C}_{2}^{\boldsymbol{P}}$ is not only a binary
${\boldsymbol{P}}$-bounded two-deletion correcting code, but also a single-
deletion correcting code.

###### Proof:

From the construction of $\mathcal{C}_{2}^{\boldsymbol{P}}$, every codeword in
$\mathcal{C}_{2}^{\boldsymbol{P}}$ has the form
$({\boldsymbol{z}},0,1,{\mathcal{E}}_{1}({\boldsymbol{z}}),{\mathcal{E}}_{2}({\boldsymbol{z}}),\xi({\mathcal{E}}_{1}({\boldsymbol{z}}),{\mathcal{E}}_{2}({\boldsymbol{z}})))$,
where ${\boldsymbol{z}}\in\\{0,1\\}^{k}$ and
${\mathcal{E}}_{1},{\mathcal{E}}_{2},\xi$ are labeling function we will
describe in Appendix A. As we will show, $\xi({\boldsymbol{z}})$ allows us
recover ${\boldsymbol{z}}$ from two deletions from the erroneous sequence, and
${\mathcal{E}}_{2}$ contains the value ${\rm VT}({\boldsymbol{z}})\bmod k+1$.

When a deletion occurs in a sequence with the form
$({\boldsymbol{z}},0,1,{\mathcal{E}}_{1}({\boldsymbol{z}}),{\mathcal{E}}_{2}({\boldsymbol{z}}),\xi({\mathcal{E}}_{1}({\boldsymbol{z}}),{\mathcal{E}}_{2}({\boldsymbol{z}})))$
and result in ${\boldsymbol{x}}\in\\{0,1\\}^{n-1}$, we first look at the $k+1$
position of ${\boldsymbol{x}}$. If $x_{k+1}$=0, then there is no error in
${\boldsymbol{z}}$, so we can calculate the values
${\mathcal{E}}_{1}({\boldsymbol{x}}_{[k]}),{\mathcal{E}}_{2}({\boldsymbol{x}}_{[k]}),\xi({\mathcal{E}}_{1}({\boldsymbol{x}}_{[k]}),{\mathcal{E}}_{2}({\boldsymbol{x}}_{[k]}))$,
and return
$({\boldsymbol{x}}_{[k]},0,1,{\mathcal{E}}_{1}({\boldsymbol{x}}_{[k]}),{\mathcal{E}}_{2}({\boldsymbol{x}}_{[k]}),\xi({\mathcal{E}}_{1}({\boldsymbol{x}}_{[k]}),{\mathcal{E}}_{2}({\boldsymbol{x}}_{[k]})))$
as the correct sequence. If $x_{k+1}=1$, then the deletion occurs at
${\boldsymbol{z}}$. We use ${\boldsymbol{x}}_{[k-1]}$ and the value ${\rm
VT}({\boldsymbol{z}})\bmod k+1$ in ${\mathcal{E}}_{2}({\boldsymbol{z}})$ to
recover ${\boldsymbol{z}}$, then we return
$({\boldsymbol{z}},{\boldsymbol{x}}_{[k,n]})$ as the correct sequence.
$\blacksquare$

######  Theorem 8.

$\mathcal{C}_{2}^{SD}$ is a $2$-SDCC, and there exist parameters such that the
redundancy is at most $\frac{12}{2-\log 3}(\log n)^{2}+M(2\log n+26\log\log
n+o(\log\log n))-\Omega(\log n\log\log n)$.

###### Proof:

The proof is similar to that of Theorem 6. $\blacksquare$

##  V A Lower Bound on the Redundancy of Known-Synthesis-Defect Correcting
Codes

In this section, we give the lower bound for redundancy on $1$-KDCC using some
tools from graph theory. Specifically, we use the same method as [17, Section
IV] to derive the lower bound for redundancy. First, let us introduce some
definitions.

######  Definition 13.

A collection ${\mathcal{Q}}$ of cliques is a clique cover of a graph
${\mathcal{G}}$ if every vertex in ${\mathcal{G}}$ belongs to some clique in
${\mathcal{Q}}$.

######  Lemma 17 ([18]).

If ${\mathcal{Q}}$ is a clique cover of ${\mathcal{G}}$, then the size of any
independent set of ${\mathcal{G}}$ is at most $|{\mathcal{Q}}|$.

Let the vertices of ${\mathcal{G}}$ to be all quaternary sequences of length
$n$, and two vertices ${\boldsymbol{u}},{\boldsymbol{v}}$ are connected if
there exists a set $\Delta=\\{\delta\\}$, such that
$\mathsf{SynDef}_{\Delta}({\boldsymbol{u}})=\mathsf{SynDef}_{\Delta}({\boldsymbol{v}})$,
where $\delta\in[4n]$. Obviously, an independent set of ${\mathcal{G}}$ is a
$1$-KDCC. By Lemma 17, the upper bound of the size of $1$-KDCC is upper
bounded by the size of any one of clique cover of ${\mathcal{G}}$. Now we give
a construction of a clique cover of ${\mathcal{G}}$.

######  Lemma 18.

There exists a clique cover ${\mathcal{Q}}$ for ${\mathcal{G}}$ and is of size
$4^{n-1}(1+3(\frac{4^{5}-16}{4^{5}})^{\lfloor\frac{n}{5}\rfloor})$.

###### Proof:

Let

$\displaystyle A=\\{11234,12134,12314,12341\\}$ $\displaystyle
B=\\{22341,23241,23421,23412\\}$ $\displaystyle
C=\\{33412,34312,34132,34123\\}$ $\displaystyle
D=\\{44123,41423,41243,41234\\},$

and $E=\Sigma^{5}\setminus(A\cup B\cup C\cup D)$. Furthermore, define

$Z=\left\\{({\boldsymbol{p}},{\boldsymbol{r}},i):{\boldsymbol{p}}\in
E^{i},{\boldsymbol{r}}\in\Sigma^{n-5i-5},i\in\\{0,\ldots,\lfloor\frac{n}{5}\rfloor-1\\}\right\\}.$

For every ${\boldsymbol{z}}=({\boldsymbol{p}},{\boldsymbol{r}},i)\in Z$, we
define

$\displaystyle
Q_{{\boldsymbol{z}}}^{(A)}=\\{{\boldsymbol{p}}{\boldsymbol{q}}{\boldsymbol{r}}:{\boldsymbol{q}}\in
A\\},$ $\displaystyle
Q_{{\boldsymbol{z}}}^{(B)}=\\{{\boldsymbol{p}}{\boldsymbol{q}}{\boldsymbol{r}}:{\boldsymbol{q}}\in
B\\},$ $\displaystyle
Q_{{\boldsymbol{z}}}^{(C)}=\\{{\boldsymbol{p}}{\boldsymbol{q}}{\boldsymbol{r}}:{\boldsymbol{q}}\in
C\\},$ $\displaystyle
Q_{{\boldsymbol{z}}}^{(D)}=\\{{\boldsymbol{p}}{\boldsymbol{q}}{\boldsymbol{r}}:{\boldsymbol{q}}\in
D\\}$

to be the cliques of size 4. For the remaining vertices, we define

$S_{\boldsymbol{x}}=\\{{\boldsymbol{x}}\\},\text{ where }{\boldsymbol{x}}\in
E^{\lfloor\frac{n}{5}\rfloor}\times\Sigma^{n-5\lfloor\frac{n}{5}\rfloor}$

to be the singletons.

Define

$\displaystyle{\mathcal{Q}}=$
$\displaystyle\left\\{Q_{{\boldsymbol{z}}}^{(A)},Q_{{\boldsymbol{z}}}^{(B)},Q_{{\boldsymbol{z}}}^{(C)},Q_{{\boldsymbol{z}}}^{(D)},{\boldsymbol{z}}\in
Z\right\\}\cup$ $\displaystyle\left\\{Q_{\boldsymbol{x}}:{\boldsymbol{x}}\in
E^{\lfloor\frac{n}{5}\rfloor}\times\Sigma^{n-5\lfloor\frac{n}{5}\rfloor}\right\\}.$

To prove that ${\mathcal{Q}}$ is a clique cover, we need to show every set in
${\mathcal{Q}}$ is a clique and all vertices in these sets cover the whole
space $\Sigma^{n}$.

First, for every ${\boldsymbol{x}}\in
E^{\lfloor\frac{n}{5}\rfloor}\times\Sigma^{n-5\lfloor\frac{n}{5}\rfloor}$, the
set $Q_{\boldsymbol{x}}$ has only one element and thus is a clique.

Then, for ${\boldsymbol{z}}\in Z$, the set $Q_{{\boldsymbol{z}}}^{(A)}$ has
$4$ elements, which are
${\boldsymbol{p}}11234{\boldsymbol{r}},{\boldsymbol{p}}12134{\boldsymbol{r}},{\boldsymbol{p}}12314{\boldsymbol{r}},{\boldsymbol{p}}12341{\boldsymbol{r}}$.
Suppose
$\mathsf{cycle}({\boldsymbol{p}}11234{\boldsymbol{r}})_{|{\boldsymbol{p}}|+2}=\delta$,
then
$\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{p}}11234{\boldsymbol{r}})=\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{p}}12134{\boldsymbol{r}})=\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{p}}12314{\boldsymbol{r}})=\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{p}}12341{\boldsymbol{r}})$,
so they are connected to each other and thus $Q_{{\boldsymbol{z}}}^{(A)}$ is a
clique. Similarly,
$Q_{{\boldsymbol{z}}}^{(B)}$,$Q_{{\boldsymbol{z}}}^{(C)}$,$Q_{{\boldsymbol{z}}}^{(D)}$
are all cliques.

For a vertex ${\boldsymbol{v}}\in\Sigma^{n}$, if there exists a
$i\in\\{0,\ldots,\lfloor\frac{n}{5}\rfloor-1\\}$, such that
$v_{[5i+1,5i+5]}\in A\cup B\cup C\cup D$, then ${\boldsymbol{v}}\in
Q_{\boldsymbol{z}}^{(A)}$ or $Q_{\boldsymbol{z}}^{(B)}$ or
$Q_{\boldsymbol{z}}^{(C)}$ or $Q_{\boldsymbol{z}}^{(D)}$ for some
${\boldsymbol{z}}=({\boldsymbol{p}},{\boldsymbol{r}},i)$. If no such $i$
exists, then ${\boldsymbol{v}}\in S_{\boldsymbol{v}}$. Therefore, we conclude
that ${\mathcal{Q}}$ is a clique cover.

For the size of ${\mathcal{Q}}$, we calculate as follows. For every
${\boldsymbol{z}}\in Z$, there are $4$ cliques of
$Q_{{\boldsymbol{z}}}^{(A)},Q_{{\boldsymbol{z}}}^{(B)},Q_{{\boldsymbol{z}}}^{(C)}$
and $Q_{{\boldsymbol{z}}}^{(D)}$. The size of $Z$ is

$\sum_{i=0}^{\lfloor\frac{n}{5}\rfloor-1}(4^{5}-16)^{i}4^{n-5i-5}.$

So there are total $4|Z|$ cliques of size $4$. On the other side, the size of
singleton is

$(4^{5}-16)^{\lfloor\frac{n}{5}\rfloor}4^{n-5\lfloor\frac{n}{5}\rfloor}.$

Therefore,

$\displaystyle|{\mathcal{Q}}|$
$\displaystyle=4\sum_{i=0}^{\lfloor\frac{n}{5}\rfloor-1}(4^{5}-16)^{i}4^{n-5i-5}+(4^{5}-16)^{\lfloor\frac{n}{5}\rfloor}4^{n-5\lfloor\frac{n}{5}\rfloor}$
$\displaystyle=4^{n-1}(1+3(\frac{4^{5}-16}{4^{5}})^{\lfloor\frac{n}{5}\rfloor}).$

$\blacksquare$

######  Theorem 9.

Let $\mathcal{C}\subseteq\Sigma^{n}$ be a $1$-KDCC, then the redundancy of
$\mathcal{C}$ is at least $\log 4-o(1)$.

###### Proof:

An independent set of ${\mathcal{G}}$ has the property that for any
${\boldsymbol{u}},{\boldsymbol{v}}\in{\mathcal{G}}$,
$\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{u}})\cap\mathsf{SynDef}_{\\{\delta\\}}({\boldsymbol{v}})=\varnothing$
for $\delta\in[4n]$. This means an independent set of ${\mathcal{G}}$ is a
$1$-KDCC. By Lemma 17, the size of any independent set is upper bounded by the
size of a clique cover of ${\mathcal{G}}$, and we can construct a clique cover
of size $4^{n-1}(1+3(\frac{4^{5}-16}{4^{5}})^{\lfloor\frac{n}{5}\rfloor})$ by
Lemma 18. So the size of a $1$-KDCC is upper bounded by
$4^{n-1}(1+3(\frac{4^{5}-16}{4^{5}})^{\lfloor\frac{n}{5}\rfloor})$, and the
redundancy of it is at least
$n-\log(4^{n-1}(1+3(\frac{4^{5}-16}{4^{5}})^{\lfloor\frac{n}{5}\rfloor}))=1-o(1)$.
$\blacksquare$

With this theorem, it follows that the $1$-KDCC $\mathcal{C}_{1}^{KDCC}(n;a)$
we construct is almost optimal.

##  VI Conclusion and Future Work

We investigate codes correcting synthesis defects and provide two type of
codes to correct this error. In the first one, we assume we have already known
the information of defective cycles. Although this seems to provide sufficient
information about the errors, it is not enough to recover the strand. We
construct $t$-KDCCs for $t=1,2$, and this shows the strategy to construct
$t$-KDCC for general $t$. Besides, we derive a bound on the size of $1$-KDCC,
which shows our construction for $1$-KDCC is almost optimal. In the second
type of codes, each codeword is a set of $M$ sequence, and they share the same
synthesis defects. We utilize this feature, and provide $t$-SDCCs for $t=1,2$,
where each codeword is divided into two parts with different coding schemes.
The redundancy of our $t$-SDCCs is roughly $\lambda_{1}(\log n)^{2}+M\log\log
n$ and $\lambda_{2}(\log n)^{2}+2M\log n$ for $t=1,2$, repectively, for some
constants $\lambda_{1}$ and $\lambda_{2}$. In contrast, if we employ the best
existing single deletions and two-deletion correcting codes for each sequence,
then the redundancy for $1$ and $2$-SDCC will be at least $M\log n$ and
$4M\log n$.

As explained in Section III-A, if we want to construct a $t$-KDCC, then if
suffices to construct a binary ${\boldsymbol{P}}$-bounded $t$-deletion
correcting code. We only provide this code for $t=2$ in this paper, and the
cases for $t>2$ are left to the future.

For the $t$-SDCC, we only provide the constructions for $t\leq 2$. The case
$t\geq 3$ is far more complicated. Even if we locate each defect in a small
interval, we cannot tell which cycles are defective in a sequence. For
example, three cycles $\delta_{1},\delta_{2},\delta_{3}$ are defective, but if
there is a sequence suffers from $2$ deletions, then we do not know these two
deletions are caused by $\delta_{1},\delta_{2}$ or $\delta_{2},\delta_{3}$ or
$\delta_{1},\delta_{3}$. So, it is not enough to let it belongs to only a
$(P_{1},P_{2},P_{3})$-bounded $3$-deletion correcting code. Even if it also
belongs to a $(P_{1},P_{2})$-bounded $2$-deletion correcting code, we cannot
recover it because we do not know the two interval. The problem of
constructing $t$-SDCCs for $t\geq 3$ is left for future work.

## References

  * [1] S. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao, and O. Milenkovic, “Dna-based storage: Trends and methods,” _IEEE Transactions on Molecular, Biological and Multi-Scale Communications_ , vol. 1, no. 3, pp. 230–248, 2015.
  * [2] I. Shomorony and R. Heckel, “Information-theoretic foundations of dna data storage,” _Foundations and Trends® in Communications and Information Theory_ , vol. 19, no. 1, pp. 1–106, 2022.
  * [3] M. Yu, X. Tang, Z. Li, W. Wang, S. Wang, M. Li, Q. Yu, S. Xie, X. Zuo, and C. Chen, “High-throughput dna synthesis for data storage,” _Chemical Society Reviews_ , 2024.
  * [4] L. Ceze, J. Nivala, and K. Strauss, “Molecular digital data storage using dna,” _Nature Reviews Genetics_ , vol. 20, no. 8, pp. 456–466, 2019.
  * [5] A. Lenz, Y. Liu, C. Rashtchian, P. H. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Coding for efficient dna synthesis,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 2885–2890.
  * [6] A. Lenz, S. Melczer, C. Rashtchian, and P. H. Siegel, “Multivariate analytic combinatorics for cost constrained channels and subsequence enumeration,” _arXiv preprint arXiv:2111.06105_ , 2021.
  * [7] K. Makarychev, M. Z. Rácz, C. Rashtchian, and S. Yekhanin, “Batch optimization for dna synthesis,” _IEEE Transactions on Information Theory_ , vol. 68, no. 11, pp. 7454–7470, 2022.
  * [8] O. Elishco and W. Huleihel, “Optimal reference for dna synthesis,” _IEEE Transactions on Information Theory_ , 2023.
  * [9] M. Abu-Sini, A. Lenz, and E. Yaakobi, “Dna synthesis using shortmers,” in _2023 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2023, pp. 585–590.
  * [10] J. Chrisnata and H. M. Kiah, “Deletion correcting codes for efficient dna synthesis,” in _2023 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2023, pp. 352–357.
  * [11] J. Lietard, A. Leger, Y. Erlich, N. Sadowski, W. Timp, and M. M. Somoza, “Chemical and photochemical error rates in light-directed synthesis of complex dna libraries,” _Nucleic acids research_ , vol. 49, no. 12, pp. 6687–6701, 2021.
  * [12] C. Schoeny, A. Wachter-Zeh, R. Gabrys, and E. Yaakobi, “Codes correcting a burst of deletions or insertions,” _IEEE Transactions on Information Theory_ , vol. 63, no. 4, pp. 1971–1985, 2017.
  * [13] G. Tenengolts, “Nonbinary codes, correcting single deletion or insertion (corresp.),” _IEEE Transactions on Information Theory_ , vol. 30, no. 5, pp. 766–769, 1984.
  * [14] V. Guruswami and J. Håstad, “Explicit two-deletion codes with redundancy matching the existential bound,” _IEEE Transactions on Information Theory_ , vol. 67, no. 10, pp. 6384–6394, 2021.
  * [15] R. R. Varshamov and G. Tenenholtz, “A code for correcting a single asymmetric error,” _Automatica i Telemekhanika_ , vol. 26, no. 2, pp. 288–292, 1965.
  * [16] S. Liu, I. Tjuawinata, and C. Xing, “Explicit construction of q-ary 2-deletion correcting codes with low redundancy,” _IEEE Transactions on Information Theory_ , 2024.
  * [17] J. Chrisnata, H. M. Kiah, and E. Yaakobi, “Correcting deletions with multiple reads,” _IEEE Transactions on Information Theory_ , vol. 68, no. 11, pp. 7141–7158, 2022.
  * [18] D. E. Knuth, “The sandwich theorem,” _The Electronic Journal of Combinatorics_ , vol. 1, no. 1, 1994.
  * [19] J. Sima, N. Raviv, and J. Bruck, “Two deletion correcting codes from indicator vectors,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2375–2391, 2019.

##  Appendix A Construction of P-bounded two-deletion correcting code for
large P

To correct two deletions where each deletion is within an interval of length
$P_{i}$, we distinguish if the two intervals are adjacent or not.

1) When the two intervals are adjacent or intersect

Denote $\rho=P_{1}+P_{2}$ and

$I_{i}=\begin{cases}[(i-1)\rho+1,(i+1)\rho],&\mbox{for }i\in\\{1,\ldots,\lceil
n/\rho\rceil-2\\},\\\ [(i-1)\rho+1,n],&\mbox{for }i=\lceil
n/\rho\rceil-1.\end{cases}$

######  Lemma 19 ([19, Theorem 1]).

For any integer $n\geq 3$, there exist a sketch function
$\xi:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{r_{0}(n)}$, computable in linear time,
such that for any ${\boldsymbol{x}}\in\\{0,1\\}^{n}$, given
$\xi({\boldsymbol{x}})$ and ${\boldsymbol{x}}_{[n]\setminus\\{i,j\\}}$, one
can uniquely recover ${\boldsymbol{x}}$, where $i,j\in[n]$, where
$r_{0}(n)=7\log n+O(\log\log n)$.

######  Construction 9.

Define
${\mathcal{E}}_{1}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{r_{1}(P_{1},P_{2})}$ as
follows:
for ${\boldsymbol{x}}\in\\{0,1\\}^{n}$,

$\displaystyle{\mathcal{E}}_{1}({\boldsymbol{x}})=$
$\displaystyle\Big{(}\sum_{j=1}^{\lceil\frac{\lceil
n/\rho\rceil-1}{2}\rceil}\xi({\boldsymbol{x}}_{I_{2j-1}})\bmod
2^{7\log\rho+O(\log\log\rho)},$ $\displaystyle\sum_{j=1}^{\lfloor\frac{\lceil
n/\rho\rceil-1}{2}\rfloor}\xi({\boldsymbol{x}}_{I_{2j}})\bmod
2^{7\log\rho+O(\log\log\rho)}\Big{)},$

where $r_{1}(P_{1},P_{2})=14\log\rho+O(\log\log\rho)$

######  Lemma 20.

For any integers $P_{1},P_{2}\geq 2$ and $n\geq 3$, there exists a sketch
function
${\mathcal{E}}_{1}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{r_{1}(P_{1},P_{2})}$,
computable in linear time, such that for any
${\boldsymbol{x}}\in\\{0,1\\}^{n}$, if ${\boldsymbol{x}}^{\prime}$ is obtained
by deleting two bits at two adjacent or overlapping intervals of lengths
$P_{1},P_{2}$, then given ${\mathcal{E}}_{1}({\boldsymbol{x}})$ and
${\boldsymbol{x}}^{\prime}$ together with the locations of this two intervals,
we can uniquely recover ${\boldsymbol{x}}$, where
$r_{1}(P_{1},P_{2})=14\log(P_{1}+P_{2})+O(\log\log(P_{1}+P_{2}))$

###### Proof:

As ${\boldsymbol{x}}^{\prime}$ is obtained by deleting two bits at two
adjacent or overlapping intervals of lengths $P_{1},P_{2}$, the locations of
two deletions are within an interval $I$ of length $\rho=P_{1}+P_{2}$.
Furthermore, there exists a $j\in[\lceil\frac{n}{\rho}\rceil-1]$, such that
$I\subseteq I_{j}$. Since $I_{j}=[(j-1)\rho+1,(j+1)\rho]$, we know
${\boldsymbol{x}}^{\prime}_{[(j-1)\rho+1,(j+1)\rho-2]}$ is a subsequence of
${\boldsymbol{x}}_{[(j-1)\rho+1,(j+1)\rho]}$, and
${\boldsymbol{x}}_{[n]\setminus[(j-1)\rho+1,(j+1)\rho]}={\boldsymbol{x}}^{\prime}_{[n-2]\setminus[(j-1)\rho+1,(j+1)\rho-2]}$.
So we can get $\xi({\boldsymbol{x}}_{I_{j}})\bmod
2^{7\log\rho+O(\log\log\rho)}$ from ${\mathcal{E}}_{1}({\boldsymbol{x}})$. By
Lemma 19, given $\xi({\boldsymbol{x}}_{I_{j}})$,
${\boldsymbol{x}}^{\prime}_{[(j-1)\rho+1,(j+1)\rho-2]}$, we can uniquely
recover ${\boldsymbol{x}}_{I_{j}}$, so ${\boldsymbol{x}}$ is recovered.
$\blacksquare$

2) When the two intervals are separated by at least one symbol

We use the same analytical approach as in [14]. First, we use
$f_{0}({\boldsymbol{x}})=\sum_{i=1}^{n}x_{i}\bmod 3$ to identify the following
3 cases:

  * i)

the two deleted symbols are both $0$;

  * ii)

the two deleted symbols are both $1$;

  * iii)

the two deleted symbols are $1$ and $0$.

Besides, we need two more functions:

$f_{1}({\boldsymbol{x}})=\sum_{i=1}^{n}ix_{i},$

and

$f_{2}({\boldsymbol{x}})=\sum_{i=1}^{n}\binom{i}{2}x_{i}.$

######  Lemma 21 ([14, Lemma 5]).

If we have deleted two $1$’s or two $0$’s in forming the subsequence
${\boldsymbol{x}}^{\prime}$ from ${\boldsymbol{x}}$, then
$f_{1}({\boldsymbol{x}})$ and $f_{2}({\boldsymbol{x}})$ together with
${\boldsymbol{x}}^{\prime}$ identify ${\boldsymbol{x}}$ uniquely.

######  Lemma 22 ([14, Observation 2]).

If we have deleted a $0$ and a $1$ from two nonadjacent intervals respectively
in forming the subsequence ${\boldsymbol{x}}^{\prime}$ from
${\boldsymbol{x}}$, then $f_{1}({\boldsymbol{x}})$ and
$f_{2}({\boldsymbol{x}})$ together with ${\boldsymbol{x}}^{\prime}$ identify
${\boldsymbol{x}}$ uniquely.

###### Proof:

As in [14], we insert a $0$ and a $1$ as far right as possible in the two
intervals of ${\boldsymbol{x}}^{\prime}$ to make the value of
$f_{1}({\boldsymbol{x}})$ correct.

When we move the $0$ left passing a $1$, the value of
$f_{1}({\boldsymbol{x}})$ increases $1$, so we need to move the $1$ in the
other interval left passing a $0$ to keep the value of
$f_{1}({\boldsymbol{x}})$ constant. During this process, the order of the $0$
and $1$ will keep, since the moving bits in the left interval will never move
to the right interval. So by Lemma 2 and Observation 2 of [14], there will
never happen an overtake event, so $f_{2}({\boldsymbol{x}})$ will be
monotonically increasing or decreasing in the process. $\blacksquare$

Combining Lemma 21 and 22, we can prove that if we have
${\boldsymbol{x}}^{\prime}$ together with
$f_{0}({\boldsymbol{x}}),f_{1}({\boldsymbol{x}}),f_{2}({\boldsymbol{x}})$,
then ${\boldsymbol{x}}$ can be uniquely recover knowing the two nonadjacent
intervals of two deletions located. Now we need to determine how many values
do we need for $f_{1}({\boldsymbol{x}})$ and $f_{2}({\boldsymbol{x}})$.

Since the two deleted bits can only move within their intervals, the bits
outside these two intervals will keep their contributions to
$f_{1}({\boldsymbol{x}})$ and $f_{2}({\boldsymbol{x}})$. So it suffices to
consider the bits in these two intervals.

First we consider $f_{1}({\boldsymbol{x}})$. We analysize case by case:

  * i)

the two deleted symbols are both $0$: For the $i$th interval, its contribution
to $f_{1}({\boldsymbol{x}})$ will increase at most $P_{i}-1$ during the
process of $0$ moving left. So $f_{1}({\boldsymbol{x}})$ will increase at most
$P_{1}+P_{2}-2$.

  * ii)

the two deleted symbols are both $1$: For the $i$th interval, its contribution
to $f_{1}({\boldsymbol{x}})$ will increase at most $P_{i}-1$ during the
process of $1$ moving rihgt. So $f_{1}({\boldsymbol{x}})$ will increase at
most $P_{1}+P_{2}-2$.

  * iii)

the two deleted symbols are $1$ and $0$: The value of
$f_{1}({\boldsymbol{x}})$ is least when $1$ is inserted in the front of the
first interval and $0$ is inserted in the end of the second interval, and is
largest when $0$ is inserted in the front of the first interval and $1$ is
inserted in the end of the second interval. The difference of them is
$j_{2}+P_{2}-1-j_{1}<n$, where $j_{i}$ is the first index of $i$th interval.

Therefore, it has at most $n$ values for $f_{1}({\boldsymbol{x}})$, so it
suffices to apply modular $n$.

Now we consider $f_{2}({\boldsymbol{x}})$. Since we must keep
$f_{1}({\boldsymbol{x}})$ constant when we insert the two bits in
${\boldsymbol{x}}^{\prime}$, we do not have to consider all the possibilities
of insertions. There are at most $\min\\{P_{1},P_{2}\\}$ possibilities of
insertions to keep $f_{1}({\boldsymbol{x}})$ constant. By [14, Lemma 2], we
can easily identify the extremal values of $f_{2}({\boldsymbol{x}})$.

  * i)

the two deleted symbols are both $0$: The value of $f_{2}({\boldsymbol{x}})$
will increase by $\binom{j+1}{2}-\binom{j}{2}=j$ if the moving $0$ moves left
passing a $1$ located at $j$, and will decrease by
$\binom{i}{2}-\binom{i-1}{2}=i-1$ if the moving $0$ moves right passing a $1$
located at $i$. First we insert the two $0$’s as far away from each other as
possible to keep $f_{1}({\boldsymbol{x}})$ correct. Then, every time we move
the left $0$ right passing a $1$ located at $i$, the right $0$ need to be
moved left passing a $1$ located at $j$. In this process,
$f_{2}({\boldsymbol{x}})$ will increase $j-i+1$. Suppose the indices of $1$’s
in the left interval are $\\{i_{1},\ldots,i_{p}\\}$, and in the right interval
are $\\{j_{1},\ldots,j_{q}\\}$, where $p<P_{1}$ and $q<P_{2}$. When the two
moving $0$’s are as far close to each other as possible, the value of
$f_{2}({\boldsymbol{x}})$ grows to maximum, and will increase at most
$\sum_{k=1}^{\min\\{p,q\\}}(j_{k}-i_{k}+1)<\min\\{P_{1},P_{2}\\}n$ compared to
the beginning.

  * ii)

the two deleted symbols are both $1$: The value of $f_{2}({\boldsymbol{x}})$
will decrease by $\binom{i+1}{2}-\binom{i}{2}=i$ if the moving $1$ moves left
passing a $0$ located at $i$, and will increase by
$\binom{j}{2}-\binom{j-1}{2}=j-1$ if the moving $1$ moves right passing a $0$
located at $j$. First we insert the two $1$’s as far close to each other as
possible to keep $f_{1}({\boldsymbol{x}})$ correct. Then, every time we move
the left $1$ left passing a $0$ located at $i$, the right $1$ need to be moved
right passing a $0$ located at $j$. In this process, $f_{2}({\boldsymbol{x}})$
will increase $j-i-1$. Suppose the indices of $0$’s in the left interval are
$\\{i_{1},\ldots,i_{p}\\}$, and in the right interval are
$\\{j_{1},\ldots,j_{q}\\}$, where $p<P_{1}$ and $q<P_{2}$. When the two moving
$1$’s are as far away from each other as possible, the value of
$f_{2}({\boldsymbol{x}})$ grows to maximum, and will increase at most
$\sum_{k=1}^{\min\\{p,q\\}}(j_{k}-i_{k}-1)<\min\\{P_{1},P_{2}\\}n$ compared to
the beginning.

  * iii)

the two deleted symbols are $1$ and $0$: By Lemma 22, The moving bits can
never change their intervals. So we can consider the two case separately.

    * –

$0$ is inserted at the first interval, and $1$ the second. Similar to the
above two cases, we insert $0$ and $1$ as left as possible to keep
$f_{1}({\boldsymbol{x}})$ correct. Once we move $0$ right passing a $1$
located at $i$, $1$ need to be moved right passing a $0$ located at $j$.
$f_{2}({\boldsymbol{x}})$ will increase by $j-i$ in this process. When the two
moving $0$ and $1$ are as far right as possible, the value of
$f_{2}({\boldsymbol{x}})$ will increase at most $\min\\{P_{1},P_{2}\\}n-1$.

    * –

$1$ is inserted at the first interval, and $0$ the second. Similar to the
previous, $f_{2}({\boldsymbol{x}})$ will increase at most
$\min\\{P_{1},P_{2}\\}n-1$.

Therefore, it has at most $\min\\{P_{1},P_{2}\\}n$ values for
$f_{2}({\boldsymbol{x}})$, so it suffices to apply modular
$\min\\{P_{1},P_{2}\\}n$ for $f_{2}({\boldsymbol{x}})$.

######  Construction 10.

Define
${\mathcal{E}}_{2}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{r_{2}(n,P_{1},P_{2})}$
as follows:
for ${\boldsymbol{x}}\in\\{0,1\\}^{n}$,

$\displaystyle{\mathcal{E}}_{2}({\boldsymbol{x}})=\Big{(}$ $\displaystyle
f_{0}({\boldsymbol{x}})\bmod 3,f_{1}({\boldsymbol{x}})\bmod n+1,$
$\displaystyle f_{2}({\boldsymbol{x}})\bmod Pn\Big{)},$

where $r_{2}(n,P_{1},P_{2})=2\log n+\log P+O(1)$.

By Lemma 21 and 22, and the above analysis for ranges of
$f_{1}({\boldsymbol{x}})$ and $f_{2}({\boldsymbol{x}})$, we have the following
lemma.

######  Lemma 23.

For any integers $P_{1},P_{2}\geq 2$ and $n\geq 3$, there exists a sketch
function
${\mathcal{E}}_{2}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{r_{2}(n,P_{1},P_{2})}$,
computable in linear time, such that for any
${\boldsymbol{x}}\in\\{0,1\\}^{n}$, if ${\boldsymbol{x}}^{\prime}$ is obtained
by deleting two bits at two non-overlapping intervals of lengths
$P_{1},P_{2}$, then given ${\mathcal{E}}_{2}({\boldsymbol{x}})$ and
${\boldsymbol{x}}^{\prime}$ together with the locations of this two intervals,
we can uniquely recover ${\boldsymbol{x}}$, where $r_{2}(n,P_{1},P_{2})=2\log
n+\log P+O(1)$.

######  Construction 11.

Define ${\mathcal{E}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n+r(n,P_{1},P_{2})}$
as follows:
for ${\boldsymbol{x}}\in\\{0,1\\}^{n}$,

${\mathcal{E}}({\boldsymbol{x}})=\Big{(}{\boldsymbol{x}},{\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}}),\xi({\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}}))\Big{)},$

where
$r(n,P_{1},P_{2})=r_{1}(P_{1},P_{2})+r_{2}(n,P_{1},P_{2})+r_{0}(r_{1}(P_{1},P_{2})+r_{2}(n,P_{1},P_{2}))=2\log
n+7\log\log n+14\log(P_{1}+P_{2})+\log P+O(\log\log(P_{1}+P_{2}))$.

###### Proof:

To be convenient, we omit the parameters of $r_{0},r_{1},r_{2}$ and $r$, and
use them to denote the lengths of
$\xi({\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}})),{\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}})$
and ${\mathcal{E}}({\boldsymbol{x}})$, respectively. Since we know the
information of the two intervals, we can distinguish if the two intervals are
separated.

  * •

If the intervals do not intersect with $[n]$: we know the part of
${\boldsymbol{x}}$ is correct, so just set
${\boldsymbol{x}}={\mathcal{E}}^{\prime}({\boldsymbol{x}})_{[n]}$.

  * •

If the intervals intersect with $[n]$:

    * –

if the two intervals are not separated, we first recover
${\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}})$ from
${\mathcal{E}}({\boldsymbol{x}})_{[n+r_{1}+r_{2}+1,n+r-2]}$ and
${\mathcal{E}}({\boldsymbol{x}})_{[n+1,n+r_{1}+r_{2}-2]}$. It is obvious that
${\mathcal{E}}({\boldsymbol{x}})_{[n+r_{1}+r_{2}+1,n+r-2]}$ is a subsequence
of
$\xi({\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}}))$
of length $r_{0}-2$, and
${\mathcal{E}}({\boldsymbol{x}})_{[n+1,n+r_{1}+r_{2}-2]}$ is a subsequence of
${\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}})$ of
length $r_{1}+r_{2}-2$. By Lemma 19, we can recover
${\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}})$.
Then, we can recovery ${\boldsymbol{x}}$ by using
${\mathcal{E}}({\boldsymbol{x}})_{[1,n-2]}$ and
${\mathcal{E}}_{1}({\boldsymbol{x}})$ by Theorem 20.

    * –

if the two intervals are separated, similar to above, we can recover
${\mathcal{E}}_{1}({\boldsymbol{x}}),{\mathcal{E}}_{2}({\boldsymbol{x}})$, and
we use ${\mathcal{E}}({\boldsymbol{x}})_{[1,n-2]}$ and
${\mathcal{E}}_{2}({\boldsymbol{x}})$ to recover ${\boldsymbol{x}}$ by Theorem
23.

$\blacksquare$