（计算机应用技术专业论文）基因表达数据的若干挖掘方法研究.pdf

唐小丽：基因表达数据若干挖掘方法的研究 摘要 微阵列技术是近年来分子生物学实验技术的一个突破，利用该技术可以对成 千上万个基因的表达进行平行分析。这些基因表达数据通常构成一个数据矩阵， 对这些矩阵进行分析和挖掘，才能得到潜在的生物学过程信息。基因表达数据的 挖掘是生物信息学的研究热点和难点。 在对基因表达数据分析中，双向聚类与频繁模式的挖掘是非常重要的操作。 通过双向聚类技术，对基因进行聚类。在同一簇中的基因都具有类似的特征，根 据己知的功能基因，能得出同聚类中其他基因的功能。同时，基因表达数据的关 联规则分析还可以发现若干个基因在多个样本之间的强弱关联关系。挖掘基因表 达的频繁模式能找出它们之间的关联关系。 由于基因表达数据的数据量多，计算量大的特点，对数据的处理要求较高。 本文主要对如下几个方面的问题进行了深入研究，提出了相应的解决算法。实验 表明这些方法简明有效。 首先，提出了解决确定性双向聚类问题的a c ab i c l u s t e r i n g 算法。将蚁群算法 a c a 运用到双向聚类问题中，给定参数k ，找到k 个满足阈值的聚类。将行与 m 列编码成一个长度为+ m 的字符串。字符串表示出了基因表达数据矩阵中包含 的聚类，聚类所在的行或列编码成1 ，否则0 ，每个字符表示一个节点。某一节点 上聚集的信息素越多，则该节点被选择的概率就越大。首先，列出了初始的k 个 字符串。根据添加移除此节点是否能最好提高聚类的质量为标准，从第一列的置 个节点中选择出某个节点，直至最后一列十肘。这样，每只蚂蚁的结果对应了对 k 个初始聚类质量的改进。比较所有蚂蚁的执行结果，保留最优解。再进行下一轮 的选择，直到解的质量不再提高为止。与其他类似的算法相比，本算法不仅能够 得到精确的结果，而且在速度和效率上也有了很大的提高。 其次，为了解决不确定性双向聚类问题，提出了基于合并的确定性双向聚类 算法m d b c 算法。基因表达数据的行数远远大于列数，我们的算法仅对每两列聚 类。应用剪枝策略对得到的这些聚类进行筛选。再建立索引树，根据此类聚类的 反单调性，采用合并的方法对这些包含列数最少的小聚类进行合并，得出所有满 足阈值的聚类。对增量数据问题，无需对所有数据重新聚类。仍采用合并的方法， 1 1扬州大学硕士学位论文 只需聚类增量数据，再和已有聚类进行合并，这样能快速得出数据增加下的所有 聚类。 最后，对基因表达数据的频繁闭合模式的挖掘问题进行了深入的研究，提出 了高维数据频繁闭合模式挖掘算法e m h c p 。将事务集的概念应用到基因表达数据 中，不同的实验条件对应了不同事件集。针对基因表达数据维度高的特点，首先 建立位图转化表，快速得到在两个事务中出现的项目集，根据这些项目集，建立 行集项目集混合树。在构建混合树的同时，采用剪枝策略，来缩小搜索空间。再 对混合搜索树，采用深度优先的方法挖掘出所有的频繁闭合模式。 关键字：基因表达数据，数据挖掘，双向聚类，关联规则，频繁模式挖掘，蚁群 算法 唐小丽：基因表达数据若干挖掘方法的研究i i i a b s t r a c t m i e r o a r r a y sa r eo n eo f t h el a t e s tb r e a k t h r o u g h si ne x p e r i m e n t a lm o l e c u l a rb i o l o g y , w h i c ha l l o wm o n i t o r i n go fg e n ee x p r e s s i o nf o rt e n so ft h o u s a n d so fg e n e si np a r a l l e l t h e g e n ee x p r e s s i o nd a t aa r eo r g a n i z e da sm a t r i c e s t h e s em a t r i c e sh a v et ob ea n a l y z e d f u r t h e r , i fa n yk n o w l e d g ea b o u tt h eu n d e r l y i n gb i o l o g i c a lp r o c e s s e si st ob ee x t r a c t e d t h eg e n ee x p r e s s i o nd a t am i n i n gi sah o ta n dd i f f i c u l tt o p i ci nb i o i n f o r m a t i c s i nt h eg e n ee x p r e s s i o nd a t aa n a l y s i s ，b i c l u s t e r i n ga n dm i n i n gf r e q u e n tp a t t e r n sa r e i m p o r t a n to p e r a t i o n s b yb i c l u s t e r i n g ，g e n e sa r eg r o u p e di n t od i f f e r e n tc l u s t e r s t h e g e n e si nt h es a m ec l u s t e rh a v et h es a m ef e a t u r e a c c o r d i n gt ot h ek n o w nf u n c t i o ng e n e s ， f u n c t i o no fo t h e rg e n e si nt h es a n l ec l u s t e ri sc o n c l u d e d b yt h ea n a l y s i so fa s s o c i a t i o n r u l e si ng e n ee x p r e s s i o nd a t a , t h es t r o n go rp o o rr e l a t i o n so fg e n e si ns e v e r a ls a m p l e s a r ef o u n d t h er e l a t i o n sa m o n gt h e mc a nb eg o a e nb ym i n i n gt h e i rf r e q u e n tp a t t e r n s a sg e n ee x p r e s s i o nd a t aa n a l y s i sc o n s u m e sh u g ea m o u n to fc o m p u t a t i o nt i m ea n d m e m o r ys p a c e ，h i g hp e r f o r m a n c ec o m p u t e ri sr e q u i r e d i nt h i sp a p e r , w er e s e a r c ho nt h e f o l l o w i n gi s s u e sd e e p l ya n dp r o p o s es o m er e l a t i v er e s o l v i n ga l g o r i t h m s t h e s em e t h o d s a r ep r o v e dc o n c i s ea n de f f i c i e n t f i r s t ，t h ea l g o r i t h ma c a _ b i c l u s t e r i n gi sp r e s e n t e dt o s o l v e t h ed e t e r m i n a t e b i c l u s t e r i n gp r o b l e m t h ea n tc o l o n ya l g o r i t h m ( a c a li sa p p l i e dt ot h eb i c l u s t e r i n g p r o b l e m g i v e nt h ep a r a m e t e r 尼kb i c l u s t e r sw h i c hm e e tt h et h r e s h o l dv a l u ea r e a t t a i n e d t h enr o w sa n dmc o l u m n si nt h em a t r i xa r ec o d e da sas t r i n g ，t h el e n g t ho f w h i c hi sn 七m t h es t r i n gd e n o t e st h eb i c l u s t e rw h i c hi se m b e d d e di nt h ee x p r e s s i o n d a t a t h er o wo rc o l u m nw h i c hi si nt h eb i e l u s t e ri sc o d e da s1 ，o re l s e0 e v e r y c h a r a c t e ro ft h es t r i n gc o r r e s p o n d st oan o d e t h em o r ei n t e n s i t yo ft h ep h e r o m o n eo n t h en o d ei s ，t h em o r ep r o b a b i l i t yt ob es e l e c t e di th a s f i r s t ，ki n i t i a ls t r i n g sa r el i s t e d a c c o r d i n g t ot h es t a n d a r dw h e t h e rt h eb i c l u s t e rq u a l i t yc a nb ei m p r o v e db ya d d i n go r r e m o v i n gan o d e ，w ec h o o s et h en o d ef r o mt h ek n o d e si nt h ef i r s tc o l u n m ，u n t i lt h el a s t c o l u m nn + m s oe v e r ya n t ss o l u t i o nc o r r e s p o n d st ot h ei m p r o v e dkb i c l u s t e r s c o m p a r i n gt h er e s u l t so f a l la n t s ，w ek e e pt h eb e s tr e s u l t t h e nt h es e l e c t i o ni t e r a t i o n i v 扬州大学硕士学位论文 c o n t i n u e su n t i lt h er e s u l ti sn ol o n g e ri m p r o v e d c o m p a r e dw i t ht h es i m i l a ra l g o r i t h m o u ra l g o r i t h mc a no b t a i nm o r ea c c u r a t er e s u l ta n dh a sh i g h e rc o m p u t a t i o n a ls p e e da n d e f f i c i e n c y s e c o n d ，w ep r o p o s eam e r g e dd e t e r m i n a t eb i c l u s t e r i n ga l g o r i t h m ( m d b c ) t os o l v e t h eu n d e t e r m i n a t eb i c l u s t e r i n gp r o b l e m i nt h eg e n ee x p r e s s i o nd a t a ，t h en u m b e ro f r o w s i sf a rm o r et h a nt h a to fc o l u m n s ，w eo n l yb i c l u s t e rt h ee v e r yt w oc o l u m n s t h ep r u n e s t r a t e g yi su s e dt or e m o v eu s e l e s sb i c l u s t e r s t h e n a ni n d e xt r e ei sc o n s t r u c t e d a c c o r d i n gt ot h ea n t i - m o n o t o n i c i t yo ft h i sk i n do fb i c l u s t e r s b a s e do nt h em e r g e d m e t h o d ，w eg e tt h eb i c l u s t e r sw h i c hm e e tt h et h r e s h o l dv a l u ef r o mt h es m a l lb i c l u s t e r s t h a ti n c l u d et h el e a s tc o l u m n s t ot h ei n c r e m e n td a t a ，i ti sn on e e dt ob i c l u s t e r i n ga l lt h e d a t a t h em e r g e dm e t h o di ss t i l lu s e d t h r o u g ht h ew a y , o n l yt h ei n c r e m e n td a t aa r c b i c l u s t e r e d ，t h e nt h ee x i s t i n gb i c l u s t e r sa r ec o m b i n e d ，t h u sa l lt h eb i c l u s t e r si nt h e i n c r e m e n t a ld a t ac a r tb eo b t a i n e df a s t e rt h a nb e f o r e f u r t h e r m o r e ，w ed e e p l ys t u d yt h ep r o b l e mo fm i n i n gf r e q u e n tc l o s e dp a r e m si n t h eg e n ee x p r e s s i o nd a t aa n dp r e s e n tt h ea l g o r i t m - - - - - e f f i c i e n tm i n i n gf r e q u e n tc l o s e d p a a e m sf r o mh i g hd i m e n s i o n a ld a t a ( e m h c p ) t h e t r a n s a c t i o ns e tn o t i o ni sa p p l i e dt o t h eg e n ee x p r e s s i o nd a t a ，a n dt h ed i f f e r e n te x p e r i m e n t sc o r r e s p o n dt ot r a n s a c t i o ns e t a i m i n ga tt h eh i g hd i m e s i o ni nt h ee x p r e s s i o nd a t a , ab i tm a p t a b l ei sc o n s t r u c t e dt og e t t h ei t e m s e t se x i s t i n gi nt h et w ot r a n s a c t i o n sf a s t w i t ht h ei t e m s e t s ，ac o m p o u n dt r e eo f m w s e ta n di t e m s e ti sc o n s t r u c t e d w h i l ec o n s t r u c t i n gi t ，e f f i c i e n tp r u n i n gs t r a t e g yi s u s e dt or e d u c et h es e a r c hs p a c ea n da c c e l e r a t et h em i n i n gs p e e d t h e nb ys e a r c h i n gt h e t r e ei nt h ed e p t hf i r s to r d e r , a 1 1f r e q u e n tc l o s e dp a t t e r n sc a nb em i n e d k e y w o r d s ：g e n ee x p r e s s i o nd a t a , d a t am i n i n g ，b i c l u s t e r i n g ，a s s o c i a t i o nr u l e ，f r e q u e n t p a t t e r n ，a n tc o l o n ya l g o r i t h m 唐小丽：基因表达数据若干挖掘方法的研究 第一章引言 生物信息学和基因芯片是生命科学研究领域中的两种新方法和新技术，生物 信息学与基因芯片密切相关，生物信息学促进了基因芯片的研究与应用，而基因 芯片则丰富了生物信息学的研究内容。基因表达数据分析有助于阐明基因的表达 调控路径和调控网络。目前，对基因表达数据的分析是一个数据挖掘问题，常采 用分类法、统计法、聚类分析、关联规则分析等。 1 1 生物信息学 生物信息学( b i o i n f o r m a t i e s ) 是由生物学、应用数学、计算机科学相互交叉 所形成的学科【l , 2 1 ，是当今生命科学和自然科学的重大前沿领域之一，也是2 1 世纪 自然科学的核心领域之一。它是指应用信息科学的理论、方法和技术，管理、分 析和利用生物分子数据。通过收集、组织、管理生物分子数据，使研究人员能够 迅速地获得和方便地使用相关信息：通过处理、分析、挖掘生物分子数据，得到 深层次的生物学知识，加深对生物世界的认识；在生物学、医学的研究和应用中， 利用生物分子数据及其分析结果，可以大大提高研究和开发的科学性及效率。如 根据基因功能分析结果来检测与疾病相关的基因，根据蛋白质分析结果进行新药 设计。目前生物信息学的主要任务是研究生物分子数据的获取、存贮和查询，发 展数据分析方法 3 , 4 1 。主要包括三个方面；第一是收集和管理生物分子数据，使得 生物学研究人员能够方便地使用这些数据，并为信息分析和数据挖掘打下基础。 第二是进行数据处理和分析。通过数据分析，发现数据之问的关系，认识数据的 本质，进而上升为生物学知识。并在此基础上，解释与生物分子信息复制、传递 和表达有关的生物过程，解释在生物过程中出现的信息变化与疾病的关系，帮助 发现新的药物作用目标，设计新的药物分子，为进一步的研究和应用打下基础。 第三个方面是开发分析工具和实用软件，解决具体的问题，为具体的生物信息学 应用服务，例如，开发生物分子序列比较工具、基因识别工具，生物分子结构预 测工具、基因表达数据分析工具等。 2 扬州大学硕士学位论文 1 2 基因表达数据 1 2 1 基因芯片 基因芯片( g e n ec h i p ) i s , 6 ，又称d n a 微阵列( m i c r o a r r a y ) ，是由大量e d n a 或寡核苷酸探针密集排列所形成的探针阵列。1 9 9 5 年由斯坦福大学率先研制成功 并应用于基因表达分析中【7 j ，首先将细胞内的m r n a 逆转录成e d n a 并分离，然后 将分离得到的所有或部分e d n a ( 其长度通常大于2 0 0 b p ) 作为探针，用机器手按 照阵列的形式点到玻璃片上。玻璃片上的每一个点只包含一种e d n a 分子，这样就 制成了c d n a 微阵列。固定在玻片上的e d n a 探针可以通过测序得到序列。在使用 e d n a 微阵列时，首先提取组织或细胞系中的m r n a 样本，逆转录成e d n a 并用荧 光索标记；然后把标记混合物加到c d n a 微阵列上，与探针杂交，杂交过程完成后， 清洗微阵列；最后用激光扫描仪扫描并获取荧光图像，对图像进行分析，得到e d n a 芯片上每一个点的荧光强度值。荧光强度值定量反映了样本中存在的与探针互补 的m r n a 丰度，也就是反映了探针所对应基因的表达水平。基因芯片技术可以大规 模并行获取基因转录结果m r n a 的数据。 d n a 序列包含着最基本的生命信息，生命的信息存贮在a 、t 、c 、g 这4 个字 符所组成的d n a 序列中。而基因芯片则是一种提取生物分子信息的有力工具，通 过基因芯片可以大规模、并行提取d n a 或r n a 信息。基因芯片能够在同一时间内 分析大量的基因，实现生物基因信息的大规模检测。基因芯片是分子生物学和微 电子学及信息学相互结合所形成的新型技术，其核心在于大规模并行提取d n a 或 m 她信息。基因芯片为进行d n a 序列分析和基因表达分析提供了一种强有力的工 具。它的应用主要分成两大类，一是应用于研究型基因。一是用于监控r n a 表达。 从本质上来讲，前者实际上是利用基因芯片进行序列分析，其中包括识别d n a ) 芋 列的突变和研究d n a 的多态性；而后者则是利用基因芯片研究序列的功能，这也 是我们本文中研究的方面。 唐小丽：基因表达数据若干挖掘方法的研究3 1 2 。2 基因表达数据的表示 基因表达数据用n x , n 矩阵爿c l ) | l 。表示：c = q 3 ： q 3 ，包 含厅个基因对象，埘个样本，其中每个元素勺表示第i 个基因在第，个条件下的表 达水平值，行向量而= 向 弛，列代表基因i 在脚个条件下的表达水平，称为基因 i 的表达谱，列向量号= b 驴孙，粕) 1 代表某一条件下的各基因的表达水平。 1 2 3 基因表达数据对生物信息学的意义 由于生物体中的细胞种类繁多，同时基因表达具有时空特异性，因此，基因 表达数据与基因组数据相比，要更为复杂，数据量更大，数据的增长速度更快。 基因表达数据中蕴含着基因活动的信息，可以反映细胞当前的生理状态，例如细 胞是处于正常还是恶化状态、药物对肿瘤细胞是否有效等【引。对基因表达数据的分 析可以获取基因功能和基因表达调控信息【9 】，这是生物信息学的重大挑战之一，也 是d n a 微阵列能够在生物医学领域中广泛应用的关键原因之一。 6 1 1 6 y h r 0 0 7 c y o l l 0 9 w r a l 力5 6 w y l 0 5 8 w y a l 9 w y a l o o o w y a “) 6 l w y a l 0 6 2 w y a r 锄口w 帕l o 5t 2 侈 1 7 巾，2 7 5 5 0 5 7 9 5 彤6 j 4 6 5 4 1 8 6 1 4 4 4 6 8 0 2 4 6 - 0 0 8 鹞5 8 3 9o ，6 4 5 2 5 2 0 3 4 o 3 6 3 1 2 9 lo 2 1 7 5 3 1 3 4 3 - 0 6 7 0 6 0 4 8 4 5 - 0 麒1 1 9 5 2 3 2 一1 2 4 6 1 4 3 7 4 3 o 0 9 1 7 2 3 o f 2 伽哪4 1 9n 1 2 4 1 7 9 4 1 o 3 5 7 3 0 9 3 l l - o o 供嘲瞄0 神 i 配8 2 8 8 0 2 7 8 7 1 6 0 2 80 肺7 9 3 3 6 7 6 一o 0 2 4 9 4 0 1 0 70 4 4 8 3 8 1 2 胡 o j 5 3 5 5 7 0 4 71 6 0 6 2 3 7 6 5 2o ，5 l o 1 9 1 90 。6 8 6 9 2 4 9 1 2 0 。1 9 3 5 4 3 7 3 s m 2 5 1 5 0 4 7 4 l0 6 4 1 9 3 4 3 6 50 7 5 6 4 1 0 3 5 71 4 1 3 2 9 0 6 鹞1 s 3 3 酗t s 6 6 由2 8 1 8 5 1 6 6 2 - 0 1 9 8 2 6 2 6 1 9m 3 8 2 2 3 2 8 2 90 7 7 9 1 6 5 0 6- o 2 6 5 4 9 0 6 5 5 矗3 3 3 4 4 9 7 钨- 2 a 2 4 8 2 5 2 5 2 - 3 瑚7 2 勰9 2 4 1 4 2 5 5 7 4 驼4 以4 2 2 7 7 3 3 3 6 0 0 2 6 8 1 6 6 6 5o 3 5 1 9 5 4 6 6 2o 2 8 3 6 醒1 0 2o 4 5 4 4 9 4 3 8 30 3 3 3 4 4 7 6 7 9 图1 - 1 酵母菌基因表达数据片断 细彬；跏 ， 4 扬州大学硕士学位论文 目前，基因表达数据主要为数值型并以矩阵的方式存储，行为一个样本在不 同环境条件下或不同时间点的表达，列是同一环境或时间下所有样本的表达情况。 矩阵元素以，是第f 个基因在实验条件，下的相对表达值，通常需要对得到的原始 实验数据进行对数变换，经过交换后，上调的基因具有正值，而下调的为负值。 基因表达数据通常都是多维的。图1 1 是酵母基因表达微阵列数据的部分片断，该 数据是在五个不同时间点测量得到的值。 通过对该数据矩阵的分析，可以回答一些生物学问题，例如，基因的功能是 什么? 在不同条件或不同细胞类型中，哪些基因的表达存在差异? 在特定的条件 下，哪些基因的表达发生了显著改变，这些基因受到哪些基因的调节，或者控制 哪些基因的表达? 哪些基因的表达是细胞状态特异性的? 根据它们的行为可以判 断细胞的状态( 生存，增殖、分化、凋亡、癌变或应激等) 等。对这些问题的回 答，结合其它生物学知识和数据有助于阐明基因的表达调控路径和调控网络。揭 示基因调控路径和网络是生物学和生物信息学共同关注的目标，是系统生物学 ( s y s t e m sb i o l o g y ) 研究的核心内容。 生物信息学研究的内容开始进步到基因和基因组的功能分析，即转向功能 基因组学( f u n a i o n a lg 胁咖i c s ) 研究【1 0 , 1 1 , 1 2 。生物信息学在基因组学研究中的重点 是基因组序列。在功能基因组中研究中的重点则是序列的生物学意义。其主要内 容有：( 1 ) 进一步识别基因，识别基因转录调控信息，分析遗传语言：( 2 ) 进行基因 组功能注释，注释所有基因和基因产物的功能，认识基因与疾病的关系；( 3 ) 研究 基因的表达调控机制，研究基因在生物体代谢途径中的地位，分析基因、基因产 物之间的相互作用关系；( 4 ) 比较基因组学研究，在基因组水平对各个生物进行对 照比较，揭示生命的起源和进化，发现蛋自质功能。 1 3 基因表达数据挖掘 基因表达数据库在不断发展，需要用先进的分析工具，从大量的数据中提取 隐含的信息。数据挖掘技术( d a t am i n i n g ) 是一种薪近的数据分析和知识发现技术， 目前被应用到生物信息学领域并取得了相当大的成功f 1 3 q 6 | 。生物信息学自诞生以 来，经历了3 个阶段：( 1 ) 基因年代的生物信息学，主要是序列分析、数据库的查 询、计算机操作和p c 的应用：( 2 ) 基因组年代的生物信息学，主要是基因的寻找、 数据与数据之间的比较、网络相互界面；( 3 ) 后基因组年代的生物信息学，主要是 数据的挖掘、表达、数据多样性的分析、相互交叉数据分布的总结与分析。其研 唐小丽：基因表达数据若干挖掘方法的研究5 究的内容不仅包括基因的查寻和同源性分析，另外包括了基因和基因组的功能分 析，即所谓的功能基因组研究。 后基因组时期的主要任务为数据挖掘，即从完全测序的基因组中预测功能 1 7 , 1 5 。功能基因组研究的具体内容表现在：( 1 ) 将已知基因的序列与功能联系在一 起研究；( 2 ) 从以常规克隆为基础的基因分离转向以序列分析和功能分析为基础的 基因分离；( 3 ) 从单个基因致病机理的研究转向多个基因发病机理的研究：( 4 ) 从组 织与组织之间的比较来研究功能基因组和蛋白组。其目的就是为了能够对整个基 因组进行分析和比较，对多元基因及相应蛋白间的功能和作用进行整体分析。如 何有效地进行数据的采集、收集、整理、检索、分析，从中提取规律，上升为理 论，以便“读懂”基因组的遗传信息。 在基因表达数据分析方面，主要进行表达数据的聚类分析【1 9 捌、分类分析【2 n 、 基因相关性研究 趋捌、基因调控网络分析删。 1 4 论文的主要工作 本文首先介绍了基因表达数据挖掘技术以及相关的算法和应用。然后对现有 的算法作了具体的介绍，指出了其存在的不足，并进行了深入研究，从而提出了 几种解决方法，取得了很好的效果。首先，对基因表达数据分析中的双向聚类 ( b i c l u s t e r i n g ) 技术进行研究。双向聚类是对数据矩阵的行与列方向同时聚类，识别 出在条件子集下表达相似的基因，得到表达模式一致的子矩阵，从而可以得出哪 些基因在哪些条件下的功能是相同的。不同的实际情况要求得出不一样的分析结 果。有些情况下，需要求出固定个数的聚类，进行分析，或者将其中满足双聚类 条件韵聚类都找出来。因此，根据求出的聚类特点，我们分为确定的双向聚类和 不确定的双向聚类。确定的双向聚类方法是在给定常量下，找出这个数目的聚类。 不确定的双向聚类方法是按照给定的阙值，找到符合条件的所有聚类。最后针对 高维基因表达数据，提出一种高效挖掘频繁闭合模式算法。本论文主要从以下几 个方面开展工作： ( 1 ) 用蚁群算法解决确定性双向聚类问题，提出了a c a 算法。biclustering 蚁群算法具有很强的鲁棒性和搜索最优解的能力。对蚁群算法a c a ，在某一路径 上信息素越多，蚂蚁选择该路径的概率也越大。运用到双向聚类问题中，在某一 节点上聚集的信息素越多，则该节点被选择的概率就越大。将行与吖列编码成 一个长度为+ 肘的字符串。如果一个聚类中包含了源数据的行( 列) ，那么字符 6 扬州大学硕士学位论文 串编码中对应位置为1 ，否则为0 。这样这个字符串就表示出了源数据中包含的聚 类。初始聚类为& 个，列出足个字符串。根据添加移除此节点是否能最好提高聚 类的质量为标准，从第一列的k 个节点中选择出某个节点，直至最后一列n + m o 这样每只蚂蚁对应了对量个初始聚类质量的改进。比较所有蚂蚁的执行结果，保 留最优解。再进行下一轮的选择，直到解的质量不再提高为止。选用标准数据库， 实验证明了此方法在准确率上的优势。 ( 2 ) 用合并的方法解决非确定性双向聚类问题，提出了基于合并的确定性双 向聚类算法m d b c 。基因表达数据的行数远远大于列数，因此我们的算法仅对每 两列聚类。应用剪枝的方法对得到的这些聚类进行筛选。再建立索引树，根据此 类聚类的反单调性，从这些小的聚类( 包含列数最少) 开始，合并这些小聚类， 从而得出所有满足阐值的聚类。对增量的数据问题，无需对所有数据重新聚类。 仍用合并的方法，只需对增量数据聚类，再与原来数据的聚类合并，这样能快速 得出数据增加下的所有聚类。 ( 3 ) 针对基因表达数据维度高的特点，用传统的频繁模式挖掘的算法难以实 现高效得挖掘，因此在已有研究的基础上，提出了一种快速挖掘高维数据频繁闭 合模式算法e m h c p 。首先建立位图转化表，快速得到两行的频繁项目集，根据这 些频繁项目集，建立行集项目集混合搜索树。在构建的时候，采用剪枝策略，缩 小搜索空问。再对混合搜索树，采用深度优先的方法挖掘出所有的频繁闭合模式。 1 5 论文组织 论文以下章节的组织结构如下：第二章介绍了基因表达数据挖掘的基本概念 以及主要的挖掘任务和相应技术方法，发展现状及应用研究，及其优点和存在的 问题。第三章中讨论了基因表达数据的确定性双向聚类，并结合蚁群优化算法， 提出了一种不同的双向聚类算法。在接下来的第四章中，提出了基于合并的不确 定性双向聚类。在第五章中，挖掘基因表达数据的频繁模式，进而可以得出关联 规则。最后，在第六章中作了总结。并给出了本论文的主要研究成果及未来的研 究方向。 唐小丽：基因表达数据若干挖掘方法的研究7 第二章基因表达数据挖掘技术 数据挖掘技术是一种先进的数据分析和知识发现技术阴，2 5 l ，该技术已经在许 多领域取得了成功的应用。在生物信息学领域，该技术也己显示出其能量，已经 运用于生物数据模式提取和基因表达数据分析。 2 1 数据挖掘技术 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提 取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程。数据 挖掘是一种从大型数据库或数据仓库中提取隐藏的预测性信息的新技术。它能开 采出潜在的模式，找出最有价值的信息，指导商业行为或辅助科学研究。数据挖 掘是一门广义的交叉学科，它汇聚了不同领域的研究者尤其是数据库、人工智能、 数理统计、可视化、并行计算等方面的学者和工程技术人员。因此有必要了解数 据挖掘的技术、方法、过程和步骤，并探索其对生物信息数据挖掘的潜在应用或 应用领域。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数据 挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息 应具有先前未知、有效和可实用三个特征。先前未知的信息是指该信息是预先未 曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违 背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越有价值。 总体上讲，数据挖掘实质上是一种决策支持过程，其主要技术手段是统计方 法，包括数理统计方法、多元统计方法、计量经济学和时间序列分析方法等。此 外，运筹学、人工神经网络和专家系统技术的发展，也为数据挖掘提供了新的思 路。它的主要特点是能高度自动分析企业原有的数据，归纳推理，从中挖掘出潜 在的模式，预测客户的行为，帮助决策者作出正确的决策。 2 2 数据挖掘的对象及主要任务 挖掘的原始数据可以是结构化的，如关系数据库，数据仓库中的数据；也可 8 扬州大学硕士学位论文 以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。 原则上讲，数据挖掘可以在任何类型的信息存储上进行，这包括关系数据库、数 据仓库、事务数据库、w w w 、面向对象数据库、对象一关系数据库、时间序列数 据库、空间数据库、文本数据库、多媒体数据库等。 数据挖掘的任务是从数据中发现模式，涉及的学科领域和方法很多，有多种 分类法1 2 6 , 2 7 , 2 s 。根据挖掘任务分，可分为数据聚合、分类、聚类、关联规则挖掘、 序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等；根据挖掘对象 分，有关系数据库、面向对象数据库、空间数据库、文本数据库、多媒体数据库、 异质数据库、遗产数据库等：根据挖掘方法分，可分为机器学习方法、统计方法、 神经网络方法和数据库方法等。 我们主要从挖掘任务的角度，来分析研究对象。其中。数据聚合目的是对数 据进行浓缩，给出它的紧凑描述。聚合方法是计算出数据库的各个字段上的求和 值、平均值、方差等统计值，或者用直方图、饼状图等图形方式表示；聚类，把 一组个体按相似性归成若干类别，即“物以类聚”。下一节将详细介绍f 分类，其 应用的事例包括图象及模式的识别。医学诊断，出错检查，以及分析经济市场的 走向等等。目的是构造个分类函数或分类模型，该模型能把数据库中的数据项 映射到给定类别中的某一个。分类可用于预测，其目的是利用历史数据纪录，对 未来数据进行预测；关联规则挖掘的任务是寻找数据项之间的联系。 本文将主要基于基因表达数据，着重讨论聚类和关联规则发现这两种非常重 要的挖掘任务。 2 3 数据挖掘在基因表达数据分析中的应用 2 3 1 聚类分析 聚类分析是模式识别和数据挖掘中普遍使用的一种方法l 礁蚓，是基于数据的 知识发现的有效方法，特别适用于模式分类数不知道的情况。聚类分析是一种无 监督学习方法，不需要任何先验领域知识，它根据数学特征提取分类标准，对数 据进行分类，这种数学特征的例子有统计平均值、相关系数、协方差矩阵的本征 值及本征向量等。 聚类是把一组个体按相似性归成若干类别，即“物以类聚”。目的是使得属于 同一类别的个体之l 可的差距尽可能小，而不同类别上的个体问的距离尽可能大， 唐小丽：基因表达数据若干挖掘方法的研究9 通常采用数据对象属性值问的距离进行相似和不相似的度量。这是一种基于全局 比较的聚类，它需要考察所有的个体才能决定类的划分，因此它要求所有的数据 必须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算 复杂度，难以适用于数据库非常大的情况。和分类学习相比，分类学习的例子或 数据对象有类别标记，而聚类的例子则没有标记，需要由聚类学习算法来自动确 定。数据聚类的研究推动了统计学、机器学习、空间数据库技术、生物学以及市 场营销的发展。聚类模式( c l u s t e r i n gp a t t e r n ) 包括统计方法、机器学习方法、神经网 络方法和面向数据库的方法，比如，系统聚类法、分解法、加入法、动态聚类法、 有序样品聚类、有重叠聚类、模糊聚类法、运筹方法等。主要的聚类算法的类型 可分为基于划分方法、基于层次的方法、基于密度的方法、基于网格的方法、基 于模型的方法等。一个聚类算法通常包含了多种聚类方法的思想。在神经网络中， 有一类无监督学习方法：自组织神经网络方法，如k o h o n e n 自组织特征映射网络、 竞争学习网络等1 3 1 j 。在数据挖掘领域里，神经网络聚类方法主要是自组织特征映 射方法，m m 在其发布的数据挖掘白皮书中就特别提到了使用此方法进行数据库 聚类分割。 基因表达数据分析所采用的常用方法是聚类 3 2 , 3 3 ，其目的就是将基因分组。 聚类分析在基因表达数据分析中应用的很多，主要有层次聚类、k 均值、自组织 特征映射网络、遗传算法、粗糙集和模糊逻辑技术等。聚类分析通过各种不同的 数学模型，将表达规律相似的基因聚为一类，在此基础上，寻找相关基因并分析 基因的功能。如：( 1 ) 根据在所有条件下的表达值，对这些基因分组：( 2 ) 给定已划 分的基因类别，将一个新的基因归入相应类。( 3 ) 基于所有基因的表达值，给条件 分组。( 4 1 给定实验条件下所有基因的表达，将一个新的样本归入这个条件中。从 数学的角度，聚类得到的基因分组，一般是组内各成员在数学特征上彼此相似， 但与其它组中的成员不同。从生物学的角度，聚类分析方法所隐含的生物学意义 或基本假设是：组内基因的表达谱相似，它们可能有相似的功能。然而，产物有 相同功能的编码基因( 例如对其它蛋白质有磷酸化作用) ，不一定共享相似的转录 模式。相反。有不同功能的基因可能因为巧合或随机扰动而有相似的表达谱。尽 管有许多意外的情况存在，大量功能相关的基因的确在相关的一组条件下有非常 相似的表达谱，特别是被共同的转录因子共调控的基因，或者产物构成同一个蛋 白复合体，或者参与相同的调控路径。因此，在具体的应用中，可以根据对相似 表达谱的基因进行聚类，从而指派未知基因的功能。 1 0 扬州大学硕士学位论文 2 3 2 双向聚类 传统聚类方法是一种全局的思想，或者仅对所有行聚类，或者仅对所有列聚 类。它是建立在数据库中仅包含同一类或者特定的条件的基础上的。它不包括从 许多实验中得到的相异的条件。这种聚类方法，通常将整个基因划成不相交的类 别，每个基因仅关联到个类别，其过度简单化了生物系统。许多实验中得到的 成百个基因表达数据中，许多活动模式的一组基因在某些特定的实验条件中的表 达是一致的。但在别的条件下，这些基因的行为又是不一样的。因此聚类在基因 表达数据分析中存在很大的困难，需要个新的技术能够找到基因表达数据中的 局部模式。基因表达数据矩阵中的列表示了实验条件，可以是时间序列，也可以 是不同的肿瘤样本或病入样本。针对列的聚类可以发现各实验条件之问的相互关 系，例如，同一肿瘤类型的样本可以聚成一类，它们具有相似的基因表达模式， 这样就可以对肿瘤进行分类。从数学的角度，数据矩阵中的每一列对基因表达谱 的行聚类结果有着不同的影响，挑选部分列进行聚类的结果与选择所有列进行聚 类的结果是不同的。将行聚类方法和列聚类方法结合起来，就称为双向聚类法。 最早对双向聚类的表述是由h a r t i g a n 提出1 3 4 3 5 1 ，也称之为块聚类。通过双向聚类 技术，在行和列两个方向上进行聚类分析，通常采用贪婪迭代检索的方法来发现 子矩阵或稳定的类，这些子矩阵中感兴趣的模式具有特定的生物学意义，它是基 因行和属性列的子集合，这些集合中的基因表示出了和这些集合中属性的高度一 致性。在应用中，可以根据具体的目的，确定以降低基因维数还是以降低样本维 数为主，通过迭代得到稳定的若干样本分类和基因分组。双向聚类算法也已经也 被用于别的一些领域，如：信息修补和数据挖掘。 双向聚类( b i d u s t e r i n g ) 这个术语2 0 0 0 年首先由c h e n ga n dc h u r c h 用于基因 表达数据分析中【3 6 】。这个截然不同的划分算法，同时对基因的行和列聚类。这些 术语，如：同时聚类，高维聚类，子