Байкал 23 августа 2011

Лингвистика
Байкал
23 августа 2011

Лингвистика
Байкал
23 августа 2011

Лингвистика
Байкал
23 августа 2011

Анализ данных
Байкал
23 августа 2011

Анализ
символьных последовательностей
от биоинформатики до лингвистики
М.А. Ройтберг
Байкал
23 августа 2011
ЦЕЛИ
Знакомство с биоинформатикой
(анализ данных в биоинформатике)
Математические этюды

Проблематика
(молекулярная биология)
Медицинские приложения (разработка лекарств, медицинская генетика, персональная медицина)
Исследования механизмов функционирования клетки (и надклеточных структур): молекулярная биология, биофизики, биохимия…
Теория эволюции, систематика, филогения

ДНК: 2 нити; L ~ 105 – 109
нуклеотиды (4)

An Example: t-RNA
From Paul Higgs
РНК: 1 нить; L ~ 102 – 103 нуклеотиды (4)

Белки: 1 нить; L ~ 102 – 103
аминокислоты (20)
PDB ID: 2act E.N. Baker, E.J. Dodson (1980):
The structure of actinidin at 1.7 Ångstroms

…Gly + Ala… = …GA…

Данные: последовательности
Не только последовательности
1. Пространственные структуры
- сравнение, анализ (пример: «докинг»)
2. Генные сети
3. «Секвенирование»
4. «Экспрессия генов»

Основные задачи анализа последовательностей
1. Сравнение
- сопоставление в целом (в т.ч. - множественное); определение количественной меры сходства последовательностей в целом;
поиск общих мотивов; поиск в базах данных;
2. Аннотация (описание)
поиск и выделение функционально значимых участков (заданных «паттернов»);
разбиение последовательности на «однородные» участки;
определение статистической значимости результатов сравнения и поиска.
3. Структуры
- предсказание; сравнение (обогащенные последовательности)

ИСТОРИЯ и ДЛИНЫ
tRNA - (1964) - 75 bases (old, slow, complicated method)
First complete DNA genome: X174 DNA (1977) - 5386 bases
human mitochondrial DNA (1981) - 16,569 bases
tobacco chloroplast DNA (1986) - 155,844 bases
First complete bacterial genome (H. Influenzae)(1995) - 1.9 x 10^6 bases
Yeast genome (eukaryote at ~ 1.5 x 10^7) completed in 1996
Several archaebacteria
E. coli -- 4 x 10^6 bases [1998]
Several pathogenic bacterial genomes sequenced
Helicobacter pyloris, Treponema pallidium, Borrelia burgdorferi, Chlamydia trachomatis, Rickettsia prowazekii, Mycobacterium tuberculosis
Nematode C. elegans ( ~ 4 x 10^8) - December 1998
Human genome (rough draft completed 2000) - 3 x 10^9 base
2010 – rat, mouse, pig, fugu, etc, full genomes 50 x 10^9
~2015 – individual human genomes (“$1000 per genome”)

План доклада
Выравнивания.
Динамическое программирование, графы и алгебра
Поиск локальных сходств, затравки
Структуры РНК
Гиперграфы и контекстно-свободные грамматики
Конечные автоматы и вероятности
Разные примеры

Тема 1. Выравнивание

Варианты выравниваний
Выровнять две символьные последовательности – удалить из них несколько фрагментов так, чтобы оставшиеся последовательности имели одинаковую длину.
--ПОДБЕРЕЗОВИК ПОДБЕРЕЗОВИК--
ПРЕДОСИНОВИЧКИ ПРЕДОСИНОВИЧКИ
ПО-ДБЕРЕЗОВИК-- П-ОДБЕРЕЗОВИК--
ПРЕДОСИН-ОВИЧКИ ПРЕД-ОСИНОВИЧКИ
ПО-ДБЕРЕЗОВИ-К-
ПРЕД-ОСИНОВИЧКИ

Какой вариант выбрать?
А) Б)
--ПОДБЕРЕЗОВИК ПОДБЕРЕЗОВИК-- ПРЕДОСИНОВИЧКИ ПРЕДОСИНОВИЧКИ
В) Г) Д)
ПО-ДБЕРЕЗОВИК-- П-ОДБЕРЕЗОВИК-- ПО-ДБЕРЕЗОВИ-К-
ПРЕДОСИН-ОВИЧКИ ПРЕД-ОСИНОВИЧКИ ПРЕД-ОСИНОВИЧКИ
Предполагается: последовательности были получены редактированием» («эволюцией») из общего предка.
Требуется: установить соответствующие друг другу участки

