Abstract : In this paper, we propose a novel iterative encoding algorithm for DNA storage to satisfy both the GC balance and run-length constraints using a greedy algorithm. DNA strands with run-length more than three and the GC balance ratio far from 50% are known to be prone to errors. The proposed encoding algorithm stores data with high flexibility of run-length at most m and GC balance between 0.5 ± α for arbitrary m and α. More importantly, we propose a novel mapping method to reduce the average bit error compared to the randomly generated mapping method. By using the proposed method, the average bit error caused by the one base error is 2.3455 bits, which is reduced by 20.5%, compared to the randomized mapping. Also, it is robust to error propagation since the input sequence is partitioned into small blocks during the mapping step. The proposed algorithm is implemented through iterative encoding, consisting of three main steps: randomization, M-ary mapping, and verification. It has an information density of 1.833 bits/nt in the case of m = 3 and α = 0.05.
Index terms : Bioinformatics, constrained coding, DNA storage, error propagation, greedy algorithm, iterative algorithm.