The Error Probability of Maximum-Likelihood Decoding over Two Deletion/Insertion Channels
Abstract
This paper studies the problem of reconstructing a word given several of its noisy copies. This setup is motivated by several applications, among them is reconstructing strands in DNA-based storage systems. Under this paradigm, a word is transmitted over some fixed number of identical independent channels and the goal of the decoder is to output the transmitted word or some close approximation. The main focus of this paper is the case of two deletion channels and studying the error probability of the maximum-likelihood (ML) decoder under this setup. First, it is discussed how the ML decoder operates. Then, we observe that the dominant error patterns are deletions in the same run or errors resulting from alternating sequences. Based on these observations, it is derived that the error probability of the ML decoder is roughly (3q - 1)/(q - 1) p2, when the transmitted word is any q-ary sequence and p is the channel's deletion probability. We also study the cases when the transmitted word belongs to the Varshamov Tenengolts (VT) code or the shifted VT code. Lastly, the insertion channel is studied as well. These theoretical results are verified by corresponding simulations.
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 [96]
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 · see citing works
A linear space algorithm for computing maximal common subsequences
Hirschberg, D. S. (1975) · Communications of the ACM · doi:10.1145/360825.360861 · Cited by 1,110 · 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
Algorithms for the Longest Common Subsequence Problem
Hirschberg, D. S. (1977) · Journal of the ACM · doi:10.1145/322033.322044 · Cited by 752 · see citing works
A faster algorithm computing string edit distances
Masek, W. J., & Paterson, M. S. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90002-1 · Cited by 656 · see citing works
Portable 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
Matching Sequences under Deletion/Insertion Constraints
Sankoff, D. (1972) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.69.1.4 · Cited by 297 · see citing works
Data storage in DNA with fewer synthesis cycles using composite DNA letters.
Anavy, L., Vaknin, I., Atar, O., Amit, R., & Yakhini, Z. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0240-x · Cited by 229 · see citing works
Efficient reconstruction of sequences
Levenshtein, V. I. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.904499 · Cited by 212 · see citing works
Efficient Reconstruction of Sequences from Their Subsequences or Supersequences
Levenshtein, V. I. (2001) · Journal of Combinatorial Theory Series A · doi:10.1006/jcta.2000.3081 · Cited by 192 · 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-citationLinear approximation of shortest superstrings
Blum, A. L., Jiang, T., Li, M., Tromp, J., & Yannakakis, M. (1994) · Journal of the ACM · doi:10.1145/179812.179818 · Cited by 140 · 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
Chee, 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-citationComputing a longest common subsequence for a set of strings
Hsu, W.-C., & Du, M. (1984) · BIT Numerical Mathematics · doi:10.1007/bf01934514 · Cited by 91 · see citing works
Trace 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
A fast parallel algorithm for finding the longest common sequence of multiple biosequences
Chen, Y., Wan, A., & Liu, W. (2006) · BMC Bioinformatics · doi:10.1186/1471-2105-7-s4-s4 · Cited by 82 · see citing works
Algorithms for subsequence combinatorics
Elzinga, C. H., Rahmann, S., & Wang, H. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.08.035 · Cited by 79 · see citing works
Fast linear-space computations of longest common subsequences
Apostolico, A., Browne, S. V., & Guerra, C. F. (1992) · Theoretical Computer Science · doi:10.1016/0304-3975(92)90132-y · Cited by 60 · 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
A linear-time algorithm for finding approximate shortest common superstrings
Ukkonen, E. (1990) · Algorithmica · doi:10.1007/bf01840391 · Cited by 55 · 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-citationSubpolynomial 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 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
Itoga, S. Y. (1981) · BIT Numerical Mathematics · doi:10.1007/bf01934067 · Cited by 41 · see citing works
Error 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
Reconstruction of a graph from 2-vicinities of its vertices
Levenshtein, V. I., Konstantinova, E. V., Konstantinov, E. S., & Molodtsov, S. G. (2007) · Discrete Applied Mathematics · doi:10.1016/j.dam.2006.11.016 · Cited by 38 · see citing works
Sequence reconstruction for Grassmann graphs and permutations
Yaakobi, E., Schwartz, M., Langberg, M., & Bruck, J. (2013) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2013.6620351 · Cited by 34 · see citing works
Self-citationOn the uncertainty of information retrieval in associative memories
Yaakobi, E., & Bruck, J. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6283016 · Cited by 33 · see citing works
Self-citationCoding 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
On the Theory and Practice of Data Recovery with Multiple Versions
Mitzenmacher, M. (2006) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2006.261874 · Cited by 24 · see citing works
Coding 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-citationThree novel combinatorial theorems for the insertion/deletion channel
Sala, F., Gabrys, R., Schoeny, C., & Dolecek, L. (2015) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2015.7282947 · Cited by 15 · 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
From Clustering Supersequences to Entropy Minimizing Subsequences for Single and Double DeletionsPreprint
Atashpendar, A., Beunardeau, M., Connolly, A., Géraud, R., Mestel, D., Roscoe, A. W., & Ryan, P. Y. A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.00703 · Cited by 10 · see citing works
Problems related to subsequences and supersequences
Tronı́ček, Z. (2003) · doi:10.1109/spire.1999.796596 · Cited by 6 · see citing works
Maximal common subsequences and minimal common supersequences
Irving, R. W., & Fraser, C. B. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58094-8_16 · Cited by 5 · see citing works
Fundamental Bounds and Approaches to Sequence Reconstruction from Nanopore SequencersPreprint
Duda, J., Szpankowski, W., & Grama, A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.02420 · Cited by 4 · see citing works
Tutorial on algebraic deletion correction codesPreprint
Tatwawadi, K., & Chandak, S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.07887 · Cited by 3 · see citing works
Flagged first, then by citations
3 of the 45 references couldn’t be matched to a known paper.
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
Reconstruction algorithms for DNA-storage systems
Sabary, O., Yucovich, A., Shapira, G., & Yaakobi, E. (2024) · Scientific Reports · doi:10.1038/s41598-024-51730-3 · Cited by 50 · 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
Reconstruction Algorithms for DNA-Storage SystemsPreprint
Sabary, O., Yucovich, A., Shapira, G., & Yaakobi, E. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.09.16.300186 · Cited by 18 · see citing works
Self-citationApproximate Trace Reconstruction: Algorithms
Davies, S., Rácz, M. Z., Schiffer, B., & Rashtchian, C. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517926 · Cited by 16 · see citing works
Decoding for Optimal Expected Normalized Distance over the t-Deletion Channel
Bar-Lev, D., Gershon, Y., Sabary, O., & Yaakobi, E. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517773 · Cited by 6 · see citing works
Self-citationSequence Design and Reconstruction Under the Repeat Channel in Enzymatic DNA Synthesis
Shafir, R., Sabary, O., Anavy, L., Yaakobi, E., & Zohar Yakhini, B. (2023) · IEEE Transactions on Communications · doi:10.1109/tcomm.2023.3330848 · Cited by 5 · see citing works
Self-citationOn Levenshtein’s Reconstruction Problem for Channels with Unique Insertion Error Patterns
Junnila, V., Laihonen, T. K., Lehtilä, T., & Devaraj, P. (2025) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw62417.2025.11240278 · Cited by 1 · see citing works
The Intersection of Insertion and Deletion Balls
Bar-Lev, D., Sabary, O., Gershon, Y., & Yaakobi, E. (2021) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw48936.2021.9611515 · Cited by 1 · see citing works
Self-citationJunnila, V., Laihonen, T. K., Lehtilä, T., & Devaraj, P. P. (2026) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit62367.2026.11653882
- Authors
- Sabary, O., Yaakobi, E., & Yucovich, A.
- Affiliations
- Technion – Israel Institute of Technology (IL)
- Venue
- 2020 IEEE International Symposium on Information Theory (ISIT)
- Publisher
- IEEE
- Published
- 2020-06
- Pages
- 763-768
- OpenAlex
- W3081211058
- Cited by
- 10
- References
- 45
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 1 · 2023: 1 · 2022: 1 · 2021: 3 · 2020: 2
- FWCI
- 1.47
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE International Symposium on Information Theory (ISIT) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- maximum likelihood decoding, deletion channel, error probability, error patterns
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
