Присоединение соседа

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

Алгоритм

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

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

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

Q-матрица

На основе матрицы расстояний, связывающей $n$ таксоны, рассчитайте $n$ х $n$ матрица $Q$ следующее:

$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)$ и следующая матрица расстояний $D$:

	а	б	с	д	и
а	0	5	9	9	8
б	5	0	10	10	9
с	9	10	0	8	7
д	9	10	8	0	3
и	8	9	7	3	0

Первый шаг

Первое присоединение

Мы рассчитываем $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)$

$=(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50$

Мы получаем следующие значения для $Q_{1}$ матрица (диагональные элементы матрицы не используются издесь опущено):

	а	б	с	д	и
а		−50	−38	−34	−34
б	−50		−38	−34	−34
с	−38	−38		−40	−40
д	−34	−34	−40		−48
и	−34	−34	−40	−48

В приведенном выше примере $Q_{1}(a,b)=-50$. Это наименьшее значение $Q_{1}$, поэтому мы соединяем элементы $a$ и $b$.

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

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

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

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

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

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

Полученная матрица расстояний $D_{1}$ является:

	в	с	д	и
в	0	7	7	6
с	7	0	8	7
д	7	8	0	3
и	6	7	3	0

Жирные значения в $D_{1}$ соответствуют вновь рассчитанным расстояниям, тогда как значения, выделенные курсивом, не затрагиваются обновлением матрицы, поскольку они соответствуют расстояниям между элементами, не участвующими в первом объединении таксонов.

Второй шаг

Второе присоединение

Соответствующий $Q_{2}$ матрица:

	в	с	д	и
в		−28	−24	−24
с	−28		−24	−24
д	−24	−24		−28
и	−24	−24	−28

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

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

Длины соединяющихся ветвей $u$ и $c$ к $v$ можно рассчитать:

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

$\delta (c,v)=d(u,c)-\delta (u,v)\quad =7-3=4$

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

Обновление матрицы второго расстояния

Обновленная матрица расстояний $D_{2}$ для остальных 3 узлов, $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	д	и
v	0	4	3
д	4	0	3
и	3	3	0

Последний шаг

На этом этапе древовидная топология полностью решена. Однако для наглядности можно вычислить $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$

	v	д	и
v		−10	−10
д	−10		−10
и	−10	−10

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

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

Дерево объединения соседей теперь завершено, как показано на рисунке .

Вывод: аддитивные расстояния

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

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

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

Преимущества и недостатки

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

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

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

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

Существует множество программ, реализующих присоединение к соседям. Среди реализаций канонического NJ (т. е. использующего классические критерии оптимизации NJ и, следовательно, дающего те же результаты), RapidNJ (начат в 2003 г., основное обновление в 2011 г., все еще обновляется в 2023 г.) и NINJA (начало 2009 г., последнее обновление 2013 г.) считаются современными. Типичное время их выполнения пропорционально квадрату числа таксонов.

Варианты, отклоняющиеся от канонических, включают:

• БИОНДЖ (1997) и Вейбор (2000), повышение точности за счет использования того факта, что более короткие расстояния в матрице расстояний обычно известны лучше, чем более длинные. Оба метода были расширены для работы с неполными матрицами расстояний.
• «Быстрый Нью-Джерси» запоминает лучший узел и всегда равен O(n^2); «Relax NJ» выполняет поиск с подъемом на холм и сохраняет сложность наихудшего случая O(n^3). Рапид Нью-Джерси быстрее, чем обычный расслабленный Нью-Джерси.
• FastME — это реализация тесно связанного метода сбалансированной минимальной эволюции (BME) (см. § Соединение соседей как минимальная эволюция ). Он примерно такой же быстрый и более точный, чем Нью-Джерси. Он начинается с грубого дерева, а затем улучшает его с помощью набора топологических ходов, таких как обмен ближайшими соседями (NNI). FastTree — родственный метод. Он работает с «профилями» последовательности, а не с матрицей. Он начинается с дерева примерно Нью-Джерси, преобразует его в BME, а затем преобразует в приближенное максимальное правдоподобие.

См. также

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

Ссылки

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

• Студент Дж. А., Кепплер К. Дж. (1988). «Заметка об алгоритме соединения соседей Сайто и Ней» . Мол Биол Эвол . 5 (6): 729–731. doi : 10.1093/oxfordjournals.molbev.a040527 . ПМИД   3221794 .
• Мартин Симонсен; Томас Майлунд; Кристиан Н.С. Педерсен (2008). «Быстрое присоединение к соседям». Алгоритмы в биоинформатике . Конспекты лекций по информатике. Том. 5251. стр. 113–122. CiteSeerX   10.1.1.218.2078 . дои : 10.1007/978-3-540-87361-7_10 . ISBN  978-3-540-87360-0 .

Внешние ссылки

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