Архив метки: функциональное программирование

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

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

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

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

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

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

Continue reading

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

Continue reading

Rosalind.info — кэширование

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

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

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

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

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

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

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

Continue reading