UPGMA

UPGMA (unweighted pair group method with arithmetic mean) (em português: método de grupo de pares não ponderados com média aritmética) é um método de agrupamento hierárquico aglomerativo (de baixo para cima) simples. Existe também uma variante ponderada, WPGMA, e os dois métodos são geralmente atribuídos a Sokal e Michener.^[1]

Observe-se que ser não ponderado indica que todas as distâncias contribuem igualmente para cada média calculada e não se referindo portanto, à matemática através da qual é obtida. Assim, a média simples no WPGMA produz um resultado ponderado e a média proporcional no UPGMA produz um resultado não ponderado ( veja o exemplo prático ).^[2]

O algoritmo UPGMA constrói uma árvore com raiz ( dendrograma ) que reflete a estrutura presente numa matriz de similaridade de pares (ou uma matriz de dissimilaridade ). Em cada etapa, os dois clusters mais próximos são combinados em um cluster de nível superior. A distância entre quaisquer dois clusters ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle {\mathcal {B}}}$, cada um de tamanho ( ou seja, cardinalidade ) ${\displaystyle {|{\mathcal {A}}|}}$ e ${\displaystyle {|{\mathcal {B}}|}}$, é considerada a média de todas as distâncias ${\displaystyle d(x,y)}$ entre pares de objetos ${\displaystyle x}$ em ${\displaystyle {\mathcal {A}}}$ e ${\displaystyle y}$ em ${\displaystyle {\mathcal {B}}}$, ou seja, a distância média entre os elementos de cada cluster:

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y)}$

Por outras palavras, em cada etapa de agrupamento, a distância atualizada entre os clusters unidos ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}}$ e um novo cluster ${\displaystyle X}$ é dada pela média proporcional das distâncias ${\displaystyle d_{{\mathcal {A}},X}}$ e ${\displaystyle d_{{\mathcal {B}},X}}$:

${\displaystyle d_{({\mathcal {A}}\cup {\mathcal {B}}),X}={\frac {|{\mathcal {A}}|\cdot d_{{\mathcal {A}},X}+|{\mathcal {B}}|\cdot d_{{\mathcal {B}},X}}{|{\mathcal {A}}|+|{\mathcal {B}}|}}}$

O algoritmo UPGMA produz dendrogramas com raiz e assume uma taxa constante, ou seja, assume uma árvore ultramétrica na qual as distâncias da raiz até ao fim de cada ramo são iguais. Quando as pontas são dados moleculares ( ou seja, DNA, RNA e proteína ) amostrados ao mesmo tempo, a suposição de ultrametricidade torna-se equivalente a assumir um relógio molecular.

Este exemplo prático é baseado numa matriz de distâncias genética JC69 calculada a partir do alinhamento da sequência de RNA ribossômico 5S de cinco bactérias: Bacillus subtilis ( ${\displaystyle a}$ ), Bacillus stearothermophilus ( ${\displaystyle b}$ ), Lactobacillus viridescens ( ${\displaystyle c}$ ), Acholeplasma modicum ( ${\displaystyle d}$ ) e Micrococcus luteus ( ${\displaystyle e}$ ).^[3][4]

• Primeiro agrupamento

Assumindo que temos cinco elementos ${\displaystyle (a,b,c,d,e)}$ e a seguinte matriz ${\displaystyle D_{1}}$ de distâncias em pares entre eles:

Neste exemplo, ${\displaystyle D_{1}(a,b)=17}$ é o menor valor de ${\displaystyle D_{1}}$, então juntamos os elementos ${\displaystyle a}$ e ${\displaystyle b}$ .

• Estimativa do comprimento do primeiro ramo

De ressaltar que ${\displaystyle u}$ denota o nó ao qual ${\displaystyle a}$ e ${\displaystyle b}$ estão agora conectados. Com ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ é garantido que os elementos ${\displaystyle a}$ e ${\displaystyle b}$ são equidistantes de ${\displaystyle u}$ . Isto corresponde à expectativa da hipótese de ultrametricidade. Os ramos que unem ${\displaystyle a}$ e ${\displaystyle b}$ a ${\displaystyle u}$ têm então comprimentos ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$ ( veja o dendrograma final )

• Primeira atualização da matriz de distâncias

