Background:

DNA data storage has emerged as a compelling medium for archival data, offering extraordinary density and durability. In practice, data is encoded into millions of short synthetic DNA strands stored in a liquid container. When retrieved, the strands are read by nanopore sequencers in random order and a random number of times, and are corrupted by substitution and deletion errors. Weinberger and Merhav [4] formally characterized the capacity of this channel, accounting for the Poisson-distributed read counts and the permutation of strands.

The classical approach to protect data in this setting is a concatenation scheme: a per-strand inner code handles sequence errors, and an outer Reed–Solomon code handles strand-level erasures. A fundamental limitation of this approach is that current DNA synthesis technology restricts strand lengths to roughly 200–300 nucleotides—a regime in which inner codes suffer a significant finite-block-length rate penalty.

Modern Relevance:

Wang and Guruswami [1] proposed Geno-Weaving to overcome this bottleneck. Rather than coding along each strand, the key idea is to code across strands: a single block code protects the same nucleotide position across all strands simultaneously. Since the number of strands (millions) is orders of magnitude larger than the strand length, this orthogonal direction provides a vastly larger effective block length, eliminating the finite-length penalty. The scheme uses polar codes and provably achieves the capacity of the DNA storage channel. Lin, Wang, and Guruswami [2] extended this framework to deletion errors, demonstrating—theoretically and through simulations—that a Geno-Weaving design for substitution channels already performs well on deletion channels at realistic rates of 0.1%–10%, outperforming even optimal concatenation schemes.

Seminar Focus:

This seminar explores the Geno-Weaving framework and its extension to deletion errors. The goal is to develop a deep understanding of the channel model, the capacity-achieving code construction, and the block-length advantage over concatenation. The student will work through the encoding and decoding procedures in detail, develop illustrative examples, and carry out a quantitative comparison of Geno-Weaving's code rates against those of concatenation schemes for different deletion probabilities.

Expected Outcomes:

- Channel Model & Capacity: A clear explanation of the DNA storage channel, including Poissonization and the three challenge factors (noise, permutation, and sampling), with worked examples.

- Code Construction: Step-by-step illustrations of the Geno-Weaving encoding and decoding, including the push/pull synchronization mechanism for deletion errors.

- Rate Comparison: Plots comparing Geno-Weaving's achievable rates against concatenation schemes across a range of deletion probabilities, with a discussion of the block-length gain.

References:

