1

Mutually Uncorrelated Primers for DNA-Based
Data Storage
S. M. Hossein Tabatabaei Yazdi∗ , Han Mao Kiah† , Ryan Gabrys∗ and Olgica Milenkovic∗

arXiv:1709.05214v1 [] 13 Sep 2017

∗ ECE

Department, University of Illinois, Urbana-Champaign

Abstract—We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNAbased data storage systems and for synchronization of communication devices. WMU sequences are characterized by the
property that no sufficiently long suffix of one sequence is
the prefix of the same or another sequence. WMU sequences
used for primer design in DNA-based data storage systems are
also required to be at large mutual Hamming distance from
each other, have balanced compositions of symbols, and avoid
primer-dimer byproducts. We derive bounds on the size of WMU
and various constrained WMU codes and present a number of
constructions for balanced, error-correcting, primer-dimer free
WMU codes using Dyck paths, prefix-synchronized and cyclic
codes.

1. I NTRODUCTION
Mutually uncorrelated (MU) codes are a class of fixed
length block codes in which no proper prefix of one codesequence is a suffix of the same or another codesequence. MU
codes have been extensively studied in the coding theory and
combinatorics literature under a variety of names. Levenshtein
introduced the codes in 1964 under the name ‘strongly regular
codes’ [1], and suggested that the codes be used for synchronization. For frame synchronization applications described by
van Wijngaarden and Willink in [2], Bajić and Stojanović [3]
rediscovered MU codes, and studied them under the name
of ‘cross-bifix-free’ codes. Constructions and bounds on the
size of MU codes were also reported in a number of recent
contributions [4], [5]. In particular, Blackburn [5] analyzed
these sequences under the name of ‘non-overlapping codes’,
and provided a simple construction for a class of codes with
optimal cardinality.
MU codes have recently found new applications in DNAbased data storage [6], [7]: In this setting, Yazdi et al. [8], [9]
developed a new, random-access and rewritable DNA-based
data storage architecture that uses MU address sequences that
allow selective access to encoded DNA blocks via Polymerase
Chain Reaction (PCR) amplification with primers complementary to the address sequences. In a nutshell, DNA informationbearing sequences are prepended with address sequences used
to access strings of interest via PCR amplification. To jump
start the amplification process, one needs to ‘inject’ complements of the sequences into the storage system, and those
complementary sequences are referred to as DNA primers.
Primers attach themselves to the user-selected address strings
and initiate the amplification reaction. In order to ensure
accurate selection and avoid expensive postprocessing, the
information sequences following the address are required to
Parts of the work were presented at ISIT 2016, Barcelona, Spain. The
research is supported in part by the NSF CCF 16-18366 grant.

† SPMS,

Nanyang Technological University, Singapore

avoid sequences that resemble the addresses, thereby imposing
a special coding constraint that may be met through the use
of MU addresses. In addition, the addressing scheme based on
MU codes may be used in conjunction with other specialized
DNA-based data storage codes like the ones outlined in [10]–
[12]. Detailed descriptions of implementations of DNA-based
data storage systems and their underlying synthetic biology
principles are beyond the scope of this paper; the interested
reader is referred to [13] for a discussion of system components and constraints.
The goal of this work is to generalize the family of MU
codes by introducing weakly mutually uncorrelated (WMU)
codes. WMU codes are block codes in which no sufficiently
long prefix of one codesequence is a suffix of the same or
another codesequence. In contrast, MU codes prohibit suffixprefix matches of any length. This relaxation of prefix-suffix
constraints was motivated in [8], with the purpose of improving code rates and allowing for increased precision DNA
fragment assembly and selective addressing. A discussion of
the utility of WMU codes in DNA-based data storage may be
found in the overview paper [9], [13] and the paper describing
recent practical implementations of portable DNA-based data
storage systems which make use of WMU codes [14].
Here, we are concerned with determining bounds on the
size of specialized WMU codes and efficient WMU code constructions. Of interest are both binary and quaternary WMU
codes, as the former may be used to construct the latter, while
the latter class may be adapted for encoding over the four
letter DNA alphabet {A, T, C, G}. Our contributions include
bounds on the largest size of unconstrained and constrained
WMU codes, constructions of WMU codes that meet the
derived upper bounds as well as results on several important
constrained versions of WMU codes: Error-correcting WMU
codes, balanced WMU codes, balanced error-correcting WMU
codes, and WMU codes that avoid primer-dimer byproducts.
The aforementioned constraints arise due to the following
practical considerations.
A binary sequence is called balanced if half of its symbols
are zero. On the other hand, a DNA sequence is termed
balanced if it has a 50% GC content (i.e., if 50% of the
symbols in the sequence are either G or C). Balanced DNA
sequences are more stable than DNA sequences with lower or
higher GC content and they have lower sequencing error-rates.
Balanced DNA sequences are also easier to synthesize than
unbalanced sequences [15]. In addition, WMU codes at large
Hamming distance limit the probability of erroneous codesequence selection dues to address errors. When referring to
primer dimer (PD) issues [16], we consider potential problems
that may arise during random access when two primers used

2

