Optimal coding strategies reduce dna data recovery reads
Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes
Information Theory
Summary
DNA storage uses many copies of tiny DNA pieces to store information, and reading enough pieces to fully recover data is a key challenge. The authors study how to design codes that minimize the average number of pieces you need to read to retrieve all the information. They show some special known codes work best for certain cases and analyze how random codes perform compared to these best codes. This helps improve how quickly and efficiently DNA data can be recovered without reading excessive amounts of DNA.
What this means in practice
- •For dna storage engineers: Design DNA synthesis and sequencing protocols that minimize the number of reads needed to reliably decode stored data by selecting optimal linear codes.
- •For error correcting code developers: Improve coding schemes in communications by understanding code designs that minimize expected samples to fully decode information in random sampling settings.
A theory result. No direct application yet.
Authors
Roee Gross, Yitzchak Grunbaum, Matteo Bertuzzo, Eitan Yaakobi, Alberto Ravagnani
Abstract
DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the $q$-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the $q$-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.