PaperlayerView exact revision on arXiv

Source-linked AI summary

DNA-Based Storage: Trends and Methods

S. M. Hossein Tabatabaei Yazdi, Han Mao Kiah, Eva Ruiz Garcia, Jian Ma, Huimin Zhao, Olgica Milenkovic

arXiv:1507.01611v1cs.ETcs.IT

TL;DR

DNA storage must provide durable, high-capacity recording while addressing limited access, rewriting, synthesis cost, and molecular errors. The paper surveys storage architectures and biochemical methods, then develops constrained coding schemes that adapt representations to DNA. These schemes target archival and random-access channels through address avoidance, balanced base content, substring constraints, and error-control mechanisms.

  • Problem

    DNA storage offers durable, high-capacity recording, but practical systems must address limited partial access, unavailable rewriting, synthesis and sequencing errors, and costly, low-throughput synthesis.

  • Method

    The paper surveys DNA storage architectures and synthesis, sequencing, and editing methods, then introduces constrained codes that avoid address patterns, balance base content, and add error-control structure.

  • Results

    The paper presents constrained coding techniques for archival, random-access, and rewritable DNA storage channels, including mutually uncorrelated addresses and error-correcting coding mechanisms.

  • Takeaways & Limitations

    Adapting stored signals to DNA constraints provides coding strategies intended to reduce inherent storage-system error rates while supporting selective access and rewriting.

Abstract

from arXiv · show

We provide an overview of current approaches to DNA-based storage system design and accompanying synthesis, sequencing and editing methods. We also introduce and analyze a suite of new constrained coding schemes for both archival and random access DNA storage channels. The mathematical basis of our work is the construction and design of sequences over discrete alphabets that avoid pre-specified address patterns, have balanced base content, and exhibit other relevant substring constraints. These schemes adapt the stored signals to the DNA medium and thereby reduce the inherent error-rate of the system.

1. INTRODUCTION

DNA-based storage combines molecular durability and density with coding, synthesis, sequencing, and editing methods to support reliable archival and potentially random-access, rewritable storage. The paper surveys these system components and constraints, emphasizing error control, access, and scalable DNA synthesis.

  • Motivation: DNA offers non-volatile storage with exceptional integrity and extremely high capacity, motivating its use as a medium for massive data archives.The introduction cites recovery of DNA from species extinct for more than 10,000 years and describes a human cell as having very high storage capacity.
  • System Challenges: Random-access, rewritable storage requires unique, mutually compatible addresses, non-overlapping blocks, and low synthesis and sequencing error rates.These requirements address partial-access limitations, rewrite inefficiency from overlapping blocks, and errors introduced during writing and reading.
  • Coding Approach: Constrained and error-control codes adapt DNA representations by avoiding error-prone patterns, synchronizing prefixes for block access, and adding redundancy against rewrite errors.The described methods include DNA-pattern avoidance, prefix-synchronized coding, and LDPC coding.
  • System Architecture: Current architectures encode digital information into DNA blocks, synthesize and store those blocks, optionally edit them, and sequence selected blocks before decoding.Encoding and DNA encoding add controlled redundancy to combat synthesis and sequencing errors; editing creates mutations, while reading retrieves selected blocks by sequencing.
  • Paper Scope: The paper surveys synthesis, sequencing, editing, storage paradigms, and associated coding techniques before presenting constrained codes for rewritable and random-access systems.The roadmap assigns these topics to Sections 2–6 and relates the new codes to classical magnetic and optical storage codes.
  • Synthesis Constraints: $0.15 per nucleotide is cited for phosphoramidite column synthesis, while microarray synthesis is roughly $0.001 per nucleotide but usually remains limited to oligos no longer than 200 nt.Microarrays reduce reagent consumption and can synthesize tens to hundreds of thousands of oligos per array, but typically have higher error rates than column methods.

3) Complex Strand and Gene Synthesis:

