УПГМА
УПГМА (енгл. Unweighted Pair Group Method with Arithmetic Mean) представља једноставну методу хијерархијског кластеровања. УПГМА метод је нашао примену у наукама као што су екологија и биоинформатика. У Бионформатици се користи за генерисање филогенетских стабала. У контексту филогенетике УПГМА се ослања на хипотезу о молекуларном сату, и сматра се једним од лошијих метода изградње филогенетских стабала. Тренутно се УПГМА користи при генерисању стабала водиља за комплексније и поузданије алгоритме у филогенетици.
УПГМА конструише филогенетско стабло са кореном (дендрограм) који описује структуру матрица сличности ( или матрица различитости ).
У сваком кораку, два најбижа кластера се комбинују у већи. Растојање између било која два кластера А и Б представља просек свих растојања између парова објеката "x" из A и "y" из B.
Конструкцију алгоритма описали су Sokal и Michener.[1] Fionn Murtagh је описао оптимални алогоритам за конструкцију УПГМА стабла.[2]
Алгоритам
[уреди | уреди извор]- Доделити сваки таксон сопственом кластеру
- Дефинисати један лист за сваки таксон и поставити га на висину 0
- Све док има више од два кластера
- Одредити два кластера са најмањим растојањем
- Дефинисати нови кластер
- Дефинисати чвор к са потомцима i и ј и поставити га на висину
- Заменити кластере i и j кластером к
- Израчунати растојање између к и осталих кластера
- Спојити последња два кластера i и j кореном на висини
Пример
[уреди | уреди извор]Нека је задата следећа матрица растојања:
А | 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. Висина дрвета је
Рачунамо растојање новог кластера АB у односу на преостале таксоне.
АB | C | D | E | |
---|---|---|---|---|
C | 4 | |||
D | 6 | 6 | ||
E | 6 | 6 | 4 | |
F | 8 | 8 | 8 | 8 |
Таксони са најмањим растојањем су D и E. Висина дрвета је
Рачунамо растојање новог кластера DE у односу на преостале таксоне.
АB | C | DЕ | |
---|---|---|---|
C | 4 | ||
DЕ | 6 | 6 | |
F | 8 | 8 | 8 |
Висина дрвета:
Рачунамо растојање новог кластера ABC у односу на преостале таксоне.
АBC | DЕ | |
---|---|---|
DE | 6 | |
F | 8 | 8 |
Висина дрвета:
Рачунамо растојање новог кластера ABCDE у односу на преостале таксоне.
АBCDE | |
---|---|
F | 8 |
Висина дрвета: