CS Paper Radar

Weak arcs and applications to the DNA-based storage access problem

Geertrui Van de Voorde, Ferdinando Zullo

cs.IT math.CO ·submitted 2026-08-20 01:32 UTC · v1
theory

Abstract

Weak arcs are point sets in PG$(n-1,q)$ meeting every general hyperplane (those are the hyperplanes not going through one of the points given by the standard basis vectors) in at most $n-1$ points. In this paper, we study weak arcs together with balanced variants which are contained on the sides of the fundamental simplex. We give an upper bound on the size of weak arcs, characterise the largest balanced quasi-arcs in the plane and construct large balanced quasi-arcs in PG$(3, q)$. We then use these configurations to build point sets for the random-access problem in DNA-based storage. The constructions are explicit, work over small fields, and attain recovery expectations matching the best known asymptotic bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

The Coverage Depth Problem in Distributed DNA Data Storage

cs.IT math.CO ·2026-10-02 ·Xiangliang Kong, Ohad Elishco, Chen Wang, Tolga M. Duman
theory similarity 0.63
Abstract · 33 pages, 2 figures

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.

0.49

A Hyperbolic Bound for File Retrieval in DNA-Based Data Storage

cs.IT math.CO ·2026-09-28 ·Constantinos Vasilios Argyris Vlachos, Daniella Bar-Lev
theory similarity 0.61
Abstract

In DNA-based storage systems, data are retrieved by sequencing molecules sampled from a DNA pool. We study how the way coding redundancy is shared between files affects their expected retrieval times. Our focus lies on the case of two files that are encoded by a systematic linear code over an arbitrary finite field. We consider the conjecture that the sum obtained by dividing each file dimension by its expected retrieval time is at most one whenever the dimension of at least one file is more than one. For this, we develop a geometric view of the retrieval process. As molecules are sampled, we follow the growing span of the corresponding columns of the generator matrix and track how much of this span comes from each file. Among the samples that enlarge the overall span, this lets us compare those that make progress toward recovering both files with those that make progress toward neither. We call a column mixed if the corresponding encoded symbol combines information from both files. In this work, we sharpen a projection bound and use it to control the effect of mixed columns. We prove the conjecture whenever the total information dimension is at least twice the number of mixed columns plus two. For equal-sized files, this allows up to one fewer mixed column than the dimension of either file and extends the previous result for codes with no mixed columns.

0.40

Optimal Codes for the Coverage Depth Problem and the Performance of Random Codes

cs.IT ·2026-10-05 ·Roee Gross, Yitzchak Grunbaum, Matteo Bertuzzo, Eitan Yaakobi, Alberto Ravagnani
benchmarkhot direction similarity 0.61
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.

0.44

The Generalized Random Access Problem for Linear Codes

cs.IT math.CO ·2026-08-20 ·Anina Gruica, Antonio Petrillo, Ferdinando Zullo
hot direction similarity 0.61
Abstract

Random access is a central requirement in DNA-based storage systems: one would like to recover selected information symbols without sequencing the whole encoded object. A recent combinatorial model associates to a generator matrix $G\in F_q^{k\times n}$ the random variable $τ_i(G)$, measuring the number of sampled columns needed to recover the information vector $e_i$. We study the cardinality-based extremal and finite-geometric aspects of simultaneous multi-symbol recovery. For a nonempty set $I\subseteq[k]$, let $τ_I(G)$ denote the number of random column samples needed until all vectors $e_i$, $i\in I$, lie in the span of the observed columns. This variable interpolates between the singleton random access problem and the full-recovery problem underlying coverage depth. For each $m$, we introduce uniform worst-case and average parameters over all requested sets $I$ with $|I|=m$. Using the known subset-counting formula for $E[τ_I(G)]$, we establish general upper and lower bounds for these parameters. In particular, the lower bounds are expressed through order statistics of the singleton recovery variables and specialize to the known singleton bounds when $m=1$. For systematic MDS encoders, we record an equivalent form of the known multi-symbol expectation formula and derive monotonicity and asymptotic consequences. For simplex encoders in arbitrary dimension, we obtain closed formulae in terms of Gaussian binomial coefficients; the full-recovery endpoint agrees with the known coverage-depth formula for simplex codes. Finally, in dimension three we study balanced quasi-arcs and compare their values with the simplex and MDS benchmarks.

0.49

Hardness, Approximation, and Parameterized Algorithms for Asynchronous Border Minimization

cs.DS ·2026-11-12 ·Giulian Buzatu, Adrian Miclăuş, Alexandru Popa
theory similarity 0.60
Abstract

In the Asynchronous Border Minimization Problem (BMP), a set of DNA probe strings is placed on a grid and synthesized using a common sequence of nucleotide-deposition steps. At each step, every cell may accept or skip the offered nucleotide. The cost is the total number of disagreements between neighboring cells over all steps. We study both free placement, where the probes may be rearranged, and fixed placement, where their positions are given. We show that free-placement BMP on a square grid is NP-complete over three symbols. For one-dimensional BMP, we prove APX-hardness over a binary alphabet, and NP-completeness even when every probe has length two. We also obtain an $8/7$-approximation for the latter restriction. For square grids, we give a randomized $O(n^{1/4}\log n)$-approximation, improving the earlier $O(n^{1/4}\log^2 n)$ guarantee. Both free- and fixed-placement BMP on rectangular grids are fixed-parameter tractable when parameterized only by the allowed border cost.