DNA storage systems rely on synthesis, assembly, error-removal, sequencing, and editing methods to create, verify, and rewrite encoded DNA. These methods address practical constraints including synthesis errors, cross-hybridization, secondary structure, and access to selected DNA regions.

  • Complex strand synthesis: Longer DNA fragments are assembled by ligation-based or polymerase-based reactions that fuse overlapping oligos, followed by amplification and verification.Gibson assembly can combine more than 30 oligos with a plasmid in one step, while other work assembled a mouse mitochondrial genome from 600 overlapping oligos.
  • Synthesis methods: Column-based oligo synthesis adds nucleotides through repeated de-blocking, coupling, capping, and oxidation cycles on a solid support.The completed oligonucleotide is then cleaved from the support and deprotected.
  • Synthesis methods: Microarray synthesis lowers oligonucleotide costs but produces small amounts and heterogeneous pools that complicate assembly and increase cross-hybridization.PCR amplification, hybridization selection, optimized assembly, and subpool isolation are used to reduce these problems, although pools larger than 10000 remain difficult to assemble.
  • DNA editing: DNA rewriting uses gBlocks for relatively short deletion or insertion edits and OEPCR for customized changes produced by overlapping primers and PCR.gBlocks replace a cleaved edit region, whereas OEPCR fuses overlapping fragments without requiring restriction sites or enzymes and is mostly used for inserts longer than 100 nucleotides.
  • Error correction: Mismatch-recognition and sequencing-based purification methods remove erroneous synthesized strands before storage use.MutS-based approaches can reduce errors to 1 nucleotide per 10 Kb, while one NGS-based approach reported 1 nucleotide error per 21 Kb; other methods selectively recover sequence-verified oligonucleotides.
  • Error correction: Synthesis errors are tolerable in DNA storage because carefully designed parity-checks can combat them, unlike in biological and medical applications where single substitutions may be detrimental.The paper frames coding-based correction as a distinguishing requirement of storage applications.

5. ARCHIVAL DNA-BASED STORAGE

The Church-Gao-Kosuri architecture maps digital data to constrained DNA blocks with addressing, then uses amplification, sequencing, and consensus decoding to recover the file. In an experiment, it encoded a 5.27 MB HTML file and achieved a reported system error rate below 2 × 10−6.

  • Architecture: The method converts each data bit to A/C or T/G while randomly selecting bases to avoid homopolymer runs longer than a specified limit.The approach also uses addressing oligonucleotides and block construction to avoid assembling long synthetic strands.
  • Architecture: A 5.27 MB HTML file was divided into 54,898 blocks of 159 oligonucleotides, including information, addressing, and amplification sequences.
  • Readout: The synthesized library was amplified by limited-cycle PCR and sequenced on an Illumina HiSeq system, after which overlapping blocks and block encodings supported decoding.
  • Result: 10 bit errors in 5.27 million encoded bits yielded a reported system error rate below 2 × 10−6.

Encoding example:

The Church-Gao-Kosuri encoding example transforms text into 8-bit ASCII, appends a barcode, maps bits to constrained DNA bases, and adds primers to form fixed-length codewords.

  • Encoding example:: Each symbol is first converted into an 8-bit ASCII representation.
  • Encoding example:: A unique 19-bit barcode is appended to the 96-bit data string, producing a 115-bit block.
  • Encoding example:: Bits are mapped randomly to A or C for 0 and T or G for 1 while disallowing homopolymer runs longer than three.The example also balances GC content and controls secondary structure.
  • Encoding example:: Two 22-nt primers are added to the DNA block, producing a codeword of length 22 + 115 + 22 = 159 nt.

B. The Goldman et al. Method

The Goldman et al. method compresses ASCII data into trits, maps trits to DNA oligonucleotides, and adds overlap, reverse complementation, indexing, and parity information. Its experiment decoded a 739 KB file with 100% accuracy.

  • Encoding: ASCII bytes are converted into 5 or 6 trits using an optimal Huffman code, producing a compressed file of 5.2×10^6 information bits.
  • Fragment construction: Adjacent 100-base segments overlap by 75 bases, providing four-fold coverage for each base.
  • Fragment construction: The method reverse complements alternate segments and appends file identification, intra-file location, parity-check, and orientation information.
  • Experiment: A 739 KB file containing multiple formats was synthesized with 1.2×10^7 copies per sequence, sequenced on Illumina HiSeq 2000, and decoded with 100% accuracy.

