Soused se připojil - Neighbor joining

v bioinformatika, soused se připojí je zdola nahoru (aglomerativní) shlukování metoda pro vytvoření fylogenetické stromy, vytvořil Naruya Saitou a Masatoshi Nei v roce 1987.^[1] Obvykle se používá pro stromy založené na DNA nebo protein sekvence data, algoritmus vyžaduje znalost vzdálenosti mezi každou dvojicí taxony (např. druh nebo sekvence) k vytvoření stromu.^[2]

Algoritmus

Počínaje hvězdným stromem (A) se vypočítá matice Q a použije se k výběru dvojice uzlů pro připojení, v tomto případě f a g. Ty jsou spojeny s nově vytvořeným uzlem, u, jak je znázorněno v (B). Část stromu zobrazená jako plné čáry je nyní pevná a v následujících krocích spojování nebude změněna. Vzdálenosti od uzlu u k uzlům a-e se počítají z rovnice (3). Tento proces se poté opakuje s použitím matice pouhých vzdáleností mezi uzly, a, b, c, d, e a u az ní odvozené matice Q. V tomto případě jsou u a e spojeny s nově vytvořeným v, jak je znázorněno na (C). Další dvě iterace vedou nejprve k (D) a poté k (E), kdy je algoritmus hotový, protože strom je plně vyřešen.

Připojení souseda se považuje za vstup a matice vzdálenosti určující vzdálenost mezi každou dvojicí taxonů. Algoritmus začíná zcela nevyřešeným stromem, jehož topologie odpovídá topologii hvězdná síť, a iteruje v následujících krocích, dokud není strom zcela vyřešen a jsou známy všechny délky větví:

1. Na základě aktuální matice vzdálenosti vypočítejte matici ${ displaystyle Q}$ (definováno níže).
2. Najděte pár odlišných taxonů i a j (tj. S ${ displaystyle i neq j}$) pro který ${ displaystyle Q (i, j)}$ má nejnižší hodnotu. Tyto taxony jsou spojeny s nově vytvořeným uzlem, který je připojen k centrálnímu uzlu. Na obrázku vpravo jsou f a g spojena s novým uzlem u.
3. Vypočítejte vzdálenost od každého z taxony v páru k tomuto novému uzlu.
4. Vypočítejte vzdálenost od každého z taxonů mimo tento pár k novému uzlu.
5. Spusťte algoritmus znovu, nahraďte pár spojených sousedů novým uzlem a použijte vzdálenosti vypočítané v předchozím kroku.

Q-matice

Na základě matice vzdálenosti vztahující se k ${ displaystyle n}$ taxony, vypočítat ${ displaystyle Q}$ jak následuje:

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

(1)

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

Vzdálenost od párových členů k novému uzlu

Pro každý z taxonů ve spojovaném páru použijte k výpočtu vzdálenosti k novému uzlu následující vzorec:

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

(2)

a:

${ displaystyle delta (g, u) = d (f, g) - delta (f, u) quad}$

Taxony ${ displaystyle f}$ a ${ displaystyle g}$ jsou spárované taxony a ${ displaystyle u}$ je nově vytvořený uzel. Spojení větví ${ displaystyle f}$ a ${ displaystyle u}$ a ${ displaystyle g}$ a ${ displaystyle u}$a jejich délky, ${ displaystyle delta (f, u)}$ a ${ displaystyle delta (g, u)}$ jsou součástí stromu, který se postupně vytváří; neovlivňují ani nejsou ovlivněny pozdějšími kroky spojování sousedů.

Vzdálenost ostatních taxonů od nového uzlu

Pro každý taxon neuvažovaný v předchozím kroku vypočítáme vzdálenost k novému uzlu následujícím způsobem:

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

(3)

kde ${ displaystyle u}$ je nový uzel, ${ displaystyle k}$ je uzel, do kterého chceme vypočítat vzdálenost do a ${ displaystyle f}$ a ${ displaystyle g}$ jsou členy právě připojeného páru.

Složitost

Soused se připojil k souboru ${ displaystyle n}$ taxa vyžaduje ${ displaystyle n-3}$ iterace. V každém kroku musí člověk vytvořit a hledat a ${ displaystyle Q}$ matice. Zpočátku ${ displaystyle Q}$ matice je velikost ${ displaystyle n krát n}$, pak je další krok ${ displaystyle (n-1) krát (n-1)}$Implementace tohoto přímým způsobem vede k algoritmu s časovou složitostí ${ displaystyle O (n ^ {3})}$;^[3] existují implementace, které používají heuristiku k tomu, aby v průměru dosáhly mnohem lepších výsledků.^[4]

Příklad

Soused se spojil s 5 taxony. V tomto případě 2 kroky připojení souseda dávají strom s plně vyřešenou topologií. Větve výsledného stromu jsou označeny jejich délkami.

Předpokládejme, že máme pět taxonů ${ displaystyle (a, b, c, d, e)}$ a následující matice vzdálenosti ${ displaystyle D}$:

První krok

První připojení

Vypočítáme ${ displaystyle Q_ {1}}$ hodnoty rovnicí (1). Například:

${ displaystyle Q_ {1} (a, b) = (n-2) d (a, b) - součet _ {k = 1} ^ {5} d (a, k) - součet _ {k = 1} ^ {5} d (b, k)}$

${ displaystyle = (5-2) krát 5- (5 + 9 + 9 + 8) - (5 + 10 + 10 + 9) = 15-31-34 = -50}$

Získáváme následující hodnoty pro ${ displaystyle Q_ {1}}$ matice (diagonální prvky matice se zde nepoužívají a jsou zde uvedeny):

Ve výše uvedeném příkladu ${ displaystyle Q_ {1} (a, b) = - 50}$. Toto je nejmenší hodnota ${ displaystyle Q_ {1}}$, takže spojujeme prvky ${ displaystyle a}$ a ${ displaystyle b}$.

Odhad délky první větve

Nechat ${ displaystyle u}$ označit nový uzel. Rovnicí (2), nahoře, větve spojující ${ displaystyle a}$ a ${ displaystyle b}$ na ${ displaystyle u}$ pak mají délky:

${ displaystyle delta (a, u) = { frac {1} {2}} d (a, b) + { frac {1} {2 (5-2)}} vlevo [ sum _ { k = 1} ^ {5} d (a, k) - sum _ {k = 1} ^ {5} d (b, k) right] quad = { frac {5} {2}} + { frac {31-34} {6}} = 2}$

${ displaystyle delta (b, u) = d (a, b) - delta (a, u) quad = 5-2 = 3}$

První aktualizace matice vzdálenosti

Poté pokračujeme v aktualizaci počáteční matice vzdálenosti ${ displaystyle D}$ do nové matice vzdálenosti ${ displaystyle D_ {1}}$ (viz níže), zmenšené o jeden řádek a jeden sloupec kvůli spojení ${ displaystyle a}$ s ${ displaystyle b}$ do svého souseda ${ displaystyle u}$. Pomocí rovnice (3) výše vypočítáme vzdálenost od ${ displaystyle u}$ do každého z ostatních uzlů kromě toho ${ displaystyle a}$ a ${ displaystyle b}$. V tomto případě získáme:

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

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

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

Výsledná matice vzdálenosti ${ displaystyle D_ {1}}$ je:

Tučné hodnoty v ${ displaystyle D_ {1}}$ odpovídají nově vypočítaným vzdálenostem, zatímco kurzívou hodnoty nejsou aktualizací matice ovlivněny, protože odpovídají vzdálenostem mezi prvky, které nebyly zahrnuty do prvního spojení taxonů.

Druhý krok

Druhé připojení

Korespondence ${ displaystyle Q_ {2}}$ matice je:

Můžeme se rozhodnout buď se připojit ${ displaystyle u}$ a ${ displaystyle c}$, nebo se připojit ${ displaystyle d}$ a ${ displaystyle e}$; oba páry mají minimum ${ displaystyle Q_ {2}}$ hodnota ${ displaystyle -28}$a obě volby vedou ke stejnému výsledku. Pro úplnost se připojme ${ displaystyle u}$ a ${ displaystyle c}$ a zavolat nový uzel ${ displaystyle v}$.

Odhad délky druhé větve

Délky spojujících se větví ${ displaystyle u}$ a ${ displaystyle c}$ na ${ displaystyle v}$ lze vypočítat:

${ displaystyle delta (u, v) = { frac {1} {2}} d (u, c) + { frac {1} {2 (4-2)}} vlevo [ sum _ { k = 1} ^ {4} d (u, k) - sum _ {k = 1} ^ {4} d (c, k) right] quad = { frac {7} {2}} + { frac {20-22} {4}} = 3}$

${ Displaystyle delta (c, v) = d (u, c) - delta (u, v) quad = 7-3 = 4}$

Spojení prvků a výpočet délky větve pomáhají nakreslit sousední spojovací strom jak je znázorněno na obrázku.

Aktualizace druhé matice vzdálenosti

Aktualizovaná matice vzdálenosti ${ displaystyle D_ {2}}$ pro zbývající 3 uzly, ${ displaystyle v}$, ${ displaystyle d}$, a ${ displaystyle e}$, je nyní vypočítán:

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

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

Poslední krok

Stromová topologie je v tomto okamžiku plně vyřešena. Pro přehlednost však můžeme vypočítat ${ displaystyle Q_ {3}}$ matice. Například:

