PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Capacity of DNA Labeling in the Single-Label Setting

Zihan Wu, Qi Cao, Ling Liu, Baoming Bai

arXiv:2609.36715v1cs.ITmath.IT

TL;DR

DNA labeling records label positions in output sequences, and a general characterization of labeling capacity remains open. The paper formulates labeling as a deterministic channel and relates its capacity to zero-error capacity. It characterizes capacities for all single-label cases and the achievable range for each fixed label length.

  • Problem

    A general characterization of labeling capacity remains open, although several cases have been characterized in single- and multiple-label settings.

    Source: §I · p. 2

  • Method

    The paper models labeling as a deterministic channel, equates its zero-error capacity with labeling capacity, and represents the single-label channel by a star graph.

    Source: §I · p. 2

  • Results

    The paper completely characterizes zero-error capacities of all star graphs and, for fixed label length, the achievable-capacity range and all structures attaining its endpoints.

    Source: §IV · p. 17

  • Takeaways & Limitations

    The results apply to labeling problems over arbitrary finite alphabets, not only the DNA alphabet.

    Source: §IV · p. 17

Abstract

from arXiv · show

DNA labeling has attracted increasing attention in biomedical applications, including molecular imaging, diagnostics, and genomic analysis. In a DNA labeling process, a set of DNA sequence patterns, referred to as labels, is designed according to the requirements of a specific application. For each DNA sequence, the labeling process generates an output sequence that records the positions of the labels. DNA sequences with different labeling outputs can therefore be distinguished through the labeling process. To quantify this capability, the labeling capacity is defined as the exponential growth rate of the maximum number of DNA sequences that can be distinguished through the labeling process as the sequence length tends to infinity [2]. To date, the labeling capacities of several cases in the single-label setting have been determined. In this paper, we formulate the labeling process as a deterministic channel and show that its zero-error capacity is equal to the labeling capacity. For a single label, the corresponding channel can be represented by a star graph. Thus, characterizing the labeling capacity of a single label is equivalent to determining the zero-error capacity of the corresponding star graph. We derive the zero-error capacities of all star graphs, thereby providing a complete characterization of the labeling capacities for all single-label cases. Furthermore, we develop a general method for constructing capacity-achieving codes. These results apply to labeling problems over arbitrary finite alphabets and are not restricted to the DNA alphabet. Finally, for a fixed label length, we exactly characterize the range of achievable labeling capacities and identify all single-label structures that attain the minimum and maximum capacities.

I. INTRODUCTION

DNA labeling records sequence-pattern locations, but a general characterization of labeling capacity remains open. This paper links labeling capacity to zero-error capacity and completely characterizes the single-label case, including the capacity range and its endpoint structures.

I. INTRODUCTION

  • DNA labeling is used in FISH, optical mapping, and molecular diagnostics to locate genomic regions, characterize sequences, and detect disease-related markers,,.Source: §I · p. 1
  • DNA-storage retrieval can use sequence-specific recognition, including PCR-based random access, hybridization-based search, and CRISPR-based approaches,,.For some access tasks, identifying patterns can suffice without recovering entire sequences.Source: §I · p. 2
  • The labeling capacity is the exponential growth rate of the number of distinct output sequences as sequence length tends to infinity, and its general characterization remains open.For label CG, the example output cannot contain consecutive 1s, satisfying the (1, ∞)-RLL constraint.Source: §I · p. 2
  • The labeling capacity of a single label equals the zero-error capacity of its star graph, whose capacities are characterized for all single-label cases.The paper also develops a general method for constructing capacity-achieving codes.Source: §I · p. 2
  • C0(α) lies between −log β and −log γ, where β and γ are the unique positive roots of x + x^ℓ(α) = 1 and x + x^((ℓ(α)+1)/2) = 1, respectively.Source: §I · p. 3
  • For fixed label length, the achievable-capacity range is exactly characterized, and all single-label structures attaining its minimum and maximum are identified.Fig. 1 illustrates the range for a single label α of length ℓ(α).Source: §I · p. 3, Figure 1 · p. 3

II. DEFINITIONS AND PRELIMINARIES

This section establishes notation over a finite alphabet and introduces sequence operations used in the paper. It also points readers to a table summarizing lemmas and corollaries used to determine single-label capacity.

II. DEFINITIONS AND PRELIMINARIES

  • The paper assumes a finite alphabet X with at least two symbols and defines a label as a nonempty finite sequence over X.Logarithms are base 2, with the base omitted for brevity.Source: §II · p. 3
  • Sequence notation includes subsequences, concatenation, repeated concatenation, and proper or non-proper prefix and suffix relations.The subsequence x[i;l] is the length-l segment beginning at index i.Source: §II · pp. 3–4
  • Table I summarizes the lemmas and corollaries used to determine the labeling capacity of a single label.Source: §II · p. 4, Table I · p. 4

