茶年 · 中文维基百科

UPGMA

Wikipedia · 2025-06-26 维基百科 👁 1 阅读

UPGMA （unweighted pair group method with arithmetic mean）是一種相對簡單的層次聚類方法。這個方法存在另一種變體 WPGMA。這個方法的創始人被認為是Sokal和Michener 。

演算方法
UPGMA 演法構建出一棵有根樹（樹狀圖）表現相似矩陣或相異矩陣中的特徵與結構。在算法裡的每一步，距離最近的兩個集群（子樹）將被組合成一個更高級別的集群。任意兩個集群\mathcal{A}和\mathcal{B} 之間的距離，是由所有\mathcal{A}裡的x元素和所有\mathcal{B}裡的y元素的距離d(x,y)的平均值，即每個集群的元素之間的平均距離，其中 和是該兩個集群的基數（集合大小）：

:: d_{\mathcal{A},\mathcal{B}}={1 \over }\sum_{x \in \mathcal{A}}\sum_{ y \in \mathcal{B}} d(x,y)

換句話說，在每一次組合成新集群的步驟中，可以由d_{\mathcal{A},X}和d_{\mathcal{B},X}的加權平均給出集群\mathcal{A} \cup \mathcal{B}和一個新集群X之間的距離：

d_{(\mathcal{A} \cup \mathcal{B}),X} = \frac

UPGMA 演算法生成的有根樹狀圖是一個超度量樹，該樹需要套用等速率的假設，也就是說根到每個分支尖端的距離皆相等。當尖端是同時採樣的分子數據（即DNA 、 RNA和蛋白質）時，超度量假設就等同於分子鐘假設。

示例
這個示例是基於JC69基因距離矩陣，該矩陣是根據五種細菌的5S 核糖體 RNA序列計算出來的，五種細菌如下所列 ：

枯草桿菌 Bacillus subtilis( a )

嗜热脂肪芽孢杆菌 Bacillus stearothermophilus( b )

魏斯氏菌 Lactobacillus viridescens( c )

無原枯草桿菌 Acholeplasma modicum( d )

藤黄微球菌 Micrococcus luteus( e )

第一步

  • 首次集群

假設有五個物件(a,b,c,d,e)和他們之間的相異矩陣D_1：

在這裡，D_1 (a,b)=17是最小值，所以將a和b集群。

  • 第一分支長度估計

令u表示現在a 和 b 的祖先。為了讓a 和 b 與 u等距，假設\delta(a,u)=\delta(b,u)=D_1(a,b)/2，這對應到了超度量的假設。在這個範例中：\delta(a,u)=\delta(b,u)=17/2=8.5

  • 第一次相異矩陣更新

然後將D_1更新成一個新的距離矩陣D_2（計算在下方），由於a和b的集群，該矩陣的尺寸減少了一行一列。（D_2中粗體表示的值是由加權平均計算出的新距離）

D_2((a,b),c)=(D_1(a,c) \times 1 + D_1(b,c) \times 1)/(1+1)=(21+30)/2=25.5

D_2((a,b),d)=(D_1(a,d) + D_1(b,d))/2=(31+34)/2=32.5

D_2((a,b),e)=(D_1(a,e) + D_1(b,e))/2=(23+21)/2=22

D_2中的斜體值不受矩陣更新影響，因為他們與第一個集群中的元素完全美有關連。

第二步

  • 第二次集群

現在重複前面的三個步驟，並從新的相異矩陣D_2開始

在這個矩陣中， D_2 ((a,b),e)=22是D_2中的最小值，所以將(a,b)和元素e集成新群。

  • 第二次分支長度估計

令v表示節點(a,b)和e的祖先。由超度量假設可以得到a,b,e三頂點到v的距離相等，即：\delta(a,v)=\delta(b,v)=\delta(e,v)=22/2=11，從而可以計算出u到v的距離\delta(u,v)=\delta(e,v)-\delta(a,u)=\delta(e,v)-\delta(b,u)=11-8.5=2.5

  • 第二次距離矩陣更新

然後將D_2更新成新的距離矩陣D_3，數值計算如下：

D_3(((a,b),e),c)=(D_2((a,b),c) \times 2 + D_2(e,c) \times 1)/(2+1)=(25.5 \times 2 + 39 \times 1)/3=30

D_3(((a,b),e),d)=(D_2((a,b),d) \times 2 + D_2(e,d) \times 1)/(2+1)=(32.5 \times 2 + 43 \times 1)/3=36

第三、四步
重複上述動作可以得到D_3是

D_4是：

UPGMA樹狀圖
這裡顯示了完成的樹狀圖。它是超度量的，所有尖端（ a到e ) 與r等距離 :

\delta(a,r)=\delta(b,r)=\delta(e,r)=\delta(c,r)=\delta(d,r)=16.5

這個樹狀圖的根是它最深的節點r 。

時間複雜度
構建 UPGMA 樹的算法有O(n^3)時間複雜度。使用一個堆維護兩個即群之間的距離可以使時間達到O(n^2 \log n) . 另外Fionn Murtagh 提出了一個O(n^2)時空複雜度的算法。

参见

  • 鄰接法
  • 集群分析
  • 单链接聚类
  • 完全连锁聚类
  • 層次即群
  • DNA进化模型
  • 分子鐘

外部連結

#生物信息学算法 #计算系统发生学 #系统发生学

评论 (0)

  • 还没有评论，来抢沙发吧。