Unweighted Pair Group Method with Arithmetic mean

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. dass alle Taxa mit derselben konstanten Rate evolvieren.

Gegeben ist eine Menge von Objekten und eine Distanzmatrix welche die paarweisen Distanzen der Objekte enthält, wobei das Distanzmaß dX,Y die Eigenschaften einer Ultrametrik 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 bei WPGMA wie folgt:


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

Sind unterschiedlich viele Objekte in einem Cluster, so tragen diese bei WPGMA nicht gleichberechtigt zur Abstandsberechnung des neuen Clusters bei. Die Distanzen werden also in der Berechnung unterschiedlich gewichtet (daher: weighted PGMA).

Verwendet man das verbesserte UPGMA, so berechnen sich die neuen Distanzen mit:


d_{X,K} := \frac{|A| \cdot d_{A,K} + |B| \cdot d_{B, K}}{|A| + |B|}

Dies bewirkt, dass alle Abstände gleichberechtigt, also ungewichtet (unweighted), in die Abstandsberechnung einbezogen werden.

Häufig werden WPGMA und UPGMA verwechselt, da die ungewichtete Berechnung, UPGMA, die mathematisch kompliziertere Formel hat, während die Formel der gewichteten Berechnung, WPGMA, einfacher aussieht. Bei der Bezeichnung wurde jedoch von dem Ergebnis ausgegangen: Der einfache Mittelwert der WPGMA ergibt ein gewichtetes Ergebnis, während der proportionale Mittelwert der UPGMA ein ungewichtetes Ergebnis liefert.[1]

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.

Einzelnachweise

  1. http://www.mun.ca/biology/scarr/UPGMA_vs_WPGMA.htm

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Unweighted Pair Group Method with Arithmetic Mean — UPGMA (Unweighted Pair Group Method with Arithmetic mean) est le nom d un algorithme destiné à la construction d un arbre phylogénétique. Cette méthode permet la transformation d une matrice de distances (entre différents organismes, populations …   Wikipédia en Français

  • 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… …   Deutsch Wikipedia

  • UPGMA — Unweighted Pair Group Method with Arithmetic Mean UPGMA (Unweighted Pair Group Method with Arithmetic mean) est le nom d un algorithme destiné à la construction d un arbre phylogénétique. Cette méthode permet la transformation d une matrice de… …   Wikipédia en Français

  • UPGMA — 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… …   Deutsch Wikipedia

  • WPGMA — 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… …   Deutsch Wikipedia

  • Cluster analysis — The result of a cluster analysis shown as the coloring of the squares into three clusters. Cluster analysis or clustering is the task of assigning a set of objects into groups (called clusters) so that the objects in the same cluster are more… …   Wikipedia

  • UPGMA — (Unweighted Pair Group Method with Arithmetic mean) is a simple agglomerative or bottom up data clustering method used in bioinformatics for the creation of phylogenetic trees. UPGMA assumes a constant rate of evolution (molecular clock… …   Wikipedia

  • Computational phylogenetics — is the application of computational algorithms, methods and programs to phylogenetic analyses. The goal is to assemble a phylogenetic tree representing a hypothesis about the evolutionary ancestry of a set of genes, species, or other taxa. For… …   Wikipedia

  • Distance matrices in phylogeny — Distance matrices are used in phylogeny as non parametric distance methods were originally applied to phenetic data using a matrix of pairwise distances. These distances are then reconciled to produce a tree (a phylogram, with informative branch… …   Wikipedia

  • Neighbor-Joining-Algorithmus — Der Neighbor Joining Algorithmus ist ein mathematisches Verfahren, um Datensätze zu vergleichen und hierarchisch bifurcal (zweigabelig) anzuordnen. Dieses Verfahren wurde 1987 von Saitou und Nei vorgestellt und 1988 von Studier und Keppler… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”