# VL-DNA: Enhance DNA Storage Capacity with Variable Payload (Strand) Lengths

Yixun Wei<EMAIL_ADDRESS>Department of Computer Science and Engineering,
University of MinnesotaUSA ,  Wenlong Wang  Department of Computer Science and
Engineering, University of MinnesotaUSA ,  Huibing Dong  Department of
Computer Science and Engineering, University of MinnesotaUSA ,  Bingzhe Li
Department of Electrical and Computer Engineering, Oklahoma State
UniversityUSA and  David H.C. Du  Department of Computer Science and
Engineering, University of MinnesotaUSA

(2018; xx February xxxx; xx March xxxx; xx June xxxx)

###### Abstract.

DNA storage is a promising archival data storage solution to today’s big data
problem. A DNA storage system encodes and stores digital data with synthetic
DNA sequences and decodes DNA sequences back to digital data via sequencing.
For efficient target data retrieving, existing Polymerase Chain Reaction (PCR)
based DNA storage systems apply primers as specific identifier to tag
different set of DNA strands. However, the PCR based DNA storage system
suffers from primer-payload collisions, causing a significant reduction of
storage capacity. This paper proposes using variable payload/strand length,
which takes advantage of the inherent payload-cutting process, to split
collisions and recover primers. The executing time of our scheme is linear to
the number of primer-payload collisions. The scheme serves as a post-
processing method to any DNA encoding scheme. The evaluation of three state-
of-the-art encoding schemes shows that the scheme can recover thousands of
usable primers and improve tube capacity ranging from 18.27% to 19x.

DNA storage

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Hardware Emerging
architectures††ccs: Hardware Emerging tools and methodologies††ccs: Hardware
Memory and dense storage

##  1\. Introduction

Modern archival storage has been trying to preserve the ever-growing digital
data reliably for centuries (Miller, 2020). However, typical archival storage
media/devices are not matching the booming storage demand. The storage
requirement in hyper-scale data centres is expected to reach 32.6 million
petabytes in 2030, which might surpass the total supplied storage capacity
(Alliance, 2021)(Corporation, 2023). Besides, the typical storage
media/devices are also not durable enough (usually within a decade), thus
introducing expensive data preservation costs.

DNA is emerging as a promising archival storage medium to meet the burgeoning
storage demand. Theoretically, DNA storage can have a density of about 1
exabyte/mm3 and preserve the data for hundreds of years (Bornholt et al.,
2016). Even considering the implementation overheads of a practical archival
system, existing DNA storage systems can still be orders of magnitude denser
than tape(Alliance, 2021). Additionally, other unique properties of DNA, such
as sustainability and energy efficiency, further make DNA a desirable medium
for storing archival data for many decades.

In existing DNA storage systems, digital data is encoded and synthesized as
the payloads of DNA strands. The DNA strands are usually dehydrated and stored
in physical tubes for long-term preservation. When retrieving data, people
liquidize the DNA and use a drop of the liquid for sequencing (i.e., the read
process in DNA storage). To ensure efficient data retrieval, polymerase chain
reaction (PCR) based random access has been introduced to DNA storage
(Organick et al., 2018)(Bornholt et al., 2016)(Yazdi et al., 2015b)(Yazdi et
al., 2017). In the PCR-based random access, each DNA payload is flanked by a
pair of primers (i.e., short nucleic acid sequences) to form DNA strands. The
primers serve as unique tags to identify different sets of DNA strands. When
retrieving payloads (data), only strands with specific primer pairs can be
amplified by PCR and then sequenced. In such a system, the number of DNA
payloads stored in a tube is proportional to the number of usable primers in a
tube. In this paper, the usable primers refer to primers that function well
without violating bio-constraints, including no primer-payload collisions,
which we discuss later.

The existence of primer-payload collisions disables many primers. Primer-
payload collisions refer to almost identical subsequences between a primer and
any portion of a payload (Organick et al., 2018). A primer must be disabled
for reliable PCR if it collides with any payloads in the same tube. The number
of usable primers in a tube can decrease up to 70%-99% as the number of
payloads increases (Wei et al., 2022). As a result, the tube capacity of
random-access-based DNA storage is significantly decreased.

A few works are trying to increase the number of primers that can be used. For
example, the approach of nested primer (Song et al., 2019)(Yamamoto et al.,
2008) combines multiple short usable primers to form a new, longer primer. The
number of new primers can increase by combining the multiple layers of short
usable primers. However, the nested primer approach does not solve the primer-
payload collision issue directly. Besides, using the usable primers in a
nested manner will reduce each DNA strand’s payload length, assuming the
length is fixed. Other related work (Organick et al., 2018)(El-Shaikh et al.,
2022) keep randomizing DNA sequences until all payload sequences have no
collision with primers and still satisfy biological constraints. These works
can avoid collisions in small-scale data. Nevertheless, as data storage
scales, they have an unacceptable computation overhead and a giant mapping
table to record the randomization.

This paper proposes a variable payload (strand) length scheme, called VL-DNA,
to break up primer-payload collisions using DNA storage’s inherent payload-
cutting process. Instead of cutting DNA payloads with fixed current maximum
length (e.g., 200 bases), VL-DNA cuts payloads into several variable payload
lengths (e.g., 150, 160, 190, and 200 in this paper). We combine these payload
lengths to build cutting points at different positions so that we can break
the potential primer-payload collisions and recover more usable primers. Since
strand length is the payload length plus metadata length (including primers
and an internal index), variable payload length means variable strand length.
Hereafter, we use variable payload/strand length interchangeably. A heuristic
scheme is proposed to find the cutting points of payload to balance the trade-
off between DNA strand length and the number of recovered usable primes. As a
result, VL-DNA extricates a considerable amount of primers from collisions and
thus improves the tube capacity of DNA storage. Note that VL-DNA is generic
and independent. We can apply it to any existing DNA encoding schemes or
optimizations (e.g., nested primer approach) to gain storage capacity
enhancements.

The rest of this paper is organized as follows. Section 2 introduces DNA
storage backgrounds, including storage workflow, factors that affect capacity,
and primer-payload collision. Section 3 elaborates on the concept of the
variable payload length and the corresponding algorithms. Section 4 shows the
complete DNA storage system equipped with the VL-DNA scheme. Section 5
evaluates our scheme. Conclusions are drawn in Section 6.

##  2\. Background

###  2.1. DNA Storage in Brief

Figure 1. Workflow of typical DNA storage system

Several researchers have demonstrated the feasibility and discussed the
potential capacity of DNA archival storage (for Policy Studies, 2018) (Li et
al., 2020)(Wei et al., 2022). Figure 1 shows the typical workflow of the
current DNA storage system.

In existing DNA storage systems, digital data will first be added with some
error correction code (e.g., Reed–Solomon Code) for data recoverability (Lin
et al., 2022) (Carmean et al., 2018). Certain encoding schemes will then
encode the resultant data to a sequence of DNA bases (A, T, G, and C). The DNA
sequences will be cut into multiple shorter subsequences called DNA payloads.
Each payload will be flanked by a pair of primers and an internal index to
form a DNA strand. The primer pair is a unique tag that enables random access
to DNA storage based on PCR. Multiple DNA strands can share one primer pair,
and an internal index helps identify the strands. Eventually, each DNA strand
will be chemically synthesized base by base and stored in physical tubes.

(a) standard PCR

(b) PCR with primer-payload collision

Figure 2. standard PCR and defective PCR with primer-payload collision

The PCR-based random access is a process that first amplifies target DNA
strands with a specific primer pair and then sequences only the target
strands. The amplification usually takes 20 to 40 PCR cycles. A standard PCR
cycle is shown in Figure 2 (a). In each cycle, target DNA strands are
denatured into two single-stranded DNA molecules, and each molecule anneals
with the added complementary primer templates. Then the DNA bases (A, T, C, G)
from the added mixture solution will pair with the annealed molecules to form
new DNA strands. After multiple PCR cycles, the target strands have enough
concentration and can be sequenced out. Finally, the read-out DNA sequences
can be decoded back to digital data. The ECC added before can help recover
some errors during the synthesis and sequencing processes.

###  2.2. DNA Tube Capacity and Primer-Payload Collisions

A DNA storage system must obey many bio-constraints to provide reliable data
storage; thus, many factors affect DNA tube capacity. DNA tube capacity is the
multiplication of the following factors (Li et al., 2020)(Wei et al., 2022):
1) DNA payload length, 2) the number of digital bits each DNA base can store
(i.e., encoding density), 3) the number of strands that one primer pair can
accommodate (i.e., parallel factor), and 4) the number of usable primers. A
practical DNA strand length is limited to 100-300 bases because the error rate
soars up when the strand becomes overlong (Alliance, 2021)(Matange et al.,
2021). After excluding the primer pair and internal index, a payload is
usually no longer than 200 bases. Similarly, the parallel factor is also
limited (e.g., 1.55 $\times 10^{6}$ (Li et al., 2020)). Based on different
encoding schemes, the encoding density varies from less than one bit per DNA
base to at most two bits per DNA base (e.g., A=00, T=01, C=10, G=11). The
number of usable primers is also limited by certain primer design rules and
the primer-payload collisions that we will discuss later. The DNA tube
capacity equals the payload length $\times$ encoding density $\times$ parallel
factor $\times$ the number of usable primers / 2 (i.e., the number of primer
pairs).

Given all biological constraints, primer-payload collision is the most
critical factor affecting the tube capacity. As Figure 2 (b) shows, a
collision occurs if a pair of almost identical subsequences exists between a
primer and a portion of payload stored in the same tube (Organick et al.,
2018)(Wei et al., 2022). The subsequences are usually longer than 12 bases and
have at most two mismatches or gaps. In each PCR cycle, the PCR can amplify
some irrelevant strands if these strands contain payloads that collide with
the target primer. More importantly, this consumes the limited PCR reagents
(e.g., complementary primers used to bind with the target primer and free DNA
bases waiting for complementing new double-helix strands). Figure 3 shows the
distribution of primers with different numbers of payload collisions. The
input data is a 135MB video (135MBVideo), and the encoding scheme is Blawat
code (Blawat et al., 2016) (see the encoding scheme, primer generating, and
collision checking in Section 5). Although input data is only 135MB, 27,658
primers (i.e., 98.77% of primers in our primer library) have collisions with
those payloads, and the average number of collisions per collided primer is
155.45 (i.e., on average, a primer has collisions with 155.45 payloads). If
the input data keeps scaling up, most collided primers likely have hundreds or
thousands of collisions. In this case, PCR amplification is very vulnerable to
primer-payload collisions. The target primer must compete for the limited PCR
reagents with thousands of collided payloads in each PCR cycle. Even if a
primer has only a few collisions at the beginning, the collisions can still
significantly impact the final result. That is because PCR is an exponential
augmentation process. Slight amplification variations can exacerbate cycle by
cycle and consume ever more PCR reagents. Eventually, the resultant solution
will be saturated with plenty of irrelevant sequences but very few target
sequences. As a result, the sequencing for target sequences is inhibited.

Figure 3. Distribution of primers with different numbers of collisions
(encoding scheme: Blawat, data: 135MB video)

Organick et al. first (Organick et al., 2018) reported a PCR failure due to
primer-payload collisions. They successfully accessed a target file when the
DNA tube contained no other data but failed to do so when there were nine
files in the tube (the target data is 17.4% of the whole data in the tube).
After that, Wei et al. (Wei et al., 2022) investigated the impact of primer
payload collisions based on 1.5TB of different types of digital data. Their
results showed that the primer payload collision could cause 70% to 99% tube
capacity loss depending on different encoding schemes. Most of the existing
encoding schemes can achieve only several Gigabytes of tube capacity, which is
much lower than people’s expectations and may inhibit DNA storage from
practical use.

Given that other capacity factors (e.g., strand length) are all restricted by
current biotechnologies, it is critical to relieve the malevolent influence of
primer-payload collisions to enhance DNA storage capacity. In this paper, we
apply BLAST (Altschul et al., 1990) to check the primer-payload collisions.
BLAST is one of the most widely used genomic sequence analysis tools and has
been applied by previous DNA storage works (Organick et al., 2018)(Wei et al.,
2022).

##  3\. VL-DNA Design and Algorithm

In this section, we first explain how VL-DNA uses the inherent payload-cutting
process to break up collisions. Then, we propose a heuristic algorithm to
achieve the balance between payload length and primer recovery.

###  3.1. Variable Payload Length

Figure 4. Possible cut-points with payload length 150/160/190/200

A collision occurs if there exist two consecutive and almost identical
subsequences longer than 12 bases in a primer and a payload. We can remove a
collision by splitting it into two parts no longer than 12 bases. However,
current DNA storage systems cut DNA sequences into fixed-length payloads. In
this case, we can only cut collisions located in the multiple of the fixed
length. By contrast, arbitrary length can cut any collision. However,
arbitrary length can generate very short payloads that not only waste strand
length but are easily mistaken as noisy reads (i.e., by-products of
sequencing, usually short broken DNA strands). Moreover, arbitrary length is
less tolerable to DNA base insertion and deletion errors.

Making a trade-off between fixed and arbitrary payload lengths, we identified
and proposed to use only four payload lengths as bases and combine them into
longer variable lengths to cut most collisions. Given that the current
practical strand length is usually 100-300 bases, we assume the maximum
payload length is around 200 bases after excluding the primer pair and
internal index. We select 150/160/190/200 as our four basic payload lengths.
Fig. 4 shows possible combinations of the four payload lengths. Starting from
any position, we can set cut points at the next 150/160/190/200th base,
generate one payload with a corresponding length, and break up collisions at
corresponding positions. Combining two or more payloads, we can further break
up collisions at more places. Specifically, we can have a possible cut point
every ten bases since the 450th base. Since collisions are longer than 12
bases, a possible cut point of every ten bases can cover most of the
collisions. We only need one DNA base as metadata to indicate the length of
the payload (i.e., less overhead).

Why these four payload lengths:  except the payload length group of
150/160/190/200, there are also many other lengths. For example, if we have a
payload length as short as 5, we can have cut points every five bases. If we
adopt more than four payload lengths, we may have more length combinations and
cover more collisions. However, too short or too many payload lengths can also
bring other overheads. To comprehensively understand and select payload
lengths, we summarize the following principles:

  * •

Payload length should not be too short: An abridged payload length means a
loss of capacity. Meanwhile, DNA sequencing will generate plenty of noisy
reads (i.e., broken segments of DNA strands). Short payloads could be easily
mistaken as noisy reads. Therefore, we only select lengths in the range of
[150,200] based on the assumption that the current maximum payload length is
200.

  * •

The number of payload lengths should not be too many: DNA strand needs extra
metadata to indicate strand length since strand length is essential in error
detection. In Section 5 we will see that increasing the number of payload
lengths does not significantly increase the capacity and will bring higher
length indicating overhead. Therefore, this paper aims for four payload
lengths with only one DNA base as the length indicator.

  * •

