Перегляд вихідного коду сторінки Метод приєднання сусідів

[[Файл:Neighbor-joining Tree-2, falsely promoting scientific racism by using Negroid, Mongoloid and Australoid.png|thumb|right|350px|Карта генетичних відстаней, створена в 2002 році&nbsp;— оцінка 18 груп людей за допомогою методу приєднання сусідів, що ґрунтується на 23 типах генетичної інформації. Карту було створено Наруя Сайтоу (斎藤成也), професором в Японському Національному інституті генетики.<ref>{{Cite web |url=http://www.museum.kyushu-u.ac.jp/WAJIN/113.html |title=Saitou. Kyushu Museum. 2002. February 2, 2007 |accessdate=грудень 11, 2014 |archiveurl=https://web.archive.org/web/20130906055349/http://www.museum.kyushu-u.ac.jp/WAJIN/113.html |archivedate=вересень 6, 2013 |deadurl=yes }}</ref>]]

У біоінформатиці '''метод приєднання сусідів''' − кластерний метод для створення [[філогенетичне дерево|філогенетичних дерев]], запропонований [[Наруя Сайтоу]] і [[Масатоші Ней]] в 1987 році.<ref>{{Cite web |url=http://mbe.oxfordjournals.org/content/4/4/406.long |title=Saitou N, Nei M. he neighbor-joining method: a new method for reconstructing phylogenetic trees // Molecular Biology and Evolution. — 1987. — Vol. 4, issue 4. — P. 406–425. — July 1987. |accessdate=11 грудня 2014 |archive-date=25 грудня 2014 |archive-url=https://web.archive.org/web/20141225202249/http://mbe.oxfordjournals.org/content/4/4/406.long }}</ref> Алгоритм звичайно використовується для дерев, заснованих на [[ДНК]] або [[білок|білкових]] послідовностях, і вимагає знання відстаней між кожною парою [[таксон]]ів (напр., видів або послідовностей) для побудови дерева.
<ref>{{cite book
 | title = Bacterial Population Genetics in Infectious Disease
 | editor = D. Ashley Robinson, Daniel Falush, Edward J. Feil
 | chapter = Sequence-Based Analysis of Bacterial Population Structures
 | author = Xavier Didelot
 | publisher = John Wiley and Sons
 | year = 2010
 | isbn = 978-0-470-42474-2
 | pages = 46–47
 | url = http://books.google.com/books?id=gPVjfsWnGCcC&pg=PA46
 | accessdate = 11 грудня 2014
 | archive-date = 1 липня 2014
 | archive-url = https://web.archive.org/web/20140701115428/http://books.google.com/books?id=gPVjfsWnGCcC&pg=PA46
 }}</ref>

== Алгоритм ==
Метод приєднання сусідів на вхід приймає [[матриця відстаней|матрицю відстаней]], де задаються відстані між кожною парою таксонів. Алгоритм починає роботу з цілком невирішеного дерева с топологією [[Зірка (топологія комп'ютерної мережі)|«зірка»]], і виконує ітерації, що складаються з описаних далі кроків, до моменту, коли дерево цілком вирішене і довжини усі гілок відомі:

# По поточній матриці відстаней вираховується <math>Q</math>-матриця (визначена нижче)
# Відшукується пара різних таксонів <math>i</math> і <math>j</math> (тобто <math>i \neq j</math>), для яких значення <math>Q(i,j)</math> − найменше. Ці таксони приєднуються до нового вузла, який, в свою чергу, з'єднується p центральним вузлом. На рисунку праворуч <math>f</math> і <math>g</math> приєднані до нового вузла <math>u</math>
# Розраховується відстань від кожного з приєднаних таксонів до нового вузла
# Розраховується відстань від кожного з залишених таксонів до нового вузла
# Алгоритм запускається знову, замінюючи пару приєднаних сусідів на новий вузол і використовуючи відстані, обраховані на попередніх кроках.

=== Q-матриця ===
<math>Q</math>-матриця розраховується за матрицею відстаней між <math>n</math> таксонами наступним чином:
<center>
<math>Q(i,j)=(n-2)d(i,j)-\sum_{k=1}^n d(i,k) - \sum_{k=1}^n d(j,k)</math>
</center>
де <math>d(i,j)</math> − відстань між таксонами <math>i</math> і <math>j</math>.

=== Відстань між парою приєднаних сусідів і новим вузлом ===
Для кожного з приєднаних таксонів використовується наступна формула для обчислення відстаней до нового вузла:
<center>
<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>
</center>
і:
<center>
<math>\delta(g,u)=d(f,g)-\delta(f,u) \quad </math>
</center>
Таксони <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> − тепер фіксована частина дерева; вони не зміняться і ні на що не вплинуть на наступних кроках алгоритму.

=== Відстань між залишеними таксонами і новим вузлом ===
Для кожного таксона, що не брав участі у попередньому кроці, розраховується відстань до нового вузла:
<center>
<math>d(u,k)=\frac{1}{2} [d(f,k)+d(g,k)-d(f,g)]</math>
</center>
де <math>u</math> − новий вузол, <math>k</math> − вузол, до якого ми хочемо обрахувати відстань, <math>f</math> і <math>g</math> − таксони тільки-но приєднаної пари.

=== Складність ===
Метод приєднання сусідів для <math>n</math> таксонів потребує <math>n-3</math> ітерацій. На кожній ітерації потрібно обчислити <math>Q</math>-матрицю. На першому кроці розмір <math>Q</math>-матриці − <math>n\times n</math>, на наступному кроці − <math>(n-1)\times(n-1)</math> і&nbsp;т.&nbsp;д. Реалізація алгоритму без оптимізації має складність <math>O(n^3)</math>; існують реалізації, що використовують [[Евристичний алгоритм|евристичний підхід]] з меншим часом виконання в середньому.

== Приклад ==
Припустимо, у нас є п'ять таксонів <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
|}

Ми одержимо наступні значення <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>Q</math>, тому ми об'єднуємо вузли <math>a</math> і <math>b</math>.
Назовемо новий вузол <math>u</math>; гілки, що з'єднують <math>a</math> i <math>b</math> з новим вузлом <math>u</math>, мають довжину <math>\delta(a,u)=2</math> і <math>\delta(b,u)=3</math> − по наведеній вище формулі.

Далі ми знов перераховуємо матрицю відстаней: ми обраховуєм відстань від <math>u</math> до кожного з вузлів, що залишилися, крім <math>a</math> та <math>b</math>. Одержуєм <math>d(u,c)=7</math>, <math>d(u,d)=7</math> і <math>d(u,e)=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>Q</math>-матриці значення <math>-28</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> наступна:

{| 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</math> і не виконувати подальші приєднання. Однак, ми використаємо ці відстані, щоб одержати довжину трьох гілок дерева, що залишилися&nbsp;— див. малюнок.

Наведений приклад є ідеальним випадком: зазначимо, що, якщо рухатися від одного таксона до іншого по гілках дерева і підсумовувати довжини пройдених гілок, результат буде дорівнювати відстані між таксонами у вихідній матриці відстаней. Напр., пройшовши від вузла <math>d</math> до вузла <math>b</math>, одержимо <math>2+2+3+3=10</math>. Про матрицю, в якій відстані узгоджені таким чином з будь-яким деревом, кажуть, що вона [[Адитивність|адитивна]] − властивість, яка рідко зустрічається на практиці. Однак варто зауважити: якщо на вхід методу приєднання сусідів подати адитивну матрицю відстаней, гарантується, що в результаті роботи методу буде побудоване дерево, узгоджене з цією матрицею.

== Метод приєднання сусідів як мінімальна еволюція ==
Метод приєднання сусідів можливо розглядати як [[жадний алгоритм]] для оптимізації дерева у відповідності з критерієм «збалансованої мінімальної еволюції»<ref name="gascuel">{{cite journal |author=Gascuel O, [[Mike Steel (mathematician)|Steel M]] |title=Neighbor-joining revealed |url=https://archive.org/details/sim_molecular-biology-and-evolution_2006-11_23_11/page/1997 |journal=Mol Biol Evol |volume=23 |issue=11 |pages=1997–2000 |year=2006 |doi=10.1093/molbev/msl072 |pmid=16877499}}</ref> (БМЕ). Для кожної топології БМЕ визначає довжину дерева (суму довжин гілок) як зважену суму відстаней з матриці відстаней, з вагами, що залежать від топології дерева. Оптимальна топологія БМЕ&nbsp;— та, при якій довжина дерева мінімальна. Метод приєднання сусідів на кожній ітерації з'єднує пару таксонів, які дадуть найменший вклад у довжину побудованого дерева. Ця процедура не гарантує, що буде знайдено дерево з топологією, оптимальною за критерієм БМЕ, тим не менше, вона часто знаходить оптимальне або близьке до оптимального дерево.

== Переваги і недоліки ==
Головна перевага методу в тому, що він швидкий&nbsp;— зокрема, через те, що алгоритм працює за поліноміальний час.
Це робить його прийнятним для аналізу великих обсягів даних (сотні або й тисячі таксонів) і для {{не перекладено|Бутстреппінг|бутстреппінгу|en|Bootstrapping}}, для яких використання інших методів аналізу (наприклад, {{iw|Maximum_parsimony|максимальна економія|en|Maximum_parsimony}}, метод максимальної правдоподібності) може бути неможливим з точки зору кількості обчислень.

Метод приєднання сусідів має властивість видавати правильне дерево на виході, якщо на вхід подається правильна матриця відстаней.
До того ж, правильну топологію дерева гарантовано, якщо матриця відстаней «приблизно адитивна», тобто, якщо кожне значення в матриці відстаней відрізняється від справжньої відстані менше, ніж на половину довжини найкоротшої гілки дерева.<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">{{cite journal |author=Mihaescu R, Levy D, Pachter L |title=Why neighbor-joining works |journal=Algorithmica |volume=54 |issue=1| pages=1–24 |year=2009 | url = http://arxiv.org/abs/cs.DS/0602041 | doi=10.1007/s00453-007-9116-4}}</ref> Метод приєднання сусідів коректно працює з приблизно адитивною матрицею відстаней тому, що вона статистично спроможна для багатьох еволюційних моделей; маючи вхідні дані придатної довжини, метод з високою ймовірністю відновить справжнє дерево. У порівнянні з {{iw|UPGMA|UPGMA|en|UPGMA}} метод приєднання сусідів має перевагу: він не передбачає, що всі покоління еволюціонують з однаковою швидкістю ([[Молекулярний годинник|гіпотеза молекулярного годинника]]).

А втім, замість методу приєднання сусідів часто застосовують інші філогенетичні методи, які не покладаються на матрицю відстаней і забезпечують більшу точність у більшості випадків. Метод приєднання сусідів має небажану рису&nbsp;— часто присвоює негативні значення деяким гілкам дерева.

== Реалізації і варіанти ==
Існує багато програм, що реалізують метод приєднання сусідів.
[http://birc.au.dk/Software/RapidNJ/ RapidNJ] и
[https://web.archive.org/web/20121106234738/http://nimbletwist.com/software/ninja/ NINJA]&nbsp;— швидкі реалізації, час роботи яких звичайно приблизно пропорційний квадрату числа таксонів.
[http://www.atgc-montpellier.fr/bionj/ BIONJ] і [https://web.archive.org/web/20150305041147/http://www.t6.lanl.gov/billb/weighbor/ Weighbor]&nbsp;— варіанти методу приєднання сусідів, що підвищують його точність шляхом використання факту, що менші відстані в матриці відстаней звичайно краще вивчені, ніж великі. [http://www.ncbi.nlm.nih.gov/CBBresearch/Desper/FastME.html FastME]&nbsp;— реалізація близького методу збалансованої мінімальної еволюції.

== Див. також ==
* {{iw|Кластеризація людських генів||en|Human genetic clustering}}
* [[Пошук найближчого сусіда]]
* {{iw|UPGMA}}

== Посилання ==
* [http://www.icp.be/~opperd/private/neighbor.html The Neighbor-Joining Method]&nbsp;— a tutorial

== Примітки ==
{{reflist|2}}

;Інші джерела
{{refbegin}}
* {{cite journal |author=Studier JA, Keppler KJ |title=A note on the Neighbor-Joining algorithm of Saitou and Nei |journal=Mol Biol Evol |volume=5 |issue=6 |pages=729–731 |year=1988 |pmid=3221794 |url=http://mbe.oxfordjournals.org/cgi/reprint/5/6/729.pdf}}
* {{cite journal |author=Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen |title=Rapid Neighbour Joining |journal=Proceedings of WABI |year=2008 |doi=10.1007/978-3-540-87361-7_10 |url=http://birc.au.dk/fileadmin/uploaded/rapidNJ.pdf |volume=5251 |pages=113–122 }}{{Недоступне посилання|date=квітень 2019 |bot=InternetArchiveBot }}
{{refend}}

[[Категорія:Біоінформатика]]
[[Категорія:Еволюційна біологія]]
[[Категорія:Алгоритми кластерування даних]]
[[Категорія:Екологічна термінологія]]