Codes in the Damerau Distance for DNA Storage

Ryan Gabrys, Olgica Milenkovic, Eitan Yaakobi

Publication date: 25 January 2016

Abstract: 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.

This page was built for publication: Codes in the Damerau Distance for DNA Storage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6269747)