БиоФизика ЭконоИнформатика СоциоЛингвистика Байкал 23 августа 2011. - презентация

1 БиоФизика ЭконоИнформатика СоциоЛингвистика Байкал 23 августа 2011

2 БиоФизика ЭконоИнформатика СоциоЛингвистика Байкал 23 августа 2011

3 БиоФизика ЭконоИнформатика СоциоЛингвистика Байкал 23 августа 2011

4 БиоФизика ЭконоИнформатика СоциоЛингвистика Байкал 23 августа 2011

5 Анализ данных Байкал 23 августа 2011 Тексты, графы Биология Информатика Лингвистика

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

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

8

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

10

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

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

13 …Gly + Ala… = …GA…

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

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

16 ИСТОРИЯ и ДЛИНЫ tRNA - (1964) - 75 bases (old, slow, complicated method) First complete DNA genome: X174 DNA (1977) bases human mitochondrial DNA (1981) - 16,569 bases tobacco chloroplast DNA (1986) - 155,844 bases First complete bacterial genome (H. Influenzae)(1995) 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)

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

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

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

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

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

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

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

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

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

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

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

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

29 Str) lkCnqli...PPFWKTCPKGKNLCYKmtmraapmvPVKRGCidv riCfnhqssqPQTTKTCSPGESSCYHkqwsdfrgtIIERGCg.. * **************** ****** AlgSW) * **************** ****** 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

30 %ID SW точность (acc) < 0,10,037 0,1-0,30,306 0,3-0,40,818 >0,40,893 Алгоритм Смита-Уотермана (SW) не может восстановить структурное выр-ние при ID< 0.3

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

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

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

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

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

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

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

38 38 Пути (примеры): BEZ = {(BE), (EZ)} (длина 2); вес W(BEZ) = = 12 BCEZ = {(BC), (CE), (EZ)} (длина 3); W(BCEZ) = = 19 Полный путь ( длина 4); : ADBEZ = ={(AD), (DB), (BE), (EZ)} W(ADBEZ) = = 32 A C Z B E F D

39 39 Полные пути – пути из источника в сток (примеры): ADEZ: длина = 3; вес W(ADEZ) = = 26; ABCFZ: длина = 4; вес W(ABCFZ) = = 19 A C Z B E F D

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

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

42

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

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

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

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

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

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

49 49 ВРЕМЯ РАБОТЫ ~ к-во РЕБЕР ПАМЯТЬ ~ к-во ВЕРШИН A C Z B E F D

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

51 51 Задача-подсказка S = =a 1 b 1 + a 1 b a 1 b a 2 b 1 + a 2 b a 2 b a 1000 b 1 + a 1000 b a 1000 b 1000 Найти сумму слагаемых за < 5000 операций.

52 52Решение S = a 1 (b 1 + b b 1000 ) + +a 2 (b 1 + b b 1000 ) a 1000 (b 1 + b b 1000 ) = = (a 1 + a a 1000 ) (b 1 + b b 1000 ) *** Алгоритм *** A = a 1 + a a 1000 // 999 операций B = b 1 + b b 1000 // 999 операций S = A B // 1 операция ***Всего: 2001 операций

53 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-й класс

54 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*ca*(b+c) = a*b+a*c Повторение: 1-й класс

55 55 Мультипликативные веса путей BEZ = {(BE), (EZ)} (длина 2); вес W(BEZ) = = 12 мультипликативный вес (м-вес) WM( BEZ ) = 75 = 35 BCEZ = {(BC), (CE), (EZ)} (длина 3); W(BCEZ) = = 19 WM( BCEZ )=11 35=165 Полный путь ( длина 4); : ADBEZ = ={(AD), (DB), (BE), (EZ)} W(ADBEZ) = = 32 WM(ADBEZ) = = 2940 A C Z B E F D

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

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

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

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

60 60 A C Z B E F D Проход от стока к источнику: из 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)

61 61 A C Z B E F D Проход от стока к источнику: из 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) }

62 62 A C Z B E F 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) }

63 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*ca*(b+c) = a*b+a*c Что использовали?

64 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*ca*(b+c) = a*b+a*c Что использовали?

65 65 A C Z B E F D 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)

66 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*ca*(b+c) = a*b+a*c Что использовали?

67 67 A C Z B E F D 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)

68 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 Что использовали?

69 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 Что использовали?

70 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*ca*(b+c) = a*b+a*c Это называется полукольцо

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

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

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

74 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) }

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

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

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

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

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

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

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

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

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

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

85 Гиперпуть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

111 111 Терминальные суммы Больцмана для гиперребер: рекурсия Утверждение. Пусть 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 =>

112 112 Терминальные суммы Больцмана для гиперребер: рекурсия 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)

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