Присоединение к соседу

В биоинформатики , сосед присоединения снизу вверх (агломерационного) кластеризация метод для создания филогенетических деревьев , созданного Naruya Saitou и Masatoshi Nei в 1987 году ^[1] Обычно используется для деревьев , основанных на ДНК или белковых последовательностей данных, алгоритм требует знание расстояния между каждой парой таксонов (например, видами или последовательностями) для формирования дерева. ^[2]

Алгоритм [ править ]

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

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

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

Q-матрица [ править ]

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

${\ Displaystyle Q (я, j) ​​= (п-2) d (я, j) ​​- \ сумма _ {к = 1} ^ {n} d (я, к) - \ сумма _ {к = 1} ^ {n} d (j, k)}$

( 1 )

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

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

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

${\displaystyle \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 )

а также:

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

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

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

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

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

( 3 )

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

Сложность [ править ]

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

Пример [ править ]

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

Первый шаг [ править ]

Первое присоединение [ править ]

Рассчитываем значения по уравнению ( 1 ). Например:${\displaystyle Q_{1}}$

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}$

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

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

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

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

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

${\displaystyle \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}$

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

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

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

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

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

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

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

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

Второй шаг [ править ]

Второе присоединение [ править ]

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

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

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

Длины стыковки ветвей и до могут быть рассчитаны:${\displaystyle u}$${\displaystyle c}$${\displaystyle v}$

${\displaystyle \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}$

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

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

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

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

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

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

Последний шаг [ править ]

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

${\displaystyle 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}$

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

${\displaystyle \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}$

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

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

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

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

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

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

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

Преимущества и недостатки [ править ]

Главное достоинство NJ в том, что он быстр ^{[6] : 466} по сравнению с методами наименьших квадратов , максимальной экономии и максимального правдоподобия . ^[6] Это делает его практичным для анализа больших наборов данных (сотни или тысячи таксонов) и для самонастройки , для чего другие средства анализа (например, максимальная экономия , максимальная вероятность ) могут быть недоступны с вычислительной точки зрения .

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

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

Реализации и варианты [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Другие источники [ править ]

Внешние ссылки [ править ]

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