A $t$-all-symbol PIR code and a $t$-all-symbol batch code of dimension $k$ consist of $n$ servers storing linear combinations of $k$ information symbols with the following recovery property: any symbol stored by a server can be recovered from $t$ pairwise disjoint subsets of servers. In the batch setting, we further require that any multiset of size $t$ of stored symbols can be recovered from~$t$ disjoint subsets of servers. This framework unifies and extends several well-known code families, including one-step majority-logic decodable codes, (functional) PIR codes, and (functional) batch codes. In this paper, we determine the minimum code length for some small values of $k$ and $t$, characterize structural properties of codes attaining this optimum, and derive bounds that show the trade-offs between length, dimension, minimum distance, and $t$. In addition, we study MDS codes and the simplex code, demonstrating how these classical families fit within our framework, and establish new cases of an open conjecture from \cite{YAAKOBI2020} concerning the minimal $t$ for which the simplex code is a $t$-functional batch code.

In this paper, we study theRandom Access Problemin DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. In this framework, the data is represented bykinformation strands which represent the data and are encoded intonstrands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case whenk= 2, showing that the best possible code attains a random access expectation of 1 + 2/ √2+1 ≈ 0.914 · 2 forqlarge enough. Moreover, we extend a previous construction, originally developed fork= 3, to arbitrary values ofk. Our construction usesBk−1sequences overZq−1, that always exist over large finite fields. We show that for everyk≥ 4, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.

Nearly perfect covering codes are covering codes that meet the van Wee lower bound on their size. This work studies such codes with covering radius 1. It is shown that the set of these codes can be partitioned into three families, depending on the distribution of the Hamming distances between neighboring codewords. General properties of these code families are presented, including a characterization of their weight and distance distributions. Constructions of codes for each of the families are presented. Finally, extended perfect covering codes are considered. Their punctured codes yield a variety of nearly perfect covering codes.

This paper introduces a new solution to DNA storage that integrates all three steps of retrieval, namely clustering, reconstruction, and error correction.DNA-correcting codesare presented as a unique solution to the problem of ensuring that the output of the storage system is unique for any valid set of input strands. To this end, we introduce a novel distance metric to capture the unique behavior of the DNA storage system and provide necessary and sufficient conditions for DNA-correcting codes. We also establish bounds and constructions for these codes, including an exploration of the ℓ∞distance applied to permutations. Here, instead of interpreting permutation elements as numerical values and assessing absolute differences, we treat them as vectors and consider the Hamming distance to better model the DNA Storage System.

Nearly perfect packing codes are those codes that meet the Johnson upper bound on the size of errorcorrecting codes. This bound is an improvement to the sphere-packing bound. A related bound for covering codes is known as the van Wee bound. Codes that meet this bound will be called nearly perfect covering codes. In this paper, such codes with covering radius one will be considered. It will be proved that these codes can be partitioned into three families depending on the smallest distance between neighboring codewords. Some of the codes contained in these families will be completely characterized. Other properties of these codes will be considered too. Construction for codes for each such family will be presented, the weight distribution and the distance distribution of codes from these families are characterized. Finally, extended nearly perfect covering code will be considered and unexpected equivalence classes of codes of the three types will be defined based on the extended codes.

Motivated by distributed algorithms for fuzzy joins, the concept of pair-covering${}^{\prime\prime}$codes is defined. This definition is a generalization of the well-known concept of covering codes. Basic properties and bounds for the pair-covering codes with comparison to the associated properties and bounds for covering codes, are provided. In particular, the sphere covering bound and normal codes are generalized.

MOTIVATION: As data storage challenges grow and existing technologies approach their limits, synthetic DNA emerges as a promising storage solution due to its remarkable density and durability advantages. While cost remains a concern, emerging sequencing and synthetic technologies aim to mitigate it, yet introduce challenges such as errors in the storage and retrieval process. One crucial task in a DNA storage system is clustering numerous DNA reads into groups that represent the original input strands. RESULTS: In this paper, we review different methods for evaluating clustering algorithms and introduce a novel clustering algorithm for DNA storage systems, named Gradual Hash-based clustering (GradHC). The primary strength of GradHC lies in its capability to cluster with excellent accuracy various types of designs, including varying strand lengths, cluster sizes (including extremely small clusters), and different error ranges. Benchmark analysis demonstrates that GradHC is significantly more stable and robust than other clustering algorithms previously proposed for DNA storage, while also producing highly reliable clustering results. AVAILABILITY AND IMPLEMENTATION: https://github.com/bensdvir/GradHC.

This paper introduces a new solution to DNA storage that integrates all three steps of retrieval, namely clustering, reconstruction, and error correction. DNA-correcting codes are presented as a unique solution to the problem of ensuring that the output of the storage system is unique for any valid set of input strands. To this end, we introduce a novel distance metric to capture the unique behavior of the DNA storage system and provide necessary and sufficient conditions for DNA-correcting codes. The paper also includes several upper bounds and constructions of DNA-correcting codes.

We study a data-driven approach to the bee identification problem for DNA strands. The bee-identification problem, introduced by Tandon et al. (2019), requires one to identify M bees, each tagged by a unique barcode, via a set of M noisy measurements. Later, Chrisnata et al. (2022) extended the model to case where one observes N noisy measurements of each bee, and applied the model to address the unordered nature of DNA storage systems.In such systems, a unique address is typically prepended to each DNA data block to form a DNA strand, but the address may possibly be corrupted. While clustering is usually used to identify the address of a DNA strand, this requires ℳ2data comparisons (when ℳ is the number of reads). In contrast, the approach of Chrisnata et al. (2022) avoids data comparisons completely. In this work, we study an intermediate, data-driven approach to this identification task.For the binary erasure channel, we first show that we can almost surely correctly identify all DNA strands under certain mild assumptions. Then we propose a data-driven pruning procedure and demonstrate that on average the procedure uses only a fraction of ℳ2data comparisons. Specifically, for ℳ = 2nand erasure probability p, the expected number of data comparisons performed by the procedure is κℳ2, where ${\left( {\frac{{1 + 2p - {p^2}}}{2}} \right)^n} \leq \kappa \leq {\left( {\frac{{1 + p}}{2}} \right)^n}$.