Объединение соседей

Метод восходящей кластеризации для создания филогенетических деревьев

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

• 1 Алгоритм
  • 1.1 Q-матрица
  • 1.2 Расстояние от членов пары до нового узла
  • 1.3 Расстояние от других таксонов до новый узел
  • 1.4 Сложность
• 2 Пример
  • 2.1 Первый шаг
    • 2.1.1 Первое соединение
    • 2.1.2 Оценка длины первой ветви
    • 2.1.3 Первое обновление матрицы расстояний
  • 2.2 Второй этап
    • 2.2.1 Второе соединение
    • 2.2.2 Оценка длины второй ветви
    • 2.2.3 Второе расстояние Обновление матрицы ce
  • 2.3 Заключительный шаг
  • 2.4 Заключение: аддитивные расстояния
• 3 Объединение соседей как минимальная эволюция
• 4 Преимущества и недостатки
• 5 Реализации и варианты
• 6 См. также
• 7 Ссылки
  • 7.1 Другие источники
• 8 Внешние ссылки

Начиная с звездообразного дерева (A), матрица Q вычисляется и используется для выбора пары узлов для объединения, в данном случае f и г. Они присоединяются к вновь созданному узлу u, как показано на (B). Часть дерева, показанная сплошными линиями, теперь зафиксирована и не будет изменена на последующих этапах соединения. Расстояния от узла u до узлов a-e вычисляются из уравнения (3). Затем этот процесс повторяется, используя матрицу только расстояний между узлами a, b, c, d, e и u и полученную из нее Q-матрицу. В этом случае u и e присоединяются к вновь созданному v, как показано на (C). Еще две итерации ведут сначала к (D), а затем к (E), после чего алгоритм завершается, поскольку дерево полностью разрешено.

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

1. На основе текущая матрица расстояний вычислить матрицу $Q\; \{\backslash \; displaystyle\; Q\}$(определено ниже).
2. Найти пару различных таксонов i и j (т.е. с $i\; \ne \; j\; \{\backslash \; displaystyle\; i\; \backslash \; neq\; j\}$), для которого $Q\; (i,\; j)\; \{\backslash \; displaystyle\; Q\; (i,\; j)\}$имеет наименьшее значение. Эти таксоны присоединяются к вновь созданному узлу, который соединен с центральным узлом. На рисунке справа f и g присоединены к новому узлу u.
3. Вычислите расстояние от каждого из таксонов в паре до этого нового узла.
4. Рассчитайте расстояние от каждого таксона за пределами этой пары до нового узла.
5. Запустите алгоритм снова, заменив пару объединенных соседей новым узлом и используя расстояния, вычисленные на предыдущем шаге.

Q-матрица

На основе матрицы расстояний, относящейся к $n\; \{\backslash \; displaystyle\; n\}$таксонам, вычислите $Q\; \{\backslash \; displaystyle\; Q\}$следующим образом:

$Q\; (i,\; j)\; =\; (n\; -\; 2)\; d\; (i,\; j)\; -\; \sum \; k\; =\; 1\; nd\; (i,\; k)\; -\; \sum \; k\; =\; 1\; nd\; (j,\; k)\; \{\backslash \; Displaystyle\; Q\; (я,\; J)\; =\; (N-2)\; d\; (я,\; J)\; -\; \backslash \; сумма\; \_\; \{к\; =\; 1\}\; ^\; \{п\}\; d\; (я,\; к)\; -\; \backslash \; сумма\; \_\; \{к\; =\; 1\}\; ^\; \{п\; \}\; d\; (j,\; k)\}$

(1)

где $d\; (i,\; j)\; \{\backslash \; displaystyle\; d\; (i,\; j)\}$- расстояние между таксонами $i\; \{\backslash \; displaystyle\; i\}$и $j\; \{\backslash \; displaystyle\; j\}$.

Расстояние от членов пары до нового узла

Для каждого таксона в паре присоединился, используйте t Следующая формула для вычисления расстояния до нового узла:

$\delta \; (f,\; u)\; =\; 1\; 2\; d\; (f,\; g)\; +\; 1\; 2\; (n\; -\; 2)\; [\sum \; k\; =\; 1\; nd\; (f,\; k)\; -\; \sum \; К\; знак\; равно\; 1\; nd\; (g,\; k)]\; \{\backslash \; displaystyle\; \backslash \; delta\; (f,\; u)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; d\; (f,\; g)\; +\; \{\backslash \; frac\; \{1\}\; \{2\; (n-\; 2)\}\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; d\; (f,\; k)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; d\; (g,\; k)\; \backslash \; right]\; \backslash \; quad\}$

(2)

и:

$\delta \; (g,\; u)\; =\; d\; (f,\; g)\; -\; \delta \; (f,\; u)\; \{\backslash \; displaystyle\; \backslash \; delta\; (g,\; u)\; =\; d\; (f,\; g)\; -\; \backslash \; delta\; (f,\; u)\; \backslash \; quad\}$

Таксоны $f\; \{\backslash \; displaystyle\; f\}$и $g\; \{\backslash \; displaystyle\; g\}$являются парными таксоны, а $u\; \{\backslash \; displaystyle\; u\}$- вновь созданный узел. Ветви, соединяющие $f\; \{\backslash \; displaystyle\; f\}$и $u\; \{\backslash \; displaystyle\; u\}$и $g\; \{\backslash \; displaystyle\; g\}$и $u\; \{\backslash \; displaystyle\; u\}$, и их длины, $\delta \; (f,\; u)\; \{\backslash \; displaystyle\; \backslash \; delta\; (f,\; u)\}$и $\delta \; (g,\; u)\; \{\backslash \; displaystyle\; \backslash \; delta\; (g,\; u)\}$являются частью дерева, которое постепенно создается; они не влияют и не влияют на последующие шаги присоединения соседей.

Расстояние других таксонов от нового узла

Для каждого таксона, не рассмотренного на предыдущем шаге, мы вычисляем расстояние до нового узла следующим образом:

$d\; (u,\; k)\; =\; 1\; 2\; [d\; (f,\; k)\; +\; d\; (g,\; k)\; -\; d\; (f,\; g)]\; \{\backslash \; displaystyle\; d\; (u,\; k)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; [d\; (f,\; k)\; +\; d\; (g,\; k)\; -d\; (f,\; g)]\}$

(3)

где $u\; \{\backslash \; displaystyle\; u\}$- новый узел, $k\; \{\backslash \; displaystyle\; k\}$- узел, расстояние до которого мы хотим вычислить, и $f\; \{\backslash \; displaystyle\; f\}$и $g\; \{\backslash \; displaystyle\; g\; \}$- это только что присоединившиеся члены пары.

Сложность

Соединение соседей в наборе из $n\; \{\backslash \; displaystyle\; n\}$таксонов требует $n\; -\; 3\; \{\backslash \; displaystyle\; n-3\}$итераций. На каждом шаге нужно построить и найти матрицу $Q\; \{\backslash \; displaystyle\; Q\}$. Первоначально матрица $Q\; \{\backslash \; displaystyle\; Q\}$имеет размер $n\; \times \; n\; \{\backslash \; displaystyle\; n\; \backslash \; times\; n\}$, затем следующий шаг - $(n\; -\; 1)\; \times \; (n\; -\; 1)\; \{\backslash \; displaystyle\; (n-1)\; \backslash \; times\; (n-1)\}$и т. д. Прямая реализация этого приводит к алгоритму с временной сложностью из $О\; (n\; 3)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{3\})\}$; Существуют реализации, которые используют эвристику для достижения более высоких результатов в среднем.

Соединение соседей с 5 таксонами. В этом случае 2 шага соединения соседей дают дерево с полностью разрешенной топологией. Ветви получившегося дерева помечены своей длиной.

Предположим, что у нас есть пять таксонов $(a,\; b,\; c,\; d,\; e)\; \{\backslash \; displaystyle\; (a,\; b,\; c,\; d,\; e)\}$и следующая матрица расстояний $D\; \{\backslash \; displaystyle\; D\}$:

	a	b	c	d	e
