Making it to First: The Random Access Problem in DNA Storage

In this paper, 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. In this framework, the data is represented by k information strands which represent the data and are encoded into n strands using a linear code. Then, each sequencing read returns one encoded strand which is chosen uniformly at random. The goal under this paradigm is to design codes that minimize the expected number of reads required to recover an arbitrary information strand. We fully solve the case when k = 2, showing that the best possible code attains a random access expectation of 1 + 2/√2+1 ≈ 0.914 · 2 for q large enough. Moreover, we extend a previous construction, originally developed for k = 3, to arbitrary values of k. Our construction uses B_k−1 sequences over Z_q−1, that always exist over large finite fields. We show that for every k ≥ 4, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation.