ABSTRACT The main obstacles for the practical deployment of DNA-based data storage platforms are the prohibitively high cost of synthetic DNA and the large number of errors introduced during synthesis. In particular, synthetic DNA products contain both individual oligo (fragment) symbol errors as well as missing DNA oligo errors, with rates that exceed those of modern storage systems by orders of magnitude. These errors can be corrected either through the use of a large number of redundant oligos or through cycles of writing, reading, and rewriting of information that eliminate the errors. Both approaches add to the overall storage cost and are hence undesirable. Here we propose the first method for storing quantized images in DNA that uses signal processing and machine learning techniques to deal with error and cost issues without resorting to the use of redundant oligos or rewriting. Our methods rely on decoupling the RGB channels of images, performing specialized quantization and compression on the individual color channels, and using new discoloration detection and image inpainting techniques. We demonstrate the performance of our approach experimentally on a collection of movie posters stored in DNA.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized, and cyclic codes.

We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNA-based storage systems and synchronization protocols. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. In addition, WMU sequences used in DNA-based storage systems are required to have balanced compositions of symbols and to be at large mutual Hamming distance from each other. We present a number of constructions for balanced, error-correcting WMU codes using Dyck paths, Knuth's balancing principle, prefix synchronized and cyclic codes.

Symmetric fix-free codes are prefix condition codes in which each codeword is required to be a palindrome. Their study is motivated by the topic of joint source-channel coding and by some information retrieval problems. Although they have been considered by a few communities they are not well understood. In earlier work, we used a collection of instances of Boolean satisfiability problems as a tool in the generation of all optimal binary symmetric fix-free codes with n codewords and observed that the number of different optimal codelength sequences grows slowly compared with the corresponding number for prefix condition codes. We demonstrate that all optimal symmetric fixfree codes can alternatively be obtained by sequences of codes generated by simple manipulations starting from one particular code. We also discuss simplifications in the process of searching for this set of codes as well as a conjecture, which if correct, together with the other results leads to a relatively fast algorithm which has been implemented in MATLAB to construct all optimal binary symmetric fix-free codes.

Symmetric fix-free codes are prefix condition codes in which each codeword is required to be a palindrome. Their study is motivated by the topic of joint source-channel coding. Although they have been considered by a few communities they are not well understood. In earlier work we used a collection of instances of Boolean satisfiability problems as a tool in the generation of all optimal binary symmetric fix-free codes with n code words and observed that the number of different optimal code length sequences grows slowly compared with the corresponding number for prefix condition codes. We demonstrate that all optimal symmetric fix-free codes can alternatively be obtained by sequences of codes generated by simple manipulations starting from one particular code. We also discuss simplifications in the process of searching for this set of codes.

Fix-free codes are prefix condition codes which can also be decoded in the reverse direction. They have attracted attention from several communities and are used in video standards. Two variations (with additional constraints) have also been considered for joint source-channel coding: 1) “symmetric” codes, which require the codewords to be palindromes; 2) codes with distance constraints on pairs of codewords. Approaches to determine the existence of a fix-free code with a given set of codeword lengths, for each of the three variations, are proposed. These appear to involve the first use of Boolean satisfiability (SAT) for the existence and design of source codes. Branch-and-bound algorithms to find the collection of optimal codes for asymmetric and symmetric fix-free codes are described. The first bound for the performance of optimal symmetric binary fix-free codes is provided. An earlier conjecture on optimal symmetric binary fix-free codes is proven and related results for asymmetric fix-free codes are presented. A variation of the 3/4 conjecture for fix-free codes is introduced. A key idea in the first conjecture and the new one is a definition of how one sequence of nondecreasing natural numbers dominates another.

In this paper, we investigate optimal coding strategies for a class of linear deterministic relay networks. The network under study is a relay network, with one source, one destination, and two relay nodes. Additionally, there is a disturbing source of signals that causes interference with the information signals received by the relay nodes. Our model captures the effect of the interference of message signals and disturbing signals on a single relay network, or the interference of signals from multiple relay networks with each other in the linear deterministic framework. For several ranges of the network parameters we find upper bounds on the maximum achievable source-destination rate in the presense of the disturbing node and in each case we find an optimal coding scheme that achieves the upper bound.