Naslavljanje DNA-pomnilnikov z maksimalnimi kodi brez prekritij

Nature provides an efficient and noise-resilient method for encoding, transmitting, and preserving information through sequences of nucleotides. The data stored in DNA and RNA sequences controls cellular processes and serves as a recipe for synthesising new molecules. In recent decades, technological progress has facilitated the manipulation of the repertoire of recipes, enabling the redesign of existing biological systems and the engineering of new ones. Advances in synthetic biology have also given rise to the first DNA-based data storage devices. As with any other synthetic biological part, the DNA sequences that make up a storage device should fulfil specific requirements to be efficiently integrated into an existing system and into the techniques used to manipulate the system in question. Mathematical modelling can, therefore, be used to develop an encoding method for information storing and estimate the maximum capacity and redundancy of DNA-based data storage. The sequence design problem is multilayered and depends on the storage device architecture. In this thesis, we focus on architectures that provide reliable partial access to the information stored on the device and one specific family of codes that can be used to address such DNA-based storage devices. This is because reading the whole set of stored data is rarely of a user's interest and becomes unmanageable with the growing storage capacity due to the price and latency of sequencing and data decoding. Herein, we investigate how the DNA-based-storage-specific constraints affect the family of non-overlapping codes. In particular, at the beginning, we provide an algorithm that constructs all non-overlapping codes. Then, we characterise the maximal non-overlapping codes and improve an algorithm that determines the maximum size of a non-overlapping code. We modify the construction algorithm to incorporate two primary constraints the DNA-based data storage requires: the balance and the run-length limit. An upper and a lower bound on the maximum code size is determined for each constraint. We also characterise the maximal polarity-balanced non-overlapping codes. Later, we develop algorithms to construct a related family of codes, the (1, k)-overlap-free codes, the weakly mutually uncorrelated codes and (t1, t2)-overlap-free codes. We characterise the maximal (1, k)-overlap-free codes and determine bounds on the maximum sizes of all families of codes. At the very end, we compute the melting temperatures of the DNA sequences that would be used as addresses for DNA-based data storage if our codes were used for this task and evaluate their appropriateness concerning the biological constraints.