C. The Grass et al. Method

The Grass et al. method combines specialized error correction with DNA preservation practices and encodes grouped text through nested Reed-Solomon codes before mapping it to constrained DNA strings.

  • Motivation: Earlier Church-Gao-Kosuri and Goldman methods used only fragment-level single parity checks, with four-fold coverage providing additional redundancy.The paper identifies the limited error correction as a disadvantage under synthesis and sequencing errors.
  • Motivation: Grass et al. address these issues with a specialized error-correcting scheme and best practices for maintaining DNA media.
  • Encoding: Text is grouped by mapping every two characters from base 256^2 to base 47^3, forming information arrays over the finite field F(47).
  • Encoding: Outer and inner Reed-Solomon encodings transform information blocks and column vectors into codewords over F(47^m) and F(47).
  • DNA mapping: Each encoded field element is mapped to a 3-nt DNA string avoiding homopolymers of length three or longer, with primers attached for sequencing.
  • Preservation: Silica-encapsulated DNA appears to offer the most durable tested storage format because silica limits water exposure and separates DNA from the environment.

6. RANDOM ACCESS AND REWRITABLE DNA-BASED

Earlier DNA-storage methods did not support accurate partial or random access, and they lacked rewriting mechanisms. Yazdi et al. addressed these limitations with coding-theoretic methods for controlled random access and rewriting.

  • The archival architectures did not provide rewrite mechanisms.
  • Earlier methods required reconstructing the whole text to retrieve information encoded in only a few bases.Their addressing methods located reads within a file but did not ensure precise selection because of potential primer cross-hybridization with information blocks.
  • Yazdi et al. introduced coding-theoretic methods enabling rewriting and controlled random access.

A. The Yazdi et al. Method

The Yazdi et al. architecture stores information in address-flanked DNA blocks using mutually uncorrelated addresses and constrained encoding. An experiment encoded 17KB into 32 blocks and verified 100% accurate selection and rewriting of three blocks.

  • Mutually uncorrelated address strings support selective access while providing inherent error-correction capabilities.For distinct addresses, no prefix of one address of length ≤n−1 appears as a proper suffix of another.
  • Each DNA block has length L = 2n + ml and is flanked by two unique addresses, with one address used for encoding.The remaining block sequence is divided into m sub-blocks of length l after digital segments are mapped to integers.
  • The experiment encoded 17KB of university text into 32 DNA blocks of length L = 1000 bps using 32 pairs of mutually uncorrelated addresses.The encoding addresses had length n = 20 bps.
  • Each group of six words became 146-bit binary sequences, which were translated into m = 12 DNA sub-blocks of length l = 80 bps.The twelve sub-blocks were joined into a 960-bps DNA string.
  • 100% accuracy was achieved when three rewritten blocks were selected, amplified, and Sanger sequenced.The 32 fragments were mixed before rewriting with gBlocks and OEPCR editing techniques.
  • The encoding example uses the self-uncorrelated address a = ACCTG and the ENCODEa,8 algorithm.The corresponding decoding procedure applies DECODEa to the encoded output.

B. Address Design and Constrained Coding

The method designs constrained address sequences and a code CA(ℓ) to support selective random access and efficient encoding and decoding. Its address design connects DNA-storage requirements with established coding concepts.

  • Address sequences of length n are constrained for selective random access, and the code CA(ℓ) provides efficient encoding and decoding of messages.In the experiment, n = 20, ℓ = 80, and twelve 80-length data subblocks were stored.
  • The address constraints are related to running digital sums and sequence correlation, while CA(ℓ) uses prefix-synchronized encoding schemes.

C. Constrained Coding for Address Sequences

