（信号与信息处理专业论文）基因微阵列数据的分析算法.pdf

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文d 论文作者签名：日期：竺! 导师签名： 乡扭互丛2 日 期：兰坚二卫旦 堆i 太i 微阵列数据的分析算法 摘要 基因微阵列数据的分析算法 中文摘要 基因微阵列( 又称基因芯片) 可应用对于不同发展阶段，不同人体组织，不同临 床条件以及不同生物体等条件下的基因表达水平的测量。基因芯片的出现币在给生命 科学研究、疾病诊断、新药丌发、食品卫尘监督等领域带来一场革命。与此同时，由 基因微阵列技术带来的海量数据也对传统的信息处理技术带来了很大的挑战。鉴于 此，本文对基因微阵列的预处理和聚类算法进行了研究。本文的主要贡献如下： 首先，提出了一种改进的稳健b w e s s 算法，对基因微阵列的数掘进行标准化处 理。该算法首先利用局部加权线性回归对数据点进行平滑估计，然后再利用核估计算 法对误差项进行估计，以进一步减小误差，最后对每个格子单的数据点进行缩放处理。 实验证明了本文算法的高效性。 其次，本文提出了一种新的基因表达矩阵的缺失值估计算法。该算法首先利用迭 代的k 哪e a n s 算法来挑选无缺失基因，再用j 踟e s $ t e i n 估计算法并结合核估计算法 得出最后的估计值。实验证明该算法在低缺失率的时候优于其它传统估计算法。 再次，本文对模糊谱双向聚类算法进行了改进。虽然模糊谱双向聚类算法能够取 得不错的效果，但是由于其使用的f c m 算法对数据类型的敏感性及其局部搜索能力， 限制了它的使用，因此本文应用g g 算法和遗传算法来改进原算法的局限性。实验证 明本文改进算法的优越性。 最后，本文提出了一种基于基因和条件提取的双向聚类算法。该算法利用央角余 弦法排除那些对聚类结果贡献小的表达数据，使得聚类只在提取的基因和条件中进 行，从而降低了计算复杂度。实验证明本文算法优于其它算法。 关键词：基因微阵列；标准化；j a m e s s t e i n 估计；核估计：双向聚类 作者：严德春 指导教师：王加俊 a b s t m c t g o r i t l l m sf o rg e n em i c r o a r r a yd a t aa n a l y s i s a l g o r i t h m sf o rg e n em i c r o a r r a yd a t aa n a l y s i s a b s t r a c t g e n em i c r o a m y ( a l s or e f b r r e dt oa sg e n ec h i p s ) c a nb eu s e di nm e a s u r i n gg e n e e x p r e s s i o nl e v e l si nd i f f b r e n td e v e i o p m e n t a ls t a g e s ，d i f f e r e n tb o d yt i s s u e s ，d i f f l e r e n tc i i n i c a i c o n d i t i o n sa n dd i 矗 e r e n t0 略a 1 1 i s m s ，e 毫c g e n ec h i p sa r en o wb r i n g i n ga 黟e a tr e v 0 l u l i o ni n t h ef i e l d so fi i f es c i e n c er e s e a r c h ，d i s e a s ed i a g n o s i s ，n e wd 1 1 l gd e v e l o p m e n t 锄df o o d h y g i e n es u p e n ，i s i o n m e a n w h i l e ，t 1 1 em a s s i v eg e n em i c r o a r r a yd a t aa l s ob r i n g g r e a t c h a l l e n g e st ot h et r a d i l i o n a l 妣h 州q u e so fi n f 0 糯a t j o np 蹴e s s i n g t h e r e f o r e ，幽sl h e s j s f b c u s e so nd e v e l o p i n ga l g o r i t h m sf o r p r e 巾r o c e s s i n ga n db i c l u s t e r i n go ft h eg e n e m i c r o a r r a yd a t a t h ec o n 讲b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： f i r s t l y a i li m p r 0 v e dv e r s i o no ft h er o b h s tl 0 w e s sno _ m 豫l i z a i o nj sp p o s e df o rm e n o 咖a l i z a t i o no ft h eg e n em i c r a o 鲫r a yd a t a i i it h i s a l g o r i t h m ，t h ed a t aa r ef i r s t l y s m o o t h e dw i t ht h el o c a l l yw e i g h t e dl i n e a rr e g r e s s i o nm e t h o d ，t h e nt h ee r r o ri sf h n h e r 愆d u c e db ye s t i m a t i n gt h e 代s i d u ei i ls m 0 0 h i n ge s t i m a t j o ni na 触m e w o 出o fk e r n e l e s t i m a t i o n ，f i n a l l y s c a l i n go p e r a t i o ni sp e r f b 邝f l e dw i t hr e s p e c tt o 髓c hd a t ap o i mo nt h e 鲥d e x p e r i m e n t a lr e s u l t ss h o wb o m e f 盹c t i v e n e s sa n d e f f i c i e n c yo f t h i sa l g o r i t h m s e c o n d l y ar 1 0 v e ls 缸a t e g yf o re s t i m a t i n gm em i s s i n gd a t ai nt h eg e n ee x p r e s s i o n m 撕xi sp r e s e n t e d t h ea l g o r i m mi sb 觞e do nm ej a m e s 心t e i na n dk e m e le s t i m a t i o n p r i n c i p l e s w h e r et l l ee s t i m a t i o nm 撕xi so b t a i 玳泔w i mt h ek 哪啪sa l g o r i t h m e x p e m e n t a lr e s u l t ss h o wt h a to u ra l g o r i t h mi ss u p e o rt oc o n v e n t i o n a ia l g 硎t 量l mu n d e r l o w e rd a t ai n j s s i n gm l e 。 t h i r d l y a ni m p r o v e dv e f s i o no fm em z z ys p c 斌m lb i c l u s t e r i n ga l g o r i t h mi sp r e s e n t e d a l t i l o u g hm z z ys p e c 删b i c i u s t e r i n ga l g o t i l mp e r f b 咖sw e i l ，d i s a d v 锄t a g e s ，s u c h 硒m e s u s c 印t i b i l j t i e st 0d a t at y p e s 卸da j s ot 1 1 el o c a ls c a r c h i n gc a p a b j l i t y o ft l l ef ma l g o r i t h m i n v o l v 酣i i li tp r e v e n ti tf r o mw i d ea p p l i c a t i o 眦t h e r e f o r e ，b o t l lt l i eg ga l g o r i t l l m 砒l dt l l e g e n e t i ca l g o r i t l l ma 陀 u s e dt 0 i m p m v e t l l e m z z ys p e 删 b i c i u s t e r i n gm g o r i t h m e x p e r i m e n t a ir e s u l t ss h o we x c e l l e n tp e r f o m a n c eo fo u ra l g o r i t h m f i n a l l y ，an e wb i c l u s t e r i n go fg e n ee x p r e s s i o nd a 妇i sp r o p 。s e dw h i c hb a s e do nr e l a t e d g e n e sa n d c o n d i t i o n se x t r a c t i o n w ep r o p o s et or e m o v et h o s eg e n e so rc o n d i t i o n sw i t hl i t t l e c o n t r i b u t i o n st ot h ec o n s i d e r e db i c l u s t e r sb yc o m p u t i n gt h ee x t e n to f r e l a t i v i t yb e t w e e nt h e g e n e s ( c o n d i t i o n s ) a n dt h eb i c l u s t e r sw i t han o v e lm e a s u r ed e 行n e db 舔e do nt h ec o n s i n eo f t h e a n g l eb e t w e e nt h eg e n e( c o n d i t i o n )v e c t o ra n dav e c t o rw i t ha l l l sb e f 0 r et h e b i c l u s t e r i n gp r o c e s s a f t e rt h i sp r o c e s s ，b i c l u s t e r i n gc a nb ep e r f o 咖e do n l yi nt h ed a t as e t c o m p o s e do ft h ea b o v ee x t r a c t e dg e n e sa n dc o n d i t i o n sa n dh e n c et h ec o m p u t i n g c o m p l e x i t yo ft h ea l g o r i t h mc a nb er e d u c e d e x p e r i m e n t a l 陀s u l t ss h o we x c e e n t p e r f o 丌n a n c e0 f 0 u r a l g o r i t h m k e y w o r d s ：g e n em i c r o a l l r a y n o m a l i z a t i o n ，j a m e s - s t e i ne s t i m a t i o n ，k e m e le s l i m a t i o n ， b i c l u s l e r i n g m w r i t t e nb yd e c h u ny a n s u p e r v i s e db yj i a j u nw a n g 目录 第一章绪论1 1 1 引言1 1 2 基因微阵列技术。1 1 3 基因微阵列的应用领域3 1 4 基因微阵列数据分析常用软件3 1 5 基因表达数据预处理3 1 6 基因表达数据聚类分析5 1 6 1 相似性度量5 1 6 2 单向聚类7 1 6 3 双向聚类9 l 。7 本论文的研究内容及结构安排1 0 第二章改进的稳健l o w e s s 标准化算法在基因微阵列中的应用1 2 2 1 引言一l2 2 2 改进的稳健h w e s s 标准化算法1 2 2 2 1 局部加权线性回归一1 3 2 2 2 误差核估计调节1 4 2 2 3 格子的划分1 5 2 3 实验结果及分析1 5 2 4 本章小结1 9 第三章基因表达数据缺失值的j a 鹏s s t e i n 估计2 0 3 1 j a m e s - s t e i n 估计原理2 0 3 2 核估计的原理2 l 3 3 缺失值的j a m e s - s t e i n 估计2 1 3 3 1 问题描述2 l 3 3 2 无缺失基因的挑选2 2 3 3 3 缺失值估计算法2 3 3 3 4 实验结果与讨论2 4 3 4 本章小结2 6 第四章模糊谱双向聚类算法2 7 4 1 模糊谱双向聚类算法2 7 4 2g g 算法2 9 4 3 遗传算法3l 4 3 1 编码方法的确定一3 l 4 3 2 适应度函数的确定3 l 4 3 3 遗传算法操作方法的确定3 2 4 3 4 终止条件的确定3 2 4 4 具体算法描述3 2 4 5 实验结果一3 3 4 6 本章小结3 4 第五章一种基于基因和条件提取的双向聚类算法3 5 5 1 引。占3 5 5 2 双向聚类算法3 5 5 2 1 相似度3 5 5 2 2 基因表达矩阵预分类3 5 5 2 3 双向聚类类型3 6 5 2 4 稀疏矩阵获取3 6 5 2 5 层次聚类3 8 5 2 6 双向聚类的打分3 8 5 2 7 算法描述一3 8 5 3 实验结果及分析3 9 5 3 1 酵母基因i 表达数据的研究3 9 5 3 2 酵母基因l l 表达数据的研究4 3 5 3 3 双向聚类的应用。4 5 5 4 本章小结4 7 第六章总结与展望4 8 缩略词表5 0 参考文献5 2 攻读硕士期间发表的文章5 7 致谢5 8 1 1 引言 第一章绪论 生物信息学是上世纪分子生物学与计算机科学交叉结合产生的新学科，该学科主 要利用计算工具和相关方法来扩展对来自生物学、医学、行为科学和卫生等的数据的 使用【i l 。具体来讲，该学科主要通过结合数学、统计、计算机科学等学科对来自生物 大分子数据库的海量实验数据进行分析、处理，使之成为具有明确生物学意义的有用 信息l2 l 。通过对获得的生物信息进行研究，从而获取基因、核酸和蛋白质的结构功能 及其相互关系等，从而探索未知世界，使其更好地服务于人类社会。 上世纪8 0 年代末，随着人类基因组计划的实施，面对生物大分子数据的指数级 增长，专家丌始使用计算机对数掘进行处理，从而促进了生物信息学的兴起1 3 】。自生 物信息学诞生以来，它在许多领域发挥着不可估量的作用，如：医药、食品、农业和 环保等领域，且推动了这些领域的进一步发展。由于生物信息学的存在，通过对众多 杂乱的生物学实验数据进行处理研究，可以从中获得对生命运行机制的详细、系统的 理解。一般基因微阵列实验都会产生海量的数据，需要对其进行加工、处理才可得出 人们需要的有用信息。 现阶段生物信息学的重要任务是发展有效的信息分析工具、发展计算方法和模 型。首先发展有效的信息分析工具，可以储存、查询、管理和使用那些不断产生的海 量信息，然后对海量数掘进行处理、分析，并发展相应的数学统计算法和模型，最后 使得这些生物信息学成为服务于人类认识大自然的强有力的工具。 1 2 基因微阵列技术 生物信息学研究对象之一是基因微阵列，又称基因芯片。基因微阵列是将大量基 因探针按一定的排列方式固定在载体( 常用的载体有：硅片、玻璃、塑料等) 上，然 后按碱基配对的特性将载体上的d n a 分子与样品进行杂交，再通过计算机来获取生 物样品信息4 1 。基因微阵列检测的基本原理与传统核酸印迹杂交方法相比具有高通 箍二重绪论基幽毯隆到数邂鲢公盘簋洼 量、高精确度分析、高灵敏度分析等显著的特点。基因微阵列技术的出现为许多领域 ( 如：生物学、医学、化学等领域) 的研究提供了一个强有力的工具，同样在无形中 生物学、光学、统计学及计算机科学等学科的发展也促进了基因微阵列技术的进一步 发展。 世界上第一块基因微阵列芯片是由美国加州a f f y m 棚x 公司于1 9 9 1 年在玻璃片 上原位合成的，它结合了计算机、寡核苷酸合成、探针杂交及其它分子生物学技术f 5 】。 基因芯片除了原位合成的外，还有直接点样法，该法制备的c d n a 芯片是由斯坦福大 学于1 9 9 4 年完成的。此后十几年间，基因微阵列芯片技术几乎深入到所有的生物学 相关的研究领域之中，同样在生命科学研究中发挥举足轻重的作用。 图1 1 是基因微阵列进行分析的主要处理流程【6 】，通常情况下对基因微阵列的分 析主要有：微阵列和靶基因的制备、标记与杂交，荧光标记检测技术。 基因芯片 萋 荧光标记的样品 共聚焦显微镜 获取荧光图象 杂交结果分析 图1 1 基因微阵列分析流程 通常的制备方法主要有上述提到的：原位合成法和直接点样法i 。寡核苷酸芯片 的制备通常使用原位合成法，该方法由于反应量大，探针密度高，且该方法可以和直 接点样法结合使用，但由于该项技术受专利保护，没有得到普及。直接点样法多用于 c d n a 芯片制备，该方法简单易行，适合于制备点阵规模适中的基因微阵列。 2 基凼磁匪划数毯殴公逝差盔笙= 至结论 靶基因在杂交前必须进行分离、扩增和标记等处理【l 】。荧光标记法、同位素标记 法为现今主要的标记方法。般微阵列的阵列密度较小时常用同位素标记法，而微阵 列的阵列密度较高时常用荧光标记法，最常用的是双色荧光标记法，双色试剂是c y 3 和c y 5 。靶基因的杂交过程与一般的分子杂交过程基本相同。 荧光标记检测就是通过扫描仪( 常用的扫描仪有：激光共聚扫描仪、g e n e p i x 系 列扫描仪l | 7 】等) 检测标记物信号的强弱和分布，然后将得到的扫描图像输入计算机， 用专门的软件( 如n a g e n e 、g e n e p i x p r 0 等) 对杂交产生的印迹进行数据处理与定量分 析，所得的数据经标准化后进行统计分析，最后得到基因表达图谱。 1 3 基因微阵列的应用领域 基因微阵列的出现币在给生命科学研究、疾病诊断、新药丌发、生物武器战争、 司法鉴定、食品卫生监督等领域带来了一场革命。基因微阵列的主要应用领域1 8 】有： 1 ) 对比j 下常组织和疾病组织的基因表达谱差异，可以预防和治疗疾病； 2 ) 对疾病发生的过程、用药过程进行研究，可以实现对临床药效和药物的研究； 3 ) 基因突变检测。 1 4 基因微阵列数据分析常用软件 基因微阵列实验通常会产生海量的数据，如何对这些海量数据进行分析一般需要 借助软件，而基因微阵列数据分析的常用软件有：r 语言【9 】；斯坦福大学d r p b r o w n 实验室开发的c l u s t e r 、t r e e v i e w l l 川；微阵列数据图形显示及分析的商业软件包 g e n e s 胛n g 1 l 】用于功能基因组丌发的软件s p o t f i r ed e c i s i o n s u i t e f ；d rf u n c t i o n a l g e n o m i c s l l 2 】；用于双向聚类的软件b i c a 一13 1 。 1 5 基因表达数据预处理 基因表达数据在进行数据分析之前需要进行预处理，预处理的操作主要有：背景 的校正、弱信号的处理、信号的对数变换、重复数据的合并、数据的标准化、缺失值 的处理等。 3 箍= 童结论 基凼邀睦到数蜒盥盆蚯簋法 荧光强度是由背景荧光和标记d n a 的荧光共同作用产生的，因此为获取与 m r n a 量成比例的数值，应当减去对应于背景的荧光强度值，背景校正荧光强度才 真j 下反映了基因真实的转录水平。实现背景校正的方法有：局部背景校j 下、亚栅格背 景校正、分组背景校j 下、空白点背景校正、对照点背景校j 下等1 5 1 。 在微阵列上存在很多弱信号点，虽然它们信号很弱，但是不能武断地把它们全部 删除，因为它们不全部都是低质量的点。找到分离噪声和真正弱信号点的方法是至关 重要的，解决其问题的主要方法是重复微阵列实验和阈值法。重复实验的成本比较高， 而使用最多的是阈值法，主要存在的方法有：固值法、信噪比、基于累积分布函数法 垒壅【5 】 寸。 对数变换能够提供从生物学角度上易于解释和有意义的数据，且它比较方便。重 复能够减少统计量的变异，重复测量可用于估计实验中的噪声，比较不同处理问和组 内的变异，在特定的条件下把所有的重复值合并成一个数值会变得更为方便。 在基因微阵列的实验中测到的c y 3 和c y 5 的荧光强度值受许多因素的影响，包 括系统变异、随机变异。随机变异是由各种随机因素引起的，这些因素是无法控制的， 只能尽量减少它发生的可能性。而系统变异是可以控制的，标准化的目的就是减少系 统变异带来的误差。引起系统变异的因素包括样品的生物学差异和系统误差，系统变 异包括以下几个方面：1 ) 荧光物质的物理和化学属性；2 ) 扫描仪等硬件的设计；3 ) 标记的方法1 5 1 等。绝大部分基因微阵列技术都会引入基因的特异性偏倚，这种现象在 自身对照实验中可以清楚地看到。因此，系统误差的存在使得微阵列的基因表达水平 的直接比较是无法实现的，必须根据系统误差的来源对基因微阵列数据进行标准化， 消除系统误差的影响。现在有很多基因微阵列的标准化的方法，有的标准化方法虽然 快捷但是误差比较大，如：比例标准化法、分位数标准化法、差值标准化法【5 t 1 4 1 等。 有的标准化方法误差明显小很多但是时间就会得不到保障，如：q u a n t i l e 标准化法【1 5 j 、 l o w e s s ( 1 0 c 址i yw e i 曲臼司s m 0 0 t hs c a n e 印1 0 t ) 标准化法l l 们、基于神经网络模型或支 持向量机的标准化法【批2 1 、迭代或交叉的标准化法【2 3 捌、选择优化参考基因的标准化 法【2 5 1 、基于混合三种状态的标准化法冽等。其中l d w e s s 标准化法的应用是最广泛的。 基因表达数据中经常会出现缺失值缺失值的产生原因有很多种，包括：不充分 的实验方案，图像的损坏或芯片上的灰尘或划痕等。由于缺失值的存在，造成了实验 4 的误差，因而缺失值的估计就显得很重要。缺失值估计最常用的方法有：最近邻插值 法k n n i m p u t e ( k 剞e a r e s tn e i 曲b o ri m p u t a t i o n ) 1 2 7 1 、s k n n 插值法( s e q u e n t i a lk _ n e a r e s t n e i g h b o ri m p u t a t i o n ) 1 2 引、最小二乘插值法l l s i m p u t e ( l o c a il e a s ts q u a r ei m p u t a t i o n ) l2 9 1 、贝叶斯插值法b p c a i m p u t e ( b a y e s i a n 蹦n c i p a lc o m p o n e n t a n a l y s i s ) l 则等。最近 邻插值法是把与目标基因的欧氏距离最接近的七个基因挑选为目标基因，然后通过相 应的权值计算得到估计值。它虽然比较常用，但是误差比较大。s k n n i m p u t e 与 k n n i m p u t e 类似，只是它从缺失率最小的基因了1 ：始填充，且后续处理过程中使用填 充过的基因数据。它在缺失率比较高时，估计比较准确。最小二乘估计是另一个比较 常用的估计，它主要是基于最小二乘理论来估计得到估计值。贝叶斯插值法主要是对 表达矩阵进行主成分回归，然后使用贝叶斯估计理论在估计值的期望最大( e m 理论， e x p e c t a t i o nm a x i i n i z a t i o n ) 的情况下对缺失值进行估计。 1 6 基因表达数据聚类分析 1 6 1 相似性度量 聚类分析是依赖于相似度量法将相似的事物划分到一起，故要进行聚类分析时首 先要确定相似性指标1 3 l 】。度量事物的相似性的方法有很多，下面介绍几种常用的方法： 假设存在两个一维向量工= ( _ ，x 2 ，工。) 和_ ) ，= ( y l ，y 2 ，) ，。) 。 1 ) e u c l i d e 卸距离( 欧氏距离) ： s f ，竹( 工，) ，) = d ( 工，) ，) = 应用最广泛的相似性度量法，该方法放大了较大元素误差的作用。 2 ) m a n h a t t 锄距离： s f 朋( 毛) ，) = 九( 工，) ，) = l 而一y i f 该方法同等对待向量中的每个元素。 3 ) m i n k o w s k y 距离( 明氏距离) ： 5 ( 1 2 ) ( 1 3 ) 当川= 1 时，m i n k o w s k y 距离即为m a n h a t t 柚距离；当班= 2 时，m i n k o w s k y 距离即为 欧氏距离。 4 ) m a i l a l a n o b i s 距离( 马氏距离) ： s f 加( 工，) ，) ：d m ( x ，) ，) ：、乏：二j 五7 i = 丽 ( 1 4 ) 式中，s 为n 九的j 下定矩阵，表示x 和y 的协方差矩阵。该方法采用的是对向量各维 加权的思想，故又称广义欧氏距离。 5 ) 夹角余弦法： s i m t x y ) ；c o s l x ，y ) = 一 y ， f ， ( 1 5 ) 该方法在计算向量问相似度时，不会放大重要的数据对象的作用，它对所有的数据对 象都是平等的。 6 ) 相关系数法： ( 一习( y ，一歹) s f ，l ( 工，y ) = r ( 工，) ，) = _ ：j l _ t ( 1 6 ) ( ( 玉一i ) 2 ( ) ，。一y ) 2 ) j f 王if = i 在多元统计学中该方法是用来测度变量问线性相关程度的，其性质与央角余弦法类 似。 相似性的度量方法还有很多，本文只列举了几种常用的，由于相似性方法确定了， 下面即可进行聚类分析，尤其在没有数据的先验知识的情况下，聚类分析是基因表达 数据分析最常用的技术。聚类可以从聚类的方向不同分为单向聚类和双向聚类。图 1 2 ( a ) 、( b ) 为单向聚类的示意图，( c ) 为双向聚类的示意图。 6 一m 、， m m 一 薯 。 ，l l i 、jy x lm d = 、，y 工 ，l m s c o n d i t i o n sc o n d i | i 0 i l sc o n d i t i o l l s g e i l ec i u s t e r s ( a ) 1 6 2 单向聚类 c o l l d i f i o nc h i s t e r s b i c h i s t e r s ( b ) 图1 2 单向聚类与舣向聚类的区别 ( c ) 单向聚类从图1 2 ( a ) 、( b ) 可知是从单一方向( 行或列) 进行聚类，研究者们 已经提出了很多单向聚类算法，下面给出了几种常用的单向聚类算法。 1 ) k - 均值法( k 哪e 觚s ) 【3 2 l k 啊e a n s 算法由于其简单和快速性，使得它成为应用最广泛的算法之一，该算法 适用于大规模的数据计算。其具体算法见算法1 1 。 算法1 1 ：k 哪e a n s 算法 i n p u t ：数据矩阵，聚类数七； o u t p u t ：每行数据所属的类别： b e g i n 1 ) 从数据矩阵中随机取七行( 或列) 元素，作为七个簇的中心： 2 ) 计算剩下的元素到七个簇的中心的距离，按最小距离法进行归类； 3 ) 根据聚类结果重新计算聚类中心； 4 ) 按新的聚类中心重新进行聚类； 5 ) 重复第4 步，直至聚类结果不再变化。 6 ) 输出对应的聚类类别； e n d 2 ) 模糊聚类算法f c m ( m z z yc l u s t e r i n gm e a n s ) 【3 3 3 4 j 7 模糊聚类分析的思想首先由b e l i m a n 和z a d e h 等人于1 9 6 6 年提出来。1 9 7 3 年d u i u l 提出了模糊聚类算法f c m ，1 9 8 1 年b e z d e k 对其进行改进并推广到实际应用中。模糊 聚类是通过隶属度函数将样本空间的样本点分成七类，任意一个样本点几乎不可能 被严格地划分给某一类。它的数学模型为： r n j n - ，m ( 【，七) = h 孑 i = l = l n ：酗。1 1 向 ( 1 7 ) “f ，【o ，1 】，l - ，玎，l f 七 o n ，l s f 惫 = i 3 ) 层次聚类法 层次聚类法是聚类分析中用的比较多的一种，它主要有凝聚型和分裂型两种聚类 算法1 3 5 1 。凝聚型中最常用的是凝聚型最近邻算法，其具体见算法1 2 。 算法1 2 ：凝聚型最近邻算法 i n p u t ：数据矩阵，聚类数七； o u t p u t ：每行数据所属的类别； b e g i n 1 ) 将数据矩阵每个行向量归为一类； 2 ) 找到最接近的两个行向量并合并成一类； 3 ) 重新计算新类与所有旧类问的距离； 4 ) 重复第2 步和第3 步，直到将所有行向量合并成合适的类为止。 5 ) 输出对应的聚类类别： e n d 分裂型聚类算法与凝聚型聚类算法相反，开始将样本看成一类然后逐步分裂直至 合并成合适的类为止。 4 ) 自组织聚类( s e l f b r g a n i z i n gm a pc l u s t e r i n g ，s o m ) 蚓 自组织聚类法是一种基于神经网络的分裂聚类方法，s o m 是由简单的拓扑结构 构成，其中一维和二维的s o m 最常使用。 8 基凼磁睦窆数挺曲公蚯篡i 圭 ， 笙二至结论 1 6 3 双向聚类 双向聚类这一概念最初由h a n i g a n 3 7 1 于1 9 7 1 年提出，c h e n g 和c h u r c h 于2 0 0 0 年将双聚类的概念引入到基因表达谱的分析中。基因表达数据的双向聚类是对行列同 时聚类。下面介绍几种常用的双向聚类算法： 1 ) c h e n g 和c h u r c h 算法( c c a ) 【3 8 1 c c a 算法通过优化的方法来解决双向聚类的问题，然后通过启发式算法解决约 束优化问题。c c a 算法首先定义一个阈值，若候选类大于这个阈值则丌始迭代地删 除候选类中的行和列直至候选类的均方残差值( 具体表达式见公式( 1 8 ) ) 低于阈值， 然后添加行均方残差和列均方残差最小的丌始添加到候选类中去，直至均方残差值高 于阈值彳停止添加。c c a 算法局限性在于：1 ) 受阈值的限定，若阈值设定不当直接 导致结果的不理想：2 ) 该算法要求数据矩阵中无缺失值，若存在缺失值则用随机数 替代，这会直接干扰到最后的聚类结果。 均方残差的具体表达式为： 州2 南。篆，( 一嘞饥) 2 ( 1 8 ) 其中， 铲南弘 9 ， 驴南善 。， 铲南，。篆， - - ， 与其类似的算法还有：f l o c ( f l e x i b l eo v e r l a p p c db i c l u s t e r i n g ) 算法3 9 1 、基于均 方残差的一些算法1 4 0 t 4 l 】。 2 ) s e b i ( s e q u e n t i a le v o l u t i o n a r yb i c l u s t e r ) 算法( 4 2 l s e b i 算法将演化算法应用到双向聚类中来，其算法主要是通过演化算法使得双 向聚类的均方残差值达到最小值。更有研究者在此基础上将单目标模型( s o e b ) 与 9 歪= 萱结论 基因邀睦到数握的公圭匠簋这 多目标模型( m o e b ) 应用到该算法中来使得双向聚类结果进一步改进，它们还提出 了一种新的测量双向聚类效果的评价标准，具体见文献f 4 3 】。 3 ) p a b ( p o s s i b i l i s t i ca p p r o a c ht ob i c l u s t e r ) 算法删 p a b 算法是利用概率聚类技术实现的，它主要利用每个条件下与每个基因间的关 系，但是每次只能发现一个双向聚类。它的算法通过优化目标函数来使得得到的双向 聚类的容量最大化和残差最小化。虽然算法有很快的收敛性，但是算法对参数的选择 很敏感。 4 ) s b ( s p e c 昀ib i c l u s t e r i n g ) 算法1 4 5 j s b 算法主要是通过奇异值分解来提取主成分，然后用k 哪e a n s 算法来聚类它们 的特征向量，从而得出原始矩阵的聚类信息。它是一种基于棋盘结构的双向聚类，所 有的基因和条件都会出现在双向聚类结果中，但是它没有相互重叠的双向聚类，且计 算复杂度比较高。 当然还有一些比较重要的算法如：s a m b a ( s t a t i s t i c a la l g o r i t h “cm e t h o df o r b i c l u s t e r i n g 觚a i y s i s ) 算法矧、c t w c ( c o u p i e dt w o 州a yc l u s t e n n g ) 算法f 4 刀、i s a ( i t e r a t i v e s i g n a t u r ea 1 9 0 一t h m ) 算法1 4 8 4 9 】等。 1 7 本论文的研究内容及结构安排 随着基因微阵列技术的应用越来越广泛，基因微阵列技术的发展越来越完善，当 然问题也会随之而生，研究得到的数据不断地以指数级增长，研究者们对如何有效的 处理和分析这些海量数据越来越重视。虽然海量数据分析的方法和软件层出不穷，但 是它们仍然还有许多问题存在，因此本文对其中存在的一些问题进行了改进。 基因微阵列数据的标准化算法有很多，其中最具代表性的是稳健l d w e s s 标准化 算法，但是它耗时比较严重，因此本文在稳健l 0 w e s s 的基础上提出了种更快捷且 精度与其相当的标准化算法。 缺失值的估计直是基因表达数据预处理的重要步骤，因此在j 啪e s 心t e i n i 姗估 计算法、核估计算法的基础上提出了一种在低缺失率的条件下优于其它传统算法的算 法。 双向聚类一直是基因微阵列技术中研究的热点，本文对双向聚类算法进行了详细 l o 基凶j 皇窒i 生窆数坦曲公圭丘篡这 蕴= 童绮论 的研究，提出了两种误差更小、质量更高的双向聚类算法。一个双向聚类算法是对传 统的模糊谱双向聚类的改进。另一个双向聚类算法足利用对现有双向聚类算法的研 究，提出了一种可以减小算法复杂度的新的算法。 本文结构安排如下： 第一章：介绍课题的研究背景及研究现状，提出拟解决的问题； 第二章：基于对标准化算法的研究，提出了一种改进的稳健l o w e s s 标准化算法； 第三章：基于对基因表达数掘缺失值的研究，提出了一种j a m e s - s t e i n 估计算法； 第四章：介绍模糊谱双向聚类算法及其改进的算法； 第五章：介绍一种基于基因和条件提取的双向聚类算法； 第六章：对本文所做工作的总结，并指出工作存在的问题为下一步的研究工作提 出参考意见。 第二章改进的稳健l o w e s s 标准化算法在基因微阵列中 的应用 2 1 引言 l o w e s s 标准化是种常用的基因微阵列数据的标准化算法，而稳健l o w e s s 标准 化法则是在此基础上加入稳健方法以进一步提高结果的准确性，且降低l d w e s s 标准 化法对噪声和异常值的敏感性。虽然稳健l 0 w e s s 标准化法能够取得不错的结果，但 是它相当耗时，且重复计算比较多。因此，本章对稳健l o w e s s 标准化法进行了改进， 并在此基础上提出了一种速度更快且效果与其相当的算法。 2 2 改进的稳健l o w e s s 标准化算法 本章介绍了一种改进的稳健l o w e s s 标准化算法，主要通过局部线性回归算法得 到标准化值，再通过核函数估计减少最小二乘估计的误差同时也使本算法得到的估计 值接近回归估计值。再通过格子算法减少稳健l o w e s s 标准化算法的重复计算。 一般基因微阵列是双色通道、双阵列，常用足和g j ( 1 f n ) 表示它们，分别 代表f 基因的红、绿荧光强度值。对荧光强度值进行对数处理时，其目的是更好地对 变换后的数据进行分析。利用对数，是因为它能够给出与原始数据特征相似的项，且 对数变换后的数据具有最有效的显著性检验。