Rosalind.info — обзор

Rosalind.info — сайт, посвященный обучению биоинформатике при помощи решения задач по программированию. Система Rosalind.info немного напоминает сайты, посвященные олимпиадному программированию (например, codeforces.ru) в том смысле, что каждую задачу необходимо решить на заранее неизвестном  наборе данных, который в большинстве случаев генерируется или выбирается из большой коллекции. В то же время, по сравнению с олимпиадными условиями, сдавать задачи в Rosalind.info легче:

  • Задачи выполняются на компьютере пользователя, что открывает возможности к использованию сторонних инструментов, библиотек, кэшированию вспомогательных данных, ручной проверке или редактированию вывода и так далее.
  • Используется единственный набор входных данных, который выбирается в соответствии с реалиями биоинформатики, а не специально для того, чтобы «подловить» некорректные или неэффективные решения.
  • Лимит времени на выполнение программы составляет 5 минут — значительно больше, чем обычно в олимпиадном программировании. К тому же, время работы программ можно уменьшить за счет использования многопоточности и подобных средств, которые обычно запрещены в олимпиадном программировании.

Несмотря на такие послабления, некоторые задачи Rosalind заставляют серьезно задуматься (поиск минимального числа обращений, сортировка обращениями, поиск всех похожих мотивов, квартетное расстояние, филогения на основе признаков), но одолеть их вполне возможно (см. мою учетную запись), не используя низкоуровневых языков программирования или многопоточности — все задачи я решил на «чистом» Python. Для вычислений использовался ноутбук с CPU Intel Core i7 Q 720 (1.6 ГГц) и 8 Гб RAM под управлением Windows 7; большинство решений вычислялось достаточно быстро (не более 5–10 секунд), хотя некоторые занимали до трех минут (например, REAR и KSIM).

К сожалению, в FAQ рекомендуется не выкладывать свои решения в открытый доступ: материалы Rosalind, насколько я понимаю, используются в учебных курсах, и недобросовестные студенты будут очень рады готовым решениям. Тем не менее, имеет смысл рассмотреть общую структуру решений.

Классы и тестирование

Решение задачи можно представить в виде отдельного класса Solver:

Разумеется, для повышения модульности логически обособленные фрагменты решения стоит выделять в отдельные методы Solver. В принципе, эти методы вместе с solve можно объявить как глобальные функции, однако это грозит проблемами, например, при использовании кэширования. К тому же, в некоторых задачах решение можно параметризовать (например, стоит ли выводить диагностические сообщения), что при использовании функций означает потребность в хранении глобального состояния. В рамках ООП эта проблема решается элегантно:

Во время написания решения не мешает воспользоваться основой основ программной инженерии — модульным тестированием методов Solver. В Python для этой цели предназначен модуль unittest. Тестирование можно выделить в отдельный класс:

Для тестирования рационально выделить отдельный режим запуска файла (например, с командной опцией test):

Функция unittest.main() по умолчанию запускает все тесты (методы, начинающиеся на test) в классах, унаследованных от unittest.TestCase. Перечень тестов можно сузить с помощью аргументов командной строки (поэтому первый аргумент 'test' нужно удалить до вызова функции).

Ввод / вывод

Поскольку объем входных и / или выходных данных может быть достаточно большим, имеет смысл организовать работу с ними так, как это принято в олимпиадном программировании: читать ввод из стандартного входного потока и писать в стандартный выходной.

Для чтения данных их стандартного входа можно приспособить специальную функцию:

Функция работает как при перенаправлении входа из файла, так и без него (в этом случае вход надо завершить Ctrl + D в Linux или Ctrl + Z в Windows).

Поскольку семантика входных данных различается от задачи к задаче, разбор данных рационально осуществлять внутри класса Solver:

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

Повторное использование кода

При решении олимпиадных задач часто возникает необходимость повторно использовать фрагменты кода, такие как функции или классы. Это в полной мере касается задач Rosalind — например, во многих из них требуется использование суффиксных деревьев. Обычный способ повторного использования, заключающийся в выделении общего кода в отдельные модули, в данной ситуации плохо подходит, поскольку решение должно представлять собой единый файл. У самого простого решения этой проблемы — копирования участков кода из модулей — есть недостатки. Если нужно исправить общий код (например, чтобы исправить ошибку или для повышения эффективности), приходится вносить изменения во многие файлы.

Возможное решение проблемы — использование утилиты, которая автоматически заменяет декларации импорта вида from common import foo, bar на тела методов или классов из соответствующего исходного файла; в данном случае — методы foo и bar из файла common.py. Для этой цели можно приспособить простой сценарий на Python. Теоретически, для определения кода, соответствующего встраиваемым методам и классам и для построения зависимостей можно использовать средства из стандартной библиотеки Python вроде абстрактных синтаксических деревьев. На практике более простой вариант — пометить участки кода с помощью комментариев, напоминающих декларации #region в C#:

Преимущество такого подхода — возможность объединить несколько деклараций в одном участке. Декларация участка может содержать зависимости от других участков для корректного встраивания кода (при встраивании за счет использования дерева зависимостей можно выяснить, какие фрагменты нужно встраивать).

Ссылки

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *