# An Improved Marker Code Scheme Based on Nucleotide Bases for DNA Data Storage
## 1 Introduction  
In the Big Data era, a huge amount of data is generated every day. It is predicted that the global data volume will reach 175 ZB by 2025 [1; 2], and the data volume will exceed the storage capacity. Therefore, there is an urgent need to find new storage media. The possibility of storing data in DNA was first proposed by [PERSON] in 1999 [3]. Due to its durability and ultrahigh density, DNA is a great potential storage medium. One gram of DNA can store 215 GB of data, and the data stored in DNA can be preserved for tens of thousands of years [4]. Therefore, DNA data storage has attracted considerable attention from the data storage community in recent years, especially in the area of cold data storage, such as government documents and historical archives [5].  
Channel error correction is a key part of DNA storage technology. In DNA synthesis and sequencing, insertion, deletion, and substitution errors of nucleotide bases occur [6]. Since DNA molecules use four nucleotide bases (i.e., adenine (A), thymine (T), cytosine (C), and guanine (G)) to store genetic information [7], DNA is a quadratic channel corrupted by insertions, deletions, and substitutions. To correct synchronization (i.e., insertion and deletion) errors, [PERSON] proposed the concatenated watermark code scheme [8], and [PERSON] proposed the concatenated marker code scheme [9]. To correct DNA channel errors, a modified concatenated watermark code scheme and a modified concatenated marker code scheme were proposed in [10; 11], respectively. The former uses watermark codes as inner codes and low-density parity-check (LDPC) codes [12] as outer codes. The latter employs the marker codes as inner codes and LDPC codes as outer codes.  
In these schemes, watermark and marker codes only assist in regaining synchronization, and they play no role in LDPC decoding. Therefore, these schemes have the disadvantage in error correction performance.To improve error correction performance, we designed an improved error correction scheme for DNA data storage.  
In Ref. [13], a novel marker code scheme, called the embedded marker code scheme, was proposed for channels corrupted by insertions, deletions, and additive white Gaussian noise (AWGN), which are binary channels. On the basis of the embedded marker code scheme, we propose an improved scheme for DNA channels. In the improved scheme, marker codes are used as inner codes and LDPC codes are used as outer codes. Marker bits are encoded as part of the information bits. Compared to the concatenated marker code scheme, marker bits in the proposed scheme additionally assist in LDPC decoding. To correct synchronization errors, a base maximal a posteriori (MAP) detector was adopted. Correspondingly, a novel base-symbol-based synchronization algorithm is provided for the detector. In LDPC decoding, we propose an improved normalized min-sum (INMS) algorithm to reduce decoding complexity. There were some biological constraints on DNA synthesis and sequencing that needed to be considered in our proposed scheme. The long nucleotide chains cannot be synthesized in modern DNA synthesis technology, and the maximal length of nucleotides is 250 [14]. To maintain stability, the GC content of the synthesized sequence must be close to 50% (i.e., 40\(\sim\)60%) [15].  
Our main contributions are summarized as follows.  
* We propose an improved marker code scheme for DNA channels based on the embedded marker code scheme. In this scheme, a novel base-symbol-based synchronization algorithm is proposed to correct synchronization errors.
* In LDPC decoding, we propose an improved decoding algorithm to reduce decoding complexity.  
The paper is organized as follows. In Section 2, the DNA channel model is described. In Section 3, related works are introduced. In Section 4, the improved marker code scheme's development is presented. In Section 5, the base-symbol-based synchronization and the low-complexity INMS algorithms are outlined. Section 6 shows the simulation results. Lastly, Section 7 concludes the paper.