🔢 mathematics

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

This paper investigates weak arcs and their balanced variants in finite projective spaces, establishing size bounds and explicit constructions that are subsequently applied to solve the random-access problem in DNA-based storage with performance matching the best known asymptotic bounds.

Original authors: Geertrui Van de Voorde, Ferdinando Zullo

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Geertrui Van de Voorde, Ferdinando Zullo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a library where every book is written in the code of life itself, stored as a vast, swirling pool of microscopic DNA molecules. To retrieve a single specific story from this pool, scientists must dip a net into the water and pull out strands of DNA, reading them one by one until they find the piece of information they need. The challenge is efficiency: if the library is disorganized, you might have to pull out thousands of strands before finding the one you want. Researchers are trying to design the library's layout so that any single piece of information can be found with the fewest possible attempts. This is not just about saving time; it is about making DNA storage practical for the massive amounts of data the world will generate in the future.

The core of the problem lies in how the information is mixed together. In a typical system, the original data is broken into separate strands, and the stored molecules are created by blending these strands in specific mathematical combinations. To recover a specific original strand, the retrieval process must collect enough of these blended molecules so that the unique "signature" of that original strand emerges from the mix. If the blending is done poorly, the retrieval process becomes a game of chance where you might need to read many, many molecules before the signal becomes clear. The goal is to arrange the blending recipe so that the worst-case scenario—finding the hardest-to-reach piece of information—requires as few reads as possible.

A team of mathematicians has approached this storage problem by looking at it through the lens of geometry. Instead of thinking about DNA strands as chemical sequences, they visualized them as points in a multi-dimensional space. In this view, the fundamental pieces of data are like the corners of a shape, and the blended molecules are points scattered along the lines connecting those corners. The researchers discovered that the most efficient way to arrange these points is to follow a very specific geometric rule. They found that if you place points only along the edges of a fundamental shape, and distribute them evenly, you create a structure that is remarkably good at revealing the original data. They call these structures "weak arcs," a name that describes how these points interact with the empty spaces around them, ensuring that no matter how you look at the shape, you never get lost in a dead end.

The researchers proved that the best arrangement is one where the points are balanced. Imagine a triangle with a point at each corner. The most efficient design places an equal number of extra points along each of the three sides, but never in the middle of the triangle itself. This balance is crucial. If you crowd too many points on one side and leave another empty, the retrieval process becomes inefficient for the empty side. The team showed that for a specific type of mathematical field, the perfect balance is achieved when the number of points on each side is exactly half of the total possible positions available. This configuration, which they constructed explicitly, allows for the recovery of any data strand with a high degree of certainty using a number of reads that is significantly lower than previous methods.

While this balanced arrangement is the best possible solution if you are restricted to placing points only on the edges, the researchers also explored what happens when you are allowed to use the entire space. They tested a more complex design that fills the interior of the shape with points, assigning different weights or frequencies to the points on the edges versus those in the center. They found that by carefully tuning these weights, it is possible to squeeze out a tiny bit more efficiency, pushing the expected number of reads even lower. However, this gain comes at a cost: the design becomes much larger and more complex to implement. The simpler, edge-only design remains a powerful tool because it works well even with small, manageable numbers and does not require the massive scale of the more complex version.

The paper provides concrete examples of how to build these structures for different sizes of data sets. They demonstrated that their geometric constructions work for any size of the underlying mathematical system, from very small to very large. This flexibility is a major advantage over other methods that might only work under very specific, restrictive conditions. By proving that these geometric patterns lead to the best possible recovery rates for their specific constraints, the researchers have given engineers a clear blueprint for building more efficient DNA storage systems. They have shown that the key to unlocking the potential of biological data storage lies not in adding more complexity, but in finding the right geometric balance, ensuring that every piece of information is just a short, predictable journey away from being found.

Technical Summary: Weak Arcs and Applications to the DNA-based Storage Access Problem

Problem Statement
This paper addresses the random-access problem in DNA-based data storage. In this model, digital information is encoded into $n$ strands over a finite field $\mathbb{F}_q$ . These strands are stored as a pool of molecules, where each encoded strand represents a linear combination of the information strands. The recovery goal is to retrieve a specific information strand (represented by a standard basis vector $e_i$ ) by sampling the pool with replacement. The performance metric is $M(G)$ , defined as the worst-case expected number of reads required to recover any single information strand. Mathematically, this problem is modeled in the projective space $PG(n-1, q)$ , where the information strands correspond to fundamental points $P_1, \dots, P_n$ . The objective is to construct a multiset of points $G$ such that the expected time $\tau_{P_i}(G)$ to span any fundamental point $P_i$ is minimized.

Methodology
The authors employ a geometric approach, translating the coding problem into the study of point sets in projective spaces.

