Motivated by applications in spatial genomics, we revisit group testing (Dorfman 1943) and propose the class of$\lambda$-ADD-codes, studying such codes with certain distance$d$and codelength$n$. When$d$is constant, we provide explicit code constructions with rates close to 1/2. When$d$is proportional to$n$, we provide a GV-type lower bound whose rates are efficiently computable. Upper bounds for such codes are also studied.

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.

Transmit a codeword x, that belongs to an (ℓ − 1)deletion-correcting code of length n, over a t-deletion channel for some 1 ≤ ℓ ≤ t < n. Levenshtein, in 2001, proposed the problem of determining N(n,ℓ,t) + 1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to this work, N(n,ℓ,t) is known only when ℓ ∈ {1,2}. Here, we provide an asymptotically exact solution for all values of ℓ and t. Specifically, we show that $N(n,\ell ,t) = \binom{{2\ell }}{\ell}/(t - \ell )!{n^{t - \ell }} - O\left( {{n^t}^{ - \ell - 1}} \right)$ and in the special instance where ℓ = t, we show that $N(n,\ell ,\ell ) = \binom{{2\ell }}{\ell}$. We also provide a conjecture on the exact value of N(n,ℓ,t) for all values of n, ℓ, and t.