（计算机科学与技术专业论文）微阵列基因表达数据双聚类的多目标进化计算技术研究.pdf

国防科学技术火学研究生院博十学位论文 摘要 微阵列技术能够同时测量数千个基因的表达水平值，产生大量的微阵列数据 集，导致需要研究更加有效的分析算法来挖掘其中的生物模式。双聚类是微阵列 数据分析中一个非常有用的数据挖掘技术，并且在许多应用中展现出其优势。在 基因表达矩阵的双聚类挖掘中，必须同时考虑优化几个相互冲突的目标，因而应 用多目标优化求解双聚类是一个非常出色的方法。 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 主要研究维持解形式的算法，偏 重于将来解的创建，进化算法包括一些通常的算法实例，如遗传算法、遗传规划、 进化策略、差分进化、模拟退火、粒子群优化、人工免疫系统优化和蚁群优化等。 进化计算作为一个总体算法方法论，其多样性对于求解多目标优化问题非常重要。 最近三十年，仿真自然现象例如进化、遗传和免疫成为数据挖掘领域普遍的 方法，采用进化算法e a ( e v o l u t i o n a r ya l g o r i t h m s ) 能发现微阵列基因表达数据 中的全局最优解，为同时优化几个相互冲突的目标( 例如聚类的大小和同源性) 提出了多目标进化优化算法来发现微阵列数据中的全局最优双聚类。 本文主要研究利用多目标优化进化计算求解微阵列数据集的聚类问题，重点 研究多目标进化优化聚类算法、多目标粒子群优化双聚类、多目标人工免疫优化 双聚类及多目标蚁群优化双聚类等相关算法。 论文首先描述了双聚类算法研究现状及应用，分析微阵列数据集双聚类面临 的挑战，对多目标优化的研究现状及在生物信息学中的应用进行描述后，给出了 多目标进化双聚类算法的基础。 论文对当前进化算法和多目标进化双聚类算法进行分析，总结了多目标进化 优化聚类算法的基本框架。引进一个局部搜索策略，提出多目标进化优化三维聚 类算法( m o e t c ) ，挖掘g s t 数据中的3 d 聚类，在此基础上，应用。选择策 略和e 支配策略加快算法的收敛，提出基于。选择的三维聚类算法，并进行实验 结果分析。 粒子群优化仿真鸟群觅食的运动，具有快速收敛和相对简单等性质，同时又 作为基于群体的技术，使其成为求解多目标优化问题的自然选择。本文应用多目 标粒子群优化算法来求解双聚类问题的全局最优解，结合支配和局部搜索方法， 提出多目标粒子群优化双聚类( m u l t i o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n b i c l u s t e r i n g ，m o p s o b ) 算法来挖掘微阵列数据集的具有较低的均方残差的具有 生物意义的最大双聚类。为进一步改善最优解的多样性，本文应用拥挤距离更新 策略，提出拥挤距离多目标粒子群优化双聚类方法( c r o w d i n gd i s t a n c eb a s e d 第i 页 国防科学技术大学研究生院博士学位论文 m u l t i o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o nb i c l u s t e r i n g ，c m o p s o b ) ，其多样性、 收敛性和算法时间复杂度优于多目标进化双聚类算法。 最近的研究工作表明， 利用人工免疫系统求解多目标优化问题，可改进搜 索能力和适用性，大大地提高了收敛速度，改进最优解的多样性。论文对当前人 工免疫算法及多目标免疫优化算法进行分析后，基于人工免疫系统的免疫响应原 理，扩展解的支配关系和拥挤更新机制，提出了多目标免疫优化双聚类 ( m u l t i - o b j e c t i v ei m m u n eo p t i m i z a t i o nb i c l u s t e r i n g ，m o i o b ) 算法，实验表明算 法能有效地找到更多有意义的双聚类。 蚁群优化算法仿真觅食蚂蚁的生物学行为，在包括多目标优化在内的许多领 域成为一个非常有效的问题求解策略。多目标蚁群优化主要求解多目标的组合优 化问题，双聚类问题是典型的组合优化问题，因此本文整合局部搜索策略，提出 了一个新的多目标蚁群优化双聚类算法( m u l t i o b j e c t i v ea n tc o l o n yo p t i m i z a t i o n b i c l u s t e r i n g ，m o a c o b ) 求解微阵列数据集的具有重大生物意义的最大双聚类。 为进一步保持最优解的多样性，本文组合拥挤群体更新策略到基于群体的多目标 蚁群优化双聚类算法中，提出基于拥挤计算的多目标蚁群优化双聚类( c r o w d i n g c o m p u t a t i o nb a s e dm o a c ob i c l u s t e r i n g ，c m o a c o b ) 算法来发现一个或者多个 具有重大生物意义的最大的双聚类，并在两个基因表达数据集进行实验分析。 总体而言，本文对于多目标进化双聚类进行了深入研究，针对微阵列数据提 出了几个双聚类算法，对于推进高维数据中的多维聚类研究具有一定的理论意义 和实用价值。 主题词：微阵列数据，双聚类，多目标进化计算，粒子群优化，蚁群优化 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t m i c r o a r r a yt e c h n i q u e sc a l lm e a s u r et h ee x p r e s s i o nl e v e l so ft h o u s a n d so fg e n e s s i m u l t a n e o u s l y t h o s em i c r o a r r a yd a t ap r o v i d em a s s i v ea m o u n to fi n f o r m a t i o n ，w h i c h i sl e a d i n gt ot h ed e v e l o p m e n to fs o p h i s t i c a t e da l g o r i t h m sc a p a b l eo fe x t r a c t i n gn o v e l a n du s e f u lp a t t e r n sf r o mab i o m e d i c a lp o i n to fv i e w b i c l u s t e r i n ga p p r o a c hi sav e r y n s e f u lt e c h n i q u eo fd a t am i l l i n gf r o mm i c r o a r r a yd a t a , a n ds h o ws t r o n ga d v a n t a g ei n m a n ya p p l i c a t i o n s l em i n i n gb i c l u s t e r i n gf r o mm i c r o a r r a yd a t a , m a n yo b j e c t i v e s c o n f l i c t i n gw i t he a c ho t h e rn e e db eo p t i m i z e ds i m u l t a n e o u s l y ，w h i c hm u l t i - o b j e c t i v e o p t i m i z a t i o n ( m o o ) i sb e i n g t h ev e r yg o o da p p r o a c ho fs o l v i n gb i c l u s t e r i n g e v o l u t i o n a r yc o m p u t a t i o n ( e c ) i saf i e l do fre s e a r c hd e d i c a t e dtoth est u d yo f a l g o r i t h m sw h i c hm a i n t a i ns o m ef o r mo fs o l u t i o nm e m o r y w h i c hi su s e dt ob i a s f u t u r es o l u t i o nc r e a t i o n s o m ec o m m o ne x a m p l e so fa l g o r i t h m sf i t t i n gi n t ot h i sb r o a d d e f i n i t i o no fe cc o n t a i ng e n e t i ca l g o r i t h m s ( g a ) ，g e n e t i cp r o g r a m m i n g ( g p ) ， e v o l u t i o n a r ys t r a t e g i e s ( e s ) ，d i f f e r e n t i a le v o l u t i o n ( d e ) ，s i m u l a t e da n n e a l i n g ( s a ) ， p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) ，a r t i f i c i a li m m u n eo p t i m i z a t i o n ( 灿o ) ，a n da n t c o l o n yo p t i m i z a t i o n ( a c o ) e c ，a sag e n e r a la l g o r i t h mm e t h o d o l o g y ，m a i n l y f o c u s e so nt h ed i v e r s i t yo fs o l u t i o n sw h i c hi sv e r yi m p o r t a n tt om 0 0 i nth er e c e n tt h ir t yy e a r s ，i ti sac o m m o nd a t am i n i n gap p r o a c h t o s i m u l a t i n g n a t u r a l p h e n o m e n as u c h a se v o l u t i o n a r y ，g e n e t i ca n di m m u n e e v o l u t i o n a r y a l g o r i t h m s ( e a ) c a l lf i n dg l o b a lo p t i m a ls o l u t i o n sf r o mm i c r o a r r a yd a t a a so p t i m i z i n g m a n yc o n f l i c t i n go b je c t i v e s ( i nt h ec a s eo f b ic l u s t e r i n g ，s u c ha st h esi z ea n do ft h e h o m o l o g o u s o fc l u s t e r ) ，m u l t i o b j e c t i v ee v o l u t i o n a r yc o m p u t a t i o na l g o r i t h m s ( m o e c a ) i sp r o p o s e dt of i n dg l o b a l l ye f f i c i e n tc l u s t e r so fm i c r o a r r a y d a t a t m s p a p e rm a i n l ya i m so nt h er e s e a r c ho nm o e c a t o s o l v i n gb i c l u s t e r i n g0 f m i c r o a r r a yd a t a ，s u c h a s m u l t i o b j e c t i v ee v o l u t i o n a r yc o m p u t a t i o nb i c l u s t e r i n g a l g o r i t h m s ，m u l t i o b j e c t i v ep a r t i c l e s w a r mo p t i m i z a t i o n b i c l u s t e r i n g ，a r t i f i c i a l i m m u n eo p t i m i z a t i o nb i c l u s t e r i n ga n dm u l l i - o b j e c t i v e a n tc o l o n y o p t i m i z a t i o n b i c l u s t e r i n g f i r s t ，t h i sp a p e rp r o v i d e sas u r v e ya n dt h ea p p l i c a t i o na r e ao fb ic l u s t e r i n g t h e a u t h o ra n a l y s e st h ec h a l l e n g eo fm i c r o a r r a yd a t ab i c l u s t e r i n g 功ec u r r e n tm o o a l g o r i t h m sa n dt h eap p l i c a t i o ni nb i o i n f o r m a t i c sa r ep r o v i d e d t h e nt h ep r e m i s e o f m o o b i c l u s t e r i n ga l g o r i t h mi sd e s c r i b e d t h i sp ap e r sa r i al y s e sth ec a l r e n te v o l u t i o n a r yc o m p u t a t i o na l g o r i t h m san d m u l t i o b j e c t i v eev o l u t i o n a r yb ic l u s t e r i n ga l g o r i t h m s ，a n ds u m m a r i z e st h eal g o r i t h m f r a m e w o r k i n t r o d u c i n ga lo c a ls e a r c hs t r a t e g y , t h ea u t h o rp r o p o s e sm u l t i - o b j e c t i v e e v o l u t i o n a r ytr i c l u s t e r i n grm o e t c ) t o m i n e3 dcl u s t e r sfr o mgs t ( g e n e s a m p l e - t i m e ) d a t a t h e nu s i n gos e l e c t i n ga n de - d o m i n a n c es t r a t e g yt o 第i i i 页 国防科学技术大学研究生院博七学位论文 q u i c k e n th ec o n v e r g e n c eo ft h ea l g o r i t h m ，t h ea u t h o rp r o p o s e s6s e l e c t i o nb a s e d m u l t i - o b j e c t i v ee v o l u t i o n a r yt r i c l u s t e r i n ga l g o r i t h m e x p e r i m e n t a la n a l y s i si s p r o v i d e di nt h el a s to ft h es e c t i o n p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) i sah e u r i s t i cs e a r c ht e c h n i q u et h a ts i m u l a t e s t h em o v e m e n t so faf l o c ko fb i r d sw h i c ha i mt of i n df o o d t h er a p i dc o n v e r g e n c ea n d r e l a t i v es i m p l i c i t yo fp s oa n dt h ef a c tt h a ti sap o p u l a t i o n - b a s e dt e c h n i q u eh a v em a d e i tan a t u r a lc a n d i d a t et ob ee x t e n d e df o rm o o t h i sp a p e ra d a p t sm u l t i - o b j e c t i v e p a r t i c l es w a r mo p t i m i z a t i o nt o f i n dt h eg l o b a lo p t i m a ls o l u t i o no fb i c l u s t e r i n g c o m b i n i n ge - d o m i n a n c e 谢l l o c a ls e a r c h t e c h n i q u e ，t h i sp a p e rp r o p o s e s m u l t i - o b j e c t i v e p a r t i c l es w a r mo p t i m i z a t i o nb i c l u s t e r i n g ( m o p s o b ) t om i n e m a x i m a lsi g n i f i c a n tb ic l u s t e r sw i t hio w e rme a ns q u a r e dre s i d u e t of u r t h e rim p r o v e t h ed i v e r s i t yo fo p t i m a ls o l u t i o n s ，a p p l y i n gc r o w d i n gd i s t a n c eb a s e du p d a t es t r a t e g y , t h ea u t h o rp r o p o s e sc r o w d i n gb a s e dm u l t i - o b j e c t i v ep a r t i c l es w a r m o p t i m i z a t i o n b i c l u s t e r i n g ，c m o p s o b ) ，w h i c hh a sb e t t e rp e r f o r m a n c et h a nm o e a ba l g o r i t h m s r e c e n t l y , w h i l eso l v i n gm o o ，t h eu s eo fa r t i f i c i a li m m u n es y s t e mca nim p r o v e s e a r c ha b i l i t ya n da d a p t a b i l i t y , a n dq u i c k e n sth ec o n v e r g e n c eoft h ea l g o r i t h ma n d e n h a n c e st h ed i v e r s i t y a f t e rp r o v i d i n gt h es u r v e yo ft h ec u r r e n ta r t i f i c i a li m m u n e a l g o r i t h m sa n dm u l t i - o b j e c t i v ei m m u n eo p t i m i z a t i o na p p r o a c h ，b a s e do nt h ei m m u n e r e s p o n s ep r i n c i p l eo fa r t i f i c i a li m m u n es y s t e m ，t h i sp a p e re x t e n d sd o m i n a n c er e l a t i o n a n dp e r f o r m st h em e c h a n i s mo f c r o w d i n gc o m p u t a t i o na n dp r o p o s e san o v e l m u l t i o b j e c t i v ei m m u n eb i c l u s t e r i n g ( m o i b ) a l g o r i t h mt o o b t a i nm a n yp a r e t o o p t i m a ls o l u t i o n sd i s t r i b u t e do n t o t h ep a r e t of r o n t e x p e r i m e n t a lr e s u l t so nr e a l d a t a s e t ss h o wt h a to u ra p p r o a c hc a ne f f e c t i v e l yf i n dm o r es i g n i f i c a n tb i c l u s t e r st h a n o t h e rb i c l u s t e r i n ga l g o r i t h m s a n tc o l o n yo p t i m i z a t i o na l g o r i t h m s ( a c o ) s i m u l a t et h eb i o l o g yb e h a v i o ro fa n t c o l o n yf i n d i n gf o o d ，a n dh a v e b e e ns h o w n t ob ee f f e c t i v ep r o b l e ms o l v i n gs t r a t e g i e s f o raw i d er a n g eo fp r o b l e md o m a i n s ，i n c l u d i n gm o o m u l t i o b j e c t i v ea n tc o l o n y o p t i m i z a t i o n ( m o a c o ) m a i n l yf o c u s e so ns o l v i n gt h em u l t i - o b j e c t i v ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，a n dt h eb i c l u s t e r i n gp r o b l e mi s c o m b i n a t o r i a l t h i sp a p e r , t h e r e f o r e ，i n c o r p o r a t e s l o c a ls e a r c h t e c h n i q u ei n t oa c o ，a n dp r o p o s e san o v e l m u l t i - o b j e c t i v ea n tc o l o n yo p t i m i z a t i o nb i c l u s t e r i n g ( m o a c o b ) a l g o r i t h mt o m i n eb i c l u s t e r sf r o m m i c r o a r r a y d a t a s e t t h e ni n c o r p o r a t e s c r o w d i n gu p d a t e t e c h n o l o g yi n t omo a c o b ，t h i sp a p e rp r o p o s e san o v e lc r o w d i n gb a s e dm o a c o b i c l u s t e r i n g ( c m o a c o b ) a l g o r i t h m e x p e r i m e n t a lr e s u l t sa r es h o w no nt w or e a l g e n ee x p r e s s i o nd a t a s e t i ns u m m a r y ，t h i st h e s i ss t u d i e sd e e p l ym u l t i o b j e c t i v ee v o l u t i o n a r yc o m p u t a t i o n b i c l u s t e r i n go fm i c r o a r r a yd a t a ，a n dd e v e l o p ss e v e r a le f f e c t i v eb i c l u s t e r i n ga l g o r i t h m s f o rm i c r o a r r a yg e n ee x p r e s s i o nd a t a , w h i c hh a sa c a d e m i ca n dp r a c t i c a lv a l u ef o r a d v a n c i n gt h et h e o r ya n dp r a c t i c a b i l i t yo fc l u s t e r i n gi nh i g hd i m e n s i o n a ld a t a 第i v 页 国防科学技术大学研究生院博十学位论文 k e yw o r d s ：m i c r o a r r a yd a t a ，b i c l u s t e r i n g ，p a r t i c l es w a r mo p t i m i z a t i o n ， m u l t i - o b j e c t i v ee v o l u t i o n a r yc o m p u t a t i o n ，a n tc o l o n yo p t i m i z a t i o n 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图2 - 1 拥挤距离计算2 1 图2 - 2 双聚类的编码方案2 3 图3 - 13 d 聚类的编码方案3 3 图3 2m o e t c 算法挖掘的三维聚类3 7 图4 1 酵母数据中挖掘的双聚类( 2 4 1 5 ) 的基因表达图谱6 1 图5 - 1 免疫算法框架7 3 图6 - 1 酵母数据中挖掘的双聚类( 1 6 1 4 ) 基因表达图谱9 8 第v 页 国防科学技术大学研究生院博士学位论文 表目录 表3 1 不同a 值产生的最好3 d 聚类3 5 表3 2 三个算法的性能比较3 6 表3 3 三个聚类的g o 术语3 6 表3 - 4 四个算法性能比较结果4 1 表4 1m o p s o b 算法在酵母数据上发现的部分双聚类5 6 表4 2m o p s o b 算法在人类数据发现的部分双聚类5 6 表4 3 算法参数设置5 7 表4 4 三算法的实验性能比较5 7 表4 5 酵母数据中获得的双聚类6 l 表4 6 人类基因数据挖掘的双聚类6 2 表4 7 算法性能比较6 2 表4 8 聚类中基因集的共享g o 术语6 3 表5 1m o i o a 算法在酵母数据中挖掘的双聚类7 7 表5 2m o i o b 算法在人类数据中挖掘的双聚类7 7 表5 3 算法参数设置7 8 表5 - 4 算法比较分析7 8 表5 5 双聚类中基因集的g o 术语7 9 表6 1 算法性能比较9 5 表6 2 算法c m o a c o b 算法在酵母数据中挖掘的双聚类表9 8 表6 3c m o a c o b 算法在人类基因数据上挖掘的双聚类9 9 表6 - 4 算法性能比较9 9 表6 5 双聚类中基因集的g o 术语1 0 0 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成 果尽我所知除文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰 写过的研究成果，也不包含为获得国防科学技术大学或其他教葭机构的学位或证书而使用 过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意 学位论文作者签期：2 0 0 9 年1 0 月1 5 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国防科学 技术大学可以保髯并向国家有关都门或机构送交论文的复印件和电子文档，允许论文被查 阅和借阅：可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文 学位论文作者签 作者指导教师签 期z2 0 0 9 年l o 月1 5 日 期：2 0 0 9 年1 0 月1 5 日 国防科学技术人学研究牛院博士学位论文 第一章绪论 聚类技术广泛应用于微阵列数据分析中，假定相关的基因在所有条件下具有 相似的表达模式，这不是非常合理的，特别是当数据集包括许多不同类型的条件 时。最近提出了一种同时对基因和条件进行聚类的双聚类方法，发现基因子集在 条件子集下表现出相似的表达模式，引起了研究人员的高度关注。 本章描述了双聚类的相关概念，然后对当前的双聚类算法进行分类总结，强 调双聚类模型建立的数学基础和算法思想，并对双聚类算法的应用进行了描述， 对微阵列数据集双聚类所面临的挑战进行了分析研究，最后描述了论文的主要工 作和结构。 1 1 引言 现代技术提供了有效的数据收集方法，d n a 微阵列技术的出现彻底改变基 因表达实验的研究。数以千计的基因可以同时进行探究，其转录m r n a 表达水 平可以同时测量。通过在不同的实验条件( 如不同的病人，不同的组织或变化莫 测的细胞环境) 下重复实验，可以收集到几十至数百个实验的数据，这些大型数 据集的分析对算法的研究提出了重大的挑战。 聚类可以说是分析基因表达数据最通用的方法，并且成功应用在许多不同的 领域，如发掘基因路径，基因聚类和功能预测等多方面。然而这种分析由于要考 虑的基因数量庞大，要考虑的条件太多以及微阵列实验的噪声【l 】而变得异常的复 杂。 研究者们提出了几个非监督聚类学习方法如层次聚类【2 j ，c 均值1 3 j ，k o h o n e n 图【4 j ，支持向量机方法【5 】等，这些聚类方法对相应条件下表达相似的基因进行分 组( 共表达基因) ，相同聚类中的基因在不同的环境下具有相似的响应，因而可 能共享共同的功能。另外，聚类能用于对具有相似基因图谱的条件进行分组，因 此也能得到相应的结论。基因发现功能、基因功能注释、疾病诊断、药物发现及 肿瘤亚型发现，就是我们进行聚类分析所追求的目标。 然而，聚类作为微阵列数据分析方法显示出某些限制：( 1 ) 一个基因( 条件) 仅可以属于一个聚类；( 2 ) 基因( 条件) 根据他们在所有条件( 基因) 下的行为 进行分组。 第一个限制使得经典的聚类不是研究基因表达最好的工具：一个基因可以起 不同的作用，即可以在不同生物过程中与不同的基因分组一起发挥不同的作用。 因此，某些基因将出现在多个聚类中。第二个限制是由于同时考虑所有的条件 ( 列) ：不能定位部分条件出现的隐藏信号。第一个限制可以通过应用模糊聚类 第1 页 国防科学技术大学研究生院博士学位论文 7 1 、模糊c 均值法或者重叠聚类方法悼j 来求解，然而，求解这两个限制的最合适 的方法还是双聚类 9 1 。 基因表达的双聚类在微阵列分析中具有特殊的意义。最近几年来，提出了几 个双聚类方法确定基因表达数据的局部模型，与经典的聚类方法相比，双聚类不 要求相同的聚类中的基因在所有的实验条件下相似地表达，一个双聚类定义为一 个基因的子集，这个集合中的基因在一个条件子集中具有可比较的表达模式，这 对于揭示仅仅在部分条件下活跃的生物过程是非常有用的。 对基因样本( 或者条件) 数据矩阵进行双聚类，可以把条件子集下表达相 似的基因子集聚集在一起，可发现微阵列基因表达数据的有趣的模式，对于基因 时间微阵列数据矩阵来说，双聚类可以发现相关基因表达水平随着时间发生变 化的趋势，从而构建基因调控网络和生物p a t h w a y 。m a d e i r a 等人在【l o 】对二维双 聚类的研究做了一个较好的综述，从双聚类的类型，双聚类的模式，聚类搜索的 方法以及主要应用领域等相关方面进行比较全面的分析和分类，总结双聚类中应 用的搜索方法包括迭代行和列聚类、分而治之策略、贪婪搜索、穷举双聚类、分 布参数确定及其他方法。 微阵列技术的迅速发展，使得同时记录一系列时间点上基因集在样本集( 条 件集) 下的表达水平已经非常普遍，这样产生了大量的三维( 3 d ) 微阵列数据 集。数据集由基因、样本和时间三种类型的数据组成，即所谓的基因样本时间 g s t 微阵列数据集，3 d 聚类引起了很多研究者的关注【1 1 以3 1 。 1 2 预备知识及问题陈述 本节首先定义一些论文所应用到的基本术语，符号表示，然后给出微阵列数 据聚类问题的陈述。 1 2 1 基本术语 一个二维基因表达数据矩阵d = g x c = d o ) ( f 【1 ，n 】，【1 ，聊】) ，为一个, x m 实数矩阵，其中g 为行的集合，代表, 个基因的集合旭1 ，9 2 ，g n 】，c 代表列 的集，代表m 个生物实验条件的集合( c 1 ，c z ，c n ) ，每个数据项西表示基因聃在 条件c i 下基因表达水平值。 定义1 1 双聚类。对于给定的基因表达数据集d = g x c = 办) ，如果存在一个 子矩阵b = g x c ，其d p g c g ，c c c ，满足某些同源特性，我们称b 为一个双聚类。 定义1 2 最大双聚类。对于一个双聚类b = g x c ，如果不存在任何其他双聚类 b - g c ，使得gcg 和ccc 成立，则称双聚类b 为最大双聚类。 第2 页 国防科学技术大学研究生院博士学位论文 定义1 3 维度平均。对于一个双聚类b = g x c ，基因子集g c g ，条件子集c c - c ， 西是数据集d 中基因舒在条件q 下的表达水平值。我们指定九表示双聚类b 中 第i 个基因表达水平值的平均，如表示双聚类b 中莉个条件下基因表达水平值的 平均，如表达双聚类b 的所有项的平均值，其定义如式( 1 1 ) ( 1 2 ) ( 1 3 ) 所示，式中 s i z e ( g ，c ) = l g l l e i 表示双聚类的大小。 d , c = 南伊吒 ( 1 1 ) 心= 击姆吃 ( 1 2 ) 叱2 南懈加。乃 ( 1 3 ) 定义1 4 残差和均方残差。给定一个双聚类b = g x c ，为评估每个元素西的真 实值与它的表达值之间的差异，我们定义西的残差为r ( 蝴，如式( 1 4 ) 所示。双聚 类b 的均方残差( m e a nsq u a r e dr e s i d u e ，m s r ) 定义为双聚类b 包括的所有元素 的残差平方总和来估计双聚类b 的总体质量，如式( 1 5 ) 所示。 ，( 乃) = 乃一d , o 一吒+ 叱 m s r ( g ，c ) = 丽1 e g e 。r ( 毛) 2 ( 1 4 ) ( 1 5 ) 定义1 5 行方差。给定一个x 2 聚类b = g x c ，其第i 个基因的方差用r v a r ( i ，c ) 表示如式( 1 6 ) 所示，总体基因维( 行) 方差定义为所有基因的方差的平均，如式 ( 1 7 ) 所示。 r v a r ( f ，加高闾( 嘭一彬 ( 1 6 ) 尺v a r ( g ，c ) = 丽1 雠e 。( 略一彬 ( 1 7 ) 1 2 2 问题描述 ( 1 ) 双聚类 给定数据矩阵a ，发现双聚类集合 反= ( 厶，以) ，k = l ，2 ，) ，每个双聚类满 足关于同源性的某些特定的性质，不同的计算方法采用不同的衡量同源性的准则。 双聚类的基本目标是挖掘满足最大可接受值均方残差阈值6 ，最小基因维方差阈 值) ，最大的双聚类。 ( 2 ) 3 d 聚类 给定一个g s t ( g e n e s a m p l e t i m e ) 微阵列数据矩阵a ，最小基因数阈值m i n g ， 最小样本数阈值m i n s 以及最小时间点数阈值r a i n ，最大可接受的均方残差阈值 第3 页 国防科学技术大学研究生院博士学位论文 j ，最小基因维方差阈值) ，3 d 聚类的目标是挖掘满足这些参数要求的具有重大 意义的最大基因聚类集合 反= ( q ，瓯，瓦) ，七= 1 ，2 ，) ，每个3 d 聚类满足关于同 源性的某些特定的性质，不同的计算方法采用不同的衡量同源性的准则。 1 3 双聚类研究现状 双聚类是一个旧的话题，早在1 9 7 2 年h a r t i g a n 1 1 就提出了双聚类 ( b i c l u s t e f i n g ) ，2 0 0 0 年c h e n g 和c h u r c h 2 1 把双聚类的概念引入到微阵列数 据分析中，随后出现了各种计算方法用于双聚类，本节对计算方法的数学模型基 础和相关聚类思想进行分类。 1 3 1 基于行或列模式的双聚类计算方法 基于模式的双聚类建立一个评价双聚类的标准优化函数，然后迭代地增加或 删除行或列来优化目标函数以求解满足相关条件的双聚类。 自顶向下的聚类算法由整个原始微阵列数据矩阵开始，重复地从当前矩阵中 贪婪地添加或删除一行或一列，直到找到所有双聚类为止【l 】。 自底向上聚类算法随机选择行和列作为初始的双聚类【3 】，建立关于双聚类的 大小、m s r 和行方差的目标函数，一次增加多行或多列改进聚类质量【4 5 1 。 双聚类质量的度量标准大多采用双聚类的方差和均方残差作为双聚类质量 的度量标准【i j 和数学平均方差【6 j ，其它标准如双聚类间的重叠度【5 】，最大标准区 域m s a ( m a x i m a ls t a n d a r da r e a ) 7 j 以及双聚类的占有率嗍。 此类方法一般需要设置一个质量阈值( 上界) 6 ，这依赖于数据集上的先验 知识，搜索过程采用随机技术，因而不能发现所有双聚类，尤其重叠的双聚类， 属于非确定的双聚类计算方法。 1 3 2 概率聚类 对于高度不确定的分析系统来说，z a d e h 提出了模糊集理论【9 】。模糊聚类产 生模糊集的聚类，因此每个对象具有成员隶属度【o ，1 】地属于一个聚类。不像经 典聚类产生非重叠聚类，在模糊聚类中，一个对象可能属于几个聚类。模糊技术 能较好地建模重叠的双聚类，并改进优化过程。这类算法应用模糊技术，考虑双 聚类的均方残差、双聚类大小等多个参数来建立一个目标函数，通过优化方法来 建立可重叠的模糊概率聚类算法【1 0 】。 在概率聚类i l i 1 2 】，一个对象的隶属度之和为1 。如果取消这个约束，就是可 能性聚类【i 引。由于特异者在所有聚类都通常被赋与较低的隶属度，可能性概率 聚类对噪声不太敏感，但趋向于产生过多重叠的聚类。为避免这种情况，可以结 第4 页 国防科学技术大学研究生院博士学位论文 合可能性聚类和概率的方法，应用其它技术进行双聚类，如谱技术、遗传模糊聚 类和范化粗糙集双聚类【5 1 。 1 3 3 图论方法双聚类 基于图论双聚类的主要观点是把数据矩阵建模成一个带权的二部图g