27 April 2021 in Bioinformatics
Motivation: In DNA storage systems, there are tradeoffs between writing and reading costs. Increasing the code rate of error-correcting codes may save writing cost, but it will need more sequence reads for data retrieval. There is potentially a way to improve sequencing and decoding processes in such a way that the reading cost induced by this tradeoff is reduced without increasing the writing cost. In past researches, clustering, alignment and decoding processes were considered as separate stages but we believe that using the information from all these processes together may improve decoding performance. Actual experiments of DNA synthesis and sequencing should be performed because simulations cannot be relied on to cover all error possibilities in practical circumstances. Results: For DNA storage systems using fountain code and Reed-Solomon (RS) code, we introduce several techniques to improve the decoding performance. We designed the decoding process focusing on the cooperation of key components: Hamming-distance based clustering, discarding of abnormal sequence reads, RS error correction as well as detection and quality score-based ordering of sequences. We synthesized 513.6 KB data into DNA oligo pools and sequenced this data successfully with Illumina MiSeq instrument. Compared to Erlich’s research, the proposed decoding method additionally incorporates sequence reads with minor errors which had been discarded before, and thus was able to make use of 10.6–11.9% more sequence reads from the same sequencing environment, this resulted in 6.5–8.9% reduction in the reading cost. Channel characteristics including sequence coverage and read-length distributions are provided as well. Availability and implementation: The raw data files and the source codes of our experiments are available at: https://github.com/jhjeong0702/dna-storage.
4 September 2020 in IEEE Access
Due to the advantages of high storage densities and longevity, DNA storage has become one of the attractive technologies for future data storage systems. However, the writing/reading cost is still high and more efficient techniques for DNA storage are required. In this paper, we propose improved log-likelihood ratio (LLR) processing schemes based on observed statistics for low-density parity-check (LDPC) code decoding to reduce reading cost while encoding schemes are kept unchanged. Due to the mismatch between the real channel and the observed statistics and also the limit of maximum decoder input value, scaling the magnitude of LLR can lead to a better error correcting performance. Therefore, we propose two strategies: 1) directly scaling LLRs and 2) scaling pairwise substitution error rates, which changes the magnitude of LLRs. We also suggest the relation between substitution error rate and scaling values in the strategies by using curve fitting methods. Simulation results show that the error correcting performance from the proposed LLR calculation is better than that from the conventional scheme. Finally, we verify that the proposed LLR methods can be generally applied in DNA storage systems, and present practical methods to calculate error rates.
26 September 2017 in IEEE Transactions on Information Theory
In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a $\delta _{s}$ -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the $\delta _{s}$ -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code.
22 September 2022 in IEEE Communications Letters
In this letter, we investigate the min-sum (MS) and neural MS (NMS) decoding algorithms for generalized low-density parity-check (GLDPC) codes. Although the MS decoder is much simpler than the a posteriori probability (APP) decoder commonly used for GLDPC codes, the MS decoder has not been considered mainly due to its inferior decoding performance. However, we show that the performance can be improved by i) employing the NMS decoding algorithm and ii) optimizing the component parity check matrix (PCM). For the four representative short GLDPC codes in the literature, experimental results show that the NMS decoding performance with the optimized component PCM significantly outperforms the MS decoding performance and even outperforms the APP decoding performance for some cases.
9 January 2023 in IEEE Access
DNA data storage systems have rapidly developed with novel error-correcting techniques, random access algorithms, and query systems. However, designing an algorithm for DNA storage systems is challenging, mainly due to the unpredictable nature of errors and the extremely high price of experiments. Thus, a simulator is of interest that can imitate the error statistics of a DNA storage system and replace the experiments in developing processes. We introduce novel generative adversarial networks that learn DNA storage channel statistics. Our simulator takes oligos (DNA sequences to write) as an input and generates a FASTQ file that includes output DNA reads and quality scores as if the oligos are synthesized and sequenced. We trained the proposed simulator with data from a single experiment consisting of 14,400 input oligo strands and 12,108,573 output reads. The error statistics between the input and the output of the trained generator match the actual error statistics, including the error rate at each position, the number of errors for each nucleotide, and high-order statistics. The code is available at https://github.com/gyfbianhuanyun/DNA_storage_simulator_GAN.
6 September 2019 in IEEE Transactions on Communications
In this paper, linear index codes with multiple senders are studied, where every receiver receives encoded messages from all senders. A new fitting matrix for the multiple senders is proposed and it is proved that the minimum rank of the proposed fitting matrices is the optimal codelength of linear index codes for the multiple senders. In addition, a new type of a side information graph related with the optimal codelength is proposed and whether given side information is critical or not is studied. Furthermore, linear index codes for the cellular network scenario are studied, where each receiver can receive a subset of sub-codewords. Since some receivers cannot receive the entire codeword in the cellular network scenario, the encoding method based on the fitting matrix has to be modified. In the cellular network scenario, we propose another fitting matrix and prove that an optimal generator matrix can be found based on these fitting matrices. In addition, some properties on the optimal codelength of linear index codes for the cellular network case are studied.