

Principle Seminar of the Department of Probability Theory, Moscow State University
February 25, 2009 16:45, Moscow, MSU, auditorium 1624






DNA codes for additive stem similarity
A. G. D'yachkov^{} 
Number of views: 
This page:  33 

Abstract:
We study the new concept of combinatorial coding theory called an additive stem similarity
between qary 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 WatsonCrick transformation and if a pair
of its codewords does not form the WatsonCrick 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.

