DNA is a promising data storing medium due to its longetivity and high storage density. However, due to its biological nature data errors can occur when storing or reading the DNA sequences. Moreover, not only substitution erros but also insertion and deletion errors occur frequently in the storage process. Therefore, it is important to tackle these kind of errors via coding. [1] presents methods how to correct combinations of prominent errors in DNA storage.

The student's task is to understand the coding theme and error models discussed in [1], including the proposed proof method.

For an introduction, the references [2] and [3] may help.

References:

• [1] R. Gabrys, V. Guruswami, J. Ribeiro, K. Wu, "Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions," arXiv preprint 2112.09971, URL: https://arxiv.org/abs/2112.09971, 2021.

• [2] N. J. A. Sloane, “On Single-Deletion-Correcting Codes,” 2002.

• [3] V. I. Levenshtein, “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals.” Soviet Physics-Doklady, Moscow, 1966.

DNA storage is an uprising topic in the research field of storage systems. Due its natural longetivity, robustness, and density properties the main application would arise in high-dense long-term storage systems. The interest has become larger and larger due the large amount of data nowadays and the relative new biological advances in DNA synthesis and sequencing processes (e.g. polymerase chain reaction). In contrary to conventional storing methods, due to the nature of DNA and the involved biological processes special error patterns such as insertion, deletion, and substitution errors occur. To tackle these errors novel methods for correction have to be investigated. Moreover, the model of the DNA storage channel needs to be investigated thorougly, e.g. capacity statements.

• Linear Algebra
• Channel Coding
• Coding Theory for Storage and Networks (optional)

This work deals with the constuction and decoding of polar codes for the insertion, deletion, and substitution channel.