Какой вариант выбрать?
Нужно «знать» что-нибудь про эволюцию
А) Б)
--ПОДБЕРЕЗОВИК ПОДБЕРЕЗОВИК-- ПРЕДОСИНОВИЧКИ ПРЕДОСИНОВИЧКИ
В) Г) Д)
ПО-ДБЕРЕЗОВИК-- П-ОДБЕРЕЗОВИК-- ПО-ДБЕРЕЗОВИ-К-
ПРЕДОСИН-ОВИЧКИ ПРЕД-ОСИНОВИЧКИ ПРЕД-ОСИНОВИЧКИ
Предположим:
Две одинаковые буквы скорее имеют общего предка, чем две разные буквы
Две буквы «одинаковой гласности» скорее имеют общего предка, чем две буквы «разные гласности»

Две одинаковые буквы скорее имеют общего предка, чем две разные буквы
Две буквы «одинаковой гласности» скорее имеют общего предка, чем две буквы «разные гласности»
А) Б)
--ПОДБЕРЕЗОВИК ПОДБЕРЕЗОВИК-- ПРЕДОСИНОВИЧКИ ПРЕДОСИНОВИЧКИ
В) Г) Д)
ПО-ДБЕРЕЗОВИК-- П-ОДБЕРЕЗОВИК-- ПО-ДБЕРЕЗОВИ-К-
ПРЕДОСИН-ОВИЧКИ ПРЕД-ОСИНОВИЧКИ ПРЕД-ОСИНОВИЧКИ
Г) лучше, чем В); Б) [немного] лучше А)
??? Верно ли, что
Г ) лучше, чем Б )

Две одинаковые буквы скорее имеют общего предка, чем две разные буквы
Две буквы «одинаковой гласности» скорее имеют общего предка, чем две буквы «разные гласности»
А) Б)
--ПОДБЕРЕЗОВИК ПОДБЕРЕЗОВИК-- ПРЕДОСИНОВИЧКИ ПРЕДОСИНОВИЧКИ
В) Г) Д)
ПО-ДБЕРЕЗОВИК-- П-ОДБЕРЕЗОВИК-- ПО-ДБЕРЕЗОВИ-К-
ПРЕДОСИН-ОВИЧКИ ПРЕД-ОСИНОВИЧКИ ПРЕД-ОСИНОВИЧКИ
??? Верно ли, что
Г ) лучше, чем Б )
=== НЕИЗВЕСТНО. Мы ничего не предположили о механизме удалений/вставок (насколько они вероятны по сравнению с заменами)

Вес выравнивания
A T – V V I — - T G S
G S M V L L E F S G T
0+2 +3+2+3 +2+7+2= 21
-1 -2 = -3
Score = Σ m(i,j)-GapPen = 21 - 3 = 18
Матрица весов замен m(a, b)
Штраф за удаление
символа δ = -1
GapPen – сумма щтрафов за удаления

Вес выравнивания
A T – V V I — - T G S
G S M V L L E F S G T
0+2 +3+2+3 +2+7+2= 21
-1 -2 = -3
Штраф за удаление символа: δ =-1
Матрица весов замен: m(a,b)
Score = Σ m(i,j)-GapPen = 21 - 3 = 18
GapPen – сумма штрафов за удаления.
Score -> MAXIMUM

~ L4
- произвольная функция
– выпуклая функция
*********************************
– линейная f(L) = a + bL
(Смит-Уотерман)
– линейная f(L) = kL
- нулевая f(L) = 0
~ L4
~ L3
~ L2
~
(зависит от п-стей)
~ L2
Штраф за делецию f(L) Время работы

Эталонные выравнивания

Структурное и алгоритмическое выравнивания
Str) 40 сопоставлений
lkCnqli...PPFWKTCPKGKNLCYKmtmraapmvPVKRGCidv
riCfnhqssqPQTTKTCSPGESSCYHkqwsdfrgtIIERGCg.. * **************** ******
1 16 6
AlgSW)
1 16 6
* **************** ******
lk..C...nqliPPFWKTCPKGKNLCYK...mtmraapmvPVKRGCidv ..riCfnhqssqPQTTKTCSPGESSCYHkqwsdfrgt...IIERGC..g
35 сопоставлений