${ displaystyle 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}$

Pro úplnost se připojme ${ displaystyle v}$ a ${ displaystyle d}$ a zavolat poslední uzel ${ displaystyle w}$. Lze vypočítat délky tří zbývajících větví:

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

${ Displaystyle delta (w, d) = d (v, d) - delta (v, w) = 4-2 = 2}$

${ Displaystyle delta (w, e) = d (v, e) - delta (v, w) = 3-2 = 1}$

Sousední spojovací strom je nyní kompletní, jak je znázorněno na obrázku.

Závěr: aditivní vzdálenosti

Tento příklad představuje idealizovaný případ: všimněte si, že pokud se přesuneme z kteréhokoli taxonu na jakýkoli jiný podél větví stromu a sečteme délky procházejících větví, výsledek se rovná vzdálenosti mezi těmito taxony ve vstupní matici vzdálenosti. Například jít z ${ displaystyle d}$ na ${ displaystyle b}$ my máme ${ displaystyle 2 + 2 + 3 + 3 = 10}$. Distanční matice, jejíž vzdálenosti tímto způsobem souhlasí s nějakým stromem, se říká „aditivní“, což je v praxi vlastnost, která je vzácná. Je však důležité si uvědomit, že vzhledem k aditivní matici vzdálenosti jako vstupu je zaručeno, že sousední spojení najde strom, jehož vzdálenosti mezi taxony s ním souhlasí.

Soused se připojil jako minimální vývoj

Sousední připojení lze zobrazit jako a chamtivý heurista pro Vyvážená minimální evoluce^[5] (BME) kritérium. Pro každou topologii definuje BME délku stromu (součet délek větví) jako konkrétní vážený součet vzdáleností v matici vzdáleností, přičemž váhy závisí na topologii. Optimální topologie BME je ta, která minimalizuje tuto délku stromu. Soused, který se připojuje na každém kroku, se chamtivě připojuje k této dvojici taxonů, což způsobí největší snížení odhadované délky stromu. Tento postup nezaručuje nalezení optima pro kritérium BME, i když to často dělá a je obvykle docela blízko.

Výhody a nevýhody

Hlavní ctností NJ je, že je rychlý^[6]:466 ve srovnání s nejmenší čtverce, maximální šetrnost a maximální pravděpodobnost metody.^[6]Díky tomu je praktické pro analýzu velkých souborů dat (stovky nebo tisíce taxonů) a pro bootstrapping, pro které účely se používají jiné analytické prostředky (např. maximální šetrnost, maximální pravděpodobnost ) možná výpočetně prohibitivní.

Sousední spojení má tu vlastnost, že pokud je vstupní matice vzdálenosti správná, pak bude výstupní strom správný. Dále je zaručena správnost topologie výstupního stromu, pokud je matice vzdálenosti „téměř aditivní“, konkrétně pokud je každá položka v matice vzdálenosti se liší od skutečné vzdálenosti o méně než polovinu nejkratší délky větve ve stromu.^[7]V praxi distanční matice zřídka splňuje tuto podmínku, ale sousední spojení často stejně vytváří správnou stromovou topologii.^[8] Správnost spojení sousedů pro téměř aditivní matice vzdálenosti znamená, že je statisticky konzistentní podle mnoha modelů evoluce; vzhledem k dostatečné délce dat, připojení sousedů rekonstruuje skutečný strom s vysokou pravděpodobností. ve srovnání s UPGMA a WPGMA, sousední spojení má tu výhodu, že nepředpokládá, že se všechny linie budou vyvíjet stejnou rychlostí (hypotéza molekulárních hodin ).

Přesto je sousedské připojení do značné míry nahrazeno fylogenetickými metodami, které se nespoléhají na měření vzdálenosti a za většiny podmínek nabízejí vynikající přesnost.^{[Citace je zapotřebí ]} Sousední spojení má nežádoucí vlastnost, že některým z větví často přiřazuje záporné délky.

Implementace a varianty

Existuje mnoho programů implementujících připojení sousedů. RapidNJ aNINJA jsou rychlé implementace s typickými dobami chodu úměrnými přibližně druhé mocnině počtu taxonů.BIONJ a We Neighbor jsou varianty spojování sousedů, které zlepšují jeho přesnost využitím skutečnosti, že kratší vzdálenosti v matici vzdáleností jsou obecně lépe známy než delší vzdálenosti. FastME je implementace úzce související metody vyváženého minimálního vývoje.

Viz také

• Hledání nejbližšího souseda
• UPGMA a WPGMA
• Minimální evoluce

Reference

Jiné zdroje

externí odkazy

• Metoda sousedství - výukový program