Metoda de anexare a vecinului

Metoda de îmbinare a vecinilor ( în lingvistică „metoda celui mai apropiat vecin” [2] ) este un algoritm de bioinformatică și lingvistică dezvoltat de Naruya Saitou și Masatoshi Nei în 1987 [3] . Este o metodă de grup de jos în sus pentru generarea arborilor filogenetici . Utilizat de obicei pentru arbori bazați pe secvențe de ADN sau proteine , în lingvistică - pe date din lexicostatistică , mai rar din fono- sau morfostatistică. Pentru a-l implementa, este necesar să se calculeze distanțele dintre fiecare pereche de taxoni(de exemplu specii sau secvențe) [4] .

Algoritm

Algoritmul începe cu un arbore de topologie în stea complet nerezolvat [5 ] .

Se calculează matricea distanțelor perechi dintre taxoni .
Pe baza matricei de distanță curentă, se calculează matricea - . $Q$
Căutăm o pereche de taxoni diferiți și (adică ) pentru care valoarea este cea mai mică. Acești taxoni sunt atașați la un nou nod, care, la rândul său, este conectat la nodul central. În imaginea din dreapta și atașată noului nod . $i$ $j$ $eu \neq j$ $Q(i,j)$ $f$ $g$ $u$
Se calculează distanța de la fiecare dintre taxonii atașați la noul nod.
Se calculează distanța de la fiecare dintre taxonii rămași până la noul nod.
Formăm o nouă matrice de distanțe perechi: din matricea curentă ștergem rândurile și coloanele corespunzătoare taxonilor nou adăugați și adăugăm un nou vârf și distanțele calculate la punctul 5.
Repetați pașii 2-5 până când copacul este complet rezolvat și lungimile tuturor ramurilor sunt cunoscute.

Q-matrix

$Q$ -matricea se calculează prin matricea distanțelor dintre taxoni după cum urmează [5] : $n$

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

$(unu)$

unde este distanța dintre taxoni și . $d(i,j)$ $i$ $j$

Distanța dintre o pereche de vecini conectați și noul nod

Pentru fiecare dintre taxonii atașați, se utilizează următoarea formulă pentru a calcula distanța până la noul nod:

$\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)\dreapta]\quad$

$(2)$

și:

\delta (g,u)=d(f,g)-\delta (f,u)\quad

Taxa și − o pereche de taxoni atașați și − un nou nod. Ramurile și lungimile lor și sunt acum o parte fixă a copacului; nu se vor modifica și nu vor afecta nimic în pașii următori ai algoritmului [5] . $f$ $g$ $u$ $(f,u)$ $(g,u)$ $\delta(f,u)$ $\delta(g,u)$

Distanța dintre taxonii rămași și noul nod

Pentru fiecare taxon care nu a participat la pasul anterior, se calculează distanța până la noul nod [5] :

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

$(3)$

unde este noul nod, este nodul la care dorim să calculăm distanța și sunt taxonii perechii nou adăugate. $u$ $k$ $f$ $g$

Dificultate

Metoda de îmbinare a vecinilor pentru taxoni necesită iterare [5] . La fiecare iterație, este necesar să se calculeze matricea -. La primul pas, dimensiunea matricei este , la pasul următor și așa mai departe. Implementarea algoritmului fără optimizare are complexitate ; există implementări care utilizează o abordare euristică cu timpi de execuție mai mici în medie. $n$ $n-3$ $Q$ $Q$ $n\ ori n$ $(n-1)\times (n-1)$ $O(n^{3})$

Exemplu

Să presupunem că avem cinci taxoni cu următoarea matrice de distanțe: $(a,b,c,d,e)$

	A	b	c	d	e
A	0	5	9	9	opt
b	5	0	zece	zece	9
c	9	zece	0	opt	7
d	9	zece	opt	0	3
e	opt	9	7	3	0

Folosind formula (1) , calculăm -matricea (elementele diagonale ale matricei nu sunt folosite și sunt omise aici): $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

Cea mai mică valoare a matricei este , ceea ce înseamnă că adăugăm taxoni și noului nod . Calculați distanțele de la și până la cu formula (2) : $Q(a,b)=-50$ $u$ $A$ $b$ $A$ $b$ $u$

\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

\delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3

Folosind formula (3) , calculăm distanțele de la noul vârf la vârfurile rămase:

d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10 -5}{2}}=7

d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10 -5}{2}}=7

d(u,e)={\frac {1}{2}}[d(a,e)+d(b,e)-d(a,b)]={\frac {8+9 -5}{2}}=6

Astfel, noua matrice de distanțe pe perechi arată astfel:

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

Matricea corespunzătoare este: $Q$

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

