（计算机科学与技术专业论文）空间环境生物信息学数据的分析方法研究.pdf

中文摘要 摘要 生物信息学是由生物学、应用数学、计算机科学相互交义所彤成的学科，c r 数掘挖掘作为一个崭新的计算机应用领域在生物信息学叶l 有着j 1 泛的j 避j h 。空川 环境生物信息学数据的分析方法研究是在生物信息学范畴内，基于当今同渐成熟 的太空技术展开，主要用来研究空间环境对水稻种子产生的生物学效应的机制， 即针对空间环境诱变因素数据以及生物学实验分析获取的表型组、蛋自质组的变 化信息数据进行存储、集成和管理，在此基础上，对数据进行聚类分析、天联规 则挖掘，试图找出空间环境诱变的机理及蛋白质约l 改变机制。 在查阅大量国内外参考文献基础上，本文开展了以下几项工作： 构建诱变水稻变化信息的数据库系统，其中包括空间环境诱凶信息、诱变水 稻的表型组和蛋白质组信息。 构建数据仓库，解决不同组学之间存在的数据不一致、冗余、噪声等问题， 为后续的数据分析与挖掘j 【作打下良好的基础。 提出了基于投票机制的动态聚类融合算法，该算法自动确定聚类个数，利用 不同的相似度准则运行k m e a n s 算法，实现了动态确定运行次数，并将多次运行得 到的结果映射到关联矩阵，使用投票机制获得最终的数据划分。该算法具有对领 域知识要求和参数依赖程度低等特点。 优化并改进了经典关联规则a p r i o r i 算法，该算法针对牛物信息学数抓普遍存 在着维数过大、数据量巨大等特点，通过减少数据库记录的扫描次数及频繁项集 的生成个数提高算法效率。 关键词：生物信息学；数据挖掘；空问环境诱变水稻；聚类融合；关联分析 英文摘要 a b s t r a c t b i o i n f o r m a t i c si sac r o s s d i s c i p l i n es u b j e c tb yb i o l o g y ，a p p l i e dm a t h e m a t i c sa n d c o m p u t e rs c i e n c e h o w e v e ra san e w f i e l do fc o m p u t e ra p p l i c a t i o n s ，d a t am i n i n gh a sa w i d er a n g eo fa p p l i c a t i o n si nb i o i n f o r m a t i c s t h er e s e a r c ho na n a l y t i c a lm e t h o d so f s p a c ee n v i r o n m e n tb i o i n f o r m a t i c sd a t a ，w h i c hi si n c l u d e di nb i o i n f o r m a t i c sa r e a s ，b a s e d o nt h em a t u r i t yo ft o d a y sl a u n c ho fs p a c et e c h n o l o g y ，m a i n l ys t u d i e st h em e c h a n i s mo f b i o l o g i c a le f f e c t so ft h er i c es e e d st h es p a c ee n v i r o n m e n tc a u s e d a c c o r d i n gt ot h e c h a n g e dd a t ai n c l u d i n gs p a c ee n v i r o n m e n ta n dt h ep h e n o t y p e ，p r o t e o m i c sw es t o r e ， i n t e g r a t ea n dm a n a g eo fb i o l o g i c a le x p e r i m e n t s ，w et r yt of i n dm e c h a n i s mo ft h es p a c e e n v i r o n m e n tg e n e r a t e da n do ft h ep r o t e o m i cc h a n g e su s i n gr e l e v a n tm c t h o d ss u c ha s c l u s t e r i n ga n da s s o c i a t i o na n a l y s i s a f t e rr e a d i n gl o t so fr e f e r e n c e s ，w ec a r r yo u tt h ef o l l o w i n gt a s k si nt h i sp a p e r ： b u i l dt h er i c em u t a t i o nd a t a b a s es y s t e m ，s t o r i n gt h ed a t ao fs p a c ee n v i r o n m e n ta n d t h ep h e n o t y p e ，p r o t e o m i c so fb i o l o g i c a le x p e r i m e n t s b u i l dad a t aw a r e h o u s et or e s o l v et h e p r o b l e m s o fd a t ai n c o n s i s t e n c i e s ， r e d u n d a n c y ，n o i s ea n do t h e ri s s u e sf o rs u b s e q u e n ta n a l y s i s a d y n a m i cc l u s t e r i n ge n s e m b l e sa l g o r i t h mb a s e do nv o t i n gm e c h a n i s m i sp r o p o s e d ， w h i c ha u t o m a t i c a l l yd e t e r m i n e st h en u m b e r so fc l u s t e r i n g ，u s e sd i f f e r e n ts i m i l a r i t y c r i t e r i at or u nk - m e a n sa l g o r i t h mm a n yt i m e s ，t h e nt h ef i n a ld a t ap a r t i t i o ni so b t a i n e db y t h ev o t i n gm e c h a n i s mo v e rt h ea s s o c i a t i o nm a t r i xt h a tt h er e s u l t sa r em a p p e dt o t h e a l g o r i t h mr e q u i r e sl o wk n o w l e d g eo f t h ea r e aa n dd e p e n d e n c ep a r a m e t e r s i m p r o v ea n do p t i m i z et h ec l a s s i c a la p r i o r ia l g o r i t h m ，b e c a u s eo fl a r g ed i m e n s i o n s a n ds i z e so fb i o i n f o r m a t i c sd a t a ，w h i c hc a nr e d u c et h et i m e so fs c a n n i n gd a t a b a s ea n d t h es i z eo ft h ec a n d i d a t ei t e m s e t si no r d e rt oi m p r o v et h ea l g o r i t h me f f i c i e n c y k e yw o r d s ：b i o i n f o r m a t i c s ；d a t am i n i n g ；s p a c e i n d u c e dr i c em u t a n t ；c l u s t e r i n g e n s e m b l e ；a s s o c i a t i o na n a l y s i s 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 窒间坯撞尘塑值星堂数型的岔逝友选婴究：。除论文巾 已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在义q j 以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公丌 发表或未公开发表的成果。本声明的法律责任山奉人承担。 学位论文作者签名：查壹查& u 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海南大学有火保留、使用研究化学 位论文的规定，即：大连海事大学有权保留并向围家有关部门或机构送交学位沦 文的复印件和电子版，允许论义被禽阅和借阅。本人授权大连海事入学叮以将本 学位论文的全部或部分内容编入有关数据库进行检索，也r j 丁采用影印、缩印或j ：l 描等复制手段保存和汇编学位论文。同意将奉学位论文收求到中凼优秀博硕二f ： 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、巾圈学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在 年解密后适用本授权+ b 。 不保密囹( 请在以上方框内打“”) 论文作者签名：套两审习导师签名：易 蝴丫钆月丫日 空间环境生物信息学数据的分析方法的研究 第1 章引言 2 0 世纪8 0 年代未，人类基凶组计划的启动推动了生物信息学的产1 t - 年u 蓬勃发展。 该计划获得了大量数据，从这些数据的分析中获取有用的! 卜物学信息，导致了乍物信息 学的产生。生物信息学是在生命科学研究中以计算机为j j ：具对生物信息进行储存、检索 和分析的科学，而数据挖掘是一个崭新的计算机应用领域。随着数据挖掘技术的f 断发 展与成熟，数据挖掘技术对生物信息挖掘的应用起着越来越重要的作用。 1 1 研究背景 1 1 1 空间生命科学与地面模拟辐照 空间生命科学足研究在空间环境条件下牛物体的尘长、发育和演变规律的l j 学 科。空间飞行环境中伴有高辐射，无搔夜、微重力等，这种胁迫环境使得，j i 物体在形态、 细胞水平等发生改变，生物体的基因表达发生变化，并进步诱导突变体的产q - ：。例如， 微重力环境下大鼠中枢神经系统胶质细胞蛋白s 1 0 0 的表达水平娃著增强1 ；微鳗川l 起大鼠海马、顶叶皮层g f a p 蛋白的表达上调【2 1 等等。 国外空问生命科学研究始于1 9 6 0 年左右，美国和f i i j ? j , 联等同家在各种类型窄l 【j j 匕 行器上研究空间条件下植物生长发育规律，失重对生物系统的作用机理，宇宙辐射对乍 物机体的影响研究，特别是宇航员在宇宙空问长期活动造成的牛理变化【3 1 。 我国空间生命科学研究始予1 9 8 7 年，主要针对空| 1 j j 植物学研究。近年来随着我h 宇航事业的发展，尤其是神舟五号和六号载人飞船的发射成功，利用空间环境进行诱叟 育种已经越来越多地引起一些育种专家的兴趣l3 1 。除了培育新品种以外，生物学家还研 究植物种类、机能状态、组织和分裂周期状态等对辐射的不同效应以及植物组织损伤。恢 复机理等。 地面模拟辐射是利用地面的高能粒子力| l 速器对辐射材料进行巾测素辐射从而研究 辐射对生物体损伤的一种实验手段。空问辐射环境相对复杂，地面环境雉以完仓模拟， 因而可选择不同的重金属离子作为辐射的粒子源来进行地面模拟辐射的实验。冈此地面 第1 章引育 模拟辐射足研究卒i h j 辐射的一个重要途径，也是目前围内外开展空i 白j 辐射生物学研究的 荸要方法。 综上所述，我们可以利用高能量重离子的地面模拟辐射来研究空间辐射对水稻基因 组的影响。使用模式生物水稻丌展地面模拟辐射实验，使我们可以获得许多有价值的实 验数据，从而更好地为研究空间辐射对生物体的损伤效应提供理论依据。 1 1 2 水稻生物信息学研究概述 作为剀际上已被公认的遗传和发育研究的模式植物，水稻是禾本科作物中基因组最 小的作物，1 9 9 8 年由中国、几本、美闷和法固等1 0 个国家和地区共同发起承担的“国 际水稻堆| 大i 组l t 划”( i r g p ) 启动。2 0 0 2 年完成了粳稻品种同本晴的测序及第l ，4 ，1 0 条染色体的完成图f 4 】；此外在中困广为种植的籼稻品种。陆矮4 号的第四条染色体的精 细测序也已究成。水稻皋冈组测序的基本完成，使得对其基冈组的研究更加方便易行。 随符l q 际r ：联网的快速发展，生物信息学迅速发展。广义的说，生物信息学是通过 对琏闪组的研究，获取、加工、存储、分配、分析和解释相关牛物信息。这包括了两层 含义，一。足对大罩数据进行收集、整理等；另一层即从中发现新的规律。美国、日本及 欧洲各h 的牛物信息学已相继在i n t e m e t 上建立了大型数据库，为研究人员提供数据的 分析、处理、采集、交换等服务。在我国，生物信息学还处于初期发展阶段。 二i 阿q ：联网上存在大量水稻生物信息资源，各种应用软件层出不穷。利用现有的网 络资源对水稻壤冈组、蛋白质组、表型的分析j 研究中发挥着巨大的作用。数据挖掘是 一个崭新的计算机应用领域，随着数据挖掘技术的发展，数据挖掘技术在生物信息学中 有着广泛的应用。 ( 1 ) d n a 序列f h j ) r t t 似搜索和比较【5 1 。在基因分析中一个最为重要的| u j 题是d n a 序 列巾的相似搜索和比较。基因分析所需要的相似搜索技术与时序数据中使用的相似数字 方法f ii r d 。l 捌为壤凶数据是非数字的，其内部的1 i 同种类核苷i 日j 的精确交叉起着重要的 功能角色。凶此在d n a 序列相似搜索和比较上，我们仍需探求更有效的方法，对数据 变换的伸缩、规范化和窗口缝合等时序数据分析中经常用到的方法加以改进、优化从而 适j j 渺用。 卒问环境生物信息学数据的分析方法的研究 ( 2 ) 关联分析【6 】。大部分疾病足由多个皋囚组合起来共i 一作用的结果。关联分析方法 有助于发现基冈组和对基因间的交叉与联系。 ( 3 ) 聚类分析。在基因的表达、d n a 序列的研究巾，聚类分析l 经成为j ：婴分析i ： 具。聚类就足根据事先确定的相似度准则将研究对象划分剑4 同的簇，使得州簇之| 1 i j 高 度相似且异簇之间娃著不同。 ( 4 ) 可视化工具和遗传数据分析7 1 。基冈的复杂结构和序列模式通常i 叮以通过各种呵 视化工具以图、树、链的形式展现，促进模式理解，为壁凶表达分析提供仆常彳j 价值的 工具，助于从新的视角看待基凶组水平的转录调控并建立模删。 1 2 研究意义 通过对引起水稻种予变异的空间辐射环境的分析，从植物学、细胞生物学及分r ，卜 物学等角度研究空间环境对水稻种子的生物学效应，1 0 5 时，我们认为对象f 与为同一类；否则，该 对缘单独为一簇。簇f n j l o 离度量方法统常有i j u 种5 4 】：最小距离、最大距离、平均距离、 均值距离。最大和最小度鼍代表簇间距离度量的两个极端，因此我们采用一种折中方法 空问环境生物信息学数据的分析方法研究 使用平均距离克服离群点敏感性问题，即如果簇的数目大于确定的聚类数目k ，我们将 采用a v e r a g e l i n k a g e 技术进行簇与簇之问的合并，直到最终聚类个数为k 。 3 2 6 动态确定运行次数 文献 5 4 中人为确定运行次数( 如n = 9 0 ) ，如果n 值过人导致运行时间相对较长 且浪费资源；而n 值选取过小则会影n 向最终聚类融合的结果。凶此，我们采用卜面的力 法来动态确定运行次数刀。 对样本数据集d 进行聚类融合，运行一次会得到两个结果：其一足运门j 余弦度量i t 算样本与样本之问的相似度；其二是通过p e a r s o n 相关系数计算相似度得到的聚类结果。 我们假设运行次数为n 。 动态确定运行次数n 的方法如下： ( 1 ) 当n 2 1 时，得到的两个聚类结果乃、万：进行聚类融合结果为1 1 ； ( 2 ) 当，z 2 时，得到的两个聚类结果刀：川、万：。与乃、万：7 ：。一：再次进行融合， 得到的聚类融合结果为1 1 。； ( 3 ) f 。与r 。进行比较，如果相同，算法结束；否则，令n + + ，删除聚类结果r 。- l ， 返回( 2 ) 。 通过该方法动态确定的运行次数n 不会过大导致运行时间相对较长，影响聚类融合 效率浪费资源；此n 值的确定是根据算法结果是甭稳定求得，从而不会冈为n 值过小影 响最终聚类融合的结果。 3 2 7 算法描述 综上所述，本文提出的基于投票机制的动态聚类融合算法的算法描述如下： 输入一个具有n 个样本的数据集d = x i , x 2 ，x 3 ，) 。 输出样本的聚类结果。 初始化：c o a s s o c ( i ，j )存储样本i 与j 同为一类的概率。 s t e p l 利用文献 2 中的一趟聚类算法，基于数据分前i 确定聚类个数k 。 第3 章基丁投票机制的动态聚类融合算法及其应用 s t e p l 1 根据不同的相似度准则得到的两个k - m e a n s 算法聚类结果乃、乃聚类融合 结果为f ； s t e p 2 运行k - m e a n s 算法刀次( 其中n 2 ) s t e p 2 1 当厅2 时，不司的相似度准则得到两个数据划分y 2 川、 2 。与 7 l 、7 1 2 7 2 帕再次进行融合得到融合结果； s t e p 2 2 更新c o a s s o c ( i ，j ) 矩阵： s t e p 2 3 扫描c o a s s o c ( i ，) ，使用a v e r a g e 1 i n k a g e 技术合并簇得到聚类融合后的 数据划分f 。； s t e p 2 4 比较r 。与f ，如果二者不同，返回s t e p 2 ：否则，算法结束。 3 2 8 实验结果及其讨论 我们在u c im a c h i n el e a r n i n gr e p o s i t o r y 5 5 】提供的机器学习数据集以及人造数据集 上对算法进行测试。实验所用环境是w i n d o w sx p 操作系统，编程语言为c 拌。在实验中 数据足按照随机顺序处理的。重复运行本文提出的基于投票机制的动态聚类融合算法1 0 次( = l ，2 10 ) ，列m 每次运行过程中所需要的动态运行次数甩和准确率a c c u r a c y 。 其i i 参数k 与数掘集本身的类数保持一致。 真实数据集 本文中采用了2 个真实的数据集：i r i s 和w i n e 。上述数据集是用来进行分类操作的， 冈此我们已知样本的分布情况。其中i r i s 数据集有1 5 0 条记录，每条记录由4 个分类属 性组成，分析j 情况为5 0 5 0 一5 0 ；数据集w i n e 有1 7 8 条数据，每条记录由1 3 个分类属性 组成，分和情况为5 9 7 1 4 8 。实验结果如表3 1 所示。 二人造数据集 如图3 4 所示是二维平面上随机产生的两个半环数据集，其中上半环有1 0 0 条数据， 下半环有1 0 0 条数据，总数据集为2 0 0 。实验结果如表3 1 所示。 空阃环境生物信息学数据的分析方法研究 削3d 人选、r 环数据集 f i g3 4s y n t h e t i ch a l f - r i n gd a l a s e t 随机雠半皿e 产牛一个双圆数据集。其中外侧i f j 】有2 0 0 条数据，内n i * 1 4j 1 2 1 条 数据总数据集为3 2 1 。数据分布如图3 5 所示，结果见表3 1 。 幽35 人造烈吲数据业 f i g , 3 5s y n t h e t i c t w o - c l r e t e d a t a s e t 随机产生二维平而上的数据集数据分布如图3 6 。其中总数抛集为4 0 0 。实验结粜 如表3 1 所示。 第3 章基丁投柴机制的动态聚类融合算法及其m 刖 陶36 人j 盘花瓣数据集 f i g3 + 6s y n t h e t i cf l o w e r d a m s e t 表3i 不m 数据批r 算法琏打的动忐次数1 ，准确率 t a b3i c h l s t e r i n g m s u h s w i l hd y n a m i co p e r a t i n gn u m b e r sa n da c c u r a c i e s o nd i f f e r e n td a t a s e l s 从表3i 的吱验结果我们可以得h 以下结论： ( 1 ) 此算法动态确定运行的次数n 相对较少，具有节省时间、提高运行效率、节约资 源等优点。 ( 2 ) 算法的准确率比较高得到的结果相对稳定 空问环境生物信息学数据的分析方法研究 ( 3 ) 本算法对领域知 ： 要求低，对数据输入顺序具有稳健性。 ( 4 ) 该算法对合成的数据集，即不规则结构的数据集的识别能力较强。 三与单一的k - m e a n s 算法比较 通常情况下，聚类准确率作为考察聚类算法优劣的标准。凶此我们采取该算法与 k - m e a n s 算法分别在上述的真实数据集和人造数据集上运行1 0 0 次，计算得剑的平均聚 类准确率。实验结果如表3 2 所示，通过对平均聚类准确牢进行比较，完成该算法与单 一k - m e a n s 算法的比较。 表3 2 聚类结果比较 t a b3 2 c l u s t e r i n gr e s u l t sbyd i f f e r e n tc l u s t e r i n ga l g o r i t h m s 从实验结果表3 2 中我们可以看出，基于投票机制的动态聚类融合算法得到的聚类 结果优于单一的k - m e a n s 算法；对于单一的k - m e a n s 算法而言，提出的此算法能史好的 识别出不规则结构的数据集。 3 2 9 结论 本文采用了一种基于投票机制的动态聚类融合算法，该算法自动确定聚类个数k ， 实现了动态确定运行次数，利用不同的相似度准则运行k m e a n s 算法2 n 次，得到的 结果映射到关联矩阵，使用投票机制最终获得数据划分。本算法对领域知谚 要求低，对 参数依赖程度低，并且对数据输入顺序具有稳健性，与单一k - m e a n s 算法相比提高了聚 类的准确率并且能够很好地识别出不规则结构的数据集。 第3 章基丁投禁机制的动态聚粪融台算法及其戍埘 33 水稻生物数据的应用 331 实验数据 实验数据为r i c e p r o t e o m e d a t a b a s e 中双向电泳凝胶数据库中的数据。该数据库中包 禽水稻若干组织、 | 官相关的蛋白质二维聚丙烯酰胺电泳参考圈。我们选取幼苗叶片组 织的：维聚丙烯酰胺电泳图的数据进行数据分析。数据从以下站点可获得 h t t p ：g e n e 6 4 d n aa f 毋c g o j p r p d d a t a l b y l b l ，h t m l 。如图3 7 所示，该图包含6 7 9 个 蛋门质 ，其中1 9 5 个蛋白质点根据质谱结果可以在n c b i 中蠢询到相关信息。我们对 这1 9 5 个点进行上面提到的摹 ：投票机制的聚类融合算法进行融合，试图发现蛋白质点 之删的功能相关性。 旷二藏 酗37 幼* d i 片组织的二雏聚丙烯酰胺电泳图 f * 3 7 l e a f b l a d e y o u n g t i s s u e s o n t w e - d i m e n s i o n a p o l y a c r t l a m i d e g e le l e c t r o p h o r e s i sr m m a p s 为了考察聚类结果中每簇的显著生物特性，我们将n c b i 中能查询到的每一个蛋 门质点的a c c e s s i o n n o 输入到u r i p r o t 数据库中，根据o n t o l o g y 注释考察蛋白质的生物 特性。其中to n t o l o g y 中的注释范围包括有分子功能( m o l e 叫盯f u n c t i o n ) 、生物过程 空间环境生物信息惴摒的分析方法研究 ( b i o l o g i c a lp r o c e s s ) 和细胞组成( c e l l u l a rc o m p o n e n t ) 。由于细胞组成的分类方法过于笼统， 根容易将功能差片很人的蛋白质分到同一组巾，对最终的聚类结果产生影响，闻此奉史 验中仅仅从分子功能和生物过程对牛物特性进行标注。 332 结果讨论 基于投票机制的动态聚类融合并法的实验结果如幽3 8 ： n h 一一l hn n 1 t | 警i3 8 基_ 。投票机制的动态聚类融合葬法的聚类结果 f i g - 3 8 m s u l t s b y d y n a m i c c l u s t e r i n g e n s e m b l e s a l g o r i t h m b a s e do r v o t i n g m e c h a n i s m 其中各个簇的具体信息详见表格3 3 。 表33 弁个攘的对象数域 t a b3 3o b j e c t sn u m b e r si no v e r ) c l u s t e r 类别i 类圳2 类别3 7 4 9 飞蠢适薹罐鍪童薹8885 第3 章基丁投票机制的动态聚类融合算法及其戍j j 类别4 类别5 类另u6 类别7 1 6 0 3 4 8 在得到的结果中，我们发现类别4 包含了大量对象，总共有1 6 0 个对象，其中有4 6 个点在u n i p r o t 巾没有记录功能，剩下的蛋门质点中1 4 个点功能过于细化无法与其他点 的功能形成联系，因此没有把它们列入下列子功能中。下面对类别4 中的数据进行生物 注释。 表3 4 类别4 中对象的生物注释 t a b3 4b i 0 1 0 9 yn o t eo fo b j e c t si nc l u s t e rf o u r 生物注释个数蛋白质点编号 a t pb i n d i n g 2 01 5 6 ，2 1 0 ，2 2 2 ，2 4 6 ，2 5 2 ，2 5 4 ，2 8 2 ， 2 9 6 ，3 4 5 ，3 6 l ，3 7 7 ，4 0 l ，4 2 6 ，4 5 3 ， 4 5 6 ，4 8 0 ，5 7 4 ，5 9 5 ，5 9 7 ，6 0 6 r n ab i n d i n g6 1 6 2 ，2 0 l ，3 2 0 ，3 4 8 ，5 8 8 ，5 9 3 f a db i n d i n g5 1 6 0 ，1 7 4 ，2 3 0 ，4 3 7 ，5 9 9 m e t a li o nb i n d i n g2 2 f e - 1 6 0 ，2 6 1 ，3 1 8 ，3 6 2 ，3 8 7 ，4 0 3 ， 4 0 5 ，4 6 6 ，5 9 9 z n - 1 8 7 ，2 9 6 ，3 8 3 ，5 6 8 ，5 7 8 ，5 9 3 c a ：3 4 4 ，3 9 1 分 m n ：1 8 5 子 m g 5 3 1 功 能 n i ：5 4 1 c a ：5 7 2 k ：5 5 9 d n ab i n d i n g1 5 18 7 ，2 2 4 ，2 5 9 ，2 8 4 ，2 9 6 ，3 3 0 ，3 5 0 ， 3 8 3 ，3 8 5 ，3 8 6 ，4 2 6 ，4 9 0 ，5 0 0 ，5 5 6 ， 5 9 3 o x i d a t i o nr e d u c t i o n7 1 6 0 ，2 0 2 ，2 6 l ，3 1 8 ，4 0 5 ，4 4 7 ，5 7 2 n a d po rn a d p h b i n d i n g 3 4 3 7 ，5 4 5 ，5 9 0 t r a n s f e r a s ea c t i v i t y6 2 2 8 ，3 4 2 ，3 7 l ，3 8 3 ，4 2 1 ，4 5 5 空问环境生物信息学数据的分析方法研究 r e s p o n s et os t r e s s 5 1 5 6 ，2 9 6 ，3 1 8 ，3 5 3 ，5 2 0 p r o t e i nf o l d i n g2 1 5 6 ，4 4 4 t r a n s p o a 1 5 1 5 6 ，1 6 l ，2 5 3 ，3 2 3 ，3 5 1 ，3 6 2 ，4 0 8 ， 4 3 7 ，4 4 9 ，4 6 2 ，4 7 l ，5 2 9 ，5 5 9 ，5 9 3 ， 5 9 8 t r a n s c r i p t i o n 1 0 1 6 2 ，2 0 l ，2 2 4 ，2 3 0 ，3 2 0 ，3 8 5 ，3 8 6 ， 生 5 5 6 ，5 8 5 ，5 8 8 物 过 a p o p t o s i s 6 2 1 0 ，2 2 2 ，3 7 7 ，4 5 6 ，4 8 0 ，5 9 5 程 t r a n s l a t i o n4 2 7 7 ，3 4 8 ，5 9 7 ，3 l l c e l lw a l lc o n s t r u c t i o n3 4 0 6 ，4 2 0 ，5 8 0 b i o s y n t h e t i cp r o c e s s 9 4 0 7 ，3 7 3 ，4 1 7 ，4 2 l ，4 3 8 ，5 5 l ，5 4 8 ， 5 4 5 ，5 9 4 c a r b o h y d r a t em e t a b o l i cp r o c e s s 5 4 6 1 ，5 0 7 ，5 2 4 ，5 4 8 ，5 5 8 从表格中我们可以看出，类别4 包禽的对象最多，并且相应的牛物功能和乍物过程 也是最多的，其中生物功能包括了：a t p 结合( a t pb i n d i n g ) 、r n a 、d n a 结合( r n a 、 d n a b i n d i n g ) 、f a d 结合( f a db i n d i n g ) 、金属离子结合( m e t a li o nb i n d i n g ) 、氧化活。件降 f k 乇( o x i d a t i o nr e d u c t i o n ) 、n a d p 或者n a d p h 结合( n a d po rn a d p hb i n d i n g ) 、转移酶活 性变化( t r a n s f e r a s ea c t i v i t y ) ；生物过程包括：压力h i 句j 粒过程( r e s p o n s et os t r e s s ) 、蛋一质折 叠过程( p r o t e i nf o l d i n g ) 、运输过程( t r a n s p o r t ) 、转录过程( t r a n s c r i p t i o n ) 、翻译过程 ( t r a n s l a t i o n ) 、细胞捌亡过程( a p o p t o s i s ) 、细胞壁构建过程( c e l lw a l lc o n s t r u c t i o n ) 、生物合 成过程( b i o s y n t h e t i cp r o c e s s ) 、糖代谢过程( c a r b o h y d r a t em e t a b o l i cp r o c e s s ) 。 我们以1 5 6 号蛋白质点为例，该蛋门质点在分子功能卜起a t pb i n d i n g 作用，在卜 物过程中参与r e s p o n s et os t r e s s ，p r o t e i nf o l d i n g ，t r a n s p o r t 过程。而在分子功能中，自3 个蛋白质点起n a d po rn a d p hb i n d i n g 作用。因此我们得m 以下结论：一个蛋白质点 可能参与多个生物过程或分子功能，而一个牛物过程或分子功能- 叮有多个蛋白质点功能 参与。 我们之所以对蛋白质点的信息进行聚类是基于以下假设：一个蛋白质点属f 且只属 于一个功能类，同类中的蛋白质功能密切相关且相似。但是从生物学的研究结果来看， 第3 章基丁投票机制的动态聚粪融台算法及其应用 蛋门质可能参与多个生物通路行使不同的功能，即蛋白质的功能具有多重性。因此近年 来适用蟹向质功能多重性的双向聚类、三项聚类的研究受到广泛关注。 我们再次对类别4 进行聚类，得到的结果如图3 9 ： * t t 目* 髓q d日月# t 自 l 蜘b t 口# i 睁e t 目* t t 口轴黼飘5 蛹鼎j 自自k # e = 诘性t 幽39 类别4 基丁投票机制的动态聚类融台算法的聚类结果 f i g 3 9r e s u l t s b y d y n a m i c c l o y t e r i n g e n s e m b l e s a l g o r i t h m b a s e do r v o t i n g m e c h a n i s m 伽c l o s t r 4 各个聚类簇的详细内容见表3 5 。 袭35 各个旗的详细内容 t a b 3 5 t h e d c 垃ij s o f e v e 4 ，d u s t e r 类别1 类别2 类别3l 卯。1 6 1 1 6 2 类别4 1 6 3 巧6 6 类别5 5 6 7 - - 6 0 6 嘉蟪0鼍篓翼翼萋篓蠢” 空间环境乍物信息学数据的分析方法研究 从表格中我们可以看出，细化的聚类结果成功的将功能为d n ab i n d i n g ，t r a n s f e r a s e a c t i v i t y ，c e l lw a l lc o n s t r u c t i o n ，b i o s y n t h e t i cp r o c e s s 聚为一类。 因此，假设我们有批蛋白质点的信息，可以通过聚类推测蛋白质点町能具有的多个 生物功能，给出预测的范闸，帮助生物工作者对实验进行设计，进一步探求蛋白质 兑行 使的具体功能。 第4 章改进的犬联规则挖掘算法及其应用 第4 章改进的关联规则挖掘算法及其应用 4 1 经典的a p rio ri 算法 a p r i o r i 算法是r a g r a w a l 和r s r i k a n t 于1 9 9 4 年提出的为布尔关联规则挖掘频繁项 集的原创性算法【5 6 。5 7 】。它使用一种称作逐层搜索的迭代方法，k 项集用于探索( k + 1 ) 项集。 首先，通过扫描数据库，积累每个项的计数，并收集满足最小支持度的项，找出频繁1 项集的集合l l 。然后，l i 用于找到l 2 ，如此下去直到不能再找到频繁项集l k 。 4 1 1 a p rio ri 算法描述 a p r i o r i 算法的具体描述如下： 输入：事务数据库d ：最小支持度阂值值m i n s u p 。 输出：d 巾的频繁项集l 。 过寿星： c i = c a n d i d a t el i t e m s e t s ) 厶= c c ic c o u n t m i ns u p f o r ( k = 2 ；厶一l o ；k + + ) 如b e g i n g = a p r i o r i g e n ( 厶一1 ) 产生新的候选集 厂o ra l lt r a n s a c t i o n sf dd ob e g i n c f = s u b s e t ( g ，f ) 事务t 中包含候选集的集合 加ra l lc a n d i d a t e sc c td o c c o u n t + + ： e n d 厶= c gc c o u n l m i ns u p e n d a n s w e r = u l k 其中a p r i o r i - g e n 函数用来产生候选肛项集。为提高频繁项集逐层产生的效率，该 函数运用a p r io fi 性质压缩产生频繁项集的搜索空间。 a p r i o r i 性质：频繁项集的所有非空子集都必须也是频繁的。如果项集i 不满足最小 空间环境生物信息学数据的分析方法研究 支持度阈值m i n _ s u p ，则i 不是频繁的。凶此，a p r i o r i g e n 函数有两个子步骤：连接步和 剪枝步。 连接步：为了生成厶，通过厶一。自己连接产生候选舡项集的集合。设，l 、1 2 是厶一中 的项集，记号“ 表示t 中的第j 项。执行连接厶一。厶一。，其中厶一。的元素是可连接的， 如果满足( 【1 】= 1 2 1 1 a 1 1 1 2 】_ 1 2 1 2 】a 人f l 【七一2 】_ 1 2 k 一2 】人【尼- 1 】 1 2 k 一1 】) 即他们的 ，j ( k 一2 ) 个项是相同的。连接，l 、，：产生的结果项集是，。 1 1 ，1 1 1 2 1 ，厶【七一l 】，： 忌一1 1 。 剪枝步：因为候选项集并小是所有的项集都是频繁的，因此为了址缩搜索空f b j ，可 以利用a p r i o r i 性质，即如果候选k 项集的( k 1 ) 项子集不在“一，中，则该候选也不可能足 频繁的，从而可以从乙k 中删除。 4 1 2a p rio ri 算法几种改进 为提高a p r i o r i 的效率，目f j 许多专家学者已经提出了一些基+ y - a p r i o r i 算法的改进 算法【5 8 1 ： ( 1 ) 基于散列的技术【5 9 6 0 】：用于压缩候选k 一项集o 。 ( 2 ) 事务压缩【6 1 】：不包含任何频繁k 项集的事务不町能包含任何( k + 1 ) 项集。【大j 此这 种事务可以加上标记或删除，数据库再次扫描的时候小需要它们。 ( 3 ) 基于划分的方法【6 2 】：算法将d 中的事务分为n 部分，找m 局部于每一部分的频 繁项集，结合局部频繁项集形成候选项集，在候选项集中找到全局频繁项集，最终确定 d 中的频繁项集。 ( 4 ) 抽样：选取给定数据库d 的随机样本s ，然后在s 中搜索频繁项集。用这种 方法牺牲了一些精度换取了有效性，使得s 町以在内存中搜索频繁项集，但是可能丢失 一些全局的频繁项集。 ( 5 ) 动态项集计数【6 4 】：动态项集计数技术将数据库划分为标i d j p 始点的块。该技术动 态地评估已被计数的所有项集的支持度，如果一个项集的所有子集已确定为频繁的，则 添加它作为新的候选。 第4 章改进的关联规则挖掘算法及其应用 4 2 其它关联规则挖掘算法 生物信息学的数据普遍存在着维数过大、数据量巨大等特点，因此我们要从数据特 点入手，折中时问、空间等因素，采用具有适应高维性、可伸缩性，即可处理高维数据、 可处理大规模数据量的关联分析算法。本文介绍了其他的一些关联分析算法，便于后期 对水稻生物信息学数据进行多粒度、多层次的关联分析。 许多频繁模式、最大频繁模式与频繁闭合模挖掘算法相继被提出，随着数据集规模 的增加，特别是海黾数据集的出现，对挖掘算法的性能提出了更高要求。频繁模式树 ( f p t r e e ) 是近螳年提出的一个很有影响的自仃缀树结构，它可以高度压缩存储数据集的频 繁项目信息，皋_ j ：该树设计的频繁模式挖掘算法具有较高的性能和较少的i o 开销【6 5 】。 基于f p t r e e 的频繁模式增长( f p g r o h ) 算法南h a n 等人于2 0 0 0 年提出【6 6 】。该算法 的思想完全不同于a p r i o r i ，它不需要产生选项，而是采取分而治之的思想。f p - g r o w t h 算法将提供频繁项的数据库压缩到棵频繁模式树( f r e q u e n t - p a t t e mt r e e ，简称f p t r e e ) ， 但仍保留项集关联信息。然后将压缩后的数据库划分成一组条件数据库，每个关联一个 频繁项或“模式段”，并分别挖掘侮个条件数据库。 一个数据集的频繁模式树是出各事务中的频繁项目序列构成的一棵前缀树，f p t r e e 满足如下条件： 1 f p t r e e 由一个标号为n u l l 的根节点和多个树节点构成，每个节点可带有1 1 个树 节点( n = o ，l ，2 ，3 ) 当n = o 时，该节点称为叶节点，除根节点以外，每个节点 由四个域构成：节点名称( n o d e n a m e ) ，节点记数( n o d e c o u n t ) ，节点链( n o d e l i n k ) 及父节点