（计算机应用技术专业论文）基因数据的动态聚类分析研究.pdf

上海人学硕士学位论文 摘要 生物学和医学的迅速发展以及基因芯片的逐步实用化都使得同时比较和研 究大量基因的特性成为可能，随之产生了海量的基因数据。通过分析这些数据 可以获得对人类有益的有关生物结构和功能的信息，对基因数据的分析研究己 成为生命科学、数学科学与计算机科学等学科非常活跃的交叉课题之一。聚类 分析是基因数据分析的一种重要手段，本文着重研究基因表达数据和基因序列 数据中的聚类分析算法。 针对目前常用的基因表达数据聚类分析算法中存在的参数依赖性强，并且 在整个聚类过程中类的数目始终保持不变的缺点，本文引入动态调整聚类个数 的思想；针对不能对空间中有部分重叠的点进行有效的分类从而不能得到全局 最优的聚类结果，本文进一步引入伪f 统计量，提出了一种基于多维伪f 统计 量的动态k 均值聚类算法。根据用户要求的聚类次数，每次开始于基因表达数 据中两两基因间在多维表达水平下的相似度矩阵，动态地选取一定数目的基因 作为初始聚类群，根据离差平方和法，不断精练初始聚类群，从而使得聚类个 数不断地变化，且动态地向正确的聚类个数逐渐收敛。该算法能保证最终聚类 结果类内散布矩阵之迹达到最小，把多维空间的数据点有效划分为具有特定数 目的不同的类，给出最佳聚类个数。 基于图b a g 的聚类算法是基因序列数据分析中经典的聚类算法，但在该算 法中相似分数阀值初始值和最长公共子串最小长度阀值如何确定没有明确给 出，本文提出了一种基于比对相似度动态矩阵s z d m 的聚类算法，利用动态矩 阵来表示序列间的匹配关系，明确给出了确定相似度分数阀值和最长公共子串 的最小长度阀值的方法，使得算法具有较好的聚类j 下确率。 在分析常用的聚类分析算法的基础上，本文提出了一种新的聚类分析方法： 基于交集的统计改进的组合聚类算法s c c a ( s t a t i s t i c a lm e n d e dc l u s t e r i n g c o m b i n a t i o na l g o r i t h mb a s e do ni n t e r s e c t i o n ) 。算法借鉴了统计学的思想，对边 缘对象进行统计分类。给定同一数据集的不同聚类结果，此算法先求出不同聚 类结果中每个分类的对应关系，然后计算这几个聚类结果对应分类的交集，对 v 上海人学硕l - 学位论文 剩余的有争议对象进行统计，最后把统计后仍未确定归属的对象分配给最近对 象所在的分类中，或者不经过统计直接将有争议的对象分配给最近对象所在的 分类。 本文对上述研究进行了验证和分析。实验结果表明，基于多维伪f 统计量 的动态k - 均值聚类算法可以动态地调整聚类个数，给出了最佳聚类数目；基于 比对相似度的动态矩阵的序列聚类算法可以获得比较好的聚类正确率；基于交 集的统计改进的组合聚类算法聚类质量优于组合前的任意一个算法。 关键词：生物信息学：k - 均值聚类；比对相似度；组合聚类算法； 上海大学硕士学位论文 a bs t r a c t t h er a p i dd e v e l o p m e n to fb i o l o g ya ni a t r o l o g ya sw e l la st h es t e p - p r a c t i c a l i t yo fg e n ec h i pm a k e c o m p a r e i n gs y n c h r o n o u s l ya n dr e s e a r c h i n gag o o dm a n yg e n e s c h a r a c t e r i s t i c sp o s s i b l e ，t h e r e s u l to fw h i c ha r ev a s tg e n e s w ec a ng a i ns o r t i ei n f o r m a t i o na b o u tb i o l o g ys t r u c t m ea n d f u n c t i o nb ya n a l y z i n gt h e s ed a t a n o wa n a l y z i n ga n dr e s e a r c h i n gg e n ed a t ah a v eb c p 。o m ev e r y a c t i v ec r o s sp r o b l e mo fl i f es c i e n c e s 、m a t h e m a t i c sa n dc o m p u t e rs c i e n c e c l u s t e r i n gi si m p o r t a n t m e a n st oa n a l y s eg e n ed a t a t h i sp a p e re m p h a s i z e so nr e s e a r c h i n gc l u s t e r i n ga n a l y s i sa l g o r t h i m s o fg e n ee x p r e s s e dd a t aa n dg e n es e q u e n c ed a t a a tp r e s e n tm o s tc l u s t e r i n g a n a l y s i sa l g o r t h i m so fg e n ee x p r e s s e dd a t as t r o n g l y d e p e n do i l p a r a m e t e r sa n dt h ec l u s t e rn u m b e ri sc h a n g e l e s s c o n s i d e r i n gt h i sd e f e c t s ，w ei n t r o d u c ea ni d e a t oa d j u s tc l u s t e rn u m b e rd y n a m i c l y ；i no r d e rt oc l a s s i f yp a r t l yo v e r l a p p e dd o t se f f e c t i v e l ya n dt o g a i nb e s tc l u s t e rr e s u l t s ，w ei n t r o d u c ef a k ef - s t a t i s t i ca n dp r o p o s e a d y n a m i c k - m e a n s c l u s t e r i n ga l g o r i t h m b a s e do nm u f t i - d i m e n s i o nf a k ef - s t a t i s t i cw i l lb ea d v a n c e di nt h i s p a p e rw h i c hb e g i n sw i t ht h es i m i l a rm a t r i xo fg e n e sa tm u l t i d i m e n s i o ne x p r e s s i o nl e v e l se a c h t i m ea i m e da tt h ec l u s t e r i n gc y c l e sr e q u i r e db yu s e r sa n ds e l e c td e f i n i t e dn u m b e ro fg e n e s d y n a m i c l yf o ro r i g i n a lc l u s t e r i n gg r o u p s t h e nw es h o u l dr e f i n et h eg r o u p sc o n t i n u o u s l yb yu s e o ft h eo f fd i s p a t c hs q u a r es u ms ot h a tc l u s t e rn u m b e rw i l lc h a n g ea n dc o n s t r i n g ec o n t i n u a l l yt o t h eb e s tc l u s t e rn u m b e rd y n a m i c l y t h i sa l g o r i t h mc a ne 1 1 s u r eal e s ti n n e r - c l u s t e rd i s p e r s em a t r i x t r a c eo ff i n a lc l u s t e r i n gr e s u l t sa n dc a np a r t i t i o nt h ep o i n t si nm u f t i - d i m e n s i o nt od i f f e r e n t c l u s t e r sw i t hs p e c i a ln u m b e r sa n dg e tb e s tc l u s t e rn u m b e r m a pb a gc l s t e r i n ga l g o r i t h mi sac l a s s i c a lc l u s t e r i n ga l g o r i t h mf o rg e n es e q u e n c ed a t a b u tt h i s a l g o r i t h md o e sn o te x p l a i nt h ei n i t i a lv a l u eo fc u t o f fa n dt h ev a l u eo f t h r e s h o l dd e f i n i t e l y i nt h i s p a p e rw ep r o p o s eac l u s t e r i n ga l g o r i t h mb a s e do ns z d m ( s i m i l a rz s c o r e sd y n a m i cm a t r i x ) w h i c hi sb a s e do nt h es i m i l a rz s c o r e sb e t w e e ns e q u e n c e sa n du s ed y n a m i cm a t r i xt od e n o t et h e r e l a t i o nb e t w e e ns e q u e n c e s t h ep a p e ra l s em a k e ss u r et h ei n i t i a lv a l u eo fc u t o f f , t h ev a l u eo f t h r e s h o l dd e f i n i t e l ya n dt h em e t h o do fh o wt od i v i d e u n i t ec l a s s e s8 0t h a tt h i sa l g o r i t h mh a s h i g h e rc l u s t e r i n gc o r r e c t n e s s v i i ， 上海人学硕j ：学位论文 b a s e do nt h ea n a l y s i so nc o m m o nc l u s t e r i n ga l g o r i t h m ，an e wc l u s t e r i n gm e t h o di sp r o p o s e d ：a s t a t i s t i c a lm e n d e dc l u s t e r i n gc o m b i n a t i o na l g o r i t h mb a s e do ni n t e r s e c t i o n g i v ed i f f e r e n t c l u s t e r i n gr e s u l t so ft h es a m ed a t ac o l l e c t i o n ，f i r s tc a l c u l a t et h er e l a t i o nb e t w e e nt h ec l u s t e r i n g r e s u l t s ，t h e nc a l c u l a t et h ei n t e r s e c t i o no ft h e s er e s u l t s ，c o u n tt h ed i s p u t e do b m t sl e f t , f i n a l l y d i s t r i b u t et h er e m a i n e rt ot h ec l o s e s tc l u s t e r a r c rv a l i d a t e da n da n a l y z e d , t h ee x p e r i m e n tr e s u l t ss h o wt h a ttd y n a m i ck - m e a n sc l u s t e r i n g a l g o r i t h mb a s e do i lm u 衔- d i m e n s i o nf a k ef s t a t i s t i c sc a na d j u s tc l u s t e rn u m b e rd y n a m i c l ya n d c a nm a k es u r et h eb e s to fa hc l u s t e r i n gn u m b e r c l u s t e r i n ga l g o r i t h mb a s e do ns z d m ( s i m i l a r z s c o r e sd y n a m i cm a t r i x ) h a sh i g h e rc l u s t e r i n gc o v r e c t n e s s s t h ec l u s t e r i n gq u a l i t yo ft h e s t a t i s t i c a lm e n d e dc l u s t e r i n gc o m b i n a t i o na l g o r i t h mb a s e do ni n t e r s e c t i o ni sb e r e t t h a na n y o t h e rc l u s t e r i n gm e t h o db e f o r ec o m b i n a t i o n k e yw o r d s ：b i o i n f o r m a t i c s ；k - m e a n sc l u s t e r i n g ；s e q u e n c e c o m p a r i o n ；c l u s t e r i n gc o m b i n a t i o na l g o r i t h m ； v i i i 上海大学硕十学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：靼日期：丛 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期：型堡：型 卜海人学硕士学位论文 1 1 研究动机与意义 第一章绪论 自上世纪9 0 年代以来，生命科学经历了前所未有的高速发展，为了处理随之而 来急剧增加的生物信息，人们巧妙的将生命科学与信息技术结合起来，诞生了- - 1 7 新的学科一生物信息学。生物信息学是一门交叉学科，它综合运用了以计算机技术 为代表的信息学和生命科学的知识来对生物信息进行收集、处理、分析，并最终获 得所研究生物数据的生物学意义。目前生物信息学的研究对象主要是功能基因组学 和蛋白质组学，其主要任务是分析研究生物分子数据中所蕴涵的各种信息，特别是 从基因组的整体水平上对基因的活动规律进行阐述，研究细胞内全部蛋白质的组成 及其活动规律。 随着分子生物学和现代医学的迅速发展，特别是人类基因组计划的实施和完成， 人类已经获得大量的生物分子数据，成百上千的生物学数据库迅速出现和成长，并 且其积累速度仍在不断提高，如何利用好获得的数据并挖掘出隐藏在其中的对人类 有用的信息则是一个迫切需要解决的问题。数据挖掘j 下是一种能够从大量数据中提 取有用的、具有潜在效用知识的技术，且已经在生物信息学领域崭露头角，逐渐成 为生物信息处理的有效方法之一。 分子生物学研究的重大突破，尤其是核苷酸序列研究的进步使得生物系统分类 的基础发生了重大的变化，分类系统已经或正在随着分子标准的不断渗入而完善。 所谓分子标准主要是指建立在核苷酸分析技术基础上的分类方法，它要求生物的序 列化，以核苷酸序列为基础研究各种生物学中的重大问题。基因序列聚类把目标序 列放入已知功能或相对同源的类里，这样就可以利用已知功能的基因推测同一类中 未知功能基因的功能。基因聚类分析还有助于发现一组序列之间的差异以及相似性 关系，以便对一个基因家族的特征有基本的了解，在基因序列的研究中聚类分析已 经成为一种普遍采用的方法，对数量巨大的核苷酸序列进行分类分析日渐成为目前 生命科学研究的重点。 数据挖掘中的聚类分析技术能够将具有某种相似性的对象聚集到一起，这些对 象构成了功能相近或者结构相关的分组，研究这些分组对于从已知功能和结构的对 上海大学硕士学位论文 象推断出未知对象的可能功能和结构具有极其重要的意义。 1 2 研究目的 多年来人们一直把生物学当作是一门实验科学，对生物学的研究主要依赖于对 实验数据的分析和处理，但是随着生命科学和计算机技术的迅猛发展，生物数据积 累速度不断加快，而且各种类型的生物数据数量巨大，特别是d n a 序列数据以千 兆计，传统的分析方法已经远远不能满足研究的需要，这就要求采用更新的方法和 工具来对生物数据进行处理和分析。生物信息学将生命科学与信息技术，尤其是计 算机与网络技术结合，使得人们能够系统的、有针对性的对海量数据进行研究，在 指导实验、精心设计实验方面将会发挥重要的作用。科学家预言：生物信息学将是 2 l 世纪生物学的核心。 分子生物学的一个普遍的规律是序列决定结构，结构决定功能。在对基因序列 相似性的研究过程中时，我们希望根据基因序列的相似性推测出序列之间结构和功 能的相似性。如果基因序列之间有相当的同源性，那么它们之间就可能有功能上的 高度相似性。利用同源比较算法，将待检测的新基因序列在d n a 序列数据库中序 列进行检索后，可以得到一系列与新基因同源性较高的基因或片段，这些基因和片 段已知的功能信息就为进一步研究新基因功能提供了具有重要参考价值的导向。利 用数据挖掘的聚类分析技术寻找同源序列就是要通过一系列的方法将待测基因序 列之间的差异标准化，比较序列的相似度来发现功能和结构相似的序列。 目前世界上有3 个相互联系的组织维护各自的d n a 数据库，他们分别是美国 的国家生物技术信息中心州c b i ) 、欧洲生物信息学研究所( e b i ) 和r 本d n a 数据库 ( d d b j ) ，这些中心和全球的基因组研究实验室通过互联网联系相互合作，各数据库 中的数据也基本保持同步。作为生物信息处理的工具之一，数据挖掘技术能够对分 布式的生物数据进行清理和语义集成，消除了数据异构和冗余的问题，为展开大规 模研究提供了必备的条件。在序列分析、蛋白质结构预测和基因表达分析等生物学 研究的热点领域也已经开发出多种有意义的数据挖掘模式、挖掘算法，并取得了良 好的效果。数据挖掘技术因其在大规模数据处理方面的卓越能力必将在生物信息学 的研究中占据越来越重要的地位。 2 上海人学硕士学位论文 1 3 研究内容 本文以聚类分析算法在生物基因序列和基因表达数据两个领域的应用为研究目 标。首先通过研究分析这两个领域中已经存在的聚类分析算法的优缺点，提出了基 于m p f 统计量( m u l t i p s e u d of s t a t i s t i c s ，多维伪f 统计量) 的动态k 均值聚类算法 和基于比对相似度动态矩阵s z d m ( s i m i l a rz s c o r e sd y n a m i cm a t r i x ) 的聚类算法，在 此基础上设计并实现基因表达数据聚类分析模型和基因序列数据聚类分析模型，并 且在基因表达数据聚类分析模型模型中利用f o m 方法、修正的( a d j u s t ) f o m 方法以 及e n t r o p y ( 熵) 评判法等评价系统对聚类结果进行评价分析，在基因序列数据聚类分 析模型中采用边缘指标( r a n di n d e x ) 方法以及修正的边缘指标( a d j u s tr a n di n d e x ) 方法 新提出的聚类算法进行性能评价。在提出以上两种优化的聚类算法后，本文还提出 了一种基于交集的统计改进的组合聚类算法( s c c a ，s t a t i s t i c a lm e n d e dc l u s t e r i n g c o m b i n a t i o na l g o r i t h mb a s e do ni n t e r s e c t i o n ) ，将两种或多种聚类方法综合起来以改 善聚类性能，并在算法中借鉴了统计学的思想，对有争议的分类结果进行统计，然 后将本算法应用到四个常用数据库中进行了测试，测试结果显示本算法的聚类质量 优于组合前的任一算法。 1 4 本文主要工作 本文主要研究的是聚类分析技术在生物基因序列和基因表达数据两个领域的应 用。聚类分析的关键技术主要集中在如何减小聚类算法实现的时间复杂度、空间复 杂度，如何提高聚类正确率以及如何确定最佳聚类个数等。这些问题的解决将对实 现生物基因的聚类分析有着重要的实际意义。为此，本文通过研究分析这两个领域 中己经存在的聚类分析算法的优缺点，提出了基于比对相似度动态矩阵s z d m 聚类 算法和基于m p f 统计量的动态k - 均值聚类算法，并应用于生物基因聚类中；在此 基础上还综合了多种聚类算法并借鉴统计学的思想，提出了一种基于交集的统计改 进的组合聚类算法。论文主要工作如下： 一、基因表达数据聚类分析及其性能评价 在研究分析常用算法的理论基础上，本文提出并重点研究分析基于m p f 统计量 的动态k - 均值聚类算法在基因表达数据分析中的应用。然后利用f o m 方法、修正 上海大学硕十学位论文 的f o m 方法和e n t r o p y ( 墒) 评判法来对这些聚类算法进行性能评价。 把这些聚类算法应用到基因表达数据分析中并对其性能进行评价分析，本文设 计实现基因表达数据聚类分析模型，主要完成以下几个功能： 1 设计实现己有的分析基因表达数据的聚类算法。 2 对已有分析基因表达数据的聚类算法进行算法改进，提出了动态k 均值聚 类算法，它是对k 均值方法的改进，可以动态地确定类的个数。 3 在动态k - 均值聚类算法中引入了m p f 统计量，研究了它如何对空间中有部 分重叠的点进行有效的分类以及如何确定最佳聚类数目。 4 利用性能评价指标对基于m p f 统计量的动态k 均值聚类算法和常用的几种 聚类算法进行比较和评价。 二、基因序列数据聚类分析及其性能评价 在研究分析基于图b a g 的聚类算法的理论基础上，本文提出并重点研究分析基 于比对相似度动态矩阵s z d m 聚类算法在基因序列数据分析中的应用。采用h u b e r t 和a r a b i e 提出边缘指标( r a n di n d e x ) 和修正的边缘指标( a d j u s t _ r a n di n d e x ) 用以评判 聚类质量。把该算法应用到基因表达数据分析中并对其性能进行评价分析，本文设 计实现基于比对相似度动态矩阵的聚类分析模型，主要完成以下几个功能： 1 在对己有的基于图b a g 的基因序列分析算法进行分析的基础上提出了基于 比对相似度动态矩阵s z d m 的聚类算法，动态矩阵的大小随数据库中序列数目而变 化，并给出了确定c u t o f f 初始值和t h r e s h o l d 的方法。 2 该聚类分析系统先通过查询检索获得基因序列数据，即通过因特网上的序列 提取系统( s r s ) n 务完成，基于的数据库是欧洲生物信息学研究所( e b i ) 维护的 e m b l 核酸序列数据库，其中用的是s r s 的e x t e n d e dq u e r yf o r m 进行查询检索基 因序列数据的。 3 序列比对利用的是经典的多序列比对算法c l u s t a l w 和相似性比对算法 f a s t a 。 4 利用s z d m 聚类算法对比对后的序列进行分析。 5 利用a d j u s tr a n d 指标方法来对该系统进行性能评价分析。 三、基于交集的统计改进的组合聚类算法及其性能测试 4 上海大学硕j ：学位论文 1 本算法借鉴了统计学的思想，对有争议的结果进行统计。在总结自组织映射 网络算法、k - 均值算法和微粒群优化算法的基础上，将多种聚类算法的结果通过取 交集的方法进行组合。 2 将本算法与自组织映射网络算法、k - 均值算法和微粒群优化算法同时应用到 4 个数据库中进行测试。 1 5 本文组织结构 全文分为六章，主要内容如下： 第一章概述了本文的研究动机、目的、内容、主要工作和组织结构等。第二章 详细介绍了研究的背景知识及研究现状，包括生物信息学、数据挖掘、聚类分析技 术的研究进展。第三章首先介绍了基因表达数据方面的聚类分析算法，分析了几种 常用聚类算法的优缺点，针对其中的不足提出了一种新的聚类算法一基于m p f 统 计量的动态k 均值聚类算法。接着引入评价指标体系，详细介绍经典的评价指标方 法：f o m 方法、修j 下的f o m ( a d j u s t _ f o m ) 方法和e n t r o p y ( 熵) 评判法。最后设计实 现一个基因表达数据聚类分析模型，对系统的设计和主要功能的实现作了全面的描 述，并根据实验结果和性能评价指标对聚类算法进行评价分析。第四章首先介绍了 基因序列数据方面的聚类分析算法，分析了聚类算法的优缺点，针对其中不足，提 出了一种新的聚类算法一基于比对相似度动态矩阵s z d m 的聚类算法。接着详细介 绍了h u b e r t 和a r a b i e 提出的修正的边缘指标。最后设计实现一个基于比对相似度 动态矩阵的聚类分析模型，对系统的设计和主要功能的实现作了全面的描述，并根 据实验结果和性能评价指标对聚类算法进行评价分析。第五章在分析常用的聚类算 法的基础上提出了一种基于交集的统计改进的组合聚类算法。然后将此算法与几种 常用的聚类算法一起应用到四个不同的数据库中进行测试。测试结果显示本算法能 明显提高聚类质量。第六章最后对全文进行了总结和展望。 l 海大学硕r 二学位论文 第二章背景知识及研究现状 2 1 生物信息处理中的数据挖掘 2 1 1 数据挖掘定义 数据挖掘( d a t am i n i n g ) 3 4 1 是数据库知识发现的精髓，指的是从大型数据库或数 据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在的和有用的 信息。是一个从存有海量信息的数据库中识别出新颖有效、潜在有用的并最终可理 解的非平凡知识的过程。这些数据可以是结构化的，如关系数据库中的数据，也可 以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。 发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以进 行数据自身的维护。数据挖掘借助了多年来数理统计技术和人工智能以及知识工程 等领域的研究成果构建自己的理论体系，是一个交叉学科领域，集成了数据库、人 工智能、数理统计、可视化、并行计算等技术。 数据挖掘的本质就是知识发现( k d d ) ，文献f 8 1 对数据挖掘的基本过程和主要步 骤进行了详细的介绍( 如图2 1 ) 。它融合了数据库技术、智能技术、模式识别和统计 学等众多学科领域的理论与方法，形成了完整的数据集成、知识挖掘、模式评价和 验证理论与方法。数据挖掘的主要任务包括关联规贝j j ( a s s o c i a t i o nr u l e s ) 、分类 ( c l a s s i f i c a t i o n ) 、聚类( c l u s t e r i n g ) 、序列模式( s e q u e n t i a lp a t t e r n s ) 等。 重新精化数据和问题 定抽净 数 算 进评 使 义取化 据 法行价用 问 +o斗。斗斗 数数引规挖结结 题 据据 擎则掘果果 图2 1 数据挖掘的基本过程和主要步骤 f i g u r e2 1p r o c e s so fd a t am i n i n g 6 上海大学硕1 ：学位论文 数据挖掘研究经过十余年的发展，初期蓬勃的数据挖掘算法研究使各种数据挖 掘技术都拥有众多的算法，这些算法各具特色，涉及了统计、人工智能、机器学习、 数字信号处理等各领域的成果，数据挖掘以其丰富、灵活的分析功能和强大的分析 能力向各行业渗透，逐步转向应用研究，结合应用领域的特色而得到发展。 2 1 2 应用及研究现状和进展 数据挖掘技术目前被应用到生物信息学领域并取得了相当大的成功。数据挖掘 技术主要功能在于从指定数据库中找到模式类型，在生物信息处理领域中，可以发 现的知识模式主要有：概念类别描述、关联分析、分类和预测、聚类分析、孤立点 分析以及演变分析。我们可以从以下几个方面得到应用： ( 1 ) 在d n a 数据分析中，由于广泛多样的d n a 数据高度分散，随机地生成与 使用，对这种异构和广泛分布的基因数据库的语义集成就成为一项重要任务，以便 于对d n a 数据库进行系统而协同的分析，而数据挖掘中的数据清理和数据集成方 法将有助于基因数据集成和用于基因数据分析的数据库的构建。 ( 2 ) 目前基因表达是研究热点，尤其是那些多基因联合控制的特性受到了人们 更多的关注，例如大部分致病因素不是由单一基因引起的，而是多基因组合起来共 同作用的结果。关联分析方法可用于帮助确定在目标样本中同时出现的基因种类。 ( 3 ) 可视化工具和遗传数据分析的研究，基因的复杂结构和序列模式通常可以 由各种可视化工具以图、树、晶格和链的形式展现，这种可视化的结构和模式方便 了模式理解、知识发现和数据交换，目前有许多学者从事这方面的研究。 ( 4 ) 数据挖掘中的关联分析是目前糖尿病数据库这类多维数据分析课题中应用 最广泛和有效的强有力的工具【2 6 1 。上海同济大学附属医院的冯波等人用统计相关分 析研究糖尿病患者肌肉组织和脂肪组织含量与骨密度之间的联系，得出高肌肉和高 脂肪脂肪含量可降低患者骸骨骨折危险性的结论【2 7 1 ；t e x a s 健康科学中心的s h a hb 分析了糖尿病患者年龄、性别和骨密度之问的关系【2 8 】；h a r r i sn d 和ir e l a n dr h 在 研究中运用时间序列关联分析发现，q t 间期和i 型糖尿病患者夜间血糖浓度有关， 并指出修正后的q t c 可能可以用于预警患者在夜间碎死的发生【2 9 】。 7 上海人学硕上学位论文 ( 5 ) 聚类分析的研究及应用，对于采集到的生物信息进行处理的一个重要模块 就是聚类，即把数据划分为一系列有意义的子集。聚类技术主要包括传统的模式识 别方法和数学分类法，如决策树归纳、贝叶斯分类、神经网络技术、k 一中心聚类、 基于知识的案例推理、遗传算法、粗糙集和模糊逻辑技术等【”】。斯洛文尼亚的 m i l a n z o r m a n 和m a s u d ag 等人在用数据挖掘技术对基因数据库进行详细分析的同 时还专门探讨了从这类缺乏先验知识的海量数据中采用决策树和关联规则算法的 效率及其改进方法。 聚类分析是进行数据挖掘的重要的手段之一，本文将着重对基因数据进行聚类 分析研究。 2 2 生物信息处理中的聚类分析技术 2 2 1 基本概念 聚类就是把一组个体按照相似性归成若干类别，即“物以类聚”。它的目的是使 得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可 能的大。 ，。 聚类分析是一种探索性的数据分析方法，算法根据目标研究对象( 个体) 的属性 数值，采用数学方法对其进行分类和整理，然后通过对类内个体的共性及类间个体 的差异作进一步的归纳，从而得到新的规律。 在目前的生物信息学领域的研究中，聚类分析受到广泛重视。在基因序列或表 达数据方面应用，一般是通过建立各种不同的数学模型，得到各种统计分析结果， 在此基础上确定不同基因在序列或表达上的相关性，从而找到未知基因的功能信息 或己知基因的未知功能。基因聚类是根据统计分析原理，对具有相同统计行为的多 个基因进行归类分析，使得被归为同一个簇或类的不同基因在功能上可能相似或有 关联。目前在生物信息学方面的研究主要有：手工分类法( m a n u a lc l a s s i f i c a t i o n m e t h o d ) ，非监督聚类法( u n s u p e r v i s e dc l u s t e r i n g ) ，混合聚类法( h y b 耐c l u s t e r i n g a p p r o a c h ) ，神经网络方法( n e u r a ln e t w o r ka p p r o a c h ) 。 、上海人学硕上学位论文 2 2 2 研究现状及进展 结构良好的基因表达数据可以为基因聚类提供良好的基础。目前在分析基因表 达数据方面涌现出了很多聚类算法，各自都有不同的特点：大多数聚类算法都是对 基因表达数据进行简单的聚类分析；文献【4 3 朋4 5 4 6 1 把聚类分析提升到了应用层次； 文献3 4 1 提出通过对基因表达数据进行聚类而得到不同的表达密度对基因进行表达 跟踪探测的聚类算法；文献【4 8 】提出的聚类算法对瘤和癌症基因表达数据进行分析从 而找出病变基因；文献【3 l 提出的聚类算法通过聚类分析从基因表达数据中提出不同 的模式；文献 4 9 5 0 1 在聚类分析前先对基因表达数据进行了数据预处理：文献1 则是 对基因表达图进行模式识别分析；文献【5 2 1 是对中枢神经系统不同时间映射的基因表 达数据进行聚类分析。目前最常用的聚类分析算法主要是：( 1 ) k - 均值聚类算法：( 2 ) 主成份分析( p c a ) ：文献【强1 对k 均值聚类算法和主成份分析进行了对比分析；( 3 ) 自组织图( s o m ) 聚类：文献 5 9 6 0 1 首次把自组织图应用到基因表达聚类分析中，文献 6 1 6 2 1 又在此基础上提出适应的加倍自组织图聚类分析算法；( 4 ) 层次聚类 ( h i e r a r c h i c a lc l u s t e r i n g ) ，包括平均连接聚类( a v e r a g el i n k a g ec l u s t e r i n g ) 、简单连接 聚类( s i n g l el i n k a g ec l u s t e r i n g ) 以完全连接聚类( c o m p l e t el i n k a g ec l u s t e r i n g ) - - 种，文献【“1 对自组织图和层次聚类算法进行了对比分析。而为了评价基因表达数据 聚类的质量，需要一定的评价指标，但该领域尚处于研究和探索阶段，在文献 6 5 , 6 6 , 6 7 , 6 8 中对指标评价体系进行了探索性的研究，但并没有形成一套公认的评价指 标体系。y e u n g 在文6 9 】中提出了质量因数f o m 方法，用以评判聚类质量。f o m 方 法完全基于类里的数据结构对类的质量作出评价。在f o m 方法的基础上，y e u n g 等又定义了调整f o m ( a d j u s t _ f o m ) 方法对聚类质量进行评价和分析。但这两种评 价方法都是内部评价标准，没有考虑外部信息，一些学者在f o m 评价的基础上引 入e n t r o p y 标准，提出了一种新的评价方法一e n 仃0 p y ( 熵) 评判法7 0 7 1 1 ，以提高评价 9 上海人学硕士学位论文 的准确性。 目前许多用于基因序列数据的聚类算法都是先读取和计算出所有序列间的匹配 情况，然后以序列为顶点，比对情况为边而建立相应的图。但有一些聚类算法所用 的序列间的匹配关系不是常用的数值型比较结果，如：c a s t o r 利用s p l a s h 模 式识别算法【“1 识别出的模式来表示序列间的关联关系。甚至在某些情况下，可以使 用二进制数来表示关联关系( 如用：0 表示不匹配，1 表示匹配) 。目前聚类分析算法 在基因序列数据方面的应用大致可以分为以下几类：文献【7 2 】通过聚类分析发现基因 序列中相似功能的片断：文献【7 3 】通过对蛋白质基因序列进行聚类分析发现可信赖的 基因序列区域；文献【7 4 1 通过聚类分析发现蛋白质基因序列中最接近的序列片断；文 献【”l 则是发现基因序列中不同功能和结构的主区域。最著名的是s u nk i m 等人提 出的基于b a g 图的聚类算法算法使用聚类单元引导类的分割，从而保证聚类结果 不会产生过多的类碎片。 在基因序列数据聚类方面的质量评价指标目前同样处于研究和探索阶段，没有 形成一套公认的评价指标体系，其中边缘指标( r a n di n d e x ) 是较经典的评价指标，该 方法是通过评估不同聚类算法的聚类结果之间的一致程度来对聚类结果质量进行 评价分析的。后来h u b e r t 和a r a b i e 提出了a d j u s t指标，其中引入了超几何分rand 布模型。m i l l i g a n 和c o o p e r 等人指出修正后的指标的有很好的健壮性。 2 3 本章小节 在目前的基因序列数据以及基因表达数据领域的研究中，数据挖掘技术，特别 是聚类分析技术受到广泛重视。本章首先简单介绍了数据挖掘和聚类分析技术的基 本概念，并讲述了在生物信息处理中这些技术的应用及研究现状和进展。 l o 上海大学硕士学位论文 第三章基因表达数据聚类算法研究 3 1 基因表达数据 基因表达数据是通过一些实验测量技术得到的，这些数据往往包含几千个基因 或基因片断和几十个属性。基因表达数据的实验测量技术最常用的有四种：哈佛大 学提出的c d n a ( c o m p l e m e n t a r yd n a ) m i c r o a r r a y 技术，基因芯片技术，序列分析 基因表达技术( s a g e ，s e r i a la n a l y s i so fg e n ee x p r e s s i o n ) ，实时p c r 技术。 下面是一段基因表达数据的片断，列是同一环境下所有基因的表达情况。通常 的基因表达数据是高维的，一般至少有八、九维，甚至多达一百维。 图3 1 基因表达数据 f i g u r e3 1d a t ao fg o n ee x p r e s s i o n 在相对大量的基因表达数据中，只有很少一部分基因己经知道它们的功能，而 大部分是不知道功能的。通过将已知功能的基因和未知功能的基因混合在一起放入 基因芯片，得到基因表达数据，再利用聚类技术将这些基因表达数据聚类，得到一 些聚在一起的类。同一类中通常是有己知功能的基因，这样我们就可以利用己知功 能的基因推测同一类中未知功能基因的功能。 借助基因芯片技术，我们可以得到“基因表达谱”矩阵 4 8 9 2 ，用它来描绘每个基 因在基因组中的动态功能，其中：行代表基因，列代表水平( 如，不同的组织、发展 阶段和处理) ，矩阵里的数字用来表示某一特定基因在某一特定水平上的表达强度， 我们称这样的数据表格为基因表达矩阵。对基因表达矩阵的分析，往往是比较矩阵 行和列的相似性或差别，如果发现两个行相似，我们可以推测它们对应的基因具有 上海大学硕士学位论文 协同调节和功能相关性。通过在不同水平的比较，我们可以发现哪些基因具有不同 的表达，并且可以研究不同化合物对它们的影响。 在基因表达数据分析方面已经有很多聚类算法，最常用的有：k 。均值、自组织 图、主成份分析和层次聚类方法。 由于聚类的目的就是预测未知基因的功能，所以通常在聚类的时候加入了一些 未知类别的基因。如果聚类算法得到的聚类结果总体和真实的类吻合，我们就可以 推断未知基因的与同类的己知基因有相似的功能。这种推断必须非常小心，如果聚 类算法得到的聚类结果总体上和真实的类相差太大，这些聚类结果就不具有推断的 价值。 上述就是基因表达数据以及聚类分析算法方面的相关背景知识，在下面的章节 中我们将详细介绍聚类算法并分析算法的效果。 3 2 聚类算法研究 在生物信息处理中，聚类方法应用最多的是基因表达数据。采用聚类算法分析 基因表达数据的一个重要原因是基因表达数据非常庞大，而生物学里己知功能的基 因相对很少。要利用相对很少的己知知识去推断未知的知识，分类方法并不非常适 合，因为用相对少的数据训练出来的模型不一定能代表整个数据空间的分布。聚类 是不需要先验知识，直接将具有相似表达性质的基因聚在一起，这对分析基因的功 能是一个非常简便有效的特性。 目前在分析基因表达数据方面常采用层次聚类、k 均值聚类、自组织图聚类、 主成份分析等几种常用的聚类算法，其中层次聚类又分为平均连接聚类i 简单连接 聚类以及完全连接聚类。k 均值聚类是最