UPGMA

UPGMA (engl. Unweighted Pair Group Method with Arithmetic Mean) predstavlja jednostavnu metodu hijerarhijskog klasterovanja. UPGMA metod je našao primenu u naukama kao što su ekologija i bioinformatika. U Bionformatici se koristi za generisanje filogenetskih stabala. U kontekstu filogenetike UPGMA se oslanja na hipotezu o molekularnom satu, i smatra se jednim od lošijih metoda izgradnje filogenetskih stabala. Trenutno se UPGMA koristi pri generisanju stabala vodilja za kompleksnije i pouzdanije algoritme u filogenetici.

UPGMA konstruiše filogenetsko stablo sa korenom (dendrogram) koji opisuje strukturu matrica sličnosti ( ili matrica različitosti ).

U svakom koraku, dva najbiža klastera se kombinuju u veći. Rastojanje između bilo koja dva klastera A i B predstavlja prosek svih rastojanja između parova objekata "x" iz A i "y" iz B.

${1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y)$

Konstrukciju algoritma opisali su Sokal i Michener. Fionn Murtagh je opisao optimalni $O(n^{2})$ alogoritam za konstrukciju UPGMA stabla.

Algoritam

1. Dodeliti svaki takson sopstvenom klasteru
2. Definisati jedan list za svaki takson i postaviti ga na visinu 0
3. Sve dok ima više od dva klastera
4. Odrediti dva klastera sa najmanjim rastojanjem $d(i,j)$
5. Definisati novi klaster $C_{k}=C_{i}\cup C_{k}$
6. Definisati čvor k sa potomcima i i j i postaviti ga na visinu $d(i,j)/2$
7. Zameniti klastere i i j klasterom k
8. Izračunati rastojanje između k i ostalih klastera
9. Spojiti poslednja dva klastera i i j korenom na visini $d(i,j)/2$

Primer

Neka je zadata sledeća matrica rastojanja:

	A	B	C	D	E	F
B	2
C	4	4
D	6	6	6
E	6	6	6	4
F	8	8	8	8	8	8

Biramo dva taksona sa najmanjim rastojanjem. To su A i B. Visina drveta je $d(A,B)/2=2/2=1$

Računamo rastojanje novog klastera AB u odnosu na preostale taksone.

	AB	C	D	E
C	4
D	6	6
E	6	6	4
F	8	8	8	8

Taksoni sa najmanjim rastojanjem su D i E. Visina drveta je $d(D,E)/2=4/2=2$

Računamo rastojanje novog klastera DE u odnosu na preostale taksone.

	AB	C	DE
C	4
DE	6	6
F	8	8	8

Visina drveta: $d(C,AB)/2=4/2=2$

Računamo rastojanje novog klastera ABC u odnosu na preostale taksone.

	ABC	DE
DE	6
F	8	8

Visina drveta: $d(ABC,DE)/2=6/2=3$

Računamo rastojanje novog klastera ABCDE u odnosu na preostale taksone.

	ABCDE
F	8

Visina drveta: $d(ABCDE,F)/2=8/2=4$

Vidi još

• Spajanje suseda
• Klaster analiza
• Hijerarhijsko klasterovanje
• Molekularni sat