Алгоритмы в биоинформатике

Планируемые темы[править]

Задача парного выравнивания. Количество выравниваний. Редакционное расстояние. Алгоритм вычисления редакционного расстояния.
Алгоритм выравнивания Миллера-Маерса
Локальное выравнивание. Алгоритм Смита-Ватермана
Алгоритм выравнивания при общих штрафах за делецию. Алгоритм выравнивания для аффинных штрафов за делецию.
Статистика выравниваний. Наибольшее общее слово. Наибольшая общая подпоследовательность. Линейное и логарифмическое поведение веса выравнивания.
Матрицы сопоставления аминокислотных остатков. Серия PAM. Серия BLOSUM.
Поиск по банку. Хэширование. FASTA, BLAST, BLAST2, быстрое выравнивание.
Байесова статистика. Априорное и апостериорное распределение. Распределение Дирихле. Оценка правдоподобия, матожидания и апостериорная оценка. Оценка параметров по результатам наблюдения.
HMM. Эмиссионные и переходные вероятности. Примеры HMM. Алгоритм Viterbi. Алгоритм Forward-Backward.
Оценка параметров HMM при наличии обучающей выборки. Биологические примеры. Оценка параметров при отсутствии обучающей выборки. Алгоритм Баума-Велча. Оценка качества обучения. Селективность и специфичность.
Профили. Консенсус, Регулярное выражение, Частотный профиль. Энтропия колонки. HMM профиль. Учет возможности вставок и делеций.
Псевдоотсчеты. Правило Лапласа, Учет фоновых частот, Учет матрицы замен.
Взвешивание последовательностей. Метод Герштейна-Сонхаммера-Чотьи. Многогранники Вороного,
Множественное выравнивание. Качество выравнивания. Энтропия, Сумма пар. Динамическое программирование. Прогрессивное выравнивание. ClustalW. Улучшение выравнивания.
Поиск сигналов. Постановка задачи. Алгоритм MEME. Гиббс сэмплер.
Вторичная структура РНК. Элементы вторичной структуры. Энергия вторичной структуры РНК.
Комбинаторный метод предсказания вторичной структуры.
Алгоритм Нуссинофф. Алгоритм Зукера. Субоптимальные структуры.
Консенсусные вторичные структуры. Метод ковариций.
Контекстно-свободные грамматики и вторичная структура РНК.
Предсказание генов в прокариотах.
Предсказание генов в эукариотах с помощью HMM.
Предсказание генов с помощью сходства.