• Diese Seite als PDF öffnen.

Analysis of Criss-Cross Deletion in Arrays

Description

yle="font-weight: normal;" lang="de-DE" align="left">In this project we study two dimensional deletion/insertion problem introduced in https://arxiv.org/pdf/2004.14740.pdf. An array of n rows and n columns is transmitted through a specific deletion channel which for example occurs in DNA storage systems and racetrack memories. After transmission the receiver observes an array of dimension (n-1)*(n-1). The goal is to allow the receiver to know exactly which n*n array was transmitted by using error-correction techniques.

The goal of the project is to derive bounds on the deletion ball of any two-dimensional array. A deletion ball of an array X is the set of unique arrays resulting from the deletion of any possible combination of a column and a row in X. Deriving such bounds is not trivial since it depends heavily on the structure of the array. Thus, it is important to investigate useful characteristics representing the structure of an array for this particular setting. Furthermore, having this bound will be helpful to characterize the optimal redundancy of a deletion-correcting code for this setting.

Supervisor:

• Diese Seite als PDF öffnen.

Error Correction in DNA Storage

Keywords:
DNA storage, Error Correction, Deletion, Insertion, Substitutions

Description

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.

Prerequisites

Supervisor:

• Diese Seite als PDF öffnen.

Construction of single-deletion-correcting DNA codes using CIS codes

Description

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] studies a method to uniquely correct one single-deletion in a DNA sequence. Moreover, it proposes methods to incorporate biologic constraints which have to be considered in the practical storage process.

The student's task is to understand the coding theme used in [1], including the proposed decoding method. Further, the design methods to tackle the biological constraints have to be well understood.

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

[1] Choi, WH., Kim, H.J. & Lee, Y. Construction of single-deletion-correcting DNA codes using CIS codes. Des. Codes Cryptogr. 88, 2581–2596 (2020). https://doi.org/10.1007/s10623-020-00802-2

yle="margin-left: 32pt; text-indent: -32.0pt;">[2] N. J. A. Sloane, “On Single-Deletion-Correcting Codes,” 2002.

yle="margin-left: 32pt; text-indent: -32.0pt;">[3]V. I. Levenshtein, “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals.” Soviet Physics-Doklady, Moscow, 1966.

Supervisor: