Распознавание регуляторных сигналов Факультет биоинженерии и биоинформатики МГУ, первый набор, второй курс. Май 2004 М. Гельфанд (лекции) Д. Равчеев (задания) - презентация

1 Распознавание регуляторных сигналов Факультет биоинженерии и биоинформатики МГУ, первый набор, второй курс. Май 2004 М. Гельфанд (лекции) Д. Равчеев (задания) А. Герасимова, Э. Пермина (занятия) В.Ю. Макеев (некоторые слайды)

2 Транскрипция и трансляция в прокариотах

3 Сплайсинг (эукариоты)

4 Инициация транскрипции

5 Регуляция транскрипции в прокариотах

6 Структура ДНК-связывающего домена (cI)

7 Структура ДНК-связывающего домена (Cro)

8 Белок-ДНКовые взаимодействия

9 Регуляция транскрипции у эукариот

10 Регуляторные модули (В.А.Макеев) Один и тот же ген может регулироваться несколькими регуляторными модулями, работающими в разных условиях Расстояние от регуляторного модуля до кодирующих областей может достигать пар оснований

11 Представление сигналов Консенсус Pattern («образец» - консенсус с вырожденными позициями) Позиционная весовая матрица (или профиль) positional weight matrix, PWM, profile Логические правила РНКовые сигналы – вторичная структура

12 Консенсус codB CCCACGAAAACGATTGCTTTTT purE GCCACGCAACCGTTTTCCTTGC pyrD GTTCGGAAAACGTTTGCGTTTT purT CACACGCAAACGTTTTCGTTTA cvpA CCTACGCAAACGTTTTCTTTTT purC GATACGCAAACGTGTGCGTCTG purM GTCTCGCAAACGTTTGCTTTCC purH GTTGCGCAAACGTTTTCGTTAC purL TCTACGCAAACGGTTTCGTCGG consensus ACGCAAACGTTTTCGT

13 Образец codB CCCACGAAAACGATTGCTTTTT purE GCCACGCAACCGTTTTCCTTGC pyrD GTTCGGAAAACGTTTGCGTTTT purT CACACGCAAACGTTTTCGTTTA cvpA CCTACGCAAACGTTTTCTTTTT purC GATACGCAAACGTGTGCGTCTG purM GTCTCGCAAACGTTTGCTTTCC purH GTTGCGCAAACGTTTTCGTTAC purL TCTACGCAAACGGTTTCGTCGG consensus ACGCAAACGTTTTCGT pattern aCGmAAACGtTTkCkT

14 Матрица частот I = j b f(b,j)[log f(b,j) / p(b)] Информационное содержание

15 Logo

16 Позиционная весовая матрица (профиль)

17 Вероятностная мотивировка: лог-правдоподобие (с точностью до линейного преобразования) Ещё одна: z-score (при соответствующем основании логарифма) Термодинамическая мотивировка: свободная энергия (в предположении независимости соседних позиций) Псевдоотсчеты (pseudocounts)

18 Логические правила, деревья и т.п. – учет зависимостей

19 Составление выборки Начало: –GenBank –специализированные банки данных –литература (обзоры) –литература (оригинальные статьи) Исправление ошибок Проверка литературных данных предсказанные сайты. Удаление дубликатов

20 Перевыравнивание Первоначальное выравнивание по биологическим признакам –промоторы: старт транскрипции –участки связывания рибосом: стартовый кодон –сайты сплайсинга: экзон-интронные границы Выделение сигнала в скользящем окне Перевыраванивание и т.д., пока не сойдётся

21 Начала генов Bacillus subtilis dnaN ACATTATCCGTTAGGAGGATAAAAATG gyrA GTGATACTTCAGGGAGGTTTTTTAATG serS TCAATAAAAAAAGGAGTGTTTCGCATG bofA CAAGCGAAGGAGATGAGAAGATTCATG csfB GCTAACTGTACGGAGGTGGAGAAGATG xpaC ATAGACACAGGAGTCGATTATCTCATG metS ACATTCTGATTAGGAGGTTTCAAGATG gcaD AAAAGGGATATTGGAGGCCAATAAATG spoVC TATGTGACTAAGGGAGGATTCGCCATG ftsH GCTTACTGTGGGAGGAGGTAAGGAATG pabB AAAGAAAATAGAGGAATGATACAAATG rplJ CAAGAATCTACAGGAGGTGTAACCATG tufA AAAGCTCTTAAGGAGGATTTTAGAATG rpsJ TGTAGGCGAAAAGGAGGGAAAATAATG rpoA CGTTTTGAAGGAGGGTTTTAAGTAATG rplM AGATCATTTAGGAGGGGAAATTCAATG

