（应用数学专业论文）基于生成树基因表达数据聚类方法分析.pdf

东北走学硕士学位论文 基于生成树基因表达数据聚类方法分析 摘要 基因芯片的发明使得同时比较和研究大量基因的特性成为可能，随之产生大量 的基因表达数据。在分析基因表达数据时最先采用的是聚类分析技术。所谓聚类就 是按照事物的某些属性将事物聚成类，使类间的相似性尽量小，类内的相似性尽量 大。如何利用计算机科学中的分析技术，以发现基因表达数据中对生物学试验有指 导意义的信息或知识成为当前生物信息学研究的新课题。 我们对d o n g x u ，v i c t o r o l m a n 等人提出的将最小生成树理论用于基因表达数据 的清除m s t 长边聚类算法和全局最优算法进行了分析和研究，发现可以将其改进， 提出了直接聚类算法、局部最优聚类算法和最大生成树模糊聚类算法。新算法主要 采用了直接分类和递推计算的手段，简化中间计算过程，提高程序运行效率，进而 达到缩短运行时间的目的。我们通过实验对比分析，发现新算法比原算法运行快， 可以达到线性的运行时间。同时，文中也介绍了我们正在开发中的用于基因表达数 据的生成树聚类软件系统m s t c l u s t e r ，该系统能够把输入的基因数据依据指定的算 法进行分类，以及对已分类的两组基因进行比对。 本文主要研究了基于生成树理论用于基因的聚类算法一最小生成树聚类算 法，得到了一些新算法。第一章对基因表达数据聚类的现状进行了概述；第二章介 绍了与研究有关的定义和公式：第三章研究了基于最小生成树基因表达数据的聚类 算法，并提出了自己的新算法，以及新算法与原算法的实验结果对比分析；第四章 介绍了本人开发的用于基因表达数据的生成树聚类软件系统m s t c l u s t e r ：第五章作 了总结与展望。 关键词：聚类；基因表达数据；最小生成树；模糊聚类 东北大学硕士学位论文 a b s t r a c t a l g o r i t h m sf o rc l u s t e r i n gg e n ee x p r e s s i o n d a t ab a s e do ns p a n n i n gt r e e a b s t r a c t t h ei n v e n t i o no fg e n e c h i p sa l l o w su st os t u d ys i m u l t a n e o u sv a r i a t i o n so fg e n e sa t t h eg e n o m e w i d es c a l e c l u s t e r i n ga n a l y s i si st h ep r e f e r r e dm e t h o dt oa n a l y s i st h eg e n e e x p r e s s i o nd a t a c l u s t e r i n ga n a l y s i si st h ea r to ff i n d i n gg r o u p si nag i v e nd a t as e ts u c h t h a to b j e c t si nt h es a , l n eg r o u pa r es i m i l a rt oe a c ho t h e rw h i l eo b j e c t si nd i f f e r e n tg r o u p s a r ed i s s i m i l a r w i t ht h ee x p l o s i o no ft h eg e n ee x p r e s s i o nd a t a ，h o wt ou s et h ea n a l y s i s t e c h n o l o g i e si nc o m p u t e rs c i e n c et oa n a l y s i st h ed a t aa n dd i s c o v e ru s e f u la n di n s t r u c t i v e k n o w l e d g ef o rb i o l o g i c a le x p e r i m e n ti sa t t r a c t i n gn l o r ca n dm o r ea t t e n t i o n sf o rt h e b i o i n f o r m a t i c i a n s t h r o u g ham a s s i v ea n a l y s e sa n dr e s e a r c h ，w ef i n dt h ec u t t i n gl o n ge d g e sa l g o r i t h m a n dt h e “b e s tr e p r e s e n t a t i v ep o i n t ”g l o b a l l yo p t i m a lc l u s t e r i n ga l g o r i t h mf o rc l u s t e r i n g g e n ee x p r e s s i o nd a t ab a s e do nm i n i m u ms p a n n i n gt r e e ，w h i c hp u tf o r w a r db yd o n gx u a n dv i c t o ro l m a n ，c o u l db ei m p r o v e di no r d e rt os h o r tr u n t i m e b a s e do nt h e m ，w ep u t f o r w a r dd i r e c tc l u s t e r i n ga l g o r i t h m ，l o c a lo p t i m a lc l u s t e r i n ga l g o r i t h ma n dm a x i m u m s p a n n i n gt r e ef u z z yc l u s t e r i n ga l g o r i t h m t h e s en e wa l g o r i t h mm a i n l ya d o p td i r e c ts o r t a n dr e c u r s i o nc o m p u t a t i o n a li n s t r u m e n t s t h e yc a ns i m p l i f yc o m p u t a t i o n a lp r o c e d u r e ， a d v a n c ep r o g r a mr u ne f f i c i e n c ya n ds h o r tr u n t i m e a c c o r d i n gt ot h er e s u l t so ft h e e x p e r i m e n t s ，d i s c u s s i o na n de v a l u a t i o na r es h o w nf o rt h ea l g o r i t h m i ti sp r o v e dt h a t o p t i m u mc l u s t e r s c a nb eo b t a i n e da n do u ra l g o r i t h m sc a nr e a c hl i n e a rr u n t i m e a tt h e s a m et i m e ，t h i sp a p e ri n t r o d u c e st h ed e v e l o p i n gs o f t w a r es y s t e mm s t o c l u s t e rd e s i g nt o c l u s t e r i n gg e n ee x p r e s s i o nd a t a ，t h i ss y s t e mc o u l dc l a s s i f yt h ei n p u t t i n gg e n ed a t a a c c o r d i n gt os p e c i f i e da l g o r i t h m ，a n da l s oc a nc o m p a r et h et w oc l a s s i f i e dg r o u p so fg e n e t h i sp a p e rh a ss t u d i e da l g o r i t h m sf o rc l u s t e r i n gg e u ee x p r e s s i o nd a t ab a s e d0 i 3 m i n i m u ms p a n n i n gt r e ea n dp u tf o r w a r dt w oi m p r o v e dc l u s t e r i n ga l g o r i t h m s t h ef i r s t c h a p t e rg i v e sa no v e r v i e wo ft h ep r e s e n ts i t u a t i o nt h a tw es t u d y ；t h es e c o n dc h a p t e r i n t r o d u c e sr e l a t e dd e f i n i t i o na n df o r m u l a e ；i nt h et h i r dc h a p t e r , w ee s s e n t i a l l ys t u d y a l g o r i t h m sf o rc l u s t e r i n gg e n ee x p r e s s i o nd a t ab a s e do nm i n i m u ms p a n n i n gt r e ea n d i m p r o v et h e m ，t h e ng i v et h es i m u l a t i o ne x p e r i m e n tr e s u l t st h r o u t g hg e n ed a t a b a s e i nt h e f o m lc h a p t e r w ed e v e l o pas o f t w a r es y s t e mm s t - c l u s t e rd e s i g nt oc l u s t e r i n gg e n e e x p r e s s i o nd a t a t h ef i f t hc h a p t e rg i v e ss u m m a r i z ea n dp u tf o r w a r dab l u e p r i n t k e yw o r d s ：c l u s t e r i n g ；g e n ee x p r e s s i o nd a t a ；m i n i m u ms p a n n i n gt r e e ；f u z z yc l u s t e r i n g m 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写 过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文作者签名：究兄圆 日 期：。z 口口许弓爿t 目 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名：导师签名： 签字日期：签字日期： 东北大学硕士学位论乏 第一章引言 第一章引言 1 1 基因表达数据聚类的现状 随着人类基因组计划( h u m a ng e n o m ep r o j e c t ) 以及分子生物学、信息科学的 发展，d n a ，r n a 以及蛋白质等生物数据量空前增长。现在人类基因组计划的测序 工作已经完成，后基因组计划开始启动，功能基因组和蛋白质组的大量数据已开始 涌现，如何分析这些数据，从中获得生物结构、功能的相关信息是研究取得成果的 决定性步骤。生物信息学是在此背景下发展起来的综合运用生物学、数学、物理学、 信息学以及计算机科学等诸多学科理论方法的崭新交叉学科。1 9 9 5 年，在美国人类 基因组计划( h g p ) 第一个五年总结报告中给出了一个较为完整的生物信息学的定 义：生物信息学是包含生物信息的获取、处理、贮存、分发、分析和解释的所有 方面的一门学科。它综合运用数学、计算机科学和生物学的各种工具进行研究，进 而达到揭示数据所蕴含的生物学意义的目的。 基因和蛋白质是生命科学研究的主要对象。目前，人们着重于研究d n a 序列 信息、蛋白质结构信息，以及它们之间的相互作用。生命物质中的d n a 序列总体 被称为基因组。因此，首先对大量的基因表达数据进行分类【2 l ，有效地鉴别基因表 达数据的模式是研究d n a 序列的重要基础。利用数学、统计学和计算机科学等学 科提供的理论和方法，解决分子生物学中大量的计算和信息处理问题越来越受到人 们的重视。人们已经提出了一些用于处理基因表达模式聚类问题的计算机算法，如 分层聚类法 3 , 4 1 、k 平均值法【5 1 、自组织映射法6 t 等。这些算法已经被证明在许多应 用中是行之有效的。然而，它们也存在一些问题：首先，人们还没有严格证明它们 能够产生全局最优的簇；其次，k 平均值算法和自组织映射法不适合发现非凸面形 状的簇1 7 1 。本文研究了一种将多基因表达数据集作为图论中最小生成树 7 , 8 1 ( m i n i m u ms p a n n i n gt r e e s ，m s t ) 的聚类方法。在这种方法的基础上，提出了直接 聚类算法、局部最优聚类算法和最大生成树模糊聚类算法。 1 2 课题背景 c d n a 微阵列技术 9 a o , l i l 是获取关于遗传变异或基因功能的高通量方法，一个显 微玻片包括成百上千固定的d n a 点。通过这种技术可以获得基因在不同时段和实 验条件下的大量表达值。但随着这种试验的不断进行产生了大量的数据，而不同试 1 东北大学硕士学位论文 第一章引言 验设计所产生的结果也需要比较，所以急需采用精确有效的方法从这些数据中提取 生物学的联系，给基因分派功能和揭示生物遗传方式。了解基因功能和生物遗传方 式有助于我们理解正常与非正常条件下基因的功能机制。通过这些知识，可以预测 特定条件下可能发生的疾病【1 2 ，从而做到增强疾病预防能力，改善诊断过程等。所 有这些都能够有效地提高医护质量。对基因表达数据进行分析组织，通常会想到的 方法是运用聚类算法把表达模式相似的基因进行分组，从聚类结果推断基因的特定 功能和基因间的相互调控作用。 有许多聚类方法【1 3 , 1 4 , 1 5 , 1 6 1 已经应用到基因表达数据聚类分析当中，特别是y i n g x u ，v i c t o ro l m a n ，d o n gx u 8 ，1 7 ，1 8 ，1 9 1 等人将晟小生成树理论用于基因表达数据的聚 类，从而丰富了基因聚类的方法。但是他们的方法在时间性能上不是很理想，本文 正是基于此提出了新的算法。 1 3 研究的成果及意义 本文主要的分析对象是基因表达数据，并选择适合分析基因表达数据的聚类算 法对已有基因数据进行聚类。我们对d o n gx u ，v i c t o ro l m a n 等人提出的将最小生 成树理论用于基因表达数据的清除m s t 长边聚类算法和全局最优算法进行了分析 和研究，发现可以将其改进，提出了直接聚类算法、局部最优聚类算法和最大生成 树模糊聚类算法。新算法主要采用了直接分类和递推计算的手段，简化中间计算过 程，提高程序运行效率，进而达到缩短运行时间的目的。我们通过实验对比分析， 发现新算法比原算法运行快，从时间性能上有较大的提高，进而丰富了最小生成树 聚类算法理论。 另外，文中也介绍了我们正在开发中的用于基因表达数据的生成树聚类软件系 统m s t - c l u s t e r ，该系统能够把输入的基因数据依据指定的算法进行分类、以及对已 分类的两组基因进行比对。 本文的内容安排如下： 第一章对基因表达数据聚类的现状进行了概述。 第二章介绍了与研究有关的定义和公式。 第三章重点研究了基于最小生成树基因表达数据的聚类算法并提出新的算法， 以及新算法与原算法的实验结果对比分析。 第四章介绍了本人开发用于基因表达数据的生成树聚类软件系统m s t c i u s t e r 。 第五章作了总结与展望。 2 东北大学硕士学位论文 第二章预备知识 第二章预备知识 2 1 生成树理论介绍 生成树理论f 2 0 】是图论中最重要的理论之一，在诸多实际问题中得到了广泛的应 用。在图论中计算生成树的方法有很多，并且利用计算机处理，这些算法得到了长 足的发展。本文注意到图论中生成树理论对基因表达数据聚类所具有的长处和启发 性，因此选用该理论作为算法的基础。 图论是数学的一门分支，从1 7 3 6 年诞生后早期发展比较缓慢，到二十世纪中期 由于计算机技术的迅速发展，图论进入了高速发展的阶段，并广泛地运用于各种领 域。图能够简洁、方便、真观、生动和形象地描述许多自然现象和人类社会诸多问 题，包括物质结构、交通运输、信息传输和变化、经济管理和计算机科学等。图论 已成为研究自然科学、工程技术及社会科学的重要工具。图论涉及的图不是一般几 何中的图形，在图论中图的点线均被赋予独特的含义，用来表达某类事物之间的某 种联系，这些反映实际问题特性的点和线组成的集合就成为图论研究的对象。 ( 1 ) 图的基本概念 图论中将图定义为一个偶对g = ( v ，e ) ，其中v 表示顶点的集合，e 表示边的集 合2 。如图2 1 所示的图g 可以表示为：v = v j ，v 2v 3 ，v 4 ，v 5 ，v 6 ，v 7 ) ， e = 岛，e 2 ，e 3 ，e 4 ，p s ，e 6 ，e 7 ) 。 v 1 e i v 2 e 2 v 3 r e 3 - e 4 v 4 v 6 图2 1 图的基本概念( 无向图) f i g 2 1b a s i cc o n c e p t so f g r a p h ( u n d i r e c t e dg r a p h ) 如果实际应用中，图中的每条边具有方向时，图就成为有向图，那么边就是有 3 查韭查芏壁主兰垒堕查鱼三主j 型至查堕 向边，有向边p 用与其关联的两个顶点的有序对来表示，即e ( u ，v ) 表示边e 的起点是 m ，终点是v ，有向图g 如图2 2 所示。 v l p 1 v 2 e 2 v 3 7 7 旬 r 旦4 v 5 图2 2 图的基本概念( 有向圈) f i g 2 2b a s i cc o n c e p t so f g r a p h ( d i r e c t e dg r a p h ) 图2 2 表示为：g = ( 矿，e ) ，v = v l ，v 2 ，v 3 ) v 4 ，v 5 ，v 6 ) v 7 ) ， e = ( v 1 ，v 2 ) ，( v 2 ，v 3 ) ，( v 1 ，v 4 ) ，( v 2 ，v 4 ) ，( v ，v 5 ) ，( v 5 ，v 6 ) ，( v 5 ，v 7 ) ) 。 如果顶点v 是边e 的一个端点，则称边e 和顶点v 相关联，对于顶点“和v ，若 们e ，则称u 和v 是邻接的。 以上是图的集合表达法，也是研究图的基本方法。 随着计算机的应用深入，矩阵成为研究图论的有力工具，因此需要用矩阵来识 别和分析图。 对于图g ：( 矿，e ) ，构造一矩阵a = ( 嘞) ，其中胛爿v i 表示顶点数， = “凳苫e ，则称这样定义的矩阵彳是图g 的邻接矩阵。给出了图g 的邻接 矩阵就等于给出了图g 的全部信息。图的某些性质就可以从矩阵a 通过运算而得到。 定义2 1 图g ：( 矿，e ) 的一个顶点和边的交替序列= v o e l v l v “吼v t ，且边e ，的 端点为v 。和v 。，i ：1 ，二 2 k ，则称为一条途径( w a y ) 。v 0 和咋分别为2 的起点和 终点。 特蹦地，芦中所有的边均不相同，刚称其为道路( p a t h ) 。以v 。为起点v t 为终 点的道路成为v 。- v 。道路。 如果道路中v o = v ，称芦为回路，回路中没有重复边时称为简单回路。 定义2 2 对图g = ，e ) 来说，若图g 的两顶点“，v 之间存在一条道路，则称“ 4 东北大学硕士学位论文 第二章预备知识 和v 是连通的。 若图g 的任意两点连通，则称其为连通的，否则称其为非连通的。非连通的图 可分解为若干连通子图。 对于有向图，若边去掉方向后是连通的，则称其为连通的有向图。 若对于有向图的任意两顶点“和v 2 间存在“到v 的道路和v 到u 的道路时，称其 为强连通的。 没有重复边和自环的图叫做简单图。 ( 2 ) 树的基本概念 树是图论中最重要的概念之一，它是基尔霍夫在解决电路理论中求解联立方程 问题时首先提出来的。 给定一个图g = ( 矿，e ) ，如果它不合任何回路，就称为林，如果g 又是连通的， 即这个林只有一个连通分支，就称它为树。如图2 _ 3 就是简单的无回路连通图，即 树。 ， 旬 - e 4 v 5 v 4 v 6 图2 3 图的基本概念( 树) f i g 2 3b a s i cc o n c e p t so fg r a p h ( t r e e ) 定义2 3 一个不含任何回路的连通图称为树，用r 来表示，中的边称为树枝。 设? 是节点数为摊2 的树，则r 具有如下性质： ( a ) t 连通且无回路； ( b ) t 连通且每条边都是割边； ( c ) t 连通且有n 一1 条边； ( d ) t 的任意两节点间有唯一道路； ( e ) r 无回路，但在任意两节点间加上一条边后恰有一个回路。 ( 3 ) 赋权图及图的生成树定义 定义2 4 设图g = ( 矿，e ) ，对g 的每一条边( v i ，v ，) 赋以权，g 连同在它边上的权 5 旬 也眈 b 东北大学硕士学位论文 第二章预备知识 称为赋权图。 定义2 5 在一个无向连通的加权图g = ( v ，e ) 中，每一条边( v ，v ，) 都赋予权值 w ( v ，v ) ，从图g 中找出一棵生成树，若它的权值和最小，则称这棵生成树为图g 的 一棵最小生成树2 2 ，2 3 1 ( m i n i m u ms p a n n i n gt r e e ) ，简记作m s t 。若它的权值和最大， 则称这棵生成树为图g 的最大生成树盼2 3 1 ( m a x i m u ms p a n n i n gt r e e ) 。 当图g 含有权值相等的边时，将会有多棵最小或最大生成树。 v 4 r1r1 4 46 -4- v 62- 7 1 04 rr1 r 5 8 7 -4j- v 72- v 1 13j r 1r1 r1 214 - 3 -v8 1 j- v 1 23 j v 1 3 v 1 4 图2 4 图的基本概念( 赋权图) f i g 2 4b a s i cc o n c e p t so fg r a p h ( w e i g h t e dg r a p h ) 如图2 4 所示，就是一个赋权的连通图，图中各边都标注了所赋的权值，那么 该图具有的最小和最大生成树将由最小和最大生成树算法得到。 同时，可以看到本图的最小和最大生成树不只一个。 2 2 基因表达数据集的生成树表示 ( 1 ) 聚类的定义和分类 无监督的学习( u n s u p e r v i s e dl e a r n i n g ) 是在没有先验知识的情况下进行的学习。 一般来说无监督的学习方法可以分为两大类，即基于概率密度函数估计的直接方法 和基于样本间相似性度量的间接聚类方法【2 4 25 1 。在本文中主要讨论后一种聚类方法。 聚类从概念上可以分为两个不同的方法，盲目的或者叫句法聚类，和基于知识 的或者语义聚类。句法聚类是盲目的没有任何先验知识，没有限制的聚类；语义聚 类提前有一个规范约束算法如何搜索。 此外，聚类还可以分为简洁的和近似的聚类，分离的和有重叠的聚类【2 5 1 2 6 1 。简 洁的聚类是指严格按照样本值进行聚类，而近似的聚类允许对样本值进行模糊。分 离的聚类是指类与类之间不会有重叠部分，而有重叠的聚类则相反。我们现在通常 - 6 东北大学硕士学位论文 第二章预备知识 考虑的是盲目的、简洁的、分离的聚类算法【26 1 ，本文也正是研究这种聚类算法。 ( 2 ) 基于最小生成树聚类定义 令d 是数据集，p 代表d 中两个数据点之间的权值，则c d 形成d 中的一个 聚类，满足对于任意分割c = c 1 u c 2 到c 最近的点d ，d 芒d - c l 是来自c ：，通常记 作： a r g 艘 幽 p ( d ，c ) ic c 1 ) ) c z ( 2 1 ) 这里d c l 表示从j d 中除去所有c 中的点后的子集，称其为聚类的可分割条件，此 条件为一个集合成为聚类的必要条件。 ( 3 ) 距离度量方法 不同的问题需要采用不同的度量方法，一般采用欧几里得距离或其它距离度量 方法。本文采用欧氏距离公式和欧氏距离平方公式。 ，i m l p ( 吐，如) = i ( 碣。一d 2 ，) 2 ( 2 2 ) l i mj p ( 吐，d 0 = ( d l ，一吐，) 2 ( 2 3 ) ( 4 ) 用生成树表示数据 设d = d ， ，i = 1 , 2 ，h 表示数据集，d ，= ( d f l ，d 1 2 ，一。) 是数据的m 个属性。权 图g ( d ) = ( 矿，e ) ，其中点集v = d 。| d ，d ) ，边集e = ( d ，d ，) lv d ，d ，d ) ，则g ( d ) 是一个完全图a g ( d ) 中每条边( d i ，d ，) e 有一个表示距离的权值p ( 一，d j ) 。 有了上面的预备知识就可以得到下面的一个重要定理，这个定理说明了，基因 表达数据能够用生成树来表示。 定理2 6 2 7 一个基因表达数据有限集能够用最小生成树表示。 2 3 聚类技术在基因表达数据中的应用 ( 1 ) 基因表达数据 基因表达数据是从基因芯片试验2 8 1 中得到的，这些数据往往包含几千个基因或 基因片断和几十个属性。基因表达数据中的基因通常分为已知基因和未知基因。己 知基因就是己经知道功能的基因，未知基因则相反。当然这些基因的功能是通过翻 译到r n a ，并最终合成蛋白质实现的。我们所说的基因的功能也就是基因编码所对 应的蛋白质的功能。表2 1 是一段基因表达数据的片断。基因表达数据的行是一个 基因在不同环境下的不同的表达，列是同一环境下所有基因的表达情况。通常的基 7 东北大学硕士学位论文第二章预备知识 ( 2 ) 基因表达数据的聚类分析 在上面已经提到了相对大量的基因表达数据，只有很少一部分基因已经知道它 们的功能，而大部分是不知道功能的。通过将已知功能的基因和未知功能的基因混 合在一起放入基因芯片，得到基因表达数据。再利用聚类技术将这些基因表达数据 聚类，得到些聚在一起的类。同一类中通常是有已知功能的基因。这样我们就可 以利用已知功能的基因推测同一类中未知功能基因的功能。而该基因的真实功能是 否跟已知功能的基因一样，就需要生物学家用生物方法去验证。作为一个例子我们 考虑表2 2 中的数据集。通过聚类算法，表2 2 中的基因表达数据可以被分为c i = a ， b ，c 和c 2 = d ，e ，f ) 两个类，因为这个数据集是简单的二维数据，从图2 5 的数 据分布我们可以直观地评价这个聚类的好坏。 从这个例子来看通过聚类算法得到的聚类效果跟实际的自然组很匹配。但是， 在实际的基因表达数据分析中，通过算法得到的类与自然类并不是那么容易完美匹 配的。 8 东北大学硕士学位论文 第二章预备知识 表2 2 基因表达数据 t a b l e2 2g e n ee x p r e s s i o nd a t a n 芎 鲁 笔 a t t r i b u t el 圈2 5 数据分布 f i g 2 5d a t ad i s t r i b u t i o n 为了解释计算杌产生的聚类的效果，我们需要通过生物知识来验证这些聚类结 果。生物学中实际基因的自然类可以用一个树形结果来表示，如图2 6 ，g o ，g 4 是5 个自然类，每个类包括几个基因。例如g o 包括a ，b ，c 三个基因。这棵树就是 用来验证聚类结果的生物知识。 对图2 6 中的a ，b ，q 共1 7 个基因应用某种聚类算法，可以得到一个聚类结 果，如图2 7 。现在我们可以对应树中的生物知识验证聚类的结果。由于聚类的目的 就是预测未知基因的功能，所以通常在聚类的时候加入了一些未知类别的基因。如 果聚类算法得到的聚类结果总体和树中的自然类吻合，我们就可以推断未知基因的 与同类的已知基因有相似的功能。这种推断必须非常小心，如果聚类算法得到的聚 类结果总体上和树中的自然组相差太大，这些聚类结果就不具有推断的价值。如图 2 7 ，c 1 和c 4 与实际情况符合；c 2 中的g 属于错误聚类，实际应该是在c 3 中； 9 东北大学硕士学位论文 第二章预备知识 c 3 和c 5 中的r ，s 是未知的基因，由于总体上聚类结果和实际的自然组比较符合， 我们可以推断r ，s 可能分别属于g 2 ，g 3 自然组。 图2 6 实际基因的自然组( 生物知识) f i g 2 6t h en a t u r eg r o u po f t h eo r i g i n a lg e n e ( b i o l o g i c a lk n o w l e d g e ) 图2 7 聚类结果 f i g 2 7c l u s t e r i n gr e s u l t s 上述就是聚类算法在分析基因表达数据时的具体用法，在下面的章节中我们将 详细介绍聚类算法并分析算法的效果。 1 0 东北大学硕士学位论文 第三章生成树聚类算法及改进 第三章生成树聚类算法及改进 3 1 现有基于生成树聚类算法 3 1 1 生成树算法介绍 在计算图g = ( v ，e ) 的最小和最大生成树中，经典的串行算法有s o l l i n 算法【2 2 】， p r i m d i j k s t r a 算法以及k r u s k a l 算法 2 9 , 3 0 , 3 1 】。 这里先介绍一下常见的p r i m 算法和k r u s k a l 算法。 ( 1 ) p r i m 算法 p r i m 算法又称为边割法。算法开始时，生成树只有一个中心点，然后每次增加 一个节点到树上。增加节点的办法是找出已生成的树上节点中最近的一个节点，将 其连在树上。为确定下一个连到树上的节点，先要考察树外的节点集，依次计算该 节点集中的某一点至树上各点的边的权值，取最小或最大边。每一个树外节点都对 应一个最小或最大权边，在这些最小或最大权边之中再选一个最小或最大的边，将 其连在树上。 它的数学描述如下： s t c p l 设v 为v 的任一顶点，令s o ； v ) ，e o = o ，k = 0 ； s t e p 2 若s 。= v ，结束，以最为顶点集、e k 为边集的图即是g 的最小或最大生 成树：否则转s t e p 3 ； s t e p 3 构造【瓯，最】，若【砩，瓦】_ o ，则g 不连通，停止；否则，设珊( 吼) = m i n o j ( e ) ， 睢( s k ，墨】 e 七= v i v ：，v 女& g 竞c o ( e ) = m a x n ) ，e 七= v 吒，v s ，令s 川= s 女u v a ， p e f s k 品】 毛+ l = 乓u 溉) ，置= k + 1 ，转s t e p 2 。 ( 2 ) k r u s k a l 算法 k r u s k a l 算法又称避圈法。将图的所有边按其权值由小到大排列。从最短或最长 边开始，依次考察各边，连到树上不会形成回路，便加入该树，否则考察下一条边。 k r u s k a l 算法的数学描述如下： 设g = ( v ，e ，珊) 是一个无向网络，l v 卜以，i e i = m 。 s t e p l 把g 的边按权的大小顺序排列，即要求国( q ) c o ( e ：) s ( e ，) 或者 ( e 1 ) c o ( e 2 ) c o ( e 。) 。令瓦= ( v ，) ，f = l ，= 0 ； 1 1 ， 东北大学硕士学位论文 第三章生成树聚类算法及改进 s t e p 2 若t + e ，含有圈，转s t e p 3 ；否则转s t e p 4 ； s t e p 3 置i = i + 1 ，若i m 转s t e p 2 否则停止，g 中不存在支撑树； s t e p 4 令巧+ 1 = t + p ，并置，= j + l ： s t e p 5 若- ，= n - i ，则算法结束，i 是最小或最大树；否则转s t e p 3 。 3 1 2 最小生成树聚类算法 定义3 1g ( d ) 的生成树r 是g ( d ) 的连通子图，如果了 包含g ( d ) 的每一个结点 且丁不包含环。 最小生成树是生成树中总距离和最小的树。 定义3 2 最小生成树中属于同一类的子数据集我们称其为簇，用符号c 来表示。 定义3 3 一个簇的中心( c e n t e r ( 1 ) 定义如下： c e n t e r ( t f ) = 两1 d ( 3 1 ) 1 1 i ld e 其中，i 互l 表示第f 个簇中数据点的个数。 由定义( 2 1 ) 式，我们可以得到： 定理3 4 一个簇内部相邻数据点之间的距离小于不同簇数据点之间的距离。 因此我们能够发现同一个簇中的数据点用较短的边相连，而不同簇之间的点用 较长的边相连。恰好满足同一类中的数据点相似性较大不同类中的数据点相似性较 小的特性。如图3 1 所示： ( a ) 展小生成树表示基因数据 ( b ) 删除最长2 条边的聚类结果 ( a ) g e n ee x p r e s s i o nd a t ab a s e do r lm s t ( b ) c l u s t e r i n gr e s u l to fc u t t i n gt w ol o n ge d g e s 图3 1 基于最小生成树聚类思想 f i g 3 1c l u s t e r i n gi d e ab a s e do nm s t 定理3 5 阳设c 。和c 2 是簇c 中的任意两点，则从c l 到c ：的最小生成树路径p 上 1 2 东北大学硕士学位论文第三章生成树聚类算法及改进 所有点一定来自簇c 。 推论3 6 【8 】通过清除g ( d ) 最小生成树中具有最大距离的k 一1 条边可得到k 个 簇。 我们将现有的几种生成树聚类算法叙述如下： ( 1 ) 清除m s t 长边聚类算法 一个简单的准则函数是分割一个m s t 成为足个子树，使得所有子树的全部边距 离和最小。这个准则2 7 1 依据如下概念：具有较短边距离的两个点应属于同一个簇( 子 树) ，具有较长边的两个点应属于不同的簇，并将要被分割。 由推论我们就可以获得世个簇，显然他们是上述准则函数的全局晟优解，这个 算法是足够好的，只要不同簇之间点的边距离大于簇内点的边距离。然而，当不同 簇没有用长距离边而是一系列短距离边连接，或者当存在“噪声”和孤立点数据时， 这一简单的方法可能得不到最好的聚类结果。 为了自动决定应该进行多少次有效分割，可在分割算法中检测新产生的子树是 否为孤立点，通过消除孤立点并增加有效分割次数，最后获得正确的k 个簇。 ( 2 ) 重复聚类算法 分割最小生成树7 1 为世棵子树 i 篙。重复聚类算法跚的准则函数如下： k p ( d ，c e n t e r ( t t ) )( 3 2 ) i = 1d e t f 这个最优化算法可以使每个簇中心和它的数据点之间的距离最小化，这是处理数据 聚类问题的一个典型的准则函数。使用不同的距离时，中心( c e n t e r ) 有不同的值。 例如，使用欧几里得距离时，一个簇的平均值是它的中心。 重复算法以任意一个树的丘分割开始( 选择k 一1 个短距离边删除它们获得k 分 割) 并计算各个子树的中心。然后重复以下操作：对每一对相邻的簇( 通过树边连 接) 将它们合并为一个簇，在这个合并的簇中搜索所有的树边并清除，然后对合并 簇通过准则( 3 2 ) 式进行全局最优化二分割。 ( 3 ) 全局最优算法 全局最优算法【8 】定义如下：使用与准则函数( 3 2 ) 式稍微有点不同的准则函数。 重复聚类算法围绕每个簇的中心进行分组，而全局最优算法是围绕数据集“最佳代 表点”进行分组。最佳代表点不是事先选择的，而是最优化过程的结果。这个算法 先分割最小生成树为足棵予树，然后针对最优准则函数( 3 3 ) 式选择k 个代表， 1 3 - 东北大学硕士学位论丈 第三章生成树聚类算法及改进 p ( a ，d ，) ( 3 3 ) 具体叙述如下：对于一个给定的最小生成树7 1 ，需要分割r 为蜀个子树 五，正，) 且d id 2 , - d 。d ，使准则函数( 3 3 ) 式最小化。这里p ( ) 是距离函数。使用“代 表”而不是使用“中心”的原理是“中心”可能不属于该簇，即使很靠近它的聚类 数据点。若簇边界不是凸形状的，可能导致中心出现没有意义的结果。基于“中心” 的聚类算法不能产生希望的结果时，使用基于“最佳代表点”的算法能提供一个满 意的替换。簇形状接近凸面时，“代表”通常最接近中心数据点，此时两个准则函数 会导致相似的结果( 假设这个算法能发现全局最优解) 。 这个算法的基本想法可以解释如下：首先任选一个树结点作为根，将m s t 转换 成有根树( a h o 等，1 9 7 4 ) ，则所有树结点的父子关系被确定。 对于每一个树结点v ，定义s ( v ，k ，d ) 表示以v 为根的子树的准则函数( 3 3 ) 式 的最小值，在这一限制下，该予树分割成k 个子树，并且根为v 的子树的“代表” 是d 。通过定义，下面给出准则函数( 3 3 ) 式的全局最小值。 r a i n s ( r o o t ，k ，d ) ( 3 - 4 ) 在有根的m s t 中，v 的联) 值基于v 的子女的双) 值，边界条件如下：如果树结 点v 没有任何子女，则： 弧剐，= 篡n ：三： s ， 对于每一个有子女的结点v ，v 的联- ) 按下式计算： 厂、 h 心e 却5 蝎r a i n 羚m 删i n h ) 。l 。娶( v j , k j , d 卜毒s ( v j , k j , d ) + 烈v ，田j 。6 ) 这里s ( v ，k ，d ) = s ( v j ，k ，x ) ，c v 代表结点v 的所有子女集合，算法为所有v r ， k 【1 ，k 和d d 的组合计算s ( v ，k ，d ) 的值。 算法是基于s ( v ，k ，d ) 可以拆分为它的子女结点的甄) 值之和。上面的循环覆盖 了所有可能的这样组合。 ( 4 ) 改进的重复聚类算法 改进的重复聚类算法2 7 1 与重复聚类算法相似，是一种面向中心的聚类方法。它 是以最小生成树世分割开始( 选择k 一1 个短距离边，删除它们获得k 分割) 并计算 各个子树的中心c e n t e r ( t _ ，) ，j = 1 ，2 ，k 。删除树中所有的边，对于树中任意的点d i 东北大学硕士学位论文第三章生成树聚类算法及改进 计算 j = r a i n i ，( 吐，c e n t e r ( t j ) ) 1 ) 其中，i = l ，2 ，n ；j = 1 ，2 ，k 。 ( 3 7 ) 取，最大时，= j ，即函距离c p 以舯( 乃) 最远，则函属于l ，中的点a 与准则函数 ( 3 _ 2 ) 式相比这个算法更容易获得全局最优解。 3 2 直接聚类算法与局部最优聚类算法 3 2 1 直接聚类算法 我们对d o n g x u ，v i c t o r o l m a n 8 , 1 7 , 1 5 , 1 9 , 3 2 , 3 3 1 等人提出的将最小生成树用于基因表 达数据的聚类算法进行了分析和研究，发现可以将其算法进行改进，进而提出了 种新的算法一一直接聚类算法。此算法能缩短运行时间，提高效率。原算法的计算 流程如图3 2 所示，先构造最小生成树，然后再对最小生成树进行分割，得到k 个 聚类，计算每个聚类的误差平方和及g 值，进而确定最佳聚类数目。新算法计算流 程如图3 3 所示，中间省略了构造最小生成树的过程，简化口值的计算方法，进而 达到了缩短运行时间的目的。 新算法的详细描述过程如下： 厂、 (开始)