A. DNA Labeling

The DNA-labeling definitions specify a prefix-free label sequence and map each input sequence to a position-wise labeling sequence. Prefix-freeness ensures that the output is uniquely defined.

A. DNA Labeling

  • A label sequence a consists of labels {αm} such that no label is a prefix of another.Source: A. DNA Labeling · p. 5
  • The a-labeling sequence La(x) records at each position the matching label's symbol, or zero when no label starts there.Source: A. DNA Labeling · p. 5
  • Because a is prefix-free, at most one label matches at any position, so La(x) is uniquely defined.Source: A. DNA Labeling · p. 5

B. Zero-Error Capacity

The labeling process is modeled as a channel whose zero-error capacity equals its labeling capacity. The channel can also be represented by a graph that encodes which inputs are distinguishable.

B. Zero-Error Capacity

  • The labeling channel maps an X-ary input sequence of length n to an (M + 1)-ary output sequence of the same length.The output records label occurrences at their positions.Source: B. Zero-Error Capacity · p. 5
  • The graph G(a) uses length-ℓmax sequences as vertices and connects pairs exactly when their labeling outputs differ.This graph is the complement of Shannon’s convention, which connects indistinguishable pairs.Source: B. Zero-Error Capacity · pp. 5–6
  • The zero-error capacity is the asymptotic rate of maximum code size, and its defining limit exists by superadditivity and Fekete’s Lemma [19].The paper defines a code as pairwise distinguishable sequences for G(a).Source: B. Zero-Error Capacity · p. 6
  • The authors apply a method from that adds arbitrary prefixes and suffixes to each sequence in an existing code to construct a new code.The resulting sequences have length n + ℓ(u) + ℓ(v).Source: B. Zero-Error Capacity · p. 6
  • For any label sequence a, the labeling capacity CL(a) equals the zero-error capacity C0(a).The proof equates the number of distinguishable outputs with the maximum cardinality of a zero-error code.Source: B. Zero-Error Capacity · p. 6

C. Key Structural Parameters of Labels

This section defines structural parameters for sequences, including units, shortest prefix-units, and shortest dividing-units. It also gives properties relating these structures and symbol counts.

C. Key Structural Parameters of Labels

III. THE LABELING CAPACITY OF A SINGLE LABEL

This section represents the single-label channel as a star graph and characterizes its zero-error labeling capacity using code-rate lower bounds and output-constraint upper bounds, alongside structural properties for sequences over a suffix-free set. For fixed label length, it bounds achievable capacities and identifies conditions for attaining the extrema.

III. THE LABELING CAPACITY OF A SINGLE LABEL

  • For a single label α, the channel graph G(α) is a star centered at α, with all other vertices representing sequences of length ℓ(α).Source: §III · p. 7
  • Every element of Θ is a prefix of P(α), and when ℓ(θ⟨1⟩) = ℓ(P(α)) − 1, the unique index k̃ equals 1.Source: §III · p. 10
  • The set Φ satisfies |Φ| ≤ ℓ(P(α)) − 1, with equality including the case ℓ(P(θ)) = 1 and ℓ(θ) = ℓ(P(α)) − 1.Source: §III · p. 11
  • C0(α) = -log μ, where μ is the unique positive root of an equation, gives the zero-error capacity of the star graph G(α).The supplied passage does not include the equation defining μ.Source: §III · p. 12
  • The constructed set B is suffix-free, so every sequence in B* has a unique decomposition, and any such sequence at least as long as α has α as a prefix.Source: §III · pp. 12–13

Theorem 2

  • For fixed label length, −log β ≤ C0(α) ≤ −log γ; the lower bound is attained if and only if ℓ(P(α)) = ℓ(α).β and γ are the unique positive roots of the equations stated in Theorem 2.Source: §III · p. 15
  • For γ, g(γ) = 1 if and only if one of two conditions holds; the supplied condition is ℓ(α) = 2ℓ(P(α)) − 1 and ℓ(P(θ)) = 1.Source: §III · pp. 15, 17

IV. CONCLUSION

The paper resolves single-label DNA labeling capacity by characterizing the zero-error capacity of star graphs. It also gives capacity-achieving codes and tight bounds for fixed label lengths, with results that apply to arbitrary finite alphabets.

  • The zero-error capacity of all star graphs is completely characterized, resolving labeling capacity for every single-label case.Source: §IV · p. 17
  • A general coding method constructs capacity-achieving codes for all star graphs.Source: §IV · p. 17
  • For any fixed label length, the paper derives tight lower and upper bounds and necessary and sufficient conditions for attaining each bound.Source: §IV · p. 17
  • The results apply to arbitrary finite alphabets; extending the coding methods to run-length- and GC-content-constrained DNA labeling is left for future research.Source: §IV · p. 17
Loading 2609.36715v1…