Семинары: Никита Алексеев, Антон Никитенко, Модель перестройки генома, перестановки, альтернирующие циклы и случайные матрицы

СЕМИНАРЫ


Семинар Лаборатории Чебышёва «Теория вероятностей» 7 ноября 2011 г. 12:00, г. Санкт-Петербург, 14-я линия ВО, 29Б, аудитория 413

Модель перестройки генома, перестановки, альтернирующие циклы и случайные матрицы Никита Алексеев, Антон Никитенко Санкт-Петербургский государственный университет
Аннотация: Наш доклад будет состоять из двух частей. Сначала мы попробуем объяснить, что такое перестройка генома и как она связана с группой перестановок. Мы дадим определения циклического графа перестановки и альтернирующих циклов в нем и покажем, почему эта конструкция естественна в вопросах биоинформатики. Во второй части мы рассмотрим некоторые чисто математические вопросы, возникающие в этом сюжете. А именно, пусть $h(n,k)$ – число перестановок из $S_n$, циклические графы которых раскладываются в $k$ альтернирующих циклов. Эти числа уже исследовались несколькими авторами (см. [2] и [4]). Мы представим новую интерпретацию чисел $h(n,k)$ в терминах склеек многоугольников и в терминах случайных матриц. $ $ [1] V. Bafna, P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics 11 (2) (1998), 224–240. [2] M. Bóna, R. Flynn, The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley, Information Processing Letters 109 (16) (2009) 927–931 [3] J.-P. Doignon, A. Labarre, On Hultman Numbers, Journal of Integer Sequences 10 (6), article 07.6.2, 13 p. [4] J. Harer, D. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math., 85 (1986), 457–485.