Em seguida, procedemos à atualização da matriz de distâncias inicial ${\displaystyle D_{1}}$ para uma nova matriz de distância ${\displaystyle D_{2}}$ (veja abaixo), reduzida em tamanho por uma linha e uma coluna devido ao agrupamento de ${\displaystyle a}$ com ${\displaystyle b}$ . Valores em negrito em ${\displaystyle D_{2}}$ correspondem às novas distâncias, calculadas pela média das distâncias entre cada elemento do primeiro par ${\displaystyle (a,b)}$ e cada um dos elementos restantes:

${\displaystyle D_{2}((a,b),c)=(D_{1}(a,c)\times 1+D_{1}(b,c)\times 1)/(1+1)=(21+30)/2=25.5}$

${\displaystyle D_{2}((a,b),d)=(D_{1}(a,d)+D_{1}(b,d))/2=(31+34)/2=32.5}$

${\displaystyle D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e))/2=(23+21)/2=22}$

Valores em itálico em ${\displaystyle D_{2}}$ não são afetados pela atualização da matriz, já que correspondem a distâncias entre elementos não envolvidos no primeiro cluster.

• Segundo agrupamento

Os três passos anteriores são então repetidos, começando agora com a nova matriz de distâncias ${\displaystyle D_{2}}$

Aqui, ${\displaystyle D_{2}((a,b),e)=22}$ é o menor valor de ${\displaystyle D_{2}}$, então juntamos o cluster ${\displaystyle (a,b)}$ e o elemento ${\displaystyle e}$ .

• Estimativa do comprimento do segundo ramo

Com ${\displaystyle v}$ a denotar o nó pelo qual ${\displaystyle (a,b)}$ e ${\displaystyle e}$ estão agora conectados. Devido à restrição de ultrametricidade, os ramos que unem ${\displaystyle a}$ ou ${\displaystyle b}$ a ${\displaystyle v}$, e ${\displaystyle e}$ a ${\displaystyle v}$ são iguais e têm o seguinte comprimento: ${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11}$

Deduzimos o comprimento do ramo restante: ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11-8.5=2.5}$ ( veja o dendrograma final )

• Atualização da matriz de segunda distância

Em seguida, procedemos à atualização ${\displaystyle D_{2}}$ em uma nova matriz de distância ${\displaystyle D_{3}}$ (veja abaixo), reduzida em tamanho por uma linha e uma coluna devido ao agrupamento de ${\displaystyle (a,b)}$ com ${\displaystyle e}$. Valores em negrito em ${\displaystyle D_{3}}$ correspondem às novas distâncias, calculadas pela média proporcional:

${\displaystyle D_{3}(((a,b),e),c)=(D_{2}((a,b),c)\times 2+D_{2}(e,c)\times 1)/(2+1)=(25.5\times 2+39\times 1)/3=30}$

Graças a esta média proporcional, o cálculo desta nova distância tem em conta o maior tamanho do cluster ${\displaystyle (a,b)}$ (dois elementos) em relação a ${\displaystyle e}$ (um elemento). Da mesma forma:

${\displaystyle D_{3}(((a,b),e),d)=(D_{2}((a,b),d)\times 2+D_{2}(e,d)\times 1)/(2+1)=(32.5\times 2+43\times 1)/3=36}$

A média proporcional, portanto, dá peso igual às distâncias iniciais da matriz ${\displaystyle D_{1}}$. Esta é a razão pela qual o método não é ponderado, não devido ao procedimento matemático, mas em relação às distâncias iniciais.

• Terceiro agrupamento

Reiteramos novamente os três passos anteriores, partindo da matriz de distância atualizada ${\displaystyle D_{3}}$ .

Aqui, ${\displaystyle D_{3}(c,d)=28}$ é o menor valor de ${\displaystyle D_{3}}$, então juntamos os elementos ${\displaystyle c}$ e ${\displaystyle d}$ .

• Estimativa do comprimento do terceiro ramo

Com ${\displaystyle w}$ a denotar o nó ao qual ${\displaystyle c}$ e ${\displaystyle d}$ estão agora conectados, os ramos que unem ${\displaystyle c}$ e ${\displaystyle d}$ a ${\displaystyle w}$ têm então comprimentos ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$ ( veja o dendrograma final )

• Atualização da matriz de terceira distância

Apenas uma entrada precisa de ser atualizada, considerando que os dois elementos ${\displaystyle c}$ e ${\displaystyle d}$ contribuem cada um com ${\displaystyle 1}$ para o cálculo da média:

