УПГМА () представља једноставну методу хијерархијског кластеровања. УПГМА метод је нашао примену у наукама као што су екологија и биоинформатика. У Бионформатици се користи за генерисање филогенетских стабала. У контексту филогенетике УПГМА се ослања на хипотезу о молекуларном сату, и сматра се једним од лошијих метода изградње филогенетских стабала. Тренутно се УПГМА користи при генерисању стабала водиља за комплексније и поузданије алгоритме у филогенетици.
УПГМА конструише филогенетско стабло са кореном (дендрограм) који описује структуру матрица сличности ( или матрица различитости ).
У сваком кораку, два најбижа кластера се комбинују у већи. Растојање између било која два кластера А и Б представља просек свих растојања између парова објеката "x" из A и "y" из B.
Конструкцију алгоритма описали су Sokal и Michener. Fionn Murtagh је описао оптимални алогоритам за конструкцију УПГМА стабла.
Алгоритам Доделити сваки таксон сопственом кластеру Дефинисати један лист за сваки таксон и поставити га на висину 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 Висина дрвета:
Види још Спајање суседа Кластер анализа Хијерархијско кластеровање Молекуларни сат
Референце
Категорија:Informatika