The combination of payload lengths should cover as many areas as possible: The
more areas a payload length group can cover, the more chances collisions are
cut. To estimate how many areas a payload length group can cover, we define
number of covered bases of a payload length group as the total number of bases
if both two sides of the base can have possible cut points. The cut points on
both two sides should be within 12 bases. Because collisions are longer than
12 bases, a base with potential cut points on both sides means collisions
starting from this base can always be covered.

Among all the four-length groups in the range of [150,200], 150/160/190/200 is
one of the groups with the highest number of covered bases. We compare the
length group of 150/160/190/200 with other length groups in Section 5. The
result shows that our length group of 150/160/190/200 outperforms all other
length groups with four lengths and is comparable to other length groups with
more lengths, as shown in section 5.

Because the four basic lengths are multiple of 10, the combination is always a
multiple of 10. We check positions inside each collision that are multiple of
10. The position is the collision’s functional cut point if it splits the
collision into two parts that are both shorter or equal to 12 bases.
Otherwise, we use BLAST (Altschul et al., 1990) to double-check whether the
collision is removed. We consider the position as the collision’s functional
cut point only if BLAST returns no collision. Otherwise, we consider that our
variable length cannot remove the collision.

###  3.2. Problem Formulation:

We first define two properties of primers and then use the properties to
formulate the primer selection problem.

  * •

Primer_capacity is the number of DNA bases the primer can accommodate. Given a
fixed parallel factor, Primer_capacity is determined by the payload length of
DNA strands. Since VL-DNA cut payloads into variable (shorter) lengths, the
more collisions a primer has, the smaller the Primer_capacity is.

  * •

Primer_conflicts describes how many other primers a primer conflicts with. We
consider two primers conflicting with each other when their collisions are
closely grouped and cannot be all cut. Recovering a primer inhibits the
recovery of other conflict primers.

Problem definition: Given all collided primers $V=(p_{1},p_{2},....p_{|V|})$,
find a primer subset $P\subseteq V$ that $\sum_{p_{i}\in P}\textit{
Primer\\_capacity }(p_{i})$ is maximum, and for each $p_{i}\in P$,
$\textit{Primer\\_conflicts }(p_{i})\cap P=\emptyset$.

Consider an undirected graph in which each vertex is a collided primer, vertex
weight is the Primer_capacity, and edges connect vertices if the corresponding
primers conflict. We can interpret the problem as selecting a vertex subset in
which the selected vertices have maximum total weight and have no edges
connected. When the weight of all vertices is equal, this is the maximum
independent set problem (Xiao and Nagamochi, 2017), a well-known NP-hard
problem. Since the maximum independent set problem is a particular case of our
problem, any solution to our problem also works to the maximum independent set
problem. Since exactly solving our problem is at least as hard as solving the
maximum independent set problem, we consider solving our problem with
efficient heuristic algorithms.

###  3.3. VL-DNA Algorithm

The heuristic algorithm is based on the number of collisions and conflicts
each primer has. The number of collisions hints at the direct overhead of
recovering a primer. The more collisions a primer has, the shorter payloads
will generate when recovering the primer. The number of conflicts indicates
the indirect overhead of recovering a primer. One primer’s recovery will block
its conflicted primers’ recovery and lead to a potential overall capacity
decrease.

Input : Collided primers and associated collisions

Output : Cut points

1

2 Function  _Variable Length(__)_ :

3

4 recovered[]= Null;

5 abandoned[] = Null;

6 pending[] = all collided primers;

7 cut_point[] = Null;

8 ascending sort primers in pending[];

9 foreach  _primer $p_{i}$ in pending[]_ do

10 foreach  _$p_{i}$ ’s collision $c_{i}$_ do

11 cut_point[].add($c_{i}$’s cut-point);

12 end foreach

13

14 foreach  _$p_{j}$ that conflicts $p_{i}$_ do

15 move $p_{j}$ from pending[] to abandoned[];

16 end foreach

17 move $p_{i}$ from pending[] to recovered[];

18 end foreach

19 return cut_point[];

20

Algorithm 1 VL-DNA algorithm

The algorithm is shown in Algorithm 1. The input is all collided primers and
their associated collisions. The goal is to obtain the necessary cut points to
remove collisions and recover primers, so that tube capacity is enhanced to
the most extent. We initialize four lists: $recovered[]$, $pending[]$,
$abandoned[]$, and $cut\\_point[]$. All collided primers are initially in
$pending[]$. We first sort primers in ascending order based on either their
number of collisions or conflicts. After that, we sequentially try to recover
each primer in $pending[]$: the functional cut point of each collision of the
current primer $c_{i}$ will be added into $cut\\_point[]$; the conflicted
primers of the current primer will also be moved from $pending[]$ to
$abandoned[]$. We then move the current primer from $pending[]$ to
$recovered[]$.

After processing all primers, we return the $cut\\_point[]$. We then combine
the variable payload lengths to reach each cut point and cut payloads
accordingly. Note that this algorithm only returns necessary cut points used
to remove collisions. As for other places with no collisions, we can just cut
payloads with a maximum allowed length or other lengths if required. The
sorting criteria can be either collision number or conflict number because
they have a very strong correlation (Section 5).

##  4\. DNA storage system equipped with VL-DNA

An archival storage system (e.g., Amazon S3 Glacier) keeps receiving data
archival requests. A DNA archival storage system equipped with the VL-DNA
scheme should be able to ingest the sequential archival requests and store
data tube by tube. We propose a system workflow to handle this situation, as
shown in Fig. 5.

The incoming data would first be buffered until it is enough to fill a DNA
tube. Initially, we start storing data in a DNA tube when it reaches 250 GB
(i.e., an empirical value of DNA tube capacity). The storage system appends
Error correction codes for the data and then encodes the data into a long DNA
sequence. Next, the system uses BLAST to check collisions and obtain each
collided primer’s collisions and their conflicted primers. Based on the
collision statistics, the VL-DNA algorithm intelligently suggests certain
primers to recover and returns necessary cut points used to break up
collisions of the recovered primers. The system can then calculate the number
of payloads the cutting process will generate.

Figure 5. Workflow of the DNA archival storage system equipped with VL-DNA

Meanwhile, the system can also calculate the number of storable payloads based
on current input data. It is the multiplication of the number of usable
primers, 0.5 (we need a primer pair), and parallel factor (Li et al., 2020).
The number of payloads generated and storable can indicate the difference
between input data size and calculated tube capacity. Only when the storable
payloads are within 5% higher/lower than the generated payloads do we consider
the VL-DNA algorithm’s result reasonable. Otherwise, we adjust the input data
size and rerun the algorithm. The size adjustment follows a binary search:
each time, we adjust the input data size to the middle of the last input data
size and the last storable data size. The rerunning is quite efficient because
most digital data has already been encoded and collision-checked. We only need
to rerun the algorithm itself. The algorithm’s time complexity is O(n), where
n is the number of collisions being cut.

After finding a proper input data size, the system cuts the DNA sequence into
payloads based on the cut points defined by the VL-DNA algorithm. Finally, the
system appends metadata (i.e., length indicator, primer pair, and internal
index) for each payload and sends them to DNA synthesis. If there is still
enough data in the buffer, the system prepares to process the data for the
next DNA tube. Note that data is sequentially processed: we do not
intentionally choose data and allocate them into different tubes. The VL-DNA
scheme works independently with DNA encoding. Even if payloads are cut into
different lengths, the decoding process is still the same: orderly assemble
payloads based on the internal index and then use the corresponding encoding
scheme to decode the DNA sequence back to a bit sequence. We can apply the VL-
DNA scheme as a post-processing method to any encoding scheme to enhance the
storage capacity.

