Neighbor joining

Em bioinformática, Neighbor joining é um método de agrupamento ascendente (aglomerativo) para criação de árvores filogenéticas, desenvolvido por Naruya Saitou e Masatoshi Nei em 1987. ^[1] Em geral, baseado em dados de sequências de ADN ou proteínas, o algoritmo requer o conhecimento da distância entre cada par de táxons (por exemplo, espécies ou sequências) para construir a árvore filogenética. ^[2]

O algoritmo

Táxon $f$ e $g$ são os táxons pareados e $u$ é o nó recém-criado. Os ramos que se unem $f$ e $u$ e $g$ e $u$ , e seus comprimentos, $δ (f, u)$ e $δ (g, u)$ fazem parte da árvore que a ser criada gradualmente; eles não afetam nem são afetados por etapas posteriores do método de neighbor-joining.

Com base na matriz de distâncias atual, calcular uma matriz $Q$ (definida abaixo).
Identificar o par de táxons distintos i e j (ou seja, com $i \neq j$ ) para o qual $Q (i, j)$ é o menor. Criar um novo nó que una os táxons i e j e conectar o novo nó ao nó central. Por exemplo, na parte (B) da figura à direita, o nó u é criado para unir f e g.
Calcular a distância de cada um dos táxons do par até esse novo nó.
Calcular a distância de cada um dos táxons fora deste par até o novo nó.
Reiniciar o algoritmo, substituindo o par de vizinhos unidos pelo novo nó e usando as distâncias calculadas na etapa anterior.

A matriz Q

Com base em uma matriz de distâncias que relaciona o $n$ taxa, calcule o $n$ x $n$ matriz $Q$ do seguinte modo: Predefinição:Bloco numerado

onde $d (i, j)$ é a distância entre os táxons $i$ e $j$ .

Distância dos membros do par até o novo nó

Para cada um dos táxons no par que está sendo unido, use a seguinte fórmula para calcular a distância até o novo nó: Predefinição:Bloco numerado onde $u$ é o novo nó, $k$ é o nó cuja distância queremos calcular e $f$ e $g$ são os membros do par que acabaram de ser conectados.

δ (g, u) = d (f, g) - δ (f, u)

onde $u$ é o novo nó, $k$ é o nó cuja distância queremos calcular e $f$ e $g$ são os membros do par que acabaram de ser conectados.

Distância dos outros táxons do novo nó

Para cada táxon não considerado na etapa anterior, calculamos a distância até o novo nó da seguinte forma: Predefinição:Bloco numerado onde $u$ é o novo nó, $k$ é o nó cuja distância queremos calcular e $f$ e $g$ são os membros do par acabado de unir.

Complexidade

O método de Neighbor joining num conjunto de $n$ táxons requer $n - 3$ iterações. A cada passo, uma matriz $Q$ é construída. Inicialmente, a matriz $Q$ é de formato $n \times n$ , então no passo seguinte é $(n - 1) \times (n - 1)$ , etc. Implementar isto de forma objetiva origina um algoritmo com uma complexidade temporal de $O (n^{3})$ ;^[3] existem implementações que usam heurística para performar bastante melhor que isto em média.^[4]

Exemplo

Supondo que temos cinco táxons $(a, b, c, d, e)$ e a seguinte matriz de distâncias $D$ :

	a	b	c	e	e
a	0	5	9	9	8
b	5	0	10	10	9
c	9	10	0	8	7
e	9	10	8	0	3
e	8	9	7	3	0

Primeiro passo

Primeira união

Calculamos os valores de $Q_{1}$ com a equação ( Predefinição:EquationNote ). Por exemplo:

Q_{1} (a, b) = (n - 2) d (a, b) - \sum_{k = 1}^{5} d (a, k) - \sum_{k = 1}^{5} d (b, k)

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

Obtivemos os seguintes valores para a matriz $Q_{1}$ (os valores das diagonais da matriz não são usados e são omitidos aqui):

	a	b	c	e	e