[1] H.-P. Wang and V. Guruswami, "Geno-Weaving: A Framework for Low-Complexity Capacity-Achieving DNA Data Storage," *IEEE Journal on Selected Areas in Information Theory*, vol. 6, pp. 383–393, 2025, doi: [10.1109/JSAIT.2025.3610643](https://doi.org/10.1109/JSAIT.2025.3610643).

[2] Y.-T. Lin, H.-P. Wang, and V. Guruswami, "Block Length Gain for Nanopore Channels," *arXiv preprint arXiv:2511.18027*, Nov. 2025.

[3] L. Organick, S. D. Ang, Y.-J. Chen, R. Lopez, S. Yekhanin, K. Makarychev, et al., "Random Access in Large-Scale DNA Data Storage," *Nature Biotechnology*, vol. 36, no. 3, pp. 242–248, Mar. 2018, doi: [10.1038/nbt.4079](https://doi.org/10.1038/nbt.4079).

[4] N. Weinberger and N. Merhav, "The DNA Storage Channel: Capacity and Error Probability Bounds," *IEEE Transactions on Information Theory*, vol. 68, no. 9, pp. 5657–5700, Sep. 2022, doi: [10.1109/TIT.2022.3176371](https://doi.org/10.1109/TIT.2022.3176371).

Prerequisites

DNA Data Storage

Data storage on DNA molecules is a promising approach for archiving massive data.

In classical DNA storage systems, binary information is encoded into sequences consisting of the four DNA bases {A, C, G, T}. The encoded sequences are used to generate DNA molecules called strands using the biochemical process of DNA synthesis. The synthesized strands are stored together in a tube. To retrieve the binary information, the strand must be read via DNA sequencing and decoded back into the binary representation.

The synthesis and the sequencing procedures are error-prone, and with the natural degradation of DNA they introduce errors to the DNA strands. To ensure data reliability, the errors have to be corrected by algorithms and error-correcting codes (ECCs).

A 5min video with an overview of DNA storage: https://youtu.be/r8qWc9X4f6k?si=Yzm5sOW-a6VDnBu3

Composite DNA

Recently, to allow higher potential information capacity, [1,2] introduced the DNA composite synthesis method. In this method, the multiple copies created by the standard DNA synthesis method are utilized to create composite DNA symbols, defined by a mixture of DNA bases and their ratios in a specific position of the strands. By defining different mixtures and ratios, the alphabet can be extended to have more than 4 symbols. More formally, a composite DNA symbol in a specific position can be abstracted as a quartet of probabilities {p_A, p_C, p_G, p_T}, in which p_X, 0 ≤ p_X ≤ 1, is the fraction of the base X in {A, C, G, T} in the mixture and p_A+p_C+ p_G+ p_T =1. Thus, to identify composite symbols it is required to sequence multiple reads and then to estimate p_A, p_C, p_G, p_T in each position.

Problem description

ECCs for DNA data storage differ in many aspects from classical error correction codes. In this model, new error type gain relevance, like deletions and insertions which affect the synchronization of the sequences. Especially for composite DNA data storage, these error types received only little attention.

The most related work to this problem was recently studied by Zhang et al. in [6]. The authors initiated the study of error-correcting codes for DNA composite. They considered an error model for composite symbols, which assumes that errors occur in at most t symbols, and their magnitude is limited by l. They presented several code constructions as well as bounds for this model. In this thesis, we want to analyse a different way to model the composite synthesis method and studies additional error models. We already have some results for substitution and single deletion errors. This thesis should focus on evaluating more error models in the channel model. 

This should only roughly introduce the problem. No need to review all references. If you are interested, please reach out to me, and we can discuss a suitable direction for you.

References

[1] L. Anavy, I. Vaknin, O. Atar, R. Amit, and Z. Yakhini, “Data storage in DNA with fewer synthesis cycles using composite DNA letters,” Nat Biotechnol, vol. 37, no. 10, pp. 1229–1236, Oct. 2019, doi: 10.1038/s41587-019-0240-x.

[2] Y. Choi et al., “High information capacity DNA-based data storage with augmented encoding characters using degenerate bases,” Sci Rep, vol. 9, no. 1, Art. no. 1, Apr. 2019, doi: 10.1038/s41598-019-43105-w.

[3] V. Guruswami and J. Håstad, “Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound,” IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384–6394, Oct. 2021, doi: 10.1109/TIT.2021.3069446.

[4] J. Sima, N. Raviv, and J. Bruck, “Two Deletion Correcting Codes From Indicator Vectors,” IEEE Trans. Inform. Theory, vol. 66, no. 4, pp. 2375–2391, Apr. 2020, doi: 10.1109/TIT.2019.2950290.

[5] I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, “Single-Deletion Single-Substitution Correcting Codes,” IEEE Transactions on Information Theory, pp. 1–1, 2023, doi: 10.1109/TIT.2023.3319088.

[6] W. Zhang, Z. Chen, and Z. Wang, “Limited-Magnitude Error Correction for Probability Vectors in DNA Storage,” in ICC 2022 - IEEE International Conference on Communications, Seoul, Korea, Republic of: IEEE, May 2022, pp. 3460–3465. doi: 10.1109/ICC45855.2022.9838471.

Prerequisites

DNA Data Storage

Data storage on DNA molecules is a promising approach for archiving massive data.

In classical DNA storage systems, binary information is encoded into sequences consisting of the four DNA bases {A, C, G, T}. The encoded sequences are used to generate DNA molecules called strands using the biochemical process of DNA synthesis. The synthesized strands are stored together in a tube. To retrieve the binary information, the strand must be read via DNA sequencing and decoded back into the binary representation.

The synthesis and the sequencing procedures are error-prone, and with the natural degradation of DNA they introduce errors to the DNA strands. To ensure data reliability, the errors have to be corrected by algorithms and error-correcting codes (ECCs).

A 5min video with an overview of DNA storage: https://youtu.be/r8qWc9X4f6k?si=Yzm5sOW-a6VDnBu3

Composite DNA

Recently, to allow higher potential information capacity, [1,2] introduced the DNA composite synthesis method. In this method, the multiple copies created by the standard DNA synthesis method are utilized to create composite DNA symbols, defined by a mixture of DNA bases and their ratios in a specific position of the strands. By defining different mixtures and ratios, the alphabet can be extended to have more than 4 symbols. More formally, a composite DNA symbol in a specific position can be abstracted as a quartet of probabilities {p_A, p_C, p_G, p_T}, in which p_X, 0 ≤ p_X ≤ 1, is the fraction of the base X in {A, C, G, T} in the mixture and p_A+p_C+ p_G+ p_T =1. Thus, to identify composite symbols it is required to sequence multiple reads and then to estimate p_A, p_C, p_G, p_T in each position.

Problem description

ECCs for DNA data storage differ in many aspects from classical error correction codes. In this model, new error type gain relevance, like deletions and insertions which affect the synchronization of the sequences. Especially for composite DNA data storage, these error types received only little attention.

The most related work to this problem was recently studied by Zhang et al. in [6]. The authors initiated the study of error-correcting codes for DNA composite. They considered an error model for composite symbols, which assumes that errors occur in at most t symbols, and their magnitude is limited by l. They presented several code constructions as well as bounds for this model. In this thesis, we want to analyse a different way to model the composite synthesis method and studies additional error models. We already have some results for substitution and single deletion errors. This thesis should focus on evaluating more error models in the channel model. 

This should only roughly introduce the problem. No need to review all references. If you are interested, please reach out to me, and we can discuss a suitable direction for you.

References

[1] L. Anavy, I. Vaknin, O. Atar, R. Amit, and Z. Yakhini, “Data storage in DNA with fewer synthesis cycles using composite DNA letters,” Nat Biotechnol, vol. 37, no. 10, pp. 1229–1236, Oct. 2019, doi: 10.1038/s41587-019-0240-x.

[2] Y. Choi et al., “High information capacity DNA-based data storage with augmented encoding characters using degenerate bases,” Sci Rep, vol. 9, no. 1, Art. no. 1, Apr. 2019, doi: 10.1038/s41598-019-43105-w.

[3] V. Guruswami and J. Håstad, “Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound,” IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384–6394, Oct. 2021, doi: 10.1109/TIT.2021.3069446.

[4] J. Sima, N. Raviv, and J. Bruck, “Two Deletion Correcting Codes From Indicator Vectors,” IEEE Trans. Inform. Theory, vol. 66, no. 4, pp. 2375–2391, Apr. 2020, doi: 10.1109/TIT.2019.2950290.

[5] I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, “Single-Deletion Single-Substitution Correcting Codes,” IEEE Transactions on Information Theory, pp. 1–1, 2023, doi: 10.1109/TIT.2023.3319088.

[6] W. Zhang, Z. Chen, and Z. Wang, “Limited-Magnitude Error Correction for Probability Vectors in DNA Storage,” in ICC 2022 - IEEE International Conference on Communications, Seoul, Korea, Republic of: IEEE, May 2022, pp. 3460–3465. doi: 10.1109/ICC45855.2022.9838471.

Prerequisites

DNA Data Storage

Data storage on DNA molecules is a promising approach for archiving massive data.

In classical DNA storage systems, binary information is encoded into sequences consisting of the four DNA bases {A, C, G, T}. The encoded sequences are used to generate DNA molecules called strands using the biochemical process of DNA synthesis. The synthesized strands are stored together in a tube. To retrieve the binary information, the strand must be read via DNA sequencing and decoded back into the binary representation.

The synthesis and the sequencing procedures are error-prone, and with the natural degradation of DNA they introduce errors to the DNA strands. To ensure data reliability, the errors have to be corrected by algorithms and error-correcting codes (ECCs).

A 5min video with an overview of DNA storage: https://youtu.be/r8qWc9X4f6k?si=Yzm5sOW-a6VDnBu3

Prerequisites

Overview:
Traditional error correction codes like LDPC (Low-Density Parity-Check) are highly effective for substitution noise but struggle when applied to deletion channels, where bits are removed and the sequence alignment is shifted. This project explores an experimental, graph-based decoding approach for handling such synchronization errors, inspired by methods in the references below.

You will design and simulate a novel decoder that tracks and corrects drift—the cumulative effect of deletions—by using a factor graph with locally connected variable nodes and drift constraints. A central idea is to model the decoding process as inference on this structured graph, leveraging probabilistic message passing.

What You'll Learn:

• How deletion errors affect classical coding theory

• Principles of LDPC codes and belief propagation

• Techniques for modeling time-varying constraints (drift) in a graphical setting

• Implementation of custom decoders and simulators in Python

References:

1. R. Shibata, G. Hosoya, and H. Yashima, “Design of Irregular LDPC Codes without Markers for Insertion/Deletion Channels,” IEEE GLOBECOM, 2019. doi: 

2. F. Wang, D. Fertonani, and T. M. Duman, “Symbol-Level Synchronization and LDPC Code Design for Insertion/Deletion Channels,” IEEE Trans. Commun., vol. 59, no. 5, 2011. doi: 

Prerequisites