for selection bond to each other, thereby prohibiting amplification of either of the two corresponding information-bearing
sequences. PD byproducts can be eliminated by restricting the
WMU codes to avoid simultaneous presence of long substrings
and their complements in the codesequences.
The paper is organized as follows. Section 2 contains an
overview of the topics and results discussed in the paper
and some formal definitions needed to follow the material in
subsequent sections. In Section 3 we review MU and introduce
WMU codes, and derive bounds on the maximum size of the
latter family of combinatorial objects. In addition, we outline
a construction of WMU codes that meets the derived upper
bound. We also describe a construction that uses binary MU
component codes and other constrained codes in order to obtain families of WMU codes that obey different combinations
of primer constraints. In Section 4 we describe constructions
for error-correcting WMU codes, while in Section 5 we discuss
balanced WMU codes. Primer-dimer constraints are discussed
in Section 6. Our main results are presented in Section 7,
where we first propose to use cyclic codes to devise WMU
codes that are both balanced and have error correcting capabilities. We then proceed to improve the cyclic code construction
in terms of coding rate through decoupled constrained and
error-correcting coding for binary strings. In this setting, we
use DC-balanced codes [17]. Encoding of information with
WMU address codes is described in Section 8.
2. ROADMAP OF A PPROACHES AND R ESULTS
Throughout the paper we use the following notation: Fq
stands for a finite field of order q ≥ 2. Two cases of special
interest are q = 2 and q = 4. In the latter case, we tacitly
identify the elements of F4 with the four letters of the DNA
code alphabet, {A, T, C, G}. We let a = (a1 , . . . , an ) ∈ Fnq
stand for a sequence of length n over Fq , and let aji , 1 ≤
i, j ≤ n, stand for a substring of a starting at position i and
ending at position j, i.e.,
(
(ai , . . . , aj )
i≤j
j
ai =
(ai , ai−1 , . . . , aj ) i > j.
Moreover, for two arbitrary sequences a ∈ Fnq , b ∈ Fm
q , we
use ab = (a1 , . . . , an , b1 , . . . , bm ) to denote a sequence of
length n+m generated by appending b to the right of a. Thus,
al stands for a sequence of length ln comprising l consecutive
copies of the sequence a.
We say that a sequence ā = (a¯1 , . . . , a¯n ) ∈ Fnq represents
the complement of sequence a ∈ Fnq if:
• For q = 2, and 1 ≤ i ≤ n,
(
1 if ai = 0,
āi =
(1)
0 if ai = 1;
•

For q = 4, and 1 ≤ i ≤ n,


T if

A if
āi =
G if



C if

ai
ai
ai
ai

= A,
= T,
= C,
= G.

(2)

The notion of complement used for F4 is often referred to as
the Watson-Crick (W-C) complement.
In this work, we define an (address) code C of length n as
a collection of sequences from Fnq , for q ∈ {2, 4}, satisfying
a set of specific combinatorial constraints described below.
The goal is to describe new constructions for address sequences used for DNA-based data storage. Address sequences
should enable reliable access to desired information content.
This is accomplished by making the addresses as distinguishable from each other as possible via a simple minimum Hamming distance constraint; recall that the Hamming distance dH
between any two sequences of length n, a = (a1 , . . . , an ) and
b = (b1 , . . . , bn ), over some finite alphabet A equals
dH (a, b) =

n
X

1(ai 6= bi ),

i=1

where 1(·) stands for the indicator function. One may also use
the Levenshtein distance instead, as discussed in the context
of MU codes in [18].
Access to desired sequences is accomplished by exponentially amplifying them within the pool of all sequences via
addition of primer sequences corresponding to the W-C complement of their addresses. As primers have to be synthesized,
they need to satisfy constraints that enable simplified synthesis,
such as having a balanced GC-content,
formally defined for
Pn
n
a sequence a over Fn4 as
1(a
i ∈ {G, C}) = 2 .
i=1
This constraint directly translates to a balancing property
for the address sequences. Furthermore, as one may require
simultaneous amplification of multiple sequences, multiple
primers need to be added in which case it is undesirable
for different pairs of primers to bond to each other via WC complementarity. The PD byproducts of this binding may
be significantly reduced if one imposes an additional PD
constraint on the primers, and hence on the address sequences,
as defined below.
Definition 1. A set of sequences C ⊆ Fnq , for q ∈ {2, 4},
is said to avoid primer dimer (APD) byproducts of effective
length f if substrings of sequences in C with length ≥ f
cannot hybridize with each other in the forward or the reverse
direction. More precisely, we say that C is an f -APD code if
for any two sequences a, b ∈ C, not necessarily distinct, and
1 ≤ i, j ≤ n + 1 − f, we have āfi +i−1 6= bfj +j−1 , bjf +j−1 . We
refer to the sequence bjf +j−1 as the reverse of the sequence
bjf +j−1 .
For practical reasons, we only focus on the parameter
regime f = Θ (n), as only sufficiently long complementary
sequences may bond with each other. Furthermore, we defer
the study of the related problem of secondary structure formation [19], [20] to future work.
In certain DNA-based data storage systems, one may be
interested in restricting the address sequences by imposing
only one or two of the above constraints. For example, if
the addresses are relatively short (≤ 10), one may dispose
of the requirement to make the sequences balanced, as short
sequences are significantly easier to synthesize than longer
ones. If one allows for postprocessing of the readouts, then the

3

Hamming distance constraint may be relaxed or completely
removed. It is for this reason that we also consider a more
general class of code constructions that accommodate only a
subset of the three previously described constraints.
By far the most important constraint imposed on the address sequences is that they enable a simple construction
of information-bearing sequences (assumed to be of length
N >> n) that do not contain any of the address sequences
of length n as substrings. It is in this context of forbidden
substring coding that MU codes were introduced in [21],
[22]. WMU codes may be used in the same setting, but they
are less restrictive than MU codes, and therefore allow for
larger codebooks. This is why our main results pertain to
constructions of WMU codes with various subsets of primer
constraints, and we formally define and discuss these codes in
the next section. For some related questions pertaining to MU
codes, the interested reader is referred to [18].
3. MU AND WMU C ODES : D EFINITIONS , B OUNDS AND
C ONSTRUCTIONS
For simplicity of notation, we adopt the following naming
convention for codes: If a code C ⊆ Fnq has properties
Property1 , Property2 , . . . , Propertys , then we say that C is a
Property1 _Property2 _ . . . , Propertys _q_n code, and use
the previous designation in the subscript.
A. Mutually Uncorrelated Codes
Fnq

is selfWe say that a sequence a = (a1 , . . . , an ) ∈
uncorrelated if no proper prefix of a matches its suffix, i.e.,
if (a1 , . . . , ai ) 6= (an−i+1 , . . . , an ), for all 1 ≤ i < n. This
definition may be extended to a set of sequences as follows:
Two not necessarily distinct sequences a, b ∈ Fnq are said to
be mutually uncorrelated if no proper prefix of a appears as a
suffix of b and vice versa. We say that C ⊆ Fnq is a mutually
uncorrelated (MU) code if any two not necessarily distinct
codesequences in C are mutually uncorrelated.
The maximum cardinality of MU codes was determined
up to a constant factor by Blackburn [5, Theorem 8]. For
completeness, we state the modified version of this result for
alphabet size q ∈ {2, 4} below
Theorem 1. Let AMU_q_n denote the maximum size of a
MU_q_n code, with n ≥ 2 and q ∈ {2, 4}. Then
cq

qn
qn
≤ AMU_q_n ≤
n
2n

2

where cq = (q−1)4q(2q−1)
, which for q = 2 and q = 4 equal
4
c2 = 0.04688 and c4 = 0.06152, respectively.
We also briefly outline two known constructions of MU
codes, along with a new and simple construction for errorcorrecting MU codes that will be used in our subsequent
derivations.
Bilotta et al. [4] described an elegant construction for
MU codes based on well-known combinatorial objects termed
Dyck sequences. A Dyck sequence of length n is a binary
sequence composed of n2 zeros and n2 ones such that no prefix
of the sequence has more zeros than ones. By definition, a

Dyck sequence is balanced and it necessarily starts with a one
and ends with a zero. The number of Dyck word
of length n

n
2
is the n2 -th Catalan number, equal to n+2
n .
2

Construction 1. (BAL_MU_2_n Codes) Consider a set D of
Dyck sequences of length n − 2 and define the following set
of sequences of length n,
C = {1a0 : a ∈ D}.
It is straightforward to show that C is balanced and MU
code. Size of C is also equal to n−2
2 -th Catalan number, or
n
1
|C| = 2(n−1)
n .
2
An important observation is that MU codes constructed
using Dyck sequences are inherently balanced, as they contain
n
n
2 ones and 2 zeros. The balancing property also carries over
to all prefixes of certain subsets of Dyke sequences. To see
this, recall that a Dyck sequence has height at most D if for
any prefix of the sequence, the difference between the number
of ones and the number of zeros is at most D. Hence, the
disbalance of any prefix of a Dyck sequence of height D
is at most D. Let Dyck(n, D) denote the number of Dyck
sequences of length 2n and height at most D. For fixed values
of D, de Bruijn et al. [23] proved that




π
π
4n
2
2n
tan
cos
. (3)
Dyck(n, D) ∼
D+1
D+1
D+1
Here, f (n) ∼ g(n) is used to denote the following asymptotic
relation limm→∞ f (n)/g(n) = 1.
Bilotta’s construction also produces nearly prefix-balanced
MU codes, provided that one restricts his/her attention to
subsets of sequences with small disbalance D; equation 3
establishes the existence of large subsets of Dyck sequences
with small disbalance. By mapping 0 and 1 to {A, T} and
{C, G}, respectively, one may enforce a similar GC balancing
constraint on DNA MU codes.
The next construction of MU codes was proposed by
Levenshtein [1] and Gilbert [21].
Construction 2. (MU_q_n Codes) Let n ≥ 2 and 1 ≤ ` ≤
n−1, be two integers and let C ⊆ Fnq be the set of all sequences
a = (a1 , . . . , an ) such that
•
•
•

The sequence a starts with ` consecutive zeros, i.e., a`1 =
0` .
It holds that a`+1 , an 6= 0.
The subsequence an−1
`+2 does not contain ` consecutive
zeros as a subsequence.

Then, C is an
Blackburn [5, Lemma 3] showed
 MU code.

that when ` = logq 2n and n ≥ 2`+2 the above construction
is optimal. His proof relies on the observation that the number
of strings an−1
`+2 that do not contain ` consecutive zeros as a
2
subsequence exceeds (q−1)4nq(2q−1)
q n , thereby establishing the
4
lower bound of Theorem 1. The aforementioned result is a
simple consequence of the following lemma.
Lemma 1. The number of q-ary sequences of length n that
avoid t specified sequences in Fnq s as substrings is greater than
q n (1 − qnt
ns ).

4

Proof: The result obviously holds for n ≤ ns . If n ≥ ns ,
then the number of bad strings, i.e., q-ary strings of length n
that contain at least one of the specified t strings as a substring,
is bounded from above by:

To maximize nH = t (` − 1) given n = (t + 1) ` + 1 and
t, ` ≥ 1, we write
p
√
nH = n − (` + t + 1) ≤ n − 2 `(t + 1) = n − 2 n − 1.

#bad strings ≤ (n − ns + 1)tq n−ns

Here, the inequality follows from
p the arithmetic and geometric
` (t + 1). On the other hand,
≥
mean inequality, i.e., `+t+1
2
it is √
easy to verify that√this upper bound is achieved by setting
` = n − 1 and t = √n − 1 − 1. Hence, the maximum value
of nH is n∗H = n − 2 n − 1.
By using a code CH with parameters [n∗H , s, d] as specified
n∗
by the GV bound, where d ≤ 2H and s = n∗H (1 − h( nd∗ ) −
H
o(1)), we obtain an
MU code Cparse with
q error-correcting
p
parameters [n∗H + 2 n∗H + 2 n∗H − 1 − 1, n∗H (1 − h( nd∗ ) −
H
o(1)), d].

≤ ntq n−ns .
Hence, the number of good sequences, i.e., the number of qary sequences of length n that avoid t specified strings in Fnq s
as substrings, is bounded from below by
#good strings ≥ q n − #bad strings
nt
≥ q n (1 − ns ).
q
It is straightforward to modify Construction 2 so as to incorporate error-correcting redundancy. Our constructive approach
to this problem is outlined in what follows.
Construction 3. (Error − Correcting_MU_2_n Codes) Fix
two positive integers t and ` and consider a binary (nH , s, d)
code CH of length nH = t(` − 1), dimension s, and Hamming
distance d. For each codesequence b ∈ CH , we map b to a
sequence of length n = (t + 1)` + 1 given by
2(`−1)

a(b) = 0` 1b`−1
1 1b`

t(`−1)

1 · · · b(t−1)(`−1)+1 1.

Let Cparse , {a(b) : b ∈ CH }.
It is easy to verify that |Cparse | = |CH |, and that the
code Cparse has the same minimum Hamming distance as
CH , i.e., d(Cparse ) = d(CH ). As nH = t(` − 1), we also
n
have Cparse ⊆ {0, 1} , where n = (t + 1)` + 1. In addition,
the parsing code Cparse is an MU code, since it satisfies all
the constraints required by Construction 2. To determine the
largest asymptotic size of a parsing code, we recall the GilbertVarshamov bound.
Theorem 2. (Asymptotic Gilbert-Varshamov bound [24],
[25]) For any two positive integers n and d ≤ n2 , there exists
n
a block code C ⊆ {0, 1} of minimum Hamming distance d
with normalized rate
 
d
R(C) ≥ 1 − h
− o(1),
n
where h(·) is the binary entropy function, i.e., h(x) =
1
x log2 x1 + (1 − x) log2 1−x
, for 0 ≤ x ≤ 1.
Recall that the parameters s (dimension) and d (minimum
Hamming distance) of the codes CH and Cparse are identical.
Their lengths, nH and n, respectively, equal nH = t (` − 1)
and n = (t + 1) ` + 1, where t, ` are positive integers. We
next aim to optimize the parameters of the parsing code for
fixed s and fixed n, which amounts to maximizing d. Since d
is equal to the corresponding minimum distance of the code
CH , and both codes have the same dimension s, in order to
maximize d we maximize nH under the constraint that n is
fixed. More precisely, we optimize the choice of `, t and then
use the resulting parameters in the Gilbert-Varshamov lower
bound.

B. Weakly Mutually Uncorrelated Codes: Definitions, Bounds
and Constructions
The notion of mutual uncorrelatedness may be relaxed by
requiring that only sufficiently long prefixes of one sequence
do not match sufficiently long suffixes of the same or another
sequence. A formal definition of this property is given next.
Definition 2. Let C ⊆ Fnq and 1 ≤ κ < n. We say that C is a
κ-weakly mutually uncorrelated (κ-WMU) code if no proper
prefix of length l, for all l ≥ κ, of a codesequence in C appears
as a suffix of another codesequence, including itself.
Our first result pertains to the size of the largest WMU code.
Theorem 3. Let Aκ−WMU_q_n denote the maximum size of a
κ-WMU code over Fnq , for 1 ≤ κ < n and q ∈ {2, 4}. Then,
qn
qn
≤ Aκ−WMU_q_n ≤
,
n−κ+1
n−κ+1
where the constant cq is as described in Theorem 1.
cq

Proof: To prove the upper bound, we use an approach first
suggested by Blackburn in [5, Theorem 1], for the purpose of
analyzing MU codes. Assume that C ⊆ Fnq is a κ-WMU code.
Let L = (n + 1) (n − κ + 1) − 1, and consider the set X of
pairs (a, i) , where i ∈ {1, . . . , L}, and where a ∈ FL
q is such
that the (possibly cyclically wrapped) substrings of a of length
n starting at position i belongs to C. Note that our choice of
the parameter L is governed by the overlap length κ.
Clearly, |X| = L |C| q L−n , since there are L different
possibilities for the index i, |C| possibilities for the string
starting at position i of a, and q L−n choices for the remaining
L − n ≥ 0 symbols in a. Moreover, if (a, i) ∈ X, then
(a, j) ∈
/ X for j ∈ {i ± 1, . . . , i ± n − κ}mod L due to the
weak mutual uncorrelatedness property.
Hence,
for a fixed
j
k
L
L
string a ∈ Fq , there are at most n−κ+1 different pairs


(a, i1 ) , . . . , a, ib L c ∈ X. This implies that
n−κ+1


L
|X| ≤
qL .
n−κ+1
Combining the two derived constraints on the size of X, we
obtain


L
|X| = L |C| q L−n ≤
qL .
n−κ+1

5

n

q
Therefore, |C| ≤ n−κ+1
.
To prove the lower bound, we describe a simple WMU code
construction, outlined in Construction 4.

Construction 4. (κ − WMU_q_n Codes) Let κ, n be two integers such that 1 ≤ κ ≤ n. A κ-WMU code C ∈ Fnq
may be constructed using a simple concatenation of the form
C = {ab | a ∈ C1 , b ∈ C2 }, where C1 ⊆ Fn−κ+1
is an MU
q
code, and C2 ⊆ Fκ−1
is
unconstrained.
q
It is easy to verify that C is an κ-WMU code with |C1 | |C2 |
codesequences. Let C2 = Fκ−1
and let C1 ⊆ Fn−κ+1
q
q
be the largest MU code of size AMU_q_n−κ+1 . Then, |C| =
q κ−1 AMU_q_n−κ+1 . The claimed lower bound now follows
from the
lower bound of Theorem 1, establishing that |C| ≥
qn
.
cq n−κ+1
As described in the Introduction, κ-WMU codes used in
DNA-based storage applications are required to satisfy a
number of additional combinatorial constraints in order to be
used as blocks addresses. These include the error-correcting,
balancing and primer dimer constraints. Balancing and errorcorrecting properties of codesequences have been studied
in great depth, but not in conjunction with MU or WMU
codes. The primer dimer constraint has not been previously
considered in the literature.
In what follows, we show that all the above constraints can
be imposed on κ-WMU codes via a simple decoupled binary
code construction. To this end, let us introduce a mapping Ψ as
follows. For any two binary sequences a = (a1 , . . . , an ) , b =
n
n
n
(b1 , . . . , bn ) ∈ {0, 1} , Ψ (a, b) : {0, 1} × {0, 1} →
n
{A, T, C, G} is an encoding function that maps the pair a, b
n
to a DNA string c = (c1 , . . . , cn ) ∈ {A, T, C, G} , according
to the following rule:

A if (ai , bi ) = (0, 0)



T if (a , b ) = (0, 1)
i i
(4)
for 1 ≤ i ≤ n, ci =

C
if
(a
,
b
)
=
(1,
0)
i
i



G if (ai , bi ) = (1, 1) .
Clearly, Ψ is a bijection and Ψ(a, b)Ψ(c, d) = Ψ(ac, bd).
The next lemma lists a number of useful properties of Ψ.

(ii) We prove the result by contradiction. Suppose that C
is not a κ-WMU code while C1 is a κ-WMU code.
Then, there exist sequences c, c0 ∈ C such that a proper
prefix of c of length at least κ appears as a suffix of
c0 . Alternatively, there exist sequences p, c0 , c00 such that
c = pc0 , c0 = c00 p and the length of p is at least κ. Next,
we use the fact Ψ is a bijection and find binary strings
a, b, a0 , b0 such that
p = Ψ (a, b) , c0 = Ψ (a0 , b0 ) , c00 = Ψ (a00 , b00 ) .
Therefore,
c = pc0 = Ψ (a, b) Ψ (a0 , b0 ) = Ψ (aa0 , bb0 ) ,
c0 = c00 p = Ψ (a00 , b00 ) Ψ (a, b) = Ψ (a00 a, b00 b) ,
where aa0 , a00 a ∈ C1 . This implies that the string a of
length at least κ appears both as a proper prefix and
suffix of two not necessarily distinct elements of C1 . This
contradicts the assumption that C1 is a κ-WMU code. The
same argument may be used for the case that C2 is a κWMU code.
(iii) For any two distinct sequences c, c0 ∈ C there exist
a, a0 ∈ C1 , b, b0 ∈ C2 such that c = Ψ (a, b) , c0 =
Ψ (a0 , b0 ). The Hamming distance between c, c0 equals
X
X
1 (ci 6= c0i ) =
1 (ai 6= a0i ∨ bi 6= b0i )
1≤i≤n

1≤i≤n

(
d1
≥
d2

if a 6= a0
≥ min (d1 , d2 ) .
if b =
6 b0

This proves the claimed result.
(iv) By combining (1), (2) and (4), one can easily verify
that Ψ(a, b) = Ψ a, b . We again prove the result by
contradiction. Suppose that C is not an f -APD code.
Then, there exist c, c0 ∈ C, a, a0 ∈ C1 , b, b0 ∈ C2
such that c = Ψ (a, b) , c0 = Ψ (a0 , b0 ) and cfi +i−1 =
(c0 )jf +j−1 or (c0 )jf +j−1 , for some 1 ≤ i, j ≤ n + 1 − f .
f +i−1

= (b0 )jf +j−1 or (b0 )jf +j−1 ,
This implies that bi
which contradicts the assumption that C2 is an f -APD
code.

n

Lemma 2. Suppose that C1 , C2 ⊆ {0, 1} are two binary block
codes of length n. Encode pairs of codesequences (a, b) ∈
C1 × C2 into a code C = {Ψ (a, b) | a ∈ C1 , b ∈ C2 }. Then:
(i) If C1 is balanced, then C is balanced.
(ii) If either C1 or C2 are κ-WMU codes, then C is also an
κ-WMU code.
(iii) If d1 and d2 are the minimum Hamming distances of
C1 and C2 , respectively, then the minimum Hamming
distance of C is at least min (d1 , d2 ).
(iv) If C2 is an f -APD code, then C is also an f -APD code.
Proof:
(i) Any c ∈ C may be written as c = Ψ (a, b) , where
a ∈ C1 , b ∈ C2 . According to (4), the number of G, C
symbols in c equals the number of ones in a. Since a is
balanced, exactly half of the symbols in c are Gs and Cs.
This implies that C has balanced GC content.

In the next sections, we devote our attention to establishing
bounds on the size of WMU codes with error-correction,
balancing and primer dimer constraints, and to devising constructions that use the decoupling principle or more specialized
methods that produce larger codebooks. As the codes C1 and
C2 in the decoupled construction have to satisfy two or more
properties in order to accommodate all required constraints,
we first focus on families of binary codes that satisfy one or
two primer constraints.
4. E RROR -C ORRECTING WMU C ODES
The decoupled binary code construction result outlined in
the previous section indicates that in order to construct an
error-correcting κ-WMU code over F4 , one needs to combine
a binary error-correcting κ-WMU code with a classical errorcorrecting code. To the best of our knowledge, no results are

6

available on error-correcting MU or error-correcting κ-WMU
codes.
We start by establishing lower bounds on the coding rates
for error-correcting WMU codes using the constrained GilbertVarshamov bound [24], [25].
For a ∈ Fnq and an integer r ≥ 0, let BFnq (a, r) denote the
Hamming sphere of radius r centered around a, i.e.,

BFnq (a, r) = b ∈ Fnq | dH (a, b) ≤ r ,
where, as before, dH denotes the Hamming distance. Clearly,
the cardinality of BFnq (a, r) equals

r 
X
n
i
Vq (n, r) =
(q − 1) ,
i
i=0

independent on the choice of the center of the sphere. For the
constrained version of Gilbert-Varshamov bound, let X ⊆ Fnq
denote an arbitrary subset of Fnq . For a sequence a ∈ X, define
the Hamming ball of radius r in X by

and
L2 =

i=0

n−κ−`
i



i

(q − 2) Vq (κ − 1, d − i − 2) .

Proof: Assume that X is a κ-WMU code over Fnq generated according to Construction
4 and such that it has the carqn
. Recall that in this
dinality at least cq n−κ+1
 case, X is the set
of sequences a ∈ Fnq that start with ` = logq 2 (n − κ + 1)
consecutive zeros (a`1 = 0` ), a`+1 , an−κ+1 6= 0, and no ` consecutive zeros appears as a subsequence in an−κ
`+2 . With every
a ∈ X, we associate two sets X (a, d − 1) and Y (a, d − 1):
The set X (a, d − 1) includes sequences b ∈ Fnq that satisfy
the following three conditions:
`
`
• Sequence b starts with ` consecutive zeros, i.e., b1 = 0 .
• One has b`+1 6= 0.

n
n
• Sequence b satisfies dH a`+1 , b`+1 ≤ d − 1.
The set Y (a, d − 1) ⊆ X (a, d − 1) is the collection of
n−κ
sequences b that contain 0` as a subsequence in b`+2
, or
that satisfy bn−κ+1 = 0. Therefore,

BX (a, r) = BFnq (a, r) ∩ X.

BX (a, d − 1) = X (a, d − 1) /Y (a, d − 1) ,

The volumes of the spheres in X may depend on the choice
of a ∈ X. Of interest is the maximum volume of the spheres
of radius r in X,
VX,max (r) = max |BX (a, r)| .

and
|BX (a, d − 1) | = |X (a, d − 1) | − |Y (a, d − 1) |.
Let L0 = |X (a, d − 1)|. Thus,

a∈X

The constrained version of the GV bound asserts that there
exists a code of length n over X, with minimum Hamming
distance d that contains
|X|
M≥
VX,max (d − 1)
codesequences. Based on the constrained GV bound, we can
establish the following lower bound for error-correcting WMU
codes. The key idea is to use a κ-WMU subset as the ground
set X ⊆ Fnq .
Theorem 4. (Lower bound on the maximum size of errorcorrecting WMU codes.) Let κ and n be two integers such
that n − κ − 1 ≥ 2`, for ` = logq 2 (n − κ + 1) , q ∈ {2, 4}.
Then there exists a κ-WMU code C ⊆ Fnq with minimum
Hamming distance d and cardinality
qn
|C| ≥ cq
,
(n − κ + 1) (L0 − L1 − L2 )

(5)

where
2

cq =

n−κ−`
X 

(q − 1) (2q − 1)
,
4q 4

and L0 , L1 , and L2 , are given by
L0 =Vq (n − ` − 1, d − 1) + (q − 2) Vq (n − ` − 1, d − 2) ,

L0 =Vq (n − ` − 1, d − 1) + (q − 2) Vq (n − ` − 1, d − 2) .
(6)
The result holds as the first term on the right hand side of the
equation counts the number of sequences b ∈ X (a, d − 1)
that satisfy b`+1 = a`+1 , while the second term counts those
sequences for which b`+1 6= a`+1 .
We determine next |Y (a, d − 1) |. For this purpose, we look
into two disjoints subsets Y I and Y II in Y (a, d − 1) which
allow us to use |Y (a, d − 1)| ≥ Y I + Y II and establish a
lower bound on the cardinality sought.
The set Y I is defined according to
YI =

n−κ−`+1
[

Y I (i) ,

i=`+2
I

where Y (i) is the set of sequences b ∈ X (a, d − 1) that
satisfy the following constraints:
`
• The sequence b contains the substring 0 starting at
i+`−1
`
position i, i.e., bi
=0 .
• It holds that bi−1 6= 0.
i−2
`
• The sequence 0 does not appears as a substring in b`+2 .


i−1
i−1
n
n
• One has dH a`+1 , b`+1 + dH ai+` , bi+` ≤ d − ` − 1.
I
The cardinality of Y (` + 2) can be found according to
Y I (` + 2) =Vq (n − 2` − 1, d − ` − 1)
+ (q − 2) Vq (n − 2` − 1, d − ` − 2)

L1 = (q − 1)

n−κ−`+1
X



i−`−2
X 


i=`+2

j=0

i−`−2
j

×Vq (n − i − ` + 1, d − ` − j − 2))] ,



j

(q − 2)

≥ (q − 1) Vq (n − 2` − 1, d − ` − 2)
The first term on the right hand side of the above equality
counts the sequences b ∈ Y I (` + 2) for which b`+1 =
a`+1 , while the second term counts sequences for which

7

b`+1 6= a`+1 . The inequality follows from the fact that
Vq (n − 2` − 1, d − ` − 1) ≥ Vq (n − 2` − 1, d − ` − 2).
To evaluate the remaining terms Y I (i)for ` + 3 ≤ i ≤
i−2
n − κ − ` + 1, assume that dH ai−2
`+1 , b`+1 = j. In this case,
there are at least


i−`−2
j
(q − 2)
j
possible choices for bi−2
`+1 . This result easily follows from
counting the number of ways to select the j positions in ai−2
`+1
on which the sequences agree and the number of choices for
the remaining symbols which do not include the corresponding
values in a and 0. As no additional symbol 0 is introduced in
i−2
i−2
`
bi−2
`+1 , b`+2 does not contain the substring 0 as a`+2 avoids
that string; similarly, b`+1 6= 0.
On the other hand, there are q − 1 possibilities for bi−1 ∈
Fq \ {0}, and to satisfy the distance property we have to have

dH ani+` , bni+` ≤ d − ` − j − 2.
Therefore,


i−`−2
X 

Y I (i) ≥ (q − 1) 

j=0

i−`−2
j



j

(q − 2)

×Vq (n − i − ` + 1, d − ` − j − 2)] .
Hence, the cardinality of Y I may be bounded from below as
Y I ≥LI ,
where
LI = (q − 1)

n−κ−`+1
X



i−`−2
X 


j=0

i=`+2

i−`−2
j


(q − 2)

×Vq (n − i − ` + 1, d − ` − j − 2))] .

(7)

It is easy to verify that
Y II ⊆ X (a, d − 1) \ [BX (a, d − 1) ∪ YI ] .
Following the same arguments used in establishing the bound
on the cardinality of Y II , on can show that
Y II ≥L2 ,
where
n−κ−`
X 
i=0

n−κ−`
i



i

(q − 2) Vq (κ − 1, d − i − 2) .
(8)

As a result, for each a ∈ X, we have
|BX (a, d − 1)| = |X (a, d − 1)| − |Y (a, d − 1)|
≤L0 − L1 − L2 .

VX,max (d − 1) ≤ L0 − L1 − L2 .
This inequality, along with the constrained form of the GV
bound, establishes the validity of the claimed result.
Figure 1 plots the above derived lower bound on the maximum achievable rate for error-correcting κ-WMU codes (5),
and for comparison, the best known error-correcting linear
codes for binary alphabets. The parameters used are n =
50, κ = 1, q = 2, corresponding to MU codes.
To construct q = 4-ary error-correcting κ-WMU codes via
the decoupled construction, we need to have at our disposition
an error-correcting κ-WMU binary code. In what follows, we
use ideas similar to Tavares’ synchronization technique [26]
to construct such codes. We start with a simple lemma and a
short justification for its validity.
Lemma 3. Let C be a cyclic code of dimension κ. Then the
run of zeros in any nonzero codesequence is at most κ − 1.
Proof: Assume that there exists a non-zero codesequence
c(x), represented in polynomial form, with a run of zeroes of length κ. Since the code is cyclic, one may write
c(x) = a(x)g(x), where a(x) is the information sequence
corresponding to c(x) and g(x) is the generator polynomial
of the code. Without loss of generality, one may assume that
the
P run of zeros appears at positions 0, . . . , κ − 1, so that
i+j=s ai gj = 0, for s ∈ {0, . . . , κ − 1}. The solution of
the previous system of equations gives a0 = a1 = . . . =
aκ−1 = 0, contradicting the assumption that c(x) is non-zero.

j

The set Y II comprises the set of sequences in b ∈
X (a, d − 1) that have the following properties:
n−κ
`
• The sequence 0 does not appear as a substring in b`+2 .
• It holds bn−κ+1 = 0.
• One has


n−κ
n
n
dH an−κ
`+1 , b`+1 + dH an−κ+2 , bn−κ+2 ≤ d − 2.

L2 =

Note that L0 , L1 , L2 are independent from a. Therefore,

Construction 5. (d − HD_κ − WMU_q_n Codes) Construct a
code C ⊆ Fnq according to
C = {a + e | a ∈ C1 , e = (1, 0, . . . , 0)}
where C1 is a [n, κ − 1, d] cyclic code.
We argue that C is a κ-WMU code, with minimum Hamming distance d. To justify the result, we first demonstrate
the property of weakly mutually uncorrelatedness. Suppose
that on the contrary the code is C is not κ-WMU. Then there
exists a proper prefix p of length at least κ such that both pa
and bp belong to C. In other words, the sequences (pa) − e
and (bp) − e belong to C1 . Consequently, (pb) − e0 belongs
to C1 , where e0 is a cyclic shift of e. Hence, by linearity
of C1 , z , 0(a − b) + e0 − e belongs to C1 . Now, observe
that the first coordinate of z is one, and hence nonzero. But
z has a run of zeros of length at least κ − 1, which is a
contradiction. Therefore, C is indeed a κ-WMU code. Since
C is a coset of C1 , the minimum Hamming distance property
follows immediately.
As an example, consider the family of primitive binary terror-correcting BCH codes with parameters [n = 2m − 1, ≥
n − mt, ≥ 2t + 1]. The family is cyclic, and when used in
Construction 5, it results in an error-correcting (n − mt + 1)WMU code of minimum distance 2t + 1. The rate of such a
≥ 1 − 2mmt−1 , while according to the Theorem
code is n−mt
n
3, the cardinality of the optimal-order corresponding κ-WMU

8

Error-correcting linear code
Error-correcting MU code

1.0

Relative rate

0.8
0.6
0.4
0.2
0.0

0

10

20
30
Hamming distance

40

50

Figure 1. Comparison of two different lower bounds for binary codes: Error-correcting MU codes (inequality (5) of Theorem 4) and the best known linear
error-correcting codes; n = 50, κ = 1, as κ = 1-WMU codes are MU codes.

code is at least
rate of at least

0.04688×2n
,
mt
n

corresponding to an information

)
log( 0.04688×2
5 + log (mt)
mt
>1−
.
(9)
n
2m − 1
As an illustration, we compare the rates of the BCH-based
κ-WMU and the optimal κ-WMU codes for different values
of m = 10, t = 1, 3, 5:
(i) m = 10, t = 1: In this case our BCH code has length
1023, dimension 1013, and minimum Hamming distance
3. This choice of a code results in a binary 1014WMU code with minimum Hamming distance 3, and
information rate 0.9902, while the optimal binary 1014WMU code has information rate greater than 0.9919.
(ii) m = 10, t = 3: In this case our BCH code has length
1023, dimension 993, and minimum Hamming distance 7.
This choice of a code results in a binary 994-WMU code
with minimum Hamming distance 7, and information rate
0.9707, while the optimal binary 994-WMU code has
information rate greater than 0.9903.
(iii) m = 10, t = 5: In this case our BCH code has length
1023, dimension 973, and minimum Hamming distance
11. This choice of a code results in a binary 974WMU code with minimum Hamming distance 11, and
information rate 0.9511, while the optimal binary 974WMU code has information rate greater than 0.9896.
Next, we present a construction for MU ECC codes of
length n, minimum Hamming distance 2t + 1 and of size
roughly (t + 1) log n. This construction outperforms the previous approach for codes of large rate, whenever t is a small
constant.
Assume that one is given a linear code of length n0 and
minimum Hamming distance dH = 2t + 1, equipped with
0
a systematic encoder EH (n0 , t) : {0, 1}κ → {0, 1}n −κ which
inputs κ information bits and outputs n0 −κ parity bits. We feed
into the encoder EH sequences u ∈ {0, 1}κ that do not contain

runs of zeros of length ` − 1 or more, where ` = log(4n0 ). Let
p = d n0κ−κ e > `. The MU ECC codesequences are of length
n = n0 + ` + 2, and obtained according to the constrained
information sequence u as:
2p
1
2
(0, 0 . . . , 0, 1, up
1 ,EH (u)1 , up+1 , EH (u)2 ,
0

0

n −κ
3
n
u3p
2p+1 ,EH (u)3 . . . , u(n0 −κ−1)p+1 , EH (u)n0 −κ , 1).

The codesequences start with the 0` 1 substring, and are
followed by sequences u interleaved with parity bits, which
are inserted every p > ` positions. Notice that the effect of the
inserted bits is that they can extend the lengths of existing runs
of zeros in u by at most one. Since u has no runs of lengths
` − 1 or more this means that we do not see any runs of zeros
of length ≥ ` in the last n − ` − 1 bits of x. This implies
that the underlying code is MU, while the ECC properties are
inherited from the initial linear code.
5. BALANCED κ-WMU C ODES
In what follows, we focus on the analysis of balanced κWMU codes, and start with a review of known bounds on the
number of balanced binary sequences.
Let Ad−HD_2_n denote the maximum size of a binary code
of length n and minimum Hamming distance d, and let
Aw−CST_d−HD_2_n denote the maximum cardinality of a binary
code with constant weight w, length n and even minimum
Hamming distance dH . Clearly,
 
n
n
A 2 −CST_2−HD_2_n = n .
2

Gyorfi et al. [27] derived several bounds for the more general
function Aw−CST_d−HD_2_n based on Ad−HD_2_n .
Theorem 5. For even integer d, 0 ≤ d ≤ n, and every w,
0 ≤ w ≤ n,

n
w

2n−1

Ad−HD_2_n ≤ Aw−CST_d−HD_2_n .

9

We present next our first construction of balanced κ-WMU
codes.
Construction 6. (BAL_κ − WMU_4_n Codes) Form a code C ∈
n
{A, T, C, G} using the decoupled construction with component
codes C1 and C2 chosen according to the following rules:
n
• Let C1 ⊆ {0, 1} be a balanced code of size equal to
n
A 2 −CST_2−HD_2_n .
n
• Let C2 ⊆ {0, 1}
be a κ-WMU code; one may use
Construction 4 to generate C2 .
n

Lemma 4. Let C ∈ {A, T, C, G} denote the code generated
by Construction 6. Then,
(i) C is a κ-WMU code.
(ii) C is balanced.
Proof:
(i) Since C2 is a κ-WMU code, property ii) of Lemma 2
ensures that C is also a κ-WMU code.
(ii) Since C1 is balanced, property i) of Lemma 2 ensures that
C is a balanced binary code.
This completes the proof.
We discuss next the cardinality of the code C generated
by Construction 6. According to Theorem
3, one has |C2 | =

2n
. In addition, |C1 | = nn . Hence, the size of C is
c2 n−κ+1
2
bounded from below by:
 n
n
n 2
2
c2
.
n−κ+1
The following Theorem proves that both Construction 1 and
6 are order optimal, in the sense that they produce codes with
cardinality within a constant factor away from the maximal
achievable value.
Theorem 6. Let ABAL_κ−WMU_q_n denote the maximum size of
a balanced κ-WMU code over Fnq , for n ≥ 2 and q ∈ {2, 4}.
Then,
(i)
 n
 n
n
n
n 2
n 2
2
2
c2
≤ ABAL_κ−WMU_4_n ≤
.
n−κ+1
n−κ+1

k


j
n
pairs (a, i1 ) , . . . , a, ib n c ∈ X.
are at most n−κ+1
n−κ+1
This implies that

n nn ( 2q )n
2
|X| ≤
.
n−κ+1
( nn2 )( q2 )n
Therefore, |C| ≤ n−κ+1
.
The lower bound in (i) can be achieved through Construction 6, while the lower bound in (iii) can be met using
Construction 1.
We complete our discussion by briefly pointing out how to
use the balanced MU code Construction 1 to derive a balanced
n
κ-WMU code C ∈ {A, T, C, G} that has the prefix balancing
property with parameter D. For this purpose, we generate C
according to the balanced WMU Construction 6. We set C2 =
n
κ−1
{0, 1} and construct C1 by concatenating C10 ⊆ {0, 1}
and
n−κ+1
00
0
00
C1 ⊆ {0, 1}
. Here, C1 is balanced and C1 is a balanced
WMU code with parameter D. It is easy to verify that C is a
balanced κ-WMU DNA code with prefix-balancing parameter
D and of cardinality
n−κ
κ−1
) Dyck(
, D) 2n
|C| =|C10 | |C100 | |C2 | = A(κ − 1, 2,
2
2




π
π
4n tan2 D+1
cosn−κ D+1
∼
.
√
1
2 π (D + 1) (κ − 1) 2
6. APD-MU C ODES
Our next goal is to provide constructions for κ-WMU codes
that do not form primer dimer byproducts.
We first discuss a construction of binary MU codes with the
APD property.
Construction 7. (f − APD_MU_2_n) Let n, f, `, p be positive
integers such that n = pf and ` + 3 ≤ f2 . Let
C = {a1 a2 . . . a2p | a ∈ C1 , a2 , . . . , a2p ∈ C2 }
f

where C1 ⊆ F22 is the set of binary sequences a =
(a1 , . . . , a f ) such that:
2

•
•

(ii)
n

ABAL_κ−WMU_2_n ≤

n
2

f



n−κ+1

.

(iii)
n
n
2

n



2(n − 1)

≤ ABAL_MU_2_n ≤

The sequence a starts with 0` 1 and ends with 1;
f
2
The substring a`+1
does not contain 0` as a substring,

n
2

n


.

Proof: To prove the upper bounds, we use the same
technique as that described in Theorem 3. Assume that C ⊆ Fnq
is a balanced κ-WMU code, for q ∈ {2, 4}, and consider the
set X of pairs (a, i) where a ∈ Fnq , i ∈ {1, . . . , n}, and the
cyclic shift of the sequence a starting at position i belongs to
C. One may easily verify that |X| = n |C|. On the other hand,
if (a, i) ∈ X, then a is balanced itself and there are nn ( 2q )n
2
balanced sequences to select from. Moreover, (a, j) ∈
/ X,
for j ∈
/ {i ± 1, . . . , i ± (n − κ)}mod n due to the κ-WMU
property. Hence, for a fixed balanced sequence a ∈ Fnq , there

and where C2 ⊆ F22 is the set of binary sequences a =
(a1 , . . . , a f ) such that:
2
• The sequence a ends with 1;
`
• The sequence a contains 01 0 as a substring.
`
• The sequence a does not contain 0 as a substring.
n

Lemma 5. Let C ∈ {0, 1}
Construction 7. Then,
(i) C is an MU code.
(ii) C is an f -APD code.

denote the code generated by

Proof: The proof follows from two observations, namely
(i) The code C satisfies the constraints described in Construction 2, and is hence an MU code.
(ii) Any substring of length f of any sequence in C contains
an element from C2 as a substring. Hence, any substring
of length f in C contains 01` 0 as a substring, and so

10

the reverse and forward complement sequence contains
10` 1. Furthermore, no proper substring of length f in C
contains 10` 1 as a substring. Hence, C is also an f -APD
code.
Next, we use Lemma 1 to derive a lower bound on the size
of the codes C1 and C2 in Construction 7, and a lower bound
on the size of the code C. First, notice that
!


f
f
f
22
f
22
2 −`−2
≥ `+2 1 − `+1 ,
|C1 | ≥ `+2 1 −
2
2`
2
2
which follows from Lemma 1, with n = f2 −`−2, ns = `, t =
1. To bound the cardinality of C2 we define an auxiliary code
f
C3 ⊆ {0, 1} 2 −`−3 such that sequences in C3 avoid 0`−1 , 1`−1
as a substring. One can once more apply Lemma 1 with n =
f
2 − ` − 3, ns = ` − 1, t = 2, to obtain
!
f
f
4( f2 − ` − 3)
22
22
f
|C3 | ≥ `+3 1 −
≥
(1 − `−1 ).
2
2`
2`+3
2
Notice that by inserting 01` 0 into sequences in C3 at any of
the f2 − ` − 2 allowed positions, and then appending 1 to the
newly obtained sequence, we obtain a subset of C2 of size
( f2 − ` − 2)|C3 |. Therefore,
 f

22
f
f
−`−2
(1 − `−1 ).
|C2 | ≥
2
2`+3
2
For ` = dlog2 (3f )e, one can verify that the size of the code C1
f

is within a constant factor of

21
f

, and the size of C2 is within

f
2

a constant factor of 2 . In the last step, we use the fact that
|C| = |C1 ||C2 |2p−1 to show that |C| is within a constant factor
n
of 2n . Therefore, Construction 7 produces an order-optimal
f -APD MU binary codes. The result is summarized in the
following theorem.
Theorem 7. Let Af−APD_MU_2_n denote the maximum size of
an f − APD_MU_2_n code, for positive integers n = pf such
that p is a constant factor. Then, there exist constants c3 > 0
such that
2n
2n
≤ Af−APD_MU_2_n ≤ .
c3
n
n
Proof: The lower bound is a direct consequence of Construction 7, while the upper bound follows from Theorem 1,
and the fact that any f − APD_MU_2_n code is also an MU_2_n
code.
7. APD, BALANCED , E RROR -C ORRECTING AND WMU
C ODES
In what follows, we describe the main results of our work:
Constructions of APD, balanced, error-correcting κ-WMU
codes. The gist of our approach is to use the decoupling
principle along with a pair of binary codes that satisfy one or
two of the desired binary primer constraints in order to obtain
a large set of proper address/primer sequences. In addition to
constructions based on the decoupling procedure, we introduce
a number of other constructions that directly produce the

desired q-ary codes with large codebooks, or allow for simple
encoding and decoding.
Recall Construction 5, which we showed results in an errorcorrecting κ-WMU DNA code. Map the elements in F4 to
{A, T, C, G} according to:
0 7→ A, 1 7→ C, ω 7→ T, ω + 1 7→ G,
where ω is a primitive element of the field F4 .
Let a be a sequence of length n. Then it is straightforward to see that the sequence (a, a + 1n ) is balanced, for
1n = (1, . . . , 1). These observations lead to the simple primer
construction described next.
Construction 8. (V1 : BAL_2d − HD_κ − WMU_4_n Codes) Let
C be an [ n2 , κ − 1, d] cyclic code over F4 that contains the all
ones vector 1. Then
n

{(c + e, c + 1 2 + e) : c ∈ C}
is a GC balanced, κ-WMU code with minimum Hamming
distance 2d.
The next construction follows by invoking the decoupling
principle with binary error-correcting WMU codes constructed
in Section 4 and codes meeting the bound of Theorem 5.
Construction 9. (V2 : BAL_d − HD_κ − WMU_4_n Codes)
n
Construct a code C ∈ {A, T, C, G} via the decoupled construction of Lemma 2 involving two codes:
(i) A balanced code C1 of length n, with minimum Hamming
distance d and of size A 2n −CST_d−HD_2_n .
n
(ii) A κ-WMU code C2 ⊆ {0, 1} of length n and minimum
Hamming distance d, described in Section 4.
n

Lemma 6. Let C ∈ {A, T, C, G} denote the code generated
by Construction 9. Then,
(i) C is a κ-WMU code.
(ii) C is balanced.
(iii) The minimum Hamming distance of C is at least d.
Example 1. The size of the code C obtained from Construction 9 equals
|C| =|C1 | |C2 |
2n A 2n −CST_d−HD_2_n
(n − κ + 1) (L0 − L1 − L2 )

n
n Ad−HD_2_n
2
≥ 0.09376
.
(n − κ + 1) (L0 − L1 − L2 )
≥ c2

(10)

The last two inequalities follow from the lower bounds of
Lemma 4 and Theorem 5, respectively.
Figure 2 plots the lower bound on the maximum achievable
rate for error-correcting κ-WMU codes (5), balanced errorcorrecting κ-WMU codes (10), and for comparison, the best
known linear error-correcting codes over quaternary alphabets.
The parameters used are n = 50, κ = 25.
The next result shows that Construction 7 may be used to
devise sequences that are balanced, MU and do not form any
PDs.

11

Error-correcting linear code
Error-correcting WMU code
Balanced error-correcting WMU code

1.0

Relative rate

0.8
0.6
0.4
0.2
0.0

0

10

20
30
Hamming distance

40

50

Figure 2. Comparison of three different lower bounds for quaternary codes: Balanced error-correcting κ-WMU codes (inequality (10) in Example 1),
error-correcting κ-WMU codes (inequality (5) in Theorem 4) and the best known linear error-correcting codes; n = 50, κ = 25.

Construction 10. (f − APD_BAL_MU_4_n Codes) Using the
decoupled code construction in Lemma 2, a balanced, MU
code C ∈ Fn4 that avoids PDs may be obtained by choosing
C1 ⊆ Fn2 to be an BAL_2_n code, and C2 ⊆ Fn2 to be an
f − APD_MU_2_n code.

It is straightforward to see that |C1 | = nn and that |C2 | ≥
2
( nn ) 2n
2n
c3 n . Therefore, the size of C is at least c3 2 n .
Theorem 8. Let Af−APD_BAL_MU_4_n denote the maximum size
of a f − APD_BAL_MU_4_n code. Then
 n
 n
n
n
n 2
n 2
2
2
c3
≤ Af−APD_BAL_MU_4_n ≤
.
n
n
Proof: The lower bound is the direct consequence of
Construction 10. To prove the upper bound, observe that
any f − APD_BAL_MU_4_n code is also a valid BAL_MU_4_n
code. The upper bound on the cardinality of an BAL_MU_4_n
code may be obtained from the upper bound of Theorem 6,
pertaining to a BAL_WMU_4_n code, by setting κ = 1.
Next, we discuss an iterative construction based on an APD,
balanced, error-correcting and κ-WMU seed code.
Construction 11. For a given integer s ≥ 1, let C0 be a set
of sequences in Fsq . Let

(i)
(ii)
(iii)
(iv)

C
C
C
C

is 2f -APD if C0 is f -APD.
is balanced if C0 is balanced.
and C0 have the same minimum Hamming distance.
is κ-WMU if C0 is κ-WMU.

Proof:
(i) Any proper substring of length 2f of any codesequence
in C contains a proper substring of length f of a codesequence in C0 . Then, C is 2f -APD if C0 is f -APD.
(ii) Codesequences in C form by concatenating codesequences in C0 . If C0 is balanced then each codesequences
in C is also balanced.
(iii) Again, any two distinct codesequences in C differ in at
least one of the concatenated codesequences from C0 .
Therefore, C and C0 have identical minimum Hamming
distance.
(iv) For any pair of not necessarily distinct a, b ∈ C and for
κ ≤ l < n, we show that al1 and bnn−l+1 cannot be
identical. This establishes that the constructed concate 
nated code is WMU. Let l = is + j, where i = sl and
0 ≤ j < s. We consider three different scenarios for the
index j:
•

C = {a1 . . . am | ai ∈ Ci for 1 ≤ i ≤ m} ,
where the subset codes C1 , . . . , Cm ⊆ C0 are chosen according
to:

•

C1 ∩ C m = ∅
and (C1 ∩ Cm−1 = ∅) or (C2 ∩ Cm = ∅)
..
.
and (C1 ∩ C2 = ∅) or . . . or (Cm−1 ∩ Cm = ∅).
Lemma 7. Let C ⊆ Fnq be a code generated according to the
Construction 11. Then

•

j = 0; In this case, 1 ≤ i < m. Therefore, (C1 ∩
Cm−i+1 = ∅) or . . . or (Ci ∩ C1 = ∅) implies that
al1 6= bnn−l+1 .
0 < j < κ; Again, one can verify that 1 ≤ i < m. It
is easy to show that al−j
l−s+1 is a suffix of length s − j
of a sequence in C0 and bn−j
n−s+1 is a prefix of length
s − j of an element in C0 . Since κ < s − j < s, one
n−j
l
n
has al−j
l−s+1 6= bn−s+1 . Hence, a1 6= bn−l+1 .
l
κ ≤ j < s; In this case, al−j+1 is a proper prefix of
length j of a sequence in C0 , and bnn−j+1 is a proper
suffix of length j of an element in C0 . Since κ ≤ j <
s, one has all−j+1 6= bnn−j+1 and al1 6= bnn−l+1 .

12

8. I NFORMATION E NCODING WITH WMU ADDRESSES
In order to store user data in DNA, one needs to encode
the binary information into relatively short sequences of nucleotide, each of which is equipped with a unique address
sequence that satisfies the constraints outlined in the previous
section. As already described, in order to enable accurate
random access via PCR, the information bearing content of
the sequences has to avoid the set of address sequences. This
leads to the following problem formulation.
Given a set of sequences A ⊆ Fnq , let CA (N ) ⊆ FN
q denote
another collection of sequences that avoid members of A as
substrings, i.e., a 6= bn+i−1
for every a ∈ A, b ∈ CA (N ),
i
1 ≤ i ≤ N − n + 1. We refer to A as the set of addresses and
CA (N ) as the set of address-avoiding information blocks.
We discuss next three different schemes for constructing an
information codebook CA (N ) of sequences of length N for
particular sets of address sequences A.
Let C be an κ-WMU code over Fnq , for κ ≤ n2 , and let
A ⊂ C. For a given integer s ≥ 1, let N = s n and define
N
CA (N ) ⊆ FN
q as the collection of all sequences b ∈ Fq of
the form
b = b1 . . . bs ,
where bi ∈ C − A, for 1 ≤ i ≤ s. This construction is
illustrated in Figure 3. We show next that no b ∈ CA (N )
contains any a ∈ A as a substring.
The proof follows by contradiction. Assume that a appears
as substring in bi bi+1 , for some 1 ≤ i < s. Since a ∈ A and
bi , bi+1 ∈ C − A, a may be written as a = sp, where s is a
proper suffix of bi and p is a proper prefix of bi+1 . Then one
of the two strings p or s has length greater than or equal to
n
2 ≥ κ, which contradicts the fact that C is an κ-WMU code.
The previously described construction may be easily extended to obtain error-correcting information blocks CA (N ).
We start by identifying a bijection M from C − A to a finite
field Fpt with appropriate prime parameter p and t ≥ 1; for
this purpose, we expurgate codesequences from the set C so
that |C| − |A| = pt .
The bijection M is used to convert every sequence b =
b1 . . . bs in CA (N ) to a sequence v = v1 . . . vs ∈ Fspt , where
vi = M(bi ), for 1 ≤ i ≤ s. The sequence v is encoded
using an [r, s, r −s+1]pt Reed-Solomon (RS) error correcting
code to arrive at a codesequence w = w1 . . . wr ∈ Frpt , where
wi ∈ Fpt for 1 ≤ i ≤ r. Since M is a bijection, one can apply
M−1 to w to reconstruct c = c1 . . . cr ∈ Fsq r , where ci =
M−1 (wi ), for 1 ≤ i ≤ r. Since c is obtained by concatenating
elements from C − A, it is easy to verify that c does not
contain any element of A as a substring. Moreover, the RS
code guarantees that given a sequence c with at most b r−s
2 c
errors, one can still fully recover b.
For the second scheme, assume that C1 , C2 ⊆ Fn2 are two
disjoint collections of binary sequences of length n such that
for all a ∈ C1 , the cyclic shifts of a do not belong to C2 , i.e.,
for all a ∈ C1 , ani ai−1
∈
/ C2 for all 1 ≤ i ≤ n.
1
Now given C1 and C2 , define the set of addresses A ⊆ F2n
4
as

A = Ψ(c, aa) | a ∈ C1 , c ∈ F2n
2

where Ψ was introduced in (4). To construct CA (N ), let s ≥ 1
be an integer such that N = s n. We define CA (N ) ⊆ FN
4 as
the collection of all sequences b = b1 . . . bs ∈ FN
4 where
bi ∈ Fn4 that can be written as bi = Ψ(fi , gi ), for some
gi ∈ C2 , fi ∈ Fn2 and 1 ≤ i ≤ s. We claim that CA (N ) does
not contain any element of A a as substring.
If Ψ(c, aa) ∈ A appears as a substring in a sequence b ∈
CA (N ), then there exists an index 1 ≤ i ≤ s − 2 such that
Ψ(c, aa) is a substring of bi bi+2 bi+3 . Since Ψ is a bijection
one can verify that aa appears as a substring in gi gi+1 gi+2 ,
for a ∈ C1 and gi , gi+1 , gi+2 ∈ C2 . In addition, C1 ∩ C2 = ∅
implies that aa can be written as aa = sgi+1 p, where s is a
proper suffix of gi and p is a proper prefix of gi+2 . It is clear
that a = sp and gi+1 = ps; hence, gi+1 ∈ C2 is a cyclic
shift of a ∈ C1 , which contradicts the fact that C2 contains no
cyclic shifts of elements in C1 .
The last information block design scheme we present is
endowed with a simple encoding and decoding procedure.
Let A ⊆ Fnq be a collection of sequences of length n such
that e ∈
/ A, where e = (0, . . . , 0, 1). For the purpose of
information block encoding, we may assume that A is a κWMU code with desired primer properties, constructed using
cyclic error-correcting codes of minimum distance at least
three, as described in Constructions 8 and 9. Let N > n
N −n+1
and define I , {a|an−1
∈ Fn−1
, aN
}, so that
q
n ∈ Fq−1
1
|I| = q n−1 (q − 1)N −n+1 . There is an efficient encoding
scheme that maps elements of I to a set of sequences CA (N )
of length N that avoid all codesequences in A.
Let H be a parity-check matrix of A. Hence, a sequence c
belongs to A if and only if cH = 0. Also, since e ∈
/ A, one
has eH 6= 0.
To describe the encoding procedure, we define the following
× {0, 1, . . . , q − 2} → Fq . Given a ∈ Fn−1
function φ : Fn−1
q
q
and 0 ≤ i ≤ q − 2, let an = φ(a, i) be the i smallest element
in Fq such that (a, an )H 6= 0. For this function to be welldefined, it suffices to demonstrate that there are at least q − 1
elements in Fq such that appending one of them to a yields a
decoding syndrome not equal to 0. Suppose otherwise. Then
there exist distinct u, u0 such that (a, u)H = (a, u0 )H = 0.
The last equality may be rewritten as (0, u − u0 )H = (u −
u0 )eH = 0, contradicting the starting assumption.
Encoding a sequence a results in a sequence b obtained by
concatenating the following sequences:
(
ai
if 1 ≤ i ≤ n − 1
bi =
i−1
φ(bi−n+1 , ai ), otherwise.
It is straightforward to see that sequences obtained via this
encoding method avoid all elements of the codebook A.
9. C ONCLUSIONS
Motivated by emerging code design problems for DNAbased data storage, we introduced the problem of address/primer sequence design. The address design problem
reduces to constructing sequences that satisfy a new form
of mutual uncorrelatedness and in addition, are balanced, at
sufficient Hamming distance from each other and such that
they avoid primer dimers which arise if a substring of an

0𝑙

Avoid 0𝑙

≠0

≠0
13

WMU Code Partition

Part 1

Address

Part 2

Sub-block 1

Sub-block 2

…

Figure 3. Concatenation construction for information blocks avoiding κ-WMU primer sequences. The gist of the approach is to use a subset of address
sequences for actual addressing, and the remaining sequences as blocks to be concatenated.
Table I
S UMMARY OF THE OPTIMAL CODE CONSTRUCTIONS FOR VARIOUS CONSTRAINED WMU CODES .
Construction No.
1

Name
BAL_MU_2_n

2
4

MU_q_n
WMU_q_n

6

BAL_κ − WMU_4_n

7

f − APD_MU_2_n

10

f − APD_BAL_MU_4_n

Rate
n
1
2(n−1) n
2
n
cq qn
qn
cq n−κ+1
 
n
n
n 2
2
c2 n−κ+1
n
c3 2n 
n
n
n 2
c3 2 n



Features
Binary, Balanced, MU

Comment

q-ary, MU
q-ary, κ-WMU

q ∈ {2, 4}, c2 = 0.04688, c4 = 0.06152
q ∈ {2, 4}, c2 = 0.04688, c4 = 0.06152

4-ary, Balanced, κ-WMU

c2 = 0.04688

Binary, f -APD, MU

For some constant c3 > 0

4-ary, f -APD, Balanced, MU

For some constant c3 > 0

address sequence is also a substring of the reverse complement
sequence of the same or another address sequence. Our main
results are listed in Table I. Given the constructed address sequences, we also described information encoding methods for
sequences endowed with addresses, such that they avoid any
address as a proper substring. This address avoidance property
allows one to randomly access desired DNA sequences via
simple and inexpensive PCR reactions.
R EFERENCES
[1] V. Levenshtein, “Decoding automata, invariant with respect to the initial
state,” Problemy Kibernet, vol. 12, pp. 125–136, 1964.
[2] A. J. De Lind Van Wijngaarden and T. J. Willink, “Frame synchronization using distributed sequences,” Communications, IEEE Transactions
on, vol. 48, no. 12, pp. 2127–2138, 2000.
[3] D. Bajić and J. Stojanović, “Distributed sequences and search process,”
in Communications, 2004 IEEE International Conference on, vol. 1.
IEEE, 2004, pp. 514–518.
[4] S. Bilotta, E. Pergola, and R. Pinzani, “A new approach to cross-bifixfree sets,” IEEE Transactions on Information Theory, vol. 6, no. 58, pp.
4058–4063, 2012.
[5] S. R. Blackburn, “Non-overlapping codes,” IEEE Transactions on Information Theory, vol. 61, no. 9, pp. 4890–4894, 2015.
[6] G. M. Church, Y. Gao, and S. Kosuri, “Next-generation digital information storage in DNA,” Science, vol. 337, no. 6102, pp. 1628–1628,
2012.
[7] N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust,
B. Sipos, and E. Birney, “Towards practical, high-capacity, lowmaintenance information storage in synthesized DNA,” Nature, 2013.
[8] S. Yazdi, Y. Yuan, J. Ma, H. Zhao, and O. Milenkovic, “A rewritable,
random-access DNA-based storage system,” Scientific Reports, vol. 5,
no. 14138, 2015.
[9] S. H. T. Yazdi, R. Gabrys, and O. Milenkovic, “Portable and error-free
DNA-based data storage,” Scientific Reports, vol. 7, 2017.

[10] H. M. Kiah, G. J. Puleo, and O. Milenkovic, “Codes for DNA sequence
profiles,” IEEE Transactions on Information Theory, vol. 62, no. 6, pp.
3125–3146, 2016.
[11] R. Gabrys, E. Yaakobi, and O. Milenkovic, “Codes in the Damerau
distance for DNA storage,” in Information Theory (ISIT), 2016 IEEE
International Symposium on. IEEE, 2016, pp. 2644–2648.
[12] R. Gabrys, H. M. Kiah, and O. Milenkovic, “Asymmetric Lee distance
codes for DNA-based storage,” IEEE Transactions on Information
Theory, 2017.
[13] S. Yazdi, H. M. Kiah, E. R. Garcia, J. Ma, H. Zhao, and O. Milenkovic,
“DNA-based storage: Trends and methods,” Molecular, Biological, and
Multi-Scale Communications, IEEE Transactions on, to appear.
[14] S. H. T. Yazdi, R. Gabrys, and O. Milenkovic, “Portable and error-free
DNA-based data storage,” bioRxiv, p. 079442, 2016.
[15] P. Yakovchuk, E. Protozanova, and M. D. Frank-Kamenetskii, “Basestacking and base-pairing contributions into thermal stability of the DNA
double helix,” Nucleic acids research, vol. 34, no. 2, pp. 564–574, 2006.
[16] P. M. Vallone, J. M. Butler et al., “AutoDimer: a screening tool for
primer-dimer and hairpin structures,” Biotechniques, vol. 37, no. 2, pp.
226–231, 2004.
[17] K. A. S. Immink, Codes for mass data storage systems. Shannon
Foundation Publisher, 2004.
[18] M. Levy and E. Yaakobi, “Mutually uncorrelated codes for DNA storage,” in Information Theory (ISIT), 2017 IEEE International Symposium
on. IEEE, 2017, pp. 3115–3119.
[19] O. Milenkovic and N. Kashyap, “On the design of codes for DNA
computing,” in Coding and Cryptography. Springer, 2006, pp. 100–119.
[20] ——, “DNA codes that avoid secondary structures,” in Information
Theory, 2005. ISIT 2005. Proceedings. International Symposium on.
IEEE, 2005, pp. 288–292.
[21] E. Gilbert, “Synchronization of binary messages,” Information Theory,
IRE Transactions on, vol. 6, no. 4, pp. 470–477, 1960.
[22] L. J. Guibas and A. M. Odlyzko, “Maximal prefix-synchronized codes,”
SIAM Journal on Applied Mathematics, vol. 35, no. 2, pp. 401–418,
1978.
[23] N. de Bruijn, D. Knuth, and S. Rice, “The average height of planted
plane trees,” Graph Theory and Computing/Ed. RC Read, p. 15, 1972.

14

[24] E. N. Gilbert, “A comparison of signalling alphabets,” Bell System
Technical Journal, vol. 31, no. 3, pp. 504–522, 1952.
[25] R. Varshamov, “Estimate of the number of signals in error correcting
codes,” in Dokl. Akad. Nauk SSSR, vol. 117, no. 5, 1957, pp. 739–741.
[26] S. Tavares, “A study of synchronization techniques for binary cyclic
codes,” Ph.D. dissertation, Thesis (Ph. D.)–McGill University, 1968.
[27] L. Gyorfi, J. Massey et al., “Constructions of binary constant-weight
cyclic codes and cyclically permutable codes,” IEEE Transactions on
Information Theory, vol. 38, no. 3, pp. 940–949, 1992.