Str)
lkCnqli...PPFWKTCPKGKNLCYKmtmraapmvPVKRGCidv
riCfnhqssqPQTTKTCSPGESSCYHkqwsdfrgtIIERGCg..
* **************** ******
1 16 6
AlgSW)
1 16 6
* **************** ******
lk..C...nqliPPFWKTCPKGKNLCYK...mtmraapmvPVKRGCidv ..riCfnhqssqPQTTKTCSPGESSCYHkqwsdfrgt...IIERGC..g
S = 40 I = 23 A= 35 Точность Acc = I/S= 23/40=0.58 Достоверность Conf = I/A= 23/35=0.66

%ID
Алгоритм
Смита-Уотермана (SW)
не может восстановить
структурное выр-ние
при ID< 0.3

Проблемы:
1. Белки( алгоритм Смита-Уотермана):
- не работает при слабом сходстве; причина этого не известна;
- нет обоснования для штрафов за делеции
2. ДНК (геномы)
- недостаток быстродействия
- нет эталонных выравниваний

Проблемы
3. Классы штрафных функций:
- расширить классы штрафных функций делеций, для которых существуют алгоритмы данной сложности
4* Алгоритмы: анализ общих основ, выяснение границ применимости

Str)
lkCnqli...PPFWKTCPKGKNLCYKmtmraapmvPVKRGCidv
riCfnhqssqPQTTKTCSPGESSCYHkqwsdfrgtIIERGCg..
^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Остров1 Остров 2
Острова – безделеционные фрагменты выравниваний.
Вес острова – сумма весов сопоставлений
1. Причины плохого качества выравниваний SW

SW выравнивания
структурные выравнивания
Island score
% островов
1. Причины плохого качества выравниваний SW

Тема 1. Динамическое программирование

Рекурсия для глобального выравнивания
(δ(L)=kL)
v, w - слова; a, b – буквы
S(v, w) – вес оптимального выравнивания v, w.
S(va, wb) = max{
S(v, w) + m(a,b), // сопоставление последних букв
S(v, wb) – k; // удаление посл. буквы в 1-м слове
S(va, w) - k // удаление посл. буквы в 2-м слове
}

Ориентированный ациклический граф с весами на ребрах
Вершина
Ребро
Ребра направлены и снабжены весами.
Путь: ABCE
W(ABCE) =
= 3+11+ 3 = 17
Источник: A; Сток: Z
Нет циклов

Пути (примеры):
BEZ = {(BE), (EZ)} (длина 2);
вес W(BEZ) = 7 + 5 = 12
BCEZ = {(BC), (CE), (EZ)} (длина 3);
W(BCEZ) = 11+ 3 +5 = 19
Полный путь (длина 4); :
ADBEZ =
={(AD), (DB), (BE), (EZ)}
W(ADBEZ) = 14+6+7 + 5 = 32

Полные пути –
пути из источника в сток (примеры):
ADEZ: длина = 3;
вес W(ADEZ) = 14+ 7 + 5 = 26;
ABCFZ: длина = 4;
вес W(ABCFZ) = 3+7+ 2 + 7 = 19

ДАНО: Ориентированный ациклический
граф с весами на ребрах
G =< V, E, W; A, Z>
ЗАДАЧА 1 (задача Беллмана) Найти оптимальный полный путь, т.е. полный путь, имеющий минимальный (максимальный) возможный вес.

Пример: предсказание 3D структуры белков
(гемоглобин, код белка 1ash, цепь А)

Дано: последовательность аминокислот
Надо: где образуются спирали
Дано: последовательность аминокислот
Надо: где образуются спирали

ДАНО: Ориентированный ациклический
граф с весами на ребрах
G =< V, E, W; A, Z>
ЗАДАЧА 1 (задача Беллмана) Найти оптимальный полный путь, т.е. полный путь, имеющий минимальный (максимальный) возможный вес.

Метод динамического программирования
(Алгоритм Беллмана, 1953)
Проход от стока к источнику:
из W есть путь в V =>
=> W обрабатывается позже, чем V.
Рекуррентное уравнение
BestW(A) = min{
W(AB) + BestW(B),
W(AC) + BestW(С),
W(AD) + BestW(D)
}

BestW(B) =
= min{
W(BC) + BestW(C),
W(BD) + BestW(D),
W(BE) + BestW(E),
}

BestW(B) =
= min{
W(BC) + BestW(C),
W(BD) + BestW(D),
W(BE) + BestW(E),
}
Best Weight: 13
Best Path: ACEZ

