Abstract:
For any two $q$-ary sequences $x$ and $y$, the stem similarity between them is defined as a total number of stems (blocks of length 2 consisting of adjacent elements of $x$ and $y$) in their longest common Hamming subsequence. For $q=4$ this similarity function and the corresponding distance function arise in molecular biology in describing an additive mathematical model of thermodynamic distance between DNA sequences. In the present paper, we derive explicit formulas for sphere sizes in this metric and consider their asymptotics in the case of spheres of a constant radius. Based on these results, we also obtain a random coding bound and Hamming bound for the optimal size of the so-called DNA codes for the case of a constant distance.
Fulltext:
PDF file (227 kB)
