Neighbor Append Metode

Nabosammenføjningsmetode ( i lingvistik "nærmeste nabometode" [2] ) er en bioinformatik- og lingvistikalgoritme udviklet af Naruya Saitou og Masatoshi Nei i 1987 [3] . Det er en bottom-up klyngemetode til generering af fylogenetiske træer . Anvendes normalt til træer baseret på DNA- eller proteinsekvenser , i lingvistik - på data fra leksikostatistik , sjældnere fra fono- eller morfostatistik. For at implementere det er det nødvendigt at beregne afstandene mellem hvert par af taxaer (for eksempel arter eller sekvenser) [4] .

Algoritme

Algoritmen starter med et fuldstændigt uløst stjernetopologitræ [5 ] .

Matrixen af parvise afstande mellem taxa beregnes .
Baseret på den aktuelle afstandsmatrix beregnes -matricen . $Q$
Vi leder efter et par forskellige taxa og (dvs. ) for hvilke værdien er den mindste. Disse taxa er knyttet til en ny node, som igen er forbundet med den centrale node. På billedet til højre og knyttet til den nye node . $jeg$ $j$ $i \neq j$ $Q(i,j)$ $f$ $g$ $u$
Afstanden fra hver af de tilknyttede taxaer til den nye knude beregnes.
Afstanden fra hver af de resterende taxa til den nye knude beregnes.
Vi danner en ny matrix af parvise afstande: Fra den nuværende matrix sletter vi rækkerne og kolonnerne, der svarer til de nyligt tilføjede taxa, og tilføjer et nyt toppunkt og afstandene beregnet i punkt 5.
Gentag trin 2-5, indtil træet er helt løst, og længden af alle grene er kendt.

Q-matrix

$Q$ -matrix beregnes af matrixen af afstande mellem taxa som følger [5] : $n$

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

$(en)$

hvor er afstanden mellem taxa og . $d(i,j)$ $jeg$ $j$

Afstanden mellem et par forbundne naboer og den nye node

For hver af de vedhæftede taxaer bruges følgende formel til at beregne afstandene til den nye knude:

$\delta (f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(n-2)}}\venstre[\sum _{ k=1}^{n}d(f,k)-\sum _{k=1}^{n}d(g,k)\right]\quad$

$(2)$

og:

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

Taxa og − et par vedhæftede taxaer og − en ny node. Grenene og og deres længder og er nu en fast del af træet; de vil ikke ændre sig og vil ikke påvirke noget i de næste trin af algoritmen [5] . $f$ $g$ $u$ $(f,u)$ $(g,u)$ $\delta(f,u)$ $\delta(g,u)$

Afstand mellem den resterende taxa og den nye node

For hver taxon, der ikke deltog i det foregående trin, beregnes afstanden til den nye node [5] :

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

$(3)$

hvor er den nye knude, er den knude, som vi ønsker at beregne afstanden til, og er taxaen for det nyligt tilføjede par. $u$ $k$ $f$ $g$

Sværhedsgrad

Nabosammenføjningsmetoden for taxa kræver iteration [5] . Ved hver iteration er det nødvendigt at beregne -matrixen. På det første trin er størrelsen af -matrixen , på det næste trin og så videre. Implementeringen af algoritmen uden optimering har kompleksitet ; der er implementeringer, der bruger en heuristisk tilgang med lavere eksekveringstider i gennemsnit. $n$ $n-3$ $Q$ $Q$ $n\ gange n$ $(n-1)\ gange (n-1)$ $O(n^{3})$

Eksempel

Antag, at vi har fem taxa med følgende afstandsmatrix: $(a,b,c,d,e)$

	-en	b	c	d	e
-en	0	5	9	9	otte
b	5	0	ti	ti	9
c	9	ti	0	otte	7
d	9	ti	otte	0	3
e	otte	9	7	3	0

Ved hjælp af formel (1) beregner vi -matrixen (de diagonale elementer i matrixen bruges ikke og udelades her): $Q$

	-en	b	c	d	e
-en		−50	-38	−34	−34
b	−50		-38	−34	−34
c	-38	-38		−40	−40
d	−34	−34	−40		−48
e	−34	−34	−40	−48

Den mindste værdi af matrixen er , hvilket betyder, at vi tilføjer taxa og til den nye node . Beregn afstandene fra og til ved formel (2) : $Q(a,b)=-50$ $u$ $-en$ $b$ $-en$ $b$ $u$

