Магистратура
2020/2021
Алгоритмы в биоинформатике
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Программирование и анализ данных)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
1-й курс, 1-4 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Елисеев Антон Игоревич
Прогр. обучения:
Программирование и анализ данных
Язык:
русский
Кредиты:
6
Контактные часы:
92
Программа дисциплины
Аннотация
Проект по секвенированию генома, начатый в 2001 году, произвел революцию в области вычислительной биологии. Результатом является постоянная востребованность в новых алгоритмах, в которых современная биология нуждается, вероятно, больше, чем любая другая область научной деятельности. Возникшая связь между информатикой и биологией влияет на процесс обучение и биологов, и программистов. Секвенирование генома лишь одна из множества проблем, решение которых тесно связано с вычислительными методами. В этом курсе будут рассмотрены базовые алгоритмы, необходимые для понимания современной биологии. Будут рассмотрены такие методы, как динамическое программирование и сетевой анализ, применимые к широкому кругу биологических задач (от поиска генов до построения филогенетического древа жизни). Процесс обучения будет построен на применении настоящих биоинформатических алгоритмов для анализа реальных генетических образцов. Для выполнения домашнего задания и закрепления изученного материала будет применяться интернет-платформа Rosalind (http://rosalind.info) — ресурс для изучения биоинформатики, созданный при участии авторов курса. Мы надеемся, что с помощью Rosalind вы поймете, насколько увлекательным может быть решение биоинформатических задач.
Цель освоения дисциплины
- формирование у студентов теоретических знаний и практических навыков по алгоритмам, необходимым для успешного решения биоинформатических задач.
Планируемые результаты обучения
- − уметь реализовывать алгоритмы Нуссинов и Цукера предсказания вторичной структуры РНК;
- − знать и уметь применять основные биоинформатические алгоритмы для решения задач, связанных с анализом генов;
- − уметь применять алгоритм BLAST для поиска последовательностей в общедоступных базах генов;
- − иметь навыки (приобрести опыт) анализа поставленных биоинформатических задач и определения подхода к их решению.
Содержание учебной дисциплины
- Задача выравнивания.Задача парного выравнивания. Редакционное расстояние. Алгоритм вычисления редакционного расстояния. Алгоритм выравнивания Миллера-Майерса. Локальное выравнивание. Алгоритм Смита-Ватермана. Выравнивание с аффинными гэпами. Подход meet-in-the-middle. Алгоритм Хиршберга.
- HMM.HMM. Эмиссионные и переходные вероятности. Примеры HMM. Алгоритм Viterbi. Алгоритм Forward-Backward. Оценка параметров HMM при наличии обучающей выборки. Оценка параметров при отсутствии обучающей выборки. Алгоритм Баума-Велча. Оценка качества обучения. Селективность и специфичность.
- Предсказание вторичной структуры РНК.Вторичная структура РНК. Элементы вторичной структуры. Энергия вторичной структуры РНК. Комбинаторный метод предсказания вторичной структуры. Алгоритм Нуссинов. Алгоритм Цукера.
- Предсказание генов.Предсказание генов в прокариотах. Предсказание генов в эукариотах с помощью HMM. Предсказание генов с помощью сходства.
- Множественное выравнивание.Качество выравнивания. Энтропия. Сумма пар. Прогрессивное выравнивание. ClustalW. Принцип его работы. Улучшение выравнивания.
- Поиск в базах. BLASTЗадача выравнивания одной последовательности на базу последовательностей. Выравнивание последовательности на бор. Алгоритмы BLAST и BLAST2.
Элементы контроля
- ДОМАШНЕЕ ЗАДАНИЕ №1Домашнее задание №1 выдается студентам в одном варианте. Срок выполнения домашнего задания – 2 недели. Форма представления обучающимися домашнего задания – программа на языке C++.
- ДОМАШНЕЕ ЗАДАНИЕ №2Домашнее задание №2 выдается студентам в одном варианте. Срок выполнения домашнего задания – 2 недели. Форма представления обучающимися домашнего задания – программа на языке Python.
- ДОМАШНЕЕ ЗАДАНИЕ №3Домашнее задание №3 выдается студентам в одном варианте. Срок выполнения домашнего задания – 2 недели. Форма представления обучающимися домашнего задания – программа на языке Haskell.
- УСТНЫЙ ЭКЗАМЕНУстный экзамен проводится в форме ответов на вопросы экзаменационного билета и дополнительные вопросы по материалам курса. Экзаменационный билет содержит два вопроса. На подготовку ответа выделяется 40 минут.
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.14 * ДОМАШНЕЕ ЗАДАНИЕ №1 + 0.17 * ДОМАШНЕЕ ЗАДАНИЕ №2 + 0.19 * ДОМАШНЕЕ ЗАДАНИЕ №3 + 0.5 * УСТНЫЙ ЭКЗАМЕН
- Промежуточная аттестация (4 модуль)0.19 * ДОМАШНЕЕ ЗАДАНИЕ №1 + 0.14 * ДОМАШНЕЕ ЗАДАНИЕ №2 + 0.17 * ДОМАШНЕЕ ЗАДАНИЕ №3 + 0.5 * УСТНЫЙ ЭКЗАМЕН
Список литературы
Рекомендуемая основная литература
- Pevsner, J. (2015). Bioinformatics and Functional Genomics (Vol. Third edition). Chichester, West Sussex, UK: Wiley-Blackwell. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1055003
- Rocha, M., & Ferreira, P. G. (2018). Bioinformatics Algorithms : Design and Implementation in Python (Vol. First edition). London: Academic Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1572286
Рекомендуемая дополнительная литература
- Bioinformatics for Evolutionary Biologists: A Problems Approach. Haubold, B., Börsch-Haubold, A. Springer International Publishing, 2017. eBook ISBN 978-3-319-67395-0.
- Bioinformatics. Volume I: Data, Sequence Analysis, and Evolution / Jonathan M. Keith. Humana Press, 2017. eBook ISBN 978-1-4939-6622-6.