Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions, and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.11Parts of the results were presented at the International Symposium on Information Theory in Barcelona, 2016.
- DNA storage
- Damerau distance
- codes for deletions
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Library and Information Sciences