Making it to First: The Random Access Problem in DNA Storage
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912550486016000 |
|---|---|
| author | Boruchovsky, Avital Elishco, Ohad Gabrys, Ryan Gruica, Anina Tamo, Itzhak Yaakobi, Eitan |
| author_facet | Boruchovsky, Avital Elishco, Ohad Gabrys, Ryan Gruica, Anina Tamo, Itzhak Yaakobi, Eitan |
| contents | 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+\frac{2}{\sqrt{2}+1}\approx 0.914\cdot 2$ for $q$ large enough. Moreover, we generalize a construction from~\cite{GMZ24}, specifically to $k=3$, for any value of $k$. Our construction uses $B_{k-1}$ sequences over $\mathbb{Z}_{q-1}$, that always exist over large finite fields. We show that for every $k\geq 4$, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12274 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Making it to First: The Random Access Problem in DNA Storage Boruchovsky, Avital Elishco, Ohad Gabrys, Ryan Gruica, Anina Tamo, Itzhak Yaakobi, Eitan Information Theory 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+\frac{2}{\sqrt{2}+1}\approx 0.914\cdot 2$ for $q$ large enough. Moreover, we generalize a construction from~\cite{GMZ24}, specifically to $k=3$, for any value of $k$. Our construction uses $B_{k-1}$ sequences over $\mathbb{Z}_{q-1}$, that always exist over large finite fields. We show that for every $k\geq 4$, this generalized construction outperforms all previous constructions in terms of reducing the random access expectation. |
| title | Making it to First: The Random Access Problem in DNA Storage |
| topic | Information Theory |
| url | https://arxiv.org/abs/2501.12274 |