a	0	5	9	9	8
b	5	0	10	10	9
c	9	10	0	8	7
d	9	10	8	0	3
e	8	9	7	3	0

Первый шаг

Первое объединение

Мы вычисляем значения $Q\; 1\; \{\backslash \; displaystyle\; Q\_\; \{1\}\}$по уравнению (1). Например:

$Q\; 1\; (a,\; b)\; =\; (n\; -\; 2)\; d\; (a,\; b)\; -\; \sum \; k\; =\; 1\; 5\; d\; (a,\; k)\; -\; \sum \; k\; =\; 1\; 5\; d\; (b,\; k)\; \{\; \backslash \; Displaystyle\; Q\_\; \{1\}\; (a,\; b)\; =\; (n-2)\; d\; (a,\; b)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{5\}\; d\; (a,\; k)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\; \}\; ^\; \{5\}\; d\; (b,\; k)\}$

$=\; (5\; -\; 2)\; \times \; 5\; -\; (5\; +\; 9\; +\; 9\; +\; 8)\; -\; (5\; +\; 10\; +\; 10\; +\; 9)\; =\; 15\; -\; 31\; -\; 34\; =\; -\; 50\; \{\backslash \; displaystyle\; =\; (5-2)\; \backslash \; times\; 5-\; (5\; +\; 9\; +\; 9\; +\; 8)\; -\; (5\; +\; 10\; +\; 10\; +\; 9)\; =\; 15-31-34\; =\; -50\}$

Получаем следующие значения для матрицы $Q\; 1\; \{\backslash \; displaystyle\; Q\_\; \{1\}\}$(диагональные элементы матрицы не используются и здесь опускаются):

	a	b	c	d	e
a		−50	−38	−34	−34
b	−50		−38	−34	−34
c	−38	-38		-40	-40
d	-34	-34	-40		-48
e	−34	−34	−40	−48

В приведенном выше примере $Q\; 1\; (a,\; b)\; =\; -\; 50\; \{\backslash \; displaystyle\; Q\_\; \{1\}\; (a,\; b)\; =\; -\; 50\}$. Это наименьшее значение из $Q\; 1\; \{\backslash \; displaystyle\; Q\_\; \{1\}\}$, поэтому мы объединяем элементы $a\; \{\backslash \; displaystyle\; a\}$и $b\; \{\backslash \; displaystyle\; b\}$.

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

Пусть $u\; \{\backslash \; displaystyle\; u\}$обозначает новый узел. По уравнению (2), приведенному выше, ветви, соединяющие $a\; \{\backslash \; displaystyle\; a\}$и $b\; \{\backslash \; displaystyle\; b\}$с $u\; \{\; \backslash \; displaystyle\; u\}$тогда имеет длины:

$\delta \; (a,\; u)\; =\; 1\; 2\; d\; (a,\; b)\; +\; 1\; 2\; (5–2)\; [\sum \; k\; =\; 1\; 5\; d\; (a,\; к)\; -\; \sum \; К\; знак\; равно\; 1\; 5\; d\; (b,\; k)]\; =\; 5\; 2\; +\; 31\; -\; 34\; 6\; =\; 2\; \{\backslash \; displaystyle\; \backslash \; delta\; (a,\; u)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; d\; (a,\; б)\; +\; \{\backslash \; frac\; \{1\}\; \{2\; (5-2)\}\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{5\}\; d\; (a,\; k)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{\; 5\}\; d\; (b,\; k)\; \backslash \; right]\; \backslash \; quad\; =\; \{\backslash \; frac\; \{5\}\; \{2\}\}\; +\; \{\backslash \; frac\; \{31-34\}\; \{6\}\}\; =\; 2\}$

$\delta \; (b,\; u)\; =\; d\; (a,\; b)\; -\; \delta \; (a,\; u)\; знак\; равно\; 5-2\; =\; 3\; \{\backslash \; displaystyle\; \backslash \; delta\; (b,\; u)\; =\; d\; (a,\; b)\; -\; \backslash \; delta\; (a,\; u)\; \backslash \; quad\; =\; 5-2\; =\; 3\}$

Первое обновление матрицы расстояний

