R&D: Permutation Recovery Problem vs. Deletion Errors for DNA Storage

arXiv has published an article written by Shubhransh Singhvi, Signal Processing & Communications Research Center, IIIT Hyderabad, India, Charchit Gupta, IIIT Hyderabad, India, Avital Boruchovsky, Yuval Goldberg, Department of Computer Science, Technion – Israel Institute of Technology, Haifa 3200003, Israel, Han Mao Kiah, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, and Eitan Yaakobi, Department of Computer Science, Technion – Israel Institute of Technology, Haifa 3200003, Israel.

Abstract: “Owing to its immense storage density and durability, DNA has emerged as a promising storage medium. However, due to technological constraints, data can only be written onto many short DNA molecules called data blocks that are stored in an unordered way. To handle the unordered nature of DNA data storage systems, a unique address is typically prepended to each data block to form a DNA strand. However, DNA storage systems are prone to errors and generate multiple noisy copies of each strand called DNA reads. Thus, we study the permutation recovery problem against deletions errors for DNA data storage.“
“The permutation recovery problem for DNA data storage requires one to reconstruct the addresses or in other words to uniquely identify the noisy reads. By successfully reconstructing the addresses, one can essentially determine the correct order of the data blocks, effectively solving the clustering problem.“
“We first show that we can almost surely identify all the noisy reads under certain mild assumptions. We then propose a permutation recovery procedure and analyze its complexity.“