Motivated by their applications in DNA-based storage systems, codes capable of correcting consecutive deletions have attracted significant attention. An important class of such codes consists of those that can correct multiple consecutive deletion errors, commonly referred to as multiple $b$-burst deletion-correcting codes. In this paper, we investigate the fundamental limits of multiple $b$-burst deletion-correcting codes. Specifically, we first characterize several structural properties of the associated deletion balls. Then, leveraging these properties, we derive several upper bounds and a combinatorial lower bound on the maximum size of such codes. As a consequence, our bounds improve upon the previously known results for general parameter regimes and are shown to be asymptotically optimal for certain cases.

As DNA data storage advances toward practical deployment, minimizing sequencing coverage depth is critical for reducing operational costs and retrieval latency. We study the random access problem of recovering a specific information strand from a DNA-based storage system. In this setting, $k$ information strands are encoded into $n$ strands using a generator matrix $G$, and each sequencing read returns one encoded strand sampled uniformly at random with replacement. We derive an exact formula for the expected number of samples required to recover a specific information strand, yielding an $O(n)$-time algorithm for fixed field size $q$ and dimension $k$. We further obtain explicit formulas for the average and maximum expected number of samples, enabling an efficient search for optimal generator matrices for small parameters. We present new constructions that improve the best-known upper bounds from $0.8815k$ to $0.8811k$ for $k=3$, and from $0.8637k$ to $0.8629k$ for $k=4$, for sufficiently large $q$. We also establish a tighter lower bound on the expected number of samples, which in particular proves the optimality of the simple parity code when $n=k+1$ over any field size $q$. Finally, for the non-random access setting, we derive new lower bounds and constructions that characterize the asymptotic behavior of the expected number of samples required to recover all information strands.

In thesequence reconstruction problem, a codewordxis transmitted through several identical channels where each channel produces a noisy read ofx, and the problem is to analyze how to uniquely reconstructxbased on these noisy reads. Levenshtein has studied the minimum number of reads which guarantees unique reconstruction ofx, which is one sufficient condition for unique reconstruction. In this paper, we move on to a different perspective and propose a new framework for unique reconstruction. Our new sufficient condition for unique reconstruction takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms for our reconstruction framework.

Composite DNA is a recent novel method to increase the information capacity of DNA-based data storage above the theoretical limit of 2 bits/symbol. In this method, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have much more than four symbols in the naire approach. While this method enables higher data content per synthesis cycle, potentially reducing the DNA synthesis cost, it also imposes significant challenges for accurate DNA sequencing since the baselevel errors can easily change the mixture of bases and their ratio, resulting in changes to the composite symbols. With this motivation, we propose efficient constrained coding techniques to enforce the biological constraints, including the runlength-limited constraint and the GC-content constraint, into every DNA synthesized oligo, regardless of the mixture of bases in each composite letter and their corresponding ratio. Our contributions include computing the capacity of the constrained channel, constructing efficient encoders/decoders, and providing the best options for the composite letters to obtain capacityapproaching codes. For certain codes' parameters, our methods incur only one redundant symbol.

High costs remain a primary limitation in the practical application of DNA storage, particularly in the synthesis process. This work focuses on a common synthesis method that generates multiple DNA strands in parallel from a fixed supersequence, one nucleotide at a time. The synthesis time is determined by the length of this supersequence. We investigate the maximum sizes and capacities of codes that restrict the maximum synthesis time while adhering to two critical biochemical constraints in a DNA storage channel: the runlength-limited constraint and the GC-content constraint. For specific parameters, we also present an encoding algorithm for codes that restrict the maximum synthesis time and satisfy both constraints.

