Русская Википедия:Метод присоединения соседей

Материал из Онлайн справочника
Версия от 14:18, 27 августа 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} Файл:Neighbor-joining Tree-2, falsely promoting scientific racism by using Negroid, Mongoloid and Australoid.png|thumb|right|344x344px|Карта генетических расстояний, созданная в 2002 году — оценка 18 групп людей с помощью метода присоединения соседей, основанная на 23 типах г...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Файл:Neighbor-joining Tree-2, falsely promoting scientific racism by using Negroid, Mongoloid and Australoid.png
Карта генетических расстояний, созданная в 2002 году — оценка 18 групп людей с помощью метода присоединения соседей, основанная на 23 типах генетической информации. Карта была создана Наруя Сайтоу Шаблон:Nihongo, профессором в Японском Национальном Институте Генетики[1].

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

Алгоритм

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

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

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

Шаблон:Anchor

Q-матрица

<math>Q</math>-матрица рассчитывается по матрице расстояний между <math>n</math> таксонами следующим образом[5]: Шаблон:Нумерованная формула

где <math>d(i,j)</math> − расстояние между таксонами <math>i</math> и <math>j</math>. Шаблон:Anchor

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

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

<math>\delta(g,u)=d(f,g)-\delta(f,u) \quad </math>

Таксоны <math>f</math> и <math>g</math> − пара присоединённых таксонов и <math>u</math> − новый узел. Ветви <math>(f,u)</math> и <math>(g,u)</math> и их длины <math>\delta(f,u)</math> и <math>\delta(g,u)</math> − теперь фиксированная часть дерева; они не изменятся и ни на что не повлияют на следующих шагах алгоритма[5]. Шаблон:Anchor

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

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

Шаблон:Нумерованная формула

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

Сложность

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

Пример

Файл:Constructing phylogenetic tree using neighbor-joining 5 taxa improved.svg
Метод присоединения соседей на примере 5 таксонов. В данном случае будет получено полностью разрешённое дерево за две итерации. На ветках итогового дерева отмечены их длины.

Шаблон:Anchor

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

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) вычислим <math>Q</math>-матрицу (диагональные элементы матрицы не используются и здесь опущены):

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

Наименьшее значение матрицы <math>Q(a,b)=-50</math>, значит к новому узлу <math>u</math> присоединяем таксоны <math>a</math> и <math>b</math>. Вычислим расстояния от <math>a</math> и <math>b</math> до <math>u</math> по формуле (2):

<math>\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</math>
<math>\delta(b,u)=d(a,b)-\delta(a,u) \quad = 5-2 = 3</math>

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

<math>d(u,c)=\frac{1}{2} [d(a,c)+d(b,c)-d(a,b)] = \frac{9+10-5}{2} = 7</math>
<math>d(u,d)=\frac{1}{2} [d(a,d)+d(b,d)-d(a,b)] = \frac{9+10-5}{2} = 7</math>
<math>d(u,e)=\frac{1}{2} [d(a,e)+d(b,e)-d(a,b)] = \frac{8+9-5}{2} = 6</math>

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

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

Соответствующая ей <math>Q</math>-матрица:

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

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

<math>d(v,d)=\frac{1}{2} [d(u,d)+d(c,d)-d(u,c)] = \frac{7+8-7}{2} = 4</math>
<math>d(v,e)=\frac{1}{2} [d(u,e)+d(c,e)-d(u,c)] = \frac{6+7-7}{2} = 3</math>

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

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

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

<math>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</math>

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

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

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

<math>\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</math>
<math>\delta(w,d)=d(v,d)-\delta(v,w) = 4-2 = 2</math>
<math>\delta(w,e)=d(v,e)-\delta(v,w) = 3-2 = 1</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

Шаблон:Примечания

Ссылки

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

Шаблон:Выбор языка Шаблон:Добротная статья