UPGMA
# 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.
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 ).

## Algoritmo

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 ${\mathcal {A}}$ e ${\mathcal {B}}$, cada um de tamanho ( ou seja, cardinalidade ) ${|{\mathcal {A}}|}$ e ${|{\mathcal {B}}|}$, é considerada a média de todas as distâncias $d(x,y)$ entre pares de objetos $x$ em ${\mathcal {A}}$ e $y$ em ${\mathcal {B}}$, ou seja, a distância média entre os elementos de cada cluster:
       ${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 ${\mathcal {A}}\cup {\mathcal {B}}$ e um novo cluster $X$ é dada pela média proporcional das distâncias $d_{{\mathcal {A}},X}$ e $d_{{\mathcal {B}},X}$:
$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.

## Exemplo prático

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 ( $a$ ), Bacillus stearothermophilus ( $b$ ), Lactobacillus viridescens ( $c$ ), Acholeplasma modicum ( $d$ ) e Micrococcus luteus ( $e$ ).

### Primeiro passo

* Primeiro agrupamento
Assumindo que temos cinco elementos $(a,b,c,d,e)$ e a seguinte matriz $D_{1}$ de distâncias em pares entre eles:
| | a | b | c | e | e |
| a | 0 | 17 | 21 | 31 | 23 |
| b | 17 | 0 | 30 | 34 | 21 |
| c | 21 | 30 | 0 | 28 | 39 |
| e | 31 | 34 | 28 | 0 | 43 |
| e | 23 | 21 | 39 | 43 | 0 |
Neste exemplo, $D_{1}(a,b)=17$ é o menor valor de $D_{1}$, então juntamos os elementos $a$ e $b$ .
* Estimativa do comprimento do primeiro ramo
De ressaltar que $u$ denota o nó ao qual $a$ e $b$ estão agora conectados. Com $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ é garantido que os elementos $a$ e $b$ são equidistantes de $u$ . Isto corresponde à expectativa da hipótese de ultrametricidade. Os ramos que unem $a$ e $b$ a $u$ têm então comprimentos $\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 $D_{1}$ para uma nova matriz de distância $D_{2}$ (veja abaixo), reduzida em tamanho por uma linha e uma coluna devido ao agrupamento de $a$ com $b$ . Valores em negrito em $D_{2}$ correspondem às novas distâncias, calculadas pela média das distâncias entre cada elemento do primeiro par $(a,b)$ e cada um dos elementos restantes:
$D_{2}((a,b),c)=(D_{1}(a,c)\times 1+D_{1}(b,c)\times 1)/(1+1)=(21+30)/2=25.5$
$D_{2}((a,b),d)=(D_{1}(a,d)+D_{1}(b,d))/2=(31+34)/2=32.5$
$D_{2}((a,b),e)=(D_{1}(a,e)+D_{1}(b,e))/2=(23+21)/2=22$
Valores em itálico em $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 passo

* Segundo agrupamento
Os três passos anteriores são então repetidos, começando agora com a nova matriz de distâncias $D_{2}$
| | (a,b) | c | e | e |
| (a,b) | 0 | 25,5 | 32,5 | 22 |
| c | 25,5 | 0 | 28 | 39 |
| e | 32,5 | 28 | 0 | 43 |
| e | 22 | 39 | 43 | 0 |
Aqui, $D_{2}((a,b),e)=22$ é o menor valor de $D_{2}$, então juntamos o cluster $(a,b)$ e o elemento $e$ .
* Estimativa do comprimento do segundo ramo
Com $v$ a denotar o nó pelo qual $(a,b)$ e $e$ estão agora conectados. Devido à restrição de ultrametricidade, os ramos que unem $a$ ou $b$ a $v$, e $e$ a $v$ são iguais e têm o seguinte comprimento: $\delta (a,v)=\delta (b,v)=\delta (e,v)=22/2=11$
Deduzimos o comprimento do ramo restante: $\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 $D_{2}$ em uma nova matriz de distância $D_{3}$ (veja abaixo), reduzida em tamanho por uma linha e uma coluna devido ao agrupamento de $(a,b)$ com $e$. Valores em negrito em $D_{3}$ correspondem às novas distâncias, calculadas pela média proporcional:
$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 $(a,b)$ (dois elementos) em relação a $e$ (um elemento). Da mesma forma:
$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 $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 passo

* Terceiro agrupamento
Reiteramos novamente os três passos anteriores, partindo da matriz de distância atualizada $D_{3}$ .
| | ((a,b),e) | c | e |
| ((a,b),e) | 0 | 30 | 36 |
| c | 30 | 0 | 28 |
| e | 36 | 28 | 0 |
Aqui, $D_{3}(c,d)=28$ é o menor valor de $D_{3}$, então juntamos os elementos $c$ e $d$ .
* Estimativa do comprimento do terceiro ramo
Com $w$ a denotar o nó ao qual $c$ e $d$ estão agora conectados, os ramos que unem $c$ e $d$ a $w$ têm então comprimentos $\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 $c$ e $d$ contribuem cada um com $1$ para o cálculo da média:
$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$

### Etapa final

A final $D_{4}$ matriz é:
| | ((a,b),e) | (cd) |
| ((a,b),e) | 0 | 33 |
| (cd) | 33 | 0 |
Então juntamos os grupos $((a,b),e)$ e $(c,d)$ .
$r$ denota o nó (raiz) ao qual $((a,b),e)$ e $(c,d)$ estão agora conectados. Os ramos que unem $((a,b),e)$ e $(c,d)$ a $r$ têm então comprimentos:
$\delta (((a,b),e),r)=\delta ((c,d),r)=33/2=16.5$
Deduzimos os dois comprimentos de ramificação restantes:
$\delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=16.5-11=5.5$
$\delta (w,r)=\delta ((c,d),r)-\delta (c,w)=16.5-14=2.5$

### O dendrograma UPGMA

O dendrograma está agora completo. É ultramétrico porque todas as pontas ( $a$ a $e$ ) são equidistantes de $r$:
$\delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=16.5$
O dendrograma tem portanto $r$ como raiz, o seu nó mais basal.

### Comparação com outras ligações

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.
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. |

## Usos

* 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). Por exemplo, tem sido usado para compreender a interação trófica entre bactérias marinhas e protistas.
* 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
* 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.

## Complexidade temporal

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

## Veja também

* 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