跳转到内容

UPGMA

维基百科,自由的百科全书

UPGMAunweighted pair group method with arithmetic mean)是一种相对简单的层次聚类方法。这个方法存在另一种变体 WPGMA。这个方法的创始人被认为是SokalMichener[1]

演算方法

UPGMA 演法构建出一棵有根树(树状图)表现相似矩阵相异矩阵中的特征与结构。在算法里的每一步,距离最近的两个集群(子树)将被组合成一个更高级别的集群。任意两个集群 之间的距离,是由所有里的元素和所有里的元素的距离的平均值,即每个集群的元素之间的平均距离,其中 是该两个集群的基数(集合大小):

换句话说,在每一次组合成新集群的步骤中,可以由的加权平均给出集群和一个新集群之间的距离:

UPGMA 算法生成的有根树状图是一个超度量树,该树需要套用等速率的假设,也就是说根到每个分支尖端的距离皆相等。当尖端是同时采样的分子数据(即DNARNA蛋白质)时,超度量假设就等同于分子钟假设。

示例

这个示例是基于JC69基因距离矩阵,该矩阵是根据五种细菌的5S 核糖体 RNA序列计算出来的,五种细菌如下所列[2] [3]

枯草杆菌 Bacillus subtilis( )

嗜热脂肪芽孢杆菌 <i>Bacillus stearothermophilus</i>( )

魏斯氏菌 Lactobacillus viridescens( )

无原枯草杆菌 Acholeplasma modicum( )

藤黄微球菌 <i>Micrococcus luteus</i>( )

第一步

  • 首次集群

假设有五个物件和他们之间的相异矩阵

a b c d e
a 0 17 21 31 23
b 17 0 30 34 21
c 21 30 0 28 39
d 31 34 28 0 43
e 23 21 39 43 0

在这里,是最小值,所以将集群。

  • 第一分支长度估计

表示现在 的祖先。为了让等距,假设,这对应到了超度量的假设。在这个范例中:

  • 第一次相异矩阵更新

然后将更新成一个新的距离矩阵(计算在下方),由于的集群,该矩阵的尺寸减少了一行一列。(中粗体表示的值是由加权平均计算出的新距离)

中的斜体值不受矩阵更新影响,因为他们与第一个集群中的元素完全美有关连。

第二步

  • 第二次集群

现在重复前面的三个步骤,并从新的相异矩阵开始

(a,b) d
(a,b) 0 25.5 32.5 22
25.5 0 28 39
d 32.5 28 0 43
22 39 43 0

在这个矩阵中, 中的最小值,所以将和元素集成新群。

  • 第二次分支长度估计

表示节点的祖先。由超度量假设可以得到三顶点到的距离相等,即:,从而可以计算出的距离

  • 第二次距离矩阵更新

然后将更新成新的距离矩阵,数值计算如下:


第三、四步

重复上述动作可以得到

((a,b),e) c d
((a,b),e) 0 30 36
c 30 0 28
d 36 28 0

是:

((a,b),e) (c,d)
((a,b),e) 0 33
(c,d) 33 0

UPGMA树状图

这里显示了完成的树状图。[4]它是超度量的,所有尖端( ) 与等距离 :

这个树状图的根是它最深的节点

时间复杂度

构建 UPGMA 树的算法有时间复杂度。使用一个堆维护两个即群之间的距离可以使时间达到 . 另外Fionn Murtagh 提出了一个时空复杂度的算法。 [5]

See also

  1. ^ Sokal, Michener. A statistical method for evaluating systematic relationships. University of Kansas Science Bulletin. 1958, 38: 1409–1438.  温哥华格式错误 (帮助)
  2. ^ Erdmann VA, Wolters J. Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences. Nucleic Acids Research. 1986,. 14 Suppl (Suppl): r1–59. PMC 341310可免费查阅. PMID 2422630. doi:10.1093/nar/14.suppl.r1. 
  3. ^ Olsen GJ. Phylogenetic analysis using ribosomal RNA. Methods in Enzymology. 1988, 164: 793–812. PMID 3241556. doi:10.1016/s0076-6879(88)64084-5. 
  4. ^ Swofford DL, Olsen GJ, Waddell PJ, Hillis DM. Hillis , 编. Phylogenetic inference. Sunderland, MA: Sinauer. 1996: 407–514. ISBN 9780878932825. 
  5. ^ Murtagh F. Complexities of Hierarchic Clustering Algorithms: the state of the art. Computational Statistics Quarterly. 1984, 1: 101–113. 

外部链接