Acum matricea noastră ia valoarea minimă pe două perechi: , și , . Arborele filogenetic final nu depinde de perechea pe care o alegem. Pentru certitudine, alegeți și atașați-le la un nou nod . Ca și în prima iterație, calculăm distanțele de la și până la . Sunt egali si . Distanțele de la noul vârf la nodurile rămase și sunt egale cu: $u$ $c$ $d$ $e$ $u$ $c$ $v$ $u$ $c$ $v$ $\delta(u,v)=3$ $\delta(c,v)=4$ $v$ $d$ $e$

d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8 -7}{2}}=4

d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7 -7}{2}}=3

Acum matricea distanțelor perechi arată astfel:

	v	d	e
v	0	patru	3
d	patru	0	3
e	3	3	0

Astfel, avem un arbore complet rezolvat. Cu toate acestea, de dragul completității, merită să faceți încă o iterație:

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

Matricea distanței în perechi:

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

Să selectăm o pereche și să creăm un nou vârf . Distanțele până la acest vârf de la vârfuri , , sunt, respectiv: $v$ $d$ $w$ $v$ $d$ $e$

\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

\delta (w,d)=d(v,d)-\delta (v,w)=4-2=2

\delta (w,e)=d(v,e)-\delta (v,w)=3-2=1

Matricea adiacentei:

	w	v	d	e
w	0	2	2	unu
v	2	0	patru	3
d	2	patru	0	3
e	unu	3	3	0

Astfel, am învățat lungimile tuturor ramurilor și am obținut arborele filogenetic complet prezentat în figură . Exemplul de mai sus este un caz ideal: rețineți că dacă vă mutați de la un taxon la altul de-a lungul ramurilor copacului și însumați lungimile ramurilor trecute, rezultatul va fi egal cu distanța dintre taxoni din matricea distanțelor inițiale. . De exemplu, trecând de la nod la nod , obținem . Se spune că o matrice în care distanțele sunt potrivite în acest fel cu un arbore este aditivă , o proprietate rar întâlnită în practică. Cu toate acestea, este important de reținut că, dacă o matrice de distanță aditivă este dată ca intrare în metoda de unire a vecinilor, este garantat că, ca urmare a metodei, va fi construit un arbore care este în concordanță cu această matrice [3] ] . $d$ $b$ $2+2+3+3=10$

Metoda de adăugare a vecinilor ca evoluție minimă

Alăturarea vecinilor poate fi considerată un algoritm lacom pentru optimizarea unui arbore în conformitate cu criteriul „evoluției minime echilibrate” [6] (BME). Pentru fiecare topologie, BME definește lungimea arborelui (suma lungimii ramurilor) ca o sumă ponderată a distanțelor de la matricea distanțelor, cu ponderi în funcție de topologia arborelui. Topologia BME optimă este cea pentru care lungimea arborelui este minimă. Metoda de îmbinare a vecinilor la fiecare iterație unește perechea de taxoni care va oferi cea mai mică contribuție la lungimea arborelui construit. Această procedură nu garantează găsirea unui arbore cu o topologie optimă conform criteriului BME; cu toate acestea, deseori găsește un arbore optim sau aproape de optim.

Avantaje și dezavantaje

Principalul avantaj al metodei este că este rapidă, în special, datorită faptului că algoritmul rulează în timp polinomial [5] . Acest lucru îl face potrivit pentru analiza unor volume mari de date (sute sau mii de taxoni) [5] și pentru bootstrap [7] , pentru care utilizarea altor metode de analiză (de exemplu, parcimonie maximă , metoda maximă probabilitate ) este dificilă în termenii numărului de calcule [8] .

Metoda de îmbinare a vecinilor are proprietatea de a produce un arbore corect ca ieșire dacă matricea de distanță corectă este dată ca intrare. În plus, topologia corectă a arborelui este garantată dacă matricea distanțelor este „aproximativ aditivă”, adică dacă fiecare valoare din matricea distanței diferă de distanța reală cu mai puțin de jumătate din lungimea celei mai scurte ramuri a arborelui. [9] .

În practică, matricea distanțelor rar îndeplinește această condiție, dar metoda de îmbinare a vecinilor produce oricum un arbore cu topologia corectă [10] . Adăugarea vecinilor funcționează corect cu o matrice de distanță aproximativ aditivă, deoarece este consistentă statistic pentru multe modele evolutive; având în vedere o intrare de o lungime adecvată, metoda este foarte probabil să reconstruiască un arbore real. Comparativ cu UPGMA , metoda de îmbinare a vecinilor are avantajul că nu presupune că toate generațiile evoluează în aceeași viteză ( ipoteza ceasului molecular ).

Cu toate acestea, în locul metodei de îmbinare a vecinilor, sunt adesea folosite alte metode filogenetice care nu se bazează pe matricea distanțelor și oferă o precizie mai mare în majoritatea cazurilor [8] .

Implementări și variante

Există multe programe care implementează metoda de alăturare a vecinilor.

