Архив метки: биоинформатика

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

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

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

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

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

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

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

Программный комплекс по биоинформатике. Сериализация выборок

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

Для того чтобы не сохранять каждый раз все данные из выборки, можно определить текстовые идентификаторы для базовых выборок, соответствующих файлам на жестком диске. Соответствие между идентификаторами и файлами определяется окружением с помощью конфигурационного файла. Использование идентификаторов позволяет решить сразу несколько проблем:

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

Логика сериализации выборки не является универсальной: в некоторых случаях (например, если необходимо сохранять результаты работы алгоритма распознавания) имеет смысл все-таки записывать все содержимое выборки. Поэтому в комплексе базовые операции над выборками (выбор строк, объединение, фильтрация и т. п.) реализованы в виде класса SimpleSequenceSet, а функциональность, которая соответствует необычному механизму сериализации, сосредоточена в дочернем классе NamedSequenceSet.

Continue reading

Программный комплекс по биоинформатике. Сохранение прогресса алгоритмов

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

  • Алгоритмы распознавания и некоторые вспомогательные алгоритмы (например, алгоритмы отбора предикатов для иерархических композиций) работают достаточно долго (от 10 минут до нескольких часов). Хотелось бы иметь возможность в любой момент прервать работу алгоритма и вернуться к нему позже. (При прерывании выполнения программы пользователем сохранение состояния алгоритма возможно за счет использования Runtime.addShutdownHook.)
  • Во многих случаях имеет ценность информация, связанная с алгоритмом (например, порядок используемой модели для распознавания). Желательно, чтобы эту информацию не требовалось хранить вручную.

Наиболее очевидный способ хранения структурированных данных в Java, который и был использован — сериализация средствами интерфейса java.io.Serializable. У этого метода есть недостатки (например, при изменении структуры наследования класса или его переименовании десериализация перестает работать), но при разумном процессе разработки количество встреч с ними минимально. Более того, разработка с оглядкой на сериализацию побуждает с самого начала создавать правильную иерархию классов и подбирать для классов подходящие поля.

Continue reading

Распознавание на основе скрытых марковских моделей (часть 2)

На второй части семинара «Образный компьютер» я рассказал о том, о чем не успел в первой части — об алгоритмических композициях, в которых составляющие являются скрытыми марковскими моделями определенного порядка. На мой взгляд, алгоритмические композиции — самая интересная часть моей диссертации.

Презентация доклада: Распознавание на основе скрытых марковских моделей (часть 2).

Continue reading

Скрытые марковские модели в биоинформатике

Биоинформатика — применение методов математической статистики и информатики для анализа и обработки биологических данных: последовательностей нуклеотидов (ДНК) и аминокислот (белки).

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

Скрытые марковские модели стали темой моей кандидатской диссертации (Методы распознавания на основе моделей Маркова со скрытыми переменными).

Continue reading

Распознавание на основе скрытых марковских моделей

9 декабря на семинаре «Образный компьютер», который ведет Михаил Иванович Шлезингер (один из авторов EM-алгоритма), я докладывал о структурном распознавании для биологических последовательностей — ДНК и белков.

Презентация доклада: Распознавание на основе скрытых марковских моделей (успел рассказать до композиций алгоритмов, слайд 23).

Как известные алгоритмы распознавания на основе обобщенных скрытых марковских моделей, так и предложенные мной модели, объединяющие в себе обыкновенные СММ и марковские цепи, максимизируют функцию совместного правдоподобия для последовательности наблюдаемых и скрытых состояний. В связи с этим на семинаре возник вопрос: действительно ли такой критерий качества адекватен для рассматриваемых задач?

Continue reading