• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2020/2021
Учебный год
RUS
Обучение ведется на русском языке
6
Кредиты
Статус:
Курс по выбору
Когда читается:
1-й курс, 1-4 модуль

Преподаватель


Елисеев Антон Игоревич

Программа дисциплины

Аннотация

Проект по секвенированию генома, начатый в 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.