Выравнивание полипептидных цепей в пространстве С.А. Спирин 20 ноября 2012

Выравнивание последовательностей гомеодоменов Пример 1: гомеодомены

Совмещение полипептидных цепей гомеодоменов

Фрагмент выравнивания (по Xu et al., 2003) Функционально консервативные остатки: 13 из 150 (8%) Пример 2: РНК-зависимые РНК полимеразы

Продолжение Функционально консервативные остатки: 5 из 140 (4%)

Выравнивание мотивов A, B, C РНК- зависимых РНК-полимераз вирусов Мотив A Консервативные остатки: 2 из 39 (5%!)

Мотив B Функционально консервативные остатки: 4 из 37 (10%)

Мотив С Консервативные остатки: 3 из 22 (14%)

Совмещение в пространстве мотивов A, B, C из полимераз 9 разных вирусов Мотив A Мотив C Мотив B Здесь расположен активный центр полимеразы

Геометрическое ядро этого семейства полимераз состоит из 58 C атомов в каждой из 9-и структур Критерий сходства – расстояния между любыми соответственными C отличаются не более чем на 2 ангстрема

Сходство всех этих полимераз продолжается на большую часть глобулы, хотя и без совпадения остовов цепей в пространстве Дополнительные фрагменты цепи некоторых полимераз не показаны

Пространственная структура остова полипептидной цепи консервативнее последовательности! Почему в ходе эволюции многих белков сохраняется геометрическое ядро (с точностью в 1–2 ангстрема) в то время, как аминокислотные остатки в тех же самых участках заменяются?

Алгоритмы пространственного выравнивания 3D структур Парное выравнивание: совмещение в пространстве при заданном частичном выравнивании последовательностей собственно выравнивание по пространственным данным без заранее заданного выравнивания последовательностей

Задача: совместить структуры по фрагментам цепей, последовательности которых хорошо выравниваются

1. Совмещение в пространстве Дано: –n точек в пространстве A 1, …, A n – центры C атомов из выровненных остатков первой структуры –n точек в пространстве B 1, …, B n – центры C атомов из выровненных остатков второй структуры A1A1 A2A2 A3A3 A4A4 A5A5 B1B1 B3B3 B1B1 B4B4 B5B5 B2B2 Структура A Структура B

A1A1 A2A2 A3A3 A4A4 A5A5 B1B1 B3B3 B4B4 B5B5 B2B2 1. Совмещение в пространстве Найти: Совмещение ломаных A и B в пространстве, при котором среднее квадратичное расстояние (Root mean square deviation) rmsd= [расст.(A 1,B 1 ) 2 +расст.(A 2,B 2 ) 2 +…+расст.(A n,B n ) 2 ] / n будет минимальным

Задача пространственного совмещения при заданном выравнивании последовательностей для критерия rmsd эффективно решается итеративными процедурами В PyMol – команда pair_fit sel_1, sel_2

Алгоритм Sippl&Stegbuchner, 1991 (1) Переместить "центры тяжести" и A, и B в начало координат (2) Подобрать поворот структуры B вокруг оси X, минимизирующий rmsd (угол поворота φ вычисляется существует формула) (3) – '' – '' – '' – '' – '' – '' – '' – '' – '' – оси Y – '' – получим угол ψ (4) – '' – '' – '' – '' – '' – '' – '' – '' – '' – оси Z – '' – получим угол ω (5) Если φ, ψ, ω оказались меньше заданного порога δ, то остановка; иначе повторить (2) – (4)

Пространственное выравнивание двух структур – общая постановка задачи Выбрать набор атомов из одной структуры и сопоставить каждому выбранному атому по атому другой структуры. Каждую сопоставленную пару будем называть позицией выравнивания Обычно выбираются С α -атомы (тем самым выравнивание последовательностей белков становится частным случаем этой задачи)

Критерии качества выравнивания Могут быть основаны: 1. На совмещении выровненных наборов атомов и вычислении RMSD 2. На сравнении расстояний между атомами в каждой их структур

Пространственное выравнивание двух структур без заданного выравнивания последовательностей Не существует эффективных алгоритмов, гарантирующих точное решение задачи (при любой её разумной формализации). Все предложенные алгоритмы основаны на эвристиках. В простых случаях дают правильный ответ, в более сложных – могут ошибаться.

