Optimal Reconstruction Codes for Deletion Channels
Open accessAbstract
The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads $N$ is fixed (Kiah et al. 2020). Of significance, for the single-deletion channel, using $\log_2\log_2 n +O(1)$ redundant bits, we designed a reconstruction code of length $n$ that reconstructs codewords from two distinct noisy reads. In this work, we show that $\log_2\log_2 n -O(1)$ redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of our previous construction. Furthermore, we show that these reconstruction codes can be used in $t$-deletion channels (with $t\ge 2$) to uniquely reconstruct codewords from $n^{t-1}+O\left(n^{t-2}\right)$ distinct noisy reads.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Recent works have explored efficient clustering methods tailored to DNA data storage and efficient encoding schemes that allow recovery of a sequence from multiple noisy reads.
“Recent works have explored the development of efficient clustering methods tailored to DNA data storage, as well as efficient encoding schemes that allow the recovery of a sequence from multiple noisy reads.93−96”
From Emerging Approaches to DNA Data Storage: Challenges and Prospects (2022) · cites this paper as [94]
Cites
Binary Codes capable of currecting deletions, insertions, and reversals
Levenshtein, V. I. (1965) · Soviet physics. Doklady · Cited by 10,387 · see citing works
Magnetic Domain-Wall Racetrack Memory
Parkin, S., Hayashi, M., & Thomas, L. (2008) · Science · doi:10.1126/science.1145799 · Cited by 4,668 · see citing works
Next-Generation Digital Information Storage in DNA
Church, G. M., Gao, Y., & Kosuri, S. (2012) · Science · doi:10.1126/science.1226355 · Cited by 1,441 · see citing works
Towards Practical, High-Capacity, Low-Maintenance Information Storage in Synthesized DNA
Goldman, N., Bertone, P., Chen, S., Dessimoz, C., LeProust, E. M., Sipos, B., & Birney, E. (2013) · Nature · doi:10.1038/nature11875 · Cited by 1,220 · see citing works
Knuth, D. E. (1994) · The Electronic Journal of Combinatorics · doi:10.37236/1193 · Cited by 296 · see citing works
DNA-Based Storage: Trends and Methods
Yazdi, S. M. H. T., Kiah, H. M., Garcia-Ruiz, E., Ma, J., Zhao, H., & Milenkovic, O. (2015) · IEEE Transactions on Molecular, Biological and Multi-Scale Communications · doi:10.1109/tmbmc.2016.2537305 · Cited by 278 · see citing works
Self-citationEfficient reconstruction of sequences
Levenshtein, V. I. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.904499 · Cited by 212 · see citing works
Codes Correcting a Burst of Deletions or Insertions
Schoeny, C., Wachter-Zeh, A., Gabrys, R., & Yaakobi, E. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541375 · Cited by 182 · see citing works
Self-citationChee, Y. M., Kiah, H. M., Vardy, A., Vu, V. K., & Yaakobi, E. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2807480 · Cited by 101 · see citing works
Self-citationExact Reconstruction From Insertions in Synchronization Codes
Sala, F., Gabrys, R., Schoeny, C., & Dolecek, L. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2649493 · Cited by 93 · see citing works
Cheraghchi, M., Gabrys, R., Milenkovic, O., & Ribeiro, J. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.2996377 · Cited by 90 · see citing works
Sequence Reconstruction Over the Deletion Channel
Gabrys, R., & Yaakobi, E. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2800044 · Cited by 55 · see citing works
Self-citationCoding for Sequence Reconstruction for Single Edits
Cai, K., Kiah, H. M., Nguyen, T. T., & Yaakobi, E. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3122798 · Cited by 44 · see citing works
Self-citationError graphs and the reconstruction of elements in groups
Levenshtein, V. I., & Siemons, J. (2008) · Journal of Combinatorial Theory Series A · doi:10.1016/j.jcta.2008.11.005 · Cited by 40 · see citing works
On reconstruction of signed permutations distorted by reversal errors
Konstantinova, E. V. (2007) · Discrete Mathematics · doi:10.1016/j.disc.2007.08.003 · Cited by 35 · see citing works
A Characterization of the Number of Subsequences Obtained via the Deletion Channel
Liron, Y., & Langberg, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2413958 · Cited by 27 · see citing works
Perspectives of Racetrack Memory for Large-Capacity On-Chip Memory: From Device to System
Zhang, Y., Zhang, C., Nan, J., Zhang, Z., Zhang, X., Klein, J., Ravelosona, D., Sun, G., & Zhao, W. S. (2016) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2016.2529240 · Cited by 27 · see citing works
Reconstruction of Sequences in DNA Storage
Abu-Sini, M., & Yaakobi, E. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849740 · Cited by 22 · see citing works
Self-citationCoding for Sequence Reconstruction for Single Edits
Kiah, H. M., Nguyen, T. T., & Yaakobi, E. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174139 · Cited by 19 · see citing works
Self-citationReconstruction Codes for DNA Sequences with Uniform Tandem-Duplication Errors
Yehezkeally, Y., & Schwartz, M. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437731 · Cited by 11 · see citing works
The Levenshtein’s Channel and the List Size in Information Retrieval
Junnila, V., Laihonen, T. K., & Lehtilä, T. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849616 · Cited by 6 · see citing works
Coding for Sequence Reconstruction for Single EditsPreprint
Cai, K., Kiah, H. M., Nguyen, T. T., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.01376 · Cited by 5 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Emerging Approaches to DNA Data Storage: Challenges and Prospects
Doricchi, A., Platnich, C. M., Gimpel, A., Horn, F., Earle, M., Lanzavecchia, G., Cortajarena, A. L., Liz-Marzán, L. M., Liu, N., Heckel, R., et al. (2022) · ACS Nano · doi:10.1021/acsnano.2c06748 · Cited by 235 · see citing works
Coding for Sequence Reconstruction for Single Edits
Cai, K., Kiah, H. M., Nguyen, T. T., & Yaakobi, E. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3122798 · Cited by 44 · see citing works
Self-citationTrace Reconstruction Problems in Computational Biology
Bhardwaj, V., Pevzner, P. A., Rashtchian, C., & Safonova, Y. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3030569 · Cited by 35 · see citing works
Correcting Deletions With Multiple Reads
Chrisnata, J., Kiah, H. M., & Yaakobi, E. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3184868 · Cited by 30 · see citing works
Self-citationSequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution
Pham, V. L. P., Goyal, K., & Kiah, H. M. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834433 · Cited by 28 · see citing works
Self-citationSequence Reconstruction Under Single-Burst-Insertion/Deletion/Edit Channel
Sun, Y., Xi, Y., & Ge, G. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3250459 · Cited by 22 · see citing works
Correcting Two-Deletion With a Constant Number of Reads
Sun, Y., & Ge, G. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3226296 · Cited by 15 · see citing works
Reconstruction of Sequences Distorted by Two Insertions
Ye, Z., Liu, X., Zhang, X., & Ge, G. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3260872 · Cited by 12 · see citing works
Correcting Two Deletions with More Reads
Chrisnata, J., & Kiah, H. M. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9518269 · Cited by 10 · see citing works
Self-citationError-Correcting Codes for Nanopore Sequencing
Banerjee, A., Yehezkeally, Y., Wachter-Zeh, A., & Yaakobi, E. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206710 · Cited by 8 · see citing works
Self-citationApproximate Trace ReconstructionPreprint
Davies, S., Rácz, M. Z., Rashtchian, C., & Schiffer, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.06713 · Cited by 7 · see citing works
Sequences and their applications
Chrisnata, J. (2021) · doi:10.32657/10356/155586 · Cited by 7 · see citing works
Self-citationHow to Find Simple Conditions for Successful Sequence Reconstruction?
Wang, C., Yaakobi, E., & Zhang, Y. (2024) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw61385.2024.10807014 · Cited by 4 · see citing works
Self-citationSome New Constructions of q-ary Codes for Correcting a Burst of at Most t Deletions
Song, W., Cai, K., & Quek, T. Q. S. (2025) · Entropy · doi:10.3390/e27010085 · Cited by 2 · see citing works
- Authors
- Chrisnata, J., Kiah, H. M., & Yaakobi, E.
- Affiliations
- Nanyang Technological University (SG)
- Technion – Israel Institute of Technology (IL)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2020
- Pages
- 279-283
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2004.06032
- OpenAlex
- W3015606853
- Cited by
- 14
- References
- 22
- Citations by year
- 2025: 1 · 2024: 1 · 2023: 3 · 2022: 4 · 2021: 3 · 2020: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- sequence reconstruction, deletion channel, optimal redundancy, storage devices, combinatorial coding
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
