DNA codes for additive stem similarity

We study the new concept of combinatorial coding theory called an additive stem similarity between q-ary sequences that can be used (for q=4) to model an additive thermodynamic similarity reflecting the "hybridization potential" of two DNA sequences. DNA code is a collection of DNA sequences (codewords) which is invariant under the Watson-Crick transformation and if a pair of its codewords does not form the Watson-Crick duplex (DNA double helix), then the additive thermodynamic similarity between these codewords should be less than a fixed level. We obtain asymptotic lower and upper bounds on the maximal size of DNA code. The lower bound is based on an ensemble of random codes, where the distribution of independent codewords is identified by a stationary Markov chain, and we apply the large deviations techniques to a sum of random variables connected via Markov chain. The paper is written jointly with A.N. Voronina.