Dna labeling capacity fully characterized for single-label cases
On the Capacity of DNA Labeling in the Single-Label Setting
Information Theory
Summary
The paper looks at how well DNA sequences can be distinguished by marking specific patterns called labels. The authors show that this labeling process works like a communication channel without errors, and they find the exact limits of how many different DNA sequences can be uniquely identified using just one type of label. They also explain how to design codes that reach this limit. This helps understand how to best label DNA or other sequences to tell them apart.
What this means in practice
- •For biomedical engineers: Design precise DNA labeling schemes that maximize the number of distinguishable DNA sequences for molecular diagnostics.
- •For communications system designers: Use the derived zero-error capacities of star graphs to design error-free codes in similar deterministic channel models beyond DNA labeling.
A theory result. No direct application yet.
Authors
Zihan Wu, Qi Cao, Ling Liu, Baoming Bai
Abstract
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.