2024
2023
2022
2021
2020
2019
2018
2017
Алгоритмы биоинформатики
Требуемые знания по вопросам, входящим в билеты, более или менее покрываются презентацией. Разумеется, "на пятёрку" надо будет знать подробности, которые в презентацию не входят. В любом случае просто выписать формулу недостаточно, надо понимать смысл всех входящих в формулу обозначений.
Подробности по большинству вопросов есть в книге Дурбина с соавт.
По проблеме малой сложности см. статьи:
По алгоритму DUST: http://www.kodomo.fbb.msu.ru/FBB/year_10/ppt/DUST.pdf
По алгоритму SEG: http://www.kodomo.fbb.msu.ru/FBB/year_10/ppt/SEG-96.pdf
По корректировке матрицы замен: http://www.pnas.org/content/100/26/15688.full
Из этих статей, разумеется, нужно учить не всё, а лишь постановку задачи и описания алгоритмов.
В качестве дополнительных вопросов могут быть заданы относящиеся к темам лекций А.Фаворова: о методе Монте-Карло и о множественном тестировании.
Презентация о методе Монте-Карло.
Презентация о P-value и множественном тестировании.
Билеты
- Задача парного выравнивания. Количество выравниваний. Вес выравнивания. Наибольшее общее слово и наибольшая общая подпоследовательность как частные случаи оптимального выравнивания.
Алгоритмы выравнивания Нидлмана – Вунша и Миллера – Маерса (при линейных штрафах за делецию).
- Алгоритм выравнивания при общих штрафах за делецию. Алгоритм выравнивания при аффинных штрафах за делецию.
Локальное выравнивание. Алгоритм Смита – Уотермана.
- Матрицы BLOSUM и вероятностная модель, на которой они основаны. Матрицы PAM.
- Модели случайных последовательностей. Статистика локальных выравниваний. P-value и E-value.
- Быстрое выравнивание и поиск по банку. Отбор диагоналей. Fasta. Хэширование ("затравки"). BLAST, BLAST2.
- Проблема малой сложности. Программы seg и dust.
- Корректировка матрицы замен по Юй и Альтшулю.
- Байесова статистика. Априорное и апостериорное распределение. Распределение Дирихле. Оценка наибольшего правдоподобия, оценка по матожиданию и оценка по максимальной апостериорной вероятности. Оценка параметров по результатам наблюдения.
- Скрытые марковские модели (HMM). Эмиссионные и переходные вероятности. Примеры HMM.
- Алгоритм Витерби.
- Алгоритм "вперёд-назад".
- Оценка параметров HMM при наличии обучающей выборки. Биологические примеры. Показатели качества обучения.
Оценка параметров HMM при отсутствии обучающей выборки. Обучение по Витерби. Алгоритм Баума – Велча.
- HMM для парного выравнивания.
- Множественное выравнивание. Оценка качества выравнивания. Энтропия колонки, сумма весов пар.
- Профили (PSSM). HMM профиль. Учет возможности вставок и делеций.
- Псевдоотсчеты. Правило Лапласа. Учет фоновых частот. Учет матрицы замен. Связь с байесовой статистикой.
Взвешивание последовательностей. Метод Герштейна – Сонхаммера – Чотьи. Метод Хеникофф. Максимизация энтропии. Многогранники Вороного.
- Алгоритмы множественного выравнивания. Динамическое программирование. Прогрессивное выравнивание. Улучшение выравнивания. ClustalW и Muscle.
- Поиск сигналов. Постановка задачи. Алгоритм MEME. Выборки Гиббса.
- Вторичная структура РНК. Элементы вторичной структуры. Энергия вторичной структуры РНК. Алгоритмы предсказания вторичной структуры.