Despite their significant advantages over competing technologies, nanopore sequencers are plagued by high error rates, due to physical characteristics of the nanopore and inherent noise in the biological processes. It is thus paramount not only to formulate efficient error-correcting constructions for these channels, but also to establish bounds on the minimum redundancy required by such coding schemes. In this context, we adopt a simplified model of nanopore sequencing inspired by the work of Mao et al., accounting for the effects of intersymbol interference and measurement noise. For an input sequence of length$n$, The vector that is produced, designated as the read vector, may additionally suffer at most$t$substitution errors. We employ the well-known graph-theoretic clique-cover technique to establish that at least$t \log n-O(1)$bits of redundancy are required to correct multiple ($t \geqslant 2$) substitutions. While this is surprising in comparison to the case of a single substitution, that necessitates at most$\log \log n-O(1)$bits of redundancy, a suitable error-correcting code that is optimal up to a constant follows immediately from the properties of read vectors.

Due to their sequential nature, traditional DNA synthesis methods are expensive in terms of time and resources. They also fabricate multiple copies of the same strand, introducing redundancy. This redundancy can be leveraged to enhance the information capacity of each synthesis cycle and DNA storage systems in general by employing composite DNA symbols. Unlike conventional DNA storage, composite DNA encodes information in the distribution of bases across a pool of strands rather than in the individual strands themselves. Consequently, error models for DNA storage must be adapted to account for this unique characteristic. One significant error model for long-term DNA storage is strand breaks, often caused by the decay of individual bases. This work extends the strand-break channel model to the composite DNA setting. To address this challenge, we propose a coding scheme that uses marker codes to correct single strand breaks. As part of this approach, we generalise run-length-limited (RLL) codes for the composite setting and derive bounds on their redundancy.

Owing to its several merits over other DNA sequencing technologies, nanopore sequencers hold an immense potential to revolutionize the efficiency of DNA storage systems. However, their higher error rates necessitate further research to devise practical and efficient coding schemes that would allow accurate retrieval of the data stored. Our work takes a step in this direction by adopting a simplified model of the nanopore sequencer inspired by Mao et al., which incorporates some of its physical aspects. This channel model can be viewed as a sliding window of length ℓ that passes over the incoming input sequence and produces the Hamming weight of the enclosed ℓ bits, while shifting by one position at each time step. The resulting (ℓ + 1)-ary vector, referred to as the ℓ-read vector, is susceptible to deletion errors due to imperfections inherent in the sequencing process. We establish that at least log$n$- ℓ bits of redundancy are needed to correct a single deletion. An error-correcting code that is optimal up to an additive constant, is also proposed. Furthermore, we find that for ℓ ≥ 2, reconstruction from two distinct noisy ℓ-read vectors can be accomplished without any redundancy, and provide a suitable reconstruction algorithm to this effect.

Nanopore sequencing, superior to other sequencing technologies for DNA storage in multiple aspects, has recently attracted considerable attention. Its high error rates, however, demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Maoet al., incorporating intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of lengthlover aq-ary input sequence that outputs thecompositionof the enclosedlbits, and shifts by δ positions with each time step. In this context, the composition of aq-ary vectorxspecifies the number of occurrences inxof each symbol in {0,1,...,q- 1}. The resulting compositions vector, termed theread vector, may also be corrupted bytsubstitution errors. By employing graph-theoretic techniques, we deduce that for δ = 1, at least log lognsymbols of redundancy are required to correct a single (t= 1) substitution. Finally, forl≥ 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is of optimal redundancy up to a (small) additive constant for this setting. This construction is also found to be optimal for the case of reconstruction from two noisy read vectors.

Nanopore sequencers, being superior to other sequencing technologies for DNA storage in multiple aspects, have attracted considerable attention in recent times. Their high error rates however demand thorough research on practical and efficient coding schemes to enable accurate recovery of stored data. To this end, we consider a simplified model of a nanopore sequencer inspired by Mao et al., that incorporates intersymbol interference and measurement noise. Essentially, our channel model passes a sliding window of length ℓ over an input sequence, that outputs the L1-weight of the enclosed ℓ bits and shifts by δ positions with each time step. The resulting (ℓ + 1)-ary vector, termed the read vector, may also be corrupted by t substitution errors. By employing graph-theoretic techniques, we deduce that for δ = 1, at least log log n bits of redundancy are required to correct a single (t = 1) substitution. Finally for ℓ ≥ 3, we exploit some inherent characteristics of read vectors to arrive at an error-correcting code that is optimal up to an additive constant for this setting.

