The presented work studies error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). A storage model is investigated where a data set is represented by an
unordered set of M sequences, each of length L. Errors within
that model are a loss of whole sequences and point errors inside
the sequences, such as insertions, deletions and substitutions.
Gilbert-Varshamov lower bounds and sphere packing
upper bounds on achievable cardinalities of error-correcting
codes are derived within this storage model. Further explicit code
constructions were proposed than can correct errors in such a storage system
that can be encoded and decoded efficiently. Comparing the sizes
of these codes to the upper bounds, it is shown that many of the
constructions are close to optimal.
The NVMWMemorable Paper Award is awarded annually to a student paper published in the last two years that is of exceptional quality and is expected to have a substantial impact on the fields of study related to non-volatile memories.
Full version of the paper: