A Caltech Library Service

Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms

Jain, Siddharth and Farnoud (Hassanzadeh), Farzad and Schwartz, Moshe and Bruck, Jehoshua (2017) Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms. IEEE Transactions on Information Theory, 63 (8). pp. 4996-5010. ISSN 0018-9448. doi:10.1109/TIT.2017.2688361.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The ability to store data in the DNA of a living organism has applications in a variety of areas including synthetic biology and watermarking of patented genetically-modified organisms. Data stored in this medium is subject to errors arising from various mutations, such as point mutations, indels, and tandem duplication, which need to be corrected to maintain data integrity. In this paper, we provide error-correcting codes for errors caused by tandem duplications, which create a copy of a block of the sequence and insert it in a tandem manner, i.e., next to the original. In particular, we present two families of codes for correcting errors due to tandem duplications of a fixed length; the first family can correct any number of errors while the second corrects a bounded number of errors. We also study codes for correcting tandem duplications of length up to a given constant k , where we are primarily focused on the cases of k=2,3 . Finally, we provide a full classification of the sets of lengths allowed in tandem duplication that result in a unique root for all sequences.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemTechnical Report Paper
Jain, Siddharth0000-0002-9164-6119
Farnoud (Hassanzadeh), Farzad0000-0002-8684-4487
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2017 IEEE. Manuscript received June 1, 2016; revised December 9, 2016; accepted March 13, 2017. Date of publication March 28, 2017; date of current version July 12, 2017. This work was supported by the NSF Expeditions in Computing Program (The Molecular Programming Project). This paper was presented at the 2016 IEEE International Symposium on Information Theory.
Funding AgencyGrant Number
Subject Keywords:Error-correcting codes, DNA, string-duplication systems, tandem-duplication errors
Issue or Number:8
Record Number:CaltechAUTHORS:20170330-092251690
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:75539
Deposited By: Kristin Buxton
Deposited On:30 Mar 2017 19:24
Last Modified:15 Nov 2021 16:34

Repository Staff Only: item control page