Метод присоединения соседей

Карта генетических расстояний, созданная в 2002 году — оценка 18 групп людей с помощью метода присоединения соседей, основанная на 23 типах генетической информации. Карта была создана Наруя Сайтоу (яп. 斎藤成也), профессором в Японском Национальном Институте Генетики.

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

Алгоритм

Алгоритм присоединения соседей начинается с дерева типа «звезда» (A), по вычисленной Q-матрице находится пара вершин с наименьшим значением, в данном случае f и g. Эта пара вершин присоединяется к новой вершине, u, как показано на рисунке (B). Ветки, вычерченные жирной линией больше не изменяются ни на одном из последующих шагов. По формуле (3) вычисляются расстояния от вершины u до вершин a — e. Затем процесс повторяется: по матрице расстояний между вершинами a, b, c, d, e, u, вычисляется Q-матрица. Затем, в данном случае, вершины u и e присоединяются к новой вершине v, как показано на дереве (C). После четвёртой итерации получаем дерево (D), а затем (E) — полностью разрешённое дерево.

Работа алгоритма начинается с полностью неразрешённого дерева с топологией «звезда».

1. Вычисляется матрица попарных расстояний между таксонами.
2. По текущей матрице расстояний считается $Q$-матрица.
3. Ищется пара различных таксонов $i$ и $j$ (то есть $i\neq j$), для которых значение $Q(i,j)$ — наименьшее. Эти таксоны присоединяются к новому узлу, который, в свою очередь, соединяется с центральным узлом. На рисунке справа $f$ и $g$ присоединены к новому узлу $u$.
4. Рассчитывается расстояние от каждого из присоединённых таксонов до нового узла.
5. Рассчитывается расстояние от каждого из оставшихся таксонов до нового узла.
6. Формируем новую матрицу попарных расстояний: из текущей матрицы удаляем строки и столбцы, соответствующие только что присоединённым таксонам и добавляем новую вершину и, вычисленные в 5 пункте, расстояния.
7. Повторяем шаги 2 — 5, пока дерево не станет полностью разрешённым и не станут известны длины всех ветвей.

Q-матрица

$Q$-матрица рассчитывается по матрице расстояний между $n$ таксонами следующим образом:

$Q(i,j)=(n-2)d(i,j)-\sum _{k=1}^{n}d(i,k)-\sum _{k=1}^{n}d(j,k)$

$(1)$

где $d(i,j)$ − расстояние между таксонами $i$ и $j$.

Расстояние между парой присоединённых соседей и новым узлом

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

$\delta (f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(n-2)}}\left[\sum _{k=1}^{n}d(f,k)-\sum _{k=1}^{n}d(g,k)\right]\quad$

$(2)$

и:

$\delta (g,u)=d(f,g)-\delta (f,u)\quad$

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

Расстояние между оставшимися таксонами и новым узлом

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

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

$(3)$

где $u$ — новый узел, $k$ — узел, до которого мы хотим рассчитать расстояние, $f$ и $g$ — таксоны только что присоединённой пары.

Сложность

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

Пример

Метод присоединения соседей на примере 5 таксонов. В данном случае будет получено полностью разрешённое дерево за две итерации. На ветках итогового дерева отмечены их длины.

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

	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

По формуле (1) вычислим $Q$-матрицу (диагональные элементы матрицы не используются и здесь опущены):

	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(a,b)=-50$, значит к новому узлу $u$ присоединяем таксоны $a$ и $b$. Вычислим расстояния от $a$ и $b$ до $u$ по формуле (2):

$\delta (a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}\left[\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)\right]\quad ={\frac {5}{2}}+{\frac {31-34}{6}}=2$

$\delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3$

По формуле (3) вычисляем расстояния от новой вершины до оставшихся вершин:

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

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

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

Таким образом, новая матрица попарных расстояний имеет вид:

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

Соответствующая ей $Q$-матрица:

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