a		-50	-38	-34	-34
b	-50		-38	-34	-34
c	-38	-38		-40	-40
e	-34	-34	-40		-48
e	-34	-34	-40	-48

No exemplo acima, $Q_{1} (a, b) = - 50$ . Este é o menor valor de $Q_{1}$ , então juntamos elementos $a$ e $b$ .

Estimativa do comprimento do primeiro ramo

Com $u$ a denotar o novo nó. Pela equação ( Predefinição:EquationNote ), acima, os ramos que unem $a$ e $b$ para $u$ têm então comprimentos:

δ (a, u) = \frac{1}{2} d (a, b) + \frac{1}{2 (5 - 2)} [\sum_{k = 1}^{5} d (a, k) - \sum_{k = 1}^{5} d (b, k)] = \frac{5}{2} + \frac{31 - 34}{6} = 2

δ (b, u) = d (a, b) - δ (a, u) = 5 - 2 = 3

Primeira atualização da matriz de distâncias

Em seguida, procedemos à atualização da matriz de distâncias inicial $D$ numa nova matriz de distâncias $D_{1}$ (veja abaixo), reduzida em tamanho (com menos uma linha e uma coluna) devido à união de $a$ e $b$ ao táxon vizinho $u$ . Usando a equação ( Predefinição:EquationNote ) acima, calculamos a distância de $u$ para cada um dos outros nós além $a$ e $b$ . Neste caso, obtemos:

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

A matriz de distâncias resultante $D_{1}$ é:

	u	c	e	e
u	0	7	7	6
c	7	0	8	7
e	7	8	0	3
e	6	7	3	0

Valores a negrito em $D_{1}$ correspondem às distâncias recém-calculadas, enquanto os valores em itálico não são afetados pela atualização da matriz, pois correspondem às distâncias entre elementos não envolvidos na primeira união de táxons.

Segundo passo

Segunda união

A matriz correspondente $Q_{2}$ é:

	u	c	e	e
u		-28	-24	-24
c	-28		-24	-24
e	-24	-24		-28
e	-24	-24	-28

Podemos escolher entre unir $u$ e $c$ , ou unir $d$ e $e$ ; ambos os pares têm o valor mínimo em $Q_{2}$ de $- 28$ , e ambas as uniões levam ao mesmo resultado. Para sermos concretos, juntemos $u$ e $c$ e chamemos o novo nó $v$ .

Estimativa do comprimento do segundo ramo

Os comprimentos dos ramos que unem $u$ e $c$ a $v$ podem ser calculados:

δ (u, v) = \frac{1}{2} d (u, c) + \frac{1}{2 (4 - 2)} [\sum_{k = 1}^{4} d (u, k) - \sum_{k = 1}^{4} d (c, k)] = \frac{7}{2} + \frac{20 - 22}{4} = 3

δ (c, v) = d (u, c) - δ (u, v) = 7 - 3 = 4

A união dos elementos e o cálculo do comprimento do ramo ajudam a desenhar a árvore de união dos vizinhos, como mostrado na figura.

Atualização da matriz de segunda distância

A matriz de distâncias atualizada $D_{2}$ para os 3 nós restantes, $v$ , $d$ , e $e$ , agora é calculada:

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

	v	e	e
v	0	4	3
e	4	0	3
e	3	3	0

Etapa final

A topologia da árvore está totalmente resolvida neste ponto. No entanto, para maior clareza, podemos calcular a matriz $Q_{3}$ . Por exemplo:

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

	v	e	e
v		-10	-10
e	-10		-10
e	-10	-10

Para sermos concretos, unamos $v$ e $d$ e chamemos o último nó $w$ . Os comprimentos dos três ramos restantes podem ser calculados:

δ (v, w) = \frac{1}{2} d (v, d) + \frac{1}{2 (3 - 2)} [\sum_{k = 1}^{3} d (v, k) - \sum_{k = 1}^{3} d (d, k)] = \frac{4}{2} + \frac{7 - 7}{2} = 2

