On the Capacity of DNA Labeling

<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">DNA labeling</i> is a powerful tool in molecular biology and biotechnology that allows for the visualization, detection, and study of DNA at the molecular level. Under this paradigm, a DNA molecule is being <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">labeled</i> by specific <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> patterns and is then imaged. Then, the resulting image is modeled as a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(k+1)$ </tex-math></inline-formula>-ary sequence in which any non-zero symbol indicates on the appearance of the corresponding label in the DNA molecule. The primary goal of this work is to study the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">labeling capacity</i>, which is defined as the maximal information rate that can be obtained using this labeling process. The labeling capacity is computed for almost any pattern of a single label and several results for multiple labels are provided as well. Moreover, we provide the optimal minimal number of labels of length one or two, over any alphabet of size <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>, that are needed in order to achieve the maximum labeling capacity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log _{2}(q)$ </tex-math></inline-formula>. Lastly, we discuss the maximal labeling capacity that can be achieved using a certain number of labels of length two.