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

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

Алгоритм

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

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

1. На основе текущей матрицы расстояний вычисляем матрицу ${ displaystyle Q}$ (определено ниже).
2. Найдите пару различных таксонов i и j (т.е. с ${ displaystyle i neq j}$) для которого ${ Displaystyle Q (я, j)}$ имеет самое низкое значение. Эти таксоны присоединяются к вновь созданному узлу, который соединен с центральным узлом. На рисунке справа f и g присоединены к новому узлу u.
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 дельта (е, и)}$ и ${ 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}$ члены пары только что присоединились.

Сложность

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

Пример

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

Допустим, у нас пять таксонов ${ Displaystyle (а, б, в, д, д)}$ и следующая матрица расстояний ${ displaystyle D}$:

Первый шаг

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

Мы рассчитываем ${ displaystyle Q_ {1}}$ значения по уравнению (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}$.

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

Позволять ${ displaystyle u}$ обозначают новый узел. По уравнению (2), вверху ветви, соединяющиеся ${ 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}$

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

Затем мы приступаем к обновлению исходной матрицы расстояний ${ displaystyle D}$ в новую матрицу расстояний ${ displaystyle D_ {1}}$ (см. ниже), уменьшенного в размере на одну строку и один столбец из-за объединения ${ displaystyle a}$ с ${ displaystyle b}$ в своего соседа ${ displaystyle u}$. Используя уравнение (3) выше, мы вычисляем расстояние от ${ 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}$

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

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

Обновленная матрица расстояний ${ displaystyle D_ {2}}$ для остальных 3 узлов, ${ 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 иНИНДЗЯ являются быстрыми реализациями с типичным временем выполнения, приблизительно пропорциональным квадрату количества таксонов.BIONJ и Вес представляют собой варианты объединения соседей, которые повышают его точность за счет использования того факта, что более короткие расстояния в матрице расстояний обычно лучше известны, чем более длинные расстояния. FastME является реализацией тесно связанного метода сбалансированной минимальной эволюции.

Смотрите также

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

Рекомендации

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

внешняя ссылка

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