The synthesis of DNA strands remains the most costly part of the DNA storage system. Thus, to make DNA storage system more practical, the time and materials used in the synthesis process have to be optimized. We consider the most common type of synthesis process where multiple DNA strands are synthesized in parallel from a common alternating supersequence, one nucleotide at a time. The synthesis time or the number of synthesis cycles is then determined by the length of this common supersequence. In this model, we design quaternary codes that minimizes synthesis time that can correct deletions or insertions, which are the most prevalent types of error in arraybased synthesis. We also propose polynomial-time algorithms that encode binary strings into these codes whose rates are close to the capacity.

Motivated by DNA-based applications, we generalize the bee identification problem proposed by Tandon et al. (2019). In this setup, we transmit all M codewords from a codebook over some channel and each codeword results in N noisy outputs. Then our task is to identify each codeword from the MN noisy outputs.First, via a reduction to a minimum-cost flow problem on a related flow network ${\mathcal{G}_N}$, we show that the problem can be solved in O(M3) time in the worst case. Next, we consider the deletion channel and study the expected number of edges in the network ${\mathcal{G}_N}$. Specifically, we obtain closed expressions for this quantity for certain codebooks and when the codebook comprises all binary words, we show that this quantity is sub-quadratic when the deletion probability is less than 1/2. This then implies that the expected running time for this codebook is o(M3). For other codebooks, we develop methods to compute the expected number of edges efficiently. Finally, we adapt classical peeling-decoding techniques to reduce the number of nodes and edges in ${\mathcal{G}_N}$.

The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads$N$is fixed. Of significance, for the single-deletion channel, using$\log _{2}\log _{2} n +O(1)$redundant bits, we designed a reconstruction code of length$n$that reconstructs codewords from two distinct noisy reads (Caiet al., 2021). In this work, we show that$\log _{2}\log _{2} n -O(1)$redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of the construction. Furthermore, we show that these reconstruction codes can be used in$t$-deletion channels (with$t \geqslant 2$) to uniquely reconstruct codewords from${n^{t-1}}/{(t-1)!}+O\left ({n^{t-2}}\right)$distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class ofhigher order constrained shifted VTcode with$2\log _{2} n +o(\log _{2}(n))$redundancy bits that can reconstruct any codeword from any$N \geqslant 5$of its length-$(n-2)$subsequences.

A two-deletion correcting code of length$n$is defined to be a set of binary words such that a codeword can be uniquely identified from any one of its length- ($n-2$) subsequence. A two-deletion correcting code requires at least$2\log n+O(1)$, while the best known explicit construction uses$4\log n+o(\log n)$redundant bits. In this work, we study this coding problem in the framework of the sequence reconstruction problem and require the receiver to uniquely reconstruct a codeword from any$N\geqslant 2$of its length- ($n-2$) subsequences. Specifically, we provide an explicit code construction that uniquely reconstructs a codeword from any five of its length-($n-2$) subsequences, using only$2\log n+o(\log n)$redundant bits.

The linear complexity of a sequence s is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence s of length N (where N is of some given form) over a finite field Fqin O(N) symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period 2n, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires βN bit operations for a small constant β, where N is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition.

