Алексей Махоткин

домашняя страница

Онлайн-курс «Алгоритмы биоинформатики» на Coursera

Год назад я прошел курс “Алгоритмы биоинформатики, ч. I” (университет Сан-Диего, проф. Павел Певзнер) и хочу порекомендовать его, поделившись своим опытом. В понедельник, 20 октября 2014 года, курс начинается заново, и у вас есть время подключиться — задачки первой недели совсем простые.

Курс ведется с помощью системы Stepic, это такой движок интерактивных учебников программирования, который позволяет принимать задания в автоматическом режиме. Каждую задачу надо запрограммировать, затем скачать контрольные входные данные, обработать их и полученный результат скормить обратно Степику. Если ответ верен, то Степик автоматически помечает задание на Курсере как пройденное (для этого надо подключить Степик к Курсере — это описано во вводной курса). Повторять попытки можно (кажется) неограниченное количество раз, просто в следующий раз вам дадут новый набор данных.

Теоретическая часть представляет собой видео-лекции четырех лекторов на английском языке, очень короткие — суммарно около часа на неделю. Тот же самый материал изложен на Степике в текстовом виде. Преподаватели также экспериментировали: одну неделю “видео без текста”, другую неделю — “текст без видео”. Надеюсь, что в этом году таких экспериментов не будет.

Для каждого задания дается два тестовых набора данных — один совсем короткий, другой подлиннее. Финальное контрольное задание, которое собственно нужно обработать, чтобы получить зачет, обычно еще длиннее, чем второе тестовое. Иногда это приводит к проблемам — некоторые случаи и условия не встречаются в коротком тестовом наборе, а проявляются только во втором тестовом. Я видел даже пару случаев, когда некоторые варианты реально встречаются только в финальном контрольном задании. Однако, я надеюсь, что в этом году многие такие баги уже будут поправлены — наш курс был первым, и мы были фактически бета-тестерами всей системы. Иногда это добавляет ненужного стресса, но на курсовом форуме преподаватели всегда внимательно слушали баг-репорты и оперативно их исправляли.

Степик основан на более ранней системе Розалинд, которая специально предназначалась для обучения биоинформатике.

Программировать можно на любом языке программирования — контрольные примеры представляют собой текстовые файлы простого ASCII-формата. Никаких специфических модулей для биоинформатики не требуется — задача всегда состоит в том, чтобы запрограммировать алгоритм с нуля. “Каноническим” языком считается Python — на Степике даже есть отдельный курс обучения Питону для биоинформатиков. Однако, я очень рекомендую программировать на хорошо знакомом языке, потому что стресс от новых задач и так достаточно высок, и если еще тратить усилия на борьбу с незнакомым языком, то есть риск просто не справиться. Подавляющее большинство учащихся было программистами. Людей со стороны биологии было несколько процентов, и тем большее уважение внушает то, как они справлялись с заданиями — были люди, которые действительно прямо перед этим курсом выучили Питон, и прямо на свежевыученном и программировал и сдавали задания. Я бы не смог.

Я программировал на Perl, на котором пишу с закрытыми глазами, и мне понравилось. На финальный контрольный прогон задачи дается всего пять минут, и для некоторых алгоритмов тестовые наборы рассчитаны так, чтобы их нельзя было решить “в лоб”, а требовалось именно запрограммировать ту оптимизацию или тот алгоритм, который требуется в учебном задании — в противном случае мощности типичного ноутбука не хватает. С одним заданием я долго возился, потому что не умещался в отведенное время. Попробовал даже запрограммировать автоматическое распараллеливание задачи на четыре процессора моего MacBook Pro (с помощью Makefile для автоматического распараллеливания). В результате оказалось, что я неправильно понял теоретическую часть, и не запрограммировал собственно главную оптимизацию, из-за которой все затевалось.

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

Курс состоит из шести секций (10 недель, но в прошлом году нам удлиняли сроки из-за проблем со Степиком, новогодних каникул и из общей скорости группы): базовые алгоритмы; алгоритмы полного перебора; “жадные” и рандомизированные алгоритмы; графовые алгоритмы; алгоритмы динамического программирования; комбинаторные алгоритмы.

Рандомизированные алгоритмы стали первыми, оказавшими на меня большое впечатление. Есть что-то магическое в том, что алгоритм на случайных тестовых данных начинает со случайного места, делает несколько случайных шагов, запоминает лучшие варианты, и самый лучший из запомненных оказывается “верным” — то есть, с этим вариантом согласен автоматический верификатор. В инструкции даже написано, что чисто теоретически ваш алгоритм может и не найти “наилучшего” варианта, и верификатор не примет ответ. В этом случае рекомендуется просто повторить прогон. У меня все ответы прошли с первого раза, и в этом есть что-то глубоко удивительное.

Графовые алгоритмы очень интересны, с некоей дополнительной особенностью — графы в некоторых задачах фактически настолько регулярны, что представляются обычной двумерной таблицей. Однако, следующая итерация задачи требует отбросить “жесткое” табличное представление и сделать полноценное “мягкое” графовое представление. Такое переключение позволяет по-новому взглянуть и на первое, и на последнее представления.

Задачи динамического программирования оказались для меня очень простыми, потому что я редактировал соответствующую статью Дмитрия Астапова в журнале “Практика функционального программирования”.

Самым интересным в комбинаторных алгоритмах было, конечно же, преобразование Берроуза-Уилера. На мой взгляд, это один из самых удивительных алгоритмов во всей computer science, и я до сих пор не понимаю, откуда он взялся, хоть и написал и успешно сдал несколько последовательных итераций этого алгоритма с различными все более сложными оптимизациями.

Через две-три недели после начала курса у нас была очень интересная встреча московских студентов с преподавателями (Павлом Певзнером и Николаем Вяххи), которая состоялась на площадке Цифрового Октября. На встрече также присутствовал Михаил Гельфанд.

Очень интересным и важным было чтение форумов — неоднократно это выводило из тупика, потому что кто-нибудь объяснял, где именно задание не до конца ясно сформулировано и что на самом деле имеется в виду. Это было очень ценно, и без этого я лично не прошел бы курс.

Зимой 2015 года начнется вторая часть курса, которую я обязательно буду проходить, чего и всем желаю.

Comments