22 dnaN ACATTATCCGTTAGGAGGATAAAAATG gyrA GTGATACTTCAGGGAGGTTTTTTAATG serS TCAATAAAAAAAGGAGTGTTTCGCATG bofA CAAGCGAAGGAGATGAGAAGATTCATG csfB GCTAACTGTACGGAGGTGGAGAAGATG xpaC ATAGACACAGGAGTCGATTATCTCATG metS ACATTCTGATTAGGAGGTTTCAAGATG gcaD AAAAGGGATATTGGAGGCCAATAAATG spoVC TATGTGACTAAGGGAGGATTCGCCATG ftsH GCTTACTGTGGGAGGAGGTAAGGAATG pabB AAAGAAAATAGAGGAATGATACAAATG rplJ CAAGAATCTACAGGAGGTGTAACCATG tufA AAAGCTCTTAAGGAGGATTTTAGAATG rpsJ TGTAGGCGAAAAGGAGGGAAAATAATG rpoA CGTTTTGAAGGAGGGTTTTAAGTAATG rplM AGATCATTTAGGAGGGGAAATTCAATG cons. aaagtatataagggagggttaataATG num

23 dnaN ACATTATCCGTTAGGAGGATAAAAATG gyrA GTGATACTTCAGGGAGGTTTTTTAATG serS TCAATAAAAAAAGGAGTGTTTCGCATG bofA CAAGCGAAGGAGATGAGAAGATTCATG csfB GCTAACTGTACGGAGGTGGAGAAGATG xpaC ATAGACACAGGAGTCGATTATCTCATG metS ACATTCTGATTAGGAGGTTTCAAGATG gcaD AAAAGGGATATTGGAGGCCAATAAATG spoVC TATGTGACTAAGGGAGGATTCGCCATG ftsH GCTTACTGTGGGAGGAGGTAAGGAATG pabB AAAGAAAATAGAGGAATGATACAAATG rplJ CAAGAATCTACAGGAGGTGTAACCATG tufA AAAGCTCTTAAGGAGGATTTTAGAATG rpsJ TGTAGGCGAAAAGGAGGGAAAATAATG rpoA CGTTTTGAAGGAGGGTTTTAAGTAATG rplM AGATCATTTAGGAGGGGAAATTCAATG cons. tacataaaggaggtttaaaaat num

24 Позиционное информационное содержание до и после перевыравнивания

25 позиционные частоты после перевыравнивания (паттерн aGGAGG)

26 Поиск сигнала с самого начала (ab initio) дискретные подходы: считать слова и образцы непрерывные подходы: оптимизация профиля

27 Как считать короткие слова Рассмотрим все слова длины k (k-меры) Для каждого k-мера вычислим количество последовательностей, которые его содержат –(не обязательно в точности) Выберем самый частый k-мер

28 Проблема: Полный перебор возможен только для относительно коротких слов Предположение: если длинное слово встречается часто, его подслова тоже будут часто встречаться Решение: выбрать набор частых коротких слов и склеить в длинное

29 Как считать длинные слова Рассмотрим некоторые k-меры Для каждого k-мера вычислим количество последовательностей, которые его содержат –(не обязательно в точности) Выберем самый частый k-мер

30 Проблема: «некоторые» k-меры - это какие? 1 я попытка: те, которые встречаются в выборке Но: сигнал (консенсусный k-мер) может и не встретиться.

31 2 я попытка: те, которые встречаются в выборке и похожие на них. Но: –опять же, сигнал может и не попасть в это множество; –а размер множества «похожих» слов растёт экспоненциально