Алгоритм DALI (Holm&Sander, 1993) Основан на сравнении расстояний между C α -атомами в каждой из структур Может сопоставлять части структур, по-разному расположенные по последовательности Работает в два этапа: сначала находятся пары «гексапептидов» (в каждой паре по шестизвенному участку из каждой структуры) близкой конфигурации; затем из таких пар «сшивается» выравнивание Может использовать две разные целевые функции: «жёсткую» (rigid) и «эластичную» (elastic)

Целевая функция алгоритма DALI (вес выравнивания, «жёсткий» вариант) Если выравнивание содержит L позиций, то его «качество» оценивается величиной S (rigid similarity score): Здесь каждое i и каждое j означает позицию выравнивания, то есть пару сопоставленных атомов; d A ij и d B ij – расстояния между атомами i и j в структурах A и B i j j i AB d A ij d B ij

Целевая функция алгоритма DALI (вес выравнивания, «эластичный» вариант) Величина S (elastic similarity score) вычисляется по той же формуле, но вклад каждой пары позиций вычисляется по формуле: Смысл такого варианта: смягчить требования на удалённые в пространстве атомы

DaliLite и FSSP Ускоренный вариант алгоритма DALI, названный DaliLite, используется для поиска по банку белков, хорошо совмещающихся с данным. Имеется также база данных Dali Database (старое название FSSP – families of structurally similar proteins), в которой хранятся наборы хорошо совмещающихся белков. См.

Алгоритм SSM (secondary structure matching) Krissinel&Henrick, 2004 (1) Пространственное выравнивание двух структур; (2) Множественное пространственное выравнивание; (3) Поиск схожих структур по PDB. (4) Совмещение, визуализация etc.

Этапы алгоритма SSM 1.Построение матрицы элементов вторичной структуры (SSE, secondary structure elements) для каждой из структур 2.Нахождение максимальных наборов SSE, сходно расположенных в двух структурах 3.Грубое совмещение структур по наборам SSE, найденным в п.2. 4.Сопоставление C атомов двух структур (структурное выравнивание) 5.Совмещение по сопоставленным C ; вычисление rmsd икачества Q 6.Удаление слабых звеньев из структурного выравнивания для максимизации Q 7.Выход: структурное выравнивание, совмещение, показатели, оценивающие результат (L align, rmsd, Q, Z- score)

Целевая функция алгоритма SSM – «качество» Q Чтобы вычислить Q, сопоставленные C α -атомы совмещаются в пространстве и вычисляется rmsd для них. Далее применяется формула: Здесь L align – количество позиций выравнивания, L 1 и L 2 – длины цепей двух белков, R 0 = 3Å

Первый этап алгоритма: матрица SSE SSE 1: H (начальный остаток 7A, всего 10 остатков) 2: S1 (начальный остаток 20A, всего 7 остатков) 3: S2 (начальный остаток 31A, всего 8 остатков) 4: S3 (начальный остаток 45A, всего 5 остатков) 1: H0D 12 D 13 D 14 2: S1D 12 0D 23 D 24 3: S2D 13 D 23 0D 34 4: S3D 14 D 24 D 34 0 Элемент матрицы: характеристика взаимного расположения двух SSE Каждому SSE приписывается - его порядковый - тип (H или S) - длина (в числе остатков) - ID первого остатка

Параметры взаимного расположение направленных отрезков i и j, идущих из начала в конец SSE i и SSE j : - расстояние ij между центрами SSE i и SSE j - углы 1 ij, 2 ij между i и j и линией, соединяющей эти центры - угол 3 ij между i и j - торсионный угол 4 ij D ij ={ ij, 1 ij, 2 ij, 3 ij, 4 ij }

Этапы алгоритма SSM 1.Построение матрицы элементов вторичной структуры (SSE, secondary structure elements) для каждой из структур 2.Нахождение максимальных наборов SSE, сходно расположенных в двух структурах 3.Грубое совмещение структур по наборам SSE, найденным в п.2. 4.Сопоставление C атомов двух структур (структурное выравнивание) 5.Совмещение по сопоставленным C ; вычисление rmsd икачества Q 6.Удаление слабых звеньев из структурного выравнивания для максимизации Q 7.Выход: структурное выравнивание, совмещение, параметры, оценивающие результат (L align, rmsd, Q, Z-score)

2. Даны две структуры (см. рис.) В них надо найти наборы сходно расположенных в пространстве [и идущих в одном и том же порядке вдоль полипептидной цепи] элементов вторичной структуры (SSE) Сходные наборы SSE: HS 2 HS 3 S 1 S 2 S 1 S 2 S 3 S 2 S 1 S 3 Можно и не учитывать порядок SSE! В таком случае H-S1-S2-S3 H-S1-S2-S3

