Архив за день: Июнь 24, 2015

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

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

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

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

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

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

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