Mixed codes, which are error-correcting codes in the Cartesian product of different-sized spaces, model degrading storage systems well. While such codes have previously been studied for their algebraic properties (e.g., existence of perfect codes) or in the case of unbounded alphabet sizes, we focus on the case of finite alphabets, and generalize the Gilbert-Varshamov, sphere-packing, Elias-Bassalygo, and first linear programming bounds to that setting. In the latter case, our proof is also the first for the non-symmetric mono-alphabetic q-ary case using Navon and Samorodnitsky’s Fourier-analytic approach.

We study the adversarial torn-paper channel. This problem is motivated by applications in DNA data storage where the DNA strands that carry information may break into smaller pieces which are received out of order. Our model extends the previously researched probabilistic setting to the worst-case. We develop code constructions for any parameters of the channel for which non-vanishing asymptotic rate is possible and show our constructions achieve asymptotically optimal rate while allowing for efficient encoding and decoding. Finally, we extend our results to related settings included multi-strand storage, presence of substitution errors, or incomplete coverage.

This paper introduces a new family of reconstruction codes which is motivated by applications in DNA data storage and sequencing. In such applications, DNA strands are sequenced by reading some subset of their substrings. While previous works considered two extreme cases in which all substrings of pre-defined lengths are read or substrings are read with no overlap for the single string case, this work studies two extensions of this paradigm. The first extension considers the setup in which consecutive substrings are read with some given minimum overlap. First, an upper bound is provided on the attainable rates of codes that guarantee unique reconstruction. Then, efficient constructions of codes that asymptotically meet that upper bound are presented. In the second extension, we study the setup where multiple strings are reconstructed together. Given the number of strings and their length, we first derive a lower bound on the read substrings’ length$\ell $that is necessary for the existence of multi-strand reconstruction codes with non-vanishing rates. We then present two constructions of such codes and show that their rates approach 1 for values of$\ell $that asymptotically behave like the lower bound.

This paper studies the adversarial torn-paper channel. This problem is motivated by applications in DNA data storage where the DNA strands that carry the information may break into smaller pieces that are received out of order. Our model extends the previously researched probabilistic setting to the worst-case. We develop code constructions for any parameters of the channel for which non-vanishing asymptotic rate is possible and show that our constructions achieve optimal asymptotic rate while allowing for efficient encoding and decoding. Finally, we extend our results to related settings included multi-strand storage, presence of substitution errors, or incomplete coverage.

We consider the problem of coding for the substring channel, in which information strings are observed only through their (multisets of) substrings. Because of applications to DNA-based data storage, due to DNA sequencing techniques, interest in this channel has renewed in recent years. In contrast to existing literature, we consider a noisy channel model, where information is subject to noise before its substrings are sampled, motivated by in-vivo storage. We study two separate noise models, substitutions or deletions. In both cases, we examine families of codes which may be utilized for error-correction and present combinatorial bounds. Through a generalization of the concept of repeat-free strings, we show that the added required redundancy due to this imperfect observation assumption is sublinear, either when the fraction of errors in the observed substring length is sufficiently small, or when that length is sufficiently long. This suggests that no asymptotic cost in rate is incurred by this channel model in these cases.

The problem of string reconstruction based on its substrings spectrum has received significant attention recently due to its applicability to DNA data storage and sequencing. In contrast to previous works, we consider in this paper a setup of this problem where multiple strings are reconstructed together. Given a multiset S of strings, all their substrings of some fixed length $\ell$, defined as the $\ell$-profile of S, are received and the goal is to reconstruct all strings in S. A multi-strand $\ell$-reconstruction code is a set of multisets such that every element S can be reconstructed from its $\ell$-profile. Given the number of strings k and their length n, we first find a lower bound on the value of $\ell$ necessary for existence of multi-strand $\ell$-reconstruction codes with non-vanishing asymptotic rate. We then present two constructions of such codes and show that their rates approach 1 for values of $\ell$ that asymptotically behave like the lower bound.

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with$m>2$strings (where a previous paper considered$m=2$) in asymptotic terms, where code-words are taken from an error-correcting code. Thus, we find the trade-off between the design minimum distance, the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease coding redundancy, or the required number of reads, or both.

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with m > 2 strings (where a previous paper considered m = 2) in asymptotic terms, where code-words are taken from a typical set of strings, consisting a growing fraction of the space size, converging to 1. Thus, we find the trade-off between the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease the required number of reads.

