k-involution codes and related sets

Abstract

This study was motivated by the problem of optimally encoding information on DNA for biocomputational purposes. Our formalization of intermolecular hybridization (binding) with bulges led to the notion, interesting in its own right, of k-involution codes. An involution code refers to any of the generalizations of the classical notion of codes in which the identity function is replaced by an involution function. (An involution function θ is such that θ² equals the identity. An antimorphic involution is the natural formalization of the notion of DNA complementarity.) We namely define and study the notions of k-θ-prefix, k-θ-suffix and k-θ-bifix codes. We also extend the notion of k-insertion set and k-deletion set of a language to incorporate the notion of an involution function. Thus, to an involution map θ and a language L, we associate a set k-θ-ins(L) (k-θ-del(L)) with the property that its k-insertion (k-deletion) into any word of L yields words which belongs to θ(L). We study the properties of these languages and their connection to involution codes.

Keywords and phrases:

• Codes
• Waston-Crick involution
• DNA computing
• insertion
• deletion