Обзор математических задач сравнительной геномики Адигеев М. Г. Ростов - на - Дону, 2010

План доклада O Основные понятия : гены, хромосомы, геном. O Выравнивание хромосом O Другие метрики O Медиана O Филогенетический анализ 2

Основные понятия O Геном = совокупность хромосом. O Каждая хромосома = последовательность нуклеотидов. Хромосома может быть линейной (linear) или кольцевой (circular). O Отдельные участки нуклеотидной последовательности образуют гены. O В математических моделях хромосомы представляются в виде цепочек либо нуклеотидов, либо сразу генов в зависимости от стоящей задачи. 3

Выравнивание последовательностей O Рассматриваются преобразования, действующие на отдельные нуклеотиды и участки хромосомы O Надо : сопоставить последовательности друг с другом таким образом, чтобы были по максимуму сопоставлены одинаковые участки 4

Выравнивание последовательностей AGACTAGTTAC CGA–––GACAC 5

Алгоритмы выравнивания 6 O Точечная матрица (dot matrix)

Алгоритмы выравнивания 7 O Алгоритм Нидлмана - Вунша ( глобальное выравнивание ) O Алгоритм Смита - Уотермана ( локальное выравнивание ) Матрица замещений : + штраф за разрыв

Другие метрики 8 Хромосома – последовательность генов. Можно представить перестановкой : Но есть несколько важных «но»… Или в виде графа:

Но 1 9 У хромосомы нет различия между началом и концом.

Но 2 10 Бывают циклические ( закольцованные ) хромосомы

Но 3 11 Надо учитывать ориентацию каждого гена в последовательности Поэтому рассматривают перестановки элементов со знаками

Breakpoint distance 12 Разрыв ( точка разрыва, breakpoint) - ситуация, когда в одной из хромосом гены g и h расположены рядом ( смежны, adjacent), а другая хромосома не содержит ни gh, ни –h–g. « Разрывная » метрика = количество таких разрывов.

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

Медиана геномов 14 O A и B – два генома, для которых мы хотим найти общего предполагаемого предка O Принцип экономии (parsimony principle) O Выберем метрику. Пусть d(X,Y) – расстояние между геномами X и Y O d(A, X) + d(B,X) min O Вводим « внешний » геном (outgroup) C

Медиана геномов 15 d(A, X) + d(B,X)+ d(C,X) min

Алгоритмы нахождения медианы 16 O Структура алгоритма и его сложность зависит от используемой метрики и вида генома : Одна или несколько хромосом Вид хромосом : линейные, кольцевые, смешанные O Для большинства вариантов задача является NP- трудной

Алгоритмы нахождения медианы 17

Алгоритмы нахождения медианы 18 Алгоритмы основаны на сведении к другим задачам : O Задача коммивояжёра При решении с помощью ДП : O(n 2 2 n ) O Задача целочисленного программирования Сложность : O(2 n ) O Задача о максимальном паросочетании. Сложность : O(n 3 )

Пример 19 O Метрика : разрывная (breakpoint distance) O Тип генома : мультихромосомный O Тип хромосомы : смешанная O Пусть Г множество всех генов из заданных геномов.

Пример 20 O Построим граф G, у которого вершины гены и их инверсии : g, –g. O Все вершины соединены рёбрами, и вес ребра (g, h) равен 3–u(g, h), где u(g, h) показывает, в скольких геномах (A, B, C) гены –g и h смежны. O Для каждого гена g вводим ребро (g, –g) с весом Z.

Задача коммивояжера 21

Пример 22 O Решаем задачу коммивояжёра O Получаем решение вида g1, -g1, g2, -g2,…,gn,-gn. O В этом случае медиана задаётся последовательностью g1,g2,…gn.

Пример 23

Пример 24 Исключение : O Разрывная метрика O Мультихромосомный геном O Смешанные или чисто линеные хромосомы Существует полиномиальный алгоритм ( сведение к задаче о максимальном паросочетании )

Филогенетическое дерево 25 O Обобщение задачи о медиане : ищем не одного предка, а множество предполагаемых предков ( видов ). O Строим дерево родственных связей – филогенетическое дерево

Филогенетическое дерево 26 Математическая формулировка : O Даны геномы G1, G2,…,Gn. O Построить дерево : G1, G2,…,Gn – листья Внутренние вершины – надо найти O Минимизировать суммарный вес дерева O Можно ограничиться вариантом : у всех внутренних вершин степень = 3

Филогенетическое дерево 27

Филогенетическое дерево 28 Два варианта : O Малая филогенетическая задача : Дерево известно Надо найти геномы для внутренних вершин O Большая филогенетическая задача : Дерево тоже не известно Сводится к задаче о дереве Штейнера

Способы решения 29 O Перебор всех вариантов и выбор наилучшего Факт : в уже заполненном филогенетическом дереве геном, которым помечена внутренняя вершина, является медианой относительно соседних вершин Поэтому порядок решения МФЗ такой : 1. Инициализируем внутренние вершины. 2. Решаем задачи о медианах от листьев к « корню ». 3. Если геномы изменились – повторяем п.2.

Способы решения 30 O Сразу строить решение ( дерево и геномы ) Пока есть только эвристические алгоритмы … Например : построить граф разрывов (breakpoint graph) и с помощью набора преобразований построить для него дерево, близкое к оптимальному.

Способы решения 31

Основные источники O Fertin G, Labarre A, Rusu I, Tannier E, Vialette S: Combinatorics of Genome Rearrangements. MIT Press; O Mount D.W. Bioinformatics. Sequence and genome analysis. Spring Harbor Press, May O Blanchette M., Bourque G., Sankoff D. Breakpoint Phylogenies. [ pdf] O Tannier E., Zheng C., Sankoff D. Multichromosomal median and halving problems under different genomic distances. [ pdf] O Sankoff D., El-Mabrouk N. Genome Rearrangement. [jiangbook.pdf] O Niklas Eriksen Combinatorics of Genome Rearrangements and Phylogeny. [lic.pdf] O Jason D. Bakos, Panormitis E. Elenis, A Special-Purpose Architecture for Solving the Breakpoint Median Problem. IEEE Trans. On Very Large Scale Integration (VLSI) SYSTEMS, Vol. 16, No. 12, December