Capacity-Approaching Constrained Codes With Error Correction for DNA-Based Data Storage

摘要

We propose coding techniques that simultaneously limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for given l, epsilon > 0, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy all of the following properties: 1) runlength constraint: the maximum homopolymer run in each codeword is at most l ; 2) GC-content constraint: the GC-content of each codeword is within [0.5- epsilon, 0.5+epsilon]; 3) error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. While various combinations of these properties have been considered in the literature, this work provides generalizations of codes constructions that satisfy all the properties with arbitrary parameters of l and epsilon. Furthermore, for practical values of l and epsilon, we show that our encoders achieve higher rates than existing results in the literature and approach capacity. Our methods have low encoding/decoding complexity and limited error propagation.