\delta (a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}\venstre[\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

Ved hjælp af formel (3) beregner vi afstandene fra det nye toppunkt til de resterende toppunkter:

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

Den nye matrix af parvise afstande ser således ud:

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

Den tilsvarende matrix er: $Q$

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

Nu tager vores matrix minimumværdien på to par: , og , . Det endelige fylogenetiske træ afhænger ikke af, hvilket par vi vælger. For at være sikker, vælg og , vedhæft dem til en ny node . Som i den første iteration beregner vi afstandene fra og til . De er ligeværdige og . Afstandene fra det nye toppunkt til de resterende knudepunkter og er lig med: $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

Nu ser matricen af parvise afstande sådan ud:

	v	d	e
v	0	fire	3
d	fire	0	3
e	3	3	0

Dermed har vi et fuldt løst træ. For fuldstændighedens skyld er det dog værd at lave en gentagelse mere:

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

Parvis afstandsmatrix:

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

Lad os vælge et par og oprette et nyt toppunkt . Afstandene til dette toppunkt fra hjørnerne , , er henholdsvis: $v$ $d$ $w$ $v$ $d$ $e$

\delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\venstre[\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

Adjacency matrix:

	w	v	d	e
w	0	2	2	en
v	2	0	fire	3
d	2	fire	0	3
e	en	3	3	0

Således lærte vi længderne af alle grene og fik det komplette fylogenetiske træ vist på figuren . Ovenstående eksempel er et ideelt tilfælde: Bemærk, at hvis du bevæger dig fra en taxa til en anden langs grenene af træet og opsummerer længderne af de passerede grene, vil resultatet være lig med afstanden mellem taxaerne i den oprindelige afstandsmatrix . For eksempel ved at gå fra node til node , får vi . En matrix, hvor afstandene på denne måde matches til et træ, siges at være additiv , en egenskab, man sjældent støder på i praksis. Det er dog vigtigt at bemærke, at hvis en additiv afstandsmatrix er givet som input til metoden til at forbinde naboer, er det garanteret, at der som et resultat af metoden vil blive bygget et træ, der er i overensstemmelse med denne matrix [3 ] . $d$ $b$ $2+2+3+3=10$

Naboadditionsmetode som en minimal udvikling

Nabosammenføjning kan betragtes som en grådig algoritme til at optimere et træ i overensstemmelse med kriteriet om "balanceret minimumsudvikling" [6] (BME). For hver topologi definerer BME trælængden (summen af grenlængder) som en vægtet sum af afstande fra afstandsmatrixen, med vægte afhængigt af trætopologien. Den optimale BME-topologi er den, hvor træets længde er minimal. Nabosammenføjningsmetoden ved hver iteration forbinder det par af taxaer, der vil give det mindste bidrag til længden af træet, der bygges. Denne procedure garanterer ikke at finde et træ med en topologi, der er optimal i henhold til BME-kriteriet, men den finder ofte et optimalt eller tæt på optimalt træ.

Fordele og ulemper

Den største fordel ved metoden er, at den er hurtig, især på grund af det faktum, at algoritmen kører i polynomiel tid [5] . Dette gør det velegnet til analyse af store datamængder (hundrede eller tusinder af taxa) [5] og til bootstrap [7] , hvor det er vanskeligt at bruge andre analysemetoder (f.eks. maximum sparsimony , maximum likelihood-metoden ). i forhold til antallet af beregninger [8] .

Neighbor join-metoden har den egenskab, at den producerer et korrekt træ som output, hvis den korrekte afstandsmatrix er givet som input. Desuden er træets korrekte topologi garanteret, hvis afstandsmatrixen er "tilnærmelsesvis additiv", det vil sige, hvis hver værdi i afstandsmatrixen afviger fra den faktiske afstand med mindre end halvdelen af længden af træets korteste gren [9] .

I praksis opfylder afstandsmatrixen sjældent denne betingelse, men nabosammenføjningsmetoden producerer alligevel ofte et træ med den korrekte topologi [10] . Naboaddition fungerer korrekt med en nogenlunde additiv afstandsmatrix, fordi den er statistisk konsistent for mange evolutionære modeller; givet et input af en passende længde, vil metoden højst sandsynligt rekonstruere et rigtigt træ. Sammenlignet med UPGMA har nabosammenføjningsmetoden den fordel, at den ikke antager, at alle generationer udvikler sig med samme hastighed ( molekylær urhypotese ).

Men i stedet for nabosammenføjningsmetoden bruges ofte andre fylogenetiske metoder, som ikke er afhængige af afstandsmatrixen og giver større nøjagtighed i de fleste tilfælde [8] .

Implementeringer og varianter

Der er mange programmer, der implementerer metoden til at slutte sig til naboer.

RapidNJ og NINJA er hurtige implementeringer, der normalt kører nogenlunde som kvadratet af antallet af taxa [11] [12] .

BIONJ og Weighbor er varianter af sammenføjningsmetoden, der forbedrer dens nøjagtighed ved at udnytte det faktum, at mindre afstande i afstandsmatrixen normalt er bedre forstået end større [13] [14] .

FastME er en implementering af en nært beslægtet metode til afbalanceret minimal evolution [15] .

Se også

human genetisk klyngedannelse
Nærmeste nabosøgning
UPGMA

Noter

↑ Saitou. Kyushu Museum. 2002. 2. februar 2007 Arkiveret fra originalen 6. september 2013.
↑ Burlak S. A., Starostin S. A. Komparativ historisk lingvistik. - 2. udg. - Moskva, 2005. - S. 270-271.
↑ 1 2 Saitou N., Nei M. Nabosammenføjningsmetoden : en ny metode til rekonstruktion af fylogenetiske træer // Molecular Biology and Evolution : journal. - Oxford University Press , 1987. - Vol. 4 , nr. 4 . - S. 406-425 . — PMID 447015 .
↑ Xavier Didelot. Sekvensbaseret analyse af bakteriepopulationsstrukturer // Bakteriel populationsgenetik i infektionssygdomme (engelsk) / Robinson D. Ashley, Falush Daniel, Feil Edward J.. - John Wiley and Sons , 2010. - S. 46-47. - ISBN 978-0-470-42474-2 .
↑ 1 2 3 4 5 6 7 Studier JA, Keppler KJ En note om naboforbindelsesalgoritmen for Saitou og Nei // Molecular Biology and Evolution : journal. - Oxford University Press , 1988. - Vol. 5 , nr. 6 . - s. 729-731 . — PMID 3221794 .
↑ Gascuel O., Steel M. Nabo-tilslutning afsløret // Molekylærbiologi og evolution : journal. - Oxford University Press , 2006. - Vol. 23 , nr. 11 . - S. 1997-2000 . - doi : 10.1093/molbev/msl072 . — PMID 16877499 .
↑ Holmes S. Bootstrapping Phylogenetic Trees : Teori og metoder // Statistical Science : journal. - 2003. - Bd. 18 , nr. 2 . - S. 241-255 .
↑ 1 2 Penny D., Hendy MD, Steel M . Fremskridt med metoder til at konstruere evolutionære træer // Trends in Ecology and Evolution : journal. - 1992. - Bd. 7 , nr. 3 . - S. 73-79 . - doi : 10.1016/0169-5347(92)90244-6 . — PMID 21235960 .
↑ Atteson K. (1997). "Udførelsen af nabosammenføjningsalgoritmer til fylogeni-rekonstruktion", s. 101-110. I Jiang, T., og Lee, D., red., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlin. COCOON '97.
↑ Mihaescu R., Levy D., Pachter L. Why neighbor-joining works (engelsk) // Algorithmica : journal. - 2009. - Bd. 54 , nr. 1 . - S. 1-24 . - doi : 10.1007/s00453-007-9116-4 .
↑ Martin Simonsen, Thomas Mailund, Christian N., S. Pedersen. Rapid Neighbor Joining (neopr.) // Proceedings of the 8th WABI. - 2008. - T. 5251 . - S. 113-122 . - doi : 10.1007/978-3-540-87361-7_10 . (utilgængeligt link)
↑ Martin Simonsen, Thomas Mailund, Christian N.S. Pedersen. Proceedings of the 8th Workshop in Algoritms in Bioinformatics . - Springer Verlag , 2008. - S. 113-122. - doi : 10.1007/978-3-540-87361-7_10 .
↑ Gascuel O. BIONJ : en forbedret version af NJ-algoritmen baseret på en simpel model af sekvensdata // Molecular Biology and Evolution : journal. - Oxford University Press , 1997. - Vol. 14 , nr. 7 . - S. 685-695 . - doi : 10.1007/978-3-540-87361-7_10 .
↑ William J. Bruno, Nicholas D. Socci, Aaron L. Halpern. Vægtet nabo-tilslutning: En sandsynlighedsbaseret tilgang til afstandsbaseret fylogeni-rekonstruktion // Molekylærbiologi og evolution : journal. - Oxford University Press , 2000. - Vol. 17 , nr. 1 . - S. 189-197 .
↑ Desper R., Gascuel O. Hurtige og nøjagtige fylogeniske rekonstruktionsalgoritmer baseret på minimums-evolutionsprincippet // Journal of Computational Biology : journal. - 2002. - Bd. 9 , nr. 5 . - S. 687-705 .

Links

The Neighbor-Joining Method - manual

Ordbøger og encyklopædier	Britannica (online)