##  5\. Evaluation

This section evaluates the VL-DNA scheme in aspects of capacity improvements
and payload length selection. Following previous works (Organick et al.,
2018)(Wei et al., 2022), we generate a primer library with 28,000 primers for
the evaluation. To obtain DNA tube capacity, we adopt the 1.55 $\times 10^{6}$
as the parallel factor and apply the same capacity calculation as described in
Section 2.2.

###  5.1. Tube Capacity Improvements

In this subsection, we use multiple encoding schemes to encode digital data
and apply two VL-DNA schemes to evaluate the improvements in the number of
usable primers and tube capacity. At the time this paper is completed, the
only scheme that tries to alleviate the primer-payload collision problem is
payload randomization used by Organick et al. (Organick et al., 2018). The
randomization is done by decoding collided payloads back to bit sequences and
XOR the bit sequences with a number of pseudo-random bit sequences. The scheme
keeps randomizing the input data until the randomized data will be encoded
into a DNA sequence without any collision. This scheme works well only in
small-scale data with a small-scale primer library. Given the size of our
primer library (i.e., 28,000 primers), each payload has to be randomized many
times to have no collision with any primer in the library. As the input data
set keeps scaling, the randomization scheme consumes unacceptable time for
collision checking with BLAST and DNA encoding/decoding. Randomization also
needs a humongous randomization seed mapping table to record which
randomization has been applied on a payload.

To fairly evaluate the VL-DNA scheme, we designed three baselines and compare
them with two VL-DNA schemes:

  * •

Fixed 200 bases: Cut the encoded DNA sequence into multiple fixed 200 bases
payloads

  * •

Fixed 200 bases + 5 randomization opportunities: We also cut the encoded DNA
sequence into multiple fixed 200 bases payloads. After that, each payload can
be randomized at most 5 times. We check the collisions of each randomization
and select the randomized result that collides with the least number of
primers. This is different from the original randomization scheme which allows
randomizing a payload unlimited times.111Grass is encoded and decoded three
DNA bases at a time which is not divisible by 200 bases. When decoding
payloads generated by Grass code, we leave the last two bases unchanged and
only randomize the first 198 bases.

  * •

Fixed 200 bases + 10 randomization opportunities: Same as the last baseline
except that each 200 bases payload has 10 randomization opportunities.

  * •

VL-DNA (collisions): Apply the VL-DNA scheme to cut payloads based on the
collision statistics reported by BLAST (Altschul et al., 1990). The procedure
is shown in Figure. 5. The VL-DNA algorithm is collisions-based (i.e.,
prioritizes the recovery of primers with fewer collisions) as discussed in
Section. 3.3.

  * •

VL-DNA (conflicts): Same as VL-DNA (collisions) except that the VL-DNA
algorithm is primer conflicts based (i.e., prioritizes the recovery of primers
that have fewer conflicts with other primers).

We have collected digital data from ImageNet (Deng et al., 2009), LibriSpeech
(Panayotov et al., 2015) and other small collections from InternetArchive
(InternetArchive, 2023). The types of digital data have insignificant
influence on collisions because all possible bit sequences will appear
multiple times as data set scales (Wei et al., 2022). Therefore, we mixed the
above data to mimic a common archival storage input. First, we apply
Reed–Solomon(255,239) on the input digital data to append 16 parity bytes to
each 239 data bytes. We then implemented three state-of-the-art encoding
schemes: Rotation code (Bornholt et al., 2016)(Yazdi et al., 2015b), Blawat
code (Blawat et al., 2016), and Grass code (Grass et al., 2015), to encode the
data respectively.

(a) Number of usable primers

(b) Achieved tube capacity

Figure 6. Enhancements of VL-DNA in the number of usable primers and tube
capacity. The parallel factor is 1.55 $\times 10^{6}$. The encoding density of
Blawat/Grass/Rotation is 1.6, 1.78, 1.58.

We respectively perform the three baselines and two VL-DNA schemes on the
encoded DNA sequences. The results are shown in Figure 6(a). Due to the
difference in encoding schemes, Rotation code initially has more usable
primers than Blawat and Grass (Rotation: 8,136, Blawat: 56, Grass: 210) when
we only cut fixed 200 bases. That is because Rotation code creates a
particular sequence pattern on its payloads: every DNA base will differ from
the last base. This pattern makes the Rotation code avoid collisions with
primers that have several identical consecutive bases. In comparison, Blawat
code and Grass code do not restrict a string pattern on their payloads and
thus suffer more collisions (see more analysis in (Wei et al., 2022)). This
difference makes DNA payloads of Blawat code and Grass code have more
collisions than DNA payloads of Rotation code. As a consequence, VL-DNA can
recover more primers in Rotation code than Blawat code and Grass Code.
Regardless of the different collision resistance of different encoding
schemes, the VL-DNA scheme can still recover thousands of primers (e.g.,
Blawat: 1,029, Grass: 908, Rotation: 1,566 in the collisions-based VL-DNA). To
recover those primers, the VL-DNA scheme (collisions-based) respectively cuts
0.94 million, 1.07 million, and 49.69 million collisions in payloads of Blawat
(157 billion DNA bases), Grass (162 billion DNA bases), and Rotation (1,398
billion DNA bases). This indicates a rather acceptable overhead of the VL-DNA
scheme. The average payload length of collisions-based VL-DNA is 199.87 for
Blawat code, 199.85 for Grass code, and 198.54 for Rotation code. Although
some payloads are tens of bases shorter than the maximum payload length (e.g.,
160 vs 200), the VL-DNA algorithm only recovers primers with fewer collisions,
and the large data set can amortize the length reduction of a few payloads.

Figure 7. Rank primers based on collision number and conflict primer number.
The encoding scheme used is Rotation and the input data is ImageNet.

The recovery of usable primers enhances tens of Gigabytes of tube capacity as
shown in Figure 6(b). Compared with only fixed 200 bases, Blawat code and
Grass code become much more practical after the VL-DNA scheme improves the
tube capacity (i.e., 19x capacity increase for Blawat and 5x capacity increase
for Grass). Rotation code also improves 18.27% of its tube capacity despite
the relatively large initial tube capacity. On the other hand, the two
randomization schemes do not significantly increase the number of usable
primers and tube capacity. That is because the randomization schemes are
essentially equivalent to selecting the most collision-resistant bit sequence
from 5 or 10 randomized bit sequences. Even though the selected randomized bit
sequence after encoding can have fewer collisions than other randomized bit
sequences, the selected bit sequence is still constrained by the encoding
schemes. Due to the absence of collision resistance, Blawat code and Grass
code still suffer from the collision problem even applied with randomization
schemes. Rotation code, because of the collision resistance stemming from its
intrinsic special payload pattern, benefits a little from the randomization
schemes. However, the increase is still subtle compared with the VL-DNA
scheme. If the number of primers in a primer library keeps increasing, the
randomization scheme can provide less and less benefit.

When comparing the VL-DNA schemes based on either primer collisions or primer
conflicts, the conflict-based scheme usually recovers a few more primers but
has a shorter average payload length. However, the differences are negligible.
That is because the primer collision number and primer conflict number have a
very strong correlation, as shown in Figure 7. In Fig.7, X-axis is the ranking
of collided primers based on the number of collisions, and Y-axis is the
ranking based on the number of conflicts. The encoding scheme used is Rotation
code (Bornholt et al., 2016), and the digital data is ImageNet (Deng et al.,
2009). The Pearson correlation coefficient, a measure of the linear dependence
between the number of conflict primers and collisions, is 0.98. That means
primers with many collisions also tend to have many conflicted primers. It is
because conflicts come from the inappropriate position of collisions, and a
primer with fewer collisions usually has a more negligible conflict
probability. This observation allows us to prioritize primers either based on
the number of collisions or the number of conflicted primers rather than any
complicated combination schemes.

