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

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

В биоинформатике, Объединение соседей - это восходящий (агломеративный) метод кластеризации для создания филогенетических деревьев, созданных и Масатоши Ней в 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 {\ displaystyle Q}Q (определено ниже).
  2. Найти пару различных таксонов i и j (т.е. с i ≠ j {\ displaystyle i \ neq j}i \ neq j ), для которого Q (i, j) {\ displaystyle Q (i, j)}Q (i, j) имеет наименьшее значение. Эти таксоны присоединяются к вновь созданному узлу, который соединен с центральным узлом. На рисунке справа f и g присоединены к новому узлу u.
  3. Вычислите расстояние от каждого из таксонов в паре до этого нового узла.
  4. Рассчитайте расстояние от каждого таксона за пределами этой пары до нового узла.
  5. Запустите алгоритм снова, заменив пару объединенных соседей новым узлом и используя расстояния, вычисленные на предыдущем шаге.

Q-матрица

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

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

(1)

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

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

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

δ (f, u) = 1 2 d (f, g) + 1 2 (n - 2) [∑ k = 1 nd (f, k) - ∑ К знак равно 1 nd (g, k)] {\ 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}\ 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)

и:

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

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

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

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

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

(3)

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

Сложность

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

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

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

abcde
a05998
b5010109
c910087
d910803
e89730

Первый шаг

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

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

Q 1 (a, b) = (n - 2) d (a, b) - ∑ k = 1 5 d (a, k) - ∑ k = 1 5 d (b, k) { \ 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 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) × 5 - (5 + 9 + 9 + 8) - (5 + 10 + 10 + 9) = 15 - 31 - 34 = - 50 {\ displaystyle = (5-2) \ times 5- (5 + 9 + 9 + 8) - (5 + 10 + 10 + 9) = 15-31-34 = -50}{\ displaystyle = ( 5-2) \ умножить на 5- (5 + 9 + 9 + 8) - (5 + 10 + 10 + 9) = 15-31-34 = -50}

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

abcde
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 {\ displaystyle Q_ {1} (a, b) = - 50}{\ displaystyle Q_ {1} (a, b) = - 50} . Это наименьшее значение из Q 1 {\ displaystyle Q_ {1}}Q_ {1} , поэтому мы объединяем элементы a {\ displaystyle a}aи b {\ displaystyle b}b .

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

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

δ (a, u) = 1 2 d (a, b) + 1 2 (5–2) [∑ k = 1 5 d (a, к) - ∑ К знак равно 1 5 d (b, k)] = 5 2 + 31 - 34 6 = 2 {\ displaystyle \ delta (a, u) = {\ frac {1} {2}} d (a, б) + {\ 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 (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}
δ (b, u) = d (a, b) - δ (a, u) знак равно 5-2 = 3 {\ displaystyle \ delta (b, u) = d (a, b) - \ delta (a, u) \ quad = 5-2 = 3}{\ displaystyle \ delta (b, u) = d (a, b) - \ delta (a, u) \ quad = 5-2 = 3}

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

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

d (u, c) = 1 2 [d (a, c) + d (b, c) - d (a, b)] = 9 + 10 - 5 2 = 7 {\ 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, c) = {\ frac {1} {2}} [d (a, c) + d (b, c) -d (a, b)] = {\ 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 {\ 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, d) = {\ frac {1} {2}} [d (a, d) + d (b, d) -d (a, b)] = {\ 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 {\ Displaystyle d (u, e) = {\ frac {1} {2}} [d (a, e) + d (b, e) -d (a, b)] = { \ frac {8 + 9-5} {2}} = 6}{\ displaystyle d (u, e) = {\ frac {1} {2}} [d (a, e) + d (b, e) -d (a, b)] = {\ гидроразрыв {8 + 9-5} {2}} = 6}

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

ucde
u0776
c7087
d7803
e6730

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

Второй шаг

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

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

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

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

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

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

δ (u, v) = 1 2 d (u, c) + 1 2 (4–2) [∑ k Знак равно 1 4 d (u, К) - ∑ К знак равно 1 4 d (c, k)] = 7 2 + 20 - 22 4 = 3 {\ 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 (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}
δ (c, v) знак равно d (u, c) - δ (u, v) = 7-3 = 4 {\ displaystyle \ delta (c, v) = d (u, c) - \ delta (u, v) \ quad = 7-3 = 4}{\ displaystyle \ delta (c, v) = d (u, c) - \ delta (u, v) \ quad = 7-3 = 4}

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

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

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

d (v, d) = 1 2 [d (u, d) + d (c, d) - d (u, c)] = 7 + 8 - 7 2 Знак равно 4 {\ 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, d) = {\ гидроразрыв {1} {2}} [d (u, d) + d (c, d) -d (u, c)] = {\ 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 {\ Displaystyle d (v, e) = {\ frac {1} {2}} [d (u, e) + d (c, e) -d (u, c)] = {\ frac {6 + 7-7} {2}} = 3}{\ displaystyle d (v, e) = { \ frac {1} {2}} [d (u, e) + d (c, e) -d (u, c)] = {\ frac {6 + 7-7} {2}} = 3}
vde
v043
d403
e330

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

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

Q 3 (v, e) = (3 - 2) d (v, e) - ∑ k = 1 3 d (v, k) - ∑ k = 1 3 d (e, k) = 3 - 7 - 6 = - 10 {\ 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 Q_ {3} (v, e) = (3-2) d (v, e) - \ sum _ {k = 1} ^ {3} d (v, k) - \ сумма _ {к = 1} ^ {3} d (е, k) = 3-7-6 = -10}
vde
v−10−10
d−10−10
e−10−10

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

δ (v, w) = 1 2 d (v, d) + 1 2 (3 - 2) [∑ k = 1 3 d (v, k) - ∑ К знак равно 1 3 d (d, k)] = 4 2 + 7 - 7 2 = 2 {\ 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 (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}
δ (w, d) = d (v, d) - δ (v, w) знак равно 4 - 2 = 2 {\ displaystyle \ delta (w, d) = d (v, d) - \ delta (v, w) = 4-2 = 2}{\ displaystyle \ delta (w, d) = d (v, d) - \ delta (v, w) = 4-2 = 2}
δ (вес, е) знак равно d (v, е) - δ (v, w) = 3 - 2 = 1 {\ displaystyle \ delta (w, e) = d (v, e) - \ delta (v, w) = 3-2 = 1}{\ displaystyle \ delta (w, e) = d (v, e) - \ delta (v, w) = 3-2 = 1}

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

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

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

Объединение соседей как минимальная эволюция

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

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

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

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

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

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

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

См. Также
Ссылки

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

Внешние links
Последняя правка сделана 2021-05-31 13:53:06
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте