Encoding methods for DNA languages defined via the subword closure operation

Abstract

In DNA computing, information is encoded onto DNA sequences. The DNA codes in the form of single-stranded DNA sequences are not stable. This is because when two single-stranded DNA sequences, used to carry data, have complement parts on them, they naturally tend to stick to each other. This is due to the Watson-Crick complementarity property and causes the problem of undesirable bonds. Some properties and constraints have been proposed to prevent the problem, but most of them are local constraints which concentrate on a segment of a DNA word of a certain length. Therefore, if we concatenate some DNA words satisfying some local constraints, the resulting words might violate the same constraints. This makes encoding methods for DNA languages difficult to design. To solve this problem, we investigate sonic properties of the subword closure operation that is used for constructing DNA languages and propose practical encoding methods for such languages. We also implement our methods using advanced C++ tools for finite automata as well as design a web interface that allows users to obtain a DNA language in response to given values for certain parameters.