Questão:
Os algoritmos de construção de árvore filogenética são diferentes dos algoritmos de agrupamento geral?
Ahmed Abdullah
2019-04-09 10:15:37 UTC
view on stackexchange narkive permalink

Os algoritmos de construção de árvores filogenéticas são diferentes dos algoritmos de agrupamento? Suspeito que a resposta seja não.

É claro que a construção de árvores filogenéticas usa conhecimento biológico, por exemplo, métricas de distância especiais, mas traz algo de novo ao algoritmo de agrupamento (por exemplo, hierárquico, união de vizinhos, etc.).

Sim, eles são muito diferentes. Se ninguém mais responder, fornecerei uma perspectiva teórica completa sobre o que está acontecendo.
@Michael G. Ansiosamente esperando por sua resposta. :)
A maior parte da teoria filogenética é baseada na probabilidade de mutações de reversão e isso a distingue drasticamente dos algoritmos de cluster baseados em uma matriz de distância simples
Bem, os algoritmos de construção de árvore baseados em distância são baseados em uma matriz de distância simples.
Dois respostas:
Michael
2019-04-10 22:18:53 UTC
view on stackexchange narkive permalink

O objetivo de uma filogenia é estimar o número "esperado" de mutações entre todos os taxa na análise e seus ancestrais comuns hipotéticos. Uma análise de agrupamento identificará apenas as mutações "observadas" e as mutações "esperadas" e "observadas" podem ser muito diferentes devido ao principal artefato de mutação de reversão. Isso é particularmente verdadeiro para filogenias de nucleotídeos.

A principal diferença entre algoritmos de agrupamento baseados em uma matriz de distância "não corrigida" e a filogenia é que a última é baseada em um modelo explícito para acomodar mutações de reversão. O verdadeiro problema é que existem apenas 4 bases, então, aleatoriamente, há 1/4 de chance de uma mutação em uma determinada posição sofrer mutação de volta para o original, por exemplo A-> C-> A. Diferenças mutacionais observadas = 0, diferenças mutacionais esperadas (reais) = 2. O que preocupa a filogenia é reconstruir esse "2". O problema é significativo porque quase todos os genes têm regiões de mutações rápidas e regiões de mutações baixas.

A principal maneira de fazer isso é por meio da correção de Jukes-Cantor e é fundamental em todas as árvores de nucleotídeos esperadas por "distâncias p". Se a divergência de nucleotídeos for inferior a 75%, então é possível estimar o número esperado de mutações usando o observado por meio da correção JC. Além disso, quando combinada com um método de estimativa da variação da taxa dentro de um gene (geralmente a distribuição gama discreta), a correção JC é muito eficaz na recuperação da "árvore verdadeira". Isso ocorre porque sites homólogos de evolução rápida são agrupados - grande correção via JC, sites de evolução lenta são agrupados - pequena correção via JC. Outras abordagens para melhorar a correção de JC são por meio da identificação do viés entre mutações de purina para purina e mutações de pirimidina para pirimidina e purina para pirimidina.

A importância de JC foi demonstrada por estudos de simulação de 4 táxons ((a, b), (c, d)), se duas linhagens evoluíram muito rapidamente quando as linhagens irmãs evoluem lentamente, um algoritmo de agrupamento relatará que as linhagens rápidas são um grupo irmão, isto é ((b, c), (a, d)). Se o método JC for implementado via máxima verossimilhança (ou Bayesiana), ele recupera corretamente a árvore verdadeira ((a, b), (c, d)). O artefato é conhecido como atração de ramo longo.

Os algoritmos de agrupamento baseados em uma matriz de distância que implementa a correção JC tendem a ter um desempenho ruim para artefatos de atração de ramos longos. Isso não significa que a correção seja inútil, apenas não particularmente poderosa. O problema é que os métodos da matriz de distância não "aderem" ao modelo e o agrupamento introduzirá uma camada de imprecisão. Normalmente, a apresentação de uma matriz de distância "corrigida" combinada com um algoritmo de agrupamento exigirá bootstrapping (reamostragem com substituição) para avaliar se um determinado agrupamento é compatível. Matrizes de distância parametrizadas, usando agrupamento de união de vizinho em conjunto com um bootstrap são consideradas corretas.

O @ user172818 mencionou a parcimônia e este método é considerado menos confiável porque não pode implementar uma correção JC. OMI, é possível que a parcimônia ponderada possa "voltar", mas seria realmente complicado implementar um método de ponderação biológica e exigiria cálculos extensos e independentes.

user172818
2019-04-09 22:14:32 UTC
view on stackexchange narkive permalink

Uma ótima pergunta, embora um pouco ambígua. Não sei a que se referem os "algoritmos gerais de agrupamento". Para sequências biológicas, construir uma árvore pode ser pensado como uma forma de agrupamento. De qualquer forma ...

Existem diferentes algoritmos de construção de árvore. Os algoritmos de parcimônia máxima (MP), probabilidade máxima (ML) e bayesianos tomam diretamente as sequências como entrada. Eles são distintos do agrupamento baseado em distância.

Então, há uma classe de algoritmos baseados em distância em filogenética. Eles partem de uma matriz de distâncias de todos os pares e visam encontrar uma árvore que seja mais compatível com a matriz. Entre eles, UPGMA é basicamente um clustering hierárquico. A união de vizinhos é um tanto semelhante ao agrupamento hierárquico, mas constrói árvores sem raiz. FastME usa uma abordagem muito diferente. Resumidamente, para cada topologia, ele tenta encontrar os melhores comprimentos de ramificação por mínimo quadrado ponderado (para obter detalhes, consulte seu papel); a melhor topologia minimiza o comprimento total dos ramos. FastME encontra a melhor topologia por meio de intercâmbio de vizinho mais próximo (NNI), mais perto de alguns algoritmos de ML (por exemplo, PhyML).

ele traz algo novo no nível de algoritmo de agrupamento?

Pessoalmente, acho que os métodos de construção de árvore baseados na distância são mais sofisticados do que o clustering hierárquico ingênuo, desde que o relacionamento real siga uma topologia de árvore.



Estas perguntas e respostas foram traduzidas automaticamente do idioma inglês.O conteúdo original está disponível em stackexchange, que agradecemos pela licença cc by-sa 4.0 sob a qual é distribuído.
Loading...