Парное выравнивание FVAH F I AG V DE G A TANL NI. - презентация

1 Парное выравнивание FVAH F I AG V DE G A TANL NI

2 Редакционное расстояние и утилита diff howtocookfor----humans howtocook---fourhumans howtocookfo-rhumans howtocookfourhumans вес = 8 вес = 17

3 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

4 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

5 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

6 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

7 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

8 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

9 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

10 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

11 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

12 Динамическое программирование ЛЯГУШКА start ЕЕ Г У Л Г Я Г Ш Е Е end ЛЯГУ--ШКА --ГУЛЯШ--

13 Динамическое программирование ЛЯГУШКА 0 Г У Л Я Ш

14 ЛЯГУШКА 0 Е -1 Г У Л Я Ш Л -

15 Динамическое программирование ЛЯГУШКА 0 Е -1 Е -2 Г У Л Я Ш ЛЯ --

16 Динамическое программирование ЛЯГУШКА 0 Е -1 Е -2 Е -3 Е -4 Е -5 Е -6 Е -7 Г У Л Я Ш ЛЯГУШКА

17 Динамическое программирование ЛЯГУШКА 0 Е -1 Е -2 Е -3 Е -4 Е -5 Е -6 Е -7 Г Г -1 У Л Я Ш - Г

18 Динамическое программирование ЛЯГУШКА 0 Е -1 Е -2 Е -3 Е -4 Е -5 Е -6 Е -7 Г Г -1 Е -2 или Г -2 У Л Я Ш -Л Г- Л- -Г или

19 Динамическое программирование ЛЯГУШКА 0 Е -1 Е -2 Е -3 Е -4 Е -5 Е -6 Е -7 Г Г -1 Е Г -2 Е Г -3 У Л Я Ш ЛЯГ -- Г ЛЯГ- --- Г -ЛЯГ Г---

20 Динамическое программирование ЛЯГУШКА 0 Е -1 Е -2 Е -3 Е -4 Е -5 Е -6 Е -7 Г Г -1 Е Г -2 Е Г -3 Е -2 Е -3 Е -4 Е -5 У Г -2 Е Г -3 Е Г -4 Г -2 0 Е -1 Е -2 Е -3 Л Г -3 Е -2 Е Г -3 Г -1 Е Г -2 Е Г -3 Е Г -4 Я Г -4 Г -2 0 Е -1 Е Г -2 Е Г -3 Е Г -4 Е Г -5 Ш Г -5 Г -3 Г -1 Е Г -2 Е Г -3 Е -1 Е -2 ЛЯГУ--ШКА --ГУЛЯШ-- --ЛЯГУШКА ГУЛЯ--Ш-- или

21 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK 0 I G D

22 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I 1 G D W(V,I)=1

23 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I1 Е0Е0 G D W(G,I)=0

24 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10 Е -1 G D W(K,I)=-3

25 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10-1 G-2 Г0Г0 D W(G,V)=0

26 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10-1 G-20 5 D W(G,G)=4

27 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10-1 G-205 Е4Е4 D W(K,G)=-8

28 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10-1 G-2054 D-3 Г -1 W(V,D)=-5

29 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10-1 G-2054 D-3 Г4Г4 W(G,D)=-6

30 Вспомним про биологию Разные буквы в тексте – это разные буквы, а вот два разных аминокислотных остатка могут быть более или менее похожи. Значит, надо ввести меру сходства для каждой возможной пары остатков. Тогда ходить по диагоналям можно всегда, но для разных пар за такой переход будут разная цена, равная этой мере сходства: VGK I10-1 G-2054 D-34 ЕГ3ЕГ3 W(K,D)=-5

31 Алгоритм Нидльмана – Вунша То, что было описано сейчас решает задачу ГЛОБАЛЬНОГО ВЫРАВНИВАНИЯ алгоритмом Нидльмана – Вунша. Он применяется если вам нужно сопоставить друг другу последовательности целиком и вы знаете, что они сильно похожи.

32 Локальное выравнивание (алгоритм Смита – Ватермана) Задача здесь чуть-чуть другая – в двух последовательностях выделить один «общий» фрагмент с наибольшим весом. То есть последовательности целиком могут быть не особенно-то и похожи, но у них есть схожие участки. В двух словах: глобальное выравнивание сравнивает две версии одного текста, а локальное выравнивание ищет плагиат в двух по большей части разных текстах.

33 Наилучшее общее подвыравнивание ЛЯГУШКА 0 Е -1 Е -2 Е -3 Е -4 Е -5 Е -6 Е -7 Г Г -1 Е Г -2 Е Г -3 Е -2 Е -3 Е -4 Е -5 У Г -2 Е Г -3 Е Г -4 Г -2 0 Е -1 Е -2 Е -3 Л Г -3 Е -2 Е Г -3 Г -1 Е Г -2 Е Г -3 Е Г -4 Я Г -4 Г -2 0 Е -1 Е Г -2 Е Г -3 Е Г -4 Е Г -5 Ш Г -5 Г -3 Г -1 Е Г -2 Е Г -3 Е -1 Е -2 ЛЯГУ--ШКА --ГУЛЯШ-- --ЛЯГУШКА ГУЛЯ--Ш-- или

34 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR 0 V D G W

35 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR 00 V D G W

36 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V0 D0 G0 W0

37 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V0 3 D0 G0 W0

38 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V03 Е2Е2 Е1Е1 Е0Е0 D0 G0 W0

39 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V03210 D0 Г2Г2 ЕГ1ЕГ100 G0 W0

40 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V03210 D02100 G0 Е1Е1 ЕГ0ЕГ0 5 Е4Е4 W0

41 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V03210 D02100 G01054 W000 Г4Г4 ЕГ3ЕГ3

42 Локальное выравнивание (алгоритм Смита – Ватермана) Технически это все – то же самое, что и глобальное выравнивание, только появляется дополнительная опция – если вес должен стать меньше нуля, можно просто поставить ноль. А искать надо не полный путь, а такой подпуть, чтобы вес в его конце был наибольшим по всей матрице. VKGR V03210 D02100 G01054 W00043 VK-G V-DG V-DG VK-G

43 Матрицы BLOSUM Henikoff, Henikoff, 1992: BLOSUM (BLOcks of Amino Acid SUbstitution Matrix).

44 Штрафы за гэп По-честному, никакой строгой теории здесь нет. Ясно, только то, что раз это слитные последовательности белков, то редко бывает 5 вставок по одному остатку и гораздо чаще – одна вставка 5 остатков. Поэтому веса с гэпами устроены так, что чем больше вставка, тем меньше за нее надо платить (как с кока-колой). Штрафы за гэп представляют в виде суммы штрафа за открытие (gap open) и штрафа за удлинение (gap extend), притом первый обычно значительно больше второго (например, 10 и 1). Это называется аффинные штрафы за гэп. За вставку 5 остатков, соответственно, надо платить 10+4*1=14 единиц веса.