Просеминар: теория графов и биоинформатика

(профессор д.ф.-м.н. В.А. Любецкий)

См. сайт http://lpcs.math.msu.su/~lyubetsky/2018/ и страничку на сайте кафедры МЛиТА.

Большая информация, для продвинутых, на сайте нашей группы http://lab6.iitp.ru/ru/pub/, https://istina.msu.ru/profile/[email protected]/, http://www.mathnet.ru/rus/person/13593.

Теория графов. Ниже – биоинформатика.

Введение. Теория графов – чисто математическая теория, одной из областей применения которой является Биоинформатика. В свою очередь, биоинформатика ставит задачи для теории графов; важно, что это математически строгие задачи. Биоинформатика – огромная прикладная область, охватывающая все явления жизни и эволюции живого; «прикладная» относительно математики, но сама по себе также фундаментальная. Её существенная черта – огромные базы данных, их анализ (вместе с моделированием на их основе), в значительной мере, составляет предмет биоинформатики. По упомянутым выше интернет-адресам можно войти с адреса кафедры http://lpcs.math.msu.su/rus/staff.htm (по фамилии лектора).

Любое конечное множество представляется конечным деревом (деревья – важный частный случай графа). Далее везде речь идёт ТОЛЬКО о конечных графах. Отсюда видно, что изучение даже произвольного дерева необозримо. Граф определяется как пара < X, Y >, где X – конечное множество (его элементы называются «вершинами») и Y – произвольное множество пар вершин (его элементы называются «рёбрами» или «дугами»). Парой (неупорядоченной) (x, y) называется множество { x, y } из двух элементов. Парой (упорядоченной) < x, y > называется множество {{ x,{ x, y }} из двух других элементов. Если Y состоит из неупорядоченных пар, то граф называется неориентированным. Если Y состоит из упорядоченных пар, то граф называется ориентированным (тогда каждое ребро имеет направление, которое показано стрелкой и соответственно ей один его край 1й, а другой – 2й). Рёбра часто имеют имена, которые могут повторяться. В случае ориентированного графа ребро с именем n имеет края n ₁ и n ₂. Края рёбер могут СКЛЕИВАТЬСЯ. Ни с кем не склеенный край называется свободным. Степенью вершины называется число рёбер, для которых она является краем. Точкой называется вершина степени 0. После Введения мы будем изучать только графы, у которых все вершины степени ≤2. Такой граф состоит из точек, цепей и циклов; они называются компонентами. Как определить компоненту у произвольного графа? («Гантели» и длинные пути. Связь с «кластерами».) Дерево определяется как граф без циклов. Петля – цикл длины 1.

Фундаментальная задача, которую мы будем изучать, – дан универсальный (=фиксированный) список операций над графами, даны два (переменных) графа a и b; найти кратчайшую цепочку операций, которая преобразует a в b. Это – задача дискретной (комбинаторной) оптимизации. Точнее, нужно найти цепочку с минимальным числом применений операций. Или: каждой операции сопоставлена фиксированная цена (строго положительное рациональное число) и нужно найти цепочку с минимальной суммарной ценой всех применений операций. Эта задача называется задачей преобразования (одного графа в другой).

Эту задачу часто рассматривают следующим образом. Определяется понятие финального графа (=графа финального вида). Для (переменного) графа a нужно найти кратчайшую цепочку операций, которая приводит a к финальному виду. Эта задача называется задачей приведения (графа к финальному виду).

Например, финальный граф состоит только из циклов длины 2 и точек. Связь задач преобразования и приведения на идейном уровне такова. Приведём данный граф a к финальному виду a ₁ и другой данный граф b к финальному виду b ₁. Можно надеяться, что a ₁ легко преобразовать в b ₁ из-за их особо простых видов, а все операции обратимы. Тогда a преобразуется в b естественным путём: a преобразуется в a ₁, a ₁ преобразуется в b ₁, а b ₁ – обратными операциями в b. Мы будем изучать этот путь.

Везде «найти» означает: найти линейный алгоритм, которым выполняет нужное действие и выдаёт нужный объект (здесь – кратчайшую цепочку операций и число применений операций в ней, т.е. её длину, или её суммарную цену) по переменному входу (здесь – по любым данным a и b или только по a). «Линейный» алгоритм означает: время его работы и используемая им память линейно зависит от суммарного размера a и b или только от размера a. «Размер» графа – это, например, число вершин и рёбер в нём.

Для полноты картины отметим другое направление в теории графов. В его рамках ребро (пусть ненаправленное, т.е. рассматриваются неориентированные графы) понимается не как пара вершин, а как непрерывная кривая с началом в a и с концом в b. Примеры задач в этом направлении. Даны три дома и три колодца в одной плоскости, т.е. три вершины («дома») и ещё три вершины («колодцы»). Можно ли от каждого дома к каждому колодцу провести тропинку (в этой плоскости), которые не пересекаются в их внутренних точках. Ответ: нет, но доказательство глубоко нетривиально. Даны пять вершин в одной плоскости, можно ли без пересечений соединить их попарно рёбрами (также без их пересечений и лежащих в той же плоскости).

План решения задачи приведения. Общий граф состоит из циклов (включая петли), цепей и точек (= вершин степени 0). Каждому ребру приписано имя – буква a или буква b, не более двух их повторений подряд. Некоторые из крайних рёбер цепи или из точек отмечены; при этом ребро, соседнее к отмеченному, должно иметь другое имя. Краю (=вершине на краю цепи) отмеченного ребра приписывается имя этого ребра, у цепи, состоящей из одного отмеченного ребра, ровно одной его вершине приписывается такое имя; каждой отмеченной точке приписывается a или b. Вершина при петле имеет имя этой петли; кроме неё имя получают край отмеченного ребра и отмеченные вершины.

Особой называется вершина, имеющая имя (отмеченная точка или край с именем отмеченного ребра или вершина при петле), или вершина между одноимёнными рёбрами; остальные вершины называются обычными. Рёбра, примыкающие к особым вершинам, называются особыми (это – отмеченные и повторяющиеся); остальные – обычными. По определению: в общем графе число обычных вершин чётное (что, как мы увидим, не существенно).

Упр. Оба конца никакого ребра не могут быть особыми. Если считать два одноимённых ребра при особой вершине за «одно двойное», то в каждой компоненте графа имена рёбер чередуются (если больше одного имени). Вершина при петле не является свободной.

a - Свободная вершина – свободный без имени конец b -ребра или без имени точка (обе – обычные вершины), a -точка или свободный особый край a -ребра(обе – особые). Неформально приставка a- означает, что к вершине можно присоединить a -ребро, см. ниже. Аналогично определим b - свободную вершину.

Определим пять операций над общим графом. Висячее ребро – крайнее в цепи отмеченное ребро. Удаление особой вершины: её удалить и два её соседних (особых) ребра объединить в одно (обычное) с тем же именем; крайняя вершина висячего ребра удаляется вместе с ним (обычная вершина ребра остаётся); вершина с петлей или особая точка удаляются. Разрез – удалить ребро из общего графа, его концы остаются. Двойная переклейка – удалить два одинаково помеченных ребра общего графа и соединить попарно четыре образовавшихся конца двумя рёбрами с той же меткой; при этом (*) две соседние особые вершины объединить с потерей ребра между ними, если имеются. Склейка – это: a -свободную вершину соединить a -ребром с a -свободной вершиной и выполнить действие (*); и симметрично для b. (Из ребра может образоваться цикл длины 2.) Полуторная переклейка – удалить ребро с последующей склейкой одного из образовавшихся краёв этого ребра со свободной вершиной. Последние 4 операции называются стандартными. Удаление и разрез могут приводить к появлению точек, если они применяются к крайнему ребру.

Вырезание обычного ребра с именем а из цикла состоит в следующем: иначе расположить два соседних (к а) b -ребра; одно из них образует вместе с ребром а цикл а b из двух обычных рёбер, а другое соединяет два "дальних" конца этих b -рёбер. Это – частный случай двойной переклейки. Аналогично определяется вырезание из цепи обычного не-крайнего ребра, а для обычного крайнего ребра а, имеющего соседнее b, используется полуторная переклейка: ребро b зациклит ребро а; образуется цикл а b из обычных рёбер. Если обычное ребро без соседнего, то оно замыкается в цикл склейкой. Здесь и далее применяется правило (*), если возможно.

Нетривиальной назовём цепь, длины ≥3 или содержащую неотмеченное ребро. Замыкание нетривиальной цепи в цикл выполняется операцией склейки краёв цепи, если они оба a -свободные или оба b -свободные (с объединением особых вершин, если существуют). Иначе: один из краёв обычный или оба края особые и разноимённые. В первом случае выполним: обычный край объявим точкой, а её ребром замкнём оставшуюся цепь в цикл (склейка концов такой цепи разрешена). Во втором случае: удалим (=разрез) второе ребро цепи, первое останется как особое ребро, образовавшуюся цепь замкнём в цикл ребром с удалённым именем. В обоих случаях выполняется полуторная переклейка.

Общий графназывается финального вида, если он содержит лишь циклы из двух обычных рёбер (финальные циклы) и непомеченные (=обычные) точки. Тривиальным назовём цикл, состоящий из двух обычных рёбер или одного обычного и двух особых или из четырёх особых рёбер.

Задача приведения общего графа: найти линейный (по времени работы и используемой памяти) алгоритм, который преобразует любой данный общий граф указанными пятью операциями к финальному виду. При этом – число операций, последовательно выполняемых в этом преобразовании, минимально по сравнению с любой другой последовательностью операций (если цены операций не указаны, т.е. все их цены равны) или суммарная цена операций в искомой последовательности минимальна (если каждой операции приписана своя цена – положительное рациональное число).

Наиболее естественный (хотя и не оптимальный) алгоритм приведения общего графа G к финальному виду – автономное приведение, которое состоит в следующем. К каждой компоненте в G, независимо друг от друга, применяется следующая последовательность действий. Петля и особая точка удаляются; из цепи и нетривиального цикла вырезаются все обычные рёбра, нетривиальная цепь замыкается в цикл. Затем нетривиальный цикл (уже только из особых рёбер) последовательно разбивается на тривиальные циклы двойными переклейками. А именно, пока цикл нетривиальный, вырезаем из него пару соседних особых рёбер так же, как вырезали обычное ребро. При этом от цикла «отщепляется» тривиальный цикл и происходит объединение двух особых вершин в одну. Удаляем все оставшиеся особые вершины. Например, пусть есть участок abba в каком-то большом цикле; двойной переклейкой удаляем слева и справа a- соседей участка bb и заменяем их на два a- ребра, которые приводят к двум меньшим циклам, один из них – тривиальный цикл abb. В последнем удаляем особую вершину и получаем финальный цикл, в большем цикле объединяем особые вершины на концах a- ребра, которое стирается. Затем аналогично разбиваем больший цикл. Удаляем особые вершины из тривиальных цепей.

Автономной ценой C (G) графа G назовём суммарную цену указанной в автономном приведении последовательности операций.

Взаимодействием в G назовём некоторую фиксированную цепочку S операций, последовательно применяемых к G. КачествомP (S) взаимодействияS назовём величину P (S)= C (G)– C (S (G))– c (S), где S (G) – граф, полученный после применения последовательности S к G, c (S) – суммарная цена операций в S. Число P (S) показывает, какая цена экономится в результате применения S по сравнению с автономным приведением графа G, т.е. без использования взаимодействия S. Конечно, имеет смысл применять лишь взаимодействие с положительным качеством. Поиск таких S – весьма нетривиальная задача.

В зависимости от соотношения цен операций следующий основной алгоритм решает задачу приведения общего графа G к финальному виду, используя свой набор взаимодействий.

ЗАДАЧИ

a -Вершиной назовём a -точку или особую вершину при a -ребре (в том числе, при a -петле). Аналогично определяется b -вершина.

Привести общий граф к финальному виду операциями двойной переклейки и удаления особой вершины при следующих условиях на цены:

1) Цены операций равны 1 (бесценовой вариант);

