Fundamental limits of DNA storage systems
The DOI matches its Crossref record; 11 of the 12 references it cites were found in a registry or an index.
Abstract
Due to its longevity and enormous information density, DNA is an attractive medium for archival storage. In this work, we study the fundamental limits and tradeoffs of DNA-based storage systems under a simple model, motivated by current technological constraints on DNA synthesis and sequencing. Our model captures two key distinctive aspects of DNA storage systems: (1) the data is written onto many short DNA molecules that are stored in an unordered way and (2) the data is read by randomly sampling from this DNA pool. Under this model, we characterize the storage capacity, and show that a simple index-based coding scheme is optimal.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
In the citing paper
“In 2017, Heckel et al. considered the storage capacity using both assembly methods and have shown that an index-based coding system is optimal for data storage purposes [31].”
From DNA Data Storage. (2023) · cites this paper as [31]
Citations
Cites
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 · cited 4×
“Several works [CGK12; Gol+13; Gra+15; Bor+16; EZ17; Yaz+15a] have demonstrated that writing, storing, and retrieving data on the order of megabytes is possible with today’s technology, and achieves information densities and information lifetimes [Gra+15] that are far beyond what state-of-the-art…”
BackgroundInfluentialTowards 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
DNA Fountain enables a robust and efficient storage architecture
Erlich, Y., & Zielinski, D. (2017) · Science · doi:10.1126/science.aaj2038 · Cited by 898
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 · cited 1×
“Several works [2– 4, 6, 7, 13] have demonstrated that writing, storing, and retrieving data on the order of megabytes is possible with today’s technology, and achieves information densities and information lifetimes [7] that are far beyond what state-of-theart tapes and discs achieve.”
BackgroundSelf-citationA 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
A DNA-Based Archival Storage System
Bornholt, J., Lopez, R., Carmean, D. M., Ceze, L., Seelig, G., & Strauss, K. (2016) · Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/2872362.2872397 · Cited by 316
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 · cited 1×
“We refer to [4, 12] for a survey and an overview of the recent advances in the area.”
BackgroundBuilding an Associative Memory Vastly Larger Than the Brain
Baum, E. B. (1995) · Science · doi:10.1126/science.7725109 · Cited by 168 · cited 1×
“The idea to store information on DNA is relatively new [Bau95], and has recently gained significant attention [CGK12; Gol+13; Gra+15; Bor+16; EZ17; Yaz+15a], due to advances in synthesis and sequencing.”
BackgroundCodes 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 145
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 92 · cited 1×
“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].”
Background
Research works printed but not linked: 3
- sayir, 2016, Codes for efficient data storage on DNA molecules, Talk at Inform Inference and Energy symposium Cambridge UK
- heckel, 2017, Fundamental Limits of DNA Storage Systems
- mackay, 2015, Near-capacity codes for fountainchannels with insertions, deletions, and substitutions, with applications to DNA archives, Unpublished manuscript
Cited by
Molecular Digital Data Storage Using DNA
Ceze, L., Nivala, J., & Strauss, K. (2019) · Nature Reviews Genetics · doi:10.1038/s41576-019-0125-3 · Cited by 551
DNA stability: a central design consideration for DNA data storage systems
Matange, K., Tuck, J. M., & Keung, A. J. (2021) · Nature Communications · doi:10.1038/s41467-021-21587-5 · Cited by 209
Reading and Writing Digital Data in DNA
Meiser, L. C., Antkowiak, P. L., Koch, J., Chen, W. D., Kohll, A. X., Stark, W. J., Heckel, R., & Grass, R. N. (2020) · Nature Protocols · doi:10.1038/s41596-019-0244-5 · Cited by 164
“TROUBLESHOOTING 8 Purify the band at 120 – 170 nt (depending on the synthesized oligo length) with the QIAquick PCR Puri fi cation Kit according to the supplier ’ s instructions.”
MethodInfluentialSelf-citationTowards practical and robust DNA-based data archiving using the yin–yang codec system
Ping, Z., Chen, S., Zhou, G., Huang, X., Zhu, S. J., Zhang, H., Lee, H. H., Lan, Z., Cui, J., Chen, T., et al. (2022) · Nature Computational Science · doi:10.1038/s43588-022-00231-2 · Cited by 165
High Density DNA Data Storage Library via Dehydration with Digital Microfluidic Retrieval
Newman, S., Stephenson, A. P., Willsey, M., Nguyen, B. H., Takahashi, C. N., Strauss, K., & Ceze, L. (2019) · Nature Communications · doi:10.1038/s41467-019-09517-y · Cited by 144
Coding Over Sets for DNA Storage
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakobi, E. (2018) · IEEE Transactions on Information Theory · doi:10.1109/isit.2018.8437544 · Cited by 158
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 87
“To avoid possible confusion we emphasize once more that what we are discussing in this paper is error correction for a different model, partially motivated by [21], which assumes that codewords are multisets of DNA molecules (or multisets of any other objects for that matter).”
BackgroundInfluentialCheraghchi, M., Gabrys, R., Milenkovic, O., & Ribeiro, J. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.2996377 · Cited by 90
“An information-theoretic treatment of related but abstracted models of DNA-based data storage may be found in [32, 33].”
BackgroundImproved read/write cost tradeoff in DNA-based data storage using LDPC codes
Chandak, S., Tatwawadi, K., Lau, B., Mardia, J., Kubit, M., Neu, J., Griffin, P., Wootters, M., Weissman, T., & Ji, H. (2019) · 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2019.8919890 · Cited by 80
“While several previous works such as [15], [16], [18] theoretically analyze various aspects of the DNA-based storage problem (such as the information-theoretic capacity in the asymptotic setting and the optimality of various techniques to recover the order of the oligonucleotides), our main focus…”
BackgroundTrellis BMA: Coded Trace Reconstruction on IDS Channels for DNA Storage
Srinivasavaradhan, S. R., Gopi, S., Pfister, H. D., & Yekhanin, S. (2021) · 2021 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517821 · Cited by 75
Nucleic Acid Databases and Molecular-Scale Computing
Song, X., & Reif, J. (2019) · ACS Nano · doi:10.1021/acsnano.9b02562 · Cited by 73
DNA-Based Storage: Models and Fundamental Limits
Shomorony, I., & Heckel, R. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3058966 · Cited by 72
“By proving Lemma 2 in this setting, one can establish a version of Theorem 1 for the sampling-with-replacement shuffling channel, as previously described in [22].”
BackgroundSelf-citationUncertainties in synthetic DNA-based data storage
Xu, C., Zhao, C., Ma, B., & Liu, H. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkab230 · Cited by 67
“Such an encoding framework has been proven to exhibit ideal storage capacity (110).”
BackgroundCapacity Results for the Noisy Shuffling Channel
Shomorony, I., & Heckel, R. (2019) · 2019 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849789 · Cited by 56
“Similar to our previous work [9], we let L = β logM , and consider the asymptotic regime M → ∞.”
BackgroundResultInfluentialSelf-citationInformation Theory in Computational Biology: Where We Stand Today
Chanda, P., Costa, E., Hu, J. K., Sukumar, S., Hemert, J. V., & Walia, R. R. (2020) · Entropy · doi:10.3390/e22060627 · Cited by 62
“Multiple methods have been proposed in the last few years [72,77,78,85–87] that aim to harness the properties of DNA to mathematically model it as a storage channel and improve it’s information capacity.”
BackgroundChandak, S., Neu, J., Tatwawadi, K., Mardia, J., Lau, B. T., Kubit, M. A., Hulett, R., Griffin, P. B., Wootters, M. K., Weissman, T., et al. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9053441 · Cited by 71
An Upper Bound on the Capacity of the DNA Storage Channel
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakobi, E. (2019) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw44776.2019.8989388 · Cited by 37
“In [7] the capacity is found for p = 0 , and [8] considers the case where each sequence is drawn exactly once.”
BackgroundMethodInfluentialCoding Theorems for Noisy Permutation Channels
Makur, A. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3009468 · Cited by 48
“A very closely related DNA based storage model to [15], known as the noisy shuffling channel, is investigated in [17].”
BackgroundMethodResultInfluentialClover: tree structure-based efficient DNA clustering for DNA-based data storage
Qu, G., Yan, Z., & Wu, H. (2022) · Briefings in Bioinformatics · doi:10.1093/bib/bbac336 · Cited by 48
On Coding Over Sliced Information
Sima, J., Raviv, N., & Bruck, J. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3063709 · Cited by 44
Trace 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 43
“Storing and retrieving a set of strings leads to interesting coding-theoretic problems as well [56], [59], [61], [63], [64], [68], [69].”
BackgroundNovel combinatorial coding results for DNA sequencing and data storage
Schoeny, C., Sala, F., & Dolecek, L. (2017) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2017.8335392 · Cited by 34
“This process has motivated a large amount of recent research into assembly and reconstruction algorithms, seeking to answer, for example, the minimum number of fragments that must be read, the smallest amount of overlap, and the most efficient algorithm required for successful assembly [6]–[9].”
BackgroundSurvey for a Decade of Coding for DNA Storage
Sabary, O., Kiah, H. M., Siegel, P. H., & Yaakobi, E. (2024) · IEEE Transactions on Molecular Biological and Multi-Scale Communications · doi:10.1109/tmbmc.2024.3403488 · Cited by 57
“(see [58], [59] and the references therein), while the code design problem is referred to as coding over sets [60].”
BackgroundAchieving the Capacity of the DNA Storage Channel
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakohi, E. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9053049 · Cited by 28
On Coding for an Abstracted Nanopore Channel for DNA Storage
Hulett, R., Chandak, S., & Wootters, M. K. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9518236 · Cited by 32
Sequence-Subset Distance and Coding for Error Control in DNA-Based Data Storage
Song, W., Cai, K., & Immink, K. A. S. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3002611 · Cited by 35
“2In [16], the storage rate of a code C is defined as log |C| ML , where M is the constant codeword size.”
BackgroundResultInfluentialDNA-Based Data Storage Systems: A Review of Implementations and Code Constructions
Milenković, O., & Pan, C. (2024) · IEEE Transactions on Communications · doi:10.1109/tcomm.2024.3367748 · Cited by 44
“…analyze the above-described architectures [58], involving overlapping DNA fragments akin to those used in the original storage architectures of [25] and [43], and nonoverlapping information-bearing blocks which model pools without address sequences (see [49], [63] and references therein).”
BackgroundShomorony, I., & Vahid, A. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3120920 · Cited by 41
“Hence, using a simple counting argument to bound the number of different possible histograms (see Lemma 1 in [25]),”
MethodSelf-citationNOREC4DNA: using near-optimal rateless erasure codes for DNA storage
Schwarz, P. M., & Freisleben, B. (2021) · BMC Bioinformatics · doi:10.1186/s12859-021-04318-x · Cited by 25
“[3] proposed an index-based coding scheme, mapping data annotated with the corresponding index, without further modification of these data packets.”
MethodBio-Constrained Codes with Neural Network for Density-Based DNA Data Storage
Rasool, A., Qu, Q., Wang, Y., & Jiang, Q. (2022) · Mathematics · doi:10.3390/math10050845 · Cited by 25
“Researchers [2,29,30] have formulized single constraints and/or combined the constraints to attain the targeted results by preventing DNA sequence (DNA code) errors.”
BackgroundIMG-DNA: approximate DNA storage for images
Li, B., Ou, L., & Du, D. H.-C. (2021) · ACM International Conference on Systems and Storage · doi:10.1145/3456727.3463771 · Cited by 29
Capacity of the Torn Paper Channel with Lost Pieces
Ravi, A. N., Vahid, A., & Shomorony, I. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9518272 · Cited by 23
Self-citationHow to make DNA data storage more applicable
Akash, A., Bencúrová, E., & Dandekar, T. (2023) · Trends in biotechnology · doi:10.1016/j.tibtech.2023.07.006 · Cited by 27
Buko, T., Tuczko, N., & Ishikawa, T. (2023) · BioTech · doi:10.3390/biotech12020044 · Cited by 21
“considered the storage capacity using both assembly methods and have shown that an index-based coding system is optimal for data storage purposes [31].”
MethodCapacity of Noisy Permutation Channels
Tang, J., & Polyanskiy, Y. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3247812 · Cited by 25
“The state-of-the-art technology for storing information on DNA uses nucleotides with relatively small lengths (few hundreds) [12].”
BackgroundOn 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 24
“The work of [8] addressed this channel model under the restriction that individual strings are read in an error free manner, and some strings might get lost as a result of random sampling of the DNA pool.”
BackgroundOligo Design with Single Primer Binding Site for High Capacity DNA-Based Data Storage
Wang, Y., Noor‐A‐Rahim, M., Zhang, J., Gunawan, E., Guan, Y. L., & Poh, C. L. (2019) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2019.2940177 · Cited by 21
“However, the practical information capacity of a typical DNA-based storage system is much lower due to the biochemical constraints and the redundancy that are added to handle mutations in the processes [17].”
BackgroundRavi, A. N., Vahid, A., & Shomorony, I. (2022) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2022.3151737 · Cited by 26
Self-citationBar-Lev, D., Marcovich, S., Yaakobi, E., & Yehezkeally, Y. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3292895 · Cited by 30
“…leads to the problem of string reconstruction from substring composition [3], [6], [15], [22], [23], [29], [31]; on the contrary, assuming no overlap in read substrings leads to the torn-paper problem [24], [26], [32], a problem closely related to the shuffling channel [18], [19], [30], [35].”
BackgroundThe Bee-Identification Problem: Bounds on the Error Exponent
Tandon, A., Tan, V. Y. F., & Varshney, L. R. (2019) · IEEE Transactions on Communications · doi:10.1109/tcomm.2019.2935204 · Cited by 18
“In another related work [5], the fundamental limits of data storage via unordered DNA molecules was investigated.”
BackgroundOn the Size of Balls and Anticodes of Small Diameter Under the Fixed-Length Levenshtein Metric
Bar-Lev, D., Etzion, T., & Yaakobi, E. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3227128 · Cited by 21
“However, DNA molecules induce error patterns that are fundamentally different from their digital counterparts [17,18,21,29]; This distinction results from the specific error behavior in DNA and it is well-known that errors in DNA are typically in the form of substitutions, insertions, and deletions, where most publish…”
BackgroundRobust Indexing - Optimal Codes for DNA Storage
Sima, J., Raviv, N., & Bruck, J. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174447 · Cited by 16
“While many coding theoretic works have been done for various channel models concerning different physical aspects of DNA storage [8], [5], [13], and [7], this paper focuses on coding over unordered sets, which captures some basic features in the writing and reading processes described above.”
BackgroundError Correction for DNA Storage
Sima, J., Raviv, N., Schwartz, M., & Bruck, J. (2023) · IEEE BITS the Information Theory Magazine · doi:10.1109/mbits.2023.3318516 · Cited by 17
“The model of encoding information into a set of unordered and equal-length sequences was introduced in [46], where it was shown that index-based schemes achieve the channel capacity when there are sequence losses.”
MethodEvolution of $k$ -Mer Frequencies and Entropy in Duplication and Substitution Mutation Systems
Lou, H., Schwartz, M., Bruck, J., & Farnoud, F. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2946846 · Cited by 14
“With challenges arising from the existence of diverse error types in DNA synthesis, replication, and sequencing, many techniques in information theory, especially coding schemes, have been studied and used to enhance the reliability of DNA storage system [22], [27], [30], [32], [45], [49].”
MethodCommunicating over the Torn-Paper Channel
Shomorony, I., & Vahid, A. (2020) · Globecom · doi:10.1109/globecom42002.2020.9348147 · Cited by 15
“Notice that the kth channel is intuitively similar to the shuffling channel with equal-length pieces considered in [16].”
Self-citationSequence-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 12
“The fundamental limits of the DNA storage model was investigated in [12] under the assumption that each sampled molecule is read in an errorfree manner.”
BackgroundUV-Vis Spectrophotometric Analysis of DNA Retrieval for DNA Storage Applications
Minhas‐Khan, A., Ghafar-Zadeh, M., Shaffaf, T., Forouhi, S., Scimè, A., Magierowski, S., & Ghafar‐Zadeh, E. (2021) · Actuators · doi:10.3390/act10100246 · Cited by 21
Generalized Unique Reconstruction From Substrings
Yehezkeally, Y., Bar-Lev, D., Marcovich, S., & Yaakobi, E. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3269124 · Cited by 13
“problem closely related to the shuffling channel [15], [18], [33], [37]), which results from an assumption of no overlap.”
BackgroundInformation Capacity of BSC and BEC Permutation Channels
Makur, A. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8636070 · Cited by 13
“The authors of [10] examined the storage capacity of systems where the source is encoded via DNA molecules.”
BackgroundDNAsmart: Multiple attribute ranking tool for DNA data storage systems
Ezekannagha, C., Welzel, M., Heider, D., & Hattab, G. (2023) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2023.02.016 · Cited by 11
“These aspects specifically target the capacity of the storage channel [12,13] and the design of error correction codes (ECC) [14,15] for the specific errors [16] that arise inside a DNA data storage system.”
BackgroundNanopore Detection Assisted DNA Information Processing
Song, Z., Liang, Y., & Yang, J. (2022) · Nanomaterials · doi:10.3390/nano12183135 · Cited by 12
“The quality of DNA storage depends on DNA synthesis and sequencing [10,11].”
BackgroundNanopore DNA Sequencing Channel Modeling
Conde-Canencia, L., & Dolecek, L. (2018) · SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems · doi:10.1109/sips.2018.8598361 · Cited by 15
“This process has motivated recent research into reconstruction algorithms [7] [8] [9].”
MethodThe Noisy Drawing Channel: Reliable Data Storage in DNA Sequences
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakobi, E. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3231752 · Cited by 11
“The capacity has been derived for this case and it has been shown [21] that a simple indexing and erasure correction scheme achieves capacity.”
BackgroundMethodResultInfluentialCoding Over Coupon Collector Channels for Combinatorial Motif-Based DNA Storage
Sokolovskii, R., Agarwal, P., Croquevielle, L. A., Zhou, Z., & Heinis, T. (2024) · IEEE Transactions on Communications · doi:10.1109/tcomm.2024.3506938 · Cited by 17
“This optimisation is introduced in [10]; in the following, we offer its visual interpretation based on the capacity curves.”
BackgroundBenine, C., Boutlelis, D. A., Laiche, A. T., Lanez, E., Amara, D. G., Rim, G., Najjaa, H., Zahnit, W., & Messaoudi, M. (2025) · International Journal of Biological Macromolecules · doi:10.1016/j.ijbiomac.2025.139709 · Cited by 14
Achievable Rates of Concatenated Codes in DNA Storage under Substitution ErrorsPreprint
Lenz, A., Welter, L., & Puchinger, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.00051 · Cited by 11
Capacity of the Erasure Shuffling Channel
Shin, S., Heckel, R., & Shomorony, I. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9053486 · Cited by 10
“…where the sequences are sampled with replacement and errors are introduced in each sampled string according to a BSC, [20] has provided an upper bound using a proof strategy that is similar to those in [7, 8] and in addition establishes a connection with the capacity of multi-draw channels [22].”
BackgroundMethodResultInfluentialSelf-citationEmbedded Codes for Reassembling Non-Overlapping Random DNA Fragments
Nassirpour, S., & Vahid, A. (2020) · IEEE Transactions on Molecular Biological and Multi-Scale Communications · doi:10.1109/tmbmc.2020.3035370 · Cited by 14
“Another indexed sequencing approach in [36] studies the fundamental limits of DNA-based storage in a specific setting.”
BackgroundA Characterization of the DNA Data Storage Channel
Heckel, R., Mikutis, G., & Grass, R. N. (2019) · Scientific Reports · doi:10.1038/s41598-019-45832-6 · Cited by 9
Self-citationGenerative Adversarial Networks for DNA Storage Channel Simulator
Kang, S., Gao, Y., Jeong, J., Park, S., Kim, J.-W., No, J., Jeon, H., Lee, J. W., Kim, S., Park, H., et al. (2023) · IEEE Access · doi:10.1109/access.2023.3235201 · Cited by 12
Electrically Controlled Nanofluidic DNA Sluice for Data Storage Applications
Athreya, N. B. M., Khandelwal, A., Li, X., & Leburton, J. (2021) · ACS Applied Nano Materials · doi:10.1021/acsanm.1c02519 · Cited by 10
Bee-Identification Error Exponent with Absentee Bees
Tandon, A., Tan, V. Y. F., & Varshney, L. R. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174504 · Cited by 9
“In another related work, the fundamental limit of data storage via unordered DNA molecules was investigated in [5], while the corresponding capacity results were extended to a noisy setting in [6].”
BackgroundIndex-Based Concatenated Codes for the Multi-Draw DNA Storage Channel
Welter, L., Maarouf, I., Lenz, A., Wachter-Zeh, A., Rosnes, E., & Amat, A. G. I. (2023) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw55543.2023.10161631 · Cited by 9
“The index codes [3, 1]4 (AIR simulations) and [6, 2]4 (information-outage/FER simulations), both with Rix = 1 3 , are obtained via an exhaustive graph search algorithm optimizing the code’s Levenshtein distance spectrum (see Table I) [10], [30].”
BackgroundMethodBounds on Permutation Channel Capacity
Makur, A. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174455 · Cited by 8
“(b) Communication system with a random permutation followed by a DMC. Finally, a third motivation for examining permutation channels arises from recent research on DNA based storage systems [13], [14].”
BackgroundBar-Lev, D., Marcovich, S., Yaakobi, E., & Yehezkeally, Y. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834766 · Cited by 10
Chandak, S., Neu, J., Tatwawadi, K., Mardia, J., Lau, B. T., Kubit, M. A., Hulett, R., Griffin, P. B., Wootters, M. K., Weissman, T., et al. (2019) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2019.12.20.871939 · Cited by 8
An Information Theory for Out-of-Order Media With Applications in DNA Data Storage
Ravi, A. N., Vahid, A., & Shomorony, I. (2024) · IEEE Transactions on Molecular Biological and Multi-Scale Communications · doi:10.1109/tmbmc.2024.3403759 · Cited by 8
“The results presented in this paper are aligned with the recent literature on modeling the DNA storage channel and studying its capacity, which includes studies on the noisy shuffling channel model [7], [19], [36] and multi-draw sampling channels [13], [37], [38].”
BackgroundResultSelf-citationDNA Merge-Sort: A Family of Nested Varshamov-Tenengolts Reassembly Codes for Out-of-Order Media
Nassirpour, S., Shomorony, I., & Vahid, A. (2023) · IEEE Transactions on Communications · doi:10.1109/tcomm.2023.3335409 · Cited by 8
“The information-theoretic capacity of the shuffling channel is understood [13], and the capacity is achievable through indexing the short DNA molecules and using the remaining space for data bits.”
BackgroundSelf-citationPermutation Capacity Region of Adder Multiple-Access Channels
Lu, W., & Makur, A. (2024) · IEEE Transactions on Information Theory · doi:10.1109/tit.2024.3350436 · Cited by 7
“Implementations of such systems store data in relatively short DNA molecules as strings of a few hundred nucleotides [21].”
BackgroundA Survey Paper on DNA-Based Data Storage
Taluja, S., Bhupal, J., & Krishnan, S. R. (2020) · International Conference on Emerging Trends in Information Technology and Engineering (ICETITE) · doi:10.1109/ic-etite47903.2020.62 · Cited by 11
“R Heckel et al [16] described how there has been a great demand for data storage as there have been different challenges to the current data centers and storage techniques.”
BackgroundAchieving the Capacity of a DNA Storage Channel with Linear Coding Schemes
Levick, K., Heckel, R., & Shomorony, I. (2022) · Conference on Information Sciences and Systems · doi:10.1109/ciss53076.2022.9751151 · Cited by 8
Self-citation10 Years of Natural Data Storage
Limbachiya, D., Gupta, M. K., & Aggarwal, V. (2022) · IEEE Transactions on Molecular Biological and Multi-Scale Communications · doi:10.1109/tmbmc.2022.3211446 · Cited by 9
“Fundamental theoretical limits have been discussed by Heckel et al. in [22].”
BackgroundBee Identification Problem for DNA Strands
Chrisnata, J., Kiah, H. M., Vardy, A., & Yaakobi, E. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834414 · Cited by 5
“Also, fundamental limits of such storage systems are studied in [22]–[24].”
BackgroundOn Achievable Rates for the Shotgun Sequencing Channel with Erasures
Narayanan, H., Krishnan, P., & Parekh, N. (2024) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit57864.2024.10619286 · Cited by 5
“For instance, the works [5], [6] identified the capacity of the Sampling-Shuffling Channel , where data is stored as a set of short DNA strands of equal length, and reads are obtained by sampling (with replacement) from this set.”
BackgroundCapacity of Noisy Permutation Channels
Tang, J., & Polyanskiy, Y. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834509 · Cited by 5
Coding for Strand Breaks in Composite DNA
Walter, F., & Yehezkeally, Y. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195278 · Cited by 9
“Many of them have been addressed [12]– [14].”
Efficiently Enabling Block Semantics and Data Updates in DNA Storage
Sharma, P., Lim, C. K., Lin, D., Pote, Y., & Jevdjic, D. (2023) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3613424.3614308 · Cited by 9
“When this tree is balanced and full, i.e., when all DNA strands have the same index length and all indexes are present, then the maximum information density is achieved [15].”
BackgroundAn End-to-End Coding Scheme for DNA-Based Data Storage With Nanopore-Sequenced Reads
Welter, L., Sokolovskii, R., Heinis, T., Wachter-Zeh, A., Rosnes, E., & Amat, A. G. I. (2026) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2026.3655592 · Cited by 19
“Index Terms —Concatenated codes, DNA storage, DNA storage dataset, error-correcting codes, nanopore sequencing, sampling channel.”
Bee Identification Problem for DNA Strands
Chrisnata, J., Kiah, H. M., Vardy, A., & Yaakobi, E. (2023) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2023.3294423 · Cited by 4
“Families of such codes are constructed in [24], [25], [26], while fundamental limits of such channels are studied in [8], [27], [28], [29], [30].”
BackgroundMatrix Recovery from Permutations: An Algebraic Geometry Approach
Tsakiris, M. C. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206879 · Cited by 4
Information Theory of Mixed Population Genome-Wide Association Studies
Tahmasebi, B., Maddah-Ali, M. A., & Motahari, S. A. (2018) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2018.8613344 · Cited by 4
“Recently, many problems dealing with the DNA sequencing have been studied from information theoretic views [8]–[12].”
BackgroundOn the Capacity of DNA-based Data Storage under Substitution Errors
Lenz, A., Siegel, P. H., Wachter-Zeh, A., & Yaakobi, E. (2021) · IEEE International Conference on Visual Communications and Image Processing (VCIP) · doi:10.1109/vcip53242.2021.9675410 · Cited by 4
“Note that in comparison to [15] we additionally incorporate the error probability into the system design.”
BackgroundResultInfluentialPermutation Sum-Capacity of Binary Adder Multiple-Access Channels
Lu, W., & Makur, A. (2023) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit54713.2023.10206781 · Cited by 3
“Implementations of such systems store data in relatively short DNA molecules as strings of a few hundred nucleotides [19].”
BackgroundWhat is the resource footprint of a computer science department? Place, people, and Pedagogy
Mian, S. I., Twisleton, D., & Timm, D. (2020) · Data & Policy · doi:10.1017/dap.2020.12 · Cited by 4
“…as an attractive medium for archival storage of digital information (Neiman, 1964; Baum, 1995; Bancroft et al., 2001; Yachie et al., 2008; Extance, 2016; Bornholt et al., 2017; Heckel et al., 2017; de Groot, 2018; Ho, 2018; Lenz et al., 2020; Lima, 2018; Stefano et al., 2018; Tavella et al., 2018).”
BackgroundNeural Polar Decoders for DNA Data Storage
Aharoni, Z., & Pfister, H. D. (2025) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2025.3610751 · Cited by 8
“The DNA storage pipeline [5], [11], [12], [13], [14], [15] typically encodes digital data into multiple short sequences over a 4-ary alphabet, which are synthesized and stored in an unordered pool.”
How to Enable Index Scheme for Reducing the Writing Cost of DNA Storage on Insertion and Deletion
Lin, Y., Liang, Y.-P., Chen, T., Chang, Y.-H., Chen, S.-H., Wei, H., & Shih, W. (2022) · ACM Transactions on Embedded Computing Systems · doi:10.1145/3516482 · Cited by 4
DNA Storage Toolkit: A Modular End-to-End DNA Data Storage Codec and Simulator
Sharma, P., Goh, G. Y., Gao, B., Ou, L., Lin, D., Sharma, D., & Jevdjic, D. (2024) · IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass61541.2024.00023 · Cited by 6
“The indices preserve the order of all molecules within the file they constitute and ensure that every molecule contains the necessary information for reconstructing the original data from its constituent parts [5], [15], [23], [25].”
BackgroundNew Upper Bounds for Noisy Permutation Channels
Feng, L., Wang, B., Lv, G., Li, X., Wang, L., & Jin, Y. (2025) · IEEE Transactions on Communications · doi:10.1109/tcomm.2025.3549500 · Cited by 2
“Furthermore, we note that the code lengths of suitable code in such systems are in the order of thousands or hundreds [3], [8], invalidating the asymptotic assumptions in classical information theory.”
Sequence analysis and decoding with extra low-quality reads for DNA data storage
Park, J., Jeon, H. H., Lee, J. W., & Park, H. (2025) · Bioinformatics · doi:10.1093/bioinformatics/btaf335 · Cited by 2
A Converse For the Capacity of the Shotgun Sequencing Channel with Erasures
Ali, M. I., Narayanan, H., & Krishnan, P. (2025) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw62417.2025.11240437 · Cited by 2
“For instance, [8]–[11] analyze the capacity in the regime where the reads are non-overlapping.”
Near Optimal Code Construction for the Adversarial Torn Paper Channel with Edit Errors
Abu-Sini, M., & Heckel, R. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195439 · Cited by 1
“Further similar channels, such as shotgun sequencing and chop and shuffle, were studied in [5], [10], [11], [17], [26], [27], [32]–[36], [43], [45], [46] as well.”
Self-citationOn Machine Learning Methods for Genome Enabled Prediction of Complex Phenotypes
Elenter, J., Etchebarne, G., & Hounie, I. (2020) · IEEE Congreso Bienal de Argentina (ARGENCON) · doi:10.1109/argencon49523.2020.9505410 · Cited by 1
Portable and Error-Free DNA-Based Data Storage
Chauhan, D., Saxena, A. K., & Sharma, S. B. (2021) · International Conference on Recent Developments in Control, Automation & Power Engineering (RDCAPE) · doi:10.1109/rdcape52977.2021.9633694 · Cited by 1
Capacity of the Shotgun Sequencing Channel
Ravi, A. N., Vahid, A., & Shomorony, I. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834409 · Cited by 3
Self-citationExact Error Exponents of Concatenated Codes for DNA Storage
Ling, Y. H., & Scarlett, J. (2025) · IEEE Transactions on Information Theory · doi:10.1109/tit.2025.3581559 · Cited by 1
New Channel Coding Lower Bounds for Noisy Permutation Channels
Feng, L., Li, X., Lv, G., & Jin, Y. (2025) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit63088.2025.11195465
“The code lengths of suitable code in such systems are in the order of thousands or hundreds [4], [5], invalidating the asymptotic assumptions in classical information theory.”
The Capacity of Associated Subsequence Retrieval
Tahmasebi, B., Maddah-Ali, M. A., & Motahari, S. A. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2020.3035032 · Cited by 1
“Also, a number of authors considered the DNA storage systems, and studied the capacity and coding designs for them in several scenarios [27]–[33].”
BackgroundA Superior “Thumb” Drive: Optimizing DNA Stability for DNA Data StoragePreprint
Liu, J.-Y. (2023) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2023.05.11.540302 · Cited by 1
Error Exponent Bounds for the Bee-Identification ProblemPreprint
Tandon, A., Tan, V. Y. F., & Varshney, L. R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.07868
“The storage capacity results in [4] were extended to noisy settings in [5] where the channel adds noise and randomly permutes the m DNA molecules used to store information.”
BackgroundInformation-theoretic problems of DNA-based storage systems
Kruglik, S., Kucherov, G., Nazirkhanova, K., & Filitov, M. (2021) · Информационно-управляющие системы · doi:10.31799/1684-8853-2021-3-39-52
Metadata
- Authors
- Heckel, R., Shomorony, I., Ramchandran, K., & Tse, D. N. C.
- Affiliations
- University of California, Berkeley (US)
- Stanford University (US)
- Venue
- 2017 IEEE International Symposium on Information Theory (ISIT)
- Publisher
- IEEE
- Published
- 2017-06
- Pages
- 3130-3134
- OpenAlex
- W2615068531
- Semantic Scholar
- cf0d56fc56021a46bbea4fefcb4fbdc27bfc0baf
- Cited by
- 123
- References
- 12
- Citations by year
- 2026: 4 · 2025: 17 · 2024: 11 · 2023: 16 · 2022: 15 · 2021: 19 · 2020: 17 · 2019: 17 · 2018: 5 · 2017: 2
- FWCI
- 41.67
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE International Symposium on Information Theory (ISIT) (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › DNA and Biological Computing
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Data Storage Technologies
- Keywords
- DNA data storage, fundamental limits, storage capacity, random sampling, archival storage, information density
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.