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

Лекция 27. Введение в облачные вычисления

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

Основа для облачных вычислений — технологии, разработанные к началу XXI века:

  • аппаратная виртуализация, сделавшая возможной быстрое масштабирование вычислительных ресурсов;
  • распространение и стандартизация веб-сервисов;
  • наработки в области распределенных вычислений, в частности, grid- и утилитарные вычисления.

Архитектура облачных систем состоит из трех уровней:

  • инфраструктура как сервис (IaaS) — базовый уровень, предоставляющий доступ к вычислительным серверам, системам хранения данных и технологиям вроде балансировки нагрузки;
  • платформа как сервис (PaaS) — промежуточный уровень, на котором находятся API для доступа к данным и проведения вычислений;
  • программное обеспечение как сервис (SaaS) — наиболее высокий уровень, обеспечивающий доступ к пользовательским приложениям (например, редактирование документов в веб-браузере).

Типичный сценарий применения облачной архитектуры — использование PaaS, предоставляемой одним из крупных игроков рынка (например, Google), для создания приложений, которые взаимодействуют с клиентами (SaaS), а также средств анализа и обработки данных (например, с помощью методов машинного обучения).

Презентация: Лекция 27.

Continue reading

Лекция 26. Сервисная архитектура приложений. Веб-сервисы

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

Выделяют два основных типа веб-сервисов в зависимости от используемых технологий:

  • SOAP-сервисы, основанные на стандартах для веб-сервисов, разработанных международным консорциумом W3C. Этот вид сервисов более сложен в разработке и использовании, поэтому применяется в тех случаях, когда важно соблюдение стандартов и высокая степень формализации. Одна из основных областей применения SOAP-сервисов — коммерческие (enterprise) системы.
  • REST-сервисы, использующие для передачи данных методы протокола HTTP (GET, PUT, POST и DELETE). В отличие от SOAP-сервисов, интерфейс REST-сервисов чаще всего определяется неформально; при передаче данных используются стандарты (де)сериализации XML, JSON, YAML и другие. Характерный вариант применения REST-сервисов — доступ к API в веб-приложениях; простота сервисов упрощает их интеграцию (web mashup).

Презентация: Лекция 26.

Continue reading

Лекция 25. Хранение данных

В самых разнообразных приложениях часто возникает задача хранения данных вне оперативной памяти (data persistence), чтобы информация оставалась доступной после завершения работы программы, ее породившей. Также требуется, чтобы из сохраненных данных можно было восстановить объект, эквивалентный сохраненному. Можно выделить по крайней мере два способа решения этой задачи:

  • Сериализация данных в виде потока байтов. В зависимости от выбранного формата, сериализованные данные могут храниться в двоичном или текстовом виде. В первом случае, как правило, оптимизируется объем данных, во втором — уделяется внимание тому, чтобы информация могла восприниматься программистом.
  • Сохранение данных в реляционную базу данных при помощи объектно-реляционного отображения (object-relational mapping, ORM).

У каждого способа хранения данных есть свои преимущества и недостатки. ORM подразумевает определенные затраты на сопровождение базы данных; с другой стороны, структуризация данных в БД позволяет более эффективно их анализировать. Сериализация данных может использоваться не только для хранения данных, но и для их передачи, например, по сети; два формата сериализации (XML и JSON) де-факто являются стандартами передачи данных в веб-приложениях.

Презентация: Лекция 25.

Continue reading