Efficient Constrained Encoders Correcting A Single Nucleotide Edit In Dna Storage

A nucleotide substitution is said to occur when a base in {A, T} is substituted for a base in {C, G}, or vice versa. Recent experiment (Heckel et al. 2019) showed that a nucleotide substitution occurs with a significantly higher probability that other substitution errors. A nucleotide edit refers to a single insertion, deletion or nucleotide substitution. In this paper, we investigate codes that corrects a single nucleotide edit and provide linear-time algorithms that encode binary messages into these codes of length n. Specifically, we provide an order-optimal encoder which corrects a single nucleotide edit with log n + log log n + O(1) redundant bits. We also demonstrate that the codewords obey certain runlength constraints and that the code can be modified to accommodate certain GC-content constraints.