Лаборатория математических методов и моделей в биоинформатике
Института проблем передачи информации им. А.А. Харкевича
Российской академии наук

• Научная деятельность
• Направления исследований
• Публикации
• Презентации
• Программы
• Сотрудники
• Контакты

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

Программа 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. Lyubetsky V.A., Rubanov L.I., Rusin L.Yu., Gorbunov K.Yu. "Cubic time algorithms of amalgamating gene trees and building evolutionary scenarios", Biology Direct, 2012, 7:48

2. К.Ю. Горбунов, В.А. Любецкий «Реконструкция эволюции генов вдоль дерева видов», Молекулярная биология, 2009, том 43, № 5, стр. 946–958

3. К.Ю. Горбунов, В.А. Любецкий «Об одном алгоритме согласования деревьев генов и видов с учетом дупликаций, потерь и горизонтальных переносов генов», Информационные процессы, 2010, том 10, № 2, стр. 140–144

4. К.Ю. Горбунов, В.А. Любецкий «Дерево, ближайшее в среднем к данному набору деревьев», Проблемы передачи информации, 2011, том 47, вып. 3, стр. 64–79