УПГМА

УПГМА (Шаблон:Јез-ен) представља једноставну методу хијерархијског кластеровања. УПГМА метод је нашао примену у наукама као што су екологија и биоинформатика. У Бионформатици се користи за генерисање филогенетских стабала. У контексту филогенетике УПГМА се ослања на хипотезу о молекуларном сату, и сматра се једним од лошијих метода изградње филогенетских стабала. Тренутно се УПГМА користи при генерисању стабала водиља за комплексније и поузданије алгоритме у филогенетици.

УПГМА конструише филогенетско стабло са кореном (дендрограм) који описује структуру матрица сличности ( или матрица различитости ).

У сваком кораку, два најбижа кластера се комбинују у већи. Растојање између било која два кластера А и Б представља просек свих растојања између парова објеката "x" из A и "y" из B.

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

Конструкцију алгоритма описали су Sokal и Michener. Fionn Murtagh је описао оптимални $O(n^2)$ алогоритам за конструкцију УПГМА стабла.

Алгоритам

1. Доделити сваки таксон сопственом кластеру
2. Дефинисати један лист за сваки таксон и поставити га на висину 0
3. Све док има више од два кластера
4. Одредити два кластера са најмањим растојањем $d(i,j)$
5. Дефинисати нови кластер $C_k=C_i\cup C_k$
6. Дефинисати чвор к са потомцима i и ј и поставити га на висину $d(i,j)/2$
7. Заменити кластере i и j кластером к
8. Израчунати растојање између к и осталих кластера
9. Спојити последња два кластера i и j кореном на висини $d(i,j)/2$

Пример

Нека је задата следећа матрица растојања:

	А	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

Бирамо два таксона са најмањим растојањем. То су А и B. Висина дрвета је $d(A,B)/2=2/2=1$

Рачунамо растојање новог кластера АB у односу на преостале таксоне.

	АB	C	D	E
C	4
D	6	6
E	6	6	4
F	8	8	8	8

Таксони са најмањим растојањем су D и E. Висина дрвета је $d(D,E)/2=4/2=2$

Рачунамо растојање новог кластера DE у односу на преостале таксоне.

	АB	C	DЕ
C	4
DЕ	6	6
F	8	8	8

Висина дрвета: $d(C,AB)/2=4/2=2$

Рачунамо растојање новог кластера ABC у односу на преостале таксоне.

	АBC	DЕ
DE	6
F	8	8

Висина дрвета: $d(ABC,DE)/2=6/2=3$

Рачунамо растојање новог кластера ABCDE у односу на преостале таксоне.

	АBCDE
F	8

Висина дрвета: $d(ABCDE,F)/2=8/2=4$

Види још

• Спајање суседа
• Кластер анализа
• Хијерархијско кластеровање
• Молекуларни сат