Motivated by DNA storage in living organisms, and by known biological mutation processes, we study the reverse-complement string-duplication system. We fully classify the conditions under which the system has full expressiveness, for all alphabets and all fixed duplication lengths. We then focus on binary systems with duplication length $2$ and prove that they have full capacity, yet surprisingly, have zero entropy-rate. Finally, by using binary single burst-insertion correcting codes, we construct codes that correct a single reverse-complement duplication of odd length, over any alphabet. The redundancy (in bits) of the constructed code does not depend on the alphabet size.
翻译:以活生物体中的DNA储存和已知的生物突变过程为动力,我们研究了反向相容字符串复制系统。我们对所有字母和所有固定重复长度都对该系统具有完全清晰度的条件进行了充分分类。然后我们把重点放在重复长度为2美元的二进制系统上,并证明它们具有完全的容量,但令人惊讶的是,它们具有零的催化速率。最后,我们通过使用二进制单爆插入校正代码,我们构建了代码,纠正单反相重叠的奇异长度,超越任何字母的单反相重叠。所建代码的冗余(以位数表示)并不取决于字母大小。