On the Reverse-Complement String-Duplication System
Abstract
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.