RapidNJ și NINJA sunt implementări rapide care de obicei rulează aproximativ ca pătratul numărului de taxoni [11] [12] .

BIONJ și Weighbor sunt variante ale metodei de îmbinare care îi îmbunătățesc acuratețea prin exploatarea faptului că distanțele mai mici din matricea distanțelor sunt de obicei mai bine înțelese decât cele mai mari [13] [14] .

FastME este o implementare a unei metode strâns legate de evoluție minimă echilibrată [15] .

Vezi și

clustering genetic uman
Căutarea celui mai apropiat vecin
UPGMA

Note

↑ Saitou. Muzeul Kyushu. 2002. 2 februarie 2007 Arhivat din original la 6 septembrie 2013.
↑ Burlak S. A., Starostin S. A. Lingvistică istorică comparată. - Ed. a II-a - Moscova, 2005. - S. 270-271.
↑ 1 2 Saitou N., Nei M. Metoda de îmbinare a vecinilor : o nouă metodă de reconstrucție a arborilor filogenetici // Biologie moleculară și evoluție : jurnal. - Oxford University Press , 1987. - Vol. 4 , nr. 4 . - P. 406-425 . — PMID 447015 .
↑ Xavier Didelot. Analiza bazată pe secvențe a structurilor populației bacteriene // Genetica populației bacteriene în bolile infecțioase (engleză) / Robinson D. Ashley, Falush Daniel, Feil Edward J.. - John Wiley and Sons , 2010. - P. 46-47. - ISBN 978-0-470-42474-2 .
↑ 1 2 3 4 5 6 7 Studier JA, Keppler KJ O notă despre algoritmul Neighbor-Joining al lui Saitou și Nei // Biologie moleculară și evoluție : jurnal. - Oxford University Press , 1988. - Vol. 5 , nr. 6 . - P. 729-731 . — PMID 3221794 .
↑ Gascuel O., Steel M. Neighbor-joining a dezvăluit // Biologie moleculară și evoluție : jurnal. - Oxford University Press , 2006. - Vol. 23 , nr. 11 . - P. 1997-2000 . - doi : 10.1093/molbev/msl072 . — PMID 16877499 .
↑ Holmes S. Bootstrapping Phylogenetic Trees : Theory and Methods // Statistical Science : jurnal. - 2003. - Vol. 18 , nr. 2 . - P. 241-255 .
↑ 1 2 Penny D., Hendy MD, Steel M . Progrese cu metodele de construire a arborilor evolutivi // Tendințe în ecologie și evoluție : jurnal. - 1992. - Vol. 7 , nr. 3 . - P. 73-79 . - doi : 10.1016/0169-5347(92)90244-6 . — PMID 21235960 .
↑ Atteson K. (1997). „Performanța algoritmilor de îmbinare a vecinilor de reconstrucție a filogeniei”, pp. 101–110. În Jiang, T. și Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlin. COCOON '97.
↑ Mihaescu R., Levy D., Pachter L. Why neighbor-joining works (engleză) // Algorithmica : jurnal. - 2009. - Vol. 54 , nr. 1 . - P. 1-24 . - doi : 10.1007/s00453-007-9116-4 .
↑ Martin Simonsen, Thomas Mailund, Christian N., S. Pedersen. Unirea rapidă a vecinilor (neopr.) // Proceedings of the 8th WABI. - 2008. - T. 5251 . - S. 113-122 . - doi : 10.1007/978-3-540-87361-7_10 . (link indisponibil)
↑ Martin Simonsen, Thomas Mailund, Christian N.S. Pedersen. Proceedings of the 8th Workshop in Algoritmi in Bioinformatics . - Springer Verlag , 2008. - P. 113-122. - doi : 10.1007/978-3-540-87361-7_10 .
↑ Gascuel O. BIONJ : o versiune îmbunătățită a algoritmului NJ bazată pe un model simplu de date secvențe // Biologie moleculară și evoluție : jurnal. - Oxford University Press , 1997. - Vol. 14 , nr. 7 . - P. 685-695 . - doi : 10.1007/978-3-540-87361-7_10 .
↑ William J. Bruno, Nicholas D. Socci, Aaron L. Halpern. Asocierea ponderată a vecinilor: o abordare bazată pe probabilitate a reconstrucției filogeniei bazate pe distanță // Biologie moleculară și evoluție : jurnal. - Oxford University Press , 2000. - Vol. 17 , nr. 1 . - P. 189-197 .
↑ Desper R., Gascuel O. Algoritmi de reconstrucție a filogeniei rapide și precise bazați pe principiul evoluției minime // Journal of Computational Biology : jurnal. - 2002. - Vol. 9 , nr. 5 . - P. 687-705 .

Link -uri

Metoda de îmbinare a vecinului - manual

Dicționare și enciclopedii	Britannica (online)