Затем мы переходим к обновлению исходной матрицы расстояний $D\; \{\backslash \; displaystyle\; D\}$в новую матрицу расстояний $D\; 1\; \{\backslash \; displaystyle\; D\_\; \{1\}\}$(см. ниже), уменьшен в размере на одну строку и один столбец из-за объединения $a\; \{\backslash \; displaystyle\; a\}$с $b\; \{\backslash \; displaystyle\; b\}$в своего соседа $u\; \{\backslash \; displaystyle\; u\}$. Используя приведенное выше уравнение (3), мы вычисляем расстояние от $u\; \{\backslash \; displaystyle\; u\}$до каждого из других узлов, кроме $a\; \{\backslash \; displaystyle\; a\}$<222.>и $b\; \{\backslash \; displaystyle\; b\}$. В этом случае получаем:

$d\; (u,\; c)\; =\; 1\; 2\; [d\; (a,\; c)\; +\; d\; (b,\; c)\; -\; d\; (a,\; b)]\; =\; 9\; +\; 10\; -\; 5\; 2\; =\; 7\; \{\backslash \; displaystyle\; d\; (u,\; c)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; [d\; (a,\; c)\; +\; d\; (b,\; c)\; -d\; (a,\; b)]\; =\; \{\backslash \; frac\; \{9\; +\; 10\; -5\}\; \{2\}\}\; =\; 7\}$

$d\; (u,\; d)\; =\; 1\; 2\; [d\; (a,\; d)\; +\; d\; (b,\; d)\; -\; d\; (a,\; b)]\; =\; 9\; +\; 10\; -\; 5\; 2\; =\; 7\; \{\backslash \; Displaystyle\; d\; (u,\; d)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; [d\; (a,\; d)\; +\; d\; (b,\; d)\; -d\; (a,\; b)]\; =\; \{\backslash \; frac\; \{\; 9\; +\; 10-5\}\; \{2\}\}\; =\; 7\}$

$d\; (u,\; e)\; =\; 1\; 2\; [d\; (a,\; e)\; +\; d\; (b,\; e)\; -\; d\; (a,\; b)]\; =\; 8\; +\; 9–5\; 2\; =\; 6\; \{\backslash \; Displaystyle\; d\; (u,\; e)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; [d\; (a,\; e)\; +\; d\; (b,\; e)\; -d\; (a,\; b)]\; =\; \{\; \backslash \; frac\; \{8\; +\; 9-5\}\; \{2\}\}\; =\; 6\}$

Результирующая матрица расстояний $D\; 1\; \{\backslash \; displaystyle\; D\_\; \{1\}\}$:

	u	c	d	e
u	0	7	7	6
c	7	0	8	7
d	7	8	0	3
e	6	7	3	0

Значения жирным шрифтом в $D\; 1\; \{\backslash \; displaystyle\; D\_\; \{1\}\}$соответствуют вновь вычисленным расстояниям, тогда как значения, выделенные курсивом, не зависят от обновления матрицы, поскольку они соответствуют расстояниям между элементами, не участвующими в первом соединении таксоны.

Второй шаг

Второе объединение

Соответствующая матрица $Q\; 2\; \{\backslash \; displaystyle\; Q\_\; \{2\}\}$:

	u	c	d	e
u		- 28	-24	-24
c	-28		-24	-24
d	-24	-24		−28
e	−24	−24	−28

Мы можем выбрать либо присоединение к $u\; \{\backslash \; displaystyle\; u\}$и $с\; \{\backslash \; displaystyle\; c\}$, или для объединения $d\; \{\backslash \; displaystyle\; d\}$и $e\; \{\backslash \; displaystyle\; e\}$; обе пары имеют минимальное значение $Q\; 2\; \{\backslash \; displaystyle\; Q\_\; \{2\}\}$от $-\; 28\; \{\backslash \; displaystyle\; -28\}$, и любой выбор приводит к тот же результат. Для конкретности соединим $u\; \{\backslash \; displaystyle\; u\}$и $c\; \{\backslash \; displaystyle\; c\}$и назовем новый узел $v\; \{\backslash \; displaystyle\; v\; \}$.

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

