Ingresso do vizinho

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Em bioinformática , a junção de vizinhos é um método de agrupamento de baixo para cima (aglomerativo) para a criação de árvores filogenéticas , criado por Naruya Saitou e Masatoshi Nei em 1987. [1] Normalmente usado para árvores baseadas em dados de sequência de DNA ou proteínas , o algoritmo requer conhecimento da distância entre cada par de táxons (por exemplo, espécies ou sequências) para formar a árvore. [2]

O algoritmo

Começando com uma árvore estrela (A), a matriz Q é calculada e usada para escolher um par de nós para junção, neste caso f e g. Estes são unidos a um nó recém-criado, u, conforme mostrado em (B). A parte da árvore mostrada como linhas sólidas agora está fixa e não será alterada nas etapas de junção subsequentes. As distâncias do nó u aos nós ae são calculadas a partir da equação ( 3 ). Este processo é então repetido, usando uma matriz apenas das distâncias entre os nós, a,b,c,d,e, eu, e uma matriz Q derivada dela. Neste caso u e e são unidos ao v recém-criado, como mostrado em (C). Mais duas iterações levam primeiro a (D) e depois a (E), ponto em que o algoritmo é concluído, pois a árvore está totalmente resolvida.

A junção de vizinhos recebe como entrada uma matriz de distância especificando a distância entre cada par de táxons. O algoritmo começa com uma árvore completamente não resolvida, cuja topologia corresponde à de uma rede em estrela , e itera nos seguintes passos até que a árvore esteja completamente resolvida e todos os comprimentos dos ramos sejam conhecidos:

  1. Com base na matriz de distância atual, calcule a matriz(definido abaixo).
  2. Encontre o par de taxa distintos i e j (ou seja, com) para qualtem seu menor valor. Esses táxons são unidos a um nó recém-criado, que é conectado ao nó central. Na figura à direita, f e g estão ligados ao novo nó u.
  3. Calcule a distância de cada um dos táxons do par até este novo nó.
  4. Calcule a distância de cada um dos táxons fora desse par até o novo nó.
  5. Inicie o algoritmo novamente, 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ância que relaciona otaxa, calculardo seguinte modo:

 

 

 

 

( 1 )

Ondeé a distância entre os taxae.

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

Para cada um dos táxons do par que está sendo unido, use a seguinte fórmula para calcular a distância até o novo nó:

 

 

 

 

( 2 )

e:

Taxaesão os táxons pareados eé o nó recém-criado. Os ramos que se unemeee, e seus comprimentos,efazem parte da árvore que vai sendo criada aos poucos; eles não afetam nem são afetados por etapas posteriores de junção de vizinhos.

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:

 

 

 

 

( 3 )

Ondeé o novo nó,é o nó para o qual queremos calcular a distância eesão os membros do par que acabou de se juntar.

Complexidade

Vizinho que se junta a um conjunto de taxa exigeiterações. A cada passo é preciso construir e pesquisar ummatriz. Inicialmente omatriz é tamanho, então o próximo passo é, etc. Implementar isso de maneira direta leva a um algoritmo com uma complexidade de tempo de; [3] existem implementações que usam heurísticas para fazer muito melhor do que isso em média. [4]

Exemplo

Vizinho juntando com 5 táxons. Nesse caso, 2 etapas de junção de vizinhos fornecem uma árvore com topologia totalmente resolvida. Os ramos da árvore resultante são rotulados com seus comprimentos.

Suponhamos que temos cinco táxonse a seguinte matriz de distância:

uma b c d e
uma 0 5 9 9 8
b 5 0 10 10 9
c 9 10 0 8 7
d 9 10 8 0 3
e 8 9 7 3 0

Primeiro passo

Primeiro ingresso

Nós calculamos ovalores pela equação ( 1 ). Por exemplo:

Obtemos os seguintes valores para omatriz (os elementos diagonais da matriz não são usados ​​e são omitidos aqui):

