Метод «Соседнего присоединения» для построения филогенетических деревьев

Введение

В биоинформатике метод «соединения соседей» является методом кластеризации снизу вверх (агломеративным) для построения филогенетических деревьев, разработанный Наруей Саиту и Масатоси Ней в 1987 году. Как правило, основанный на данных последовательностей ДНК или белков, алгоритм требует знания расстояния между каждой парой таксонов (например, видов или последовательностей) для построения филогенетического дерева.

Сложность

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

Оценка первой длины ветви

Пусть обозначит новый узел. Согласно уравнению выше, ветви, соединяющие и с , имеют следующие длины:

Сосед присоединяется как минимальная эволюция

Присоединение соседей может рассматриваться как жадная эвристика для критерия сбалансированной минимальной эволюции (BME). Для каждой топологии BME определяет длину дерева (сумму длин ветвей) как определенную взвешенную сумму расстояний в матрице расстояний, при этом веса зависят от топологии. Оптимальная топология BME – это та, которая минимизирует длину дерева. Алгоритм присоединения соседей на каждом шаге жадно объединяет ту пару таксонов, которая приводит к наибольшему уменьшению расчетной длины дерева. Эта процедура не гарантирует нахождение оптимального решения для критерия BME, хотя часто это происходит и обычно результат довольно близок к оптимальному. Это делает его практичным для анализа больших наборов данных (сотни или тысячи таксонов) и для бутстрэппинга, для которых другие методы анализа (например, максимальная экономия признаков, максимальное правдоподобие) могут быть вычислительно невозможны. Присоединение соседей обладает свойством, что если входная матрица расстояний корректна, то и выходное дерево будет корректным. Более того, корректность топологии выходного дерева гарантируется, если матрица расстояний является «почти аддитивной», то есть каждая ячейка в матрице расстояний отличается от истинного расстояния не более чем на половину длины самой короткой ветви в дереве. На практике матрица расстояний редко удовлетворяет этому условию, но алгоритм присоединения соседей часто все равно строит правильную топологию дерева. Корректность присоединения соседей для почти аддитивных матриц расстояний подразумевает его статистическую согласованность при многих моделях эволюции; при наличии данных достаточной длины, алгоритм присоединения соседей восстановит истинное дерево с высокой вероятностью. По сравнению с UPGMA и WPGMA, присоединение соседей имеет преимущество в том, что оно не предполагает, что все линии эволюционируют с одинаковой скоростью (гипотеза молекулярных часов). Тем не менее, присоединение соседей в значительной степени уступило место филогенетическим методам, которые не опираются на меры расстояния и обеспечивают более высокую точность в большинстве случаев. Присоединение соседей имеет нежелательную особенность – оно часто присваивает отрицательные длины некоторым ветвям.

Neighbor joining may be viewed as a greedy heuristic for the balanced minimum evolution (BME) criterion. For each topology, BME defines the tree length (sum of branch lengths) to be a particular weighted sum of the distances in the distance matrix, with the weights depending on the topology. The BME optimal topology is the one which minimizes this tree length. NJ at each step greedily joins that pair of taxa which will give the greatest decrease in the estimated tree length. This procedure does not guarantee to find the optimum for the BME criterion, although it often does and is usually quite close. This makes it practical for analyzing large data sets (hundreds or thousands of taxa) and for bootstrapping, for which purposes other means of analysis (e. g. maximum parsimony, maximum likelihood) may be computationally prohibitive. Neighbor joining has the property that if the input distance matrix is correct, then the output tree will be correct. Furthermore, the correctness of the output tree topology is guaranteed as long as the distance matrix is 'nearly additive', specifically if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree. In practice the distance matrix rarely satisfies this condition, but neighbor joining often constructs the correct tree topology anyway. The correctness of neighbor joining for nearly additive distance matrices implies that it is statistically consistent under many models of evolution; given data of sufficient length, neighbor joining will reconstruct the true tree with high probability. Compared with UPGMA and WPGMA, neighbor joining has the advantage that it does not assume all lineages evolve at the same rate (molecular clock hypothesis). Nevertheless, neighbor joining has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions. Neighbor joining has the undesirable feature that it often assigns negative lengths to some of the branches.