Длины ветвей, соединяющих $u\; \{\backslash \; displaystyle\; u\}$и $c\; \{\backslash \; displaystyle\; c\}$до $v\; \{\backslash \; displaystyle\; v\}$можно вычислить:

$\delta \; (u,\; v)\; =\; 1\; 2\; d\; (u,\; c)\; +\; 1\; 2\; (4–2)\; [\sum \; k\; Знак\; равно\; 1\; 4\; d\; (u,\; К)\; -\; \sum \; К\; знак\; равно\; 1\; 4\; d\; (c,\; k)]\; =\; 7\; 2\; +\; 20\; -\; 22\; 4\; =\; 3\; \{\backslash \; displaystyle\; \backslash \; delta\; (u,\; v)\; =\; \{\backslash \; frac\; \{1\}\; \{\; 2\}\}\; d\; (u,\; c)\; +\; \{\backslash \; frac\; \{1\}\; \{2\; (4-2)\}\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{4\}\; d\; (u,\; k)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{4\}\; d\; (c,\; k)\; \backslash \; right]\; \backslash \; quad\; =\; \{\backslash \; frac\; \{7\}\; \{2\}\}\; +\; \{\backslash \; frac\; \{20-22\}\; \{4\}\}\; =\; 3\}$

$\delta \; (c,\; v)\; знак\; равно\; d\; (u,\; c)\; -\; \delta \; (u,\; v)\; =\; 7-3\; =\; 4\; \{\backslash \; displaystyle\; \backslash \; delta\; (c,\; v)\; =\; d\; (u,\; c)\; -\; \backslash \; delta\; (u,\; v)\; \backslash \; quad\; =\; 7-3\; =\; 4\}$

Объединение элементов и вычисление длины ответвления помогает нарисовать дерево соединения соседей, как показано на рисунке.

Второе обновление матрицы расстояний

Обновленная матрица расстояний $D\; 2\; \{\backslash \; displaystyle\; D\_\; \{2\}\; \}$для остальных трех узлов: $v\; \{\backslash \; displaystyle\; v\}$, $d\; \{\backslash \; displaystyle\; d\}$и $e\; \{\backslash \; displaystyle\; e\}$, теперь вычисляется:

$d\; (v,\; d)\; =\; 1\; 2\; [d\; (u,\; d)\; +\; d\; (c,\; d)\; -\; d\; (u,\; c)]\; =\; 7\; +\; 8\; -\; 7\; 2\; Знак\; равно\; 4\; \{\backslash \; displaystyle\; d\; (v,\; d)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; [d\; (u,\; d)\; +\; d\; (c,\; d)\; -d\; (u,\; c)]\; =\; \{\backslash \; frac\; \{7\; +\; 8-7\}\; \{2\}\}\; =\; 4\}$

$d\; (v,\; e)\; =\; 1\; 2\; [d\; (u,\; e)\; +\; d\; (c,\; e)\; -\; d\; (u,\; c)]\; =\; 6\; +\; 7\; -\; 7\; 2\; =\; 3\; \{\backslash \; Displaystyle\; d\; (v,\; e)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; [d\; (u,\; e)\; +\; d\; (c,\; e)\; -d\; (u,\; c)]\; =\; \{\backslash \; frac\; \{6\; +\; 7-7\}\; \{2\}\}\; =\; 3\}$

	v	d	e
v	0	4	3
d	4	0	3
e	3	3	0

Заключительный шаг

На этом этапе топология дерева полностью определена. Однако для ясности мы можем вычислить матрицу $Q\; 3\; \{\backslash \; displaystyle\; Q\_\; \{3\}\}$. Например:

$Q\; 3\; (v,\; e)\; =\; (3\; -\; 2)\; d\; (v,\; e)\; -\; \sum \; k\; =\; 1\; 3\; d\; (v,\; k)\; -\; \sum \; k\; =\; 1\; 3\; d\; (e,\; k)\; =\; 3\; -\; 7\; -\; 6\; =\; -\; 10\; \{\backslash \; Displaystyle\; Q\_\; \{3\}\; (v,\; e)\; =\; (3-2)\; d\; (v,\; e)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{3\}\; d\; (v,\; k)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{3\}\; d\; (e,\; k)\; =\; 3-7-6\; =\; -10\}$

	v	d	e