uma b c d e
uma −50 −38 −34 −34
b −50 −38 −34 −34
c −38 −38 −40 −40
d −34 −34 −40 −48
e −34 −34 −40 −48

No exemplo acima,. Este é o menor valor de, então juntamos elementose.

Estimativa do comprimento da primeira ramificação

Deixardenotar o novo nó. Pela equação ( 2 ), acima, os ramos que unem eparaentão tem comprimentos:

Primeira atualização da matriz de distância

Em seguida, procedemos à atualização da matriz de distância inicialem uma nova matriz de distância(veja abaixo), reduzido em tamanho em uma linha e uma coluna por causa da junção decomem seu vizinho. Usando a equação ( 3 ) acima, calculamos a distância depara cada um dos outros nós aléme. Neste caso, obtemos:

A matriz de distância resultanteé:

você c d e
você 0 7 7 6
c 7 0 8 7
d 7 8 0 3
e 6 7 3 0

Valores em negritocorrespondem às distâncias recém-calculadas, enquanto os valores em itálico não são afetados pela atualização da matriz, pois correspondem a distâncias entre elementos não envolvidos na primeira junção dos táxons.

Segundo passo

Segunda entrada

O correspondentematriz é:

você c d e
você −28 −24 −24
c −28 −24 −24
d −24 −24 −28
e −24 −24 −28

Podemos optar por aderire, ou para participare; ambos os pares têm o mínimovalor de, e qualquer uma das escolhas leva ao mesmo resultado. Para concretude, juntemosee chame o novo nó.

Estimativa do comprimento do segundo ramo

Os comprimentos dos ramos que se unem eparapode ser calculado:

A junção dos elementos e o cálculo do comprimento do ramo auxiliam no desenho da árvore de junção vizinha conforme mostrado na figura .

Atualização da segunda matriz de distância

A matriz de distância atualizadapara os 3 nós restantes,,, e, agora é calculado:

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

Etapa final

A topologia de árvore está totalmente resolvida neste ponto. No entanto, para maior clareza, podemos calcular omatriz. Por exemplo:

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

Para concretude, juntemosee chame o último nó. Os comprimentos dos três ramos restantes podem ser calculados:

A árvore de junção vizinha agora está completa, conforme mostrado na figura .

Conclusão: distâncias aditivas

Este exemplo representa um caso idealizado: observe que se movermos de qualquer 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âncias de entrada. Por exemplo, indo deparatemos. Uma matriz de distâncias cujas distâncias concordam desta forma com alguma árvore é dita 'aditiva', uma propriedade que é rara na prática. No entanto, é importante notar que, dada uma matriz de distância aditiva como entrada, a junção de vizinhos é garantida para encontrar a árvore cujas distâncias entre táxons concordam com ela.

Vizinho se juntando como evolução mínima

A junção de vizinhos pode ser vista como uma heurística gulosa para o critério Balanced Minimum Evolution [5] (BME). Para cada topologia, o BME define o comprimento da árvore (soma dos comprimentos dos ramos) para ser uma determinada soma ponderada das distâncias na matriz de distâncias, com os pesos dependendo da topologia. A topologia ótima do BME é aquela que minimiza este comprimento de árvore. O vizinho que se junta a cada passo junta-se avidamente ao par de táxons que dará a maior diminuição no comprimento estimado da árvore. Este procedimento não garante encontrar o ótimo para o critério BME, embora muitas vezes o faça e seja geralmente bastante próximo.

Vantagens e desvantagens

A principal virtude do NJ é que ele é rápido [6] : 466  em comparação com os métodos de mínimos quadrados , máxima parcimônia e máxima verossimilhança . [6] Isso torna prático para analisar grandes conjuntos de dados (centenas ou milhares de taxa) 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.

