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 $\tau$-metric, which applies charge-constrained errors, and $\ell_\infty$-metric, is useful in case limited magnitude errors. In both cases construct rate asymptotically tending 1. provide efficient successor-calculation functions, well ranking unranking functions. Finally, bounds on...

DNA as a data storage medium has several advantages, including far greater density compared to electronic media. We propose that schemes for in the of living organisms may benefit from studying reconstruction problem, which is applicable whenever multiple reads noisy are available. This strategy uniquely suited medium, inherently replicates stored distinct ways, caused by mutations. consider noise introduced solely uniform tandem-duplication, and utilize relation constant-weight integer...

Even tough DNA can be considered as a very stable long term storage medium, errors must expected during storage. From experiments it is evident that the most common error type due to are strand breaks. We address problem of correcting breaks in sequences resulting from composite synthesis. introduce novel channel model with realistic assumptions about Our proposed coding scheme employs marker codes correct single For this purpose, we generalize run-length-limited for setting and derive...

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

This paper introduces a new family of reconstruction codes which is motivated by applications in DNA data storage and sequencing. In such applications, strands are sequenced reading some subset their substrings. While previous works considered two extreme cases all substrings pre-defined lengths read or with no overlap for the single string case, this work studies extensions paradigm. The first extension considers setup consecutive given minimum overlap. First, an upper bound provided on...

Nanopore sequencers, being superior to other sequencing technologies for DNA storage in multiple aspects, have attracted considerable attention recent times. Their high error rates however demand thorough research on practical and efficient coding schemes enable accurate recovery of stored data. To this end, we consider a simplified model nanopore sequencer inspired by Mao et al., that incorporates intersymbol interference measurement noise. Essentially, our channel passes sliding window...

DNA as a data storage medium has several advantages, including far greater density compared to electronic media. We propose that schemes for in the of living organisms may benefit from studying reconstruction problem, which is applicable whenever multiple reads noisy are available. This strategy uniquely suited medium, inherently replicates stored distinct ways, caused by mutations. consider noise introduced solely uniform tandem-duplication, and utilize relation constant-weight integer...

We construct Gray codes over permutations for the rank-modulation scheme, which are also capable of correcting errors under infinity-metric. These model limited-magnitude or spike errors, only single-error-detecting currently known. Surprisingly, error-correcting we achieve a better asymptotic rate than that presently known constructions not having property, and exceed Gilbert-Varshamov bound. Additionally, present efficient ranking unranking procedures, as well decoding procedure runs in...

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

We consider the problem of coding for substring channel, in which information strings are observed only through their (multisets of) substrings. Due to existing DNA sequencing techniques and applications DNA-based storage systems, interest this channel has renewed recent years. In contrast literature, we a noisy model where is subject noise before its substrings sampled, motivated by in-vivo storage. study two separate models, substitutions or deletions. both cases, examine families codes...

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 enable accurate recovery of stored data. To this end, we consider a simplified model nanopore sequencer inspired by Mao <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i> ., incorporating...

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

We consider the problem of coding for substring channel, in which information strings are observed only through their (multisets of) substrings. Due to existing DNA sequencing techniques and applications DNA-based storage systems, interest this channel has renewed recent years. In contrast literature, we a noisy model where is subject noise before its substrings sampled, motivated by in-vivo storage. study two separate models, substitutions or deletions. both cases, examine families codes...

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

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

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 charge-constrained errors, and ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> -metric, is useful in case limited-magnitude errors. In both cases construct rate asymptotically tending 1.

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

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

The problem of string reconstruction based on its substrings spectrum has received significant attention recently due to applicability DNA data storage and sequencing. In contrast previous works, we consider in this paper a setup where multiple strings are reconstructed together. Given multiset $S$ strings, all their some fixed length $\ell$, defined as the $\ell$-profile $S$, goal is reconstruct $S$. A multi-strand $\ell$-reconstruction code set multisets such that every element can be from...

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

Owing to its several merits over other DNA sequencing technologies, nanopore sequencers hold an immense potential revolutionize the efficiency of storage systems. However, their higher error rates necessitate further research devise practical and efficient coding schemes that would allow accurate retrieval data stored. Our work takes a step in this direction by adopting simplified model sequencer inspired Mao \emph{et al.}, which incorporates some physical aspects. This channel can be viewed...

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

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 enable accurate recovery of stored data. To this end, we consider a simplified model nanopore sequencer inspired by Mao \emph{et al.}, incorporating intersymbol interference measurement noise. Essentially, our channel passes sliding window length...

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