###  5.2. Comparison of Payload Length Groups

Table 1. Comparison of Length groups in terms of the number of usable primers and tube capacity Length groups | # usable primers | Tube capacity
---|---|---
150/160/190/200 | 9,702 | 257.35 GB
————– | — | —-
150/160/180/200 | 9,657 | 255.11 GB
150/170/190/200 | 9,652 | 255.69 GB
150/170/180/200 | 9,652 | 255.48 GB
150/180/190/200 | 9,643 | 255.49 GB
160/170/180/200 | 9,583 | 254.66 GB
160/170/190/200 | 9,612 | 255.50 GB
160/180/190/200 | 9,585 | 254.83 GB
170/180/190/200 | 9,532 | 253.59 GB
————— | — | —-
160/170/180/190/200 | 9,628 | 255.80 GB
150/160/170/180/190/200 | 9,756 | 258.96 GB
————— | — | —-
100/130/160/200 | 9,885 | 254.23 GB
100/140/170/200 | 9,822 | 253.71 GB

This subsection compares the 150/160/190/200 length group to other length
groups. Table 1 lists the number of usable primers and the obtained tube
capacity of different length groups. The scheme used is collisions-based VL-
DNA. All length groups are supposed to have a length of 200 so that we can cut
the maximum payload length when the DNA sequence has no collisions. We first
consider the lengths $\in$ [150,200] to ensure considerable long payload
lengths. Meanwhile, the lengths are multiple of 10 for ease of implementation.
The first length group in Table 1 is our length group. The following eight
length groups are all possible groups that have four lengths and the lengths
satisfy the above demands. Our length group outperforms all other four length
groups in terms of the number of usable primers and obtained tube capacity.
That is mainly because the combination of 150/160/190/200 can cover more bases
(the number of covered bases is defined in Section. 3.1). 150/160/190/200 can
have potential cut points every ten bases as early as 450th bases. In
comparison, other groups have recurrent cut points since 600+th bases.

We also compare groups that have more than four lengths (the two length groups
in the middle). Although the two length groups have five and six variable
lengths, they may not be better or just slightly better than the
150/160/190/200 group. Nevertheless, they need one more DNA base to indicate
the length used. Considering the overhead of the VL-DNA scheme (i.e.,
reduction of payload length) is just one or less than one DNA base (Section
5.1), trading one more DNA base for the limited increases in the number of
covered bases is relatively costly. We only show length groups with up to six
lengths because the capacity increment diminishes as the number of lengths
increases.

Moreover, we extend the length space from [150,200] to [100,200] to check
whether shorter payload lengths can recover significantly more primers (the
last two length groups). Since there are two many possible length groups, we
only show two of them. Other length groups roughly have similar trends.
Shorter payloads do recover more usable primers than our four length group and
even the six length group. However, the capability of recovering more primers
means cutting more collisions with shorter payloads and thus leading to a
suboptimal tube capacity.

The above discussion is based on the current practical payload length (200
bases). However, the VL-DNA scheme also works well for future DNA strand
lengths. As strand length increases, it is reasonable to have more basic
lengths to combine more variable lengths because the increased strand length
amortizes the overhead of metadata (i.e., indicating length). Moreover, as
strand length increases, the capacity of primer also increases. VL-DNA, which
targets to recover more usable primers, becomes ever more valuable.

##  6\. Conclusion

This paper proposes a variable payload length scheme for DNA storage systems.
This scheme serves as a post-processing to enhance DNA tube capacity by
recovering more usable primers. It can be applied on top of any encoding
schemes. Evaluation of multiple existing encoding schemes shows that our
scheme can improve tens of Gigabytes of tube capacity, which counts for at
least 18.27% tube capacity.

###### Acknowledgements.

To Robert, for the bagels and explaining CMYK and color spaces.

