[МУЗЫКА] [МУЗЫКА] На прошлой лекции мы с вами ввели основные понятия теории групп, мы рассмотрели простейшие числовые группы, а также поговорили немножко о диэдральной группе. Кроме этого, мы увидели, что симметрическая группа, а это группа всех перестановок, играет очень важную роль в комбинаторике групп Коксетера в дискретной геометрии. Сегодня на примере одной очень простой задачи, которую можно легко объяснить любому ребенку, мы покажем, как возникают графовые модели на симметрической группе, в частности, в биоинформатике. Простота постановки задачи вовсе не означает, что эта задача очень легко решается, и это мы тоже сегодня с вами увидим. Итак, постановка этой задачи была сделана в 1975 году Джейкобом Гудманом, американским математиком, специалистом в дискретной геометрии. Итак, представьте себе, что вы пришли в американский ресторан, где готовят блинчики. Вы спешите, поэтому эти блинчики укладывают сразу на тарелку на поднос, который держит официант. И все блинчики выходят разного размера, поэтому официант пытается свободной рукой, которая у него имеется, сделать следующее: он подхватывает стопку блинчиков и переворачивает ее так, чтобы упорядочить нужны образом, чтобы наверху был маленький блинчик, а внизу — самый большой. Эта операция называется «флип», и вопрос Джейкоба состоял в следующем: каково минимальное количество флипов, которое необходимо совершить официанту для того, чтобы упорядочить стопку блинчиков разного размера от минимального на самом верху, до максимального в самом низу, где под флипом понимается операция переворачивания стопки блинчиков от верхнего до некоторого фиксированного? Давайте попробуем посмотреть на эту задачу с точки зрения симметрической группы, а именно, если перенумеровать все блинчики в стопке от 1 до n в соответствии с тем, как устроен размер этого блинчика, то мы получим с вами некоторую перестановку, на которой введем операцию под названием «префикс-реверсал». Она будет совершать то же самое действие, что и флип на стопке блинчиков. Тогда задача сводится к поиску расстояния между произвольной перестановкой π и единичной перестановкой, где под расстоянием в данном случае будет пониматься префикс-реверсальное расстояние. Эту задачу в компьютерных науках принято также называть «сортировка префикс-реверсалами». А теперь давайте мы с вами определим эту операцию префикс-реверсал, что же это такое? На самом деле когда я говорю «операция», то под этим понимается следующее. Рассмотрим симметрическую группу степени n с порождающим множеством всех префикс-реверсалов ri, так, что при умножении любой перестановки π на этот префикс-реверсал справа мы получаем другую перестановку, у которой в интервале от 1 до i меняется порядок всех элементов. Так, например, при умножении единичной перестановки степени 4 на все возможные префикс-реверсалы мы получаем следующие перестановки. Это будет перестановка [2 1 3 4], если мы используем префикс-реверсал r2, при умножении на r3 мы получим перестановку [3 2 1 4]. И, наконец, мы получим полностью инвертированную перестановку в том случае, если умножаем на префикс-реверсал r4. Таким образом мы с вами получили три новых перестановки. Давайте сейчас проверим следующее, что действительно три элемента, три префикс-реверсала, r2, r3, r4, порождают всю симметрическую группу степени 4. Мы продолжим порождать новые перестановки, используя это порождающее множество. И нетрудно показать, что на основе трех ранее полученных перестановок можно получить шесть различных новых перестановок. Вы можете наблюдать этот процесс сейчас на слайде, где появляются перестановки в виде вершин графа, и между вершинами появляются ребра в том случае, если одна перестановка получается из другой умножением на некоторый префикс-реверсал. Продолжая действовать таким образом, достаточно просто и быстро получить все 24 перестановки на четырех элементах. Вы видите, что последними получаются перестановки такого вида. Это три перестановки, [2 4 1 3], [3 1 4 2], [4 2 3 1]. При этом каждая из них получается путем умножения единичной перестановки на последовательность из четырех префикс-реверсалов. В первом случае это будет последовательность r2, r3, r4, r2. Во втором случае это будет последовательность r2, r4, r3, r2. И, наконец, в последнем случае это будет последовательность r4, r2, r3, r2. Итак, что мы с вами получили? Если добавить к тому графу, который мы уже построили, недостающие ребра, то мы с вами получим слоевое представление графа, которое называется «блинчиковый граф». И задача Гудмана сводится к поиску диаметра в этом графе. Конечно же, в самом общем случае, то есть мы берем симметрическую группу степени n, (n − 1) префикс-реверсал в качестве порождающего множества и получаем блинчиковый граф. Вот графы, которые определены на группе, как мы с вами говорили еще в самом начале этого курса, будут специально рассматриваться в третьем модуле. Такие графы называются графами Кэли, и наш блинчиковый граф является графом Кэли. А вот что же касается диаметра этого графа, то на сегодняшний день эта проблема по-прежнему остается открытой. Точные значения диаметра блинчикового графа для n ≤ 19 известны, и вы их сейчас видите на слайде. Только представьте себе, если n = 19, то диаметр такого графа будет равен 22. Что такое n = 19? Это значит, что у вас 19! вершин, это число вы сейчас видите на слайде. А две наиболее удаленные вершины будут находиться всего лишь на расстоянии 22. Удивительная компактность графа. Но этот граф обладает и другими удивительными свойствами. Именно поэтому его архитектура используется для представления компьютерных сетей в компьютерных науках. В самом общем виде задачу определения диаметра такого графа пытался решить Билл Гейтс, когда он был студентом Гарвардского университета и выполнял научно-исследовательскую работу под руководством Христоса Пападимитриу, профессора компьютерных наук. В 1979 году они опубликовали совместную научную статью, в которой были найдены оценки на диаметр графа, нижняя и верхняя. Через 20 лет эти оценки были немного улучшены, но существенного продвижения в решении этой задачи по-прежнему нет. Хотелось бы отметить, что у этой задачи имеется также некоторое интересное обобщение, на подгоревших с одной стороны блинчиках, которые также нужно упорядочить, но не только так, чтобы самый маленький был наверху, а самый большой внизу, нужно сделать так, чтобы у вас наверху были только неподгоревшие стороны ваших блинчиков. В этом случае математическая задача сводится к моделированию на группе, содержащей все помеченные перестановки. «Помеченные» — это означает, что, помимо того, что у вас есть множество от 1 до n, каждый из этих элементов имеет право иметь свой собственный знак, плюс или минус. В этом случае вы получаете тогда (2 ^ n) * n! перестановок, которые образуют гипероктаэдральную группу. Так вот, этот вариант задачи Билл Гейтс рассказал своему другу, Дэвиду Коэну, который в 1995 году опубликовал совместную статью с Мануэлем Блюмом, в которой они показали оценки на диаметр уже этого графа, блинчикового графа, но на гипероктаэдральной группе. После чего Дэвид Коэн, который также учился в Гарвардском университете на факультете компьютерных наук, он решил, что внес достаточный вклад в развитие математики, он написал сценарий к «Футураме», чем в основном он и известен нам. А теперь самое время сказать, какое это все имеет отношение к биоинформатике. В молекулярной биологии геном представляется в виде перестановки, в которой гены занумерованы от 1 до n. И в 1986 году Джефри Палмер и Лаура Хербон обнаружили, что на самом деле X-хромосомы человека и мыши содержат одно и то же количество одинаковых генов, а именно, в X-хромосоме человека они упорядочены так, как мы записали бы в виде перестановки [4 6 1 7 2 3 5 8]. А вот X-хромосома мыши будет соответствовать единичной перестановке. При этом одним из способов мутации является следующий. При переходе от одного вида к другому происходит следующее. Число генов остается тем же самым, но запись, порядок записей их меняется, точно так же, как это происходит при применении префикс-реверсала к перестановке. То есть если вы себе представите геном в виде некоторого червяка в пространстве, то у него отрывается хвост, кусок, переворачивается в пространстве и вновь приклеивается. Таким образом блинчиковый граф служит графовой моделью для исследования мутационных процессов генома, а диаметр соответствует удаленности этих геномов друг от друга. Кроме этого, в 2007 году был создан биокомпьютер на основе генетически модифицированной кишечной палочки, который на самом деле решал задачу о подгорелых блинах. Роль блинов в этом случае играли фрагменты дезоксирибонуклеиновой кислоты. Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. А вот время, которое затрачивалось на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагментов. Вот такие удивительные приложения симметрической группы в молекулярной биологии и биоинформатике наблюдаются. А в следующий раз мы с вами разберемся с тем, как симметрическая группа помогла найти наилучшее решение задачи кубика Рубика.