BestW(A) =
= min{
W(AB) + BestW(B),
W(AC) + BestW(C),
W(AD) + BestW(D),
}
Для любой вершины T:
BestW (T) = min{
W(T N1) + BestW(N1),
…..,
W(T Nt) + BestW(Nt),
} где
N1, ..., Nt – все наследники T

ВРЕМЯ РАБОТЫ ~ к-во РЕБЕР
ПАМЯТЬ ~ к-во ВЕРШИН

1.2. Алгебраическая основа алгоритма Беллмана
1. Динамическое программирование, графы и алгебра

Задача-подсказка
S =
= a1 ⋅ b1 + a1 ⋅ b2 + ... + a1 ⋅ b1000 +
+ a2 ⋅ b1 + a2 ⋅ b2 + ... + a2 ⋅ b1000 +
+ ... +
+ a1000 ⋅ b1 + a1000 ⋅b2 + ... + a1000 ⋅ b1000
Найти сумму 1 000 000 слагаемых за < 5000 операций.

Решение
S = a1 ⋅ (b1 + b2 + ... + b1000 ) +
+ a2 ⋅ (b1 + b2 + ... + b1000 ) +
+ ... +
+ a1000 ⋅ (b1 + b2 + ... + b1000 ) =
= (a1 + a2 + ... + a1000 ) ⋅ (b1 + b2 + ... + b1000 )
*** Алгоритм ***
A = a1 + a2 + ... + a1000 // 999 операций
B = b1 + b2 + ... + b1000 // 999 операций
S = A ⋅ B // 1 операция
*** Всего: 2001 операций

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1
Повторение: 1-й класс ☺

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Повторение: 1-й класс ☺

Мультипликативные веса путей
BEZ = {(BE), (EZ)} (длина 2);
вес W(BEZ) = 7 + 5 = 12
мультипликативный вес (м-вес)
WM(BEZ) = 7•5 = 35
BCEZ = {(BC), (CE), (EZ)} (длина 3);
W(BCEZ) = 11+ 3 +5 = 19
WM(BCEZ)=11•3•5=165
Полный путь (длина 4); :
ADBEZ =
={(AD), (DB), (BE), (EZ)}
W(ADBEZ) = 14+6+7 + 5 = 32
WM(ADBEZ) = 14•6•7•5 = 2940

ДАНО: Ориентированный ациклический
граф с весами на ребрах
G =< V, E, W; A, Z>
ЗАДАЧА 2 («задача Больцмана») Найти сумму мультипликативных весов всех полных путей.
Лю́двиг Больцман (нем. Ludwig Eduard Boltzmann, 1844 - 1906), основатель
статистической механики и молекулярно-кинетической теории

Лю́двиг Больцман (Ludwig Eduard Boltzmann, 1844 – 1906; Австро-Венгрия, Италия), основатель
статистической меха-ники и молекулярно-кинетической теории
Лю́двиг Больцман (Ludwig Eduard Boltzmann, 1844 – 1906; Австро-Венгрия, Италия), основатель
статистической меха-ники и молекулярно-кинетической теории
Эрнст Изинг (Ernst Ising, 1900-1998, Германия-США) - физик, позже - педагог, автор модели Изинга (см. предсказание спиралей в белке и т. п.)

Интерпретации:
1. Вероятность прохода лабиринта: Вершины – города; Ребра - дороги;
Вес ребра: вероятность перехода по ребру (сумма вероятностей выхода из вершины может быть меньше 1)
Статистическая физика – без
комментариев

Проход от стока к источнику:
из W есть путь в V =>
=> W обрабатывается позже, чем V. Пример: вершина B.
Пути из B в Z: BCEZ, BCFZ, BDZ, BDEZ, BEZ
Sum(B) = M(BCEZ) + M(BCFZ) +
+ M(BDZ) + M(BDEZ) +
+ M(BEZ) =
= W(BC)*M(CEZ) + W(BC)*M(CFZ) +
+W(BD)*M(DZ) + W(BD)*M(DEZ) +
+W(BE)* M(EZ) =
= W(BC)*(M(CEZ) + M(CFZ)) +
+ W(BD)*(M(DZ) + M(DEZ)) +
+ W(BE)* M(EZ) = ….

Проход от стока к источнику:
из W есть путь в V =>
=> W обрабатывается позже, чем V. Пример: вершина B.
Пути из B в Z: BCEZ, BCFZ, BDZ, BDEZ, BEZ
Sum(B) =…
= W(BC)*(M(CEZ) + M(CFZ)) +
+ W(BD)*(M(DZ) + M(DEZ)) +
+ W(BE)* M(EZ) =
= W(BC)* Sum(C) +
+ W(BD)* Sum(D) +
+ W(BE)* Sum(E)