## References

  * (1)
  * com ([n. d.) ]computationalbiology [n. d.].  The digital side of biology.  https://phys.org/news/2011-03-digital-side-biology.html.  Accessed: 2022-09-12.
  * DNA ([n. d.) ]DNAsimulator [n. d.].  DNA Storage Simulation.  https://master.dbahb2jho41s4.amplifyapp.com/.  Accessed: 2022-09-12.
  * Oli ([n. d.) ]OligoAnalyzer [n. d.].  Integrated DNA technology: OligoAnalyzer.  https://www.idtdna.com/calc/analyzer.  Accessed: 2022-09-12.
  * MSI ([n. d.) ]MSI [n. d.].  Minnesota Supercomputing Institute (MSI) at the University of Minnesota.  http://www.msi.umn.edu.  Accessed: 2022-09-12.
  * del ([n. d.) )]deltaG1 [n. d.]a.  OligoArchitect Online - Glossary of Parameters.  https://www.gene-quantification.de/oligo_architect_glossary.pdf.  Accessed: 2022-09-12.
  * dep ([n. d.) ]depth [n. d.].  Sequencing depth.  https://www.genomicseducation.hee.nhs.uk/glossary/read-depth/.  Accessed: 2022-09-12.
  * del ([n. d.) )]deltaG2 [n. d.]b.  What is delta G value?  https://www.researchgate.net/post/What-is-delta-G-value.  Accessed: 2022-09-12.
  * DNA (2022) [Online] Accessed on Augest. 6, 2022.  New breakthrough gets us closer to using DNA as data storage.  ([Online] Accessed on Augest. 6, 2022).
  * Abd-Elsalam (2003) Kamel A Abd-Elsalam. 2003\.  Bioinformatic tools and guideline for PCR primer design.  _african Journal of biotechnology_ 2, 5 (2003), 91–95.
  * Allentoft et al. (2012) Morten E Allentoft, Matthew Collins, David Harker, James Haile, Charlotte L Oskam, Marie L Hale, Paula F Campos, Jose A Samaniego, M Thomas P Gilbert, Eske Willerslev, et al. 2012\.  The half-life of DNA in bone: measuring decay kinetics in 158 dated fossils.  _Proceedings of the Royal Society B: Biological Sciences_ 279, 1748 (2012), 4724–4733.
  * Alliance (2021) DNA Data Storage Alliance. 2021\.  _Preserving Our Digital Legacy: an Introduction To Dna Data Storage_.  Technical Report. tech. rep. June.
  * Altschul et al. (1990) Stephen F Altschul, Warren Gish, Webb Miller, Eugene W Myers, and David J Lipman. 1990.  Basic local alignment search tool.  _Journal of molecular biology_ 215, 3 (1990), 403–410.
  * Anavy et al. (2018) Leon Anavy, Inbal Vaknin, Orna Atar, Roee Amit, and Zohar Yakhini. 2018.  Improved DNA based storage capacity and fidelity using composite DNA letters.  _bioRxiv_ (2018), 433524\.
  * Appuswamy et al. (2019) Raja Appuswamy, Kevin Le Brigand, Pascal Barbry, Marc Antonini, Olivier Madderson, Paul Freemont, James McDonald, and Thomas Heinis. 2019.  OligoArchive: Using DNA in the DBMS storage hierarchy.. In _CIDR_.
  * Atikoglu et al. (2012) Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. 2012.  Workload analysis of a large-scale key-value store. In _Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems_. 53–64.
  * Batu et al. (2004) Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. 2004.  Reconstructing strings from random traces.  _Departmental Papers (CIS)_ (2004), 173.
  * Baum (1995) Eric B Baum. 1995\.  Building an associative memory vastly larger than the brain.  _Science_ 268, 5210 (1995), 583–585.
  * Bhagwat et al. (2009) Deepavali Bhagwat, Kave Eshghi, Darrell DE Long, and Mark Lillibridge. 2009.  Extreme binning: Scalable, parallel deduplication for chunk-based file backup. In _2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems_. IEEE, 1–9.
  * Blawat et al. (2016) Meinolf Blawat, Klaus Gaedke, Ingo Huetter, Xiao-Ming Chen, Brian Turczyk, Samuel Inverso, Benjamin W Pruitt, and George M Church. 2016.  Forward error correction for DNA data storage.  _Procedia Computer Science_ 80 (2016), 1011–1022.
  * Bornholt et al. (2016) James Bornholt, Randolph Lopez, Douglas M Carmean, Luis Ceze, Georg Seelig, and Karin Strauss. 2016\.  A DNA-based archival storage system. In _Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems_. 637–649.
  * Cao et al. (2018) Zhichao Cao, Hao Wen, Fenggang Wu, and David HC Du. 2018\.  $\\{$ALACC$\\}$: Accelerating restore performance of data deduplication systems using adaptive look-ahead window assisted chunk caching. In _16th $\\{$USENIX$\\}$ Conference on File and Storage Technologies ($\\{$FAST$\\}$ 18)_. 309–324.
  * Carlson (2017) R Carlson. 2017\.  Guesstimating the size of the global array synthesis market.  _Synthesis August_ 30 (2017).
  * Carmean et al. (2018) Douglas Carmean, Luis Ceze, Georg Seelig, Kendall Stewart, Karin Strauss, and Max Willsey. 2018\.  DNA data storage and hybrid molecular–electronic computing.  _Proc. IEEE_ 107, 1 (2018), 63–72.
  * Ceze et al. (2019) Luis Ceze, Jeff Nivala, and Karin Strauss. 2019.  Molecular digital data storage using DNA.  _Nature Reviews Genetics_ 20, 8 (2019), 456–466.
  * Choi et al. (2018) Yeongjae Choi, Taehoon Ryu, Amos C Lee, Hansol Choi, Hansaem Lee, Jaejun Park, Suk-Heung Song, Seoju Kim, Hyeli Kim, Wook Park, et al. 2018\.  Addition of degenerate bases to DNA-based data storage for increased information capacity.  _bioRxiv_ (2018), 367052\.
  * Choi et al. (2019) Yeongjae Choi, Taehoon Ryu, Amos C Lee, Hansol Choi, Hansaem Lee, Jaejun Park, Suk-Heung Song, Seojoo Kim, Hyeli Kim, Wook Park, et al. 2019\.  High information capacity DNA-based data storage with augmented encoding characters using degenerate bases.  _Scientific reports_ 9, 1 (2019), 1–7.
  * Church et al. (2012) George M Church, Yuan Gao, and Sriram Kosuri. 2012\.  Next-generation digital information storage in DNA.  _Science_ 337, 6102 (2012), 1628–1628.
  * Corporation (2023) International Data Corporation. 2023\.  Worldwide Global StorageSphere Forecast, 2021–2025: To Save or Not to Save Data, That Is the Question.  Retrieved March 1, 2023 from https://www.idc.com/getdoc.jsp?containerId=US47509621
  * Das et al. (1999) Simantini Das, Satish C Mohapatra, and James T Hsu. 1999\.  Studies on primer-dimer formation in polymerase chain reaction (PCR).  _Biotechnology Techniques_ 13, 10 (1999), 643–646.
  * Deng et al. (2009) J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. 2009.  ImageNet: A Large-Scale Hierarchical Image Database. In _CVPR09_.
  * Deng et al. (2019) Li Deng, Yixin Wang, MD Noor-A-Rahim, Yong Liang Guan, Zhiping Shi, Erry Gunawan, and Chueh Loo Poh. 2019.  Optimized code design for constrained DNA data storage with asymmetric errors.  _IEEE Access_ 7 (2019), 84107–84121.
  * Dieffenbach et al. (1993) CW Dieffenbach, TM Lowe, and GS Dveksler. 1993.  General concepts for PCR primer design.  _PCR methods appl_ 3, 3 (1993), S30–S37.
  * Dutch (2008) Mike Dutch. 2008\.  Understanding data deduplication ratios. In _SNIA Data Management Forum_. 7.
  * El-Shaikh et al. (2022) Alex El-Shaikh, Marius Welzel, Dominik Heider, and Bernhard Seeger. 2022.  High-scale random access on DNA storage systems.  _NAR genomics and bioinformatics_ 4, 1 (2022), lqab126.
  * Erlich and Zielinski (2017) Yaniv Erlich and Dina Zielinski. 2017.  DNA Fountain enables a robust and efficient storage architecture.  _Science_ 355, 6328 (2017), 950–954.
  * Everitt et al. ([n. d.) ]everitt2011cluster Brian S Everitt, Sabine Landau, Morven Leese, and Daniel Stahl. [n. d.].  Cluster Analysis. –John Wiley & Sons.  _Ltd., New York_ ([n. d.]), 330\.
  * Extance (2016) Andy Extance. 2016\.  How DNA could store all the world’s data.  _Nature_ 537, 7618 (2016).
  * Fontana Jr and Decad (2018) Robert E Fontana Jr and Gary M Decad. 2018.  Moore’s law realities for recording systems and memory storage components: HDD, tape, NAND, and optical.  _AIP Advances_ 8, 5 (2018), 056506.
  * for Policy Studies (2018) Potomac Institute for Policy Studies. 2018\.  _The Future of DNA Data Storage_.  Retrieved March 1, 2023 from https://potomacinstitute.org/images/studies/Future_of_DNA_Data_Storage.pdf
  * Fu et al. (2015) Min Fu, Dan Feng, Yu Hua, Xubin He, Zuoning Chen, Wen Xia, Yucheng Zhang, and Yujuan Tan. 2015\.  Design tradeoffs for data deduplication performance in backup workloads. In _13th $\\{$USENIX$\\}$ Conference on File and Storage Technologies ($\\{$FAST$\\}$ 15)_. 331–344.
  * Gantz and Reinsel (2010) John Gantz and David Reinsel. 2010.  The Digital Universe Decade – Are You Ready?  _IDC White Paper_ (2010).
  * Goldman et al. (2013) Nick Goldman, Paul Bertone, Siyuan Chen, Christophe Dessimoz, Emily M LeProust, Botond Sipos, and Ewan Birney. 2013\.  Towards practical, high-capacity, low-maintenance information storage in synthesized DNA.  _Nature_ 494, 7435 (2013), 77–80.
  * Grass et al. (2015) Robert N Grass, Reinhard Heckel, Michela Puddu, Daniela Paunescu, and Wendelin J Stark. 2015.  Robust chemical preservation of digital information on DNA in silica with error-correcting codes.  _Angewandte Chemie International Edition_ 54, 8 (2015), 2552–2555.
  * Guo and Efstathopoulos (2011) Fanglu Guo and Petros Efstathopoulos. 2011.  Building a High-performance Deduplication System.. In _USENIX annual technical conference_.
  * Heinis (2019) Thomas Heinis. 2019\.  Survey of Information Encoding Techniques for DNA.  _arXiv preprint arXiv:1906.11062_ (2019).
  * InternetArchive (2023) InternetArchive. 2023\.  Internet Archive Public library.  Retrieved March 1, 2023 from https://archive.org/
  * Jain et al. (2020) Siddhartha Jain, Farzad Farnoud, Moshe Schwartz, and Jehoshua Bruck. 2020.  Coding for Optimized Writing Rate in DNA Storage.  _2020 IEEE International Symposium on Information Theory (ISIT)_ (2020), 711–716.
  * Kannan and Zacharias (2007) Srinivasaraghavan Kannan and Martin Zacharias. 2007.  Folding of a DNA hairpin loop structure in explicit solvent using replica-exchange molecular dynamics simulations.  _Biophysical journal_ 93, 9 (2007), 3218–3228.
  * Korte and Vygen (2012) Bernhard Korte and Jens Vygen. 2012.  Bin-packing.  In _Kombinatorische Optimierung_. Springer, 499–516.
  * Kosuri and Church (2014) Sriram Kosuri and George M Church. 2014.  Large-scale de novo DNA synthesis: technologies and applications.  _Nature methods_ 11, 5 (2014), 499.
  * Kruus et al. (2010) Erik Kruus, Cristian Ungureanu, and Cezary Dubnicki. 2010\.  Bimodal content defined chunking for backup streams.. In _Fast_. 239–252.
  * Lai et al. (2015) Chunbo Lai, Song Jiang, Liqiong Yang, Shiding Lin, Guangyu Sun, Zhenyu Hou, Can Cui, and Jason Cong. 2015\.  Atlas: Baidu’s key-value storage system for cloud data. In _2015 31st Symposium on Mass Storage Systems and Technologies (MSST)_. IEEE, 1–14.
  * Lee et al. (2018) Henry H Lee, Reza Kalhor, Naveen Goela, Jean Bolot, and George M Church. 2018.  Enzymatic DNA synthesis for digital information storage.  _bioRxiv_ (2018), 348987\.
  * Lenz et al. (2020) Andreas Lenz, Paul H. Siegel, Antonia Wachter-Zeh, and Eitan Yaakobi. 2020.  Coding Over Sets for DNA Storage.  _IEEE Transactions on Information Theory_ 66 (2020), 2331–2351.
  * Li et al. (2021) Bingzhe Li, Li Ou, and David Du. 2021.  Img-dna: approximate dna storage for images. In _Proceedings of the 14th ACM International Conference on Systems and Storage_. 1–9.
  * Li et al. (2020) Bingzhe Li, Nae Young Song, Li Ou, and David HC Du. 2020\.  Can We Store the Whole World’s Data in $\\{$DNA$\\}$ Storage?. In _12th $\\{$USENIX$\\}$ Workshop on Hot Topics in Storage and File Systems (HotStorage 20)_.
  * Lin et al. (2022) Dehui Lin, Yasamin Tabatabaee, Yash Pote, and Djordje Jevdjic. 2022.  Managing reliability skew in DNA storage. In _Proceedings of the 49th Annual International Symposium on Computer Architecture_. 482–494.
  * Lu and Kim (2021) Xiaozhou Lu and Sunghwan Kim. 2021.  Design of Nonbinary Error Correction Codes With a Maximum Run-Length Constraint to Correct a Single Insertion or Deletion Error for DNA Storage.  _IEEE Access_ 9 (2021), 135354–135363.
  * Luby (2002) Michael Luby. 2002\.  LT codes. In _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ IEEE Computer Society, 271–271.
  * Ma et al. (2006) Hairong Ma, David J Proctor, Elzbieta Kierzek, Ryszard Kierzek, Philip C Bevilacqua, and Martin Gruebele. 2006.  Exploring the energy landscape of a small RNA hairpin.  _Journal of the American Chemical Society_ 128, 5 (2006), 1523–1530.
  * Matange et al. (2021) Karishma Matange, James M Tuck, and Albert J Keung. 2021\.  DNA stability: a central design consideration for DNA data storage systems.  _Nature communications_ 12, 1 (2021), 1–9.
  * Matteucci and Caruthers (1981) Mark Douglas Matteucci and M Ho Caruthers. 1981.  Synthesis of deoxyoligonucleotides on a polymer support.  _Journal of the American Chemical Society_ 103, 11 (1981), 3185–3191.
  * Meyer and Bolosky (2012) Dutch T Meyer and William J Bolosky. 2012.  A study of practical deduplication.  _ACM Transactions on Storage (ToS)_ 7, 4 (2012), 1–20.
  * Miller (2020) Ethan L Miller. 2020\.  The Future of the Past: Challenges in Archival Storage.  (2020).
  * Muthitacharoen et al. (2001) Athicha Muthitacharoen, Benjie Chen, and David Mazieres. 2001\.  A low-bandwidth network file system. In _Proceedings of the eighteenth ACM symposium on Operating systems principles_. 174–187.
  * Nemhauser et al. (1978) George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions—I.  _Mathematical programming_ 14, 1 (1978), 265–294.
  * Newman (2004) Mark EJ Newman. 2004\.  Fast algorithm for detecting community structure in networks.  _Physical review E_ 69, 6 (2004), 066133.
  * Newman and Girvan (2004) Mark EJ Newman and Michelle Girvan. 2004.  Finding and evaluating community structure in networks.  _Physical review E_ 69, 2 (2004), 026113.
  * Newman et al. (2019) Sharon Newman, Ashley P Stephenson, Max Willsey, Bichlien H Nguyen, Christopher N Takahashi, Karin Strauss, and Luis Ceze. 2019\.  High density DNA data storage library via dehydration with digital microfluidic retrieval.  _Nature communications_ 10, 1 (2019), 1–6.
  * Niedringhaus et al. (2011) Thomas P Niedringhaus, Denitsa Milanova, Matthew B Kerby, Michael P Snyder, and Annelise E Barron. 2011.  Landscape of next-generation sequencing technologies.  _Analytical chemistry_ 83, 12 (2011), 4327–4341.
  * Organick et al. (2018) Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Sergey Yekhanin, Konstantin Makarychev, Miklos Z Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, et al. 2018\.  Random access in large-scale DNA data storage.  _Nature biotechnology_ 36, 3 (2018), 242.
  * Organick et al. (2020) Lee Organick, Yuan-Jyue Chen, Siena Dumas Ang, Randolph Lopez, Xiaomeng Liu, Karin Strauss, and Luis Ceze. 2020.  Probing the physical limits of reliable DNA data retrieval.  _Nature communications_ 11, 1 (2020), 1–7.
  * Panayotov et al. (2015) Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. 2015.  Librispeech: an asr corpus based on public domain audio books. In _2015 IEEE international conference on acoustics, speech and signal processing (ICASSP)_. IEEE, 5206–5210.
  * Popescu et al. (2012) Adrian Daniel Popescu, Vuk Ercegovac, Andrey Balmin, Miguel Branco, and Anastasia Ailamaki. 2012.  Same queries, different data: Can we predict runtime performance?. In _2012 IEEE 28th International Conference on Data Engineering Workshops_. IEEE, 275–280.
  * Quinlan and Dorward (2002) Sean Quinlan and Sean Dorward. 2002.  Venti: A New Approach to Archival Storage.. In _FAST_ , Vol. 2. 89–101.
  * Reinsel et al. (2018) David Reinsel, John Gantz, and John Rydning. 2018\.  The digitization of the world from edge to core.  _IDC White Paper_ (2018).
  * Richterich (1998) Peter Richterich. 1998\.  Estimation of errors in “raw” DNA sequences: a validation study.  _Genome Research_ 8, 3 (1998), 251–259.
  * Rutten et al. (2018) Martin GTA Rutten, Frits W Vaandrager, Johannes AAW Elemans, and Roeland JM Nolte. 2018.  Encoding information into polymers.  _Nature Reviews Chemistry_ 2, 11 (2018), 365–381.
  * Sella et al. (2021) Omer S Sella, Amir Apelbaum, Thomas Heinis, Jasmine Quah, and Andrew W Moore. 2021.  DNA archival storage, a bottom up approach. In _Proceedings of the 13th ACM Workshop on Hot Topics in Storage and File Systems_. 58–63.
  * Singh et al. (2000) Vinay K Singh, R Govindarajan, Sita Naik, and Anil Kumar. 2000.  The effect of hairpin structure on PCR amplification efficiency.  _Mol Biol Today_ 1, 3 (2000), 67–69.
  * Song et al. (2019) Xin Song, Shalin Shah, and John Reif. 2019.  Multidimensional data organization and random access in large-scale DNA storage systems.  _bioRxiv_ (2019), 743369\.
  * Steadman and Fair (2012) Andrew Steadman and Ivan Fair. 2012.  Variable-length constrained sequence codes.  _IEEE communications letters_ 17, 1 (2012), 139–142.
  * Steadman and Fair (2016) Andrew Steadman and Ivan Fair. 2016.  Simplified search and construction of capacity-approaching variable-length constrained sequence codes.  _IET Communications_ 10, 14 (2016), 1697–1704.
  * Tarasov et al. (2012) Vasily Tarasov, Amar Mudrankit, Will Buik, Philip Shilane, Geoff Kuenning, and Erez Zadok. 2012\.  Generating realistic datasets for deduplication analysis. In _Presented as part of the 2012 USENIX Annual Technical Conference (ATC 12)_. 261–272.
  * Tomek et al. (2019) Kyle J Tomek, Kevin Volkel, Alexander Simpson, Austin G Hass, Elaine W Indermaur, James M Tuck, and Albert J Keung. 2019.  Driving the scalability of DNA-based information storage systems.  _ACS synthetic biology_ 8, 6 (2019), 1241–1248.
  * Van Dijk et al. (2014) Erwin L Van Dijk, Hélène Auger, Yan Jaszczyszyn, and Claude Thermes. 2014.  Ten years of next-generation sequencing technology.  _Trends in genetics_ 30, 9 (2014), 418–426.
  * Wallace et al. (2012) Grant Wallace, Fred Douglis, Hangwei Qian, Philip Shilane, Stephen Smaldone, Mark Chamness, and Windsor Hsu. 2012.  Characteristics of backup workloads in production systems.. In _FAST_ , Vol. 12. 4–4.
  * Wang et al. (2019) Yixin Wang, Md Noor-A-Rahim, Jingyun Zhang, Erry Gunawan, Yong Liang Guan, and Chueh Loo Poh. 2019.  High capacity DNA data storage with variable-length Oligonucleotides using repeat accumulate code and hybrid mapping.  _Journal of biological engineering_ 13, 1 (2019), 1–11.
  * Wei et al. (2022) Yixun Wei, Bingzhe Li, and David HC Du. 2022.  DNA Storage: A Promising Large Scale Archival Storage?  _arXiv preprint arXiv:2204.01870_ (2022).
  * Wu et al. (2017) Jie Wu, Yu Hua, Pengfei Zuo, and Yuanyuan Sun. 2017\.  A cost-efficient rewriting scheme to improve restore performance in deduplication systems. In _Proc. MSST_.
  * Wu et al. (2021) Jianjun Wu, Shufang Zhang, Tao Zhang, and Yuhong Liu. 2021\.  HD-Code: End-to-End High Density Code for DNA Storage.  _IEEE Transactions on NanoBioscience_ 20 (2021), 455–463.
  * Xia et al. (2016) Wen Xia, Hong Jiang, Dan Feng, Fred Douglis, Philip Shilane, Yu Hua, Min Fu, Yucheng Zhang, and Yukun Zhou. 2016.  A comprehensive study of the past, present, and future of data deduplication.  _Proc. IEEE_ 104, 9 (2016), 1681–1710.
  * Xia et al. (2014a) Wen Xia, Hong Jiang, Dan Feng, and Yu Hua. 2014a.  Similarity and locality based indexing for high performance data deduplication.  _IEEE transactions on computers_ 64, 4 (2014), 1162–1176.
  * Xia et al. (2014b) Wen Xia, Hong Jiang, Dan Feng, and Lei Tian. 2014b.  Combining deduplication and delta compression to achieve low-overhead data reduction on backup datasets. In _2014 Data Compression Conference_. IEEE, 203–212.
  * Xiao and Nagamochi (2017) Mingyu Xiao and Hiroshi Nagamochi. 2017.  Exact algorithms for maximum independent set.  _Information and Computation_ 255 (2017), 126–146.
  * Xu et al. (2009) Qikai Xu, Michael R Schlabach, Gregory J Hannon, and Stephen J Elledge. 2009.  Design of 240,000 orthogonal 25mer DNA barcode probes.  _Proceedings of the National Academy of Sciences_ 106, 7 (2009), 2289–2294.
  * Yamamoto et al. (2008) Masahito Yamamoto, Satoshi Kashiwamura, Azuma Ohuchi, and Masashi Furukawa. 2008.  Large-scale DNA memory based on the nested PCR.  _Natural Computing_ 7, 3 (2008), 335–346.
  * Yazdi et al. (2017) SM Yazdi, Ryan Gabrys, and Olgica Milenkovic. 2017.  Portable and error-free DNA-based data storage.  _Scientific reports_ 7, 1 (2017), 1–6.
  * Yazdi et al. (2015a) SM Hossein Tabatabaei Yazdi, Han Mao Kiah, Eva Garcia-Ruiz, Jian Ma, Huimin Zhao, and Olgica Milenkovic. 2015a.  DNA-based storage: Trends and methods.  _IEEE Transactions on Molecular, Biological and Multi-Scale Communications_ 1, 3 (2015), 230–248.
  * Yazdi et al. (2015b) SM Hossein Tabatabaei Yazdi, Yongbo Yuan, Jian Ma, Huimin Zhao, and Olgica Milenkovic. 2015b.  A rewritable, random-access DNA-based storage system.  _Scientific reports_ 5 (2015), 14138.
  * Yin et al. (2021) Qiang Yin, Yanfen Zheng, Bin Wang, and Qiang Zhang. 2021\.  Design of Constraint Coding Sets for Archive DNA Storage.  _IEEE/ACM transactions on computational biology and bioinformatics_ PP (2021).
  * Zadeh et al. (2011) Joseph N Zadeh, Conrad D Steenberg, Justin S Bois, Brian R Wolfe, Marshall B Pierce, Asif R Khan, Robert M Dirks, and Niles A Pierce. 2011\.  NUPACK: Analysis and design of nucleic acid systems.  _Journal of computational chemistry_ 32, 1 (2011), 170–173.
  * Zhirnov et al. (2016) Victor Zhirnov, Reza M Zadegan, Gurtej S Sandhu, George M Church, and William L Hughes. 2016\.  Nucleic acid memory.  _Nature materials_ 15, 4 (2016), 366–370.
  * Zhu et al. (2008) Benjamin Zhu, Kai Li, and R Hugo Patterson. 2008.  Avoiding the Disk Bottleneck in the Data Domain Deduplication File System.. In _Fast_ , Vol. 8. 1–14.