δ (w, d) = d (v, d) - δ (v, w) = 4 - 2 = 2

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

A árvore de neighbor joining está agora completa, como demonstrado na figura.

Conclusão: distâncias aditivas

Este exemplo representa um caso ideal: observe que, se movermos de um táxon para qualquer outro ao longo dos ramos da árvore e somarmos os comprimentos dos ramos percorridos, o resultado será igual à distância entre esses táxons na matriz de distância de entrada. Por exemplo, indo de $d$ para $b$ nós temos $2 + 2 + 3 + 3 = 10$ . Uma matriz de distância cujas distâncias concordam desta maneira com uma árvore é chamada de "aditiva", uma propriedade rara na prática. No entanto, é importante observar que, dada uma matriz de distância aditiva como entrada, o método de neighbor joining certamente encontrará a árvore cujas distâncias entre táxons concordam com ela.

Neighbor joining como evolução mínima

Neighbor joining pode ser visto como uma heurística gananciosa para o critério de evolução mínima balanceada ^[5] (BME). Para cada topologia, o BME define o comprimento da árvore (soma dos comprimentos dos ramos) como uma soma ponderada particular das distâncias na matriz de distância, com os pesos dependendo da topologia. A topologia ótima do BME é aquela que minimiza o comprimento desta árvore. NJ, a cada passo, une avidamente o par de táxons que proporcionará a maior diminuição no comprimento estimado da árvore. Este método não garante encontrar o ótimo para o critério BME, embora frequentemente o faça e geralmente se aproxime bastante disso. ^[5]

Vantagens e desvantagens

A principal vantagem do método NJ é a sua rapidez Predefinição:Referências múltiplas em comparação com os métodos dos mínimos quadrados, máxima parcimônia e máxima verossimilhança. ^[6] Isso torna-o prático para analisar grandes conjuntos de dados (centenas ou milhares de táxons) e para bootstrapping, para os quais outros meios de análise (por exemplo, máxima parcimônia, máxima verossimilhança) podem ser computacionalmente proibitivos.

Neighbor joining tem a propriedade de que, se a matriz de distâncias de entrada estiver correta, a árvore resultante estará correta. Além disso, a correção da topologia da árvore resultante é garantida desde que a matriz de distâncias seja 'quase aditiva', especificamente se cada entrada na matriz de distâncias diferir da distância real em menos da metade do comprimento do ramo mais curto na árvore. Na prática, a matriz de distâncias raramente satisfaz esta condição, mas o método de Neighbor joining frequentemente constrói a topologia de árvore correta de qualquer forma. ^[7] A precisão do método para matrizes de distâncias quase aditivas implica que este é estatisticamente consistente em muitos modelos de evolução; dados de comprimento suficiente, o método de Neighbor joining reconstruirá a árvore verdadeira com alta probabilidade. Comparado com UPGMA e WPGMA, Neighbor joining tem a vantagem de não assumir que todas as linhagens evoluem na mesma taxa evolutiva (hipótese do relógio molecular).

No entanto, Neighbor joining foi amplamente substituído por métodos filogenéticos que não dependem de medidas de distância e oferecem precisão superior na maioria das condições. ^{[ <span title="This claim needs references to reliable sources. (November 2012)">citação necessária</span> ]} Neighbor joining tem a característica indesejável de frequentemente atribuir comprimentos negativos a alguns dos ramos.

Implementações e variantes

Há muitos programas disponíveis que implementam a união de vizinhos. Entre as implementações de NJ canônico (ou seja, com uso dos critérios clássicos de otimização de NJ, portanto retornando os mesmos resultados), RapidNJ (iniciado em 2003, atualização principal em 2011, ainda atualizado em 2023) ^[8] e NINJA (iniciado em 2009, última atualização em 2013) ^[9] são considerados de última geração. Eles têm tempos de execução típicos proporcionais aproximadamente ao quadrado do número de táxons.

