The Coverage Depth Problem in Distributed DNA Data Storage
Abstract
Random sampling in DNA sequencing produces repeated reads, increasing retrieval latency and sequencing cost. We study the coverage-depth problem for full-message recovery in distributed DNA storage under noiseless uniform sampling, where strands are partitioned among M containers and one strand is independently sampled with replacement from each container per round. For arbitrary linear codes and ordered partitions, we derive exact formulas for the recovery-time distribution and expectation. We prove that MDS codes, whenever they exist, are optimal for every fixed partition, and establish a universal lower bound on the expected total read cost together with its equality conditions. For MDS codes, we identify container-size regimes that yield genuine savings in total reads and regimes that provide only parallelism without changing the asymptotic sequencing cost. For simplex codes, we prove that the q-ary simplex code is, up to isomorphism, the unique single-container minimizer among codes with the same parameters, resolving a recent conjecture by Bertuzzo, Ravagnani, and Yaakobi. We further construct a partition attaining the minimum total read cost and derive bounds for intermediate and balanced partitions. These results clarify when distributed sampling reduces latency alone and when it also reduces sequencing cost.
Related
- Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes
- Optimisation of distributed storage in existing district heating networks to solve hydraulic bottlenecks
- Latency-Optimal Geo-Distributed Storage over Structured Networks
- Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys
- Selection-Safe Conformal Early Exit: Distribution-Free Coverage under Adaptive Depth
BibTeX
@misc{kong2026coverage,
title = {{The Coverage Depth Problem in Distributed DNA Data Storage}},
author = {Xiangliang Kong and Ohad Elishco and Chen Wang and Tolga M. Duman},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02931},
eprint = {2610.02931},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02931},
}
RIS
TY - UNPB
TI - The Coverage Depth Problem in Distributed DNA Data Storage
AU - Xiangliang Kong
AU - Ohad Elishco
AU - Chen Wang
AU - Tolga M. Duman
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02931
UR - https://arxiv.org/abs/2610.02931
AB - Random sampling in DNA sequencing produces repeated reads, increasing retrieval latency and sequencing cost. We study the coverage-depth problem for full-message recovery in distributed DNA storage under noiseless uniform sampling, where strands are partitioned among M containers and one strand is independently sampled with replacement from each container per round. For arbitrary linear codes and ordered partitions, we derive exact formulas for the recovery-time distribution and expectation. We prove that MDS codes, whenever they exist, are optimal for every fixed partition, and establish a universal lower bound on the expected total read cost together with its equality conditions. For MDS codes, we identify container-size regimes that yield genuine savings in total reads and regimes that provide only parallelism without changing the asymptotic sequencing cost. For simplex codes, we prove that the q-ary simplex code is, up to isomorphism, the unique single-container minimizer among codes with the same parameters, resolving a recent conjecture by Bertuzzo, Ravagnani, and Yaakobi. We further construct a partition attaining the minimum total read cost and derive bounds for intermediate and balanced partitions. These results clarify when distributed sampling reduces latency alone and when it also reduces sequencing cost.
ER -