Проход от стока к источнику:
из W есть путь в V =>
=> W обрабатывается позже, чем V.
Пример: вершина B.
Пути из B в Z: BCEZ, BCFZ, BDZ, BDEZ, BEZ
Sum(B) = M(BCEZ) + M(BCFZ) +
+ M(BDZ) + M(BDEZ) +
+ M(BEZ) =
Рекуррентное уравнение (сумма м-весов):
Sum(A) =
W(AB)*Sum(B) +
+ W(AC)*Sum(C) +
+ W(AD)*Sum(D)
}

Проход от стока к источнику:
из W есть путь в V =>
=> W обрабатывается позже, чем V.
Рекуррентное уравнение (минимальный путь)
BestW(A) = min{
W(AB) + BestW(B),
W(AC) + BestW(C),
W(AD) + BestW(D)
}
Рекуррентное уравнение (сумма м-весов):
Sum(A) =
W(AB)*Sum(B) +
+ W(AC)*Sum(C) +
+ W(AD)*Sum(D)
}

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Что использовали?

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Что использовали?

Sum(B) =
= M(BCEZ) + M(BCFZ) + M(BDZ) + M(BDEZ) + M(BEZ) =
= W(BC)*M(CEZ) + W(BC)*M(CFZ) +
+W(BD)*M(DZ) + W(BD)*M(DEZ) +
+W(BE)* M(EZ) =
= W(BC)*(M(CEZ) + M(CFZ)) +
+ W(BD)*(M(DZ) + M(DEZ)) +
+ W(BE)* M(EZ) =
= W(BC)*(M(CEZ) + M(CFZ)) +
+ W(BD)*(M(DZ) + M(DEZ)) +
+ W(BE)* M(EZ) =
= W(BC)* Sum(C) +
+ W(BD)* Sum(D) +
+ W(BE)* Sum(E)

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Что использовали?

Sum(B) =
= M(BCEZ) + M(BCFZ) + M(BDZ) + M(BDEZ) + M(BEZ) =
= W(BC)*M(CEZ) + W(BC)*M(CFZ) +
+W(BD)*M(DZ) + W(BD)*M(DEZ) +
+W(BE)* M(EZ) =
= W(BC)*(M(CEZ) + M(CFZ)) +
+ W(BD)*(M(DZ) + M(DEZ)) +
+ W(BE)* M(EZ) =
= W(BC)*(M(CEZ) + M(CFZ)) +
+ W(BD)*(M(DZ) + M(DEZ)) +
+ W(BE)* M(EZ) =
= W(BC)* Sum(C) +
+ W(BD)* Sum(D) +
+ W(BE)* Sum(E)

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Что использовали?

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение Умножение a+b = b+a a*b = b*a
Нейтральный элемент:
Сложение Умножение
a+0 = 0+a =а a*1 = 1*a = a
Обратные элементы (3-й класс☺) :
Сложение Умножение
a+(-a) = 0 a*(1/a) = 1a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Что использовали?

Сочетательный закон (ассоциативность):
Сложение Умножение
(a+b)+c = a+(b+c) (a*b)*c = a*(b*c)
Переместительный закон (коммутативность):
Сложение a+b = b+a
Нейтральный элемент:
Умножение
a*1 = 1*a = a
РАСПРЕДЕЛИТЕЛЬНЫЙ ЗАКОН (ДИСТРИБУТИВНОСТЬ)
умножение относительно сложения
(a+b)*c = a*c + b*c a*(b+c) = a*b+a*c
Это называется полукольцо ☺

Полукольцо A – это множество, на котором заданы две бинарные всюду определенные операции + и * («сложение» и «умножение»), удовлетворяющие следующим свойствам:
операции + и * ассоциативны;
операция + коммутативна, коммутативность операции * не обязательна;
в A есть правый нейтральный элемент относительно операции *;
Операции и обычно называют сложением и умножением.
+ - «целевая» операция
* - «соединительная»
операция

Примеры полуколец.
Первая операция – аналог сложения («целевая операция»), вторая – аналог умножения («соединяющая операция»):
на числах: {+, x}, {max, +}; {max, min};
на множествах: {∪, ∩}
на множествах слов: {∪, •}
на матрицах: {+, x}.
+ - «целевая» операция
* - «соединительная»
операция

