Архив рубрики: Прикладное программирование

SVGTreeViewer — плагин для SVGTree

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

  • создание и удаление вершин дерева при помощи более удобных средств, чем кнопки Insert и Delete (в мобильных устройствах этих кнопок попросту нет);
  • настройка внешнего вида дерева (например, формы вершин и ребер);
  • просмотр «исходного кода» дерева в Newick-формате и, возможно, его непосредственное редактирование (по аналогии с тем, как HTML-редакторы вроде TinyMCE предоставляют возможность редактировать исходный код HTML);
  • откат / повторение произведенных изменений (undo / redo).

Поскольку в неинтерактивных случаях использования базовой функциональности библиотеки SVGTree вполне достаточно, новую функциональность логично выделить в отдельный компонент — SVGTreeViewer, зависящий от базовой библиотеки. Компонент представляет собой JavaScript-файл и таблицу стилей, которые в сжатом виде занимают около 15 килобайт.

Базовые примеры использования компонента приведены на этой веб-странице, еще пара есть под катом.

Continue reading

SVGTree — HTML5-библиотека для рисования деревьев

При описании алгоритмов на деревьях у меня возникла небольшая проблема визуализации деревьев, записанных в Newick-формате. Для рисования деревьев можно использовать различные десктопные инструменты (например, в LaTeX для этой цели подходит замечательный пакет TikZ). Возникает вопрос, можно ли для рисования использовать веб-технологии; результатом моих недельных усилий в этом направлении стала небольшая JavaScript-библиотека SVGTree.

Как видно из названия, для рисования в SVGTree используется один из аспектов HTML5 — масштабируемая векторная графика (scalable vector graphics, SVG). SVG — язык разметки на основе XML, предназначенный для отображения векторной графики; SVG-изображения можно встраивать в обычные HTML-страницы и динамически изменять при помощи JavaScript. На нынешнее время SVG поддерживается в достаточной степени всеми основными веб-браузерами: Firefox, Chrome и даже Internet Explorer 11+. По сравнению с альтернативными методами, которые можно применить для отображения деревьев, у SVG есть несколько преимуществ:

  • Поскольку SVG — стандарт векторной графики, изображения легко масштабируются; SVG, в отличие от скалярной графики, отображаемой элементом HTML5 <canvas>, походит для огромных рисунков (порядка 10000×10000).
  • Внешний вид SVG можно менять при помощи таблиц стилей CSS, совершенно аналогичных таблицам для обычных HTML-страниц. Это позволяет разделить логику создания базовых элементов рисунка и их отображения.
  • К элементам SVG можно обратиться при помощи JavaScript DOM API почти так же, как к элементам HTML-страницы. При этом элементы SVG поддерживают базовые события (например, click), что упрощает реализацию интерактивности.

Библиотека доступна в виде Github-репозитория.

Несколько примеров использования библиотеки есть на этой странице, еще несколько приведено под катом.

Continue reading

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

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

Continue reading

Фракталы — использование WebGL

Общее описание сайта и математическая теория здесь; рисование при помощи фоновых потоков выполнения обрисовано здесь.

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

Использование GPU для рисования фракталов упрощается за счет двух факторов:

  • Цвет пикселей изображения, которое необходимо получить, определяется исключительно расположением пикселя. Это значит, что процесс рисования можно эффективно распараллелить без использования особых ухищрений. Поскольку в современных графических платах количество пиксельных конвейеров (то есть модулей для определения цвета пикселей) составляет порядка сотни, фрактал будет генерироваться значительно быстрее, чем при использовании CPU.
  • Для вычисления цвета не используются экстраординарные математические понятия; весь процесс сводится к преобразованию пар действительных чисел при помощи базовых функций (exp, log, геометрические и обратные геометрические).

Continue reading

Фракталы — использование Web Workers API

Общее описание сайта и математическая теория здесь.

После того, как определен способ вычисления функции f (за счет синтаксического разбора), остается вычислить «скорость убегания» P(z, f) для комплексных чисел z, соответствующих отдельным пикселям изображения. Наиболее простой способ вычислений — цикл по всем пикселям. Фатальный недостаток этого метода состоит в том, что подсчеты занимают существенное время (порядка нескольких секунд или десятков секунд), и во время выполнения цикла браузер перестает отвечать на внешние раздражители, что, разумеется, неприемлемо. К счастью, для этой проблемы есть решение — современные браузеры (Firefox, Chrome, IE 10+) поддерживают выполнение JavaScript-кода в фоновых потоках выполнения.

Continue reading

Фракталы — синтаксический разбор арифметических выражений

Общее описание сайта и математическая теория создания фрактальных изображений здесь.

Одна из основных задач, которые пришлось решить в ходе создания сайта «Fun with Fractals», заключается в следующем:

Задача. На основе понятного для человека описания функции комплексного переменного составить ее представление, позволяющее вычислять ее значения при помощи JavaScript или WebGL.

Continue reading

Фракталы — общее описание

Сайт Fun with Fractals — небольшой проект, наглядно демонстрирующий возможности HTML5 на примере фракталов:

  • элемент HTML5 <canvas> для рисования (<canvas>, HTMLCanvasElement);
  • фоновые потоки выполнения JavaScript для ускорения процесса рисования и избавления от «подвисания» браузера;
  • WebGL для рисования с помощью графического ускорителя вместо JavaScript (значительно быстрее).

В результате получаются достаточно красивые картинки:

Фрактал №1
ссылка на сайт
Фрактал №2
ссылка на сайт
Фрактал №3
ссылка на сайт

Continue reading