A junção de vizinhos tem a propriedade de que, se a matriz de distância de entrada estiver correta, a árvore de saída estará correta. Além disso, a correção da topologia da árvore de saída é garantida desde que a matriz de distância seja 'quase aditiva', especificamente se cada entrada na matriz de distância difere da distância real por menos da metade do comprimento do ramo mais curto na árvore. [7] Na prática, a matriz de distância raramente satisfaz essa condição, mas a junção de vizinhos geralmente constrói a topologia de árvore correta de qualquer maneira. [8] A exatidão da junção de vizinhos para matrizes de distância quase aditivas implica que é estatisticamente consistentesob muitos modelos de evolução; dados dados de tamanho suficiente, a junção de vizinhos reconstruirá a árvore verdadeira com alta probabilidade. Comparado com UPGMA e WPGMA , a junção de vizinhos tem a vantagem de não assumir que todas as linhagens evoluem na mesma taxa ( hipótese do relógio molecular ).

No entanto, a junção de vizinhos foi amplamente substituída por métodos filogenéticos que não dependem de medidas de distância e oferecem precisão superior na maioria das condições. [ citação necessária ] A junção de vizinhos tem a característica indesejável que muitas vezes atribui comprimentos negativos a alguns dos ramos.

Implementações e variantes

Existem muitos programas disponíveis que implementam a junção de vizinhos. RapidNJ e NINJA são implementações rápidas com tempos de execução típicos proporcionais a aproximadamente o quadrado do número de táxons. BIONJ e Weighbor são variantes de junção de vizinhos que melhoram sua precisão, fazendo uso do fato de que as distâncias mais curtas na matriz de distância são geralmente mais conhecidas do que as distâncias mais longas. FastME é uma implementação do método de evolução mínima balanceada intimamente relacionado.

Veja também

Referências

  1. ^ Saitou, N.; Nei, M. (1 de julho de 1987). "O método de junção de vizinhos: um novo método para reconstruir árvores filogenéticas" . Biologia Molecular e Evolução . 4 (4): 406-425. doi : 10.1093/oxfordjournals.molbev.a040454 . PMID  3447015 .
  2. ^ Xavier Didelot (2010). "Análise baseada em sequências de estruturas populacionais bacterianas" . Em D. Ashley Robinson; Daniel Falush; Edward J. Feil (eds.). Genética de Populações Bacterianas em Doenças Infecciosas . John Wiley e Filhos. págs. 46–47. ISBN  978-0-470-42474-2.
  3. ^ Estudante, JA; Keppler, KJ (novembro de 1988). "Uma nota sobre o algoritmo de junção de vizinhos de Saitou e Nei" . Biologia Molecular e Evolução . 5 (6): 729–31. doi : 10.1093/oxfordjournals.molbev.a040527 . ISSN 1537-1719 . PMID 3221794 .  
  4. ^ Mailund, Thomas; Brodal, GerthS; Fagerberg, Rolf; Pedersen, ChristianNS; Phillips, Derek (2006). "Recriando o método de junção de vizinhos" . BMC Bioinformática . 7 (1): 29. doi : 10.1186/1471-2105-7-29 . PMC 3271233 . PMID 16423304 .  
  5. ^ Gascuel O, Aço M (2006). "Juntar-se ao vizinho revelado" . Mol Biol Evol . 23 (11): 1997-2000. doi : 10.1093/molbev/msl072 . PMID 16877499 . 
  6. ^ a b Kuhner, MK; Felsenstein, J. (1994-05-01). "Uma comparação de simulação de algoritmos de filogenia sob taxas evolutivas iguais e desiguais" . Biologia Molecular e Evolução . 11 (3): 459–468. doi : 10.1093/oxfordjournals.molbev.a040126 . ISSN 0737-4038 . PMID 8015439 .  
  7. ^ Atteson K (1997). "O desempenho de algoritmos de junção de vizinhos de reconstrução de filogenia", pp. 101–110. Em Jiang, T., e Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlim. COCOON '97.
  8. ^ Mihaescu R, Levy D, Pachter L (2009). "Por que a união de vizinhos funciona". Algoritmica . 54 (1): 1–24. arXiv : cs/0602041 . doi : 10.1007/s00453-007-9116-4 . S2CID 2462145 . {{cite journal}}: CS1 maint: vários nomes: lista de autores ( link )

Outras fontes

Links externos