Soused se připojuje - Neighbor joining

V bioinformatiky , soused spojování je zdola nahoru (aglomerativní) shlukování metoda pro vytvoření fylogenetických stromů , vytvořený Naruya Saitou a Masatoshi Nei v roce 1987. Obvykle se používá pro stromy na bázi DNA nebo proteinové sekvence dat, algoritmus vyžaduje znalost vzdálenost mezi každým párem taxonů (např. druhů nebo sekvencí) za vzniku stromu.

Algoritmus

Počínaje stromem hvězd (A) se vypočítá matice Q a použije se k výběru dvojice uzlů pro spojení, v tomto případě f a g. Ty jsou připojeny k nově vytvořenému uzlu, 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 ae jsou vypočítány z rovnice ( 3 ). Tento proces se poté opakuje pomocí matice pouze vzdáleností mezi uzly a, b, c, d, e a u az ní odvozené matice Q. V tomto případě jsou u a e připojeny k nově vytvořenému v, jak je znázorněno na (C). Další dvě iterace vedou nejprve k (D) a poté k (E), v tomto okamžiku je algoritmus hotový, protože strom je plně vyřešen.

Spojování sousedů bere jako vstup matici vzdálenosti určující vzdálenost mezi každým párem taxonů. Algoritmus začíná zcela nevyřešeným stromem, jehož topologie odpovídá hvězdicové síti , a opakuje následující kroky, dokud není strom zcela vyřešen a nejsou známy všechny délky větví:

1. Na základě aktuální matice vzdálenosti vypočítejte matici (definovanou níže).${\ displaystyle Q}$
2. Najděte pár odlišných taxonů i a j (tj. S ), pro které má nejnižší hodnotu. Tyto taxony jsou připojeny k nově vytvořenému uzlu, který je připojen k centrálnímu uzlu. Na obrázku vpravo jsou f a g spojeny s novým uzlem u.${\ Displaystyle i \ neq j}$${\ displaystyle Q (i, j)}$
3. Vypočítejte vzdálenost od každého z taxonů 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. Znovu spusťte algoritmus, nahraďte dvojici spojených sousedů novým uzlem a použijte vzdálenosti vypočítané v předchozím kroku.

Matice Q

Na základě distanční matice související s taxony vypočítejte takto: ${\ displaystyle n}$${\ displaystyle Q}$

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

( 1 )

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

Vzdálenost od členů páru k novému uzlu

Pro každý taxon v páru, který se spojuje, použijte následující vzorec pro výpočet vzdálenosti k novému uzlu:

${\ Displaystyle \ 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}$

( 2 )

a:

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

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

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 je nový uzel, je uzel, ke kterému chceme vypočítat vzdálenost a jsou členy právě připojeného páru. ${\ displaystyle u}$${\ displaystyle k}$${\ displaystyle f}$${\ displaystyle g}$

Složitost

Sousední připojení k sadě taxonů vyžaduje iterace. V každém kroku je třeba vytvořit a hledat matici. Zpočátku je matice velikost , pak je to další krok atd. Implementace této přímočaré cesty vede k algoritmu s časovou složitostí ; existují implementace, které pomocí heuristiky dosahují v průměru mnohem lepších výsledků. ${\ displaystyle n}$${\ displaystyle n-3}$${\ displaystyle Q}$${\ displaystyle Q}$${\ displaystyle n \ times n}$${\ Displaystyle (n-1) \ times (n-1)}$${\ displaystyle O (n^{3})}$

Příklad

Sousední spojení s 5 taxony. V tomto případě 2 kroky spojování sousedů poskytnou 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ů a následující matici vzdáleností : ${\ Displaystyle (a, b, c, d, e)}$${\ displaystyle D}$

První krok

První připojení

Hodnoty vypočítáme rovnicí ( 1 ). Například: ${\ displaystyle Q_ {1}}$

${\ Displaystyle Q_ {1} (a, b) = (n-2) d (a, b)-\ sum _ {k = 1}^{5} d (a, k)-\ sum _ {k = 1}^{5} d (b, k)}$

${\ Displaystyle = (5-2) \ times 5- (5+9+9+8)-(5+10+10+9) = 15-31-34 = -50}$

Pro matici získáme následující hodnoty (diagonální prvky matice nejsou použity a zde jsou vynechány): ${\ displaystyle Q_ {1}}$

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

Odhad první větve

Nechť značí nový uzel. Podle rovnice ( 2 ), výše, větve spojení a aby pak mají délky: ${\ displaystyle u}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle u}$

${\ Displaystyle \ 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}$

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

První aktualizace matice vzdálenosti

Poté přistoupíme k aktualizaci počáteční matice vzdálenosti na novou matici vzdáleností (viz níže), zmenšenou o jeden řádek a jeden sloupec kvůli spojení s do jejich souseda . Pomocí výše uvedené rovnice ( 3 ) vypočítáme vzdálenost od každého dalšího uzlu kromě a . V tomto případě získáme: ${\ displaystyle D}$${\ displaystyle D_ {1}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle u}$${\ displaystyle u}$${\ displaystyle a}$${\ displaystyle b}$

