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

В системе Rosalind.info филогенетические деревья используются в нескольких задачах:

• построение дерева  на основе признаков (CHBP);
• восстановление генетической информации предков на основе этих данных у потомков (ALPH);
• сравнение двух филогенетических деревьев с  помощью расстояния на основе разделений (англ. split) и квартетов (англ. quartet) — SPTD и QRTD, соответственно.

Имеет смысл рассмотреть общие задачи, полезные для их решения:

• построение дерева на основе текстового представления;
• вычисление рекуррентных функций на деревьях;
• сравнение деревьев между собой.

Читать далее Rosalind.info — алгоритмы на деревьях →

Несмотря на то, что кэширование может быть чрезвычайно полезным для ускорения вычисления рекуррентных отношений, оно не решает проблему переполнения стека вызовов. Например, в ходе вычисления n-го числа Фибоначчи по формуле

стек будет содержать n вызовов F(n - 1), F(n - 2), …, F(1), F(0). Это означает, что при значениях n около 1000 стек вызовов Python исчерпается, возбудив ошибку времени выполнения (RuntimeError).

Для того чтобы избежать переполнения стека, можно воспользоваться техникой динамического программирования. В широком смысле динамическое программирование означает, что решение задачи зависит от решения ограниченного числа подзадач меньшего размера; очевидно, это утверждение справедливо для рекуррентных отношений. Вместе с тем, зачастую под динамическим программированием подразумевается частный способ его реализации, при котором вычисления производятся «снизу вверх» (bottom-up approach). Это означает, что сначала вычисляются простые задачи, а затем на их основе агрегируются решения более сложных задач. Именно этот подход позволяет избавиться от рекурсии и, следовательно, переполнения стека.

Динамическое программирование широко используется в биоинформатике, прежде всего для выравнивания биополимеров (участков ДНК и белков). В системе Rosalind.info выравниванию посвящены задачи EDIT, EDTA, GLOB, LOCA, GAFF, LAFF, OSYM, KSIM и другие. Другое применение динамического программирования — распознавание с использованием скрытых марковских моделей (алгоритм Витерби).

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

Читать далее Rosalind.info — динамическое программирование →

Во многих задачах биоиноформатики возникает проблема вычисления рекуррентных отношений. Простейший пример рекуррентного отношения — числа Фибоначчи, задаваемые уравнениями

В рамках биоинформатики числа Фибоначчи и подобные используются для описания динамики популяций (числа F(n) равны размеру популяции при условии бессмертия индивидов). Обобщения чисел Фибоначчи рассматриваются в задачах Rosalind FIB и FIBD.

Другой пример рекуррентного отношения — числа Каталана, которые можно задать рекуррентным отношением

C(n) равняется количеству правильных скобочных последовательностей длины 2n. В биоинформатике подобные числам Каталана формулы возникают в задачах сворачивания молекул РНК (см. задачи Rosalind CAT, MMCH, PMCH).

Простейший способ вычисления рекуррентных отношений — использование рекуррентных вызовов функций — на практике редко приводит к эффективным решениям:

• Значение функции для одного и того же набора аргументов при рекуррентных вызовах может вычисляться несколько раз.
• Глубина стека вызовов в современных системах выполнения хоть и велика, но все же ограничена.

Для борьбы с первой проблемой можно использовать кэширование (другое название — мемоизация) результатов вычислений. Справиться с обеими проблемами позволяет динамическое программирование. В рамках Python оба этих средства могут быть реализованы как при помощи императивной парадигмы (то есть так, как в C++ или Pascal), так и с использованием шаблонов функционального программирования.

Читать далее 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, насколько я понимаю, используются в учебных курсах, и недобросовестные студенты будут очень рады готовым решениям. Тем не менее, имеет смысл рассмотреть общую структуру решений.

Читать далее Rosalind.info — обзор →