Codes in the Damerau Distance for Deletion and Adjacent Transposition Correction

Ryan Gabrys, Eitan Yaakobi, Olgica Milenkovic

Research output: Contribution to journalArticle

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.11Parts of the results were presented at the International Symposium on Information Theory in Barcelona, 2016.

Original languageEnglish (US)
Pages (from-to)2550-2570
Number of pages21
JournalIEEE Transactions on Information Theory
Volume64
Issue number4
DOIs
StatePublished - Apr 2018

Keywords

  • DNA storage
  • Damerau distance
  • codes for deletions

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Codes in the Damerau Distance for Deletion and Adjacent Transposition Correction'. Together they form a unique fingerprint.

  • Cite this