Теперь наша матрица принимает минимальное значение на двух парах: $u$, $c$ и $d$, $e$. Конечное филогенетическое дерево не зависит от того, какую пару мы выберем. Для определённости, выберем $u$ и $c$, присоединим их к новому узлу $v$. Как и в первой итерации вычислим расстояния от $u$ и $c$ до $v$. Они равны $\delta (u,v)=3$ и $\delta (c,v)=4$. Расстояния от новой вершины $v$ до оставшихся узлов $d$ и $e$ равны:

$d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4$

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

Теперь матрица попарных расстояний имеет вид:

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

Таким образом, мы получили полностью разрешённое дерево. Однако, для полноты стоит провести ещё одну итерацию:

$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$

Матрица попарных расстояний:

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

Выберем пару $v$ и $d$ и создадим новую вершину $w$. Расстояния до этой вершины от вершин $v$, $d$, $e$ равны соответственно:

$\delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+{\frac {7-7}{2}}=2$

$\delta (w,d)=d(v,d)-\delta (v,w)=4-2=2$

$\delta (w,e)=d(v,e)-\delta (v,w)=3-2=1$

Матрица смежности:

	w	v	d	e
w	0	2	2	1
v	2	0	4	3
d	2	4	0	3
e	1	3	3	0

Таким образом, мы узнали длины всех ветвей и получили полное филогенетическое дерево, показанное на рисунке. Приведённый пример представляет собой идеальный случай: заметим, что если двигаться от одного таксона к другому по ветвям дерева и суммировать длины пройденных ветвей, результат будет равен расстоянию между таксонами в первоначальной матрице расстояний. Например, пройдя от узла $d$ к узлу $b$, мы получим $2+2+3+3=10$. Про матрицу, в которой расстояния согласованы таким образом с каким-либо деревом, говорят, что она аддитивна — свойство, редко встречающееся на практике. Однако важно заметить: если на вход методу присоединения соседей подать аддитивную матрицу расстояний, гарантируется, что в результате работы метода будет построено дерево, согласованное с этой матрицей.

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

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

Достоинства и недостатки

Главное достоинство метода в том, что он быстрый — в частности, из-за того, что алгоритм работает за полиномиальное время. Это делает его приемлемым для анализа больших объёмов данных (сотни или тысячи таксонов) и для бутстрэпа , для которых использование других методов анализа (например, максимальная экономия, метод максимального правдоподобия) затруднительно с точки зрения количества вычислений.

Метод присоединения соседей имеет свойство выдавать правильное дерево на выходе, если на вход подается правильная матрица расстояний. Более того, правильная топология дерева гарантирована, если матрица расстояний «примерно аддитивна», то есть если каждое значение в матрице расстояний отличается от настоящего расстояния менее, чем на половину длины кратчайшей ветви дерева.

На практике матрица расстояний редко удовлетворяет этому условию, но метод присоединения соседей часто выдает дерево с правильной топологией в любом случае. Метод присоединения соседей корректно работает с примерно аддитивной матрицей расстояний, потому что она статистически состоятельна для многих эволюционных моделей; имея входные данные подходящей длины, метод с высокой вероятностью восстановит настоящее дерево. По сравнению с UPGMA метод присоединения соседей имеет преимущество: он не предполагает, что все поколения эволюционируют с одинаковой скоростью (гипотеза молекулярных часов).

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

Реализации и варианты

Существует много программ, реализующих метод присоединения соседей.

RapidNJ и NINJA — быстрые реализации, время работы которых обычно примерно пропорционально квадрату числа таксонов.

BIONJ и Weighbor — варианты метода присоединения, повышающие его точность путём использования факта, что меньшие расстояния в матрице расстояний обычно лучше изучены, чем большие.

FastME — реализация близкого метода сбалансированной минимальной эволюции.

См. также

• Human genetic clustering
• Nearest neighbor search
• UPGMA

Ссылки

• The Neighbor-Joining Method — руководство (англ.)