Adversarial Torn-paper Codes
Authors:
- 26 June 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2934-2939
Abstract
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.Keywords
All Related Versions
Funding Information
- European Research Council
This publication has 32 references indexed in Scilit:
- A complete bacterial genome assembled de novo using only nanopore sequencing dataNature Methods, 2015
- Robust Chemical Preservation of Digital Information on DNA in Silica with Error‐Correcting CodesAngewandte Chemie International Edition, 2015
- String Reconstruction from Substring CompositionsSIAM Journal on Discrete Mathematics, 2015
- Nonhybrid, finished microbial genome assemblies from long-read SMRT sequencing dataNature Methods, 2013
- Towards practical, high-capacity, low-maintenance information storage in synthesized DNANature, 2013
- Next-Generation Digital Information Storage in DNAScience, 2012
- Mind the gapsNature Methods, 2010
- Organic data memory using the DNA approachCommunications of the ACM, 2003
- On the existence of optimum cyclic burst correcting codes over GF(q)IEEE Transactions on Information Theory, 1988
- On the existence of optimum cyclic burst- correcting codesIEEE Transactions on Information Theory, 1986