ДАНО: Ориентированный ациклический
граф с весами на ребрах
G =< V, E, W; A, Z>
ЗАДАЧА 1 Найти оптимальный полный путь,
т.е. полный путь, имеющий минимальный
(максимальный) возможный вес.
ЗАДАЧА 2 Найти сумму
мультипликативных
весов всех полных путей.

Метод динамического программирования
(Алгоритм Беллмана)
Проход от стока к источнику:
из W есть путь в V =>
=> W обрабатывается позже, чем V.
Рекуррентное уравнение (минимальный путь)
BestW(A) = min{
W(AB) + BestW(B),
W(AC) + BestW(C),
W(AD) + BestW(D)
}
Рекуррентное уравнение (сумма м-весов):
Sum(A) =
W(AB)*Sum(B) +
+ W(AC)*Sum(C) +
+ W(AD)*Sum(D)
}

ДАНО: Ориентированный ациклический
граф с весами на ребрах
G =< V, E, W; A, Z>;
веса W(e) – элементы полукольца K с операциями + и *.
ЗАДАЧА 3 Найти сумму
мультипликативных
весов всех полных путей.
Операция * («умножение»)
определяет веса путей
(«соединительная операция»).
Операция + («сложение»)
определяет целевую функцию
(«соединительная операция»).

ВРЕМЯ РАБОТЫ ~ к-во РЕБЕР
ПАМЯТЬ ~ к-во ВЕРШИН
ДАНО: Ориентированный ациклический
граф с весами на ребрах
G =< V, E, W; A, Z>;
веса W(e) – элементы полукольца K с операциями + и *.
ЗАДАЧА 3 Найти сумму
мультипликативных
весов всех полных путей.

