聚类分析方法

北京信息工程学院毕业论文（设计）用纸第1页第一章Microarray介绍1.1生物信息处理基于对生物体“硬件”和“软件”的认识,提出暂时地撇开生物的物理属性,着重研究其信息属性,从而进入到生物信息处理(关于生命硬件的信息和软件的信息,即生理信息和生命信息)的一个分支,生物信息学。于是,为揭开生命之秘、揭示与生命现象相关的复杂系统的运作机制打开一条新的途径。什么是生物信息处理生物信息处理的英文是Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ。1994年初,诺贝尔医学奖获得者美国教授Ｍ·罗德贝尔发表一篇评论,题为《生物信息处理:评估环境卫生的新方法》。他认为生物信息处理是在基因数据库基础上,计算机驱动的能快速获得表达基因部分序列的方法。通过ＭＥＤＬＩＮＥ数据库,可以查阅到很多与生物信息处理(Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ)有关的记录，其中ＪＦＡｉｔｏｎ认为生物信息处理是基于计算机的数据库和信息服务;ＲＰＭｕｒｒａｙ认为生物信息处理包括两方面：第一是大量现存数据的自动化处理,第二是新的信息资源的生成；ＤＢｅｎｔｏｎ在题为《生物信息处理———一个新的多学科工具的原理和潜力》的文章中说,生物信息处理的材料是生物学数据,其方法来自广泛的各种各样的计算机技术。其方法来自广泛的各种各样的计算机技术。近年来,生物学数据在爆炸式增长,新的计算机方法在不断产生。这些方法在结构生物学、遗传学、结构化药品和分子演变学中是研究工作进展的基础。如果生物医学工程要在各个领域都从研究进展中获取最大好处,那么生物学数据健全的基础设施的开发与维护是同等重要的。尽管生物信息处理已经作出重要贡献,但是在它成熟时就会面临更大的需求在爆炸式增长,新的计算机方法在不断产生。这些方法在结构生物学、遗传学、结构化药品和分子演变学中是研究工作进展的基础。如果生物医学工程要在各个领域都从研究进展中获取最大好处,那么生物学数据健全的基础设施的开发与维护是同等重要的。尽管生物信息处理已经作出重要贡献,但是在它成熟时就会面临更大的需求。北京信息工程学院毕业论文（设计）用纸第2页在整体上可以看出,生物信息处理的两个基本内容是生物数据库建立和计算机信息服务,也就是生物数据处理的计算机数据库化和程序化。当前这种数据库的内容主要是目录、期刊、遗传基因和细胞三维结构学。服务程序主要用于信息检索和基因序列分析。所以,严格地说,当前生物信息处理远未形成独立的学科,它同计算机生物学应用并无重大区别。在1998年第九届世界医药信息学大会上,它才作为一个讨论题目被列出来。可以说，生物信息处理技术是一项年轻的研究领域。1．2Microarray技术1．2．1Microarray技术原理微阵列技术是利用分子杂交的原理，用自动化仪器arrayer把不同的，数以百计、千计、万计已知部分序列的DNA探针“印”在玻璃片或者尼龙膜上面成阵列。为了比较两份标本中核酸表达的丰度，两份标本中核酸用同位素或者荧光素（红和绿两种）标记，再于微阵列杂交，然后检测杂交信号的强度，通过一定的数据处理系统，把它们转化成两份不同标本中特异基因的丰度，最后对这些数据进行分析。根据微阵列技术原理，微阵列技术的处理流程如下：1.实验设计2.样品制备（指mRNA或总RNA样品，包括对照组和实验组）3.芯片制备（包括PCR，纯化，点样等步骤）4.芯片杂交（将mRNA或总RNA分别进行逆转录生成cDNA，在此步骤中将对照组和实验组cDNA分别标记CY3和CY5荧光信号）5.芯片扫描（采用激光扫描仪，分别用532nm和635nm波长激光扫描芯片，对于每张芯片，得到CY3和CY5通道两幅图象）6.图象处理（采用专门软件，对图象进行分析，提取每个点上的数字信号），得到原始数据表。7.数据校正和筛选（对cy5或cy3信号进行校正，消除实验或扫描等各环节因素对数据的影响，同时利用筛选规则对数据中的“坏点”，“小点”，“低信号点”进行筛选，并作标记。）8.差异表达基因的确定（采用ratio值对差异基因进行判断，或采用统计方法如线性回归、主成分分析、调整P值算法等对差异基因进行统计推断）北京信息工程学院毕业论文（设计）用纸第3页9.生物信息学分析（如cluster算法、差异基因的同源性比对，差异基因的相关文献检索等）一个最简单的配置应包括微阵列制作系统(ａｒｒａｙｅｒ),信号收集系统(ｓｃａｎｎｅｒ),计算机和软件(操作系统和微阵列技术处理的相关软件)。1．2．2Microarray技术应用领域Microarray技术是近几年兴起的新技术，但短短几年中，该技术已经被分子生物学的很多领域接受，并广泛应用于以下领域：1、基因表达分析和检测微阵列技术已经被许多研究小组应用于与基因表达有关的工作中,如对细菌、动植物和人类的研究。包括：特异性相关的基因、差异表达的基因、基因功能研究、健康状况的检测、毒理学研究、药物作用机制的研究、定位克隆。2、功能分析检测到基因表达差异之后,下一步是寻找这些差异的生物学功能。最近Ｄａｖｉｓ等人[17]发明了一种新的方法。主要是应用插入一个独特序列或标记的突变酵母链。分子标记在特殊的的生长条件下从生存链中扩增,并与高密度微阵列进行杂交。这样不仅可以确定这条链的相对丰度,而且可以在不同时间点反复进行,同时还可以精确比较每条缺失链的适应性。3、基因作图微阵列技术的应用补充了基因表达研究的方法,加强了对疾病易感性和疾病本质的研究。这种方法无论是在速度上还是在准确性上都远胜于传统方法,它将会改变基因制图的方法。1．2．3Microarray技术发展现状DNA微阵列技术（DNAmicroarraytechnology）是近几年发展起来的应用DNA微阵列进行基因功能研究的新的生物技术。微阵列自1995年在《Ｓｃｉｅｎｃｅ》上报道后,被认为是该年度《Ｓｃｉｅｎｃｅ》上发表的最有影响的文章之一。微阵列是新出现的分子生物学技术,是本世纪重要的科学进展,它能够高效率、大规模地获取相关生物信息,是现代生物技术、微电子技术、机械制造技术、计算机技术的结合。其对科学的深远影响将远胜过ＤＮＡ测序和ＰＣＲ等,使人们更大规模北京信息工程学院毕业论文（设计）用纸第4页地获取生物信息,使人类基因组计划早日实现。微阵列技术的迅速发展已经引起了各方面的广泛关注。许多实验室、专业公司和制药公司都在大力开发与此相关的技术。在制作设备、分析设备、支持软件和探针的构建等方面均投入巨资,尤其是一些新兴的从事微阵列相关产业的公司如Ａｆｆｙｍｅｔｒｉｘ,Ｉｎｃｙｔｅ,Ｓｙｎｔｅｎｉ,Ｃｌｏｎｔｅｃｈ等公司均已研制生产出相关的产品。有供诊断用的芯片如ＨＩＶ,ｐ53和细胞色素ｐ450的芯片;有可供研究用的人、大鼠、小鼠不同基因类别的芯片;有与不同疾病如肿瘤、心血管疾病、神经系统疾病相关的芯片也已投入使用。而且很多公司可根据需要定制各种微阵列系统,为研究人员提供方便。国内也开展了此项工作,清华大学、上海细胞生物所、军事医学科学院放射医学研究所及广州等地正在进行此项研究。微阵列技术的发展为探索生命科学提供了强有力的工具。使一些原本复杂的工作变得简捷。正如ＮＩＨ的主任ＨａｒｏｌｄＶａｒｍｕｓ在旧金山美国细胞生物学年会上指出的:“应用微阵列技术,我们将最终揭示单个细胞的全部基因表达,甚至整个机体的基因概况”。同时,他还预言:“微阵列技术将改变我们对生命本质的认识”。1．3本次毕业设计的目标微阵列（Microarray）技术是一门新兴学科，它是结合了生物学、计算机技术、电子技术、生物信息学的特征而形成的一门交叉学科。微阵列技术发展到现在，虽然已经取得了惊人的改变和进步，广泛应用于分子生物学领域。但是，微阵列技术毕竟是一门新学科、一种新的思维方法，还需要在新的环境和领域下进行试验和完善，特别是在于其它学科、技术的结合方面，还需要研究人员花一定时间来研究和试验。本次毕业设计要达到以下的目标：（1）学习生物信息学的背景知识和微阵列技术的处理流程；（2）学习聚类分析中的主要概念和技术方法，并阐述聚类分析在微阵列技术中的重要地位；（3）分析几种常用的聚类方法，将其中存在的一些问题提炼出来加以分析；（4）在前几步的基础之上，结合所分析的常用算法设计一种改进算法；（5）用C语言实现设计的聚类算法和数据预处理工作。北京信息工程学院毕业论文（设计）用纸第5页第二章聚类分析方法概述2．1聚类分析及相关概念簇（Cluster）是指一个数据对象的集合。聚类就是将物理或抽象对象的集合分组成为由类似的对象组成的多个簇的过程。由聚类所生成的簇是一组数据对象的集合，这些对象于同一个簇中的对象彼此相似，与其它簇中的对象相异。在许多应用中可以将一个簇中的对象作为一个整体来对待。聚类是通过对数据对象本身数据的分析，从而将数据对象分成不同的类。聚类是一种无监督分类法，没有预先指定的类别。在机器学习领域，聚类是无指导学习（unsupervisedclustering）。与分类不同，聚类和无指导学习不依赖预先定义的类和带类标号的训练实例。由于这个原因，聚类是观察式学习，而不是示例式学习。聚类分析已经广泛的应用在许多领域中，包括模式识别、数据分析、图像处理、以及市场研究。通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。“聚类的典型应用是什么？”在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。聚类在地球观测数据库中相似地区的确定和汽车保险单持有者的分组上也可以发挥作用。聚类也能用于对Web上的文挡进行分类，以发现信息。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析，获得对种群中固有结构的认识。此外，聚类分析可以作为其他算法（如特征和分类等）的预处理步骤，这些算法再在生成的簇上进行处理。数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学，以及市场营销。由于数据库中收集了大量的数据，聚类分析已经成为生物学种生物信息分析研究领域中一个非常活跃的研究课题。聚类是一个富有挑战性的研究领域，那么怎样才算是一个好的聚类方法?最重要的是，一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：北京信息工程学院毕业论文（设计）用纸第6页高的簇内相似性低的簇间相似性此外，在不同的领域有一些对聚类更深入的要求，例如在生物信息学中对聚类算法的更深一步要求如下：1．能应付脏数据。绝大多数现实世界中的数据库都包含了孤立点、空缺、未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。2．对于数据不同的顺序不敏感。一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序提交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。3．模型可解释性和可使用性。用户希望聚类结果是可解释的、可理解的和可用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。2．2聚类分析中的数据类型在本节，我们研究在聚类分析中经常出现的数据类型，以及如何对其进行预处理。许多基于内存的聚类算法选择如下两种有代表性的数据结构：·数据矩阵（datamatrix，或称为对象与变量结构）：它用p个变量（也称为度量或属性）来表现n个对象，例如用年龄、身高、体重、性别、种族等属性来表现对象“人”。这种数据结构是关系表的形式，或者看成n×p（n个对象×p个变量）的矩阵。图示如下：·相异度矩阵（dissimilaritymatrix，或称为对象－对象结构）：存储n个对象两两之间的近似性，表现形式是一个n×n维的矩阵。图示如下：npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x（8．1）0.