Презентации / Информатика 6 Класс / Алгоритмы биоинформатики

ФББ 2004 г., осенний семестр, 3-й курс. Миронов Андрей Александрович
Скачать презентацию: Алгоритмы биоинформатики
Информатика и Биоинформатика
Пример: сравнение последовательностей
Сравнение последовательностей
Выравнивания
Редакционное расстояние
Сколько существует выравниваний?
Динамическое программирование для редакционного расстояния
Подмена задачи и обобщение
Граничные условия
Как не штрафовать за концевые делеции
Оценка времени работы и необходимой памяти
Где можно сэкономить?
Линейный по памяти алгоритм Миллера-Маерса
Алгоритм Миллера-Маерса
Еще один способ сэкономить время и память
Локальное выравнивание
Алгоритм Смита-Ватермана
Более общая зависимость штрафа за делецию от величины делеции
Более общая зависимость штрафа за делецию от величины делеции. Алгоритм
Аффинные штрафы за делецию
Алгоритм для аффинных штрафов
Рекурсия для аффинных штрафов
Матрицы замен
Откуда берутся параметры для выравнивания?
Серия матриц BLOSUM
Серия матриц PAM
Статистика выравниваний
Параметры выравнивания
Статистика выравниваний
Частные случаи локального выравнивания
Наибольшая общая подпоследовательность
Наибольшее общее слово
Зависимость от параметров
Распределение экстремальных значений
e-value & p-value
Поиск по банку
Поиск по банку. Хеширование
Поиск по банку. FASTA
Поиск по банку. BLAST1
Поиск по банку. BLAST2
Быстрое выравнивание
Введение в Байесову статистику
Определения
Пример
Оценка параметров по результатам
Распределение Дирихле
prior = распределение Дирихле
Скрытые Марковские модели (HMM)
Пример
Биологические примеры
Описание HMM
Решение задачи о монете
Viterbi рекурсия
Другая постановка задачи
Оценка параметров HMM
Оценка параметров HMM при наличии обучающей выборки
Если нет обучающей выборки
Оценки параметров по Бауму-Велчу
Предсказание кодирующих областей в прокариотах
Оценка качества обучения
Профили
Способы описания множественного выравнивания
Энтропия колонки
HMM профиль
HMM с учетом возможности вставок
Определение параметров модели
Для тонких выравниваний
Смеси Дирихле
Использование матрицы замен
Использование предка
А чему же равно A?
Это еще не все …
Взвешивание последовательностей
Взвешивание последовательностей Метод Герштейна-Сонхаммера-Чотьи
Взвешивание последовательностей Многогранники Воронова
Взвешивание последовательностей Максимально дискриминирующие веса
Взвешивание последовательностей Максимизация энтропии
Множественное выравнивание
Оценка качества множественного выравнивания Энтропийная оценка
Оценка качества множественного выравнивания Сумма пар
Если есть функционал, то его надо оптимизировать
Динамическое программирование для множественного выравнивания
Прогрессивное выравнивание
Выравнивание профилей
ClustalW
Улучшение выравнивания
Множественное выравнивание с помощью HMM
Блочное выравнивание
Поиск сигналов
Постановка задачи
Графвая постановка задачи
HMM-постановка задачи
Алгоритм максимизации ожидания
Гиббс сэмплер
Вероятности для Гиббс сэмплера
Комбинаторные методы
RNA
Вторичная структура РНК
Элементы вторичной структуры
Способы представления вторичных структур
Задача
Комбинаторный подход
Структуры без псевдоузлов
Оптимизация количества спаренных оснований
Динамическое программирование для количества спаренных оснований (Нуссинофф)
Динамическое программирование для количества спаренных оснований
Восстановление структуры по матрице спаривания
Энергия вторичной структуры
Энергия петель
Минимизация энергии
Алгоритм Зукера
Проблемы минимизации энергии
Решение проблем
Поиск субоптимальных структур и структурных элементов
Консенсусные вторичные структуры РНК
Основные задачи
Метод ковариаций
Грамматики
Стохастические контекстно-свободные грамматики
Задача выравнивания СКСГ с последовательностью
Общая модель для выравнивания вторичной структуры с последовательностью
Общая идея алгоритма разбора последовательности
Поиск генов