УПГМА

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

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

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

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

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

Конструкцију алгоритма описали су Sokal и Michener.[1] Fionn Murtagh је описао оптимални O(n^2) алогоритам за конструкцију УПГМА стабла.[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
C 4
6 6
F 8 8 8

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



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

АBC
DE 6
F 8 8

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



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

АBCDE
F 8

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

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

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

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