Алгоритмы в биоинформатике, онлайн-курс

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

21 октября мы с Филлипом Компо ^[1] и Павлом Певзнером ^[2] из Университета Калифорнии запускаем онлайн-курс по алгоритмам в биоинформатике ^[3] на Coursera. Уже до 21 октября можно посмотреть содержание первой главы курса и порешать задачи на нашем новом образовательном проекте Stepic ^[4], над которым работает команда широко известного в узких (биоинформатических) кругах проекта Розалинд ^[5].

Секвенирование генома является лишь одной из сотен биологических задач, которые стали неразрывно связаны с вычислительными методами, необходимыми для их решения. В этом курсе будут рассмотрены алгоритмические идеи, которые являются фундаментальными для понимания современной биологии. Такие вычислительные понятия, как динамическое программирование и теория графов, помогут изучить алгоритмы, применяемые в широком спектре биологических задач: сборке геномов, сравнении последовательностей ДНК и белков, поиске регуляторных мотивов, анализе перестроек генома, идентификации белков, восстановлении дерева жизни и многих других. На протяжении всего курса, участники будут применять реальные алгоритмы из биоинформатики к реальным генетических данным.

Каждая глава курса содержит отдельно взятую биологическую тему. Например, первая глава посвящена поиску точек начала репликации (позиций в геноме, с которых ДНК начинает делиться в клетке), и как эту с первого взгляда сугубо биологическую задачу можно решить с помощью простого программирования и анализа геномных последовательностей.

Программа курса по неделям

1. Поиск точек начала репликации: Where Does DNA Replication Begin? (Algorithmic Warm-up)
2. Вычислительная масс-спектрометрия: How Do We Sequence Antibiotics? (Brute Force Algorithms)
3. Поиск часто повторяющихся последовательностей (регуляторных мотивов): Which DNA Patterns Act As Cellular Clocks? (Greedy and Randomized Algorithms)
4. Сборка геномов: How Do We Assemble Genomes? (Graph Algorithms)
5. Геномные перестройки: Are There Fragile Regions in the Human Genome? (Combinatorial Algorithms)
6. Выравнивание строк: How Do We Compare Biological Sequences? (Dynamic Programming Algorithms)
7. Быстрый поиск подстроки, индексирование строк: How Do We Locate Disease-Causing Mutations? (Combinatorial Pattern Matching)

Вступительное видео профессора Певзнера

Massive Open Online Research

Важной составляющей курса являются открытые научные задачи, сформулированные к каждой главе. Дискуссию по каждой задаче будет курировать ведущий учёный-биоинформатик в каждой конкретной области. Например, открытые задачи из первой главы курса ^[6] курируют Михаил Гельфанд ^[7] (ИППИ РАН, МГУ), Uri Keich ^[8] (University of Sydney) и Glenn Tesler ^[9] (UCSD).

Ссылки по теме

• Coursera: Bioinformatics Algorithms (Part 1) ^[3]
• Stepic: Bioinformatics Algorithms: An Active-Learning Approach ^[10]
• Пресс-релиз курса от University of California, San Diego ^[11]
• Пресс-релиз курса от California Institute for Telecommunications and Information Technology ^[12]
• UC San Diego Team To Intro Massive Open Online Research ^[13]
• Предварительная детализированная программа курса (pdf) ^[14]
• Розалинд — платформа для изучения биоинформатики ^[15]
• Институт биоинформатики ^[16]

Автор: vyahhi

Источник ^[17]