'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7


Слайд 8

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


Слайд 9


Слайд 10

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


Слайд 11

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


Слайд 12

…Gly + Ala… = …GA…


Слайд 13

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


Слайд 14

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


Слайд 15

ИСТОРИЯ и ДЛИНЫ 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”)


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

24   Вес выравнивания 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 = S m(i,j)-GapPen = 21 - 3 = 18 Матрица весов замен m(a, b) Штраф за удаление символа ? = -1 GapPen – сумма щтрафов за удаления


Слайд 24

  Вес выравнивания 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 = S m(i,j)-GapPen = 21 - 3 = 18 GapPen – сумма штрафов за удаления. Score -> MAXIMUM


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

Рекурсия для глобального выравнивания (?(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-м слове }


Слайд 36

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


Слайд 37

38 Пути (примеры): 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


Слайд 38

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


Слайд 39

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


Слайд 40

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


Слайд 41


Слайд 42

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


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

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


Слайд 47

48 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


Слайд 48

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


Слайд 49

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


Слайд 50

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


Слайд 51

52 Решение 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 операций


Слайд 52

53 Сочетательный закон (ассоциативность): Сложение Умножение (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-й класс ?


Слайд 53

54 Сочетательный закон (ассоциативность): Сложение Умножение (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-й класс ?


Слайд 54

55 Мультипликативные веса путей 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


Слайд 55

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


Слайд 56

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


Слайд 57

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


Слайд 58

59 Проход от стока к источнику: из 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) = ….


Слайд 59

60 Проход от стока к источнику: из 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)


Слайд 60

61 Проход от стока к источнику: из 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) }


Слайд 61

62 Проход от стока к источнику: из 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) }


Слайд 62

63 Сочетательный закон (ассоциативность): Сложение Умножение (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 Что использовали?


Слайд 63

64 Сочетательный закон (ассоциативность): Сложение Умножение (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 Что использовали?


Слайд 64

65 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)


Слайд 65

66 Сочетательный закон (ассоциативность): Сложение Умножение (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 Что использовали?


Слайд 66

67 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)


Слайд 67

68 Сочетательный закон (ассоциативность): Сложение Умножение (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 Что использовали?


Слайд 68

69 Сочетательный закон (ассоциативность): Сложение Умножение (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 Что использовали?


Слайд 69

70 Сочетательный закон (ассоциативность): Сложение Умножение (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 Это называется полукольцо ?


Слайд 70

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


Слайд 71

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


Слайд 72

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


Слайд 73

74 Метод динамического программирования (Алгоритм Беллмана) Проход от стока к источнику: из 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) }


Слайд 74

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


Слайд 75

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


Слайд 76

Замечание 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. ]


Слайд 77

78 Замечание 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, на котором (-рых) минимум достигается. Примеры были раньше.


Слайд 78

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


Слайд 79

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


Слайд 80

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


Слайд 81

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


Слайд 82

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


Слайд 83

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


Слайд 84

Гиперпуть


Слайд 85

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


Слайд 86

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


Слайд 87

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


Слайд 88

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


Слайд 89

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


Слайд 90

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


Слайд 91

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


Слайд 92

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


Слайд 93

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


Слайд 94

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


Слайд 95

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


Слайд 96

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


Слайд 97

Разреженные затравки: в чем преимущество? 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


Слайд 98

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


Слайд 99

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 Семейства затравок


Слайд 100

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


Слайд 101

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


Слайд 102

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


Слайд 103

#### ###-## Пример: ВСЕ (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)


Слайд 104

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


Слайд 105

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


Слайд 106

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


Слайд 107

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


Слайд 108

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


Слайд 109

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


Слайд 110

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


Слайд 111

112 ?Терминальные суммы Больцмана для гиперребер: рекурсия 2) существует взаимно-однозначное соответствие между дере-вьями T ? Fr(y) и наборами <T1, …, Tk>, где 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)


Слайд 112

Осталось: 1. Вычисление рангов вершин гиперграфа. Решение задачи Больцмана, когда порядок просмотра вершин гиперграфа неизвестен. 2. Вычисление специальных сумм Больцмана. 3. Разбор примеров. 4. Решение задачи про триангуляцию.


×

HTML:





Ссылка: