Построение тонкослойной филогенетической сети

Постановка задачи

Филогенетическое дерево – это бинарное корневое неупорядоченное дерево с уникальными метками листьев. Филогенетическая сеть представляет собой обобщение филогенетического дерева, формально определямое как корневой связный ориентированный ациклический граф, в котором: (1) полустепень выхода каждой вершины не превышает 2; (2) полустепень захода каждой вершины равна 1 или 2, кроме корневой вершины, у которой она равна 0; (3) ни одна вершина не имеет полустепени захода и выхода, одновременно равные 1; (4) все вершины с полустепенью выхода 0 помечены элементами конечного множества L таким образом, что никаким двум вершинам не присваивается одинаковая метка. Вершины с полустепенью выхода 0 называются листьями и идентифицируются по соответствующим им элементам L. Для любой филогенетической сети N обозначим за U(N) неориентированный граф, полученный из N в результате замены каждого ориентированного ребра неориентированным. N называется тонкослойной филогенетической сетью (или просто тонкослойной сетью), если все циклы в U(N) являются вершинно-непересекающимися. Тонкослойные сети в разных источниках также называются топологиями с независимыми событиями рекомбинации [17], галловыми деревьями [3], gt-сетями [13] и филогенетическими сетями первого уровня [2, 7].

Филогенетическое дерево, имеющее ровно три листа, называется корневым триплетом. Уникальный корневой триплет на множестве листьев {x, y, z}, в котором самый низкий общий предок листьев x и у является непосредственным потомком самого низкого общего предка листьев x и z (или, что эквивалентно, непосредственным потомком самого низкого общего предка листьев y и z), обозначим за ({x, y}, z). Для любой филогенетической сети N корневой триплет t называется согласующимся с N, если он является порожденным подграфом N; множество корневых триплетов T называется согласующимся с N, если каждый триплет из T является согласущимся с N.

Обозначим множество листьев в любой филогенетической сети N за A(N) и определим для любого множества корневых триплетов T A(T) = ljt.ea-/l(f,). Множество корневых триплетов T является плотным, если для каждого триплета {x, y, z} С А(Т) по меньшей мере один из возможных корневых триплетов ({x, y}, z), ({x, z}, y) и ({y, z}, x) входит в T. Если T является плотным, то |T| = в(\А(Т)\ъ). Далее, для любого множества корневых триплетов T и L0 С /1(Т^) определим T j L0 как подмножество T, состоящее из всех корневых триплетов t с yl(f) С L0. Рассматриваемая задача [8] выглядит следующим образом.

Задача 1. Пусть дано множество корневых триплетов T. Необходимо построить тонкослойную сеть N с A(N) = A(T), такую, что N и T являются согласующимися, если такая сеть существует; в противном случае вывести нулевой результат. (См. пример на рис. 1).

Родственная задача о запрещенных триплетах [4] определяется следующим образом.

Задача 2. Пусть даны два множества корневых триплетов T и F. Если существует тонкослойная сеть N с A(N) = A(T), такая, что (1) N и T являются согласующимися; (2) каждый корневой триплет в F не согласуется с N, вывести ее; в противном случае вывести нулевой результат.

Далее положим L = A(T) и n = |L|.

Плотное множество корневых триплетов T с множеством листьев {a, b, c, d} и тонкослойная филогенетическая сеть, согласующаяся с T. Отметим, что это решение не является единственным

Основные результаты

Теорема 1. Пусть дано плотное множество корневых триплетов T с множеством листьев L. Тонкослойную сеть, согласующуюся с T, можно построить за время O(n3), где n = |L|.

Теорема 2. Пусть дано неплотное множество корневых триплетов T. Задача определения того, существует ли согласующаяся с T тонкослойная сеть, является NP-полной. Такую же сложность имеет задача определения того, существует ли простая филогенетическая сеть, согласующаяся с T.

Далее рассматривается задача построения тонкослойной сети N, согласующейся с максимальным количеством корневых триплетов из T для любого (не обязательно плотного) множества T. Поскольку из теоремы 2 следует, что эта задача является NP-полной, были исследованы алгоритмы аппроксимации для ее приближенного решения. Алгоритм называется k-аппроксимируемым, если он всегда возвращает тонкослойную сеть N, такую, что N(T)/|T| > k, где N(T) – количество корневых триплетов в T, согласующихся с N.

Теорема 3. Пусть дано множество корневых триплетов T. Не существует алгоритма аппроксимации, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 0.4883.

Теорема 4. Пусть дано множество корневых триплетов T. Существует алгоритм аппроксимации, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 5/12. Время работы алгоритма составляет О(\А(Т)\\Т\Ъ).

Следующая теорема касается задачи о запрещенных триплетах.

Теорема 5. Пусть даны два множества корневых триплетов T. Существует алгоритм с временем выполнения O(|L| 2 |T| (|T| + |F|)), результатом работы которого является тонкослойная сеть N, такая, что > 5/12(|7l F j.

Применение

Филогенетические сети используются учеными для описания эволюционных взаимоотношений, не вписывающихся в традиционные модели, представляющие эволюцию в виде дерева (см., например, [12, 16]). Такие эволюционные события, как горизонтальный перенос генов и гибридогенное видообразование (часто называемые событиями рекомбинации), предполагающие конвергенцию между объектами, не могут быть представлены в виде одного дерева [3, 5, 13, 15, 17], но могут моделироваться филогенетической сетью, в которой внутренние вершины могут иметь более одного предка. Тонкослойные сети представляют собой важную разновидность филогенетических сетей, получившую широкое освещение в литературе [2, 3, 13, 17] в силу их значимости для биологических наук ([3]) и простой, почти древесной структуры. Если количество событий рекомбинации ограничено и большая их часть имела место недавно, тонкослойная сеть может быть способна точно описать исследуемый эволюционный процесс [3].

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

Подход на основе корневых триплетов получил широкое распространение в силу того, что для любого подмножества мощности 3 множества листьев можно построить дерево высокой точности на основе методов максимального правдоподобия (см., например, [1]) или экспериментов с гибридизацией ДНК-ДНК в духе Сибли-Алквиста ([10]). Алгоритмы, представленные в работе [7], могут использоваться на этапе слияния при реализации подхода «разделяй и властвуй» в процессе построения филогенетических сетей аналогично методу квартета для вывода некорневых филогенетических деревьев [9, 11] и другим методам построения супердеревьев (см. [6, 14] и ссылки в этих работах). В частности, рассматриваются плотные входные множества, поскольку в этом случае задачи могут быть решены за полиномиальное время.

Открытые вопросы

Текущий коэффициент аппроксимации для задачи на основе корневых триплетов является нестрогим (0,4883 > N(T)/|T| > 5/12). Пока неизвестно, можно ли найти строгий коэффициент аппроксимации для этой задачи. Также не найден строгий коэффициент аппроксимации для задачи о запрещенных триплетах.

Еще одно направление исследований – разработка алгоритма с фиксированными параметрами с полиномиальным временем выполнения. Предположим, что количество гибридных вершин ограничено значением h. Может ли существовать алгоритм, полиномиальный относительно |T| и экспоненциальный относительно h?

См. также

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

Литература

1. Chor, B., Hendy, M., Penny, D.: Analytic solutions for three-taxon MLMC trees with variable rates across sites. In: Proc. 1st Workshop on Algorithms in Bioinformatics (WABI 2001). LNCS, vol. 2149, pp. 204-213. Springer, Berlin (2001)

2. Choy, C., Jansson, J., Sadakane, K., Sung, W.-K.: Computing the maximum agreement of phylogenetic networks. In: Proc. Computing: the 10th Australasian Theory Symposium (CATS 2004), 2004, pp. 33-45

3. Gusfield, D., Eddhu, S., Langley, C.: Efficient reconstruction of phylogenetic networks with constrained recombination. In: Proc. of Computational Systems Bioinformatics (CSB2003), 2003 pp. 363-374

4. He, Y.-J., Huynh, T.N.D., Jannson, J., Sung, W.-K.: Inferring phylogenetic relationships avoiding forbidden rooted triplets. J Bioinform. Comput. Biol. 4(1), 59-74 (2006)

5. Hein, J.: Reconstructing evolution of sequences subject to recombination using parsimony. Math. Biosci. 98(2), 185-200 (1990)

6. Henzinger, M.R., King, V., Warnow, T.: Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica 24(1), 1-13 (1999)

7. Jansson, J., Sung, W.-K.: Inferring a level-1 phylogenetic network from a dense set of rooted triplets. In: Proc. 10th International Computing and Combinatorics Conference (CO COON 2004), 2004

8. Jansson, J., Nguyen, N.B., Sung, W.-K.: Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J. Comput.35(5), 1098-1121 (2006)

9. Jiang, T., Kearney, P., Li, M.: A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput. 30(6), 1942-1961 (2001)

10. Kannan, S., Lawler, E., Warnow, T.: Determining the evolution ary tree using experiments. J. Algorithms 21(1), 26-50 (1996)

11. Kearney, P.: Phylogenetics and the quartet method. In: Jiang, T., Xu, Y., and Zhang, M.Q. (eds.) Current Topics in Computational Molecular Biology, pp. 111-133. MIT Press, Cambridge (2002)