Domanda:
Gli algoritmi di costruzione di alberi filogenetici sono diversi dagli algoritmi di clustering generali?
Ahmed Abdullah
2019-04-09 10:15:37 UTC
view on stackexchange narkive permalink

Gli algoritmi di costruzione di alberi filogenetici sono diversi dagli algoritmi di clustering? Sospetto che la risposta sia no.

Ovviamente la costruzione di alberi filogenetici utilizza conoscenze biologiche, ad esempio metriche di distanza speciali, ma porta qualcosa di nuovo all'algoritmo di clustering (ad esempio gerarchico, unione di vicini ecc.).

Sì, sono molto diversi. Se nessun altro risponde, fornirò una prospettiva teorica completa su ciò che sta accadendo.
@Michael G. Attendo con impazienza la tua risposta. :)
La maggior parte della teoria filogenetica si basa sulla probabilità di mutazioni di reversione e questo la distingue drasticamente dagli algoritmi di cluster basati su una semplice matrice di distanza
Ebbene, gli algoritmi di costruzione di alberi basati sulla distanza si basano su una semplice matrice di distanza.
Due risposte:
Michael
2019-04-10 22:18:53 UTC
view on stackexchange narkive permalink

L'obiettivo di una filogenesi è stimare il numero "previsto" di mutazioni tra tutti i taxa nell'analisi e i loro ipotetici antenati comuni. Un'analisi a grappolo identificherà solo le mutazioni "osservate" e le mutazioni "attese" e "osservate" possono essere notevolmente diverse a causa del principale artefatto della mutazione di reversione. Ciò è particolarmente vero per le filogenesi nucleotidiche.

La differenza fondamentale tra gli algoritmi di clustering basati su una matrice di distanza "non corretta" e la filogenesi è che quest'ultima si basa su un modello esplicito per accogliere mutazioni di reversione. Il vero problema è che ci sono solo 4 basi, quindi casualmente c'è 1/4 di possibilità che una mutazione in una data posizione ritorni all'originale, ad es. A-> C-> A. Differenze mutazionali osservate = 0, differenze mutazionali (reali) attese = 2. Ciò di cui si preoccupa la filogenesi è ricostruire quel "2". Il problema è significativo perché quasi ogni gene ha regioni di mutazioni rapide e regioni di mutazioni basse.

Il modo principale per farlo è tramite la correzione Jukes-Cantor ed è fondamentale in tutti gli alberi nucleotidici che si aspettano "p-distanze". Se la divergenza nucleotidica è inferiore al 75%, è possibile stimare il numero previsto di mutazioni utilizzando l'osservato tramite la correzione JC. Inoltre, se combinata con un metodo per stimare la variazione di velocità all'interno di un gene, (solitamente la distribuzione gamma discreta), la correzione JC è molto efficace nel recuperare il "vero albero". Questo perché i siti omologhi in rapida evoluzione sono raggruppati insieme - grande correzione tramite JC, i siti a lenta evoluzione sono raggruppati insieme - piccola correzione tramite JC. Altri approcci per migliorare la correzione JC sono attraverso l'identificazione del bias tra mutazioni da purina a purina e da pirimidina a pirimidina e mutazioni da purina a pirimidina.

L'importanza di JC è stata dimostrata da studi di simulazione di 4 taxa ((a, b), (c, d)), se due ceppi si sono evoluti molto rapidamente quando le linee gemelle si evolvono lentamente un algoritmo di clustering riporterà che i ceppi veloci sono un gruppo sorella, cioè ((b, c), (a, d)). Se il metodo JC viene implementato tramite la massima verosimiglianza (o bayesiano), ripristina correttamente il vero albero ((a, b), (c, d)). Il manufatto è noto come attrazione del ramo lungo.

Gli algoritmi di clustering basati su una matrice di distanza che implementa la correzione JC, tendono a funzionare male per artefatti di attrazione di rami lunghi. Ciò non significa che la correzione sia inutile, ma non particolarmente potente. Il problema è che i metodi della matrice di distanza non "aderiscono" al modello e il clustering introdurrà uno strato di imprecisione. Normalmente la presentazione di una matrice di distanza "corretta" combinata con un algoritmo di clustering richiederà il bootstrap (ricampionamento con sostituzione) per valutare se un dato cluster è supportato. Le matrici di distanza parametrizzate, che utilizzano il clustering di join adiacenti in combinazione con un bootstrap, sono considerate a posto.

La parsimonia @ user172818 ha menzionato e questo metodo è considerato meno affidabile perché non può implementare una correzione JC. IMO è possibile che la parsimonia ponderata possa fare un "ritorno", ma sarebbe davvero complicato implementare un metodo di ponderazione biologica e richiederebbe calcoli estesi e indipendenti.

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

Una bella domanda, anche se un po 'ambigua. Non so a cosa si riferiscano gli "algoritmi di clustering generale". Per le sequenze biologiche, la costruzione di un albero può essere pensata come un modo per raggrupparsi. Comunque ...

Ci sono diversi algoritmi di costruzione di alberi. La massima parsimonia (MP), la massima probabilità (ML) e gli algoritmi bayesiani prendono direttamente le sequenze come input. Sono distinti dal clustering basato sulla distanza.

Poi c'è una classe di algoritmi basati sulla distanza nella filogenetica. Partono da una matrice di distanza per tutte le coppie e mirano a trovare un albero che sia più compatibile con la matrice. Tra questi, UPGMA è in gran parte un clustering gerarchico. Il Neighbor-join è in qualche modo simile al clustering gerarchico, ma costruisce alberi senza radici. FastME utilizza un approccio molto diverso. In breve, per ciascuna topologia cerca di trovare le migliori lunghezze dei rami in base ai minimi quadrati ponderati (per i dettagli, vedere il suo articolo); la migliore topologia riduce al minimo le lunghezze totali delle diramazioni. FastME trova la topologia migliore tramite il più vicino interscambio (NNI), più vicino ad alcuni algoritmi ML (ad esempio PhyML).

porta qualcosa di nuovo a livello di algoritmo di clustering?

Personalmente, penso che i metodi di costruzione di alberi basati sulla distanza siano più sofisticati del raggruppamento gerarchico ingenuo, a condizione che la relazione reale segua una topologia ad albero.



Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 4.0 con cui è distribuito.
Loading...