# An Improved Marker Code Scheme Based on Nucleotide Bases for DNA Data Storage
## 5 Decoding Algorithm  
### Base-Symbol-Based Synchronization Algorithm  
A conventional forward/backward (FB) algorithm is usually used to correct the synchronization errors [8; 9; 10; 11]. A novel base-symbol-based synchronization (i.e., FB) algorithm is proposed and used to regain synchronization in the improved scheme. In this subsection, we describe the algorithm in the case of the maximal insertion length (of the channel) \(I_{m}=2\). Suppose that channel input sequence \(\mathbf{s}=\{s_{1},s_{2},\ldots,s_{T}\}\) and output sequence \(\mathbf{r}=\{r_{1},r_{2},\ldots,r_{Q}\}\). These are both nucleotide base sequences, but their lengths, \(T\) and \(Q\), may be different. Let the position offset be \(O_{k}=n\), \(k\in[1,T]\) if the \((k+n)\)-th base of the output sequence corresponds to the \(k\)-th base of the input sequence. Let \(O_{\text{max}}\) be the maximal allowed position offset. Thus, \(O_{k}\in[-O_{\text{max}},O_{\text{max}}]\). Sequence \(\{O_{k}\}\) forms the hidden states of the hidden Markov model. To express the transfer probabilities among the bases, we define the following function:  
\[F(s_{k},r_{k+n})=\left\{ \begin{array}{ll}1-p_{1},&if\ r_{k+n}=s_{k}\\ \frac{1}{3}p_{1},&otherwise\end{array} \right., \tag{8}\]  
if \(s_{k}=\text{T}\) or G,  
\[F(s_{k},r_{k+n})=\left\{ \begin{array}{ll}1-p_{2},&if\ r_{k+n}=s_{k}\\ \frac{1}{3}p_{2},&otherwise\end{array} \right.. \tag{9}\]  
As in [8], we define the coefficients as follows:  
\[\alpha_{k}(n)=P(\mathbf{r}_{1}^{k+n},O_{k}=n), \tag{10}\] \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]  
where \(\mathbf{r}_{1}^{k+n}=\{r_{1},\ldots,r_{k+n}\}\) and \(\mathbf{r}_{k+1+n}^{Q}=\{r_{k+1+n},\ldots,r_{Q}\}\). These coefficients can be obtained with forward and backward recursion. Suppose \(\lambda=1/(1-P_{i}^{2})\); thus, the transfer probabilities between two adjacent hidden states are \(P_{t}\), \(P_{d}\), \(\lambda P_{1}P_{d}\), \(\lambda P_{1}P_{t}\), \(\lambda P_{1}^{2}P_{d}\), and \(\lambda P_{1}^{2}P_{1}\). Figure 4: The encoding process of the improved marker code scheme. Figure 3: The procedure of the improved marker code scheme. For example, the transfer probability from state \(O_{k-1}=n-2\) to state \(O_{k}=n\) is \(\lambda P_{i}^{2}P_{i}\); thus, the probability of conversion from \(\alpha_{k-1}(n-2)=P(r_{1},\ldots,r_{(k-1)+(n-2)},O_{k-1}=n-2)\) to \(\alpha_{k}(n)=P(r_{1},\ldots,r_{(k-1)+(n-2)},r_{(k-1)+(n-1)},r_{(k-1)+n},r_{k+n} O_{k}=n)\) is \(\lambda P_{i}^{2}P_{i}\cdot\frac{1}{16}\sum\limits_{s_{k}}P(s_{k})F(s_{k},r_{k+n})\). Suppose  
\[\Phi(x)=\sum\limits_{s_{k}}P(s_{k})F(s_{k},x),x\in\{\text{A,T,C,G}\}. \tag{12}\]  
The calculations are given as follows. \[\alpha_{k}(n) =\frac{\lambda P_{i}^{2}P_{t}}{16}\Phi(r_{k+n})\alpha_{k-1}(n-2)\] \[+\left[\frac{\lambda P_{i}^{2}P_{d}}{16}+\frac{\lambda P_{i}P_{t }}{4}\Phi(r_{k+n})\right]\alpha_{k-1}(n-1)\] \[+\left[\frac{\lambda P_{i}P_{d}}{4}+P_{t}\Phi(r_{k+n})\right] \alpha_{k-1}(n)\] \[+P_{d}\alpha_{k-1}(n+1). \tag{13}\]  
\[\beta_{k}(n) =\frac{\lambda P_{i}^{2}P_{t}}{16}\Phi(r_{k+1+n})\beta_{k+1}(n+2)\] \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]0 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]1 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]2  
The probabilities of certain states can be derived after recurring all coefficients. In other words, the a posteriori probabilities of the channel input bases can be obtained and expressed as follows:  
\[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]3 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]4 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]5 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]6 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]7 \[\beta_{k}(n)=P(\mathbf{r}_{k+1+n}^{Q}|O_{k}=n), \tag{11}\]8  
The a posteriori probabilities of the bases need to be converted into the soft information of bits (which is the input of the binary LDPC decoder).