Сравнение матриц SSE двух структур 1: H2: S13: S24: S3 1: H0D 12 D 13 D 14 2: S1 D 12 0 D 23 D 24 3: S2 D 13 D 23 0D 34 4: S3 D 14 D 24 D : S12: H3: S34: S2 1: S10D 12 D 13 D 14 2: H D 12 0 D 23 D 24 3: S3 D 13 D 23 0 D 34 4: S2 D 14 D 24 D 34 0 Матричные элементы сходно расположенных пар SSE изображены одинаковыми цветами Сходство расположения пар SSE из двух структур определяется близостью значений матричных элементов

Сходство расположения пар SSE из двух структур определяется близостью значений матричных элементов Пары (SSE i, SSE j ) из 1-ой и (SSE k, SSE l ) из 2-ой структуры считаются сходно расположенными, если - типы первых SSE пары совпадают - типы вторых SSE пары совпадают - длины SSE примерно равны - D ij D kl т.е. ij kl, 1 ij 1 kl, 2 ij 2 kl, 3 ij 3 kl, 4 ij 4 kl Структура 1я: SSE i-й и j-й Структура 2я: SSE k-й и l-й Допустимые погрешности при сравнении двух значений установлены эмпирически

Граф сходства SSE (для двух структур) Вершина – пара (SSE i, SSE k ) одного типа (H или S) и примерно одинаковой длины; SSE i из 1-ой структуры, SSE k – из 2-ой Две вершины V=(SSE i, SSE k ) и V=(SSE j, SSE l ) соединены ребром, если пары (SSE i, SSE j ) и (SSE k, SSE l ) сходно расположены

(H,H) Список вершин графа сходства структур 1 и 2 (S1,S1) (S1,S2) (S1,S3) (S2,S2) (S2,S1) (S2,S3) (S3,S2) (S3,S1) (S3,S3) Примеры ребер (H, H)––––(S3,S3) Так как (H,S3) (H,S3) (S1,S3)––––(S2,S2) Так как (S1,S2) (S3,S2) 12

Максимальная клика в графе соответствует максимальным наборам сходно расположенных SSE (один набор SSE из 1-ой структуры, другой – из 2-ой структуры) Клика – это подграф, в котором каждая вершина соединена с каждой

Забудем в этом примере о порядке следования SSE (H, H)(S1, S1) (S2, S2) (S3, S3) (H,S1) из 1й структуры Расположены так же, как (H,S1) из 2й структуры. Поэтому вершины (H,H) И (S1, S1) соединены ребром Аналогично – все остальные ребра Упражнение. Постройте весь граф сходства. Порядок SSE не учитывать

Задача поиска максимальных клик в графе сложна для компьютера! Алгоритм точного решения, годный для любого графа, требует невообразимого времени Пользуясь особенностями графов сходства, можно предложить эффективные эмпирические алгоритмы. Один из них работает в SSM-алгоритме

Этапы алгоритма SSM 1.Построение матрицы элементов вторичной структуры (SSE, secondary structure elements) для каждой из структур 2.Нахождение максимальных наборов SSE, сходно расположенных в двух структурах 3.Грубое совмещение структур по наборам SSE, найденным в п Сопоставление C атомов двух структур (структурное выравнивание) 5.Совмещение по сопоставленным C ; вычисление rmsd икачества Q 6.Удаление слабых звеньев из структурного выравнивания для максимизации Q 7.Выход: структурное выравнивание, совмещение, параметры, оценивающие результат (L align, rmsd, Q, Z-score)

3. Совмещение двух структур по наборам сходно расположенных SSE Набор SSE в каждой структуре представляется началами B i и концами E i направленных отрезков i, идущих от начала к концу SSE i. Таким образом, в каждой структуре имеем одинаковое число последовательно идущих точек пространства (B 1, E 1, B 2, E 2, …) Эти точки совмещаются одним из алгоритмов совмещения при заданном сопоставлении точек. Результат: черновое совмещение структур.

Совмещение по сходно расположенным SSE

Этапы алгоритма SSM 1.Построение матрицы элементов вторичной структуры (SSE, secondary structure elements) для каждой из структур 2.Нахождение максимальных наборов SSE, сходно расположенных в двух структурах 3.Грубое совмещение структур по наборам SSE, найденным в п.2. 4.Сопоставление C атомов двух структур (структурное выравнивание) 5.Совмещение по сопоставленным C ; вычисление rmsd икачества Q 6.Удаление слабых звеньев из структурного выравнивания для максимизации Q 7.Выход: структурное выравнивание, совмещение, параметры, оценивающие результат (L align, rmsd, Q, Z-score)