As variantes que se desviam do canônico incluem:

BIONJ (1997) ^[10] e Weighbor (2000), ^[11] que melhoram a precisão através do uso do fato das distâncias mais curtas na matriz de distâncias serem geralmente mais conhecidas do que as distâncias mais longas. Os dois métodos foram estendidos para serem executados em matrizes de distâncias incompletas. ^[12]
"Fast NJ" lembra-se do melhor nó e é sempre O(n^2); "relax NJ" realiza uma busca por escalada e retém a pior complexidade de caso de O(n^3). NJ rápido é mais rápido do que NJ relaxado simples. ^[13]
FastME é uma implementação do método de evolução mínima balanceada (BME) intimamente relacionado (ver [[Neighbor joining#Neighbor joining como evolução mínima]]). É tão rápido e mais preciso que o NJ. Começa com uma árvore bruta e depois melhora-a através de um conjunto de movimentos topológicos, como Rearranjos de Taxón mais próximos (NNI). ^[14] FastTree é um método relacionado. Ele funciona em "perfis" de sequência em vez de uma matriz. Começa com uma árvore aproximadamente NJ, reorganiza-a em BME e, em seguida, reorganiza-a numa máxima verossimilhança aproximada. ^[15]

Ver também

Máxima Parsimônia

Referências

Predefinição:Reflist

Outras fontes

The Neighbor-Joining Method — a tutorial

[1] Predefinição:Citar periódico

[2] Predefinição:Citar livro

[3] Predefinição:Citar periódico

[4] Predefinição:Citar periódico

[gascuel-5] 5,0 ^5,1 Predefinição:Citar periódico

[Kuhner1994-6] Predefinição:Citar periódico

[levy-7] Predefinição:Citar periódico

[8] Predefinição:Citar web

[9] Predefinição:Citar web

[10] Predefinição:Citar web

[11] Predefinição:Citar web

[12] Predefinição:Citar periódico

[13] Predefinição:Citar livro

[14] Predefinição:Citar web

[15] Predefinição:Citar web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Neighbor joining

Índice

O algoritmo

A matriz Q

Distância dos membros do par até o novo nó

Distância dos outros táxons do novo nó

Complexidade

Exemplo

Primeiro passo

Primeira união

Estimativa do comprimento do primeiro ramo

Primeira atualização da matriz de distâncias

Segundo passo

Segunda união

Estimativa do comprimento do segundo ramo

Atualização da matriz de segunda distância

Etapa final

Conclusão: distâncias aditivas

Neighbor joining como evolução mínima

Vantagens e desvantagens

Implementações e variantes

Ver também

Referências

Outras fontes

Menu de navegação

	a	b	c	e	e
a		-50	-38	-34	-34
b	-50		-38	-34	-34
c	-38	-38		-40	-40
e	-34	-34	-40		-48
e	-34	-34	-40	-48

	a	b	c	e	e
a		-50	-38	-34	-34
b	-50		-38	-34	-34
c	-38	-38		-40	-40
e	-34	-34	-40		-48
e	-34	-34	-40	-48

Neighbor joining

O algoritmo

A matriz Q

Distância dos membros do par até o novo nó

Distância dos outros táxons do novo nó

Complexidade

Exemplo

Primeiro passo

Primeira união

Estimativa do comprimento do primeiro ramo

Primeira atualização da matriz de distâncias

Segundo passo

Segunda união

Estimativa do comprimento do segundo ramo

Atualização da matriz de segunda distância

Etapa final

Conclusão: distâncias aditivas

Neighbor joining como evolução mínima

Vantagens e desvantagens

Implementações e variantes

Ver também

Referências

Outras fontes

Menu de navegação

Pesquisa

	a	b	c	e	e
a		-50	-38	-34	-34
b	-50		-38	-34	-34
c	-38	-38		-40	-40
e	-34	-34	-40		-48
e	-34	-34	-40	-48