R&D: Making it to First, Random Access Problem in DNA Storage

ArXiv has published an article written by Avital Boruchovsky, Technion – Israel Institute of Technology, Haifa, Israel, Ohad Elishco, Ben Gurion University of the Negev, Beer-Sheva, Israel, Ryan Gabrys, University of California, San Diego, USA, Anina Gruica, Technical University of Denmark, Lyngby, Denmark, Itzhak Tamo, Tel-Aviv University, Tel-Aviv, Israel, and Eitan Yaakobi, Technion – Israel Institute of Technology, Haifa, Israel.

Abstract: “We study the Random Access Problem in DNA storage, which addresses the challenge of retrieving a specific information strand from a DNA-based storage system. Given that k information strands, representing the data, are encoded into n strands using a code. The goal under this paradigm is to identify and analyze codes that minimize the expected number of reads required to retrieve any of the k information strand, while in each read one of the n encoded strands is read uniformly at random. We fully solve the case when k=2, showing that the best possible code attains a random access expectation of 0.914⋅2. Moreover, we generalize a construction from \cite{GMZ24}, specific to k=3, for any value of k. Our construction uses Bk−1 sequences over Zq−1, that always exist over large finite fields. For k=4, we show that this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.“