Address design combines GC balance, distance, uncorrelatedness, and avoidance of secondary structure to improve DNA-storage compatibility and selective retrieval. The paper develops constrained-code constructions but notes that jointly optimizing all constraints remains open.

  • Address constraints: Address constraints target balanced GC content, sufficient Hamming distance, uncorrelatedness, and absence of secondary structure.These constraints address sequencing-error-prone patterns, erroneous address selection, cross-hybridization, and PCR or rewriting problems.
  • GC balance: GC-prefix balance keeps addresses and their prefixes near 50% GC content, supporting stable strands and better sequencing coverage.Prefix balance is also important because information encoding uses prefix synchronization.
  • Running digital sums: A D-bounded running digital sum limits the difference between zeros and ones in every prefix to at most D.
  • Running digital sums: A binary unrestricted code of length n and minimum distance d yields a 1-BRDS set of length 2n, minimum distance 2d, and the same size M.
  • Running digital sums: The Gilbert–Varshamov bound gives a lower-bound construction for 1-BRDS sets with prescribed length and minimum distance.The supplied passage states that such sets have size bounded by the displayed expression.
  • DNA constrained codes: Mapping binary zeros to A or T and ones to G or C converts D-BRDS sets into D-GCPB DNA-sequence sets.
  • DNA constrained codes: Theorem 6.1 and the binary-to-DNA mapping provide estimates for code sizes satisfying constraints C1 and C2.
  • Sequence correlation: Correlation records positional matches between overlapping words, and autocorrelation is the correlation of a word with itself.The correlation vector is directional and can differ between X ◦Y and Y ◦X.

D. Prefix-Synchronized DNA Codes

Prefix-synchronized coding constructs DNA sequences that avoid specified address strings, enabling address-aware encoding and decoding for random-access and rewritable storage.

  • Mutually uncorrelated addresses reduce long prefix-suffix matches that can cause hybridization and assembly errors during joint sequencing.
  • The set C_A(ℓ) contains length-ℓ sequences that do not contain any address in A, and messages are mapped one-to-one into this constrained set.
  • The encoding scheme assumes mutually uncorrelated addresses ending in a common base and recursively maps integers to sequences in C_A(ℓ).
  • Theorem 6.6 establishes that ENCODE_a,ℓ is one-to-one and that decoding its output recovers every encoded integer.
  • M = 32 addresses of length n = 20 supported G_20,80 = 1.56 × 10^38, corresponding to at least 126 bits, versus at least 159 bits for |C_A(80)|.
  • The original encoder permits arbitrarily long prefixes, so controlled cyclic shifting is recommended to mitigate unwanted cross-hybridization with address primers.
  • For arbitrary addresses, prefix shifting may not preserve unique decoding, but suitable primers enabled unique recovery in the reported experiments.
  • Prefix-synchronized coding also supports error detection and limited correction by recognizing address prefixes and shifted prefixes.

E. Error-Control Coding for DNA Storage

DNA storage errors arise during synthesis and sequencing, motivating distinct coding strategies for substitutions, deletions, coverage errors, and platform-specific signal distortions.

  • Substitution errors during synthesis can be addressed with classical Reed-Solomon and low-density parity-check codes, but synthesized errors may propagate across sequencing reads as bursts.
  • Single deletion errors introduced during synthesis may be corrected with Levenshtein-Tenengolts codes encoded directly into the DNA string.
  • Deletion and insertion errors may be incorporated into DNA profile coding, although the passage reports no results for that extension.
  • Illumina-compatible substitution and coverage errors can be handled similarly to synthesis substitutions, whereas PacBio and Oxford Nanopore require specialized correction procedures.

APPENDIX

The appendix defines DNA-storage terminology spanning molecular components, laboratory processes, sequencing concepts, and the encoding algorithm.

  • DNA bases are A, G, C, and T, the four nucleotide building units used to express DNA sequence lengths.
  • Coverage is the average number of sequencing reads containing a base at a particular position.
  • De novo means creating DNA from scratch without a template, while primers initiate DNA synthesis and PCR amplifies selected DNA sequences.
  • DNA hybridization combines complementary single-stranded nucleic-acid molecules into a double-stranded molecule through base pairing.
  • Algorithm 1 presents paired encoding and decoding procedures, with encoding written as X = ENCODE_a,ℓ(x) and decoding recovering x from X.
  • Sequence assembly aligns and merges shorter DNA fragments to reconstruct the original longer sequence.
Loading 1507.01611v1…