Minimal multicast networks are fascinating and efficient combinatorial objects, where the removal of a single link makes it impossible for all receivers to obtain all messages. We study the structure of such networks, and prove some constraints on their possible solutions. We then focus on the combination network, which is one of the simplest and most insightful network in network-coding theory. Of particular interest are minimal combination networks. We study the gap in alphabet size between vector-linear and scalar-linear network-coding solutions for such minimal combination networks and some of their sub-networks. For minimal multicast networks with two source messages we find the maximum possible gap. We define and study sub-networks of the combination network, which we call Kneser networks, and prove that they attain the upper bound on the gap with equality. We also prove that the study of this gap may be limited to the study of sub-networks of minimal combination networks, by using graph homomorphisms connected with the q -analog of Kneser graphs. Additionally, we prove a gap for minimal multicast networks with three or more source messages by studying Kneser networks. Finally, an upper bound on the gap for full minimal combination networks shows nearly no gap, or none in some cases. This is obtained using an MDS-like bound for subspaces over a finite field.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. Such code constructions are almost optimal to combat tandem duplications of length at most k where k ≤ 3. However, the problem of designing efficient encoder/decoder for such codes has not been investigated. In addition, the method cannot be extended to deal with the case of arbitrary k, where k ≥ 4. In this work, we study efficient encoding/decoding methods for irreducible words over general q-ary alphabet. Our methods provide the first known efficient encoder/decoder for q-ary codes correcting tandem duplications of length at most k, where k ≤ 3. In particular, we describe an (1, m)-finite state encoder and show that when m = Θ(1/ε) and ϊ = Θ(1/ε), the encoder achieves rate that is ε away from the optimal rate. We also provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder. Over the DNA alphabet (or quaternary alphabet), we also impose weight constraint on the codewords. In particular, a quaternary word is GC-balanced if exactly half of the symbols of are either C or G. Via a modification of Knuth's balancing technique, we provide an efficient method that translates quaternary messages into GC-balanced codewords and the resulting codebook is able to correct tandem duplications of length at most k, where k ≤ 3. In addition, we provide the first known construction of codes to combat tandem duplications of length at most k, where k ≥ 4. Such codes can correct duplication errors in linear-time and they are almost optimal in terms of rate.

Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to be ⩽-confusable if there exists a sequence of tandem duplications for each word, where each duplication is of length at most k , such that the resulting two words after duplications are equal. For k =3, we demonstrate that the problem of deciding whether two words is ⩽3-confusable is linear-time solvable through a characterisation that can be checked efficiently. Combining with previous results, the decision problem is linear-time solvable for k ⩽ 3. We conjecture that this problem is undecidable for k > 3. Using insights gained from the algorithm, we study the size of tandem-duplication codes. We improve the previous known upper bound and then construct codes with larger sizes as compared to the previous constructions. We determine the sizes of optimal tandem-duplication codes for lengths up to 20, develop recursive methods to construct tandem-duplication codes for all word lengths, and compute explicit lower bounds for the size of optimal tandem-duplication codes for lengths from 21 to 30.

We investigate constant-composition constrained codes for the mitigation of intercell interference for multilevel cell flash memories with a dynamic threshold scheme. The first explicit formula for the maximum size of a q-ary F-avoiding code with a given composition and certain families of substrings F is presented. In addition, we provide methods to determine the asymptotic rate for F-avoiding codes with any composition ratio and to find the optimal composition ratio that maximizes the asymptotic rate. We also give the first efficient encoder/decoder for these q-ary constant-composition codes achieving the channel capacity, for all q values.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. We study efficient encoding/decoding methods for irreducible words. First, we describe an (ℓ, m) -finite state encoder and show that when m=Θ(1/ε) and ℓ = Θ(1/ε), the encoder has rate that is ε away from the optimal. Next, we provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder.

A recent study by one of the authors has demonstrated the importance of profile vectors in DNA-based data storage. We provide exact values and lower bounds on the number of profile vectors for finite values of alphabet size q, read length 1, and word length n. Consequently, we demonstrate that for q ≥ 2 and n ≤ q1/2-1, the number of profile vectors is at least qκnwith κ very close to 1. In addition to enumeration results, we provide a set of efficient encoding and decoding algorithms for certain families of profile vectors.

A recent study by one of the authors has demonstrated the relevance of profile vectors in DNA-based data storage. We provide exact values and lower bounds on the number of profile vectors for finite values of alphabet size q, read length ℓ, and word length n. Consequently, we demonstrate that for q ≥ 3 and n = qaℓ, a = o(ℓ), the number of profile vectors is at least qκnfor some constant 0 < κ ≤ 1. In addition to enumeration results, we provide a set of efficient encoding and decoding algorithms for a family of profile vectors.

For certain families of substrings F, we provide a closed formula for the maximum size of a q-ary F-avoiding code with a given composition. In addition, we provide numerical procedures to determine the asymptotic information rate for F-avoiding codes with certain composition ratios. Using our procedures, we recover known results and compute the information rates for certain classes of F-avoiding constant-composition codes for 2 ≤ q ≤ 8. For these values of q, we find composition ratios such that the rates of F-avoiding codes with constant composition achieve the capacity of the F-avoiding channel.

We give the first known efficient encoder/decoder for q-ary constant-composition ICI-free codes achieving ICI channel capacity, for all q. Previously, the best result known is an efficient encoder/decoder for binary constant-weight ICI-free codes with more than 2% loss over ICI channel capacity.