Composite DNA is a novel approach that enables DNA-based data storage to exceed the theoretical limit of 2 bits per symbol. In this approach, every composite symbol does not store a single DNA nucleotide but a mixture of the four nucleotides in a predetermined ratio. By using different mixtures and ratios, the alphabet can be extended to have far more than four symbols compared to the naive approach. Although this method increases data density per synthesis cycle and potentially reduces DNA synthesis costs, it also introduces significant challenges for accurate DNA sequencing since the base-level errors can easily change the mixture of bases and their ratio, leading to changes in the composite symbols.With this motivation, we investigated error-correcting codes for composite DNA in a general setting. Consider a data storage scenario where m reads are provided for each composite DNA sequence, and for each composite symbol, the difference between the observation ratio and the original ratio in its base mixture is at most ϵ. We further assume that at most δm sequences have errors, for some 0 ≤ δ ≤ 1, and each of them suffers from at most t edit errors (i.e., substitutions, insertions, and deletions). Given arbitrary values of m, ϵ, δ and t, our task is to design a codebook such that every codeword can be uniquely reconstructed. In this work, we focus on single edit error, i.e., t = 1, and for several cases, we show that our proposed codes are asymptotically optimal.

Batch codes are a type of codes specifically designed for coded distributed storage systems and private information retrieval protocols. These codes have received much attention in recent years due to their ability to enable efficient and secure storage in distributed systems. In this paper, we study an array code version of the batch codes, which is called the batch array code (BAC). Under the setting of BAC, each node stores a bucket containing multiple code symbols and responds with a locally computed linear combination of the symbols in its bucket during the recovery of a requested symbol. We demonstrate that BACs can support the same type of requests as the original batch codes but with reduced redundancy. Specifically, we establish information theoretic lower bounds on the code lengths and provide several code constructions that confirm the tightness of the lower bounds for certain parameter regimes.

Codes correcting insertion and deletion errors have received considerable attention in recent years due to their applications in DNA storage and other communication and storage systems with synchronization errors. Given two sequences$u$and v, their insdel (short for insertion and deletion) distance is defined as the minimum number of insertions and deletions needed to transform one sequence into the other. Let$I_{q}(n,d)$be the maximum size of a code$\mathcal{C}\subseteq\Sigma^{n}$where$\vert \Sigma\vert =q$, such that any two distinct codewords have insdel distance at least$d$. In this paper, we analyze the upper bound of$I_{q}(n, d)$and improve the results from Liu and Xing [IEEE-IT. 69(2), 928–940, 2023].

We study a model in which a codeword$x$is transmitted through several identical channels, where each channel produces a noisy read of$x$. The sequence reconstruction problem, proposed by Levenshtein, asks for how to uniquely re-construct$x$based on these noisy reads. Most of previous works focused on the minimum number of reads which guarantees unique reconstruction of$x$in the worst case. In this paper, we move on to a new perspective on the sequence reconstruction problem, and propose a different sufficient condition for unique reconstruction which takes both the number of reads and the distances among the reads into consideration. We offer both theoretical analysis and corresponding efficient reconstruction algorithms.

The PIR (Private information retrieval) array code is as an array version of the PIR codes proposed by Fazeli et al., and both codes aim at designing distributed storage systems with m servers which can implement classical k-PIR protocols while reducing the storage overhead. The central problem in PIR array codes is to maximize k/m, known as the virtual server rate. Blackburn and Etzion provided an asymptotically optimal construction and it has been conjectured to be exactly optimal. We provide a new upper bound of the virtual server rate by linear programming, indicating the optimality of Blackburn-Etzion construction for a wide range of parameters. Besides, we give a general construction of PIR array codes with much fewer servers, with a slight sacrifice on the virtual server rate.

Motivated by applications in DNA-based storage, we study explicit encoding and decoding schemes of binary strings satisfying locally balanced constraints, where the (ℓ, δ)-locally balanced constraint requires that the weight of any consecutive substring of length ℓ is between $\frac{\ell }{2} - \delta $ and $\frac{\ell }{2} + \delta $. In this paper we present coding schemes for the strongly locally balanced constraints and the locally balanced constraints, respectively. Moreover, we introduce an additional result on the linear recurrence formula of the number of binary strings which are (6, 1)-locally balanced, as a further attempt to both capacity characterization and new coding strategies.