${\displaystyle D_{4}((c,d),((a,b),e))=(D_{3}(c,((a,b),e))\times 1+D_{3}(d,((a,b),e))\times 1)/(1+1)=(30\times 1+36\times 1)/2=33}$

A final ${\displaystyle D_{4}}$ matriz é:

Então juntamos os grupos ${\displaystyle ((a,b),e)}$ e ${\displaystyle (c,d)}$ .

${\displaystyle r}$ denota o nó (raiz) ao qual ${\displaystyle ((a,b),e)}$ e ${\displaystyle (c,d)}$ estão agora conectados. Os ramos que unem ${\displaystyle ((a,b),e)}$ e ${\displaystyle (c,d)}$ a ${\displaystyle r}$ têm então comprimentos:

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=33/2=16.5}$

Deduzimos os dois comprimentos de ramificação restantes:

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=16.5-11=5.5}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=16.5-14=2.5}$

O dendrograma está agora completo.^[5] É ultramétrico porque todas as pontas ( ${\displaystyle a}$ a ${\displaystyle e}$ ) são equidistantes de ${\displaystyle r}$:

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=16.5}$

O dendrograma tem portanto ${\displaystyle r}$ como raiz, o seu nó mais basal.

Esquemas de ligação alternativos incluem agrupamento de ligação simples, agrupamento de ligação completa e agrupamento de ligação média WPGMA . Implementar uma ligação diferente é simplesmente uma questão de usar uma fórmula diferente para calcular distâncias entre clusters durante as etapas de atualização da matriz de distâncias do algoritmo acima. O agrupamento de ligação completa evita uma desvantagem do método alternativo de agrupamento de ligação única - o chamado fenômeno de encadeamento, onde os agrupamentos formados por meio do agrupamento de ligação única podem ser forçados a unir-se devido a elementos individuais estarem próximos uns dos outros, mesmo que muitos dos elementos em cada agrupamento possam estar muito distantes uns dos outros. A ligação completa tende a encontrar aglomerados compactos de diâmetros aproximadamente iguais.^[6]

Comparison of dendrograms obtained under different clustering methods from the same distance matrix.

Single-linkage clustering	Complete-linkage clustering	Average linkage clustering: WPGMA	Average linkage clustering: UPGMA.

• Em ecologia, é um dos métodos mais populares para a classificação de unidades de amostragem (como parcelas de vegetação) com base na sua semelhança em variáveis descritivas relevantes (como a sua composição de espécies).^[7] Por exemplo, tem sido usado para compreender a interação trófica entre bactérias marinhas e protistas.^[8]
• Em bioinformática, o UPGMA é usado na criação de árvores fenéticas (fenogramas). O UPGMA foi inicialmente projetado para uso em estudos de eletroforese de proteínas, mas atualmente é mais frequentemente usado para produzir árvores-guia para algoritmos mais sofisticados. Este algoritmo é usado, por exemplo, em procedimentos de alinhamento de sequências, pois propõe uma ordem na qual as sequências serão alinhadas. Na verdade, a árvore guia visa agrupar as sequências mais semelhantes, independentemente da sua taxa evolutiva ou afinidades filogenéticas, e é exatamente esse o objetivo do UPGMA^[9]
• Em filogenética, o UPGMA assume uma taxa constante de evolução ( hipótese do relógio molecular ) e que todas as sequências foram amostradas ao mesmo tempo, e não é um método bem conceituado para inferir relacionamentos, a menos que essa suposição tenha sido testada e justificada para o conjunto de dados usado. Observe que, mesmo sob um "relógio estrito", sequências amostradas em momentos diferentes não devem levar a uma árvore ultramétrica.

Uma implementação trivial do algoritmo para construir a árvore UPGMA tem ${\displaystyle O(n^{3})}$ complexidade temporal e usar um heap para cada cluster para manter suas distâncias de outro cluster reduz seu tempo para ${\displaystyle O(n^{2}\log n)}$ . Fionn Murtagh apresentou um ${\displaystyle O(n^{2})}$ algoritmo de tempo e espaço.^[10]

• Método de Neighbor joining
• Análise de clusters
• Agrupamento de ligação única
• Agrupamento de ligação completa
• Agrupamento hierárquico
• Modelos de evolução do DNA
• Relógio molecular

Referências

• Implementação do algoritmo de agrupamento UPGMA em Ruby (AI4R)
• Exemplo de cálculo de UPGMA usando uma matriz de similaridade
• Exemplo de cálculo de UPGMA usando uma matriz de distância