УПГМА

Из Википедије, слободне енциклопедије

УПГМА (енгл. Unweighted Pair Group Method with Arithmetic Mean) представља једноставну методу хијерархијског кластеровања. УПГМА метод је нашао примену у наукама као што су екологија и биоинформатика. У Бионформатици се користи за генерисање филогенетских стабала. У контексту филогенетике УПГМА се ослања на хипотезу о молекуларном сату, и сматра се једним од лошијих метода изградње филогенетских стабала. Тренутно се УПГМА користи при генерисању стабала водиља за комплексније и поузданије алгоритме у филогенетици.

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

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

Конструкцију алгоритма описали су Sokal и Michener.[1] Fionn Murtagh је описао оптимални алогоритам за конструкцију УПГМА стабла.[2]


Алгоритам[уреди]

  1. Доделити сваки таксон сопственом кластеру
  2. Дефинисати један лист за сваки таксон и поставити га на висину 0
  3. Све док има више од два кластера
  4. Одредити два кластера са најмањим растојањем
  5. Дефинисати нови кластер
  6. Дефинисати чвор к са потомцима i и ј и поставити га на висину
  7. Заменити кластере i и j кластером к
  8. Израчунати растојање између к и осталих кластера
  9. Спојити последња два кластера 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
C 4
6 6
F 8 8 8

Висина дрвета:



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

АBC
DE 6
F 8 8

Висина дрвета:



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

АBCDE
F 8

Висина дрвета:

Види још[уреди]

Референце[уреди]

  1. Sokal R and Michener C (1958). „A statistical method for evaluating systematic relationships”. University of Kansas Science Bulletin. 38: 1409ֱ438. 
  2. F, Murtagh (1984). „Complexities of Hierarchic Clustering Algorithms: the state of the art”. Computational Statistics Quarterly. 1: 101ֱ13.