32 Теоретико-графовый подход Каждый k-мер в каждой последовательности соответствует вершине. Два k-мера соединены ребром, если они похожи (например, отличаются не более, чем в h позиций, h

33 Простой алгоритм Удалить все вершины, которые не могут быть продолжены до полных графов –то есть, не имеют ребер во все доли Из списка пар вершин удалить все, которые не могут быть продолжены до полных графов –то есть не образуют треугольники с третьими вершинами во всех долях И т.д.. (не будет в такой форме работать для поиска плотных подграфов)

34 Оптимизация. Expectation - Maximization Породим начальное множество профилей (например, каждый из имеющихся k-меров породит один профиль) Для каждого профиля: –найти наилучшего представителя в каждой последовательности –обновить профиль Повторять пока не сойдётся

35

36 Этот алгоритм сходится, но не может покинуть область локального максимума. Поэтому если начальное приближение было плохим, он сойдётся к ерунде. Решение: стохастическая оптимизация.

37 Имитация теплового отжига Цель: максимизировать информационное содержание I I = j b f(b,j)[log f(b,j) / p(b)] или любой другой функционал, измеряющий однородность множества сайтов

38 Алгоритм Обозначим: A – текущий сигнал (множество потенциальных сайтов), I(A) – его информационное содержание. B – сигнал, отличающийся от А выбором сайта в одной последовательности, I(B) – его информационное содержание. если I(B) I(A), B принимается если I(B) < I(A), B принимается с вероятностью P = exp [(I(B) – I(A)) / T] Температура T медленно снижается, первоначально она такова, что почти все изменения принимаются (Р близко к 1).

39 Gibbs sampler Опять, A – сигнал, I(A) – его информационное содержание. На каждом шаге в одной последовательности выбирается новый сайт с вероятностью P ~ exp [(I(A new )] Для каждого потенциального сайта подсчитывается, сколько раз он был выбран. (Замечание: сигнал всё время меняется)

40

41 Использование свойств сигнала ДНК-связывающие белки и их сигналы Кооперативные однородные палиндромы прямые повторы Кооперативные неоднородные кассеты Другие РНКовые сигналы

42 Распознавание: весовые матрицы (профили) Позиционные веса нуклеотидов W(b,j)=ln(N(b,j)+0.5) – 0.25 i ln(N(i,j)+0.5) Вес потенциального сайта b 1 …b k – это сумма соответствующих позиционных весов: S(b 1 …b k ) = j=1,…,k W(b j,j)

43 Усиление слабого сигнала

44 Распределение весов сайтов связывания рибосом на сайтах (зеленый) и не-сайтах (красный)

45 Нейронные сети: архитектура 4 k входных нейронов (сенсоров), присутствие конкретного нуклеотида в конкретной позиции (да/нет) или 2 k нейронов (пурин/пиримидин, AT/GC) один или более слоёв внутренних нейронов один выходной нейрон (сайт/не-сайт)

46 каждый нейрон связан соединениями с нейронами соседнего уровня каждому соединению приписан вес Нейрон: суммирует (с весами) входящие сигналы сравнивает результат с порогом (или преобразует по заданному правилу) если сумма выше порога, отправляет сигнал всем нейронам следующего уровня (или просто преобразованное значение)

47 Обучение: Обработать сайты и не-сайты из обучающей выборки одни за одним, несколько полных итераций. Для каждого объекта сделать предсказание. Если оно неправильное, изменить веса. Сети отличаются архитектурой, способом обработки сигнала, расписанием обучения

48 Оценка качества алгоритмов Чувствительность: правильно предсказанные / все правильные Специфичность: правильно предсказанные / все предсказанные Трудно составить тестирующую выборку: –неизвестные сайты –активация в определенных условиях –неспецифическое связывание

49 Промоторы E. coli профиль, предсказывающий 1 сайт на 2000 нт, имеет чувствительность: –25% на всех промоторах, –60% на конститутивных (неактивируемых) промоторах

50 Эукарио- тические промоторы

51 Сайты связывания рибосом Надежность предсказания зависит от информационного содержания

52 CRP (E. coli)

53 Запись GenBank для гена E. coli

54 Что же делать? филогенетическое картирование: правильные сайты консервативны

55 Консервативная область

56 Менее консервативная область

57 rbsD в энтеробактериях: ответ Sty AGGGTTACACTGCGGC-CAGCGAAACGTTTCGCTAGTGGAGCAGAAAAATGAAGAAAGGC Sen AGGGTTACACTGCGGC-CAGCGAAACGTTTCGCTAGTGGAGCAGAAAAATGAAGAAAGGC Stm GGGGTTACACTGCGGC-CAGCGAAACGTTTCGCTAGTGGAGCAGAAAAATGAAGAAAGGC Eco AGGATTAAACTGTGGGTCAGCGAAACGTTTCGCTGATGGAGAA-AAAAATGAAAAAAGGC Ype TTTTCTAAACTCCTTGTTAGCGAAACGTTTCGCTCTTGGAGTA-GATCATGAAAAAAGGT ** *** **************** ***** * * ***** ***** Sty ACCGTACTCAACTCTGAAATCTCGTCGGTCATTTCCCGTCTGGGGCATACTGATACTCTG Sen ACCGTACTCAACTCTGAAATCTCGTCGGTCATTTCCCGTCTGGGGCATACTGATACTCTG Stm ACCGTACTCAACTCTGAAATCTCGTCGGTCATTTCCCGTCTGGGGCATACTGATACTCTG Eco ACCGTTCTTAATTCTGATATTTCATCGGTGATCTCCCGTCTGGGACATACCGATACGCTG Ype GTATTACTGAACGCTGATATTTCCGCGGTTATCTCCCGTCTGGGCCATACCGATCAGATT * ** ** **** ** ** **** ** *********** ***** *** *

58 Регулирующие модули обычно консервативны и часто содержат кластеры сходных сайтов связывания одинаковых молекул фактора (В.Макеев)

59

60 rVISTA:все / выравненные / консервативные сайты

61 ура!