Coded Trace Reconstruction
Open accessAbstract
Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of coded trace reconstruction, the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called traces) corrupted by edit errors. Codes used in current portable DNA-based storage systems with nanopore sequencers are largely based on heuristics, and have no provable robustness or performance guarantees even for an error model with i.i. d. deletions and constant deletion probability. Our work is a first step towards the design of efficient codes with provable guarantees for such systems. We consider a constant rate of i.i. d. deletions, and begin by analyzing marker-based code-constructions coupled with worst-case trace reconstruction algorithms. Then, we show how a more careful design of the code allows us to exploit ideas from average-case trace reconstruction to reduce the number of traces required with the same redundancy.
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 [93]
Cites
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
Random access in large-scale DNA data storage
Organick, L., Ang, S. D., Chen, Y.-J., Lopez, R., Yekhanin, S., Makarychev, K., Racz, M. Z., Kamath, G., Gopalan, P., Nguyen, B., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4079 · Cited by 775 · see citing works
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 · see citing works
Simple Constructions of Almost k‐wise Independent Random Variables
Alon, N., Goldreich, O., Håstad, J., et al. (1992) · Random Structures and Algorithms · doi:10.1002/rsa.3240030308 · Cited by 561 · see citing works
A Rewritable, Random-Access DNA-Based Storage System
Tabatabaei Yazdi, S. M. H., Yuan, Y., Ma, J., Zhao, H., & Milenkovic, O. (2015) · Scientific Reports · doi:10.1038/srep14138 · Cited by 401 · see citing works
Self-citationPortable and Error-Free DNA-Based Data Storage
Yazdi, S. M. H. T., Gabrys, R., & Milenkovic, O. (2017) · Scientific Reports · doi:10.1038/s41598-017-05188-1 · Cited by 361 · see citing works
Self-citationKnuth, D. E. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057136 · Cited by 288 · 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
Coding Over Sets for DNA Storage
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakobi, E. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437544 · Cited by 133 · see citing works
Reconstructing Strings from Random Traces
Batu, T., Kannan, S., Khanna, S., & McGregor, A. (2004) · London School of Economics and Political Science Research Online (London School of Economics and Political Science) · Cited by 130 · see citing works
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 · see citing works
Codes for DNA Sequence Profiles
Kiah, H. M., Puleo, G. J., & Milenković, O. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2555321 · Cited by 121 · see citing works
Exact 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
Self-citationTrace reconstruction with constant deletion probability and related results
Holenstein, T., Mitzenmacher, M., Panigrahy, R., & Wieder, U. (2008) · Symposium on Discrete Algorithms · Cited by 91 · see citing works
Codes in the Space of Multisets—Coding for Permutation Channels With Impairments
Kovačević, M., & Tan, V. Y. F. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2789292 · Cited by 91 · see citing works
Mutually Uncorrelated Primers for DNA-Based Data Storage
Yazdi, S. M. H. T., Kiah, H. M., Gabrys, R., et al. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2792488 · Cited by 73 · see citing works
Self-citationImmink, K. A. S., & Weber, J. H. (2010) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2010.100207 · Cited by 71 · see citing works
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
Cheng, K., Jin, Z., Li, X., et al. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00028 · Cited by 63 · see citing works
Trace reconstruction with exp(O(n 1/3 )) samples
Nazarov, F., & Peres, Y. (2017) · ACM SIGACT Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055494 · Cited by 58 · see citing works
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice
Peres, Y., & Zhai, A. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.29 · Cited by 55 · 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-citationCapacity Results for the Noisy Shuffling Channel
Shomorony, I., & Heckel, R. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849789 · Cited by 54 · see citing works
Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
Holden, N., Pemantle, R., Peres, Y., & Zhai, A. (2020) · Mathematical Statistics and Learning · doi:10.4171/msl/16 · Cited by 52 · see citing works
Optimal Document Exchange and New Codes for Insertions and Deletions
Haeupler, B. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00029 · Cited by 51 · see citing works
Optimal mean-based algorithms for trace reconstruction
De, A., O’Donnell, R., & Servedio, R. A. (2017) · ACM SIGACT Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055450 · Cited by 46 · see citing works
New lower bounds for trace reconstruction
Chase, Z. (2021) · Annales de l Institut Henri Poincaré Probabilités et Statistiques · doi:10.1214/20-aihp1089 · Cited by 43 · see citing works
Trace Reconstruction Revisited
McGregor, A., Price, E., & Vorotnikova, S. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44777-2_57 · Cited by 42 · see citing works
Lower bounds for trace reconstruction
Holden, N., & Lyons, R. (2020) · The Annals of Applied Probability · doi:10.1214/19-aap1506 · Cited by 38 · see citing works
Anchor-Based Correction of Substitutions in Indexed Sets
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakobi, E. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849523 · Cited by 36 · see citing works
Coding for Deletion Channels with Multiple Traces
Abroshan, M., Venkataramanan, R., Dolecek, L., & Fàbregas, A. G. I. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849647 · Cited by 31 · see citing works
On Maximum Likelihood Reconstruction over Multiple Deletion Channels
Srinivasavaradhan, S. R., Du, M., Diggavi, S. N., & Fragouli, C. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437519 · Cited by 30 · see citing works
Trace Reconstruction: Generalized and Parameterized
Krishnamurthy, A., Mazumdar, A., McGregor, A., et al. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3066010 · Cited by 29 · see citing works
Unique Reconstruction of Coded Sequences from Multiset Substring Spectra
Gabrys, R., & Milenković, O. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437909 · Cited by 28 · see citing works
Self-citationTrace reconstruction with varying deletion probabilities
Hartung, L., Holden, N., & Peres, Y. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975062.6 · Cited by 27 · see citing works
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel
Ban, F., Chen, X., Freilich, A., Servedio, R. A., & Sinha, S. (2019) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2019.00050 · Cited by 26 · see citing works
Shinkar, T., Yaakobi, E., Lenz, A., & Wachter-Zeh, A. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849737 · Cited by 23 · see citing works
On Coding Over Sliced Information
Sima, J., Raviv, N., & Bruck, J. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849596 · Cited by 23 · 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
Fundamental Bounds for Sequence Reconstruction From Nanopore Sequencers
Magner, A., Duda, J., Wojciech Szpankowski, A., & Grama, A. Y. (2016) · IEEE Transactions on Molecular Biological and Multi-Scale Communications · doi:10.1109/tmbmc.2016.2630056 · Cited by 21 · see citing works
Haeupler, B., & Mitzenmacher, M. (2014) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2014.6970811 · Cited by 17 · see citing works
Milenković, O., Gabrys, R., Kiah, H. M., & Yazdi, S. M. H. T. (2018) · IEEE Spectrum · doi:10.1109/mspec.2018.8352574 · Cited by 15 · see citing works
Self-citationReconstruction of Sequences Over Non-Identical Channels
Horovitz, M., & Yaakobi, E. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2859813 · Cited by 14 · see citing works
Symbolwise MAP for Multiple Deletion Channels
Srinivasavaradhan, S. R., Du, M., Diggavi, S. N., & Fragouli, C. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849567 · Cited by 14 · see citing works
The hybrid k-deck problem: Reconstructing sequences from short and long traces
Gabrys, R., & Milenković, O. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006740 · Cited by 13 · see citing works
Self-citationReconstructing trees from traces
Davies, S., Rácz, M. Z., & Rashtchian, C. (2021) · The Annals of Applied Probability · doi:10.1214/21-aap1662 · Cited by 13 · see citing works
Sequence-Subset Distance and Coding for Error Control for DNA-based Data Storage
Song, W., Cai, K., & Immink, K. A. S. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849687 · Cited by 13 · see citing works
New upper bounds for trace reconstructionPreprint
Chase, Z. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.03296 · Cited by 10 · see citing works
Sequence-Subset Distance and Coding for Error Control in DNA-based Data StoragePreprint
Song, W., Cai, K., & Immink, K. A. S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.05821 · Cited by 7 · see citing works
On Coding over Sliced InformationPreprint
Sima, J., Raviv, N., & Bruck, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.02716 · Cited by 6 · see citing works
Beyond trace reconstruction: Population recovery from the deletion channelPreprint
Ban, F., Chen, X., Freilich, A., et al. (2019) · arXiv (Cornell University) · doi:10.4230/lipics.approx-random.2019.44 · Cited by 6 · see citing works
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
Information-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 · see citing works
Optimal Reconstruction Codes for Deletion Channels
Chrisnata, J., Kiah, H. M., & Yaakobi, E. (2020) · arXiv · doi:10.48550/arxiv.2004.06032 · Cited by 14 · see citing works
- Authors
- Cheraghchi, M., Gabrys, R., Milenkovic, O., & Ribeiro, J.
- Affiliations
- Imperial College London (GB)
- University of Illinois Urbana-Champaign (US)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2020-10
- Volume
- 66
- Issue
- 10
- Pages
- 6084-6103
- ISSN
- 0018-9448
- 1557-9654
- OpenAlex
- W2922965174
- Cited by
- 90
- References
- 51
- Citations by year
- 2026: 2 · 2025: 11 · 2024: 11 · 2023: 9 · 2022: 18 · 2021: 24 · 2020: 13 · 2019: 2
- FWCI
- 39.62
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Information Theory Workshop (ITW) (publishedVersion)
- IEEE Transactions on Information Theory (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Defense Advanced Research Projects Agency (DARPA) Molecular Informatics Program
- NSF and Semiconductor Research Corporation (SRC) SemiSynBio Award
- NSF (1618366)
- Center for Science of Information
- NSF Science and Technology Center (CCF-0939370)
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Keywords
- trace reconstruction, DNA data storage, nanopore sequencing, deletion, error-correcting codes
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
