Efficient Constrained Encoders Correcting a Single Nucleotide Edit in DNA Storage
Kui Cai, Xuan He, Han Mao Kiah, Tuan Thanh Nguyen
Abstract
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 than 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..
BibTeX
@inproceedings{icassp2020_efficientconstra,
title = {Efficient Constrained Encoders Correcting a Single Nucleotide Edit in DNA Storage},
author = {Kui Cai and Xuan He and Han Mao Kiah and Tuan Thanh Nguyen},
booktitle = {ICASSP 2020},
year = {2020}
}