Geometric Definitions: The paper introduces weak arcs, defined as point sets $S$ in $PG(n-1, q)$ such that every "general hyperplane" (a hyperplane not containing any fundamental point) intersects $S$ in at most $n-1$ points.
Balanced Quasi-arcs: A specific subclass of weak arcs is studied where points are constrained to lie on the edges (sides) of the fundamental simplex. A balanced quasi-arc of parameter $a$ contains the fundamental points and exactly $a$ non-fundamental points on every edge.
Analytical Tools:
- Combinatorial Counting: The authors derive upper bounds on the size of weak arcs and characterize the maximum size of balanced quasi-arcs in the plane ( $PG(2, q)$ ) using properties of multiplicative subgroups and cosets in $\mathbb{F}_q^*$ .
- Probabilistic Method: A probabilistic construction is used to establish the existence of balanced quasi-arcs of a certain size, serving as a baseline.
- Expectation Calculation: The expected recovery time $E[\tau_{P_i}]$ is expressed using harmonic numbers and the counts of subsets whose spans do not contain the target point. This allows for the comparison of different point set configurations.
- Weighted Constructions: The paper extends these geometric configurations to multisets by assigning multiplicities to fundamental points and non-fundamental points to optimize the recovery expectation.

Key Contributions and Results

Geometric Characterization:
- An upper bound on the size of weak arcs in $PG(n, q)$ is established: $|S| \le nq + (n+1)$ .
- In the planar case ( $PG(2, q)$ ), the paper characterizes the largest balanced quasi-arcs. For odd $q$ , the maximum parameter is $a = (q-1)/2$ , achieved by taking squares and non-squares in $\mathbb{F}_q^*$ . For even $q$ , the construction involves unions of cosets of proper subgroups.
- In $PG(3, q)$ , the authors construct a "weak cap" on the edges of the fundamental tetrahedron and extract a balanced quasi-arc from it.
Optimization for DNA Storage:
- The paper demonstrates that for point sets confined to the edges of the fundamental triangle, the balanced quasi-arc with parameter $(q-1)/2$ minimizes the recovery expectation among all balanced sets.
- The asymptotic limit of the normalized recovery expectation for these balanced quasi-arcs is shown to be $17/18 \approx 0.9444$ (for $n=3$ ).
Explicit Constructions with Multiplicities:
- Weighted Weak Arcs: The authors propose a construction in $PG(3, q)$ $P G (3, q)$ where fundamental points have multiplicity $a$ $a$ and non-fundamental points on edges have multiplicity 1. This construction realizes the recovery-complete family $G_4(a, a)$ $G_{4} (a, a)$ from prior literature.
  - Result: As $a \to \infty$ , the normalized expectation approaches $\approx 0.863788$ .
  - Advantage: This construction is explicit and works over small fields (e.g., $a=4$ is realizable over $\mathbb{F}_{17}$ ), whereas previous general constructions required significantly larger fields.
- The $H_q$ Construction: A discrete version of the Wang-Yaakobi construction is presented, utilizing points on edges and the interior of the tetrahedron with specific integer multiplicities, while excluding points strictly on the faces (but not edges).
  - Result: This construction achieves a normalized asymptotic expectation of $\approx 0.862795$ , slightly improving the explicit numerical bound of $0.862882$ previously reported in the literature.
  - Trade-off: This improvement comes at the cost of a significantly larger set size ( $|H_q| = 47(q-1)^3$ ).

Significance and Claims
The paper claims that its geometric constructions provide explicit, field-independent solutions to the random-access DNA storage problem.

Explicitness and Small Fields: Unlike previous asymptotic or large-field constructions, the weighted weak arc construction (Proposition 9) provides explicit examples for small $q$ and small support sizes, making it practically relevant for systems with alphabet constraints.
Asymptotic Performance: The $H_q$ construction (Proposition 10) offers a slight improvement over the best-known explicit asymptotic bounds for $n=4$ information strands, confirming the efficacy of the Wang-Yaakobi framework while providing a concrete, integer-multiplicity realization.
Geometric Insight: The work bridges finite geometry and coding theory, showing that weak arcs and balanced quasi-arcs are natural geometric structures that yield near-optimal recovery expectations for DNA storage. The authors note that while balanced quasi-arcs are not proven to be globally optimal for all point sets (as off-edge points can improve performance), they are optimal within the class of sets confined to the simplex edges.

The paper concludes by comparing these constructions against prior work, highlighting that the choice between constructions depends on the specific constraints of the storage system: the weighted weak arcs are preferable for small support and small fields, while the $H_q$ construction is superior for minimizing asymptotic recovery expectation at the cost of larger set sizes.

More like this