4. Совмещение позволяет сопоставить C атомы, т.е. построить структурное выравнивание 1)В сопоставленных SSE находятся четверки (для спиралей) или тройки (для тяжей) идущих подряд наиболее близких C атомов (черные кружки на рис.) 2)Сопоставление четверок (троек) продолжается на все SSE без разрывов и вставок в последовательности

Продолжение 3)Находятся близкие в пространстве пары SSE из разных структур, которые не были сопоставлены, но и не противоречат прежним сопоставлениям 4)Для таких пар повторяются п.п.1–2 Пример противоречивого сопоставления Серые SSE сопоставлены правильно. Сопоставление белых SSE запрещено т.к. нарушает порядок SSE вдоль цепи

Продолжение 5)Для оставшихся неспаренными C атомов находятсяконтакты – наиболее сближенные пары (A,B), A=C из 1й; B= C из второй структуры; точный критерий: 1.B ближайший к A C атом из второй структуры 2.A ближайший к B C атом из первой структуры 3.Расст.(A,B) < R c =3Å 6)Сопоставление от наиболее близких контактирующих пар продолжается на соседей по последовательности (см. рис.)

Этапы алгоритма SSM 1.Построение матрицы элементов вторичной структуры (SSE, secondary structure elements) для каждой из структур 2.Нахождение максимальных наборов SSE, сходно расположенных в двух структурах 3.Грубое совмещение структур по наборам SSE, найденным в п.2. 4.Сопоставление C атомов двух структур (структурное выравнивание) 5.Совмещение по сопоставленным C ; вычисление rmsd икачества Q 6.Удаление слабых звеньев из структурного выравнивания для максимизации Q 7.Выход: структурное выравнивание, совмещение, параметры, оценивающие результат (L align, rmsd, Q, Z-score)

5. Вычисление качества Q пространственного выравнивания 1)Улучшение пространственного совмещения. Для этого используется построенное (структурное) выравнивание. 2)Вычисление rmsd по сопоставленным C атомам 3)Вычисление Q

Качество Q 0

Этапы алгоритма SSM 1.Построение матрицы элементов вторичной структуры (SSE, secondary structure elements) для каждой из структур 2.Нахождение максимальных наборов SSE, сходно расположенных в двух структурах 3.Грубое совмещение структур по наборам SSE, найденным в п.2. 4.Сопоставление C атомов двух структур (структурное выравнивание) 5.Совмещение по сопоставленным C ; вычисление rmsd икачества Q 6.Удаление слабых звеньев из структурного выравнивания для максимизации Q 7.Выход: структурное выравнивание, совмещение, параметры, оценивающие результат (L align, rmsd, Q, Z-score)

6. Удаление слабых звеньев для получения лучшего качества Q. При выкидывании пары C из списка сопоставленных остатков L align уменьшается (что плохо), но и rmsd уменьшается (что хорошо). Q может уменьшиться, а может и увеличиться! Из списка сопоставленных атомов выкидывается наиболее разошедшаяся пара Пересчитывается качество Q Эта процедура повторяется до тех пор, пока не будет достигнут максимум Q Оставляются только не менее трёх идущих подряд сопоставленных C ; изолированные или пары идущих подряд C выкидываются

7. Результат Полученное выравнивание с максимальным Q и считается результатом Кроме того, процедура повторяется со всеми другими сходными наборами SSE, включающими столько же SSE, что и первый, или на один или два SSE меньше Все полученные выравнивания сортируются по Q и первым выдается то, у которого Q наибольшее

Обсуждение алгоритма SSM Работоспособен. На уровне нескольких других алгоритмов. Не гарантирует правильного ответа в достаточно сложной ситуации; бывают ошибки. Плюс: использование элементов вторичной структуры. Минус: не все знания о структурных элементах использует (бета-листы; геометрическое ядро семейства доменов при поиске по банку; гидрофобное ядро; …) Ещё минус: много параметров, значения которых взяты произвольно Имеется web-сервер: (PDBeFOLD)

Всё, что было изложено – «жёсткое выравнивание» Критерии качества основывались на предположении, что белки совмещаются как твёрдые тела. Вообще говоря, выравниванием следует считать любое обоснованное сопоставление остатков одного белка остаткам другого. В частности, сопоставляемые части могут двигаться относительно друг друга. Про то, как быть в такой ситуации – в следующей лекции.