Exact Reconstruction From Insertions in Synchronization Codes
Open accessThe DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion/deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion/insertion-correcting Varshamov-Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion/deletion channels and probabilistic channels.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Robust Chemical Preservation of Digital Information on DNA in Silica with Error-Correcting Codes
Grass, R. N., Heckel, R., Puddu, M., Paunescu, D., & Stark, W. J. (2015) · Angewandte Chemie International Edition · doi:10.1002/anie.201411378 · Cited by 754
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
Research works printed but not linked: 34
- 10.1109/JSAC.2008.081204 · doi:10.1109/jsac.2008.081204
- 10.1109/ISIT.2012.6284242 · doi:10.1109/isit.2012.6284242
- 10.1109/ISIT.2016.7541568 · DOI
- 10.1016/S0019-9958(69)90442-2 · doi:10.1016/s0019-9958(69)90442-2
- wilf, 1990, Generatingfunctionology
- 10.1109/TCOMM.2016.2552175 · doi:10.1109/tcomm.2016.2552175
- 10.1109/TIT.2015.2466635 · doi:10.1109/tit.2015.2466635
- 10.1109/TIT.2013.2290045 · doi:10.1109/tit.2013.2290045
- 10.1109/TIT.2015.2508800 · DOI
- farnoud, 2016, Estimating Mutation Rates and Sequence age Under a Stochastic Model for Tandem Duplication and Point Mutation
- benson, 1999, Reconstructing the duplication history of a tandem repeat, Proc Int Conf Intell Syst Molecular Biol (ISMB), 44
- 10.1109/ISIT.2016.7541455 · DOI
- 10.1109/TIT.2015.2505735 · doi:10.1109/tit.2015.2505735
- 10.1109/ISIT.2016.7541778 · DOI
- 10.1109/ISIT.2015.7282587 · DOI
- 10.1109/ITW.2015.7133132 · DOI
- levenshtein, 1966, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Phys Doklady, 10, 707
- 10.1109/ISIT.2005.1523342 · DOI
- 10.1109/TIT.2005.853300 · DOI
- batu, 2004, Reconstructing strings from random traces, Proc ACM-SIAM Symp Discrete Algorithms (SODA), 910
- holenstein, 2008, Trace reconstruction with constant deletion probability and related results, Proc ACM-SIAM Symp Discrete Algorithms (SODA), 389
- varshamov, 1965, Codes which correct single asymmetric errors, Avtomat i Telemeh, 26, 288
- viswanathan, 2008, Improved string reconstruction over insertion-deletion channels, Proc ACM-SIAM Symp Discrete Algorithms (SODA), 399
- 10.1109/ISIT.2015.7282947 · DOI
- 10.1109/ISIT.2012.6283016 · DOI
- 10.1006/jcta.2000.3081 · DOI · Paper page
- 10.1109/ISIT.2016.7541372 · doi:10.1109/isit.2016.7541372
- 10.1109/18.904499 · DOI · Paper page
- yazdi, 2015, A rewritable, random-access DNA-based storage system, Nature Sci Rep, 5, 14138, 10.1038/srep14138 · DOI · Paper page
- 10.1145/2872362.2872397 · DOI · Paper page
- 10.1109/TIT.2013.2257917 · doi:10.1109/tit.2013.2257917
- 10.1109/TIT.2015.2413958 · DOI
- 10.1109/TIT.2004.831751 · doi:10.1109/tit.2004.831751
- 10.1109/TIT.2016.2544348 · doi:10.1109/tit.2016.2544348
Cited by
Fundamental limits of DNA storage systems
Heckel, R., Shomorony, I., Ramchandran, K., & Tse, D. N. C. (2017) · 2017 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8007106 · Cited by 123
“Some of these aspects include DNA synthesis constraints such as sequence composition [4, 8, 13], the asymmetric nature of the DNA sequencing error channel [5], the need for codes that correct insertion errors [10], and the need for techniques to allow random access [13].”
BackgroundCheraghchi, M., Gabrys, R., Milenkovic, O., & Ribeiro, J. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.2996377 · Cited by 90
Self-citationInformation-Theoretic Foundations of DNA Data Storage
Shomorony, I., & Heckel, R. (2022) · Foundations and Trends® in Communications and Information Theory · doi:10.1561/0100000117 · Cited by 62
Optimal Reconstruction Codes for Deletion Channels
Chrisnata, J., Kiah, H. M., & Yaakobi, E. (2020) · arXiv · doi:10.48550/arxiv.2004.06032 · Cited by 14
Metadata
- Authors
- Sala, F., Gabrys, R., Schoeny, C., & Dolecek, L.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2017-04
- Volume
- 63
- Issue
- 4
- Pages
- 2428-2445
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2338754814
- Cited by
- 92
- References
- 2
- FWCI
- 4.92
- Type
- journal article
- Language
- en
- Open access
- green
- Licence
- Funders
- NSF Graduate Research Fellowship Program
- NSF (CCF-1527130)
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.