0.25

Source Assignment: Hardness, Approximation, and Parameterized Algorithms

cs.DS ·2026-11-10 ·Ruxandra Marinescu-Ghemeci, Adrian Miclăuş, Alexandru Popa
hot direction similarity 0.58
Abstract

In Source Assignment, each pointer represents a substring of a common reference string and may have several possible source occurrences. The goal is to choose one source for each pointer while minimizing the number of distinct reference boundaries used by the selected sources. The problem was introduced by Qiu and Kingsford (Bioinformatics 2021) in the context of compact genome-graph construction. We distinguish \emph{Explicit Source Assignment}, where admissible source sets are given explicitly, from \emph{Complete Source Assignment}, where all occurrences of each pointer string are available. We show that Explicit Source Assignment has an exact value-preserving formulation as cardinality Set Cover with Pairs. For every fixed $\varepsilon>0$, it cannot be approximated within $(1-\varepsilon)\ln p$ unless $\mathrm{P}=\mathrm{NP}$, even over a binary alphabet when all pointers have length one, while known algorithms for Minimum-Weight Multicolored Subgraph give an $O(\sqrt{q\log p})$-approximation for arbitrary pointer lengths. Our main hardness result proves that Complete Source Assignment is APX-hard even over a binary alphabet, with equal pointer lengths and at most two sources per pointer. For edge-disjoint equal-length instances, we give a $3/2$-approximation and a $1.12585$-approximation when each pointer has at most two sources. We also introduce the rainbow-path length $λ$: the problem is polynomial-time solvable for $λ\le2$, and for $λ\le3$ we obtain a $(9/8+\varepsilon)$-approximation. We further give a polynomial-time test for deciding whether abstract source sets can be realized exactly as complete occurrence sets over an unrestricted alphabet. Finally, we give exact fixed-parameter algorithms for several structural parameters, and show that Complete Source Assignment is fixed-parameter tractable in the alphabet size and maximum pointer length.

0.34

Sequential Random Sampling PIR with Multiple Colluding Servers in DNA-Based Data Storage

cs.IT ·2026-10-07 ·Chen Wang, Natalia Silberstein, Eitan Yaakobi
similarity 0.58
Abstract

As DNA-based data storage evolves, protecting user privacy during data retrieval has become increasingly important. We study sequential random sampling DNA private information retrieval (SRS DNA PIR) with multiple colluding random sampling servers, where the database is partitioned into servers of equal size. We investigate the tradeoff between the download cost, defined as the expected number of queries, and the privacy leakage, measured by mutual information. We derive lower bounds on this tradeoff, including a bound given by an optimization problem. This bound is tight when each server stores two files, and we construct schemes that attain it. For servers of any size, we construct schemes that apply a single-server scheme to a randomly selected subset of servers.

0.16

Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels

cs.IT ·2026-09-21 ·Hassan Khodaiemehr, Chen Feng
theory similarity 0.58
Abstract · 13 pages, 4 figures, 9 tables. v2: corrected orbit reduction (complement-reversal theorem); ORD values recomputed with numerical certificate…

In DNA data storage, racetrack memories, and packet networks, data are written as many short strands of fixed length. The receiver knows where each strand begins and ends, and deletions occur only inside a strand. The relevant limit for such systems is the block capacity $C_N(d)$, the largest mutual information between a length-$N$ input and the output of a binary deletion channel with deletion probability $d$. Because the boundaries are known, $C_N(d)/N$ is never smaller than the classical capacity $C(d)$. Computing $C_N(d)$ is hard because the input takes $2^N$ values. For $0\le d<1$, we show that the optimal input is unique, gives positive probability to every string, and is unchanged by complementing or reversing the strings. We then introduce the optimized run distribution (ORD), which assigns one probability to each number of runs; it is optimal for $N\le3$ and is solved with a numerical optimality certificate up to $N=16$. For longer strands, an exact recursion for the output distribution gives unbiased rate estimates, and an empirical Bernstein inequality turns them into confidence intervals. Within the statistical precision, a one-parameter Markov input performs as well as the best inputs found. For strands of 100-200 bits, known boundaries increase the rate by up to 0.026 bits per symbol beyond the best certified upper bound on the capacity of the unsegmented channel. Via Fano's inequality, the block capacity also bounds the rate of any code that uses a single strand; in the tabulated case, this bound is tighter than the best known finite-length bound for strands longer than about 90 bits. Conversely, block rates yield lower bounds on $C(d)$; at $d=0.1$, the bound is within $1.1\times10^{-4}$ bits/use of the best certified lower bound. Finally, InfoNCE estimates, even with the optimal critic, empirically lose most of their ability to rank inputs as the strand length grows.

0.24