Русская Википедия:Метод присоединения соседей
Mетод присоединения соседей (в лингвистике «метод ближайших соседей»[2]) — алгоритм биоинформатики и лингвистики, разработанный Наруя Сайтоу и Масатоcи Нэи в 1987 году[3]. Это восходящий кластерный метод для создания филогенетических деревьев. Обычно используется для деревьев, основанных на ДНК или белковых последовательностях, в лингвистике — на данных лексикостатистики, реже фоно- или морфостатистики. Для его реализации необходимо вычислить расстояния между каждой парой таксонов (например, видов или последовательностей)[4].
Алгоритм
Работа алгоритма начинается с полностью неразрешённого дерева с топологией «звезда»[5].
- Вычисляется матрица попарных расстояний между таксонами.
- По текущей матрице расстояний считается <math>Q</math>-матрица.
- Ищется пара различных таксонов <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>.
- Рассчитывается расстояние от каждого из присоединённых таксонов до нового узла.
- Рассчитывается расстояние от каждого из оставшихся таксонов до нового узла.
- Формируем новую матрицу попарных расстояний: из текущей матрицы удаляем строки и столбцы, соответствующие только что присоединённым таксонам и добавляем новую вершину и, вычисленные в 5 пункте, расстояния.
- Повторяем шаги 2 — 5, пока дерево не станет полностью разрешённым и не станут известны длины всех ветвей.
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>; существуют реализации, использующие эвристический подход с меньшим временем выполнения в среднем.
Пример
Предположим, у нас есть пять таксонов <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].
См. также
Примечания
Ссылки
- The Neighbor-Joining Method — руководствоШаблон:Ref-en
- ↑ Saitou. Kyushu Museum. 2002. February 2, 2007 Шаблон:Webarchive
- ↑ Шаблон:Книга
- ↑ 3,0 3,1 Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ 5,0 5,1 5,2 5,3 5,4 5,5 5,6 Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 8,0 8,1 Шаблон:Статья
- ↑ Atteson K. (1997). "The performance of neighbor-joining algorithms of phylogeny reconstruction", pp. 101–110. In Jiang, T., and Lee, D., eds., Lecture Notes in Computer Science, 1276, Springer-Verlag, Berlin. COCOON '97.
- ↑ Шаблон:Статья
- ↑ Шаблон:СтатьяШаблон:Недоступная ссылка
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
Шаблон:Выбор языка Шаблон:Добротная статья
