Содержание
-
БІОІНФОРМАТИКА к.б.н. Нипорко О. Ю. Київський національний університет ім. Тараса Шевченка Інститут високих технологій
-
При аналізі первинних структур процедура вирівнювання виявляє сходство між послідовностями (sequence similarity), яке може свідчити про гомологію (homology), тобто еволюційну спорідненість макромолекул. Основний спосіб визначити схожість двох послідовностей - вирівняти їх Геп – пропуск в послідовності >EC_Tr : MQNRLTIKDIARLSGVGKSTVSRVLNNE---YR >EC_Fr : ----MKLDEIARLAGVSRTTASYVINGKAKQYR
-
Гомологичные последовательности – последовательности, имеющие общее происхождение (общего предка). Признаки гомологичности белков сходная 3D-структура в той или иной степени похожая аминокислотная последовательность разные другие соображения…
-
Что изображено?
Название последовательности Номер столбца выравнивания Номер последнего в строке остатка ИЗ ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ Консервативный остаток Функционально консервативная позиция
-
«Идеальное» выравнивание – запись последовательностей одна под другойтак, чтобы гомологичные фрагментыоказались друг под другом. домовойскупидомводомерка ? лесовоз ---лесо---воз ледоход лед---оход--- ? Гэп – пропуск в последовательности
-
Множественное выравнивание: Попарное выравнивание:
-
Ортологи и паралоги
Ортологи – гени з різних організмів, що розійшлися при видоутворенні. Мається на увазі, що ортологи мають спільного «предка» і однакову функцію (якщо тиск відбора слабкий, то функція может «плисти»). Паралоги – гени, що розійшлися при дуплікації («копіюванні»). Копії гена не зазнавали тиска відбора, а значить, могли змінити функцію.
-
Множественное выравнивание: содержание
Определение, разновидности, решаемые задачи, общие проблемы Глобальное выравнивание Прогрессивное выравнивание Итерационные методы Локальные множественные выравнивания Вероятностно-статистические методы множественного выравнивания Оценка качества выравнивания Структурное выравнивание
-
Выравнивание полных геномов:крыса – мышь – человек
-
Множественное выравнивание: иллюстрации
-
Множественное выравнивание:определение и проблемы
Определение: найти оптимальное соответствие между несколькими последовательностями, если заданы Матрица соответствия Штраф за делецию Функция веса выравнивания Проблемы: Множество делеций, замен,… Ограниченное обобщение метода динамического программирования Подсчет суммарного веса замен в колонке Размещение делеций в разных пос-стях и штрафы за них
-
Множественное выравнивание:проблемы (прод.)
Проблемы: Локальные минимумы накопление первоначальных ошибок в иерархических алгоритмах лучшее дерево соответствует лучшему выравниванию Выбор параметров один набор параметров не может быть пригодным на все случаи жизни Сложности выравнивания нарастают с ростом различий между последовательностями
-
Множественное выравнивание:решаемые задачи
Поиск мотивов (блоков) – коротких сигнатур, идентифицируемых в консервативных участках множественного выравнивания отсутствие вставок и делеций Построение профилей (матриц весов): оценка частоты встречаемости каждой АК в каждой позиции Построение скрытых марковских моделей (HMM) – обобщенных профилей, описываемых строго математически
-
Паттерн – регулярное выражение UNIX’a: [AC]-x-V-x(4)-{ED} Ala или Cys- х-Val- х- х- х - х-(любой, но не Glu и не Asp) Выравнивание хорошо изучен-ного семейства Функционально важные остатки 4-5 консервативных остатков Паттерн Если находим только«пра-вильные», то ОК Если много лишнего, то увеличиваем паттерн Поиск в UniProt
-
Профиль или весовая матрица (PSSM)
Seq1 FK L L S H C L L V Seq2 FK A F G Q T M F Q Seq3 Y P I V G Q E L L G Seq4 FP V V K E A I L K Seq5 FK V LA A V I A D Seq6 L E F I S E C I I Q Seq7 FK L L G N V L V C A -18 -10 -1 -8 8 -3 3 -10 -2 -8 C -22 -33 -18 -18 -22 -26 22 -24 -19 -7 D -35 0 -32 -33 -7 6 -17 -34 -31 0 E -27 15 -25 -26 -9 23 -9 -24 -23 -1 F 60 -30 12 14 -26 -29 -15 4 12 -29 G -30 -20 -28 -32 28 -14 -23 -33 -27 -5 H -13 -12 -25 -25 -16 14 -22 -22 -23 -10 I 3 -27 21 25 -29 -23 -8 33 19 -23 K -26 25 -25 -27 -6 4 -15 -27 -26 0 L 14 -28 19 27 -27 -20 -9 33 26 -21 M 3 -15 10 14 -17 -10 -9 25 12 -11 N -22 -6 -24 -27 1 8 -15 -24 -24 -4 P -30 24 -26 -28 -14 -10 -22 -24 -26 -18 Q -32 5 -25 -26 -9 24 -16 -17 -23 7 R -18 9 -22 -22 -10 0 -18 -23 -22 -4 S -22 -8 -16 -21 11 2 -1 -24 -19 -4 T -10 -10 -6 -7 -5 -8 2 -10 -7 -11 V 0 -25 22 25 -19 -26 6 19 16 -16 W 9 -25 -18 -19 -25 -27 -34 -20 -17 -28 Y 34 -18 -1 1 -23 -12 -19 0 0 -18 Паттерн: F-[KP]-x(3)-[EQ]-x(4) Не найдем! Позиционно-специфичная матрица весов аминокислот
-
Множественное выравнивание:области применения
Один из ключевых методов в современной молекулярной биологии Сферы применения Филогенетический анализ, «эволюция» пос-сти Предсказание вторичной/третичной структуры белков Выявление АК-остатков (консервативных участков) экспонированных на поверхности белка формирующих активный центр обеспечивающих субстратную специфичность критичных для стабилизации втор./трет. структуры Выявление характерных фрагментовдля описания белковых семейств Выявление неизвестных ранее гомологиймежду генами и последовательностями Длинные пос-сти из случайных коротких фрагментов
-
Множественное выравнивание и филогенетический анализ
Идея – минимизация числа мутаций Что сначала: выравнивание или дерево? Решение не единственно !
-
Множественное выравнивание:консервативные участки во многих пос-стях
Консервативный – не значит «совпадающий» !
-
Множественное выравниваsние:белки vs. ДНК
Выравнивание белковых семейств В алфавите много «букв» Эволюционная близость белковых молекул, основа для филогенетических деревьев какие события привели к возникновению данного семейства? Идентификация функционально важных областей Данные для предсказания структуры Выравнивание некодирующих участков ДНК Консервативные участки, отвечающие за регуляцию экспрессии Установление эволюционной близости Идентификация функционально важных областей
-
Множественное выравнивание ДНК
Сайты связывания TFs = мотивы ДНК-последовательностей Консерватизм внутривидовой (синергичная регуляция транскрипции нескольких генов) межвидовой (близкие механизмы регуляции транскрипции) Дивергенция внутривидовая («специальные» цели, завязанные на метаболизм) межвидовая (эволюционный дрейф)
-
Множественное выравнивание ДНК: проблемы и варианты решения
Гораздо сложнее выравнивания белков всего 4 «буквы» Отсутствие «золотого стандарта» Необходимость оценить способность связывать белки влияние на функцию Смысл – тестирование гипотез об общем предке об общих механизмах связывания белков о близости функций
-
Множественное выравнивание:четыре группы методов
Прогрессивноеглобальное выравнивание начать с наиболее близких пос-стей Итерационные процедуры выравнивание групп пос-стей с последующей оптимизацией Выравнивание по локальным консерватив-ным участкам построение профилей (разновидности матрицы весов) поиск блоков в пос-стях (выравниваний без делеций) Статистическиеметоды и вероятностные модели поиск шаблонов (patterns) скрытые марковские модели
-
Множественное выравнивание: история
До 1987 г. множественные выравнивания строились вручную Sankoff (1975 и 1987) – первый программно реализованный алгоритм основа – филогенетический анализ Barton (1990) – оценка качества выравнивания методом рандомизации, AMPS Russel & Barton (1992) – структурное выравнивание, STAMP Thomson et al. (1994) – ClustalW Altshul et al. (1997) – PSI-BLAST Notredame et al. (2000) – неиерархическое выравнивание, T-Coffee Clamp (2004) - JalView
-
Глобальное выравнивание (обобщение ДП)
-
Глобальное выравнивание
Обобщение метода динамического программирования программа MSA (Lipman et al., 1989) результат далек от оптимального (Gupta et al., 1995) ресурсы: Nmсравнений для mпос-стей длины N Развитие MSA метод суммирования пар (sum of pairs, SP) – Carrillo & Lipman (1988) попарные выравнивания филогенетическое дерево выравнивание в ограниченной области куба эвристическое выравнивание ≠ оптимальному реализация в ClustalW / ClustalX сокращение необходимых ресурсов – Gupta et al. (1995)
-
Множественное выравнивание: трехмерное динамическое программирование
-
Множественное выравнивание: трехмерное динамическое программирование (прод.)
-
Глобальное выравнивание (прод.)
Оценка качества веса множественных выравниваний (SP score) = сумме весов попарных выравниваний поиск набольшего суммарного веса взвешивание весов (опционально) по филогенетическому дереву учет эволюционно близких пос-стей «дифференц.» весεдля каждой пары = (вес пары в MSA) – (вес при оптимальн. парном вырав-нии) степень дивергенции пос-стей в выравниванииδ= Σεi(чем больше δ, тем сильнее дивергенция) MSA: матрица замен PAM250, постоянный штраф за любую делецию Возможность применения к большему числу (6-8) короткихпоследовательностей
-
Прогрессивное выравнивание
-
Прогрессивное выравнивание:идея
Сначала – эволюционно наиболее близкие пос-сти Постепенное добавление новых пос-стей / групп пос-стей Waterman & Perlwitz (1984) Feng & Doolittle (1987, 1996) Higgins et al. (1996) … Отображение близости на филогенетическом дереве методы попарного сравнения пос-стей Проблема: неопределенность отдельных замен
-
Филогенетический анализ –не панацея
Проблемы неопределенность в порядке замен / делеций взвешивание ветвей (пос-стей) подбор матрицы замен назначение штрафов за делеции Реализация: ClustalW/Xи PILEUP ? } ? Отражение эволюции
-
Прогрессивное выравнивание
Если эволюционное дерево известно сначала выравниваются элементы, самые близкие на эволюционном дереве на каждом шаге выравниваются пос-стиx иy, или профилиpx иpyдля построения нового выравнивания с профилемpresult Версия со взвешиванием ветви дерева имеют веса, пропорциональные степени расхождения новый профиль – взвешенное среднее двух предыдущих x w y z pxy pzw pxyzw
-
Прогрессивное выравнивание (прод.)
Если эволюционное дерево неизвестно: построить всевозможные парные выравнивания определить матрицу расстоянийD, элементы которой D(x, y)соответствуют эволюционному расстоянию, определенному по парным выравниваниям реконструировать эволюционное дерево построить выравнивание на основе реконструированного дерева x w y z ?
-
Прогрессивное выравнивание:детали алгоритма
Три этапа попарные выравнивания «каждая с каждой» филогенетическое дерево по весам парных выравниваний (по генетическим расстояниям) последовательное построение множественного выравнивания от похожих – к непохожим Генетическое расстояние= (число замен) / (полное число соответствий) делеции не учитываются Дерево
-
Прогрессивное выравнивание:детали алгоритма (прод.)
Взвешивание пос-стей (ветвей дерева) мультипликативная модель Штрафы за делеции предыдущие делеции влияют на последующие выравнивания местоположение делеций (учет вторичной структуры) таблица встречаемости делеций штраф за открытие делеции и ее продолжение на каждую позицию штрафы во множественном выравнивании модифицируются с учетом матрицы замен, степени сходства и длины пос-стей Схема назначения штрафов в Clustalпротивоположна таковой в MSA чем уникальнее пос-сть, тем больше вес
-
Прогрессивное выравнивание:взвешивание ветвей дерева
-
Множественное выравнивание: популярный инструментарий
ClustalX DCSE
-
Прогрессивное выравнивание:штрафы за делеции
Существующие делеции влияют на выравнивание следующих пос-стей их позиции фиксируются ClustalW: размещение делеций между консервативными доменами Pascarella & Argos (1992): частоты встречаемости делеций после каждой АК в неконсервативных участках структурно близких белков Штрафы за открытие делеции за продолжение делеции та же схема за делеции внутри существующих делеций
-
Прогрессивное выравнивание:штрафы за делеции (прод.)
Компенсационная модификация штрафов средний вес соответствий по матрице замен уровень гомологии между пос-стями длины пос-стей Таблица делеций для каждой группы выравниваемых пос-стей Другие варианты модификаций ↓ штрафов для областей с существующими делециями ↑ штрафов для областей, соседствующих с делециями ↑ штрафов для областей с гидрофильными АК
-
Прогрессивное выравнивание:проблемы
Результат зависит от начальных парных выравниваний ошибки первых выравниваний накапливаются выравнивание непохожих пос-стей Байесовские методы (e.g. HMM) Матрица замен и штрафы за делеции должны отражать специфику всего набора пос-стей
-
Итерационное выравнивание
-
Итерационное выравнивание:идея метода
Задача избежать накопления ошибок начальных выравнива-ний, свойственных прогрессивным методам Вариант решения многократные итерационные выравнивания подгрупп последовательностей построение общего глобального выравнивания оптимизация общего веса выравнивания (суммы парных весов)
-
Итерационное выравнивание:варианты реализации
MultAlin (Corpet, 1998) пересчет весов парных выравниваний в прогрессивном алгоритме использование весов для пересчета дерева улучшение множественного выравнивания PRRP (1994) построение дерева по начальным парным выравниваниям вычисление весов по дереву и построение выравниваний по аналогии с MSA (но: локальные участки вместо глобального выравнивания + возможны делеции) итерационный пересчет локально выровненных участков для повышения веса выравнивания выравнивание с наибольшим весом новое дерево, новые веса и новые выравнивания повторение, пока суммарный вес не перестанет меняться
-
Muscle или как исправить ClustalW
-
Локальные множественные выравнивания
-
Локальные множественные выравнивания: виды алгоритмов
Анализ профилей Блочное выравнивание Поиск мотивов Статистические методы
-
Анализ профилей: введение
Идея: MSA для группы пос-стей Выделение высоко консервативных участков в мини-MSA Профиль - матрица весов для мини-MSA Профиль допускает соответствия, замены, делеции и вставки Применения поиск соответствий профилю в последовательности-мишени (программа Profilesearch) в качестве матрицы замен для построения выравниваний (программа Profilegap)
-
Анализ профилей: идентификация в семействе белков теплового шока (hsp70)
Матрица весов (профиль) содержит вероятности встречаемости АК в разных позициях
-
Блочное выравнивание: семейство из 34 тубулиновых белков
-
Анализ профилей: ограничения
Профиль отражает вариабельность в данном MSA смещение в сторону похожих пос-стей вариант коррекции: Gribskov & Veternik, 1996 взвешивание пос-стей по удаленности на филогенетическом дереве: чем меньше расстояние, тем меньше вес Недостаточное число пос-стей в MSA некоторые АК на некоторых позициях не представлены
-
Профиль – позиционно-специфическая матрица замен
21 столбец и Nстрок N – длина последовательностей в выравнивании
-
Множественное выравнивание на базе вероятностно-статистических методов
Максимизация математического ожидания Сэмплирование Гиббса Скрытые марковские модели see Russ Altman, Lecture 4-27-06, pp. 8-20
-
Множественное выравнивание, весна 2008 Наиболее известные программы множественного выравнивания: MSA => оптимальное выравнивание, если дождаться результата ClustalW(реализации ClustalX, emmaиз EMBOSS) до сих порсамый популярный алгоритм, в сложных случаях можетошибиться. Muscle итеративный прогрессивный алгоритм, точнее и быстрее ClustalW Т-COFFEE – немного точнее, но существенно медленнее HMMER – часто ошибается, но хорошо строит профили .........
-
Структурное выравнивание
-
Правильно ли выровнены последовательности?
-
В чем биологический смысл выравнивания?
Буквы в одной колонке определяют сопоставление аминокислотных остатков двух белков Сопоставленные остатки, по идее, должны иметь что-то общее в молекулах белка; что??? Предложение: биологический смысл имеет сопоставление одинаковых или функционально сходных остатков белка. Эти остатки играют сходную роль. Сопоставление непохожих остатков не имеет смысла.
-
Какое выравнивание “правильнее”?
13 “консервативных” остатков 12 консервативных остатков
-
Чтобы понять смысл выравнивания, вернемся к тому, что такое последовательность аминокислотных остатков и что такое белок
-
(i)Последовательность– удобный способ закодировать структурную (химическую) формулу молекулы белка (до посттрансляционных модификаций)
(iii) Последовательность однозначно определяет в какую пространственную структуру свернется белокв клетке (ii) Белок – это большая молекула, сохраняющая в живой клетке постоянную пространственную структуру, т.е.– взаимное расположение ковалентно связанных атомов (конформацию) (iv) Функция белка в клеткепроявляется только при сохранении уникальной пространственной структуры
-
Пространственное совмещение полипептидных цепей белков mta1_yeast и mat2_yeast
На плоской картинке видно плохо
-
Схематическое изображение совмещенных структур
1 2 3 4 5 6 7 8 9 10 11 12 Белок 2 1 2 3 4 5 6 7 8 Белок 1 Сαатомы Соответствие между Сαатомами двух совмещенных структур, основанное на близости в пространстве
-
Другой способ отобразить совмещение полипептидных цепей называется структурным выравниванием последовательностей
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 Стрелки как на предыдущем слайде Вставка трех остатков
-
Совмещение структур и выравнивание последовательностей
-
Еще раз: разметка по совмещенным структурам
-
Биологически обоснованное выравнивание гомеодоменов
-
Совмещение 5-и гомеодоменов
-
Множественное выравнивание гомеодоменов
Красным выделены консервативные (одинаковые у всех) остатки; желтым – на 80% консервативные (одинаковые почти у всех) остатки Красным выделены консервативные и функционально консервативные остатки
-
Размеченное множественное выравнивание
-
Функции аминокислотных остатков
Trp48 Arg53 Leu16 Pro442/ Lys442
-
В “правильном” выравнивании много консервативных аминокислотных остатков и функционально консервативных позиций
-
Выравнивание и эволюция
Последовательности белка оболочки из двух штаммов вируса Коксаки
-
..
Последовательности белка оболочки из двух штаммов вируса Коксаки и энтеровируса человека
-
Аминокислотные остатки в одной колонке биологически обоснованного выравнивания, как правило, “произошли” изодного и того же остатка - их общего предка
-
Алгоритмические решения проблемы воплощены в программах
Программы выравнивания последовательностей тестируются путем сравнения с биологически обоснованными – построенными по совмещению структур – выравниваниями Существуют базы данных структурных выравниваний последовательностей (BAliBAseи др.)
-
Предположим, известны структуры родственных белков и, значит, биологически обоснованное выравнивание последовательностей
При > 60% совпадающих букв любая современная программа даст (почти) правильный результат При
-
Применения «золотой стандарт» для выравнивания высоко гомологичных белков – выявление общего предка идентификация общих значимых элементов структуры для негомологичных белков кластеризация белков (разбиение на белковые семейства) на основе структурной близости Выравнивание должно отражать сходство структур совпадение общих структурных и функциональных элементов Проблема: оптимум в вычислениях ≠ оптимуму в биологии
-
Структурное выравнивание:постановка задачи
Для двух пространственных структур найти соответствие между атомами, обеспечивающее наилучшее «выравнивание» для большинства атомов достигается минимум с.к.о. проблема:«идеальное» выравнивание для нескольких атомов и плохоедля остальных
-
Структурное выравнивание:оценка результата
Критерии число соответствий между АК суммарное евклидово расстояние между выровненными АК доля идентичных АК среди выровненных число введенных делеций размер сравниваемых белков консерватизм окружения известных активных центров Универсальных критериев не существует Замечание отличие от поиска минимума евклидова расстояния при известном соответствии атомов с.к.о. используется только в качестве метрики комбинаторный подход !!
-
Структурное выравнивание:наложение пространственных структур
Наложение на усредненную структуру
-
-
Структурное выравнивание: различные классы белковых структур (1)
-
Структурное выравнивание: различные классы белковых структур (2)
-
Структурное выравнивание: различные классы белковых структур (3)
Разные суперсемейства «бочонков»
-
Поиск структурного выравнивания «вручную»
Класс похожие вторич. структуры все α, все β, α + β, α/β Слой (fold) значительное структурное сходство сходная организация вторичной структуры Суперсемейство (топология) предположительный общий предок Семейство очевидные эволюционные отношения гомологичность последовательностей > 25% Конкретный белок
-
Пример инструментария: Structural Classification Of Proteins (SCOP)
http://scop.stanford.edu http://scop.mrc-lmb.cam.ac.uk/scop/
-
Пример инструментария: SCOP (прод.)
-
-
http://scop.stanford.edu http://scop.mrc-lmb.cam.ac.uk/scop/
-
Как распознать близость структур?
На глаз Алгоритмически точечные методы: установление соответствий по точечным свойствам (расстояниям) анализ вторичной структуры: установление соответствий по векторам, изображающим элементы вторичной структуры Четыре метода, оперирующих прототипами STRUCTAL (Levitt, Subbiah, Gerstein) DALI (Holm, Sander) LOCK (Singh, Brutlag) геометрическое хэширование (Nussinov et al)
-
Структурное выравнивание при помощи прототипов: STRUCTAL
Итерационное динамическое программирование для улучшения случайно выбранного начального выравнивания Шаги алгоритма начать с произвольного набора соответствий между двумя структурами (выравнивание пос-стей, вторичных структур, на глаз, случайное) выровнять две структуры, исходя из текущего набора соответствий построить матрицу весов (Нидлмана-Вунша), исходя из расстояний между всевозможными парами точек ДП: обратное движение по матрице весов для нахождения выравнивания с наибольшим суммарным весом повторение шагов 2-4, пока суммарный вес не перестанет меняться Метод эвристический, не гарантирует результата, зависит от выбора начального выравнивания
-
Структурное выравнивание при помощи прототипов: STRUCTAL (прод.)
Оценка выравнивания: чем лучше выравнивание, тем выше суммарный вес возможность учесть дополнительные факторы Вес S(d) = M { 2 / [1 + (d/d0)2]– 1} где M – максимальный ожидаемый вес, d – измеряемая величина (e.g. расстояние между точками), d0 – значение d, соответствующее M = 0 При 0 ≤ d ≤ d0увеличение веса, при d > d0 - штраф
-
Итерационное динамическое программирование
-
-
Структурное выравнивание при помощи прототипов: LOCK
Основная идея: элементы вторичной структуры представляются при помощи векторов быстрый поиск похожих структур
-
Структурное выравнивание при помощи прототипов: LOCK (прод.)
Сравнение «векторов вторичной структуры»
-
Выравнивание «векторов вторичной структуры»
-
Шаги алгоритма определить локальные элементы вторичной структуры построить начальное наложение структур методом ДП, используя выбранную функцию веса векторное представление элементов вторичной структуры определить ближайших соседей, минимизируя евклидовы расстояния удалить лишние атомы, чтобы получить минимальное с.к.о.
-
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK (1)
-
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK (1a)
-
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK (1b)
-
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK (2)
-
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK (3)
-
Структурное выравнивание:«за» и «против»
«Золотой» стандарт для выравнивания пос-стей Трехмерная структура часто неизвестна Структурное выравнивание не всегда отражает ход эволюции точная последовательность вставок/замен/делеций неизвестна
-
ПРОБЛЕМА: как построить “правильное” выравнивание последовательностей белков если структуры белков неизвестны?
-
На сегодня известны: более 10 млн(!!!) последовательностей белков (включая фрагменты и трансляты) пространственные структуры около 70 тыс. белков
-
Дякую за увагу Благодарю за внимание Thank you for your attention
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.