基于聚类分析的基因表达差异筛选方法研究

《基于聚类分析的基因表达差异筛选方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

中南大学硕士学位论文基于聚类分析的基因表达差异筛选方法研究姓名：熊芳申请学位级别：硕士专业：计算机技术指导教师：肖大光;阳菊华20070501 摘要人类基因组计划的顺利完成标志着生命科学的研究进入了后基因组时代。科学家的研究重点转向了从大规模生物数据中发掘蕴含的结构和功能信息。基因表达系列分析(sAGE)微阵列和基因芯片等技术的运用使得研究者可以同时观察成千上万条基因在某个生命过程中的表达情况，己经成为了生物信息学研究的一个重要方向。如何利用计算机科学中的分析技术，从海量基因表达数据中筛选出对了解生命过程有指导意义的信息成为当前生物信息学研究的新课题。聚类分析是在分析基因表达数据时最常使用的方法之一。具有相似表达特征的基因能够被聚到一起，提示这些基因具有相近的生物学功能。我们对基于CF树的两种BIRCH算法进行了分析和研究，发现其有两点不足，一是采用统一阈值形成多个簇，二是不能发现不规则形状的簇。本文提出了一种基于多代表点的特征树，它基于BIRCH算法的思想，融人了CURE算法的优点，可以对海量的聚类数据进行压缩，并且能够捕捉复杂形状的簇。利用该数据结构，采用随机采样的方法，提出了一个适合的处理数据的聚类算法，该算法能够满足上述聚类算法的要求，有效地快速地处理海量数据。并从定量和定性两方面分析了改进算法。同时，文中也介绍了我们基于扩展的cF树的聚类软件系统实现，并运行了实例，应用于胃癌SAGE文库，有效而快速的筛选出肿瘤差异表达基因。筛选出的胃癌差异表达基因可指导后续分子生物学实验研究，验证后有望成为新的胃癌分子靶标。通过对筛选出的EST进行进一步生物信息学分析和分子生物学实验，有望克隆新的胃癌相关基因。关键词生物信息学，基因表达序列分析，聚类算法，扩展CF-树 Abs仃actWiththeaccomplishmentofHumanGenomeProject,thebiologicalresearchcomestothenewpostogenomeera．ScientistsnOWfocusonexploringgenomestructuresandfunctionsfrombiologicaldata．Serialanalysisofgeneexpression(SAGE)，DNAmicro-arrayandgenechiptechnologyhavenowmadeitpossibletosimultaneouslymonitortheexpressionlevelsofthousandsofgenesduringbiologicalprocesses，Andserialanalysisofgeneexpression(SAGE)hasbecomeaveryimportantbranchofbioinformaticsresearch．Howtousetheanalysistechnologiesofcomputersciencetoanalysisthemillionsdataanddiscovertheusefulandinstructiveknowledgeofbiologicalexperimentisattractingmoreandmoreattentionsfortheinformationbiology．ClusteringanalysisiSthefrequentmethodtoanalysisthegeneexpressiondata．GeneswithsimilarexpressionparentsCanbeclusteredtogether谢msimilarfunctions，allofthemhavetheclosebiologyfunction．Throughmassiveanalysesandresearch,wefindthetwoofBIRCH-clusteringarithmeticbasedonCF—treehavetheirshortcomingseach,oneusesthesamethresholdtoshapemulti-cluster,andtheotherCan’tfindanomalouscluster．Thispaperpresentsmulti-representativepointsalgorithmbaseOilthefeaturetree，thealgorithmbasedOiltheideaofBmCHalgorithm，addadvantageoftheCUREalgorithm,itCancompressmassiveclusteringdata,andCancapturethecomplexshapesoftheclusters．Usethedatastructure，anduserandomsamplingmethod,weadvanceasuitabledatahandlingclusteringalgorithm，ThealgorithmCansatisfytheaboveclusteringalgorithm,andCanprocessdatarapidlyandeffectivemass．Atthesanletime，weanalysistheimprovedalgorithmfrombothofthequantitativeandqualitative．Meanwhile，thearticlealsointroducetheexpandedsoftwaresystemsbaseonourCF-treeclustering,andruntheexampleofgastricCanCer’SSAGEDatebase，benefittheeffectiveandfasttool，differenceexpressiongenesofgastricCanCerWeredistinguished，whichwillguideOurfurthermolecularbiologyresearch．Ifvalidatedbymolecularbiologyexperiment,thesedifferenceexpressiongeneswillbeusedasmoleculartargetsofgastriccarcinonla．Somenovelgastriccarcinomaassociatedgeneswillalsobe clonedbasedonthesedifferenceexpressionofESTsbyfurtherbioinformaticsanalysisandmolecularbiologyexperiment．Keywordsbioinformatics，serialanalysisofgeneexpression，clusteringarithmetic，extendCF-tree 原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。作者签名：垒盔日期：旦年』月鲨日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，ep．学校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文。作者签名：鲢导师签名§盛日期：21年￡月上日 王程硇±堂位论奎筮=重缝i金第一章绪论2l世纪是生命科学蓬勃发展的世纪，而最能够体现这一时代特点的则莫过于著名的人类基因组计划的实施和完成。从此，分子生物学研究从单个基因或蛋白质研究转向大规模全基因组层面的研究。除了人类基因组外，其他模式生物诸如啤酒酵母、线虫、果蝇、小鼠、拟南芥、水稻等的基因组测序计划也均相继完成或全面实施。伴随这些测序计划出现的、呈爆炸性指数增长的各类基因序列和表达信息致使全世界的科学家们积极运用数学、计算机科学和生物学的各种工具，来阐明和理解基因组学获得的大量数据中所包含的生物学意义，生物信息学这一新兴交叉学科应运而生【¨。1．1研究背景1．1．1生物信息学的发展生物信息学是一个新的学科领域，包含着基因组信息的获取、处理、存储、分配、分析、解释的所有方面。由于生物体的结构和功能以及生命活动过程本身的多样性和复杂性、生物实验方法的独特性导致生物学数据的复杂性，面对生物学数据在量(海量)与质(复杂性)方面所提出的严峻挑战，生物信息学综合了计算机科学、数学、物理学、生物学、医学等多个学科领域的知识，运用数学j。计算机科学和生物学的各种工具进行研究，以了解数据中的生物学意义。这种基于序列及其相关信息的新生物学的终极目的，就是破译在生命过程中的信息密码。生物信息学不仅仅成为一门前沿理论学科，更重要的是它已经成为一个融入到实验室的具体实践方法【l】。它就如同～个向导，帮助实验室中的生物学研究者通过这个向导对将要开展的实验研究作出更周密的实验设计、预测研究的结果和对实验结果作出规律分析，以减少实验失败率，缩短实验周期，获得实验成功。随着基因组计划的不断深入，以功能鉴定为目标的功能基因组学(functionalgenomics)㈣@究的一大重点【2】，而基因表达分析是基因功能研究最重要的组成部分。目前，阻值或细胞间差异表达基因的研究广泛采用的实验方法有表达序列标签(EST)测序、mRNA差别显示RT．PCR法(ml埘AdiferentialdisplayRT-PCR．mRNADDRT-PCR)、消减杂交(subtractivehybridization)等等[31，但是这些技术具有共同的缺点：它们的随机性均使其只能反映有限基因的表达频谱，无法描绘出基因表达模式的全貌，通过这些方法所获得的多限于高丰度或表达差异大的基因，无法大量地分析组织或细胞内基因组表达的状况，也无法知道究竟有多少个差异表达的基因及其差异表达的程度，更无法得知丰度的信息以及与其他差异表达基因相比的相对重要性，而细胞中绝大部分基因属于低丰度表达，而且相当一部分是具有重要功能的未知基因组。另外，目前用于定量表达分析的还有基因芯片或cDNA微阵列，基因芯片或微阵列法虽 工程硒±堂位论奎筮=童结j金然可以一次分析大量基因的表达状况、具有大规模、高通量和并行处理的优点，但由于其分析的基因数量很有限，而且价格昂贵、对设备有特殊要求，并不能被每个实验室所承受，因此目前尚不能得以广泛使用和普遍推广．美国科学家Velculescu等于1995年建立了一种快速而高效地分析组织或细胞基因表达状态的方法——基因表达系列分析(serialanalysisofgeneexpression，SAGE)14]。SAGE是一种基于测序技术，能快速定量分析某些生物、组织或细胞基因表达模式的实验技术。作为一种高通量分析基因表达模式的实验方法，SAGE技术能够快速全面地分析在特定组织和细胞中表达的基因并得到这些基因表达丰度的数量信息，而且还可以比较不同时、空条件下基因表达的差异。这种技术得到迅速推广，成功应用于多种肿瘤组织的基因表达谱的构建，并得到了海量的信剧，】。有观点认为sAGE在研究基因表达差异上比芯片数据更有优势。它与芯片技术最明显的差别是该技术不需要知道在样本中哪些基因被表达了的先验知识，SAGE发现的某些基因在已有数据库中并不存在，这些是芯片技术所遗漏的信息，这部分数据的比例保守估计有百分之十到十五。并且研究发现，SAGE对低丰度表达基因有较好检测效果，有报道称，SAGE检测3个拷贝表达基因的可靠性达92％以上[61。现在已经有越来越多的基因表达差异分析的工作应用了该技术，可以预期该技术会更加得到重视并被广泛应用。作为目前唯一以测序为基础的定量分析全基因组表达模式的技术，其在定量分析各转录子表达水平及检测表达丰度等方面所具有的明显优势，为其在将来的广泛应用创造了条件川。1．1．2课题背景本论文接受以下国家自然科学基金项目资助：1．项目名称：染色体3p2l区域鼻咽癌易感，抑瘤基因研究项目批准号：303002012．项目名称：湖南鼻咽癌易感基因的进一步定位与克隆项目批准号：304709553．项目名称：长沙汉族人群脑出血相关SNPs及其单体分子标志研究项目批准号：30600199本课题是基金项目研究工作的一部分，承担差异基因筛选工作的数据处理及分类筛选工作。本文中所研究的基因数据处理、聚类分析和差异分析等技术，对于分析基因表达数据以便理解和推断基因功能、基因规则及细胞过程有着重要的意义。如何利用并改进传统的数据挖掘领域的聚类算法或引入新的聚类算法来适应基因表达数据的分析、为生物研究者提供更好地服务是一个重要的、很有意义的研究课题。不同的数据挖掘方法都有一定的适用范围和相应的限制条件，基因表达数据分析因为其特有的表达数据特点给数据挖掘方法提出了一些新要求。因此根据基因表达数据的特点对数据挖掘2 王程亟主堂位论塞箍二童绪论方法进行改进找到更合适的方法或引入更合适的方法仍需要继续深入研究。此外，整合已有的方法构建平台，为生物研究人员进行研究提供服务，也是一项十分有意义的工作。本文针对基因表达数据中常有一小部分基因的功能是己知的特点，利用己知类别的基因分别指导聚类中心初始化和聚类过程，实验证明这些方法是可行的，为生物研究者引入了可行的方法。从基于基因的聚类结果看，挖掘基因间的相关性可以减少关联规则在挖掘规则时的搜索空间和时间复杂度，同时可以减少大量的冗余规则，从而节省生物研究者进行生物实验验证所获规则所需的时间、精力和财力。1．2基因数据库研究现状本文研究的基因数据库是来自SAGE基因数据库，SAGE技术开始主要应用于Genbank中EST数据比较丰富的生物，包含人类，小鼠，大鼠等。近年来，SAGE技术已经逐步在生命科学中得到广泛的应用，主要表现在以下几个方耐明：1．动物基因组转录图谱的构建今后可以利用SAGE庞大的基因表达数据给出的特定的数据信息，将基因定位在染色体上，根据基因对应的标签丰度，以染色体长度为横轴，转录水平(标签丰度)为纵轴，绘制转录图谱，这样可以识别单纯序列信息所不能预测的基茵。2．动物基因功能的研究应用SAGE研究未知基因的功能是其最主要的用途之一，根据人为表达或封闭未知基因，观测细胞或实验动物表达谱的改变，可以推测该新基因的功能。3．动物发病机制的研究疾病的发生多是由于正常的生理状态下基因表达发生改变的结果，通过比较分析发病组织细胞和正常组织细胞中基因表达的变化和差异，可以了解疾病发生、发展的过程，明确疾病发生的机制。4．信号传导通路分析Zhang等在2006建立了6个SAGE文库，对在正常胰腺发育过程中起关键作用的间样细胞，上皮细胞相互作用的信号传导通路进行研究，发现以前未报道的Writ通路中的一些成员在胰腺发育过程中基因差异无表达，而其竞争者s卸2蛋白在胰腺发育早期表达上调，在胰腺发育晚期表达下调，Writ的4个配体只有wnt4配体的转录体可以在发育的胰腺中检测到。5．药物研究中的应用应用SAGE检测受药物治疗后相关组织细胞中基因转录情况，可以明确药物的有效作用位点，毒性和药效情况，大大简化了药物的筛选过程，从而极大地降低了新药的开发成本。同样，也可应用于对疾病有效治疗方法的筛选，并可对治疗效果在分子水平上进行客观定量的评价．SAGE可以在分析基因表达水平差异的基础上寻找药物的靶标，用于新型药物的研究，通过比较不同组织间tuRNA表达谱，选择只在特异组 王程亟±堂缱论奎箍=重绪论织中才表达的蛋白，作为筛选的靶位，通过这些选择，可以减少药物对整体的不良反应。SAGE技术还可以分析药物作用在基因表达变化的研究。从理论上讲，SAGE技术能应用于研究由细胞内转录水平发生改变引起的各种生物现象。由于该技术具有定量、高通量分析基因表达的特点，不仅能提供某些简单生物个体或特殊类型的细胞和组织全基因表达图谱，同时能通过建立不同生理条件下细胞群的基因表达标签库，寻找和证实一套由于细胞内或周围环境因子的改变而引起的差异表达基因。目前，SAGE技术已成功运用于酵母转录本标签库的建立、人类很多疾病相关基因特别是肿瘤发病相关基因的研究、药物治疗作用路径的证实及相关调节基因研究和发育时空差异表达基因研究等【9I。随着SAGE技术的不断改进，该技术在应用上也得到了拓展，为原来很多由于材料原因受局限的研究领域如视网膜、胚胎早期的血管疾病等开辟了新的研究热点。如Neilson等人最近应用PCR-SAGE技术仅仅使用8个卵母细胞建立了人卵母细胞的SAGE标签库。通过SAGE方法产生特异表达或丰度表达新标签，筛选候选新基因的研究，是目前报道的一个热点，另外，目前SAGE技术研究的最新的热点问题，主要集中在以下几点110】：1．癌症诊断或致病相关的候选新基因的筛选癌症是一种遗传疾病，某一组织的癌变可能引起相关的成百上千基因表达模式的改变。SAGE技术和cDINA微矩阵检测技术的出现，使得同时分析大量基因表达模式成为可能。SAGE技术与cDNA微矩阵检测技术相比，由于具有不需要知道待分析对象的基因组序列信息的特点，己成为发现癌症相关新基因的有效手段。目前在GenBank登记的SAGE标签库(http：／／www．ncbi．nlm．nih．gov／SAGE)有160个，其中来自人类不同组织或不同生理状态的细胞群标签库占了89．4％。2002年5月8日，在C-enbank中公布的将9696个表达标签定位在人类23条染色体的SAGEmap(http：／／w删．ncbi．nlm．nih．gov／c星舢in／Entrez／maps．cgi?ORG：hum)，是目前对人类癌症等疾病相关基因研究的重要成果。作为CGAP(cancergenomeanatomyproject)一部分，美国国家生物技术信息中心已经建立了一个SAGE标签库共享网站(http．．／／w、删．ncbi．him．nih．gov／ncicgap)，研究者可以应用DDD(digitaldifferemialdisplay)接在线比较选择的SAGE标签库，寻找作为癌症发病诊断的标记分子。Mitas等通过在CGAP网站对95个SAGE库的在线nortbemblot发现，已经证实的前列腺癌特异丰度表达标签(PSE，Prostate-SpecificEts)在乳腺癌的15个SAGE标签库中表达的有93％，而正常组织的SAGE标签库中PSE标签出现只有13％。通过对乳腺癌患者腋窝淋巴结定量的适时RT--PCR揪4，证明PSE的表达水平可以作为转移乳腺癌患者新的诊断指标。2．器官发育时空差异表达候选基因的筛选脊椎动物发育的肢(翼)是研究调节生长、决定细胞分化调控因子的很好模式。目前研究发现，决定前后肢发育的基因主要有Pitxl、Tbx4、Tbx5和几个Hox基因，其中Pitxi、Tbx4在发育的前肢(翼)中优势表达，Tbx5仅在后肢(翼)中表达；而几个Hox相4 王程亟±堂位j金奎筮=童绪论关基因的表达受P戤L-Tbx表达模式影响。但是，很多相关研究结果表明，在肢(翼)发育过程中还存在其他的相关调控因子。为了全面地了解肢发育过程中特异基因差异表达以及形态学和功能上差异遗传基础，Margulies等采用SAGE技术分别建立了正在发育的小鼠完整前肢和后肢的基因转录标签库．比较前后肢标签库发现，表达丰度差异在5倍以上的标签序列有96个，其中包括己知的Pitxl、Tbx4，但Tb)【5的表达标签仅仅只出现在后肢标签库中。由于用倍数关系分析低丰度表达水平差异基因的局限性，Tbx5没有表现出明显的表达差异。通过将小鼠前后肢两个标签库与小鼠6个其他的sAGE标签库进行事实差减发现，原来证实的在前后肢差异表达的810个标签，实际上只有26％是与肢体发育相关的特异标签。因此，通过事实差减进一步缩小了前后肢特异差异表达相关的候选基因范围。SAGE文库事实差减后得到的候选基因是研究畸形肢遗传综合症的遗传基础，同时对发现新的肢发育特异性调节因子具有很大参考价值。3．受调控的增效表达候选基因的筛选vHL(vOnHippel--Lindau)综合症，是由于VHL基因突变引起的家族性视网膜血管瘤，该病经常伴发腹腔内脏器官病变，如肾细胞瘤、中枢神经系统的血管瘤和胰腺瘤等。VHL基因的机构和功能已经有较为深入的研究，虽然已有证据说明VHL对相关基因的表达影响是多途径和复杂的，但基因缺失或过表达对整个组织IrIRNAs稳定表达状态改变的影响尚不清楚。最近CraigCaldweU等人应用SAGE技术构建了两种gCC(renalcellcarcinoma)细胞系(786_一。和OMP．C6)缺失或表达野生型VHL的4个SAGE标签库。通过比较构建的VHL缺失型和表达野生型Ⅷ标签库，发现在VHL缺失的细胞系构建的标签库中有25个表达明显增加的标签序列，而在表达野生型VHL的SAIG王’麻签库中表达丰度明显增加的有33个．这些表达丰度存在明显差异的基因，有已经揭示了在病理和正常状态下差异表达的基因如Glut—l，但绝大部分基因是没有研究报道的。为了证实这些得到的差异表达基因的表达是否受VHL影响的真实性，他们引入了第3种RCC细胞株CLIOK--121)，同样包括缺失和表达野生型VHL两种。采用northemblot方法检测已经得到的部分差异增效表达基因在两种UOK--121细胞中的转录冰平，证实了通过SAGE技术得到的VHL缺失或过表达生理状态下丰度表达的候选基因的有效性。因此这些丰度表达的新基因可能能作为VHL综合症发生的指症基因或治疗的靶位基因。围绕以上的热点问题，全世界的生物学家们进行广泛深入的研究，取得了很多的成绩。Velculescu等在提出SAGE技术时预测，在阐明基因组全部序列信息后，SAGE将能直接分析任何细胞、组织的基因表达。随着SAGE技术的进一步发展和完善以及生物信息技术的迅速发展和数据库的不断丰富，以及SAGE研究技术的更加有利应用条件，可以预测，SAGE技术在生命科学领域应用前景将更为广阔。特别是SAGE技术与蛋白质组学相关技术【11】如二维凝胶电泳、质谱技术和蛋白质芯片技术等相结合，SAGE技术有望在后基因组学研究和揭示了解生命活动的本质规律中开辟一片崭新的5 工程亟±堂僮i金奎差=童绪i金天地。可以预计，SAGE技术将为功能基因组学研究的深入开展和应用起到巨大的推动作用[121。1．3本文主要工作生物信息学的研究需要一些必要的基础，一是要建立各种数据库，使得实验获得的数据能够被更加容易的存储、提取和分析，二是基于这些数据开发各种算法，从数据中挖掘出新的有用信息，帮助生物学家得出许多新的生物学知识和提出有价值的生物学问题，而且有些生物学问题必须通过生物信息学的手段来实现。本文主要针对SAGE技术的最热门研究内容之一，“癌症诊断或致病相关的候选新基因的筛选”，将伴随基因组测序计划出现的、呈爆炸性指数增长的基因序列信息海量数据，进行聚类研究1131，本文的研究目标有两个：1．作为实验手段的辅助工具，为分子生物研究提供各种分析方法和高效算法，并用软件加以实现，以尽可能消除实验误差及由于个体差异而造成的数据差异，高效、准确地筛选出肿瘤和正常组织的差异基因，并将改进的聚类方法应用于胃癌基因差异表达筛选的工作。2．利用有效的算法及工具，从已有的大量数据库中提取信息，挖掘新的生物学知识，推延新的发现。它的最终研究目标是解读生命的遗传密码。．针对本文目标，本文研究了基于基因表达数据的肿瘤分类和基因功能分类以及相关算法。主要工作总结如下：1．SAGE数据的主要生物学和数学方面的特征，提出利用聚类的方法，对SAGE数据库的数据进行处理，并对常用于基因表达数据的几个层次聚类的方法进行系统的分析，比较深入地研究了它们的分类原理。2．因表达数据集数据量大、维度高的特点，必须利用增量式的算法来提高聚类效率，通过具体分析在实验中的缺陷，在BmCH算法的基础上，提出基于扩展CF树的层次聚类算法，试验结果显示，提高了肿瘤分类的准确率，提高了分类性能。3．利用改进的算法进行基因表达数据聚类分析，并以一个运行实例来说明，利用聚类分析结果再将胃癌基因与正常胃组织文库的基因表达进行差异分析，筛选出差异表达基因。4．筛选出的基因中可靠性较高的PTMA基因进行基于EST和基于SAGE的虚拟Northern分析。通过该结果，我们发现该基因在全身多种组织的肿瘤中，有较弱的表达上调总体趋势(EsT和SAGE数据库的结果F分别为0．79和0．96，P值分别为0．00和O06)，其中，在骨髓、肝、卵巢、子宫等组织中，肿瘤组织较正常组织表达明显升高。得到了它的表达谱，发现该基因在多种肿瘤中表达上调，提示该基因可能是一个在多种组织癌变过程中其作用的癌基因；5．选取了一个胃癌中表达下调的基因利用SAGE数据库进行了差异显示，发现该6 工程亟±堂位i金塞筮=童绪论基因主要在正常胃组织中表达，而在胃癌及其它组织中表达水平较低，提示该基因有可能为正常胃组织相对特异表达基因，并有可能是胃癌特异性的抑瘤基因。从代表未知基因的差异标签入手，有望克隆新的胃癌相关基因。1．4本文组织全文主要包括以下5个章节：第一章为绪论，首先介绍了本文研究的背景和课题项目背景，并指出了本文在课题项目中作用，然后介绍了本文的研究基础基因数据库SAGE技术的研究现状以及本文所做的主要工作和组织结构。第二章为基因差异表达筛选方法的综述，分析了基于基因数据库的基因差异表达序列方法和基于基因表达的数据分析方法，着重介绍了数据挖掘的聚类分析方法，这是本文的研究重点，为本文接下来的研究提供理论基础．第三章为，提出改进算法，并对其中的关键技术进行了详细研究，分析了新算法的原理及实现，最后从定性和定量两个方面分析了基于聚类分析的基因差异表达筛选方法的性能．第四章基于聚类分析的基因表达差异筛选设计与实现，，对其中的消息结构、数据结构和主要功能模块进行了详细设计，并运行改进算法实例．第五章总结与展望，对己做的工作进行了总结，并提出了应迸一步深入研究的问题。7 王捏亟±堂焦途毫簋三童基固羞昱塞达缝选左选绽述第二章基因差异表达筛选方法综述我们利用CGAP的SAGEGenie数据库的基因数据，运用数据处理与数据分析方法，对胃癌差异表达基因进行初步筛选，差异表达的己知基因涉及细胞周期调控、细胞增殖、凋亡等生物学过程，参与了JAK．STAT、Writ等多条信号传导通路1141。基因差异表达筛选一般采用CGAP提供的SAGE系统可以进行可视化展现，从而得出其差异表达谱并进行筛选。2．1基因表达系列分析基因表达实际上是细胞、组织、器官受遗传和环境影响的结果。一个基因的转录和表达由细胞的生化状态所决定，在一个基因的转录过程中，一组转录因子作用于该基因的启动子区域，控制该基因转录，而这些转录因子本身又是其它基因的产物。当一个基因通过转录、翻译形成功能基因产物后，它将改变细胞的生化状态，从而直接或间接地影响其它基因的表达，甚至影响自身的表达。多个基因的表达不断变化，使得细胞的生化状态不断地变化。一个基因的表达受其它基因的影响，而这个基因又会影响其它基因的表达，这种相互影响、相互制约关系构成了复杂的基因表达调控网络。基因表达数据之中隐含基因之间的相互作用关系，因而可以通过分析基因表达数据，构建基因调控网络【”1。细胞或组织的生理和病理状态取决于基因表达模式，即基因的选择性表达及表达量的多少。在功能基因组时代，随着大规模DNA测序等支撑技术的发展、计算机分析手段的丰富以及生物信息资源的积累，人们迫切希望能从整体水平对细胞或组织的基因表达模式进行研究，并通过不同样本之间的分析对比，了解复杂生命现象与基因表达变化之间的内在联系，从20世纪90年代至今，已发展了多种高通量的基因表达研究技术。SAGE是1995年由Velculesce等建立的一种新的基因表达模式研究技术，它可以在整体水平对细胞或组织中的大量转录本同时进行定量分析，而无论其是否为己知基因。SAGE技术不仅能够全面地分析特定组织或细胞表达的基因并得到这些基因表达丰度的数量信息，而且还可比较不同组织、不同时空条件下基因表达的差异。SAGE技术所显示的优点，己受到广泛的重视。SAGE技术建立在两个基本原理之上【161：1．在一个转录体系中，每种转录本都可以用一个特异的固定长度寡核苷酸序列(9一14bp)来代表，这些短序列称为SAGE标签(SAGEtag)。从人类基因组计划的结果来看，人类基因组编码的基因数目在3万个左右，特定组织或细胞表达的基因数量则不超过15，000种。以一个9bp的标签库为例，理论上可以区分49(=262，144)种转录本，己足够代表任何一种特定的人组织或细胞的全部转录本。8 工程亟圭堂位j金塞筮三重基国差显盘盗缝选友蜚绽述2．通过一定的实验步骤，将这些SAI强标签从cDNA中分离出来制备成一个SAGE标签库，然后连接成标签多聚体进行克隆测序，并将得到的短序列核苷酸顺序以连续的数据形式进行处理，就能对数以千计的mRNA转录物进行分析，每种标签在全部标签中所占的比例可以反映它所代表的转录本在整个转录体系中的表达丰度。2．2基于基因差异表达的数据分析方法基因表达数据分析就是对从基因差异表达分析实验(通过基因芯片或者SAGE等高通量技术)得到的大量数据，通过有效数据的筛选和相关基因表达谱的聚类，最终整合杂交点的生物学信息，发现基因的表达谱与功能可能存在的联系【171．每次实验都产生海量数据，如何解读基因表达上成千上万个基因点的杂交信息，将无机的信息数据与有机的生命活动联系起来，阐释生命特征和规律以及基因的功能，是生物信息学研究的重要课题。基因表达的数据分析方法从机器学习的角度可分为监督分析和非监督分析，假如分类还没有形成，非监督分析和聚类方法是恰当的分析方法；假如分类已经存在，则监督分析和判别方法就比非监督分析和聚类方法更有效率。肿瘤识别是在已有数据的基础上建立分类器，并利用所建立的分类器对目标样品的状态进行判别。但是，由于高密度芯片可以同时检测成千个上万个基因的表达水平，然而在很多情况下，只有一小部分基因对识别是有价值的，而且相对于样本数来说，过多的基因(特征)个数对以后使用的统计方法也会产生不良的影响。因此，在判别分析之前需要进行基因筛选，采用假设检验方法检验每个基因，选取那些在不同总体样品间表达差异显著的基因。基于基因差异表达的数据分析方法，可以从统计学方面和数据挖掘两方面进行分类：2．2．1统计学方法对于使用参照实验设计进行的重复实验，可以对2样本的基因表达数据进行差异基因表达分析，目前使用的基因筛选方法按统计学上来分具体方法包括倍数分析、t检验、方差分析等。用统计学的方法，筛选差异基因，可分为以下几种：1．倍数变化(foldchange，FC)倍数分析是最早应用于基因芯片数据分析的方法【瑚，该方法是通过对基因芯片的ratio值从大到小排序，ratio是cy3／cy5的比值，又称R／G值。一般0．5．2．O范围内的基因不存在显著表达差异，该范围之外则认为基因的表达出现显著改变。由于实验条件的不同，此阈值范围会根据可信区间应有所调整。处理后得到的信息再根据不同要求以各种形式输出，如柱形图、饼形图、点图等。该方法的优点是需要的芯片少，节约研究成本；缺点是结论过于简单，很难发现更高层次功能的线索；除了有非常显著的倍数变化的基因外，其它变化小的基因的可靠性就值得怀疑了；这种方法对于预实验或9 王捏丝主堂焦监塞箍三童基固羞是塞达蕴选左选绫亟实验初筛是可行的。此外倍数取值是任意的，而且可能是不恰当的，例如，假如以2倍为标准筛选差异表达基因，有可能没有1条入选，结果敏感性为0，同样也可能出现很多差异表达基因，结果使人认为倍数筛选法是在盲目的推测。2．t检验(t-test)差异基因表达分析的另一种方法是t检验【19J，当t超过根据可信度选择的标准时，比较的两样本被认为存在着差异。但是t检验常常受到样本量的限制，由于基因芯片成本昂贵，重复实验又很费时，小样本的基因芯片实验是很常见的，但是小样本导致了不可信的变异估计。为了克服这种缺点，研究者提出了调节性t检验(regularizedt-test)，它是根据在基因表达水平和变异之间存在着相互关系，相似的基因表达水平有着相似的变异这个经验，应用贝叶斯条件概率(贝叶斯定理)统计方法，通过检测同～张芯片临近的其它基因表达水平，可以对任何基因的变异程度估计进行弥补。这种方法对于基因表达的标准差估计优于简单的t-test和固定倍数分析法。3．方差分析(analysisofvariance，∞qOVA)：方差分析(ANOVA)又称变异数分析或F检验[20l，其目的是推断两组或多组资料的总体均数是否相同，检验两个或多个样本均数的差异是否有统计学意义，方差分析可用于差异基因表达研究。方差分析需要参照实验设计，参照样本常用多种细胞的mRNA混合而成，由于所有的细胞同时表达的基因众多，结果低表达基因在样本混合后就被稀释而减少了参照样本的代表性，因此，增加参照样本的细胞不会提高参照样本的代表性。方差分析能计算出哪些基因有统计差异，但它没有对那些组之问有统计差异进行区分，比如用单因素方差分析对A、B、C、D四组进行分析，对于某一个基因，方差分析能够分析出A组与B、C、D组之间有差异，但是B、C、D之间无统计学意义。这就需要使用均值问的两两比较(post-hoccomparisons)检验，该检验是对经方差分析后的基因进行下一水平更细节的分析【211。即t-检验只能用于检验两样本中均值是否存在显著性差异，而两两比较技术考虑了多于2样本间均数的比较。上述所有的参数分析方法必须平衡假阳性、假阴性错误【22】，控制假阳性率有4种方法：(1)邦弗朗尼(Bonferroni)方法，计算公式：CorrectedP-value=P．valuexn(numberofgenesintest)，如果纠正P值仍小于错误率(如0．05)，则该基因将属于有表达差异的基因。(2)BonferroniStep．down(Holm)法，这种校正方法与邦弗朗尼很相似，但没有前者严格。主要思想如下：每个基因的P值从低到高排序，Correc￡edP．value=P-value×n(n．1／n-2⋯⋯)，如果纠iEP值仍小于错误率(如0．05)，则该基因将属于有表达差异的基因。(3)Westafall&Young参数法，前面2种方法部是单独对P值进行纠正，本方法通过同时对所有基因进行排序，充分利用基因问的独立性进行P值纠正。每个基因的P值是按原始资料的排序进行计算；将资料划分为人工组和对照组而产生新的数据。采用新10 王程亟主堂焦i金塞筮三童基国差爰麦达缝选友鎏签述数据计算所有基因的P值，新P值再与以前的P值进行比较，上述过程重复很多次，最后计算出纠正P值．如果纠iE．P值仍小于错误率(如O。05)，则该基因将属于有表达差异的基因。(4)Benjamini&Hochberg'f殴阳性率法，该方法是4种方法中最不严谨的方法，因此可能产生很多的假阳性和假阴性，其方法如下：首先对每一个基因的P值由小到大排序，最大的P值保持不变，其它基因按下列公式计算P值，CorrectedP-value----Pvalue×(n／n-1)此类推，若P=2)个簇Ci进行合并，n个簇的聚类特征表示为·+CF=04，LS，SS，T1其qa(I=l，2，3，⋯，n)，那么合并后簇为w，其聚类特征表示为—÷CFw---(N，LS，SS，n---o-合并后簇的聚类特征一方面精确的表示两个聚集合并后的渐增性，如N，LS，Ss，另一方面，根据原有簇的阂值对新阈值进行修改，动态地调整合并后簇的阈值，调整后的阈值不仅包括原有簇的所有数据对象，而且大大增加了重建树后新的数据对象插入的可能性，最终产生不同阈值的聚类结果。综合考虑数据对象与簇的中心点的距离和簇的阈值，文献‘川提出针对多阈值BIRCH。聚类算法的插入算法和分裂算法为：插入算法：将聚类特征CF插入到聚类特征树CF-tree中：(1)初始化根结点为插入结点。(2)确定CF的插入位置。<1>当插入结点类型为非叶子结点时，循环：如果CF与插入结点包含的各Entryqb的CF之间的距离小于相应的Entry阈值，分别转入i-*．),Entry对应的子结点；否则，转入与CF距离最近的Entry的子结点；<》当插入结点类型为叶子结点时：如果CF与插入结点包含的各Entryqj的cF之间的距离小于相应LEntry的阈值，选择阈值T最小的Entry采用合并算法将cF与L*．．tEntry的cF合并，这时称cF被某结点吸收；否则，称CF无法被结点吸收。(3)修改聚类特征树。如果插入的CF被某结点的Entry吸收，自下而上修改相应结点qaEmry的CF：如果CF无法被结点吸收，新建Entry并赋值为CF，按B+树的插入算法将该Entry插入到原树中距离cF最近的Entry后，并相应修改聚类特征树的结构。分裂算法：假定结点中包含N个Entry插入无法被Entryff)及收的cF：(1)将CF作为一个Ent耐算N+1个Entry的qa心点。(2)根据各Entry口fi该中心点的距离对N+l+Entry进行排序。选择分割因子P％，RON+I+Entry中的P％个Emry作为新结点，与新结点距离最远的Entry作为另一个结点，剩余结点根据与两结点的距离依次插入，最终g§N+1个Entry分化为两个结点。并向树的根结点传递修改得聚类特征信息。分割因子设定的准确与否，直接关系着最终的聚类效果，通过实验得知，分割因子取值在5006．70％，能够得到较好的聚类结果。，一旦当前聚类特征树所使用的内存空间达到系统所能提供的最大内存空间，这时取叶子结点相邻Entry之_间距离的平均值作为新的阈值，提升各叶子节点中包含的簇蛆 王猩蘧土堂焦i金塞箍三童基王嚣娄筮扳鳇基国差昱盘达垣选友洼的阈值，使叶子节点中的阈值大于等于新阈值，并将所有叶子结点Entry重新插入聚类特征树中。由于阈值的提升，使得原聚类特征树中的部分叶子结点的Entryn-I"进一步合并，重建一棵较小的聚类特征树，从而允许数据的继续插入．2、多代表点BIRCH算法BmcH算法是一种基于距离的聚类算法，这就必然带来一个缺陷就是不能发现不规则形状的簇，为了克服这个缺陷，黄添强等人【蛐l提出了采用多代表点的方法。定义3．1(代表点)从一个簇中选择出的在形状上具有一定代表性的n个点，通过收缩因子s，将这些点向质心收缩所得到的点称为簇的代表点。定义3．2(多代表点特征)假设某个簇中包含，n个d维的数据点，即数据对象抽庙{五‘)，其中XI={Xil，Xi2，．．．，Xia}，i=l，2⋯．，n，定义为一个三元的数组如·’—’下：MRF=(n，乩，Rcp)，其中n是簇中数据对象的数目，sL是n个对象的线性和Ⅳ^=X(扭J‘)，Rep是簇的代表点集，用来代表这个簇。则这带有代表点的聚类特征三元组称为多代表点特征。这个三元组记录了计算聚类的聚类的对象个数、代表点与质心，衡量簇之间距离通常采用的欧几里得距离和曼哈顿距离都可以通过代表点聚类特征求出，并且这些代表点概括了簇的几何或物理形状．定义3．3(多代表点特征树，MRF．树)一棵多代表点特征树(MP．F-树)是带有分支因子与阈值参数的平衡树，它存储了层次聚类的簇的统计特征与几何(物理)特征，如图l所示。每一个内部结点(非叶子结点)的分支因子为F，叶子结点的分支因子为L(L通常大于F，是聚类个数k的函数)，每个结点阈值为RT。分支因子F限定了每个内部结点最多含有的孩子的个数，即每个内部结点最多包含F个结点；阈值RT是指与距离最近的代表点的距离，它限定了存放在叶子结点中簇的大小．但与BIRCH的结点阙值T不同，BIRCH中闺值T是指存放在叶子结点中簇的半径或直径，故每个簇的大小是固定不变的，而MRF中的簇大小是可变的。当一个簇增大时，它的代表点将随着簇的边界扩大而移动，相应地，代表点或结点所能吸收的对象也增多，但代表点的个数不变．这样，结点所代表簇的大小没有严格限制的，并且可以有效地适应簇的各种形状，克服了引言中提到的BIRCH中CF-树的缺点▲(1)这个定义使叶子结点所覆盖的对象数目可大可小，可以对应数据的自然聚类；而不像BIRCH中结点大小是固定的，用户一旦设定了阈值，结点的半径或直径就固定了，这不能对应数据各种大小不同的自然聚类。(2)多代表点可以概括聚类的各种形状，有利于捕捉复杂形状的聚类而不像BIRCH定义了固定半径(或直径)的球形的结点，这不利查找球形以外的各种聚类。(3)分支因子与结点阙值影响了最终产生的树的大小。内部结点的形式为[EMRi，childi]，其中i-l，2，⋯⋯，F；MREi代表第i个结点的子聚类，childi是指33 工程亟主堂僮j盆塞筮三童基王鐾耋盆扭鳇基固差显麦达蕴造左鎏向它的第i个子结点的指针。叶子结点的形式为[MREi，prey，next]，指针prey，next用来连接所有的结点，以提高查询速度。MRF-树的插入操作：要建立一棵MRF．树最基本的操作是插入操作，这种操作分两种：一是插入新数据点的操作，另一种是重建树时旧的条目重新插入新树的操作。插入新数据点的操作可以看作是含一个对象的条目的插入操作，下文中这两种操作都以插入条目论述。这里我们定义条目A的所有代表点(或对象a)与另一条目B所有代表点距离的最小值，称为条目A(或对象a)与条目B的代表距离。插入算法的基本思想是：从根结点开始，由上向下查找代表距离最近的结点，达到叶子结点后，查找最近的条I；tLi，经测试阈值RT，若“能吸收E，则更新叶条目“；若不可以，则插入一个新的条目到叶子结点。如果插入后这个结点分支因子不超过L，则插入完成。否则，要进行分裂操作。与结点或条目的最近距离是用代表点来计算，这种方式可以有效提高计算速度。代表距离形式如下：RDist(Node，MRFi)=Min{Dist(Node．Repro，MRFi．Repn)，m=l，2，．．．，c：n予l，2，⋯，c，，其中c为代表点数目。测试RT也是用RDist(Node，Ⅶ旺i)进行计算。插入条目Node到叶子结点后，要对路径上的每个内部结点的MRF信息更新。每插入～个点立即重新计算代表点，这种动态地计算代表点的方法，会使代表点更加具有轮廓的代表性，而且可以节省时间，提高效率【581。3、基于扩展CF树的聚类分析算法阈值BIRCH算法和多分布点B玎良c=H算法，分别从阈值和中心点方面改进了BIRCH算法，能够适应各自特定领域的分析应用，但是，由于生物学信息的复杂性和特殊性，他们不能满足生物信息分析的需要，本文基于生物信息聚类需要，结合两种算法的优点，提出了～种扩展的cF树，并基于扩展的CF树提出了一个聚类分析算法。定义3，4(扩展聚类代表点)：从一个簇中选择出的在形状上具有一定代表性的11个点，通过收缩因子s，将这些点向质心收缩所得到的点称为簇的代表点。定义3．5(扩展聚类特征)：扩展聚类特征(E—CF)定义为一个五元组ETFi=(Ni，三墨，SSi，Repi，TO，其中(I=1，2，3，⋯，n)是簇中数据对象的数目，假定对n个簇Ci进行合并，设合并后簇为W，其聚类特征表示为ETFw=(N，三墨，Rep，T)，其中nN-E形i-1‘rt瑟=∑蕊 王程亟±堂僮迨塞筮三童基王覆娄筮扭酸基固差昱盘达缝选友洼T=max(dist(W．mean，Ci．mean+Ti))Rep是簇的代表点集，用来代表这个簇，T代表该簇的阈值，用来存储子节点的阈值信息，描述子节点中簇与簇的关系，mean代表gep簇的中心点Ct．mean=争∑竭W_me趾：兰!￡巩定义3．6扩展聚类特征树：记凹树为extend-tree，一棵扩展特征特征树(E-tree)是带有分支因子与阙值参数的平衡树，它存储了层次聚类的簇的统计特征与几何(物理)特征。每一个内部结点(非叶子结点)的分支因子为F，叶子结点的分支因子为m通常大-T-F，是聚类个数k的函数)，每个结点阈值为T。分支因子F限定了每个内部结点最多含有的孩子的个数，即每个内部结点最多包含F个结点；非叶子结点中的CF也包含阈值T，用来存储子节点的阈值的信息，描述子节点中簇与簇的关系。在插入过程中综合考虑两方面因素：与中心点的距离和簇的阈值，从而提高了数据对象插入的准确性；另外在节点分裂过程中引入分割因子P，通过分割因子的设定尽可能在最大限度的保持原节点的聚类特征信息的前提下，将节点中的聚类特征合理地划分开来。在重建过程中，当两个或多个簇合并为一个簇时，新簇的阑值由合并算法根据被合并簇的聚类特征求出。但与BIRCH的结点阈值T不同，BIRCH中阈值T是指存放在叶子结点中簇的半径或直径，故每个簇的大小是固定不变的，而E-tree中的簇大小是可变的．当一个簇增大时，它的代表点将随着簇的边界扩大而移动。相应地，代表点或结点所能吸收的对象也增多，但代表点的个数不变。这样，结点所代表簇的大小没有严格限制的，并且可以有效地适应簇的各种形状，克服了引言中提到的BIRCH中CF．树的缺点。我们在多代表点算法的基础上引进了多阈值算法的阈值调整，算法主要有代表点选择算法【辩1和结点插入算法，参考多代表点算法，具体算法描述如下：算法3．1：代表点的选择算法：输入：簇中点的集合输出：代表点过程：RepSelection(C){M--theentroidofC：／／C为聚类代表点合并后的集合，M为C的质心for=ltondo{fin为用户定义代表点的数目MaxRepDist--O；35 王崔熊±堂僮途塞筮三童基王鐾差盆圭丘的基固差是麦述缝选友鎏ForeachpointPinCdo{if(i=1)MinRepDist=Dist(P，M)／／第一个代表点是距离质心最远的点ElseMinRepDist=Min{dist(p，q)：qERepSet})，，第二个起的代表点是离已经选出的代表点最远的点。If(MinRepDist)=MaxRepDist){MaxRepDist=MinRepDist；RepPoin仁p)；}；RepSet=RepSetU{RepPoim))／／存放已选出的代表点。)；ReturnRepSet；)；算法3．2：插入算法：输入：插入点向量、扩展CF树输出：扩展CF树过程：Node+Insert_Entry_Etree(tree+T，Node+CurNode，EntryE){，，查找最近的结点EntryNewE，Node+NewNode；iffCurNodeisleafnode){／／若当前结点是叶子结点CLeatE=ClosestEntry(CurNode，E)；，／找到最近的条目，E为最近的节点if(Absorb(CLeafE，E)istrue／／若吸收后阈值小于该节点设定的阈值则吸收，并调整阈值{ThredModi(E)；／／调整闽值到节点最小值returnNull} 王捏亟±堂焦丝塞箍三童基王蕉娄筮蚯的基国差昱耋达蕴盗友迭e1∞{／／若吸收后阙值大于该节点阙值，则插人新条目NewNode=Node_Split_ForleafNode(CurNode，E)；，，插入新条目后返回值有两种，若为Null则不需分裂节点．否则分裂结点RetureNewNode，)，else{／／若当前结点不是叶子结点CNodeE=ClosestChild(CurNode，E)；，，查找最近的条目的结点)NowNode—Insert_Entry_Etrea(T，CNodoE，玢；／，循环递归寻找最近的结点iffNewNode==Null){／／不需分裂UpdateEF(CurNode．CLeatE，E))；／／不许插人新结点．只需更新吸收结点的路径上的CRFReturnNull：)；else{H需要分裂UlxlateEF(CurNode，CLe也，E)；／／更新EFNewEnt《reate_New_Emry(NewNode))，，产生新结点．NcwNodv=Node_Split_For_Nonleaf_Node(CurNode，NcwNode)；，，分裂结点iffNewNode==Null){／／不需继续分裂Merge_Not_Split(CurNode)ReturnNull：'else{／／需要继续分裂if(CurNodF=*T{／／若父结点为根节点’T—CreateNew_Root(CurNode，NewNode)；ReturnNun：}ElseretulllNe’^，Node；l 工程亟±堂僮监塞簋三童基王鐾娄筮圭匠趁基固羞基麦签缝选友洼))；3．4基于扩展cF树聚类分析算法分析基于扩展CF树的聚类分析算法，是针对基因数据具有海量、连续、复杂、存在缺损与误差等的特点的提出的分析方法，具有高效率，聚类结果独立于基因片段在空间的顺序，能处理各种不同形状的簇，并且对离群点是健壮的等性能，可以对海量的聚类数据进行压缩，并且能够捕捉复杂形状的簇。针对基于扩展CF树的聚类分析算法，我们从定性分析与定量分析两个角度来说明算法的优越性。3．4．1定性分析与单一定阈值或者单一多代表点的BIRCH算法相比较，基于扩展CF树的聚类分析算法在保留原算法优点的基础上，充分考虑到簇大小的不一致性，针对不同大小的簇采用不同的阈值，大大减少了聚类特征树的重建次数，从而降低了时间复杂度；在数据对象同时属于多个簇的情况下，将数据对象归属为较小阈值的簇，提高了算法的精确性，弥补了原算法中的不足。基因数据具有海量、连续，复杂、存在缺损与误差等的特点，要求宅间聚类算法具有高效率，聚类结果独立于基因片段在空间的顺序，能处理各种不同形状的簇，并且对离群点是健壮的等性能，已有的算法难以同时满足要求【”】。本文提出了一种基于多代表点的特征树，它基于BIRCH算法的思想，融人了CURE算法的优点，可以对海量的聚类数据进行压缩，并且能够捕捉复杂形状的族。利用该数据结构，采用随机采样的方法，提出了一个适合处理空间数据的聚类算法，该算法能够满足上述空间聚类算法的要求，有效地快速地处理海量空间数据。实验结果表明扩展CF犍算法可以识别不同形状的基因片段聚类，并且效率优于已有的适合处理空间数据的聚类算法BIRCH与CURE。最后，本文对影响算法的参数进行r评价，得出了随机采样比例、代表点的数目、收缩因子、树结点的分支因子与阈值等参数与算法聚类结果的关系。同时根据原有簇的阂值对新阈值进行修改，动态地调整合并后簇的阂值，调整后的阂值不仅包括原有簇的所有数据对象，而且大大增加了重建树后新的数据对象插入的可能性，最终产生不同阀值的聚类结果。3．4．2定量分析首先，我们讨论时间复杂性中的计算复杂性。上面我们已经指出算法在第一阶段随机取样的代价是很小的(不N2秒的时问从几十万个数据点中取到几千个样本数据)，故不作讨论。算法在第二阶段所耗费CPU的代价如下：设树的高度为h(树的高度是由内存的大小与页面大小决定的)，树的内结点分支因子为F，为了插入一个 王程亟±堂焦i金塞差三重基王嚣耋筮扭的基固差显垂述蕴盗友洼点，需要访问的结点数为l+logFh。在每一个结点为了查找最近的结点必须检查F个结点，访问结点的代价与对象纬度d有关，故插入所有的对象生成一棵树的代价是O(d*n*F(1+logFh))但是，通常树不是一次生成的，必须经过多次的重建。设最多有1个叶子结点需要重建，故重建树的代价是O(d*l*F(1+logFh))。设第一次装入内存的对象数是nl，要建树的总结点数是n．我们提高阈值的启发式方法是把I汀设为所有最邻近的结点代表点之问的距离的平均值，每一次树的重建将把树的高度降为一半，故重建树的次数为l092(n／n1)。故重建树的总代价为O(1092(n／n1)+d+z+F(1+logFh))所以第二阶段算法的总代价为O(d*n*F(1+IogFh)+l092(n／n1)。d+l+F(1+logFh))。值得注意的是，第二阶段操作的对象都是第一阶段取样的对象，它们通常约为总对象的3％．对于基因数据的操作，时间复杂性更重要的是花费在I／0的时间。第l阶段对数据进行取样要扫描一次数据库，第2阶段在处理离群点时会访问内存，但这极少次数的访问可以忽略不计．第3阶段在内存进行，没有I／0时间。第4阶段算法再次访问一遍数据库。故本算法I／0的时间复杂性为0(n)。在空间复杂性方面，本算法对内存并没有特别的要求，算法可以适应不同的内存，当内存空不足时可以空间来换取时间。3．5本章小结本章结合生物学SAGE数据库数据的特点，主要关注层次聚类算法，采用扩展的CF树聚类分析算法，针对可变阈值和多代表点特征树改进BⅡ屺H层次聚类算法，用以分析基因表达数据。由于基于距离限制的多代表点算法在数据分布己知，而且各个类别所含数据的分散度比较接近时，容易找到合适的距离阐值，如果数据分布未知，或者各个类别所含数据的分散度相差比较大时，很难确定限制距离阐值的大小，因而会造成聚类结果会较差。因此在分析基因表达数据时，效果并不是十分显著，而多代表点特征树算法对高维数据集能够很好的表达所输入数据集的空间分布的特点，模型本身自组织的特性使得其对噪声或者奇异点聚类不充分。因此在分析基因表达数据时，我们采用融合了关于代表点和可变阈值的扩展特征树聚类算法，基于扩展CF树得聚类算法很好的聚类了不规则形状的簇，并能对噪声数据何奇异点数据不敏感，提高了基因数据聚类的效率和效果。 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现经过不断的改进SAGE技术已成为基因表达模式研究的一项有力的工具，而数据的不断积累为进行多样本基因表达差异分析提供了可能。对于国内大多数实验室来说，构建SAGE标签库及相应的测序花费还是显得过高，但是各研究单位可以根据自身的研究方向，充分利用已发表的SAGE数据资源，结合聚类分析，统计分析、表达差异、可视化技术等计算技术以及虚拟Northem杂交等研究方法，对特定组织或细胞的～些已知或未知标签对应的基因进行研究，以期发现一些组织特异性表达或与某些病理变化相关的新基因或蛋白，这不失为一种简便而易行的研究途径，本文就是这种研究方向的一个实现。4．1设计概述人类基因组技术产生的大规模数据的存储与管理就成了生物研究人员必须面对的问题。另外，随着生物信息技术的研究与发展，基因表达数据及其分析已经和众多计算机相关学科紧密地结合在一起，其中涉及到很多方法思路以及设计实现并不是生物学研究人员的长项。同时。数据分析后所产生大量试验结果多以数字的形式为主，而研究人员希望能够更直观、更便利的对试验结果进行查询、比较、分析，从而对试验的结果产生深入的理解唧】。为了解决诸如以上这些问题，我们充分利用数据处理、数据挖掘、数据可视化等技术建立的该套生物信息学分析方法：扩展的CF树基因表达数据聚类分析方法，是基于开放的基因表达数据挖掘平台，整合了数据预处理、聚类分析、差异表达以及生物杂交的生物学和数据挖掘功能，可以方便地为生物相关领域的研究人员提供基因表达数据挖掘服务，为研究人员提供了一个生物信息学分析的试验平台。该平台的核心是在基因数据处理的基础上设计的基于扩充CF．树的聚类分析算法，该算法是以扩充—cF树为其基础数据结构，同时该算法可以很方便的语其他算法进行结合。下面我们主要针对该平台相关设计与实现内容进行介绍。4．1．1设计原则在充分分析研究已有的基因表达分析方法的基础上，根据基因表达差异筛选的特点，提出以下几条设计原则：·数据源异构处理。基因表达数据格式多样，因此要充分考虑数据格式的异构性问题，应该提供统一的数据访问接口，屏蔽数据源的异构性，做到能让用户透明访问数据，尽量减少数据访问的用户控制成份，这样的系统才能具有较强的健壮性和可扩充性。·增量式数据分析能力。由于基因数据库中的基因数据量大，并且基因功能不40 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现明确，因此，要求选择数据处理与聚类算法时应该考虑增量式方法，从而对于新增加数据时不需要所有数据再重新处理扫描．●友好的人机交互功能。在界面设计过程中，既要考虑到专业人员的需要，也要考虑非专业人员的特点，所设计的系统应易于各类人员使用。·模块化的软件设计。这样可以使系统软件结构清晰、易于维护，增强软件的可重用性，提高整个系统的开发效率。4．’．2设计目标本文所提出的基于扩展CF树的数据聚类算法是在B琢CH算法的基础进行的改进，基于该算法设计实现的基因表达数据分析平台应能很好的满足第三章所提出的具体需求。主要满足以下功能：·提供基因表达数据的抽取与装载功能．能适时接收并处理不同样本的基因表达数据，并能对这些不同样本数据进行合并处理。●提供基因表达数据的浏览与管理功能．必须提供基本的基因表达数据浏览和可视化功能，同时在用户信息需求基本明确的情况下，能根据用户的输入条件精确查询符合查询条件的基因信息．，●提供针对多样本的基因表数据进行分析的功能。针对基因表达数据进行基因差异分析和数据挖掘分析的功能，对样本池的基因片段进行聚类和样本丰度计算，并能对基因表达数据进行差异分析和筛选。4．2系统设计4．2．1总体结构本文总体结构如图4．1所示：4l 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现4．2．2数据结构图4-1总体结构图系统采用C语言，ORACLE8．0．5进行设计、开发、编码、调试。程序采用面向对象思想进行设计，具体数据结构类如下：l、扩展CF向量类定义classEntry{public：intn：Vectorsx；doublesxx；CArrayDset；／／代表点集合Doublethred：／／闽值牟if．defRECTANGLERectangleBoxrect；群endifRECTANGLEEntry()；／／构造函数voidInit(shortd)；／／初始化函数voidReset()；／／重设Entry(constEntry&ent)；／／构造函数～Entry0；／／析构函数 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现voidoperato—constEntry&ent)；voidoperato—constintval)；voidoperator=-(constVector&v)；shortDimOcon．st；intNOconst；voidSX(Vector&tmpsx)const；doubleSxxoconst；／／canbecalculatedfromn,sx,sxxvoidxo(v∞tor&tmpxO)const；doubleDiameter0const；doubleP．adiusOconst；doubleFitness(shorttb2pe)const；doubleNorm_Kernel_Density_Effect(constVector&】【，doubleh)const；doubleNorm_KernelProbEffect(constVector&a，doubleh)con．st；doubleUnif_Kemel_DensityEffect(constVector&x,doublenconst；doubleUnifKernel_I'rob_Effect(constVector&a'doubleh)const；群ifdefR：ECTANGLE／／Rectanglerectoconst；voidRect呦gleBox&tmprect)const；#endifvoidoperatorqconstEntry&em)；voidoper砒or—co哑Entry＆em)；／／Entryoperator+(constEntry&ent)oonst；voidAdd(constEntry&el，constEntry&e2)；／／Entryoperator-(constEntry&ent)const；voidSub(connEntry&el，constEntry&哟；voidTransform(constVector&W，constVector&M)；voidVisualize_Circle(ostream&fo)const；voidVisualize_Circle(ofstream&鼢const；voidVisualize_Reaangle(ostre垃m&础const；voidVisualize_Rectangle(ofstream&向1const；／／DOeudidiandistanceofcentroidsdoubleoperatorllCcoustEntry&ent)const；4， 三堡堡主兰垡堡塞兰婴童茎王窭耋坌堑塑董里耋垄茎墨堑!童堡生皇塞翌一／／D1manhatandistanceofcentroidsdoubleoperatorX(eonstEntry&ent)const；／'／D2inter-clusterdistancebeforemergedoubleoperatorl(constEntry&ent)const；||D3itara-clusterdistanceaftermergedoubleoperator&(constEntry&ent)const；／／varianceincreasedistance1)4doubleEntry：-operator&&(constEntry&v2)const,／／inputentryfriendistream&operator>>(istream&fi，Entry&ent)；friendifstr髓m&operator>>(ifstream&fi。Entry&em)；l|inputdatapoint褐entry：friendistream&operator：叫istream&fi，Entry&en嘎friendifstream&operator>---(ifstream&fi，Entry&ent)；||outputentryfriendostrenm&operator<<(ostream&fo，constEntry＆eⅡt)；fiiendofstream&operator<<(ofstream&fo，constEntry&em)；||connectivitytestsfriendshortcormected(constEntry&entl，constEntry&ent2)；friendshortconnected(constEntry&entl，constEntry&ent2，shortt}type，doubleFt，doubledensity)；||RPeffectsfrienddoubleNormKernelRfEffect(constEntry&entl，constEntry&ent2，doubleh)：frienddoubleUnif_KerndN里ffec：t(constEntry&eml，constEntry&ent2，doubleh)：)；istream&operator>>(istream&fi，Entry&em)；ifstream&operator>>(ifstream&fi，Entry&em)；istream&operator>=(istream&fi，Entry&ent)；ifstream&operator坷ifstream&fi，Entry&emXostream&operator<<(ostream&fo，constEntry&em)'ofstream&operator<<(ofstream&fo，constEntry&eflt)；shortconneaed(constEntry&entl，constEntry&ent2)；shortconnected(constEntry&entl，constEntry&ent2，shortlhlpe，doubleFt)； 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现doubleNorm_KernelRfEffect(constEntry&entl，constEntry&ent2，doubleh)；doubleUnif_KerneL咿珏ect(constEntry&entl，constEntry&ent2，double”；扩展CF-树的层次结构类classHierarchy{public：intsize；intstep；im+ii：im巧；Entry‘c￡double’dd：shortstopchain；intchainpw,int+chain；Hierarchy(intn，shortd){size=n：step2-l：ii=ncwim【n】；JJ=newim【n】；cf=BewEmry[n】；for(inti=o；iattrproj->FirstRccId(recidl)；r∞idl=o；彬曾量聚类时，从界面指定。VectorArray‘vectors；Paras->CreateRecordList(vectors)； 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现Entry+entries=newEntry[1]；for(i=O；iDimension)；，，l开始扫描数据VectorrecVector；recVector=vectors->at(o)；booldstat；for(recidi=recidl；；recidi++){dstat=Parav>Readgec(recidi，recVector)；if(!dstat)break；entries[0]=recVector；if(Stats[0]一>WMfhg)entries[0]．Transform(Stats[O]->W，Stats[0]-埔D；switch(Stats[O]->PhaselScheme){easeO：Stats[O]一>AcceptlA(entries[0])；break；casel：Stats[0]->AcceptlB(entries[0])；break；default：print_error(”BirchPhasel”，。invalidPhaselScheme’’1；break；')／／2数据装载完毕，构建扩展CF数for(i=0；i<1；i++){if(Stats[i]·->SplitBuffer!=NULL)Stats[i]·->ScanSplitBuffer0；if(Stats[i]··>OutlierQueue!=NULL)Stats[i]·->ScanOutlierQueue0；／／cout<<”#”<name<<”“／／<Phase<<”<Passi<<’‘”／／<MemUsed<<”<CurrDataCnt<<’⋯／／<CurrEntryCnt<<””<CurFt)<PhaselScheme){caseO：Stats[i]->RebuiltTreelA(0)；break；easel：Stats[i]一>RebuiltTreelB(0)；break；52 工程硕士学位论文第四章基于聚类分析的基因表达差异筛选设计与实现default：print_error(”BirchPhasel“，break：)／／cotn<<“妒<name<<。。／／<Phase<<“<Passi<<”II<MemUsed<<。。<CurrDataCnt<<。。／／<CurrEntryCnt<<”<CurFt)<SplitBuffer!=NULL)Stats[i]->ScanSplitBuffcr0；if(Stats【i】->OutlierQueue!=NULL)Stats[i]->ScanOutlierQueueO；)DeletevectorsDelete口entries；)5．差异计算利用以上章节提出的聚类算法的结果，将筛选出的数据中2个正常胃组织来源的文库构建文库池(P001)A，4个胃癌来源的文库构建文库池B。以表达差异率F(Expressionfactor)>29统计学指标P