Metoda sousedského připojení

Metoda spojování sousedů ( v lingvistice „metoda nejbližšího souseda“ [2] ) je bioinformatický a lingvistický algoritmus vyvinutý Naruyou Saitou a Masatoshi Nei v roce 1987 [3] . Jedná se o shlukovou metodu zdola nahoru pro generování fylogenetických stromů . Obvykle se používá pro stromy založené na DNA nebo proteinových sekvencích, v lingvistice - na datech z lexikostatistiky , méně často z fono- nebo morfostatistiky. K jeho realizaci je nutné vypočítat vzdálenosti mezi jednotlivými páry taxonů (například druhy nebo sekvence) [4] .

Algoritmus

Algoritmus začíná zcela nevyřešeným stromem topologie hvězdy [5 ] .

Vypočítá se matice párových vzdáleností mezi taxony .
Na základě aktuální matice vzdálenosti se vypočítá matice - . $Q$
Hledáme pár různých taxonů a (tj. ), pro které je hodnota nejmenší. Tyto taxony jsou připojeny k novému uzlu, který je zase připojen k centrálnímu uzlu. Na obrázku vpravo a připojený k novému uzlu . $i$ $j$ $i \neq j$ $Q(i,j)$ $F$ $G$ $u$
Vypočítá se vzdálenost od každého z připojených taxonů k novému uzlu.
Vypočítá se vzdálenost od každého ze zbývajících taxonů k novému uzlu.
Vytvoříme novou matici párových vzdáleností: z aktuální matice odstraníme řádky a sloupce odpovídající nově přidaným taxonům a přidáme nový vrchol a vzdálenosti vypočítané v bodě 5.
Opakujte kroky 2-5, dokud nebude strom plně vyřešen a nebudou známy délky všech větví.

Q-matice

$Q$ -matice se vypočítá pomocí matice vzdáleností mezi taxony takto [5] : $n$

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

$(jeden)$

kde je vzdálenost mezi taxony a . $d(i,j)$ $i$ $j$

Vzdálenost mezi párem připojených sousedů a novým uzlem

Pro každý z připojených taxonů se pro výpočet vzdáleností k novému uzlu použije následující vzorec:

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

$(2)$

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

Taxony a − pár připojených taxonů a − nový uzel. Větve a jejich délky a jsou nyní pevnou součástí stromu; v dalších krocích algoritmu se nezmění a nic neovlivní [5] . $F$ $G$ $u$ $(f,u)$ $(g,u)$ $\delta(f,u)$ $\delta(g,u)$

Vzdálenost mezi zbývajícími taxony a novým uzlem

Pro každý taxon, který se nezúčastnil předchozího kroku, se vypočítá vzdálenost k novému uzlu [5] :

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

$(3)$

kde je nový uzel, je uzel, ke kterému chceme vypočítat vzdálenost, a jsou taxony nově přidaného páru. $u$ $k$ $F$ $G$

Obtížnost

Metoda sousedského spojení pro taxony vyžaduje iteraci [5] . Při každé iteraci je nutné vypočítat -matici. V prvním kroku je velikost -matice , v dalším kroku atd. Implementace algoritmu bez optimalizace je složitá ; existují implementace, které používají heuristický přístup s průměrně kratší dobou provádění. $n$ $n-3$ $Q$ $Q$ $n\krát n$ $(n-1)\times (n-1)$ $O(n^{3})$

Příklad

Předpokládejme, že máme pět taxonů s následující maticí vzdáleností: $(a,b,c,d,e)$

	A	b	C	d	E
A	0	5	9	9	osm
b	5	0	deset	deset	9
C	9	deset	0	osm	7
d	9	deset	osm	0	3
E	osm	9	7	3	0

Pomocí vzorce (1) vypočítáme -matici (diagonální prvky matice nejsou použity a jsou zde vynechány): $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

Nejmenší hodnota matice je , což znamená, že přidáme taxony a do nového uzlu . Vypočítejte vzdálenosti od a do podle vzorce (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)-\součet _{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

Pomocí vzorce (3) vypočítáme vzdálenosti od nového vrcholu ke zbývajícím vrcholům:

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

Nová matice párových vzdáleností tedy vypadá takto:

	u	C	d	E
u	0	7	7	6
C	7	0	osm	7
d	7	osm	0	3
E	6	7	3	0

Odpovídající matice je: $Q$

	u	C	d	E
u		−28	−24	−24
C	−28		−24	−24
d	−24	−24		−28
E	−24	−24	−28

Nyní naše matice nabývá minimální hodnoty na dvou párech: , a , . Finální fylogenetický strom nezávisí na tom, jaký pár zvolíme. Pro jistotu vyberte a , připojte je k novému uzlu . Stejně jako v první iteraci vypočítáme vzdálenosti od a do . Jsou si rovni a . Vzdálenosti od nového vrcholu ke zbývajícím uzlům a jsou rovné: $u$ $C$ $d$ $E$ $u$ $C$ $proti$ $u$ $C$ $proti$ $\delta(u,v)=3$ $\delta(c,v)=4$ $proti$ $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

Nyní matice párových vzdáleností vypadá takto:

	proti	d	E
proti	0	čtyři	3
d	čtyři	0	3
E	3	3	0

Tím máme plně vyřešený strom. Pro úplnost však stojí za to udělat ještě jednu iteraci:

Q_{3}(v,e)=(3-2)d(v,e)-\součet _{k=1}^{3}d(v,k)-\součet _{k= 1}^{3}d(e,k)=3-7-6=-10

Párová matice vzdálenosti:

	proti	d	E
proti		−10	−10
d	−10		−10
E	−10	−10

Vyberme pár a a vytvořte nový vrchol . Vzdálenosti k tomuto vrcholu od vrcholů , , jsou v tomto pořadí: $proti$ $d$ $w$ $proti$ $d$ $E$

\delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{ k=1}^{3}d(v,k)-\součet _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+ {\frac {7-7}{2}}=2

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

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

Matice sousedství:

	w	proti	d	E
w	0	2	2	jeden
proti	2	0	čtyři	3
d	2	čtyři	0	3
E	jeden	3	3	0

Tak jsme se naučili délky všech větví a dostali jsme kompletní fylogenetický strom znázorněný na obrázku . Výše uvedený příklad je ideální případ: všimněte si, že pokud přejdete z jednoho taxonu do druhého podél větví stromu a sečtete délky projetých větví, výsledek se bude rovnat vzdálenosti mezi taxony v původní matici vzdálenosti . Například přechodem z uzlu do uzlu dostaneme . Matice, ve které jsou vzdálenosti tímto způsobem přiřazeny ke stromu, je považována za aditivní , což je vlastnost, se kterou se v praxi setkáváme jen zřídka. Je však důležité poznamenat, že pokud je jako vstup pro metodu spojování sousedů uvedena aditivní matice vzdáleností, je zaručeno, že v důsledku této metody bude vytvořen strom, který je v souladu s touto maticí [3 ] . $d$ $b$ $2+2+3+3=10$

Metoda sčítání sousedů jako minimální evoluce

Sousední spojování lze považovat za chamtivý algoritmus pro optimalizaci stromu v souladu s kritériem "vyvážené minimální evoluce" [6] (BME). Pro každou topologii BME definuje délku stromu (součet délek větví) jako vážený součet vzdáleností od matice vzdáleností, přičemž váhy závisejí na topologii stromu. Optimální topologie BME je ta, pro kterou je délka stromu minimální. Metoda sousedského spojování při každé iteraci spojuje pár taxonů, které budou mít nejmenší příspěvek k délce budovaného stromu. Tento postup nezaručuje nalezení stromu s topologií, která je optimální podle kritéria BME, nicméně často najde optimální nebo blízko optimální strom.

Výhody a nevýhody

Hlavní výhodou metody je její rychlost, zejména díky tomu, že algoritmus běží v polynomiálním čase [5] . Díky tomu je vhodný pro analýzu velkých objemů dat (stovky nebo tisíce taxonů) [5] a pro bootstrap [7] , pro které je použití jiných analytických metod (např. maximální šetrnost , metoda maximální věrohodnosti ) obtížné. z hlediska počtu výpočtů [8] .

Metoda sousedského spojení má tu vlastnost, že vytváří správný strom jako výstup, pokud je jako vstup uvedena správná matice vzdálenosti. Správná topologie stromu je navíc zaručena, pokud je matice vzdálenosti „přibližně aditivní“, to znamená, pokud se každá hodnota v matici vzdálenosti liší od skutečné vzdálenosti o méně než polovinu délky nejkratší větve stromu. [9] .

V praxi matice vzdálenosti jen zřídka splňuje tuto podmínku, ale metoda sousedského spojení často stejně vytvoří strom se správnou topologií [10] . Sčítání sousedů funguje správně se zhruba aditivní maticí vzdálenosti, protože je statisticky konzistentní pro mnoho evolučních modelů; pokud je zadán vstup o vhodné délce, metoda s vysokou pravděpodobností rekonstruuje skutečný strom. Ve srovnání s UPGMA má metoda sousedského spojování tu výhodu, že nepředpokládá, že se všechny generace vyvíjejí stejnou rychlostí ( hypotéza molekulárních hodin ).

Místo metody sousedského spojování se však často používají jiné fylogenetické metody, které se nespoléhají na matici vzdálenosti a ve většině případů poskytují větší přesnost [8] .

Implementace a varianty

Existuje mnoho programů, které implementují metodu spojování sousedů.

RapidNJ a NINJA jsou rychlé implementace, které obvykle běží zhruba jako druhá mocnina počtu taxonů [11] [12] .

BIONJ a Weighbor jsou varianty metody spojení, které zlepšují její přesnost využitím skutečnosti, že menší vzdálenosti v matici vzdáleností jsou obvykle lépe pochopitelné než ty větší [13] [14] .

FastME je implementace úzce související metody vyvážené minimální evoluce [15] .

Viz také

lidské genetické shlukování
Hledání nejbližšího souseda
UPGMA

Poznámky

↑ Saitou. Muzeum Kjúšú. 2002. 2. února 2007 Archivováno z originálu 6. září 2013.
↑ Burlak S. A., Starostin S. A. Srovnávací historická lingvistika. - 2. vyd. - Moskva, 2005. - S. 270-271.
↑ 1 2 Saitou N., Nei M. Metoda sousedského spojení : nová metoda pro rekonstrukci fylogenetických stromů // Molekulární biologie a evoluce : deník. - Oxford University Press , 1987. - Sv. 4 , ne. 4 . - str. 406-425 . — PMID 447015 .
↑ Xavier Didelot. Sekvenční analýza struktur bakteriální populace // Bakteriální populační genetika při infekčním onemocnění (anglicky) / 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 Poznámka k algoritmu sousedství Saitou a Nei // Molekulární biologie a evoluce : deník. - Oxford University Press , 1988. - Sv. 5 , č. 6 . - str. 729-731 . — PMID 3221794 .
↑ Gascuel O., Steel M. Spojení sousedů odhaleno // Molekulární biologie a evoluce : deník. - Oxford University Press , 2006. - Sv. 23 , č. 11 . - S. 1997-2000 . - doi : 10.1093/molbev/msl072 . — PMID 16877499 .
↑ Holmes S. Bootstrapping Fylogenetické stromy : Teorie a metody // Statistická věda : deník. - 2003. - Sv. 18 , č. 2 . - str. 241-255 .
↑ 1 2 Penny D., Hendy MD, Steel M . Pokrok s metodami pro konstrukci evolučních stromů // Trendy v ekologii a evoluci : deník. - 1992. - Sv. 7 , č. 3 . - str. 73-79 . - doi : 10.1016/0169-5347(92)90244-6 . — PMID 21235960 .
↑ Atteson K. (1997). „Výkon algoritmů pro rekonstrukci fylogeneze pro spojování sousedů“, s. 101–110. V Jiang, T. a Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlín. COCOON '97.
↑ Mihaescu R., Levy D., Pachter L. Proč funguje sousedské spojení (anglicky) // Algorithmica : deník. - 2009. - Sv. 54 , č. 1 . - str. 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 . (nedostupný odkaz)
↑ Martin Simonsen, Thomas Mailund, Christian N.S. Pedersen. Sborník příspěvků z 8. workshopu z Algoritmů v bioinformatice . - Springer Verlag , 2008. - S. 113-122. - doi : 10.1007/978-3-540-87361-7_10 .
↑ Gascuel O. BIONJ : vylepšená verze NJ algoritmu založená na jednoduchém modelu sekvenčních dat // Molekulární biologie a evoluce : deník. - Oxford University Press , 1997. - Sv. 14 , č. 7 . - str. 685-695 . - doi : 10.1007/978-3-540-87361-7_10 .
↑ William J. Bruno, Nicholas D. Socci, Aaron L. Halpern. Spojení váženého souseda: Pravděpodobně založený přístup k rekonstrukci fylogeneze na základě vzdálenosti // Molekulární biologie a evoluce : deník. - Oxford University Press , 2000. - Sv. 17 , č. 1 . - str. 189-197 .
↑ Desper R., Gascuel O. Rychlé a přesné algoritmy rekonstrukce fylogeneze založené na principu minimální evoluce // Journal of Computational Biology : deník. - 2002. - Sv. 9 , č. 5 . - S. 687-705 .

Odkazy

Metoda sousedství – manuál

Slovníky a encyklopedie	Britannica (online)