Motivated by mutation processes occurring in in-vivo DNA-storage applications, a channel that mutates stored strings by duplicating substrings as well as substituting symbols is studied. Two models of such a channel are considered: one in which the substitutions occur only within the duplicated substrings, and one in which the location of substitutions is unrestricted. Both error-detecting and error-correcting codes are constructed, which can handle correctly any number of tandem duplications of a fixed length k , and at most a single substitution occurring at any time during the mutation process.

DNA as a data storage medium has several advantages, including far greater data density compared to electronic media. We propose that schemes for data storage in the DNA of living organisms may benefit from studying the reconstruction problem, which is applicable whenever multiple reads of noisy data are available. This strategy is uniquely suited to the medium, which inherently replicates stored data in multiple distinct ways, caused by mutations. We consider noise introduced solely by uniform tandem-duplication, and utilize the relation to constant-weight integer codes in the Manhattan metric. By bounding the intersection of the cross-polytope with hyperplanes, we prove the existence of reconstruction codes with full rate, as well as suggest a construction for a family of reconstruction codes.

Motivated by mutation processes occurring in in-vivo DNA-storage applications, a channel that mutates stored strings by duplicating substrings as well as substituting symbols is studied. Two models of such a channel are considered: one in which the substitutions occur only within the duplicated substrings, and one in which the location of substitutions is unrestricted. Both error-detecting and error-correcting codes are constructed, which can handle correctly any number of tandem duplications of a fixed length k, and at most a single substitution occurring at any time during the mutation process.

DNA as a data storage medium has several advantages, including far greater data density compared to electronic media. We propose that schemes for data storage in the DNA of living organisms may benefit from studying the reconstruction problem, which is applicable whenever multiple reads of noisy data are available. This strategy is uniquely suited to the medium, which inherently replicates stored data in multiple distinct ways, caused by mutations. We consider noise introduced solely by uniform tandem-duplication, and utilize the relation to constant-weight integer codes in the Manhattan metric. By bounding the intersection of the cross-polytope with hyperplanes, we prove the existence of reconstruction codes with greater capacity than known error-correcting codes.

We construct error-correcting codes over permutations under the infinity-metric, which are also Gray codes in the context of rank modulation, i.e., are generated as simple circuits in the rotator graph. These errors model limited-magnitude or spike errors, for which only single-error-detecting Gray codes are currently known. Surprisingly, the error-correcting codes we construct achieve a better asymptotic rate than that of presently known constructions not having the Gray property, and exceed the Gilbert-Varshamov bound. Additionally, we present efficient ranking and unranking procedures, as well as a decoding procedure that runs in linear time. Finally, we also apply our methods to solve an outstanding issue with error-detecting rank-modulation Gray codes (also known in this context as snake-in-the-box codes) under a different metric, the Kendall τ-metric, in the group of permutations over an even number of elements S2n, where we provide asymptotically optimal codes.

We construct Gray codes over permutations for the rank-modulation scheme, which are also capable of correcting errors under the infinity-metric. These errors model limited-magnitude or spike errors, for which only single-error-detecting Gray codes are currently known. Surprisingly, the error-correcting codes we construct achieve better asymptotic rates than that of presently-known constructions not having the Gray property. We also cast the problem of improving upon these results into the context of finding a certain type of auxiliary codes in the symmetric group of even orders.

Motivated by the rank-modulation scheme with applications to flash memory, we consider Gray codes capable of detecting a single error, also known as snake-in-the-box codes. We study two error metrics: Kendall's τ-metric, which applies to charge-constrained errors, and the ℓ∞-metric, which is useful in the case of limited-magnitude errors. In both cases we construct snake-in-the-box codes with rate asymptotically tending to 1.

Motivated by the rank-modulation scheme with applications to flash memory, we consider Gray codes capable of detecting a single error, also known as snake-in-the-box codes. We study two error metrics: Kendall's τ-metric, which applies to charge-constrained errors, and the ℓ∞-metric, which is useful in the case of limited-magnitude errors. In both cases, we construct snake-in-the-box codes with rate asymptotically tending to 1. We also provide efficient successor-calculation functions, as well as ranking and unranking functions. Finally, we also study bounds on the parameters of such codes.