Программа для филогенетического исследования совместной эволюции генов и видов

Программа Embed3GL предназначена для решения четырёх задач филогенетики и основана на оригинальном алгоритме [1–4] полиномиальной (кубической) сложности. Общие для первых трёх задач исходные данные включают в себя:

• корневое дерево видов, изначально двоичное, с добавленными затем дополнительными вершинами, разбивающими дерево на временны́е слои, так что все листья (современные виды) находятся в одном слое. Количество добавляемых дополнительных вершин указывается в форме длины соответствующего ребра дерева видов: если длина 1 или не указана, то вершины не добавляются; длина 2 означает, что на ребре имеется одна дополнительная вершина, и т.д. Дерево должно содержать аутгруппу (с именем «вида» Out). Для разбивки дерева на временны́е слои и добавления аутгруппы (при необходимости) может использоваться отдельная программа (см. ссылку ниже).
• набор корневых деревьев генов (в текущей версии политомические вершины не допускаются).

Подробнее структура исходных данных описана в руководстве к программе.

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

Задача 2 решается на базе результатов и промежуточных данных, полученных в Задаче 1. В результате отдельно для каждого дерева генов строится сценарий его вложения в общее дерево видов. Сценарий имеет вид дерева событий, содержащего как одинарные, так и бирёбра.

Задача 3 решается после бинаризации исходного набора деревьев генов и использует задаваемые пользователем дополнительные данные двоякого рода:

1. I-тип — фиксированное множество типов эволюционных событий (например, потери, возникновения, дупликации, переносы);
2. T-тип — множество вершин деревьев генов, у которых все листья-потомки помечены определённым образом в одном или нескольких деревьях генов (например, «множество предков рибосомных генов»).

Результатом решения Задачи 3 являются представленные в табличной форме две функции: f(I,x) — матожидание числа событий типа I в трубе (ребре) x дерева видов и g(I,T) — матожидание числа событий типа I, происшедших с ребрами типа T.

Начиная с текущей версии, программа Embed3GL также обеспечивает решение Задачи 4 — построения супердерева (видов), согласующего набор исходных двоичных деревьев, в качестве которых используются базисные деревья, полученные программой Basis3GL. Такой метод сборки супердерева, основанный на суммарной цене вложения, точнее приближённого алгоритма, реализованного в программе Super3GL, но значительно медленнее. По этой причине рекомендуется при решении Задачи 4 запускать программу в параллельном режиме на высокопроизводительном кластере.

Программа Embed3GL написана на C/С++ и имеет интерфейс командной строки. Программа допускает распараллеливание в среде MPI версии 1.2 и выше. Текст программы переносим, и после соответствующей перекомпиляции может использоваться в среде ОС Windows 32/64-bit, Linux, Unix, MacOS.

Исполняемые модули программы для Windows (32- и 64-битная версии) и исходный код для Linux (одно- и мультипроцессорный варианты) можно загрузить по ссылкам ниже. Исходный код программы предоставляется бесплатно на условиях лицензии GNU General Public License (GPL) версии 3.

Файлы для загрузки

Литература

1. V.A. Lyubetsky, L.I. Rubanov, L.Yu. Rusin, K.Yu. Gorbunov. Cubic time algorithms of amalgamating gene trees and building evolutionary scenarios. Biology Direct, 2012, Vol. 7, Art. 48. DOI: 10.1186/1745-6150-7-48
2. К.Ю. Горбунов, В.А. Любецкий. Реконструкция эволюции генов вдоль дерева видов. Молекулярная биология, 2009, том 43, № 5, стр. 946–958. Перевод: K.Yu. Gorbunov, V.A. Lyubetsky. Reconstructing the evolution of genes along the species tree. Molecular Biology, 2009, Vol. 43, No. 5, P. 881–893. DOI: 10.1134/S0026893309050197
3. К.Ю. Горбунов, В.А. Любецкий. Об одном алгоритме согласования деревьев генов и видов с учетом дупликаций, потерь и горизонтальных переносов генов. Информационные процессы, 2010, том 10, № 2, стр. 140–144. EDN: OXAFBL
4. К.Ю. Горбунов, В.А. Любецкий. Дерево, ближайшее в среднем к данному набору деревьев. Проблемы передачи информации, 2011, том 47, вып. 3, стр. 64–79. Перевод: K.Yu. Gorbunov, V.A. Lyubetsky. The tree nearest on average to a given set of trees. Problems of Information Transmission, 2011, Vol. 47, No. 3, P. 274–288. DOI: 10.1134/S0032946011030069