Введение в биоинформатику

Кафедра прикладной математики

Специальность: Прикладная математика и информатика

Преподаватель: Юсипов И.И.

Предметом рассмотрения настоящего курса являются основные задачи биоинформатики, которые могут быть сформулированы как задачи поиска, выравнивания, прочие задачи на строках и графах. Цель курса состоит в изучении соответствующих методов и алгоритмов биоинформатики. Особое внимание уделяется формированию у студентов навыков реализации и применения рассматриваемых методов к решению конкретных биоинформатических задач. Задачей дисциплины является теоретическое и практическое освоение вышеупомянутых методов и алгоритмов.

В результате освоения дисциплины обучающийся должен:

Знать:

– базовые алгоритмы биоинформатики, условия их применимости.

Уметь:

– определять и профессионально реализовывать необходимые для решения прикладных задач биоинформатики вычислительные алгоритмы, анализировать полученные результаты;

– профессионально разрабатывать и использовать программное обеспечение для решения прикладных задач биоинформатики;

-  проводить процедуры корректности работы реализуемых численных методов.

Владеть:

– вычислительными методами биоинформатики;

– современными инструментальными вычислительными средствами.

Содержание

Тема 1. Введение. Основные макромолекулы живых организмов.

Тема 2. Алгоритмы полного перебора.

Тема 3. Поисковые деревья. Метод ветвей и границ.

Тема 4. Динамическое программирование. Введение.

Тема 5. Динамическое программирование. Локальное и глобальное выравнивание.

Тема 6. Графовые алгоритмы.

 

Выполнение лабораторных работ на следующие темы

  1. Введение. Основные макромолекулы живых организмов
    • Поиск обратно-комплементарной цепи ДНК.
    • Поиск стартовых позиций паттерна в геноме.
    • Определение числа вхождений паттерна в геном.
    • *Определение числа вхождений паттерна в геном с учетом возможных допустимых мутаций паттерна.
    • Поиск наиболее часто встречаемых паттернов в геноме.
    • *Поиск наиболее часто встречаемых паттернов в геноме с учетом возможных допустимых мутаций.
    • *Поиск наиболее часто встречаемых паттернов в геноме, а также в обратно-комплементарной цепи для заданного генома, с учетом возможных допустимых мутаций.
    • *Поиск паттерна, встречающегося в подстроках генома фиксированной длины не менее заданного числа раз (Clump Finding Problem).
  2. Алгоритмы полного перебора
    • Алгоритм полного перебора для задачи поиска регуляторного мотива.
    • Алгоритм полного перебора для задачи поиска срединной строки.
    • *Поиск наиболее вероятного паттерна в геноме.
  3. Поисковые деревья. Метод ветвей и границ
    • Алгоритм ветвей и границ для задачи поиска регуляторного мотива.
    • Алгоритм ветвей и границ для задачи поиска срединной строки.
  4. Динамическое программирование. Введение
    • Решение задачи о размене монет (нерекурсивный алгоритм динамического программирования).
    • Решение задачи о манхэттенском туристе.
    • *Поиск длиннейшей общей подстроки.
  5. Динамическое программирование. Локальное и глобальное выравнивание
    • Алгоритм глобального выравнивания с использованием оценочной матрицы «BLOSUM62».
    • Алгоритм локального выравнивания с использованием оценочной матрицы «PAM250».
    • *Задача о подсчете операций при трансформировании строк.
    • *Аппроксимирующее выравнивание.
    • *Перекрывающее выравнивание.
    • Глобальное выравнивание с аффинными штрафами за непрерывные пропуски.
  6. Графовые алгоритмы
    • Задача о композиции строк.
    • Задача о формировании простого пути генома.
    • Построение графа перекрытий для заданного генома.
    • Построение графа де Брейна для заданного генома.
    • Нахождение Эйлерова цикла в графе.
    • Нахождение Эйлерова пути в графе.
    • Задача восстановления генома.

Литература

а) основная литература:

  1. An Introduction to Bioinformatics Algorithms. Neil C. Jones, Pavel A. Pevzner. MIT Press. 2004.
  2. Computational Molecular Biology: An Algorithmic Approach. Pavel A. Pevzner. MIT Press. 2000.

б) дополнительная литература:

  1. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Daniel M. Gusfield. Cambridge University Press, 1997.
  2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2013. — 1328 с.

в) программное обеспечение и Интернет-ресурсы

  1. Курс «Алгоритмы биоинформатики» Н.И.Вяххи: https://www.lektorium.tv/course/22933

Отчетность

  • Семестр 1: Зач