To make DNA a suitable medium for archival data storage, it is essential to consider the decay process of the strands observed in DNA storage systems. This paper studies the decay process as a probabilistic noisy torn paper channel (TPC), which first corrupts the bits of the transmitted sequence in a probabilistic manner by substitutions, then breaks the sequence into a set of noisy unordered substrings. The present work devises coding schemes for the noisy TPC by embedding markers in the transmitted sequence. We investigate the use of static markers and markers connected to the data in the form of hash functions. These two tools have also been recently exploited to tackle the noiseless TPC. Simulations show that static markers excel at higher substitution probabilities, while data-dependent markers are superior at lower noise levels. Both approaches achieve reconstruction rates exceeding 99% with no false decodings observed, primarily limited by computational resources.

Motivated by DNA storage systems and 3D finger-printing, this work studies the adversarial noisy torn paper channel, which first applies at most$t_{e}$edit errors (i.e., insertions, deletions, and substitutions) to the transmitted word then breaks it into$t$+ 1 fragments at arbitrary positions. Specifically, we construct a near optimal error correcting code for this channel, and refer to it by ($t, t_{e}$)-resilient code. Furthermore, we study list decoding of the noiseless torn paper channel by deriving bounds on the size of the list (of codewords) obtained from cutting a codeword of a ($t, 0$) - resilient code$t^{\prime}$times, where$t^{\prime}> t$.

In conventional DNA synthesis machines, usually many strands are synthesized in parallel by iterating through a supersequence$\boldsymbol {s}$and adding in each cycle the next nucleotide to a programmable subset of the strands. The length of$\boldsymbol {s}$determines the number of the cycles, hence the time and the cost of the synthesis process. Recently, in order to reduce the number of synthesis cycles, researchers have suggested to append in each cycle a shortmer, i.e., a sequence of nucleotides, instead of a single one. The present work studies this synthesis technique from a theoretical point of view. In particular, it discusses which shortmers are the best to use (in order to reduce the number of cycles), and how to calculate the number of cycles required to synthesize in parallel a set of strands using a given set of shormers. Lastly, and following a previously described connection between the DNA synthesis problem and costly constrained graphs, this paper investigates calculating the capacity of non-deterministic costly constrained graphs.

In the reconstruction model, first proposed by Levenshtein in 2001, a word is transmitted over multiple identical noisy channels that output distinct erroneous words. Given the channels’ outputs, unique decoding of the transmitted word is guaranteed to succeed only if the number of the channels is greater than a specific value. Otherwise, there may be several transmitted words that lead to the same channels’ outputs. In this case, these words are recovered using a list decoder. Calculating the largest list size is a fundamental task when studying the list decoding problem. The present work takes the first steps towards studying list decoding of insertions and deletions under the reconstruction model. More specifically, it assumes that an arbitrary binary word is transmitted over$m~t$-insertion (or$t$-deletion) identical channels, and provides the largest list size for specific values of$m$. These results are mainly achieved by investigating the largest intersection of$m~t$-insertion (or$t$-deletion) balls surrounding arbitrary binary words in the space.

In conventional DNA synthesis machines 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 present work studies 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 shormers. Lastly, and following a previously described connection between the DNA synthesis problem and costly constrained graphs, the paper investigates calculating the capacities of such non-deterministic graphs.

The reconstruction model, first proposed by Levenshtein in 2001, assumes that a word is transmitted over multiple identical noisy channels that output distinct words. Given the channels' outputs, the transmitted word is guaranteed to be decoded uniquely only if the number of the channels is greater than some value. Otherwise, there could be several transmitted words leading to the same channels' outputs. Hence, these words should be found following the list decoding approach. Motivated by DNA storage systems, the present work takes the first steps towards studying list decoding for insertions and deletions under the reconstruction model. More specifically, it will be assumed that an arbitrary binary word is transmitted over$m$t-insertions (or$t$deletions) identical channels. For specific values of$m$, bounds on the largest list decoder size are provided. These bounds are mainly derived by investigating the largest intersection of$m$t- insertion (or t-deletion) balls surrounding arbitrary binary words in the space. Furthermore, all pairs of binary words achieving the largest intersection of their t-insertion balls are characterized.

Thesequence reconstruction problemcorresponds to the model in which a sequence from some code is transmitted over several noisy channels that produce distinct outputs. Then, the channels’ outputs, received by the decoder, are used to recover the transmitted sequence, and the main problem under this paradigm is to calculate the minimum number of channels that enables unique reconstruction of the transmitted word. This problem is equivalent to finding the size of the largest intersection of channels’ outputs sets received after transmitting distinct codewords. Motivated by the error behavior observed in DNA storage systems, the present work extends the study of the reconstruction model to the case in which a binary word is transmitted over channels prone to substitutions, insertions, and deletions. Furthermore, we also study the size of the error balls generated by either one deletion and at most a fixed number of substitutions or one insertion and at most one substitution in a binary word. For the case of only substitutions, we present a decoder of optimal complexity, which improves upon a recent construction of such a decoder. Lastly, a simplification of that decoder is studied in case there are more channels than the minimum required number.

The sequence reconstruction problem corresponds to a model in which a sequence from some code is transmitted over several noisy channels. The channels are almost independent as it is only required that their outputs are different. The main problem under this paradigm is to determine the minimum number of channels required to reconstruct the transmitted sequence. This problem is equivalent to finding the maximum intersection size between two balls of any possible two inputs, where the balls are all possible channel outputs. Motivated by the error behavior in the DNA storage channel, this work extends this study to the case where the channels are prone to substitutions, insertions, and deletions. For the case of only substitutions, we also present a decoder of optimal complexity, which improves upon a recent construction of such a decoder. Lastly, it is also studied how the decoder is simplified in case there are more channels than the minimum required number.