Генная инженерия
<<  Построение множественных выравниваний Системная инженерия - процессы жизненного цикла систем  >>
Часть I. Структурная геномика: выравнивание последовательностей
Часть I. Структурная геномика: выравнивание последовательностей
Ссылки
Ссылки
Выравнивание последовательностей: классификация
Выравнивание последовательностей: классификация
Множественное выравнивание (multiple alignment)
Множественное выравнивание (multiple alignment)
Множественное выравнивание: содержание
Множественное выравнивание: содержание
Множественное выравнивание: введение
Множественное выравнивание: введение
Структурная геномика: выравнивание последовательностей
Структурная геномика: выравнивание последовательностей
Выравнивание полных геномов: крыса – мышь – человек
Выравнивание полных геномов: крыса – мышь – человек
Множественное выравнивание: иллюстрации
Множественное выравнивание: иллюстрации
Множественное выравнивание: определение и проблемы
Множественное выравнивание: определение и проблемы
Множественное выравнивание: проблемы (прод
Множественное выравнивание: проблемы (прод
Множественное выравнивание: три решаемые задачи
Множественное выравнивание: три решаемые задачи
Множественное выравнивание: области применения (1/2)
Множественное выравнивание: области применения (1/2)
Множественное выравнивание и филогенетический анализ
Множественное выравнивание и филогенетический анализ
Множественное выравнивание: консервативные участки во многих пос-стях
Множественное выравнивание: консервативные участки во многих пос-стях
Множественное выравнивание: белки vs
Множественное выравнивание: белки vs
Множественное выравнивание ДНК
Множественное выравнивание ДНК
Множественное выравнивание ДНК: проблемы и варианты решения
Множественное выравнивание ДНК: проблемы и варианты решения
Множественное выравнивание: четыре группы методов
Множественное выравнивание: четыре группы методов
Множественное выравнивание: история
Множественное выравнивание: история
Глобальное выравнивание (обобщение ДП)
Глобальное выравнивание (обобщение ДП)
Глобальное выравнивание
Глобальное выравнивание
Множественное выравнивание: трехмерное динамическое программирование
Множественное выравнивание: трехмерное динамическое программирование
Множественное выравнивание: трехмерное динамическое программирование
Множественное выравнивание: трехмерное динамическое программирование
Глобальное выравнивание (прод
Глобальное выравнивание (прод
Оценка качества
Оценка качества
Множественное выравнивание повышает точность парного выравнивания
Множественное выравнивание повышает точность парного выравнивания
Метод SP не свободен от недостатков
Метод SP не свободен от недостатков
Матрицы замен: BLOSUM62
Матрицы замен: BLOSUM62
Метод SP не свободен от недостатков
Метод SP не свободен от недостатков
Более совершенные методы оценки качества
Более совершенные методы оценки качества
Статистическая значимость выравнивания
Статистическая значимость выравнивания
Статистическая значимость выравнивания (прод
Статистическая значимость выравнивания (прод
Структурное выравнивание
Структурное выравнивание
Структурное выравнивание: зачем
Структурное выравнивание: зачем
Структурное выравнивание: постановка задачи
Структурное выравнивание: постановка задачи
!!
!!
Структурное выравнивание: наложение пространственных структур
Структурное выравнивание: наложение пространственных структур
Структурное выравнивание: наложение пространственных структур
Структурное выравнивание: наложение пространственных структур
Структурное выравнивание: различные классы белковых структур (1)
Структурное выравнивание: различные классы белковых структур (1)
Структурное выравнивание: различные классы белковых структур (2)
Структурное выравнивание: различные классы белковых структур (2)
Структурное выравнивание: различные классы белковых структур (3)
Структурное выравнивание: различные классы белковых структур (3)
Поиск структурного выравнивания «вручную»
Поиск структурного выравнивания «вручную»
Пример инструментария: Structural Classification Of Proteins (SCOP)
Пример инструментария: Structural Classification Of Proteins (SCOP)
Пример инструментария: SCOP (прод
Пример инструментария: SCOP (прод
Пример инструментария: SCOP (прод
Пример инструментария: SCOP (прод
Пример инструментария: SCOP (прод
Пример инструментария: SCOP (прод
Как распознать близость структур
Как распознать близость структур
Структурное выравнивание при помощи прототипов: STRUCTAL
Структурное выравнивание при помощи прототипов: STRUCTAL
Структурное выравнивание при помощи прототипов: STRUCTAL (прод
Структурное выравнивание при помощи прототипов: STRUCTAL (прод
Структурное выравнивание при помощи прототипов: STRUCTAL (прод
Структурное выравнивание при помощи прототипов: STRUCTAL (прод
Структурное выравнивание при помощи прототипов: STRUCTAL (прод
Структурное выравнивание при помощи прототипов: STRUCTAL (прод
Структурное выравнивание при помощи прототипов: LOCK
Структурное выравнивание при помощи прототипов: LOCK
Структурное выравнивание при помощи прототипов: LOCK (прод
Структурное выравнивание при помощи прототипов: LOCK (прод
Структурное выравнивание при помощи прототипов: LOCK (прод
Структурное выравнивание при помощи прототипов: LOCK (прод
Структурное выравнивание при помощи прототипов: LOCK (прод
Структурное выравнивание при помощи прототипов: LOCK (прод
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK
Структурное выравнивание: «за» и «против»
Структурное выравнивание: «за» и «против»
Прогрессивное выравнивание
Прогрессивное выравнивание
Прогрессивное выравнивание: идея
Прогрессивное выравнивание: идея
Неопределенность конкретных замен
Неопределенность конкретных замен
} ?
} ?
Прогрессивное выравнивание
Прогрессивное выравнивание
?
?
Прогрессивное выравнивание: детали алгоритма
Прогрессивное выравнивание: детали алгоритма
Прогрессивное выравнивание: детали алгоритма (прод
Прогрессивное выравнивание: детали алгоритма (прод
Прогрессивное выравнивание: взвешивание ветвей дерева
Прогрессивное выравнивание: взвешивание ветвей дерева
Множественное выравнивание: популярный инструментарий
Множественное выравнивание: популярный инструментарий
Прогрессивное выравнивание: штрафы за делеции
Прогрессивное выравнивание: штрафы за делеции
Прогрессивное выравнивание: штрафы за делеции (прод
Прогрессивное выравнивание: штрафы за делеции (прод
Clustalw: пример выравнивания семейства глобинов
Clustalw: пример выравнивания семейства глобинов
Прогрессивное выравнивание: проблемы
Прогрессивное выравнивание: проблемы
Прогрессивное выравнивание: вариант с иерархической кластеризацией
Прогрессивное выравнивание: вариант с иерархической кластеризацией
Инструментарий: ALSCRIPT (1993)
Инструментарий: ALSCRIPT (1993)
Инструментарий: AMAS (1993)
Инструментарий: AMAS (1993)
Итерационное выравнивание
Итерационное выравнивание
Итерационное выравнивание: идея метода
Итерационное выравнивание: идея метода
Итерационное выравнивание: варианты реализации
Итерационное выравнивание: варианты реализации
Итерационное выравнивание: блок-схема алгоритма PRRP
Итерационное выравнивание: блок-схема алгоритма PRRP
Итерационное выравнивание: варианты реализации (прод
Итерационное выравнивание: варианты реализации (прод
Генетичекие алгоритмы: идея и реализация
Генетичекие алгоритмы: идея и реализация
Генетические алгоритмы: этапы
Генетические алгоритмы: этапы
Генетичекие алгоритмы: этапы (прод
Генетичекие алгоритмы: этапы (прод
Генетичекие алгоритмы: этапы (прод
Генетичекие алгоритмы: этапы (прод
Генетичекие алгоритмы: этапы (прод
Генетичекие алгоритмы: этапы (прод
Локальные множественные выравнивания
Локальные множественные выравнивания
Локальные множественные выравнивания: виды алгоритмов
Локальные множественные выравнивания: виды алгоритмов
Анализ профилей: введение
Анализ профилей: введение
Анализ профилей: идентификация в семействе белков теплового шока
Анализ профилей: идентификация в семействе белков теплового шока
Построение профилей: метод средних
Построение профилей: метод средних
Построение профилей: эволюционный метод
Построение профилей: эволюционный метод
Блочное выравнивание: семейство из 34 тубулиновых белков
Блочное выравнивание: семейство из 34 тубулиновых белков
Анализ профилей: ограничения
Анализ профилей: ограничения
Профиль – позиционно-специфическая матрица замен
Профиль – позиционно-специфическая матрица замен
Статистические методы множественного выравнивания
Статистические методы множественного выравнивания
Множественное выравнивание на базе вероятностно-статистических методов
Множественное выравнивание на базе вероятностно-статистических методов
Максимизация математического ожидания
Максимизация математического ожидания
Максимизация математического ожидания (Expectation Maximization, EM)
Максимизация математического ожидания (Expectation Maximization, EM)
Максимизация математического ожидания: предварительное выр-ние
Максимизация математического ожидания: предварительное выр-ние
Максимизация математического ожидания: таблица частот
Максимизация математического ожидания: таблица частот
Максимизация математического ожидания: этап «ожидание» (прод
Максимизация математического ожидания: этап «ожидание» (прод
Максимизация математического ожидания: этап максимизации
Максимизация математического ожидания: этап максимизации
Выборки Гиббса
Выборки Гиббса
Выборки Гиббса (Gibbs sampler)
Выборки Гиббса (Gibbs sampler)
Выборки Гиббса: алгоритм (прод
Выборки Гиббса: алгоритм (прод
Выборки Гиббса: идея
Выборки Гиббса: идея
Выборки Гиббса: алгоритм
Выборки Гиббса: алгоритм
Выборки Гиббса: алгоритм – шаг 1
Выборки Гиббса: алгоритм – шаг 1
Выборки Гиббса: алгоритм – шаг 2a
Выборки Гиббса: алгоритм – шаг 2a
Выборки Гиббса: алгоритм – шаг 2b
Выборки Гиббса: алгоритм – шаг 2b
Выборки Гиббса: алгоритм – шаг 2b
Выборки Гиббса: алгоритм – шаг 2b
Выборки Гиббса: алгоритм – шаг 2b
Выборки Гиббса: алгоритм – шаг 2b
Выборки Гиббса: алгоритм – шаг 2c
Выборки Гиббса: алгоритм – шаг 2c
Выборки Гиббса: алгоритм – шаг 2c
Выборки Гиббса: алгоритм – шаг 2c
Выборки Гиббса: алгоритм – шаг 2d
Выборки Гиббса: алгоритм – шаг 2d
Выборки Гиббса: иллюстрация сходимости алгоритма
Выборки Гиббса: иллюстрация сходимости алгоритма
Выборки Гиббса: иллюстрация сходимости алгоритма (прод
Выборки Гиббса: иллюстрация сходимости алгоритма (прод
Выборки Гиббса: алгоритм – шаг 3
Выборки Гиббса: алгоритм – шаг 3
Выборки Гиббса: куда двигаться дальше
Выборки Гиббса: куда двигаться дальше
Скрытые марковские модели (HMM)
Скрытые марковские модели (HMM)
Марковские модели (Markov Models): введение
Марковские модели (Markov Models): введение
Марковские модели: введение (прод
Марковские модели: введение (прод
Марковские модели: представление последовательности ДНК
Марковские модели: представление последовательности ДНК
Скрытые марковские модели (Hidden Markov Models)
Скрытые марковские модели (Hidden Markov Models)
Скрытые марковские модели: применение для множественного выравнивания
Скрытые марковские модели: применение для множественного выравнивания
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
Скрытые марковские модели: формализация множ
HMM для семейства глобинов
HMM для семейства глобинов
Структурная геномика: выравнивание последовательностей
Структурная геномика: выравнивание последовательностей
Выравнивание семейства глобинов
Выравнивание семейства глобинов
HMM: выравнивание последовательности по модели
HMM: выравнивание последовательности по модели
Скрытые марковские модели: программы для множ
Скрытые марковские модели: программы для множ
Скрытые марковские модели: три вычислительные задачи
Скрытые марковские модели: три вычислительные задачи
НММ: от обучения к применению
НММ: от обучения к применению
НММ: проблемы
НММ: проблемы

Презентация: «Структурная геномика: выравнивание последовательностей». Автор: Chinh & Birgitta. Файл: «Структурная геномика: выравнивание последовательностей.ppt». Размер zip-архива: 7844 КБ.

Структурная геномика: выравнивание последовательностей

содержание презентации «Структурная геномика: выравнивание последовательностей.ppt»
СлайдТекст
1 Часть I. Структурная геномика: выравнивание последовательностей

Часть I. Структурная геномика: выравнивание последовательностей

2 Ссылки

Ссылки

Учебники: D.W. Mount. Bioinformatics. Sequence and Genome Analysis. NY, Cold Spring Harbor, 2001. A.D. Baxevanis, B.F.F. Ouellette (eds.). Bioinformatics. A Practical Guide to the Analysis of Genes and Proteins. NJ, Wiley, 2005. Обзоры и статьи

3 Выравнивание последовательностей: классификация

Выравнивание последовательностей: классификация

Выравнивание последовательностей

Парное

Множественное

Локальное

Глобальное

4 Множественное выравнивание (multiple alignment)

Множественное выравнивание (multiple alignment)

5 Множественное выравнивание: содержание

Множественное выравнивание: содержание

Определение, разновидности, решаемые задачи, общие проблемы Глобальное выравнивание Оценка качества выравнивания Структурное выравнивание Прогрессивное выравнивание Итерационные методы Локальные множественные выравнивания Вероятностно-статистические методы множественного выравнивания

6 Множественное выравнивание: введение

Множественное выравнивание: введение

7 Структурная геномика: выравнивание последовательностей
8 Выравнивание полных геномов: крыса – мышь – человек

Выравнивание полных геномов: крыса – мышь – человек

9 Множественное выравнивание: иллюстрации

Множественное выравнивание: иллюстрации

10 Множественное выравнивание: определение и проблемы

Множественное выравнивание: определение и проблемы

Определение: найти оптимальное соответствие между несколькими последовательностями, если заданы Матрица соответствия Штраф за делецию Функция веса выравнивания Проблемы: Множество делеций, замен,… Ограниченное обобщение метода динамического программирования Подсчет суммарного веса замен в колонке Размещение делеций в разных пос-стях и штрафы за них

11 Множественное выравнивание: проблемы (прод

Множественное выравнивание: проблемы (прод

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

12 Множественное выравнивание: три решаемые задачи

Множественное выравнивание: три решаемые задачи

Поиск мотивов (блоков) – коротких сигнатур, идентифицируемых в консервативных участках множественного выравнивания отсутствие вставок и делеций Построение профилей (матриц весов): оценка частоты встречаемости каждой АК в каждой позиции Построение скрытых марковских моделей (HMM) – обобщенных профилей, описываемых строго математически

13 Множественное выравнивание: области применения (1/2)

Множественное выравнивание: области применения (1/2)

Один из ключевых методов в современной молекулярной биологии Сферы применения Филогенетический анализ, «эволюция» пос-сти Предсказание вторичной/третичной структуры белков Выявление АК-остатков (консервативных участков) экспонированных на поверхности белка формирующих активный центр обеспечивающих субстратную специфичность критичных для стабилизации втор./трет. структуры Выявление характерных фрагментов для описания белковых семейств Выявление неизвестных ранее гомологий между генами и последовательностями Длинные пос-сти из случайных коротких фрагментов

14 Множественное выравнивание и филогенетический анализ

Множественное выравнивание и филогенетический анализ

Идея – минимизация числа мутаций Что сначала: выравнивание или дерево? Решение не единственно !

15 Множественное выравнивание: консервативные участки во многих пос-стях

Множественное выравнивание: консервативные участки во многих пос-стях

Консервативный – не значит «совпадающий» !

16 Множественное выравнивание: белки vs

Множественное выравнивание: белки vs

ДНК

Выравнивание белковых семейств В алфавите много «букв» Эволюционная близость белковых молекул, основа для филогенетических деревьев какие события привели к возникновению данного семейства? Идентификация функционально важных областей Данные для предсказания структуры Очевидный «золотой стандарт» Выравнивание некодирующих участков ДНК Консервативные участки, отвечающие за регуляцию экспрессии Установление эволюционной близости Идентификация функционально важных областей Трудно определяемый «золотой стандарт»

17 Множественное выравнивание ДНК

Множественное выравнивание ДНК

Сайты связывания TFs = мотивы ДНК-последовательностей Консерватизм внутривидовой (синергичная регуляция транскрипции нескольких генов) межвидовой (близкие механизмы регуляции транскрипции) Дивергенция внутривидовая («специальные» цели, завязанные на метаболизм) межвидовая (эволюционный дрейф)

18 Множественное выравнивание ДНК: проблемы и варианты решения

Множественное выравнивание ДНК: проблемы и варианты решения

Гораздо сложнее выравнивания белков всего 4 «буквы» Отсутствие «золотого стандарта» Необходимость оценить способность связывать белки влияние на функцию Смысл – тестирование гипотез об общем предке об общих механизмах связывания белков о близости функций Эффективны вероятностно-статистические методы выборки Гиббса максимизация энтропии

19 Множественное выравнивание: четыре группы методов

Множественное выравнивание: четыре группы методов

Прогрессивное глобальное выравнивание начать с наиболее близких пос-стей Итерационные процедуры выравнивание групп пос-стей с последующей оптимизацией Выравнивание по локальным консерватив-ным участкам построение профилей (разновидности матрицы весов) поиск блоков в пос-стях (выравниваний без делеций) Статистические методы и вероятностные модели поиск шаблонов (patterns) скрытые марковские модели

20 Множественное выравнивание: история

Множественное выравнивание: история

До 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

21 Глобальное выравнивание (обобщение ДП)

Глобальное выравнивание (обобщение ДП)

22 Глобальное выравнивание

Глобальное выравнивание

Обобщение метода динамического программирования программа 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)

23 Множественное выравнивание: трехмерное динамическое программирование

Множественное выравнивание: трехмерное динамическое программирование

24 Множественное выравнивание: трехмерное динамическое программирование

Множественное выравнивание: трехмерное динамическое программирование

(прод.)

25 Глобальное выравнивание (прод

Глобальное выравнивание (прод

Оценка качества веса множественных выравниваний (SP score) = сумме весов попарных выравниваний поиск набольшего суммарного веса взвешивание весов (опционально) по филогенетическому дереву учет эволюционно близких пос-стей «дифференц.» вес ? для каждой пары = (вес пары в MSA) – (вес при оптимальн. парном вырав-нии) степень дивергенции пос-стей в выравнивании ? = ? ?i (чем больше ?, тем сильнее дивергенция) MSA: матрица замен PAM250, постоянный штраф за любую делецию Возможность применения к большему числу (6-8) коротких последовательностей

26 Оценка качества

Оценка качества

27 Множественное выравнивание повышает точность парного выравнивания

Множественное выравнивание повышает точность парного выравнивания

R.B.Russel & G.J.Barton (1992). Proteins 14, 309-323.

28 Метод SP не свободен от недостатков

Метод SP не свободен от недостатков

SP: сумма весов любых парных комбинаций АК в данном столбце C – цистеин N - аспарагин

Расчет весов по BLOSUM62

29 Матрицы замен: BLOSUM62

Матрицы замен: BLOSUM62

30 Метод SP не свободен от недостатков

Метод SP не свободен от недостатков

SP: сумма весов любых парных комбинаций АК в данном столбце Быстрое убывание веса с ростом числа замен Отношение весов при фиксированном числе замен убывает с ростом числа пос-стей для одной замены (BLOSUM62) 9(n-1)/[6n(n-1)/2] = = 3/n

31 Более совершенные методы оценки качества

Более совершенные методы оценки качества

Не любая последовательность может быть предшественницей любой другой Филогенетические деревья сумма длин ветвей отражает возможные замены Дерево в топологии «звезда»

32 Статистическая значимость выравнивания

Статистическая значимость выравнивания

Оценка качества выравнивание с высоким весом не эквивалентно биологической близости оценка методом рандомизации случайное перемешивание «букв» в последовательности при сохранении состава и длины выборочная функция распределения весов оценка Z-веса: Z = (S - <s>)/? и Z > 6 квантильные оценки Недостатки Z < 6 может также отвечать осмысленному выравниванию стандартные таблицы для Z дают завышенные уровни значимости

33 Статистическая значимость выравнивания (прод

Статистическая значимость выравнивания (прод

34 Структурное выравнивание

Структурное выравнивание

35 Структурное выравнивание: зачем

Структурное выравнивание: зачем

Применения «золотой стандарт» для выравнивания высоко гомологичных белков – выявление общего предка идентификация общих значимых элементов структуры для негомологичных белков кластеризация белков (разбиение на белковые семейства) на основе структурной близости Выравнивание должно отражать сходство структур совпадение общих структурных и функциональных элементов Проблема: оптимум в вычислениях ? оптимуму в биологии

36 Структурное выравнивание: постановка задачи

Структурное выравнивание: постановка задачи

Для двух пространственных структур найти соответствие между атомами, обеспечивающее наилучшее «выравнивание» для большинства атомов достигается минимум с.к.о. проблема: «идеальное» выравнивание для нескольких атомов и плохое для остальных

37 !!

!!

Структурное выравнивание: оценка результата

Критерии число соответствий между АК суммарное евклидово расстояние между выровненными АК доля идентичных АК среди выровненных число введенных делеций размер сравниваемых белков консерватизм окружения известных активных центров Универсальных критериев не существует Замечание отличие от поиска минимума евклидова расстояния при известном соответствии атомов с.к.о. используется только в качестве метрики комбинаторный подход

38 Структурное выравнивание: наложение пространственных структур

Структурное выравнивание: наложение пространственных структур

Наложение на усредненную структуру

39 Структурное выравнивание: наложение пространственных структур

Структурное выравнивание: наложение пространственных структур

40 Структурное выравнивание: различные классы белковых структур (1)

Структурное выравнивание: различные классы белковых структур (1)

41 Структурное выравнивание: различные классы белковых структур (2)

Структурное выравнивание: различные классы белковых структур (2)

42 Структурное выравнивание: различные классы белковых структур (3)

Структурное выравнивание: различные классы белковых структур (3)

Разные суперсемейства «бочонков»

43 Поиск структурного выравнивания «вручную»

Поиск структурного выравнивания «вручную»

Класс похожие вторич. структуры все ?, все ?, ? + ?, ?/? Слой (fold) значительное структурное сходство сходная организация вторичной структуры Суперсемейство (топология) предположительный общий предок

Семейство очевидные эволюционные отношения гомологичность последовательностей > 25% Конкретный белок

44 Пример инструментария: Structural Classification Of Proteins (SCOP)

Пример инструментария: Structural Classification Of Proteins (SCOP)

http://scop.stanford.edu http://scop.mrc-lmb.cam.ac.uk/scop/

45 Пример инструментария: SCOP (прод

Пример инструментария: SCOP (прод

46 Пример инструментария: SCOP (прод

Пример инструментария: SCOP (прод

47 Пример инструментария: SCOP (прод

Пример инструментария: SCOP (прод

http://scop.stanford.edu http://scop.mrc-lmb.cam.ac.uk/scop/

48 Как распознать близость структур

Как распознать близость структур

На глаз Алгоритмически точечные методы: установление соответствий по точечным свойствам (расстояниям) анализ вторичной структуры: установление соответствий по векторам, изображающим элементы вторичной структуры Четыре метода, оперирующих прототипами STRUCTAL (Levitt, Subbiah, Gerstein) DALI (Holm, Sander) LOCK (Singh, Brutlag) геометрическое хэширование (Nussinov et al)

49 Структурное выравнивание при помощи прототипов: STRUCTAL

Структурное выравнивание при помощи прототипов: STRUCTAL

Итерационное динамическое программирование для улучшения случайно выбранного начального выравнивания Шаги алгоритма начать с произвольного набора соответствий между двумя структурами (выравнивание пос-стей, вторичных структур, на глаз, случайное) выровнять две структуры, исходя из текущего набора соответствий построить матрицу весов (Нидлмана-Вунша), исходя из расстояний между всевозможными парами точек ДП: обратное движение по матрице весов для нахождения выравнивания с наибольшим суммарным весом повторение шагов 2-4, пока суммарный вес не перестанет меняться Метод эвристический, не гарантирует результата, зависит от выбора начального выравнивания

50 Структурное выравнивание при помощи прототипов: STRUCTAL (прод

Структурное выравнивание при помощи прототипов: STRUCTAL (прод

Оценка выравнивания: чем лучше выравнивание, тем выше суммарный вес возможность учесть дополнительные факторы Вес S(d) = M { 2 / [1 + (d/d0)2] – 1} где M – максимальный ожидаемый вес, d – измеряемая величина (e.g. расстояние между точками), d0 – значение d, соответствующее M = 0 При 0 ? d ? d0 увеличение веса, при d > d0 - штраф

51 Структурное выравнивание при помощи прототипов: STRUCTAL (прод

Структурное выравнивание при помощи прототипов: STRUCTAL (прод

Итерационное динамическое программирование

52 Структурное выравнивание при помощи прототипов: STRUCTAL (прод

Структурное выравнивание при помощи прототипов: STRUCTAL (прод

53 Структурное выравнивание при помощи прототипов: LOCK

Структурное выравнивание при помощи прототипов: LOCK

Основная идея: элементы вторичной структуры представляются при помощи векторов быстрый поиск похожих структур

54 Структурное выравнивание при помощи прототипов: LOCK (прод

Структурное выравнивание при помощи прототипов: LOCK (прод

Сравнение «векторов вторичной структуры»

55 Структурное выравнивание при помощи прототипов: LOCK (прод

Структурное выравнивание при помощи прототипов: LOCK (прод

Выравнивание «векторов вторичной структуры»

56 Структурное выравнивание при помощи прототипов: LOCK (прод

Структурное выравнивание при помощи прототипов: LOCK (прод

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

57 Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

(1)

58 Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

(1a)

59 Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

(1b)

60 Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

(2)

61 Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

Структурное выравнивание при помощи прототипов: шаги алгоритма LOCK

(3)

62 Структурное выравнивание: «за» и «против»

Структурное выравнивание: «за» и «против»

«Золотой» стандарт для выравнивания пос-стей Трехмерная структура часто неизвестна Структурное выравнивание не всегда отражает ход эволюции точная последовательность вставок/замен/делеций неизвестна

63 Прогрессивное выравнивание

Прогрессивное выравнивание

64 Прогрессивное выравнивание: идея

Прогрессивное выравнивание: идея

Сначала – эволюционно наиболее близкие пос-сти Постепенное добавление новых пос-стей / групп пос-стей Waterman & Perlwitz (1984) Feng & Doolittle (1987, 1996) Higgins et al. (1996) … Отображение близости на филогенетическом дереве методы попарного сравнения пос-стей Проблема: неопределенность отдельных замен

65 Неопределенность конкретных замен

Неопределенность конкретных замен

66 } ?

} ?

?

Филогенетический анализ – не панацея

Проблемы неопределенность в порядке замен / делеций взвешивание ветвей (пос-стей) подбор матрицы замен назначение штрафов за делеции Реализация: ClustalW/X и PILEUP

Отражение эволюции

67 Прогрессивное выравнивание

Прогрессивное выравнивание

x

y

z

w

Если эволюционное дерево известно сначала выравниваются элементы, самые близкие на эволюционном дереве на каждом шаге выравниваются пос-сти x и y, или профили px и py для построения нового выравнивания с профилем presult Версия со взвешиванием ветви дерева имеют веса, пропорциональные степени расхождения новый профиль – взвешенное среднее двух предыдущих

pxy

pxyzw

pzw

68 ?

?

Прогрессивное выравнивание (прод.)

x

y

z

w

Если эволюционное дерево неизвестно: построить всевозможные парные выравнивания определить матрицу расстояний D, элементы которой D(x, y) соответствуют эволюционному расстоянию, определенному по парным выравниваниям реконструировать эволюционное дерево (UPGMA / объединение соседей / другие методы) построить выравнивание на основе реконструированного дерева

69 Прогрессивное выравнивание: детали алгоритма

Прогрессивное выравнивание: детали алгоритма

Три этапа попарные выравнивания «каждая с каждой» филогенетическое дерево по весам парных выравниваний (по генетическим расстояниям) последовательное построение множественного выравнивания от похожих – к непохожим Первичные выравнивания k-кортежи поиск «мотивов» (a la FASTA) обычное или усовершенствованное (Myers & Miller, 1988) динамическое программирование Генетическое расстояние = (число замен) / (полное число соответствий) делеции не учитываются

Дерево

70 Прогрессивное выравнивание: детали алгоритма (прод

Прогрессивное выравнивание: детали алгоритма (прод

Взвешивание пос-стей (ветвей дерева) мультипликативная модель Штрафы за делеции предыдущие делеции влияют на последующие выравнивания местоположение делеций (учет вторичной структуры) таблица встречаемости делеций (Pascarella & Argos, 1992) штраф за открытие делеции и ее продолжение на каждую позицию штрафы во множественном выравнивании модифицируются с учетом матрицы замен, степени сходства и длины пос-стей Схема назначения штрафов в Clustal (1988) противоположна таковой в MSA чем уникальнее пос-сть, тем больше вес

71 Прогрессивное выравнивание: взвешивание ветвей дерева

Прогрессивное выравнивание: взвешивание ветвей дерева

72 Множественное выравнивание: популярный инструментарий

Множественное выравнивание: популярный инструментарий

ClustalX

DCSE

73 Прогрессивное выравнивание: штрафы за делеции

Прогрессивное выравнивание: штрафы за делеции

Существующие делеции влияют на выравнивание следующих пос-стей их позиции фиксируются ClustalW: размещение делеций между консервативными доменами Pascarella & Argos (1992): частоты встречаемости делеций после каждой АК в неконсервативных участках структурно близких белков Штрафы за открытие делеции за продолжение делеции та же схема за делеции внутри существующих делеций

74 Прогрессивное выравнивание: штрафы за делеции (прод

Прогрессивное выравнивание: штрафы за делеции (прод

Компенсационная модификация штрафов средний вес соответствий по матрице замен уровень гомологии между пос-стями длины пос-стей Таблица делеций для каждой группы выравниваемых пос-стей Другие варианты модификаций ? штрафов для областей с существующими делециями ? штрафов для областей, соседствующих с делециями ? штрафов для областей с гидрофильными АК

75 Clustalw: пример выравнивания семейства глобинов

Clustalw: пример выравнивания семейства глобинов

76 Прогрессивное выравнивание: проблемы

Прогрессивное выравнивание: проблемы

Результат зависит от начальных парных выравниваний ошибки первых выравниваний накапливаются выравнивание непохожих пос-стей ? Байесовские методы (e.g. HMM) Матрица замен и штрафы за делеции должны отражать специфику всего набора пос-стей

77 Прогрессивное выравнивание: вариант с иерархической кластеризацией

Прогрессивное выравнивание: вариант с иерархической кластеризацией

78 Инструментарий: ALSCRIPT (1993)

Инструментарий: ALSCRIPT (1993)

79 Инструментарий: AMAS (1993)

Инструментарий: AMAS (1993)

80 Итерационное выравнивание

Итерационное выравнивание

81 Итерационное выравнивание: идея метода

Итерационное выравнивание: идея метода

Задача избежать накопления ошибок начальных выравнива-ний, свойственных прогрессивным методам Вариант решения многократные итерационные выравнивания подгрупп последовательностей построение общего глобального выравнивания оптимизация общего веса выравнивания (суммы парных весов) Как выделить эти подгруппы? известное / предсказанное филогенетическое дерево K-out cross validation (KOCV) рандомизация

82 Итерационное выравнивание: варианты реализации

Итерационное выравнивание: варианты реализации

Multalin (corpet, 1998) пересчет весов парных выравниваний в прогрессивном алгоритме использование весов для пересчета дерева улучшение множественного выравнивания PRRP (1994) построение дерева по начальным парным выравниваниям вычисление весов по дереву и построение выравниваний по аналогии с MSA (но: локальные участки вместо глобального выравнивания + возможны делеции) итерационный пересчет локально выровненных участков для повышения веса выравнивания выравнивание с наибольшим весом ? новое дерево, новые веса и новые выравнивания повторение, пока суммарный вес не перестанет меняться

83 Итерационное выравнивание: блок-схема алгоритма PRRP

Итерационное выравнивание: блок-схема алгоритма PRRP

84 Итерационное выравнивание: варианты реализации (прод

Итерационное выравнивание: варианты реализации (прод

DIALIGN участки без делеций в попарных выравниваниях (аналогично точечной матрице) взвешенная сумма диагоналей Генетические алгоритмы SAGA (Notredame, Higgins, 1996) Zhang, Wang (1997)

85 Генетичекие алгоритмы: идея и реализация

Генетичекие алгоритмы: идея и реализация

Идея – имитация событий реальной эволюции Реализация (SAGA) делеции и рекомбинация в процессе репликации много множественных выравниваний ? увеличение суммарного веса Проблемы (SAGA) окончательное выравнивание не всегда оптимально или имеет максимально возможный вес значительные времена счета при > 20 пос-стях

86 Генетические алгоритмы: этапы

Генетические алгоритмы: этапы

Около 100 случайных начальных выравниваний перекрывание 20-25% от длины пос-стей делеции на концах Веса начальных выравниваний (SP) матрицы АК-замен штрафы за открытие / продолжение делеции наилучшее выравнивание – минимальный вес, ближайший к сумме весов парных выравниваний Репликация начальных выравниваний для генерации следующего поколения 50 % выравнивания (наименьшие веса) – неизменны оставшиеся 50%: вероятность выбора ~ вес-1 мутации в оставшихся 50% выравниваний

87 Генетичекие алгоритмы: этапы (прод

Генетичекие алгоритмы: этапы (прод

Мутации с учетом филогенетического дерева Мутации сдвигом блоков

88 Генетичекие алгоритмы: этапы (прод

Генетичекие алгоритмы: этапы (прод

Рекомбинации с учетом гомологии

89 Генетичекие алгоритмы: этапы (прод

Генетичекие алгоритмы: этапы (прод

Мутации прежний порядок АК добавление и перестановка делеций ? увеличение веса ориентация на дерево => группы белков, случайные длины и расположение делеций, фиксированные для данной группы делеции максимизируют вес делеции, разделяющие выровненные блоки Рекомбинация без учета гомологий – поиск максимального веса учет гомологий – сохранение консервативных позиций Оценка 50% родительских и 50% дочерних выравниваний повторение шагов репликация/мутации/рекомбинации 100-100 раз до достижения наилучшего веса Многократное повторение всего алгоритма до достижения наилучшего веса выравнивания

90 Локальные множественные выравнивания

Локальные множественные выравнивания

91 Локальные множественные выравнивания: виды алгоритмов

Локальные множественные выравнивания: виды алгоритмов

Анализ профилей Блочное выравнивание Поиск мотивов Статистические методы

92 Анализ профилей: введение

Анализ профилей: введение

Идея: MSA для группы пос-стей Выделение высоко консервативных участков в мини-MSA Профиль - матрица весов для мини-MSA Профиль допускает соответствия, замены, делеции и вставки Применения поиск соответствий профилю в последовательности-мишени (программа Profilesearch) в качестве матрицы замен для построения выравниваний (программа Profilegap) Две группы алгоритмов построения профилей метод средних эволюционный метод

93 Анализ профилей: идентификация в семействе белков теплового шока

Анализ профилей: идентификация в семействе белков теплового шока

(hsp70)

Матрица весов (профиль) содержит вероятности встречаемости АК в разных позициях

94 Построение профилей: метод средних

Построение профилей: метод средних

Элемент матрицы – взвешенная частота встречаемости частоты по MSA взвешивание все 20 потенциальных предшественниц данной АК равновероятны ИЛИ вероятности предшественников вычисляются из матриц замен (PAM, BLOSUM) штрафы за делеции

95 Построение профилей: эволюционный метод

Построение профилей: эволюционный метод

Определение эволюционного расстояния в единицах PAM для получения частот АК, наблюдаемых в выравнивании разные темпы эволюции в разных колонках MSA любая АК может быть предшественницей данной Информационная вероятность H = - ?a falog(pa) где f и p – наблюдаемая и ожидаемая частоты встречаемости АК в данной колонке MSA для фиксированного предшественника Информация H вычисляется для 20 АК и для разных эволюционных расстояний (PAMn) Поиск n = argmin (H) Байесовский анализ P(Ma|F) = P(Ma) x P(F|Ma) / ?a P(Ma) x P(F|Ma)

96 Блочное выравнивание: семейство из 34 тубулиновых белков

Блочное выравнивание: семейство из 34 тубулиновых белков

97 Анализ профилей: ограничения

Анализ профилей: ограничения

Профиль отражает вариабельность в данном MSA смещение в сторону похожих пос-стей вариант коррекции: Gribskov & Veternik, 1996 взвешивание пос-стей по удаленности на филогенетическом дереве: чем меньше расстояние, тем меньше вес Недостаточное число пос-стей в MSA некоторые АК на некоторых позициях не представлены

98 Профиль – позиционно-специфическая матрица замен

Профиль – позиционно-специфическая матрица замен

21 столбец и N строк N – длина последовательностей в выравнивании

99 Статистические методы множественного выравнивания

Статистические методы множественного выравнивания

100 Множественное выравнивание на базе вероятностно-статистических методов

Множественное выравнивание на базе вероятностно-статистических методов

Максимизация математического ожидания Сэмплирование Гиббса Скрытые марковские модели see Russ Altman, Lecture 4-27-06, pp. 8-20

101 Максимизация математического ожидания

Максимизация математического ожидания

102 Максимизация математического ожидания (Expectation Maximization, EM)

Максимизация математического ожидания (Expectation Maximization, EM)

Применение консервативные домены в невыровненных белках сайты связывания белков в невыровненных ДНК-последовательностях Предварительные шаги алгоритма произвольный выбор начального положения и длины искомого сайта в каждой пос-сти выравнивание пос-стей по выбранным «искомым» сайтам и вычисление частот встречаемости по столбцам Два основных этапа алгоритма Ожидание: оценка вероятности обнаружения сайта в каждой из позиций каждой из пос-стей по частотам Максимизация: использование новых частот

103 Максимизация математического ожидания: предварительное выр-ние

Максимизация математического ожидания: предварительное выр-ние

Таблица частот

104 Максимизация математического ожидания: таблица частот

Максимизация математического ожидания: таблица частот

Фон

Столбец 1

Столбец 2

G

0,27

0,4

0,1

C

0,25

0,4

0,1

A

0,25

0,1

0,1

T

0,23

0,1

0,7

1,00

1,0

1,0

1,0

Наиболее вероятные положения сайтов в каждой из пос-стей расчет вероятностей для разных позиций, исходя из таблицы на предыдущем шаге, путем перемножения вероятность для k-й позиции ? нормировка

105 Максимизация математического ожидания: этап «ожидание» (прод

Максимизация математического ожидания: этап «ожидание» (прод

- Вер-сти сайтов = весам - новые таблицы частот

106 Максимизация математического ожидания: этап максимизации

Максимизация математического ожидания: этап максимизации

Таблица частот, полученная на этапе «ожидания» Итерационное повторение двух этапов до тех пор, пока таблица не перестанет меняться Альтернативный метод подсчета частот встречаемости матрица весов – нормировка частот «внутри сайта» на фоновые величины Реализация – программа MEME (Multiple EM for Motif Elicitation), UCSD Supercomputing Center вариация длины мотива ? максимизация вер-сти ParaMEME (поиск блоков) MetaMEME (HMM)

107 Выборки Гиббса

Выборки Гиббса

108 Выборки Гиббса (Gibbs sampler)

Выборки Гиббса (Gibbs sampler)

Lawrence, CE et al. (1993). Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science, 262, 208-14. Применение множественное выравнивание пос-стей поиск мотивов (локальное множественное выр-ние) Та же идея, что в EM… поиск наиболее вероятных мотивов оценка их длины и положения в каждой из пос-стей … но другой алгоритм веса мотивов в пос-стях вместо вероятностей

109 Выборки Гиббса: алгоритм (прод

Выборки Гиббса: алгоритм (прод

110 Выборки Гиббса: идея

Выборки Гиббса: идея

Вероятностный профиль мотива длины w Base\Position 1 2 3 4 … w A 0.7 0.05 0.2 ... T 0.1 0.05 0.2 ... G 0.1 0.1 0.59 C 0.1 0.8 0.01 0.8 Фоновые вероятности: A – 0.3, T – 0.3, G – 0.2, C – 0.2 Задача: максимизировать разницу между частотным составом мотива и фоновым распределением вероятностей встречаемости

111 Выборки Гиббса: алгоритм

Выборки Гиббса: алгоритм

Шаг 1 (предсказание): произвольное расположение мотива во всех пос-стях, кроме одной вероятность встречаемости мотива = произведению частот встречаемости в мотиве фоновая вероятность для мотива = произведению фоновых частот встречаемости движение с единичным «окном»: W = Pmotif/Pbgrd ? max веса W для каждой позиции нормируются на сумму всех весов Шаг 2 (проверка и коррекция): случайный выбор расположения мотива в отброшенной пос-сти в соответствии с нормированными весами Повторение шагов 1 и 2 сотни или тысячи раз с учетом выбранного расположения мотива в ранее отброшенной пос-сти частоты встречаемости в столбцах мотива должны перестать меняться

112 Выборки Гиббса: алгоритм – шаг 1

Выборки Гиббса: алгоритм – шаг 1

Случайный выбор расположений мотивов Вычисление матрицы мотива фоновых частот

113 Выборки Гиббса: алгоритм – шаг 2a

Выборки Гиббса: алгоритм – шаг 2a

Исключение одной последовательности Обновление матрицы мотива

114 Выборки Гиббса: алгоритм – шаг 2b

Выборки Гиббса: алгоритм – шаг 2b

Для каждой позиции исключенной последовательности вычисление вероятности быть началом мотива

115 Выборки Гиббса: алгоритм – шаг 2b

Выборки Гиббса: алгоритм – шаг 2b

Допустим, мотив начинается в позиции p пос-сти и мы рассматриваем j-ю букву после p (s[p+j] = i) В какой мере она соответствует j–й позиции мотива? ?j = { nj (s[p + j]) + ?i } / (n* + ?*) где s[p + j] -- буква i в позиции p последовательности s nj(i) – число букв i в позиции j текущей матрицы мотивов n* -- все буквы, встретившиеся в позиции j мотива = выровненным сегментам ?i – псевдоколичество для буквы i Вес соответствия мотива, начинающегося в пос-сти с позиции p Fit (p) = ? ?i / ?background

116 Выборки Гиббса: алгоритм – шаг 2b

Выборки Гиббса: алгоритм – шаг 2b

Для каждой позиции исключенной последовательности вычисление вероятности быть началом мотива

117 Выборки Гиббса: алгоритм – шаг 2c

Выборки Гиббса: алгоритм – шаг 2c

Случайный выбор (sampling) начальной позиции мотива в исключенной последовательности по Fit(p)

118 Выборки Гиббса: алгоритм – шаг 2c

Выборки Гиббса: алгоритм – шаг 2c

Случайный выбор (sampling) начальной позиции мотива в исключенной последовательности по Fit(p)

119 Выборки Гиббса: алгоритм – шаг 2d

Выборки Гиббса: алгоритм – шаг 2d

Исключение другой последовательности – до схождения алгоритма

120 Выборки Гиббса: иллюстрация сходимости алгоритма

Выборки Гиббса: иллюстрация сходимости алгоритма

Матрица частот встречаемости и функция соответствия в начале итераций

121 Выборки Гиббса: иллюстрация сходимости алгоритма (прод

Выборки Гиббса: иллюстрация сходимости алгоритма (прод

Матрица частот встречаемости и функция соответствия вблизи точки сходимости алгоритма

122 Выборки Гиббса: алгоритм – шаг 3

Выборки Гиббса: алгоритм – шаг 3

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

123 Выборки Гиббса: куда двигаться дальше

Выборки Гиббса: куда двигаться дальше

Алгоритм стоило бы развить для анализа множественных консервативных мотивов, разделенных делециями мотивов неизвестной длины включения в выравнивания последовательностей, не содержащих мотива

124 Скрытые марковские модели (HMM)

Скрытые марковские модели (HMM)

125 Марковские модели (Markov Models): введение

Марковские модели (Markov Models): введение

Krogh et. al. (1994). Hidden Markov models in computational biology: applications to protein modeling. J. Mol. Biol. 235, 1501-1531. Определение: свойство марковости P(X0, X1, … , Xt) = P(X0) P(X1|X0) … P(Xt|Xt-1) Матрица переходов:

126 Марковские модели: введение (прод

Марковские модели: введение (прод

Марковская цепь пос-сть состояний, через которые проходит система Пример S0 , S1, S1, S1, S0 , S1, … вероятность такой пос-сти: P(Sequence) = P(S0 , S1, S1, S1, S0 , S1,…) = ? (S0) P(S1 | S0 ) P(S1 | S1) P(S1 | S1)…

127 Марковские модели: представление последовательности ДНК

Марковские модели: представление последовательности ДНК

P(AGATCG) = ?(A) P(G|A) P(A|G) P(T|A)…

128 Скрытые марковские модели (Hidden Markov Models)

Скрытые марковские модели (Hidden Markov Models)

Наблюдаемая пос-сть – вероятностная функция некоторой марковской цепи Исходная пос-сть состояний неизвестна (скрыта), но ее можно попробовать восстановить по наблюдаемой пос-сти «зашумленная пос-сть» ? возможны ошибки

129 Скрытые марковские модели: применение для множественного выравнивания

Скрытые марковские модели: применение для множественного выравнивания

Характеристики семейства выровненных последовательностей какие АК с какой вероятностью могут появиться в данном положении? где наиболее вероятны вставки и делеции? генерация гипотетических (но вполне вероятных) новых последовательностей семейства Оценка вероятности принадлежать семейству для новой последовательности позволяет ли модель создать высоковероятную последовательность? Построение самого выравнивания как объяснить «организацию» всех выровненных пос-стей, считая, что они принадлежат одному семейству?

130 Скрытые марковские модели: формализация множ

Скрытые марковские модели: формализация множ

выравнивания (2)

Красный цвет – выравнивание в столбце Зеленый цвет – вставка символа в столбце Пурпурный цвет – делеция в столбце

131 Скрытые марковские модели: формализация множ

Скрытые марковские модели: формализация множ

выравнивания (1)

m = состояние выравнивания ? появление одной АК выравнивание по соответствию или аналогичной замене в различных пос-стях i = состояние вставки ? появление (N-1) аминокислот, которые не могут быть выровнены d = состояние делеции ? новые АК не появляются

132 Скрытые марковские модели: формализация множ

Скрытые марковские модели: формализация множ

выравнивания (2)

133 Скрытые марковские модели: формализация множ

Скрытые марковские модели: формализация множ

выравнивания (3)

Скрытая марковская модель и вероятности переходов между состояниями

134 HMM для семейства глобинов

HMM для семейства глобинов

Высоковероятная последовательность V L S A E E K A N V K A … G H T P A - W QAK L C T S … m-состояния показаны с вер-стями появления каждой из 20 АК i-состояниям приписаны длины вставок, если они выбраны d-состояния показывают позицию в выравнивании столбца с данными m,i,d

135 Структурная геномика: выравнивание последовательностей
136 Выравнивание семейства глобинов

Выравнивание семейства глобинов

137 HMM: выравнивание последовательности по модели

HMM: выравнивание последовательности по модели

Для семейства белков построена HMM Для новой последовательности найти наиболее вероятный путь на графе

138 Скрытые марковские модели: программы для множ

Скрытые марковские модели: программы для множ

выравнивания

Sequence alignment and modeling (SAM) krogh et al. (1994), hughey & krogh (1996) HMMER eddy (1998) pfam – база данных белковых семейств sonhammer et al. (1997)

139 Скрытые марковские модели: три вычислительные задачи

Скрытые марковские модели: три вычислительные задачи

Вероятность наблюдаемой пос-сти для данной O1, O2, …, Ot найти P(O1, O2, …, Ot) Наиболее вероятная скрытая пос-сть состояний для данной O1, O2, …, Ot найти max P(Q1, Q2, …, Qt|O1, O2, …, Ot) O – наблюдаемые, Q – скрытые состояния Оценка параметров модели для набора наблюдаемых пос-стей {S1, S2, …, SN} и заданной топологии модели найти вероятности переходов и вставок ? max ? P(Si)

140 НММ: от обучения к применению

НММ: от обучения к применению

Инициализация модели для данного набора пос-стей своя HMM для каждого набора Итерационное обучение модели на 20-100 пос-стях представление вариабельности пос-стей из одного семейства построение наилучшей HMM для данного семейства пос-стей путем оптимизации вер-стей переходов и АК-состава в каждой выровненной позиции алгоритм forward-backward алгоритм Baum-Welch Применения множественные выравнивания (алгоритм Viterbi, аналог ДП) анализ пос-стей и представление профилей (HMM профиля пос-сти) анализ состава пос-стей предсказание структуры белков локализация генов путем предсказания ORF

141 НММ: проблемы

НММ: проблемы

Значительное число пос-стей для обучения Чувствительность к параметрам инициализации чем меньше начальное число пос-стей, тем выше чувствительность к начальным параметрам модели > 50 пос-стей ? чувствительность минимальна неравномерное распределение частот встречаемости АК PAM BLOSUM смеси Дирихле (Sj?lander, 1996) Слишком строгая «привязка» к обучающему семейству сглаживание частот встречаемости АК сохранение сведений о наиболее консервативных фрагмента метод регуляризации Чем больше различий в пос-стях, тем труднее построить выравнивание при помощи HMM Локальные оптимумы вместо глобальных подмешивание шума при обучении имитационный отжиг (simulated annealing)

«Структурная геномика: выравнивание последовательностей»
http://900igr.net/prezentacija/biologija/strukturnaja-genomika-vyravnivanie-posledovatelnostej-154464.html
cсылка на страницу
Урок

Биология

136 тем
Слайды
900igr.net > Презентации по биологии > Генная инженерия > Структурная геномика: выравнивание последовательностей