Abstract:
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.
|
