Unweighted Pair Group Method with Arithmetic mean

Unweighted Pair Group Method with Arithmetic mean (kurz UPGMA) bezeichnet eine Bottom-Up Clustering Methode. Sie wird oft in der Bioinformatik zur Rekonstruktion phylogenetischer Bäume angewendet. Im Gegensatz zu anderen Verfahren wie Neighbour Joining basiert UPGMA auf der Annahme der Molekularen Uhr, d.h. alle Taxa evolvieren mit der selben konstanten Änderungsrate.

Weiteres empfehlenswertes Fachwissen

Leitfaden zu den grundlegenden Laborkenntnissen

Leitfaden für die Waagenreinigung: 8 einfache Schritte

Empfindlichkeitsprüfung von Laborwaagen

Gegeben ist eine Menge von Objekten und eine Distanzmatrix welche die paarweisen Distanzen der Objekte enthält, wobei das Distanzmaß $d X, Y$ die Eigenschaften einer Metrik aufweisen muss. Gesucht ist ein binärer Baum, dessen Blätter die Objekte darstellen und dessen Kanten möglichst gut die Distanzen in der Distanzmatrix reflektieren.

Zu Beginn ist jedes Objekt in einem eigenen Cluster. In jedem Schritt werden die beiden Cluster mit der geringsten Distanz zusammengefasst und die Distanzmatrix neu berechnet. Die Distanz zwischen zwei Clustern ist der Mittelwert der paarweisen Distanzen aller Objekte in beiden Clustern. Sei $X$ der neue Cluster der aus den beiden Clustern $A$ und $B$ gebildet wurde: $X = A \cup B$ . Die Distanz zu einem Cluster $K$ berechnet sich dann wie folgt:

$d_{X,K} := \frac{\Sigma_{x \in X, k \in K} d_{x,k}}{|X|\cdot|K|}$

Bei der Berechnung der neuen Distanzen unterscheidet sich UPGMA von WPGMA, wo gilt:

$d_{X,K} := \frac{d_{A,K} + d_{B,K}}{2}$

Literatur

R.R. Sokal and C.D. Michener.: A statistical method for evaluating systematic relationships. In: University of Kansas Science Bulletin, 38:1409–1438, 1958.

Kategorie: Bioinformatik