Метод приєднання сусідів

Карта генетичних відстаней, створена в 2002 році — оцінка 18 груп людей за допомогою методу приєднання сусідів, що ґрунтується на 23 типах генетичної інформації. Карту було створено Наруя Сайтоу (斎藤成也), професором в Японському Національному інституті генетики.

У біоінформатиці метод приєднання сусідів − кластерний метод для створення філогенетичних дерев, запропонований Наруя Сайтоу і Масатоші Ней в 1987 році. Алгоритм звичайно використовується для дерев, заснованих на ДНК або білкових послідовностях, і вимагає знання відстаней між кожною парою таксонів (напр., видів або послідовностей) для побудови дерева.

Алгоритм

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

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

Q-матриця

$Q$-матриця розраховується за матрицею відстаней між $n$ таксонами наступним чином:

$Q(i,j)=(n-2)d(i,j)-\sum _{k=1}^{n}d(i,k)-\sum _{k=1}^{n}d(j,k)$

де $d(i,j)$ − відстань між таксонами $i$ і $j$.

Відстань між парою приєднаних сусідів і новим вузлом

Для кожного з приєднаних таксонів використовується наступна формула для обчислення відстаней до нового вузла:

$\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 (g,u)=d(f,g)-\delta (f,u)\quad$

Таксони $f$ і $g$ − пара приєднаних таксонів і $u$ − новий вузол. Гілки $(f,u)$ і $(g,u)$ і їх довжина $\delta (f,u)$ і $\delta (g,u)$ − тепер фіксована частина дерева; вони не зміняться і ні на що не вплинуть на наступних кроках алгоритму.

Відстань між залишеними таксонами і новим вузлом

Для кожного таксона, що не брав участі у попередньому кроці, розраховується відстань до нового вузла:

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

де $u$ − новий вузол, $k$ − вузол, до якого ми хочемо обрахувати відстань, $f$ і $g$ − таксони тільки-но приєднаної пари.

Складність

Метод приєднання сусідів для $n$ таксонів потребує $n-3$ ітерацій. На кожній ітерації потрібно обчислити $Q$-матрицю. На першому кроці розмір $Q$-матриці − $n\times n$, на наступному кроці − $(n-1)\times (n-1)$ і т. д. Реалізація алгоритму без оптимізації має складність $O(n^{3})$; існують реалізації, що використовують евристичний підхід з меншим часом виконання в середньому.

Приклад

Припустимо, у нас є п'ять таксонів $(a,b,c,d,e)$ з такою матрицею відстаней:

	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

Ми одержимо наступні значення $Q$-матриці (діагональні елементи матриці не використовуються і тут не наводяться):

	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

У наведеному прикладі $Q(a,b)=-50$. Це найменше значення $Q$, тому ми об'єднуємо вузли $a$ і $b$. Назовемо новий вузол $u$; гілки, що з'єднують $a$ i $b$ з новим вузлом $u$, мають довжину $\delta (a,u)=2$ і $\delta (b,u)=3$ − по наведеній вище формулі.

Далі ми знов перераховуємо матрицю відстаней: ми обраховуєм відстань від $u$ до кожного з вузлів, що залишилися, крім $a$ та $b$. Одержуєм $d(u,c)=7$, $d(u,d)=7$ і $d(u,e)=6$. Перерахована матриця відстаней має такий вигляд:

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

Відповідна до неї $Q$-матриця:

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

Тепер ми можем зробити вибір: з'єднувати $u$ і $c$ або з'єднувати $d$ і $e$; обидві пари мають найменше в $Q$-матриці значення $-28$, і будь-який вибір дасть однаковий результат. Для визначеності, оберемо $u$ і $c$, приєднаємо їх до нового вузла $v$; одержані гілки мають довжину $\delta (u,v)=3$ і $\delta (c,v)=4$, як показано на малюнку. Матриця відстаней для трьох вузлів, що залишилися $v$, $d$ і $e$ наступна:

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

Дерево цілком вирішено на цьому кроці, тому можна не обчислювати матрицю $Q$ і не виконувати подальші приєднання. Однак, ми використаємо ці відстані, щоб одержати довжину трьох гілок дерева, що залишилися — див. малюнок.

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

Метод приєднання сусідів як мінімальна еволюція

Метод приєднання сусідів можливо розглядати як жадний алгоритм для оптимізації дерева у відповідності з критерієм «збалансованої мінімальної еволюції» (БМЕ). Для кожної топології БМЕ визначає довжину дерева (суму довжин гілок) як зважену суму відстаней з матриці відстаней, з вагами, що залежать від топології дерева. Оптимальна топологія БМЕ — та, при якій довжина дерева мінімальна. Метод приєднання сусідів на кожній ітерації з'єднує пару таксонів, які дадуть найменший вклад у довжину побудованого дерева. Ця процедура не гарантує, що буде знайдено дерево з топологією, оптимальною за критерієм БМЕ, тим не менше, вона часто знаходить оптимальне або близьке до оптимального дерево.

Переваги і недоліки

Головна перевага методу в тому, що він швидкий — зокрема, через те, що алгоритм працює за поліноміальний час. Це робить його прийнятним для аналізу великих обсягів даних (сотні або й тисячі таксонів) і для бутстреппінгу, для яких використання інших методів аналізу (наприклад, максимальна економія, метод максимальної правдоподібності) може бути неможливим з точки зору кількості обчислень.

Метод приєднання сусідів має властивість видавати правильне дерево на виході, якщо на вхід подається правильна матриця відстаней. До того ж, правильну топологію дерева гарантовано, якщо матриця відстаней «приблизно адитивна», тобто, якщо кожне значення в матриці відстаней відрізняється від справжньої відстані менше, ніж на половину довжини найкоротшої гілки дерева. На практиці матриця відстаней рідко задовольняє цій умові, але метод приєднання сусідів часто видає дерево з правильною топологією у будь-якому випадку. Метод приєднання сусідів коректно працює з приблизно адитивною матрицею відстаней тому, що вона статистично спроможна для багатьох еволюційних моделей; маючи вхідні дані придатної довжини, метод з високою ймовірністю відновить справжнє дерево. У порівнянні з UPGMA метод приєднання сусідів має перевагу: він не передбачає, що всі покоління еволюціонують з однаковою швидкістю (гіпотеза молекулярного годинника).

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

Реалізації і варіанти

Існує багато програм, що реалізують метод приєднання сусідів. RapidNJ и NINJA — швидкі реалізації, час роботи яких звичайно приблизно пропорційний квадрату числа таксонів. BIONJ і Weighbor — варіанти методу приєднання сусідів, що підвищують його точність шляхом використання факту, що менші відстані в матриці відстаней звичайно краще вивчені, ніж великі. FastME — реалізація близького методу збалансованої мінімальної еволюції.

Див. також

• Кластеризація людських генів
• Пошук найближчого сусіда
• UPGMA

Посилання

• The Neighbor-Joining Method — a tutorial

Примітки

Інші джерела

• Studier JA, Keppler KJ (1988). A note on the Neighbor-Joining algorithm of Saitou and Nei (PDF). Mol Biol Evol. 5 (6): 729—731. PMID 3221794.
• Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen (2008). Rapid Neighbour Joining (PDF). Proceedings of WABI. 5251: 113—122. doi:10.1007/978-3-540-87361-7_10.^{[недоступне посилання з квітня 2019]}