2) Цена двойной переклейки равна 1, цена удаления равна 0.5 (стационарный малый вариант);

3) Цена двойной переклейки 1, цена удаления 1.5 (стационарный средний вариант);

4) Цена двойной переклейки 1, цена удаления 2.5 (стационарный большой вариант);

5) Цены двойной переклейки и удаления a -вершины 1, цена удаления b -вершины равна 1.5 (нестационарный вариант).

Граф задан ниже и состоит только из циклов и петель («циклический случай»).

 

Условия на общий граф G.

1. цикл (abab).

Решение. Для всех вариантов цен: вырежем обычное a -ребро, цикл разбивается на два финальных цикла.

 

2. цикл (aabab).

Решение. Для всех вариантов цен: вырежем обычное a -ребро, кроме финального цикла остаётся цикл (aab), удаляем его a -вершину.

 

3. цикл (aabbab).

Решение. Для всех вариантов цен: вырежем обычное a -ребро, кроме финального цикла остаётся цикл (aabb), удаляем его две особые вершины.

 

4. цикл (aabbaab).

Решение. Для всех вариантов цен: вырежем обычное b -ребро, объединим две a -вершины, кроме финального цикла остаётся цикл (aabb), удалим его две особые вершины.

 

5. цикл (aabbaabb).

Решение. Для всех вариантов цен, кроме третьего и четвёртого: вырежем пару соседних a -рёбер, при этом объединим две b -вершины и цикл разбивается на циклы (aab) и (aabb), удалим три особые вершины. Для третьего и четвёртого вариантов: инверсией (двойная переклейка, обращающая порядок букв в отрезке) перевернём отрезок aab с объединением двух b -вершин, получим цикл (aabbaab), затем как в задаче 4.

 

6. цикл (abb) и b -петля.

Решение. Для первого и второго варианта цен: удалим две особые вершины. Для других вариантов: двойной переклейкой вливаем петлю в цикл с объединением b -вершин, получим опять цикл (abb), удалим его b -вершину.

 

7. два циклa (baa).

Решение. Для всех вариантов цен, кроме четвёртого: удалим две a -вершины. Для четвёртого варианта: двойной переклейкой объединим два цикла в один цикл (aabab) с объединением двух a -вершин, затем как в задаче 2.

 

8. циклы (abb) и (aabb).

Решение. Для всех вариантов цен, кроме четвёртого: удалим три особые вершины. Для четвёртого варианта: двойной переклейкой объединим два цикла в один цикл (aabbab) с объединением двух b -вершин, затем как в задаче 3.

 

9. два цикла (aabb).