v		−10	−10
d	−10		−10
e	−10	−10

Для конкретности соединим $v\; \{\backslash \; displaystyle\; v\}$и $d\; \{\backslash \; displaystyle\; d\}$и вызовите последний узел $w\; \{\backslash \; displaystyle\; w\}$. Длины трех оставшихся ветвей можно вычислить:

$\delta \; (v,\; w)\; =\; 1\; 2\; d\; (v,\; d)\; +\; 1\; 2\; (3\; -\; 2)\; [\sum \; k\; =\; 1\; 3\; d\; (v,\; k)\; -\; \sum \; К\; знак\; равно\; 1\; 3\; d\; (d,\; k)]\; =\; 4\; 2\; +\; 7\; -\; 7\; 2\; =\; 2\; \{\backslash \; displaystyle\; \backslash \; delta\; (v,\; w)\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; d\; (v,\; d)\; +\; \{\backslash \; frac\; \{1\}\; \{2\; (3-2)\}\}\; \backslash \; left\; [\backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{3\}\; d\; (v,\; k)\; -\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{3\}\; d\; (d,\; k)\; \backslash \; right]\; \backslash \; quad\; =\; \{\backslash \; frac\; \{4\}\; \{2\}\}\; +\; \{\backslash \; frac\; \{7-7\}\; \{2\}\}\; =\; 2\}$

$\delta \; (w,\; d)\; =\; d\; (v,\; d)\; -\; \delta \; (v,\; w)\; знак\; равно\; 4\; -\; 2\; =\; 2\; \{\backslash \; displaystyle\; \backslash \; delta\; (w,\; d)\; =\; d\; (v,\; d)\; -\; \backslash \; delta\; (v,\; w)\; =\; 4-2\; =\; 2\}$

$\delta \; (вес,\; е)\; знак\; равно\; d\; (v,\; е)\; -\; \delta \; (v,\; w)\; =\; 3\; -\; 2\; =\; 1\; \{\backslash \; displaystyle\; \backslash \; delta\; (w,\; e)\; =\; d\; (v,\; e)\; -\; \backslash \; delta\; (v,\; w)\; =\; 3-2\; =\; 1\}$

Теперь дерево соединения соседей завершено, как показано на рисунке.

Заключение: аддитивные расстояния

Этот пример представляет идеализированный случай: обратите внимание, что если мы перейдем от одного таксона к любому другому по ветвям дерева и просуммируем длины пройденных ветвей, результат будет равен расстоянию между этими таксонами во входной матрице расстояний. Например, переходя от $d\; \{\backslash \; displaystyle\; d\}$к $b\; \{\backslash \; displaystyle\; b\}$, мы имеем $2\; +\; 2\; +\; 3\; +\; 3\; =\; 10\; \{\backslash \; Displaystyle\; 2\; +\; 2\; +\; 3\; +\; 3\; =\; 10\}$. Матрица расстояний, расстояния которой совпадают таким образом с некоторым деревом, называется «аддитивной», что редко встречается на практике. Тем не менее, важно отметить, что, учитывая аддитивную матрицу расстояний в качестве входных данных, соединение соседей гарантированно найдет дерево, расстояния между таксонами которого согласуются с ним.

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

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

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

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

Есть много доступных программ, реализующих соединение соседей. RapidNJ и NINJA - это быстрые реализации с типичным временем выполнения, пропорциональным приблизительно квадрату количества таксонов. BIONJ и Weighbor - это варианты объединения соседей, которые улучшают его точность за счет использования того факта, что более короткие расстояния в матрице расстояний обычно лучше известны, чем более длинные расстояния. FastME - это реализация тесно связанного метода сбалансированной минимальной эволюции.

• Поиск ближайшего соседа
• UPGMA и WPGMA
• Минимальная эволюция

Другие источники

• Метод соединения соседей - учебное пособие