Замечание 1.
Память
ВРЕМЯ РАБОТЫ ~ к-во РЕБЕР
ПАМЯТЬ ~ к-во ВЕРШИН
ПАМЯТЬ МОЖЕТ БЫТЬ МЕНЬШЕ !
(если в графе можно выделить «слои»)
Пример: нахождение веса оптимального выравнивания (но не самого выравнивания !)
Space ~ L1 = SQRT(|Vertex|)
!! Выравнивание тоже можно найти с памятью Space ~ L1 и временем Time ~ L1*L2, но для этого нужны новые идеи [Hirschberg D.S. Algorithms for the Longest Common Subsequence Problem. // Journal of the ACM . 1977. Vol. 24 , N.4. P. 664 – 675. ]

Замечание 2.
Различие между min и суммой: argmin
Рекуррентное уравнение (минимальный путь)
BestW(V) = min{
W(VB) + BestW(B),
W(VC) + BestW(C),
W(VD) + BestW(D) }
Рекуррентное уравнение (сумма Больцмана)
Sum(V) = ∑{
W(VB) * BestW(B),
W(VC) * BestW(C),
W(VD) * BestW(D) }
Операция min предполагает не только получение числа, но и (неявно) выбор одного из операндов. Поэтому при работе с min мы кроме значения веса «оптимального» пути находим и сам оптимальный путь.
Для этого при вычислении значения BestW(V) = min{…} мы запоминаем дополнительно argmin{…} – наследника (-ков) вершиныV, на котором (-рых) минимум достигается.
Примеры были раньше.

Раздел 3
Гиперграфы: знакомство
Пока без слайдов ☹
Развернутый план
1. Задача о триангуляции выпуклого треугольника. Неправильное решение. Сведение задачи к нескольким подзадачам меньшего размера. Невозможность моделирования этого с помощью задач на ориентированных графах.
2. Понятие гиперграфа. Гиперребро. Гиперпуть. Вес гиперребра. Вес гиперпуть.
3. Задача Больцмана для гиперграфов. Рекурсия и алгоритм решения. Понятие ранга вершины для гиперграфов.

3.1. Задача о триангуляции
(рисунок на доске)
Идея сведения: провести диагональ, разбить на два многоугольника меньшего размера
Недостатки:
много промежуточных задач
нет взаимно-однозначного соответствия между структурами и последовательностью сведений
!!!! Сведения образуют не последовательность, а дерево!!!
? НЕ СВОДИТСЯ К ЗАДАЧЕ НА ГРАФЕ !!!

Задача о триангуляции
(рисунок на доске)
Идея сведения: провести диагональ, разбить на два многоугольника меньшего размера
Недостатки:
много промежуточных задач
нет взаимно-однозначного соответствия между структурами и последовательностью сведений
!!!! Сведения образуют не последовательность, а дерево!!!
? НЕ СВОДИТСЯ К ЗАДАЧЕ НА ориентированном ГРАФЕ
Сводится к задаче на ориентированном ГИПЕРГРАФЕ!!

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

�3.2. Понятие гиперграфа
Определение 1. Граф G – это пара
, где V – это множество вершин, E – множество ребер .
Ребро – это пара
, где V – начальная вершина ребра, W- конечная вершина ребра
V W
Определение 2. Гиперграф Y – это пара
, где V – это множество вершин, H – множество гиперребер.
Гиперребро – это пара
, где V – начальная вершина ребра,
, - упорядоченный набор конечных вершин гиперребра
W1 W2 W3
V
.

�3.2. Понятие гиперграфа
Определение 3. Путь в графе G=
– это простая цепь, узлы которой помечены вершинами графа G, такая что ….
Начальная вершина пути – это вершина, которой помечена первый узел цепи, конечная вершина – вершина, которой помечен последний узел цепи.
Определение 4. Гиперпуть в гиперграфе Y=
, > – это упорядоченное дерево, узлы которой помечены вершинами графа G, такое что ….
Начальная вершина пути – это вершина, которой помечен корень дерева, конечные вершины – это вершины, которыми помечены листья дерева.

Гиперпуть

An Example: t-RNA
From Paul Higgs
Вторичная структура РНК.

3. Выравнивание последовательностей
РНК с заданной вторичной структурой.

Пример: РНК и гиперпуть

Тема 4. Поиск локальных сходств
Использование затравок (seed)
Избирательность и чувствительность
Типы затравок (seed model)

Затравки: фильтрация пространства поиска
Сначала ищем небольшие и легко диагностируемые участки сходства («затравочные сходства», seed similarities).
Далее ищем сходства только в окрестностях затравочных сходств (одного или нескольких).

«Классическая затравка»
(пример: 6 совпадений подряд)
Точные совпадения :
Затравка («затравочное слово», описание затравочных сходств) : ######
Вес : 6 [количество #]
Пример : 16 совпадений из 20
ATCAGT
||||||
ATCAGT
######
ATCAGTGCAATGCTCATGAA
|||.|.|||||||:||.|||
ATCGGCGCAATGCGCAAGAA

Затравка ловит сходство
(затавка соответствует сходству)
Затравка ##### ? seed
Затравочное сходство (… выравнивание) ATGCAA
ATGCAA
Затравка соответствует сходству в позиции 10 Затравка не соответствует сходству в позиции 1
Затравка ловит сходство
###### ######
1 10

Недостатки подхода
Случайное сходство
Пропущенное сходство: не содержит затравок
######
ATCAGTGCAATGCTCATGAA
::|::::||||||:::..::
CCCGACACAATGCGTGACCC
##☹### [16 of 20!]
ATCAGTGCGATGCTCATGAA
|||.|||||:|||:||.|||
ATCGGTGCGGTGCGCAAGAA

Две проблемы
“Избирательность”
Затравка может НЕ быть частью важного (для нас) сходства
“Чувствительность”
Важное (для нас) сходство может НЕ содержать ни одной затравки
Нужно уточнить:
Что такое «важное сходство»?

Что может быть мерой избирательности и чувствительности
Избирательность затравки: ~ 4-weight вероятность ее обнаружения при сравнении независимых случайных последовательностей
Чувствительность затравки:
вероятность того, что затравка попадет в важное сходство.
Нужно уточнить:
Что такое «важное сходство»?
Каково распределение вероятностей для важных сходств?

Множество важных [целевых] выравниваний и их вероятности
Выравнивания фиксированной длины без удалений
L=18
Вероятностная модель: Бернулли ;
Случайные вырaвнивания: Prob(match) =0.25
Целевые выравнивания: Prob(match) >> 0.25
Обобщения: Марковские модели, скрытые марковские модели (сегодня не рассматриваем)
GCTACGACTTCGAGCTGC
...CTCAGCTATGACCTCGAGCGGCCTATCTA...

Разреженные затравки
Ma, Tromp, Li 2002 (PatternHunter)
Затравка: ###--#-##
‘#’ : должно быть совпадение
‘-’ : «джокер» (“все равно, что” )
Вес : 6 [количество #]
Пример:
###--#-##
ATCAGTGCAATGCTCAAGA
|||||.||.||||:|||||
ATCAGCGCGATGCGCAAGA

Разреженные затравки: в чем преимущество?
For spaced seeds, hits at subsequent positions are “more independent events”
For contiguous vs. spaced seeds of the same weight, the expected number of hits is (basically) the same but the probabilities of having at least one hit are very different

Sensitivity: PH weight 11 seed vs BLAST 11 & 10
[after Ma, Tromp and Li]

single filter based on several distinct seed patterns
each seed pattern detects a part of interesting similarities but together they detect [almost] all of them
Li, Ma, Kisman, Tromp 2004 (PatternHunter II)
Kucherov, Noe, Roytberg, 2005
Sun, Buhler, RECOMB 2004
Семейства затравок

Пример: ВСЕ (18,3)
Обнаружить все сходства длины 18,
в которых не более 3 несовпадений
Чувствительность = 1.0
Избирательность
(вероятность случайного появления затравочного сходства) -> MIN

Пример: ВСЕ (18,3)
Обнаружить все сходства длины 18,
в которых не более 3 несовпадений
Множественная затравка F решает проблему ВСЕ(18, 3)
Затравка F состоит из двух простых затравок, каждая из них имеет вес 7

Пример: ВСЕ (18.3)
###-##---#-###
###---#--##-#
###---#--##-#
w=7
w=9

####
###-##
Пример: ВСЕ (18.3).
Избирательности
w=4 ~39. 10-4
w=5 ~9.8 10-4
w=7 ~1.2 10-4
w=9 ~0.23 10-4
Избирательность семейства затравок – вероятность встретить хотя бы одну из них в случайном месте (p(match) = 1/4)

СПАСИБО за ВНИМАНИЕ
0. Введение
1. Выравнивания
2. ДП и алгебра
3. Гипернрафы и РНК
4. Разреженные затравки
Чего не было:
Сравнительная геномика
Разработка лекарств
Клеточные автоматы….

Инициальный (гипер) путь
Терминальный (гипер) путь
Полный (гипер) путь

Вес гиперпути
ДОПИСАТЬ !!!
М-ВЕС НАД ПОЛУКОЛЬЦОМ

3.3. Задача Больцмана для гиперграфов.
.
Формулировка задачи Больцмана.
.

�Подход к решению
Терминальная сумма Больцмана вершины V:
F(V) – множество всех терминальных гиперпутей с начальной вершиной V.
Sum(V) = ∑{M(T)| T∈ F(V) }
Идея: Найти терминальные суммы Больцмана для всех вершин. Вершины перебираются в порядке возрастания рангов.
Уточнить: что такое ранг вершины в гиперграфе (= максимальная высота гиперпути с данной начальной вершиной)
Пока считаем ранги известными

�Терминальные суммы Больцмана для гиперребер
Терминальная сумма Больцмана гиперребра y:
FF(y) – множество всех терминальных гиперпутей с начальной вершиной V.
S(y) = ∑{M(T)| T∈ Fr(y) }
Start(V) – множество всех гиперребер с начальной вершиной V.
Утверждение.
Sum(V) = ∑{S(y)| y∈ Start(V) }

�Терминальные суммы Больцмана для гиперребер: рекурсия
Утверждение.
Пусть y = - гиперребро. Тогда
S(y) = W(y)*Sum(W1)*…* Sum(Wk)
Доказательство. Пусть T ∈ Fr(y),
Ti – поддерево T с корнем в узле, соответствующем i-й конечной вершине гиперрбра y – начального гиперребра дерева T.
Тогда:
1) Ti ∈ F(Wi)
2) существует взаимно-однозначное соответствие между деревьями
T ∈ Fr(y) и наборами
,
где Ti ∈ F(Wi), i =1,…, k
=>

�Терминальные суммы Больцмана для гиперребер: рекурсия
2) существует взаимно-однозначное соответствие между дере-вьями T ∈ Fr(y) и наборами
, где Ti ∈ F(Wi), i =1,…, k
=>
S(y) = ∑{M(T)| T∈ Fr(y) } =
= ∑… ∑{W(y)*M(T1)*…*M(Tk)| T1∈ F(w1, …, F(Wk) } =
= W(y)*∑… ∑{M(T1)*…*M(Tk)| T1∈ F(w1, …, F(Wk) } =
[СУММА ПРОИЗВЕДЕНИЙ = ПРОИЗВЕДЕНИЕ СУММ]
= W(y)* ∑{M(T1)| T1∈ F(w1}* …
…* ∑{M(T1)| T1∈ F(w1} =
= W(y)*Sum(W1)*…* Sum(Wk)