Решение. Для первого и второго варианта цен: удалим 4 особые вершины. Для других вариантов: двойной переклейкой объединим два цикла в один цикл (aabbaab) с объединением двух b -вершин, затем как в задаче 4.

 

10. цикл (aabbaabbaabb).

Решение. Для первого и второго вариантов цен: пока есть нетривиальный цикл вырезаем из него пару соседних особых ребер, в конце удалим особые вершины. Для третьего и четвёртого варианта: двойной переклейкой вырежем участок abba, разбивая цикл на циклы (aabb) и (aabbabb). Вырежем из последнего цикла обычное a -ребро, получим ещё один цикл (aabb); далее как в задаче 9. Для пятого варианта: пока есть нетривиальный цикл вырежем из него пару соседних особых a -рёбер, в конце удалим особые вершины (из них ровно одна b -вершина).

 

Привести общий граф к финальному виду четырьмя стандартными операциями и операцией удаления особой вершины (общий случай) при следующих условиях на цены:

1) Цены всех операций равны 1 (бесценовой вариант).

2) Цены стандартных операций равны 1, цена удаления равна 0.5 (стационарный малый вариант).

Указать взаимодействия (когда они есть) и их качества.

 

Условия на общий граф G. Выделенные крайние рёбра в цепях указаны подчёркиванием.

11. цепь [ abbaa ].

Решение. Для обоих вариантов цен: полуторной переклейкой вырежем обычное a -ребро, кроме финального цикла остаётся цепь [ b aa ], склейкой краёв замкнём её в цикл (aabb), удалим две его особые вершины.

 

12. цепь [ a bb a ].

Решение. Для обоих вариантов цен: склейкой краёв цепи с объединением двух a -вершин замкнём её в цикл (aabb), удалим две особые вершины.

 

13. цепь [ bbaa b ].

Решение. Для обоих вариантов цен: полуторной переклейкой отрежем крайнюю обычную вершину и замкнём (с объединением) получившуюся цепь в цикл (aabb), удалим две особые вершины.

 

14. цепь [ b aabb a ].

Решение. Для обоих вариантов цен: полуторной переклейкой отрежем крайнюю и вторую с краю вершины вместе с ребром между ними и замкнём (с объединением) получившуюся цепь в цикл (aabb), удалим две особые вершины.

 

15. цепи [ aa b ] и [ bb a ].

Решение. Для обоих вариантов цен: полуторной переклейкой отрежем крайнюю обычную вершину первой цепи и соединим (с объединением) a -вершину этой цепи с a -вершиной второй цепи (взаимодействие качества 2 для 1-го варианта и качества 1 для 2-го). Получим цепь [ bbaa b ], затем как в задаче 13.

 

16. цепь [ bbaabb ] и особая b -точка.

Решение. Для обоих вариантов цен: полуторной переклейкой отрежем крайнюю обычную вершину первой цепи и соединим (с объединением) b -вершину этой цепи с b -точкой (взаимодействие качества 1 для 1-го варианта и качества 0.5 для 2-го). Получим цепь [ bbaa b ], затем как в задаче 13.

 

17. цепи [ b aa ] и [ a bb a ].

Решение. Для обоих вариантов цен: полуторной переклейкой отрежем крайнюю обычную вершину первой цепи и соединим (с объединением) a -вершину этой цепи с a -вершиной второй цепи (взаимодействие качества 1 для 1-го варианта и качества 0.5 для 2-го). Получим цепь [ b aabb a ], затем как в задаче 14.

 

18. цепи [ bb a ] и [ aa ].

Решение. Для обоих вариантов цен: полуторной переклейкой отрежем крайнюю обычную вершину второй цепи и соединим (с объединением) a -вершину этой цепи с a -вершиной первой цепи (взаимодействие качества 1 для 1-го варианта и качества 0.5 для 2-го). Получим цепь [ bbaa ], затем как в задаче 13 (только без объединения).

 

19. цепи [ ab ] и [ aabb ].

Решение. Для первого варианта цен: полуторной переклейкой отрежем крайнюю обычную вершину второй цепи при a -ребре и соединим (с объединением) a -вершину этой цепи с a -вершиной первой цепи (взаимодействие качества 1). Получим цепь [ bbaa b ], затем как в задаче 13. Для второго варианта цен: автономно приведём каждую цепь к финальному виду: в первой цепи удалим две особые вершины, вторую – как описано ранее.

 

20. цепи [ ab ] и [ bb a ].

Решение. Для первого варианта цен: полуторной переклейкой отрежем крайнюю обычную вершину второй цепи и соединим (с объединением) b -вершину этой цепи с b -вершиной первой цепи (взаимодействие качества 1). Получим цепь [ a bb a ], затем как в задаче 12. Для второго варианта цен: автономно приведём каждую цепь к финальному виду.

 

21. две цепи [ aa b ].

Решение. Для первого варианта цен: склейкой соединим и объединим b -вершины цепей, получим цепь [ aabbaa ] (взаимодействие качества 1), затем приводим её автономно: склейка концов обычным b -ребром, его вырезание, удаление двух особых вершин. Для второго варианта цен: автономно приведём каждую цепь к финальному виду.

 

22. цепи [ aa b ], [ aabb ] и особая a -точка.

Решение. Для первого варианта цен: полуторной переклейкой отрежем крайнюю обычную вершину первой цепи и соединим (с объединением) a -вершину этой цепи с a -точкой, получим цепь [ ab ]. Затем как в задаче 19. Первые две операции – взаимодействие качества 2. Для второго варианта цен: первая операция такая же (взаимодействие качества 0.5), затем автономное приведение.

 

23. две цепи [ aa b ] и особая a -точка.

Решение. Для первого варианта цен: первая операция – как в задаче 22. Затем как в задаче 20 (с переменой местами a и b). Первые две операции – взаимодействие качества 2. Для второго варианта цен: первая операция такая же (взаимодействие качества 0.5), затем автономное приведение.

Альтернативное решение для первого варианта цен: первая операция – как в задаче 21. Затем как в задаче 16 (с переменой местами a и b). Первые две операции – взаимодействие качества 2.

 

Биоинформатика. Также см. мой курс прошлого года http://lpcs.math.msu.su/~lyubetsky/mfk2017/.

 

В Table 0 ниже выписаны имена видов, полезно загрузить файл mouse_pix.

Также полезен адрес http://www.ensembl.org/info/about/species.html.

ЗАДАНИЕ 1: выписать распределение генов мыши Mus_musculus по видам (есть/нет данный ген в данном виде и сколько его копий – «паралогов»). Рассматриваются виды из Таблицы 1 и гены из Таблицы 2. Использовать базу данных Ensembl.

Решение: зайти на сайт http://www.ensembl.org/Mus_musculus/Info/Index, написать идентификатор или имя гена (копировать из Таблицы 1), go, выбрать верхнюю мышь, выбрать опцию Gene gain / loss tree, списать числа при видах из Таблицы 2, числа появятся при листьях дерева. Занести числа в новую Таблицу 3 вида «число генов»Х«число видов».

Table 0.

#

Species