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]

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 $𝒜$ e $ℬ$ , cada um de tamanho ( ou seja, cardinalidade ) $| 𝒜 |$ e $| ℬ |$ , é considerada a média de todas as distâncias $d (x, y)$ entre pares de objetos $x$ em $𝒜$ e $y$ em $ℬ$ , ou seja, a distância média entre os elementos de cada cluster:

\frac{1}{| 𝒜 | \cdot | ℬ |} \sum_{x \in 𝒜} \sum_{y \in ℬ} d (x, y)

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

$d_{(𝒜 \cup ℬ), X} = \frac{| 𝒜 | \cdot d_{𝒜, X} + | ℬ | \cdot d_{ℬ, X}}{| 𝒜 | + | ℬ |}$

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$ ).^[3]^[4]

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 $δ (a, u) = δ (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 $δ (a, u) = δ (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: $δ (a, v) = δ (b, v) = δ (e, v) = 22 / 2 = 11$

Deduzimos o comprimento do ramo restante: $δ (u, v) = δ (e, v) - δ (a, u) = δ (e, v) - δ (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 $δ (c, w) = δ (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:

$δ (((a, b), e), r) = δ ((c, d), r) = 33 / 2 = 16.5$

Deduzimos os dois comprimentos de ramificação restantes:

$δ (v, r) = δ (((a, b), e), r) - δ (e, v) = 16.5 - 11 = 5.5$

$δ (w, r) = δ ((c, d), r) - δ (c, w) = 16.5 - 14 = 2.5$

O dendrograma UPGMA

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

$δ (a, r) = δ (b, r) = δ (e, r) = δ (c, r) = δ (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.^[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.

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).^[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.

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.^[10]

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

Predefinição:Referências

Ligações externas

[1] Predefinição:Citar periódico

[2] Predefinição:Citar web

[Erdmann1986-3] Predefinição:Citar periódico

[Olsen1988-4] Predefinição:Citar livro

[Swofford1996-5] Predefinição:Citar livro

[6] Predefinição:Citar livro

[7] Predefinição:Citar livro

[8] Predefinição:Citar periódico

[pmid17646343-9] Predefinição:Citar periódico

[10] Predefinição:Citar periódico

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

UPGMA

Índice

Algoritmo