Eitan Yaakobi - The Applications of Constrained Systems in DNA Storage: Efficient Synthesis and DNA Labeling

DNA-based storage has attracted significant attention due to recent demonstrations of the viability of storing information in macromolecules. Given the trends in cost decreases of DNA synthesis and sequencing, it is estimated that within the next decade DNA storage may become a highly competitive archiving technology. This technology introduces new challenges in finding coding solutions to address various problems associated with the implementation of DNA-based storage systems. In this talk, I will present two applications of constrained systems in solving practical problems in DNA-based storage systems. The first application is motivated by conventional DNA synthesis machines where many strands are usually synthesized in parallel by iterating through a supersequence s and adding in each cycle a single nucleotide to a subset of the strands. Then, the length of s determines the number of the cycles, hence the time and the cost of the synthesis process too. Recently, in order to optimize the synthesis process, researchers have suggested to append in each cycle a shortmer instead of a single nucleotide. The goal of this work is to study this optimization from a theoretical point of view. In particular, it discusses which shortmers are the best to use, and how to calculate the number of cycles required to synthesize in parallel a set of strands using a set of shortmers. The second application is motivated by DNA labeling, where a DNA molecule is being labeled by specific k patterns and is then imaged. Then, the resulted image is modeled as a (k + 1)-ary sequence in which any non-zero symbol indicates on the appearance of the corresponding label in the DNA molecule. The primary goal is to study the labeling capacity, which is defined as the maximal information rate that can be obtained using this labeling process