UPGMA ( método de grupos de pares no ponderados con media aritmética ) es un método simple de agrupamiento jerárquico aglomerativo (ascendente) . El método generalmente se atribuye a Sokal y Michener . [1]
El método UPGMA es similar a su variante ponderada , el método WPGMA .
Tenga en cuenta que el término no ponderado indica que todas las distancias contribuyen por igual a cada promedio que se calcula y no se refiere a las matemáticas mediante las cuales se logra. Por lo tanto, el promedio simple en WPGMA produce un resultado ponderado y el promedio proporcional en UPGMA produce un resultado no ponderado ( ver el ejemplo de trabajo ). [2]
Algoritmo
El algoritmo UPGMA construye un árbol enraizado ( dendrograma ) que refleja la estructura presente en una matriz de semejanza por pares (o una matriz de disimilitud ). En cada paso, los dos grupos más cercanos se combinan en un grupo de nivel superior. La distancia entre dos grupos cualesquiera y , cada uno de tamaño ( es decir , cardinalidad ) y , se toma como el promedio de todas las distancias entre pares de objetos en y en , es decir, la distancia media entre elementos de cada grupo:
En otras palabras, en cada paso de agrupamiento, la distancia actualizada entre los grupos unidos y un nuevo clúster viene dada por el promedio proporcional de la y distancias:
El algoritmo UPGMA produce dendrogramas enraizados y requiere una suposición de tasa constante, es decir, asume un árbol ultramétrico en el que las distancias desde la raíz hasta la punta de cada rama son iguales. Cuando las puntas son datos moleculares ( es decir , ADN , ARN y proteínas ) muestreados al mismo tiempo, el supuesto de ultrametricidad se vuelve equivalente a suponer un reloj molecular .
Ejemplo de trabajo
Este ejemplo de trabajo se basa en una matriz de distancia genética JC69 calculada a partir de la alineación de la secuencia de ARN ribosómico 5S de cinco bacterias: Bacillus subtilis (), Bacillus stearothermophilus (), Lactobacillus viridescens (), Acholeplasma modicum () y Micrococcus luteus (). [3] [4]
Primer paso
- Primera agrupación
Supongamos que tenemos cinco elementos y la siguiente matriz de distancias por pares entre ellos:
a | B | C | D | mi | |
---|---|---|---|---|---|
a | 0 | 17 | 21 | 31 | 23 |
B | 17 | 0 | 30 | 34 | 21 |
C | 21 | 30 | 0 | 28 | 39 |
D | 31 | 34 | 28 | 0 | 43 |
mi | 23 | 21 | 39 | 43 | 0 |
En este ejemplo, es el valor más pequeño de , entonces unimos elementos y .
- Estimación de la longitud de la primera rama
Dejar denotar el nodo al que y ahora están conectados. Configuración asegura que los elementos y son equidistantes de . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que se unen y a luego tener longitudes ( ver el dendrograma final )
- Actualización de la primera matriz de distancias
Luego procedemos a actualizar la matriz de distancias inicial en una nueva matriz de distancia (ver más abajo), reducido en tamaño en una fila y una columna debido a la agrupación de con . Valores audaces encorresponden a las nuevas distancias, calculadas promediando las distancias entre cada elemento del primer grupo y cada uno de los elementos restantes:
Valores en cursiva en no se ven afectados por la actualización de la matriz, ya que corresponden a distancias entre elementos no involucrados en el primer grupo.
Segundo paso
- Segundo agrupamiento
Ahora reiteramos los tres pasos anteriores, comenzando desde la nueva matriz de distancias
(a, b) | C | D | mi | |
---|---|---|---|---|
(a, b) | 0 | 25,5 | 32,5 | 22 |
C | 25,5 | 0 | 28 | 39 |
D | 32,5 | 28 | 0 | 43 |
mi | 22 | 39 | 43 | 0 |
Aquí, es el valor más pequeño de , entonces nos unimos al clúster y elemento .
- Estimación de la longitud de la segunda rama
Dejar denotar el nodo al que y ahora están conectados. Debido a la restricción de ultrametricidad, las ramas que se unen o a , y a son iguales y tienen la siguiente longitud:
Deducimos la longitud de la rama que falta: ( ver el dendrograma final )
- Actualización de la segunda matriz de distancia
Luego procedemos a actualizar en una nueva matriz de distancia (ver más abajo), reducido en tamaño en una fila y una columna debido a la agrupación de con . Valores audaces encorresponden a las nuevas distancias, calculadas por promediado proporcional :
Gracias a este promedio proporcional, el cálculo de esta nueva distancia da cuenta del mayor tamaño de la cluster (dos elementos) con respecto a (un elemento). Similar:
Por lo tanto, el promedio proporcional da el mismo peso a las distancias iniciales de la matriz. . Esta es la razón por la que el método no está ponderado , no con respecto al procedimiento matemático sino con respecto a las distancias iniciales.
Tercer paso
- Tercer agrupamiento
Reiteramos de nuevo los tres pasos anteriores, partiendo de la matriz de distancias actualizada .
((a, b), e) | C | D | |
---|---|---|---|
((a, b), e) | 0 | 30 | 36 |
C | 30 | 0 | 28 |
D | 36 | 28 | 0 |
Aquí, es el valor más pequeño de , entonces unimos elementos y .
- Estimación de la longitud de la tercera rama
Dejar denotar el nodo al que y ahora están conectados. Las ramas que se unen y a luego tener longitudes ( ver el dendrograma final )
- Actualización de la matriz de la tercera distancia
Hay una única entrada para actualizar, teniendo en cuenta que los dos elementos y cada uno tiene una contribución de en el cálculo promedio :
Último paso
El final matriz es:
((a, b), e) | (CD) | |
---|---|---|
((a, b), e) | 0 | 33 |
(CD) | 33 | 0 |
Entonces nos unimos a grupos y .
Dejar denotar el nodo (raíz) al que y ahora están conectados. Las ramas que se unen y a luego tener longitudes:
Deducimos las dos longitudes de rama restantes:
El dendrograma UPGMA
El dendrograma ahora está completo. [5] Es ultramétrico porque todas las puntas ( a ) son equidistantes de :
Por tanto, el dendrograma tiene sus raíces en , su nodo más profundo.
Comparación con otros vínculos
Los esquemas de vinculación alternativos incluyen agrupación de vinculación única , agrupación de vinculación completa y agrupación de vinculación promedio WPGMA . Implementar un enlace diferente es simplemente una cuestión de usar una fórmula diferente para calcular las distancias entre grupos durante los pasos de actualización de la matriz de distancia del algoritmo anterior. La agrupación de enlaces completa evita un inconveniente del método alternativo de agrupación de enlaces únicos: el llamado fenómeno de encadenamiento , en el que los grupos formados a través de la agrupación de enlaces únicos pueden forzarse juntos debido a que los elementos individuales están cerca unos de otros, aunque muchos de los elementos de cada uno de ellos. Los grupos pueden estar muy distantes entre sí. El enlace completo tiende a encontrar grupos compactos de diámetros aproximadamente iguales. [6]
Agrupación de un solo enlace. | Agrupación de enlaces completos. | Agrupación de enlaces promedio: WPGMA. | Agrupación de enlaces promedio: UPGMA . |
Usos
- En ecología , es uno de los métodos más populares para la clasificación de unidades de muestreo (como parcelas de vegetación) sobre la base de sus similitudes por pares en las variables descriptivas relevantes (como la composición de especies). [7] Por ejemplo, se ha utilizado para comprender la interacción trófica entre las bacterias marinas y los protistas. [8]
- En bioinformática , UPGMA se utiliza para la creación de árboles fenéticos (fenogramas). UPGMA se diseñó inicialmente para su uso en estudios de electroforesis de proteínas , pero actualmente se utiliza con mayor frecuencia para producir árboles guía para algoritmos más sofisticados. Este algoritmo se utiliza, por ejemplo, en procedimientos de alineación de secuencias , ya que propone un orden en el que se alinearán las secuencias. De hecho, el árbol guía tiene como objetivo agrupar las secuencias más similares, independientemente de su tasa evolutiva o afinidades filogenéticas, y ese es exactamente el objetivo de UPGMA [9].
- En filogenética , UPGMA asume una tasa constante de evolución ( hipótesis del reloj molecular ) y que todas las secuencias fueron muestreadas al mismo tiempo, y no es un método bien considerado para inferir relaciones a menos que esta suposición haya sido probada y justificada para que el conjunto de datos sea usó. Tenga en cuenta que incluso bajo un 'reloj estricto', las secuencias muestreadas en diferentes momentos no deberían conducir a un árbol ultramétrico.
Complejidad del tiempo
Una implementación trivial del algoritmo para construir el árbol UPGMA ha complejidad del tiempo, y el uso de un montón para cada clúster para mantener sus distancias de otro clúster reduce su tiempo para . Fionn Murtagh presentó algunos otros enfoques para casos especiales, unalgoritmo de tiempo de Day y Edelsbrunner [10] para datos k-dimensionales que son óptimos para k constante, y otro algoritmo para entradas restringidas, cuando "la estrategia aglomerativa satisface la propiedad de reducibilidad". [11]
Ver también
- Unión de vecinos
- Análisis de conglomerados
- Agrupación de un solo enlace
- Agrupación de enlaces completos
- Agrupación jerárquica
- Modelos de evolución del ADN
- Reloj molecular
Referencias
- ^ Sokal , Michener (1958). "Un método estadístico para evaluar relaciones sistemáticas" . Boletín de Ciencias de la Universidad de Kansas . 38 : 1409-1438.
- ^ Garcia S, Puigbò P. "DendroUPGMA: Una utilidad de construcción de dendrogramas" (PDF) . pag. 4.
- ^ Erdmann VA, Wolters J (1986). "Colección de secuencias de ARN ribosómico 5S, 5.8S y 4.5S publicadas" . Investigación de ácidos nucleicos . 14 Supl (Supl): r1–59. doi : 10.1093 / nar / 14.suppl.r1 . PMC 341310 . PMID 2422630 .
- ^ Olsen GJ (1988). "Análisis filogenético mediante ARN ribosómico". Métodos en enzimología . 164 : 793–812. doi : 10.1016 / s0076-6879 (88) 64084-5 . PMID 3241556 .
- ^ Swofford DL, Olsen GJ, Waddell PJ, Hillis DM (1996). "Inferencia filogenética". En Hillis DM, Moritz C, Mable BK (eds.). Sistemática Molecular, 2ª edición . Sunderland, MA: Sinauer. págs. 407–514. ISBN 9780878932825.
- ^ Everitt, BS; Landau, S .; Leese, M. (2001). Análisis de conglomerados. 4ª Edición . Londres: Arnold. pag. 62–64.
- ^ Legendre P, Legendre L (1998). Ecología numérica . Desarrollos en Modelización Ambiental. 20 (Segunda edición en inglés). Amsterdam: Elsevier.
- ^ Vázquez-Domínguez E, Casamayor EO, Català P, Lebaron P (abril de 2005). "Diferentes nanoflagelados heterótrofos marinos afectan diferencialmente la composición de las comunidades bacterianas enriquecidas". Ecología microbiana . 49 (3): 474–85. doi : 10.1007 / s00248-004-0035-5 . JSTOR 25153200 . PMID 16003474 . S2CID 22300174 .
- ^ Wheeler TJ, Kececioglu JD (julio de 2007). "Alineación múltiple alineando alineaciones" . Bioinformática . 23 (13): i559–68. doi : 10.1093 / bioinformatics / btm226 . PMID 17646343 .
- ^ Día WH, Edelsbrunner H (1 de diciembre de 1984). "Algoritmos eficientes para métodos de agrupamiento jerárquico aglomerativo". Revista de clasificación . 1 (1): 7–24. doi : 10.1007 / BF01890115 . ISSN 0176-4268 . S2CID 121201396 .
- ^ Murtagh F (1984). "Complejidades de algoritmos de agrupamiento jerárquico: el estado del arte". Estadística Computacional Trimestral . 1 : 101-113.
enlaces externos
- Implementación del algoritmo de agrupación en clústeres UPGMA en Ruby (AI4R)
- Ejemplo de cálculo de UPGMA usando una matriz de similitud
- Ejemplo de cálculo de UPGMA usando una matriz de distancia