Просмотр кода страницы Метод присоединения соседей

[[Файл:Neighbor-joining Tree-2, falsely promoting scientific racism by using Negroid, Mongoloid and Australoid.png|thumb|right|344x344px|Карта генетических расстояний, созданная в 2002 году — оценка 18 групп людей с помощью метода присоединения соседей, основанная на 23 типах генетической информации. Карта была создана Наруя Сайтоу {{nihongo||斎藤成也}}, профессором в Японском Национальном Институте Генетики<ref>[http://www.museum.kyushu-u.ac.jp/WAJIN/113.html Saitou. Kyushu Museum. 2002. February 2, 2007] {{webarchive|url=https://web.archive.org/web/20130906055349/http://www.museum.kyushu-u.ac.jp/WAJIN/113.html |date=2013-09-06 }}</ref>.]]
'''Метод присоединения соседей''' (''в лингвистике'' «метод ближайших соседей»<ref>{{книга |автор= Бурлак С. А., Старостин С. А. |заглавие=Сравнительно-историческое языкознание |издательство= |год=2005 |isbn= |страницы=270—271 |ссылка= |издание = 2-е изд. | место         = Москва}}</ref>) — алгоритм [[биоинформатика|биоинформатики]] и [[лингвистика|лингвистики]], разработанный [[Наруя Сайтоу]] и [[Нэи, Масатоси|Масатоси Нэи]] в 1987 году<ref name="saitou">{{статья |заглавие=The neighbor-joining method: a new method for reconstructing phylogenetic trees |издание={{Нп3|Molecular Biology and Evolution}} |том=4 |номер=4 |страницы=406—425 |pmid=447015 |ссылка=http://mbe.oxfordjournals.org/content/4/4/406.long |язык=en |тип=journal |автор=Saitou N., Nei M. |год=1987 |издательство=[[Oxford University Press]] |archivedate=2014-12-25 |archiveurl=https://web.archive.org/web/20141225202249/http://mbe.oxfordjournals.org/content/4/4/406.long }}</ref>. Это восходящий кластерный метод для создания [[филогенетическое дерево|филогенетических деревьев]]. Обычно используется для деревьев, основанных на [[ДНК]] или [[белок|белковых]] последовательностях, в лингвистике — на данных [[лексикостатистика|лексикостатистики]], реже фоно- или морфостатистики. Для его реализации необходимо вычислить расстояния между каждой парой [[таксон]]ов (например, видов или последовательностей)<ref>
{{книга |заглавие=Bacterial Population Genetics in Infectious Disease |часть=Sequence-Based Analysis of Bacterial Population Structures |издательство=[[John Wiley & Sons|John Wiley and Sons]] |год=2010 |isbn=978-0-470-42474-2 |страницы=46—47 |ссылка=https://books.google.com/books?id=gPVjfsWnGCcC&pg=PA46 |язык=en |автор=Xavier Didelot |ответственный=Robinson D. Ashley, Falush Daniel, Feil Edward J.}}</ref>.

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

Работа алгоритма начинается с полностью неразрешённого дерева с топологией «[[Звезда (топология компьютерной сети)|звезда]]»<ref name = "studier" />.
# Вычисляется [[Матрица расстояний|матрица попарных расстояний]] между таксонами.
# По текущей матрице расстояний считается <math>Q</math>-[[#f2|матрица]].
# Ищется пара различных таксонов <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, пока дерево не станет полностью разрешённым и не станут известны длины всех ветвей.
{{anchor|f1}}

=== Q-матрица ===
<math>Q</math>-матрица рассчитывается по матрице расстояний между <math>n</math> таксонами следующим образом<ref name="studier" />:
{{Нумерованная формула|:| <math>Q(i,j)=(n-2)d(i,j)-\sum_{k=1}^n d(i,k) - \sum_{k=1}^n d(j,k)</math>|3=<math>(1)</math>|RawN=.|LnSty=5px none white}}

где <math>d(i,j)</math> − расстояние между таксонами <math>i</math> и <math>j</math>.
{{anchor|f2}}

=== Расстояние между парой присоединённых соседей и новым узлом ===
Для каждого из присоединённых таксонов используется следующая формула для расчета расстояний до нового узла:
{{Нумерованная формула|:|<math>\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 </math>|3=<math>(2)</math>|RawN=.|LnSty=5px none white|ref=2}}
и:
: <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> − теперь фиксированная часть дерева; они не изменятся и ни на что не повлияют на следующих шагах алгоритма<ref name="studier" />.
{{anchor|f3}}

=== Расстояние между оставшимися таксонами и новым узлом ===
Для каждого таксона, не участвовавшего в предыдущем шаге, рассчитывается расстояние до нового узла<ref name="studier" />:

{{Нумерованная формула|:|<math>d(u,k)=\frac{1}{2} [d(f,k)+d(g,k)-d(f,g)]</math>|3=<math>(3)</math>|RawN=.|LnSty=5px none white|ref=3}}

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

=== Сложность ===
Метод присоединения соседей для <math>n</math> таксонов требует <math>n-3</math> итерации<ref name="studier" />. На каждой итерации требуется рассчитать <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|thumb|360px|Метод присоединения соседей на примере 5 таксонов. В данном случае будет получено полностью разрешённое дерево за две итерации. На ветках итогового дерева отмечены их длины.]]{{anchor|NJ_with_5_taxa}}

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

{| class="wikitable"
|-
! style="width: 20px;" |
! style="width: 20px;" | a
! style="width: 20px;" | b
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | 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
|}

По [[#f1|формуле (1)]] вычислим <math>Q</math>-матрицу (диагональные элементы матрицы не используются и здесь опущены):

{| class="wikitable"
|-
! style="width: 20px;" |
! style="width: 20px;" | a
! style="width: 20px;" | b
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | 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> по [[#f2|формуле (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>

По [[#f3|формуле (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>

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

{| class="wikitable"
|-
! style="width: 20px;" |
! style="width: 20px;" | u
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! u
| 0
| 7
| 7
| 6
|-
! c
| 7
| 0
| 8
| 7
|-
! d
| 7
| 8
| 0
| 3
|-
! e
| 6
| 7
| 3
| 0
|-
|}

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

{| class="wikitable"
|-
! style="width: 20px;" |
! style="width: 20px;" | u
! style="width: 20px;" | c
! style="width: 20px;" | d
! style="width: 20px;" | 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>

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

{| class="wikitable"
|-
! style="width: 20px;" |
! style="width: 20px;" | v
! style="width: 20px;" | d
! style="width: 20px;" | 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>
Матрица попарных расстояний:
{| class="wikitable" style="text-align: center;
|-
! style="width: 20px;" |
! style="width: 20px;" | v
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! v
|
| style=background:#ffffcc; | −10
| style=background:#ffffcc; | −10
|-
! d
| style=background:#ffffcc; | −10
|
| style=background:#ffffcc; | −10
|-
! e
| style=background:#ffffcc; | −10
| style=background:#ffffcc; | −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>

Матрица смежности:
{| class="wikitable"
|-
! style="width: 20px;" |
! style="width: 20px;" | w
! style="width: 20px;" | v
! style="width: 20px;" | d
! style="width: 20px;" | e
|-
! w
| 0
| 2
| 2
| 1
|-
! v
| 2
| 0
| 4
| 3
|-
! d
| 2
| 4
| 0
| 3
|-
! e
| 1
| 3
| 3
| 0
|-
|}

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

== Метод присоединения соседей как минимальная эволюция ==
Метод присоединения соседей можно рассматривать как [[жадный алгоритм]] для оптимизации дерева в соответствии с критерием «сбалансированной минимальной эволюции»<ref name="gascuel">{{статья |заглавие=Neighbor-joining revealed |издание={{Нп3|Molecular Biology and Evolution}} |том=23 |номер=11 |страницы=1997—2000 |doi=10.1093/molbev/msl072 |pmid=16877499 |язык=en |автор=Gascuel O., [[Mike Steel (mathematician)|Steel M]] |год=2006 |тип=journal |издательство=[[Oxford University Press]] }}</ref> (БМЭ). Для каждой топологии БМЭ определяет длину дерева (сумму длин ветвей) как взвешенную сумму расстояний из матрицы расстояний, с весами, зависящими от топологии дерева. Оптимальная топология БМЭ — та, при которой длина дерева минимальна. Метод присоединения соседей на каждой итерации соединяет пару таксонов, которые дадут наименьший вклад в длину строящегося дерева. Эта процедура не гарантирует нахождение дерева с топологией, оптимальной по критерию БМЭ, тем не менее, она часто находит оптимальное или близкое к оптимальному дерево.

== Достоинства и недостатки ==
Главное достоинство метода в том, что он быстрый — в частности, из-за того, что алгоритм работает за [[Класс P|полиномиальное]] время<ref name="studier">{{статья |заглавие=A note on the Neighbor-Joining algorithm of Saitou and Nei |издание={{Нп3|Molecular Biology and Evolution}} |том=5 |номер=6 |страницы=729—731 |pmid=3221794 |ссылка=http://mbe.oxfordjournals.org/cgi/reprint/5/6/729.pdf |язык=en |тип=journal |автор=Studier J. A., Keppler K. J. |год=1988 |издательство=[[Oxford University Press]] |archivedate=2008-12-16 |archiveurl=https://web.archive.org/web/20081216225203/http://mbe.oxfordjournals.org/cgi/reprint/5/6/729.pdf }}</ref>.
Это делает его приемлемым для анализа больших объёмов данных (сотни или тысячи таксонов)<ref name="studier" /> и для [[Статистический бутстрэп|бутстрэпа]]<ref>{{статья |заглавие=Bootstrapping Phylogenetic Trees:Theory and Methods |издание={{Нп3|Statistical Science}} |том=18 |номер=2 |страницы=241—255 |язык=en |тип=journal |автор=Holmes S. |год=2003}}</ref>
, для которых использование других методов анализа (например, [[:en:Maximum parsimony|максимальная экономия]], [[метод максимального правдоподобия]]) затруднительно с точки зрения количества вычислений<ref name = "all_methods">{{статья |заглавие=Progress with methods for constructing evolutionary trees |издание={{Нп3|Trends (journals)|Trends in Ecology and Evolution||Trends (journals)}} |том=7 |номер=3 |страницы=73—79 |doi=10.1016/0169-5347(92)90244-6 |pmid=21235960 |язык=en |тип=journal |автор=Penny D., Hendy M.D., [[Mike Steel (mathematician)|Steel M]] |год=1992}}</ref>.

Метод присоединения соседей имеет свойство выдавать правильное дерево на выходе, если на вход подается правильная матрица расстояний. Более того, правильная топология дерева гарантирована, если матрица расстояний «примерно аддитивна», то есть если каждое значение в матрице расстояний отличается от настоящего расстояния менее, чем на половину длины кратчайшей ветви дерева<ref>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.</ref>.

На практике матрица расстояний редко удовлетворяет этому условию, но метод присоединения соседей часто выдает дерево с правильной топологией в любом случае<ref name="levy">{{статья |заглавие=Why neighbor-joining works |издание={{Нп3|Algorithmica}} |том=54 |номер=1 |страницы=1—24 |ссылка=http://arxiv.org/abs/cs.DS/0602041 |doi=10.1007/s00453-007-9116-4 |язык=en |автор=Mihaescu R., Levy D., Pachter L. |год=2009 |тип=journal}}</ref>. Метод присоединения соседей корректно работает с примерно аддитивной матрицей расстояний, потому что она [[Состоятельная оценка|статистически состоятельна]] для многих эволюционных моделей; имея входные данные подходящей длины, метод с высокой вероятностью восстановит настоящее дерево. По сравнению с [[:en:UPGMA|UPGMA]] метод присоединения соседей имеет преимущество: он не предполагает, что все поколения эволюционируют с одинаковой скоростью ([[Молекулярные часы|гипотеза молекулярных часов]]).

Тем не менее, вместо метода присоединения соседей часто применяют другие филогенетические методы, не полагающиеся на матрицу расстояний и обеспечивающие бо́льшую точность в большинстве случаев<ref name = "all_methods"/>.

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

[http://birc.au.dk/Software/RapidNJ/ RapidNJ] и [https://web.archive.org/web/20121106234738/http://nimbletwist.com/software/ninja/ NINJA] — быстрые реализации, время работы которых обычно примерно пропорционально квадрату числа таксонов<ref>{{статья |заглавие=Rapid Neighbour Joining |издание=Proceedings of the 8th WABI |doi=10.1007/978-3-540-87361-7_10 |ссылка=http://birc.au.dk/fileadmin/uploaded/rapidNJ.pdf |том=5251 |страницы=113—122 |язык=und |автор=Martin Simonsen, Thomas Mailund, Christian N., S. Pedersen |год=2008}}{{Недоступная ссылка|date=Ноябрь 2017 |bot=InternetArchiveBot }}</ref><ref>{{книга |заглавие=Proceedings of the 8th Workshop in Algorithms in Bioinformatics |издательство=[[Springer Science+Business Media|Springer Verlag]] |год=2008 |doi=10.1007/978-3-540-87361-7_10 |страницы=113—122 |ссылка=http://users-birc.au.dk/cstorm/software/rapidnj/papers/SimonsenOthers2008_WABI.pdf |язык=en |автор=Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen |archivedate=2016-06-10 |archiveurl=https://web.archive.org/web/20160610154754/http://users-birc.au.dk/cstorm/software/rapidnj/papers/SimonsenOthers2008_WABI.pdf }}</ref>.

[http://www.atgc-montpellier.fr/bionj/ BIONJ] и [https://web.archive.org/web/20150305041147/http://www.t6.lanl.gov/billb/weighbor/ Weighbor] — варианты метода присоединения, повышающие его точность путём использования факта, что меньшие расстояния в матрице расстояний обычно лучше изучены, чем большие<ref>{{статья |заглавие=BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data |издание={{Нп3|Molecular Biology and Evolution}} |doi=10.1007/978-3-540-87361-7_10 |ссылка=http://www.atgc-montpellier.fr/download/papers/bionj_1997.pdf |том=14 |номер=7 |страницы=685—695 |язык=en |тип=journal |автор=Gascuel O. |год=1997 |издательство=[[Oxford University Press]] |archivedate=2021-04-25 |archiveurl=https://web.archive.org/web/20210425162318/http://www.atgc-montpellier.fr/download/papers/bionj_1997.pdf }}</ref><ref>{{статья |заглавие=Weighted Neighbor Joining: A Likelihood-Based Approach to Distance-Based Phylogeny Reconstruction |издание={{Нп3|Molecular Biology and Evolution}} |ссылка=http://mbe.oxfordjournals.org/content/17/1/189.full |том=17 |номер=1 |страницы=189—197 |язык=en |тип=journal |автор=William J. Bruno,  Nicholas D. Socci,  Aaron L. Halpern |год=2000 |издательство=[[Oxford University Press]] }}</ref>.

[https://www.ncbi.nlm.nih.gov/CBBresearch/Desper/FastME.html FastME] — реализация близкого метода сбалансированной минимальной эволюции<ref>{{статья |заглавие=Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle |издание={{Нп3|Journal of Computational Biology}} |ссылка=http://www.atgc-montpellier.fr/download/papers/fastme_2002.pdf |том=9 |номер=5 |страницы=687—705 |язык=en |тип=journal |автор=Desper R., Gascuel O. |год=2002 |archivedate=2021-04-25 |archiveurl=https://web.archive.org/web/20210425160837/http://www.atgc-montpellier.fr/download/papers/fastme_2002.pdf }}</ref>.

== См. также ==
* [[:en:Human genetic clustering|Human genetic clustering]]
* [[:en:Nearest neighbor search|Nearest neighbor search]]
* [[:en:UPGMA|UPGMA]]

== Примечания ==
{{примечания|2}}

== Ссылки ==
* [http://www.icp.be/~opperd/private/neighbor.html The Neighbor-Joining Method] — руководство{{ref-en}}

{{внешние ссылки}}
{{Добротная статья|Биоинформатика}}

{{DEFAULTSORT:Метод присоединения соседей}}
[[Категория:Биоинформатика]]
[[Категория:Эволюционная биология]]
[[Категория:Кластерный анализ]]