Séminaire de groupe
|How the size of nucleotide alphabet influences the secondary structures of RNA?|
|Physics Department, Moscow State University|
|jeudi 04 octobre 2012 , 10h25|
|Salle de séminaire du groupe de Physique Statistique|
I start with discussing the celebrated longest common subsequence (LCS) problem, mention some of the main results known about the LCSs of random sequences, and introduce the so-called Bernoulli matching approximation in which they can be studied exactly. Then I introdcue some generalization of the LCS problem which has a direct connection to the problem of reconstracting the RNA secondary strcture from the known sequence of nucleotides. With this application in mind I concentrate on the random sequences of letters drown from a given finite set (e.g., four types of nucleotides in case of RNA), and argue that the behavior of the generalized LCS depends drastically on the size of the set. Namely, for small sets the fraction of letters involved in the generlized LCS converges to one as the sequence size goes to infinity, while for large sets it does not. These two regimes are separated by a morphological phase transition. I prove the upper and lower bounds for the position of the transition point, and then employ the Bernoulli matching approximation to study the transition numerically in more detail. The talk is mostly based on O. Valba, M. Tamm, S. Nechaev, PRL, 109, 018102 (2012).