R&D: Optimal Reverse-Complement-Duplication Error-Correcting Codes

arXiv has published an article written by Lev Yohananov, Department of ECE and Institute for Systems Research, University of Maryland, College, Park, MD 20742, USA, and Moshe Schwartz, School of Electrical and Computer Engineering, Ben-Gurion University of the Negev,Beer Sheva 8410501, Israel (on a leave of absence), and Department of Electrical and Computer Engineering, McMaster University, Hamilton,ON L8S 4K1, Canada.

Abstract: “Motivated by DNA storage in living organisms and inspired by biological mutation processes, this study explores the reverse-complement string-duplication system. We commence our investigation by introducing an optimal q-ary reverse-complement-duplication code construction for duplication length 1 and any number of duplications, achieving a size of Θ(qn). Subsequently, we establish a fundamental limitation, proving that for duplication lengths greater than 1, all reverse-complement-duplication codes correcting any number of duplications possess a size of o(qn). Further, we present a construction of reverse-complement-duplication codes with a duplication length of 2, demonstrating a redundancy of at most logq(n/2)+logq(logq(n)+1)+2+logq(3). Finally, we contribute an explicit construction for q-ary codes addressing a single classical tandem duplication for any k. The redundancy of these codes is logq(n/k)+1+(k−1)logq(logq(2n/k)+1).“