${\ 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 je: ${\ displaystyle D_ {1}}$

Tučné hodnoty 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é se netýkají prvního spojování taxonů. ${\ displaystyle D_ {1}}$

Druhý krok

Druhé připojení

Odpovídající matice je: ${\ displaystyle Q_ {2}}$

Můžeme se rozhodnout buď se připojit a , nebo se připojit a ; oba páry mají minimální hodnotu a každá volba vede ke stejnému výsledku. Pro konkrétnost, spojme a a volat nový uzel . ${\ displaystyle u}$${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle e}$${\ displaystyle Q_ {2}}$${\ displaystyle -28}$${\ displaystyle u}$${\ displaystyle c}$${\ displaystyle v}$

Odhad délky druhé větve

Délky spojování větví a do lze vypočítat: ${\ displaystyle u}$${\ displaystyle c}$${\ displaystyle v}$

${\ Displaystyle \ delta (u, v) = {\ frac {1} {2}} d (u, c)+{\ frac {1} {2 (4-2)}} \ left [\ 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í strom, jak ukazuje obrázek .

Aktualizace matice druhé vzdálenosti

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

${\ 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

V tomto bodě je topologie stromu plně vyřešena. Pro přehlednost však můžeme matici vypočítat . Například: ${\ displaystyle Q_ {3}}$

${\ Displaystyle 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}$

Pro konkrétnost, spojme a a zavolat na poslední uzel . Délky tří zbývajících větví lze vypočítat: ${\ displaystyle v}$${\ displaystyle d}$${\ displaystyle w}$

${\ Displaystyle \ 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}$

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

Strom spojování sousedů je nyní dokončen, jak ukazuje obrázek .

Závěr: aditivní vzdálenosti

Tento příklad představuje idealizovaný případ: všimněte si, že pokud se přesuneme z jakéhokoli taxonu do jiného podél větví stromu a sečteme délky větví, které jsme prošli, výsledek se rovná vzdálenosti mezi těmito taxony ve vstupní matici vzdáleností. Například jít od do máme . Matice vzdáleností, jejíž vzdálenosti se tímto způsobem shodují s nějakým stromem, se říká „aditivní“, což je vlastnost, která je v praxi vzácná. Je však důležité si uvědomit, že vzhledem k tomu, že jako vstup je použita aditivní matice vzdáleností, sousední spojení zaručeně najde strom, jehož vzdálenosti mezi taxony s ním souhlasí. ${\ displaystyle d}$${\ displaystyle b}$${\ Displaystyle 2+2+3+3 = 10}$

Připojení sousedů jako minimální evoluce

Připojení ke sousedům může být považováno za chamtivou heuristiku pro kritérium Balanced Minimum Evolution (BME). Pro každou topologii BME definuje 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ž hmotnosti závisí na topologii. Optimální topologie BME je ta, která minimalizuje tuto délku stromu. Sousední spojení v každém kroku se chamtivě připojí k tomuto páru taxonů, což způsobí největší pokles odhadované délky stromu. Tento postup nezaručuje nalezení optima pro kritérium BME, i když často ano a obvykle je docela blízko.

Výhody a nevýhody

Hlavní předností NJ je, že je rychlá ve srovnání s metodami nejmenších čtverců , maximální šetrnosti a maximální pravděpodobnosti . To je praktické pro analýzu velkých datových sad (stovky nebo tisíce taxonů) a pro bootstrapping , pro které mohou být jiné analytické prostředky (např. Maximální šetrnost , maximální pravděpodobnost ) výpočetně prohibitivní.

Spojování sousedů má tu vlastnost, že pokud je matice vstupní vzdálenosti správná, pak bude správný i výstupní strom. Kromě toho je správnost topologie výstupního stromu zaručena, pokud je matice vzdáleností „téměř aditivní“, konkrétně pokud se každý záznam v matici vzdáleností liší od skutečné vzdálenosti o méně než polovinu nejkratší délky větve ve stromu. V praxi distanční matice tuto podmínku splňuje jen zřídka, ale spojování sousedů často stejně vytvoří správnou topologii stromu. Správnost spojování sousedů pro téměř aditivní matice vzdáleností naznačuje, že je statisticky konzistentní v mnoha evolučních modelech; daná data dostatečné délky, spojení sousedů zrekonstruuje skutečný strom s vysokou pravděpodobností. Ve srovnání s UPGMA a WPGMA má sousedské připojení tu výhodu, že nepředpokládá, že by se všechny linie vyvíjely stejnou rychlostí ( hypotéza molekulárních hodin ).

Spojování sousedů však bylo do značné míry nahrazeno fylogenetickými metodami, které nespoléhají na měření vzdálenosti a nabízejí vynikající přesnost za většiny podmínek. Sousední spojování má nežádoucí vlastnost, že některým větvím často přiřazuje záporné délky.

Implementace a varianty

K dispozici je mnoho programů implementujících připojení sousedů. RapidNJ a NINJA jsou rychlé implementace s typickými běhovými časy úměrnými přibližně druhé mocnině počtu taxonů. BIONJ a Weighbor jsou varianty spojování sousedů, které zlepšují jeho přesnost využíváním skutečnosti, že kratší vzdálenosti v matici vzdáleností jsou obecně známější než delší vzdálenosti. FastME je implementací úzce související vyvážené metody minimálního vývoje.

Viz také

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

Reference

Jiné zdroje

externí odkazy

• Metoda spojování sousedů- návod