（信号与信息处理专业论文）基于邻接谱分解的基因表达谱数据分类研究.pdf

安徽大学硕士学位论文摘要 摘要 。 进入2 1 世纪以来，科学技术高度发达，人们的生活水平不断提高，人类越 来越渴望理解自身的起源过程，探索生命的奥秘。随着现代生物技术的不断发展， 生物信息学近年来获得了突破性进展，对基因芯片技术的研究也日趋成熟，基因 表达数据的获取变得越来越容易，得到的数据也越来越准确。随着人们不断对公 布的大量d n a 序列进行分析和数据挖掘，基因的神秘面纱也随之揭开。对肿瘤 基因表达谱进行深入研究，可以了解肿瘤的发生发展机制，有助于人们发现新的 疾病亚型，找出肿瘤早期的诊断指标和治疗靶点，提高复杂疾病诊断的准确率， 增强临床治疗肿瘤的有效性。但是由于基因表达谱数据具有高维度，小样本的特 点，远远超出传统分析方法所能处理的范畴，现有的相关数据分析和数据挖掘方 法已经不能满足实际的需要，如何对其进行有效的处理、挖掘、分析和理解成了 生物信息学研究的瓶颈。为此，研究人员将对肿瘤基因表达谱数据的分析从传统 的统计学方法逐渐过渡到运用机器学习的方法上，成为生物信息学近年来研究的 热点。 本文基于生物信息学理论和谱图理论，运用模式识别方法和计算机技术，将 反映图结构的特征表示引入到基因表达谱数据的分类中，研究了基于谱图理论的 肿瘤基因表达谱数据的特征提取及分类，并对数据的分析结果，算法的性能进行 了论证。主要研究内容有： 1 详细介绍了基因表达谱的基础知识，对近年来基因芯片表达数据的分类 分析方法进行了综述，在分析基因表达谱数据特点的基础上，对分类的研究背景， 研究现状，研究意义，现阶段存在的问题以及未来的研究方向进行了探讨。 2 提出了一种基于邻接矩阵分解的肿瘤亚型特征提取及分类方法，首先对 肿瘤基因表达谱数据以高斯权构造邻接矩阵，然后进行奇异值分解，最后将分解 得到的特征向量作为分类特征输入支持向量机进行分类识别。对白血病的两个亚 型采用留法进行试验，取得了良好的效果。 3 结合主分量分析方法，对基因表达谱数据样本点构造高斯权邻接矩阵， 使样本点具有空间结构信息，s v d 分解后，采用特征记分准则进行筛选，找出 安徽大学硕士学位论文 基于邻接谱分解的基因表达谱数据分类研究 最大限度区分肿瘤样本与正常样本的主分量作为样本特征，输入k n n 分类器进 行分类。通过对白血病和结肠癌表达谱数据进行实验，证明了该方法的可行性与 有效性。 关键词：生物信息学；基因表达谱数据；分类；邻接图：主分量分析 i i 安徽大学硕士学位论文 a b s t r a c t a b s t r a c t i nt h e21s tc e n t u r y , s c i e n c ea n dt e c h n o l o g yi sh i g h l yd e v e l o p e d ，p e o p l e sl i v i n g s t a n d a r di sg r e a t l yi m p r o v e d ，m o r ea n dm o r ep e o p l ea r ee a g e rt ol e a r nt h e i ro w n o r i g i np r o c e s s ，e x p l o r i n gt h es e c r e to fh u m a n sl i f e w i t ht h ec o n t i n u o u sd e v e l o p m e n t o fm o d e mb i o l o g i c a lt e c h n o l o g y , b i o i n f o r m a t i c sg e tab r e a k t h r o u g hi nr e c e n ty e a r s ， r e s e a r c ho ng e n ec h i pt e c h n o l o g yi sb e c o m i n gm a t u r e ，a c q u i r eg e n ee x p r e s s i o nd a t ai s b e c o m i n gm o r ea n dm o r ee a s i l ya n dm o r ea n dm o r ea c c u r a t e a st h ed n as e q u e n c e h a sb e e nc o n s t a n t l yp u b l i s h e da n da n a l y s i s ，t h ev e i lo fg e n ei su n c o v e r e d w i t ht h e d e e ps t u d yo nt u m o rg e n ee x p r e s s i o np r o f i l e s ，c a n h e l pp e o p l eu n d e r s t a n d m e c h a n i s m so ft u m o rd e v e l o p m e n t ，d i s c o v e rn e w s u b t y p eo fd i s e a s e ，i d e n t i f yc a n c e r e a r l yd i a g n o s t i cm a r k e ra n dt h e r a p e u t i ct a r g e t ，i m p r o v et h ed i a g n o s i sa c c u r a c yo n c o m p l e xd i s e a s e ，a n de n h a n c et h ee f f e c t i v e n e s so fc l i n i c a lt r e a t m e n t h o w e v e r ，d u et o t h ec h a r a c t e r i s t i c so fh i g hd i m e n s i o n sa n ds m a l ls i z eo fg e n ee x p r e s s i o nd a t a , i th a s f a rb e y o n dt h eh a n d l es c o p eo ft r a d i t i o n a la n a l y s i sm e t h o d ，t h ee x i s t i n gm e t h o d sc a n n o tm e e tt h ep r a c t i c a ln e e d s ，h o wt ot r e a t m e n t ，m i n i n g ，a n a l y z e ，a n di n t e r p r e tg e n e e x p r e s s i o nd a t ae f f e c t i v e l yh a sb e c a m et h eb o t t l e n e c ko fb i o i n f o r m a t i c s t h e r e f o r e ， t h er e s e a r c h e r sh a s g r a d u a l l yt r a n s i t i o ng e n ee x p r e s s i o nd a t aa n a l y s i sf r o mt h e t r a d i t i o n a ls t a t i s t i c a lm e t h o d st om a c h i n el e a r n i n gm e t h o d s ，t h i sh a sb e c o m et h e h o t s p o ti nb i o i n f o r m a t i c sr e s e a r c ht h e s ey e a r s t h i st h e s i si sb a s e do nb i o i n f o r m a t i c sa n ds p e c t r u md i a g r a mt h e o r y , u s i n g p a r e mr e c o g n i t i o nt e c h n o l o g ya n dc o m p u t e rs c i e n c e ，t h ef e a t u r e st h a tw i l lr e f l e c t e d t h eg r a p hs t r u c t u r e si si n t r o d u c e di n t ot h ec l a s s i f i c a t i o no fg e n ee x p r e s s i o nd a t at o s t u d yt h ef e a t u r ee x t r a c t i o na n dt h ec l a s s i f i c a t i o no ft u m o rg e n ee x p r e s s i o n , t h ed a t a a n dt h er e s u l tw e r ew e l l a n a l y s i s ，a n dt h ep e r f o r m a n c eo ft h ea l g o r i t h mw e r e d e m o n s t r a t e d 1 1 1 em a i nr e s e a r c hc o n t e n t s ： 1 i n t r o d u c e dt h eb a s i ck n o w l e d g eo fg e n ee x p r e s s i o nd a t a , s u m m a r i z e dt h e c l a s s i f i c a t i o na n a l y s i sm e t h o d so fg e n ee x p r e s s i o nd a t ai nr e c e n ty e a r s ，b a s e do nt h e c h a r a c t e r i s t i c so fg e n ee x p r e s s i o nd a t aa n a l y s i s ，d i s c u s s e dt h eb a c k g r o u n d ，s t a t u s ， i i i s i g n i f i c a n c e ，e x i s t i n gp r o b l e m sa n df u t u r ed i r e c t i o no fc l a s s i f i c a t i o nr e s e a r c h 2 p r o p o s e dac a n c e rs u b t y p ef e a t u r ee x t r a c t i o na n dc l a s s i f i c a t i o nm e t h o db a s e d o nt h e a d j a c e n c ym a t r i xd e c o m p o s i t i o n , u s i n gg a u s s i a nd g h to nt u m o rg e n e e x p r e s s i o nd a t at ot e c t o n i ca d j a c e n c ym a t r i xf i r s t ，t h e ns i n g u l a rv a l u ed e c o m p o s i t i o n , p u td e c o m p o s e de i g e n v e c t o ra sc l a s s i f i c a t i o nf e a t u r ei n t os u p p o r tv e c t o rm a c h i n e st o c l a s s i f i c a t i o na n dr e c o g n i t i o n t h ee x p e r i m e n tb yu s i n gl e a v eo n eo u tc r o s sv a l i d a t i o n o nt w ol e u k e m i as u b t y p e sa c h i e v e dg o o dr e s u l t s 3 c o m b i n et h ep r i n c i p a lc o m p o n e n ta n a l y s i sm e t h o d ，u s i n gg a u s s i a n r i g h t t e c t o n i ca d j a c e n c ym a t r i xo ng e n ee x p r e s s i o nd a t ao ft h es a m p l ep o i n t s ，m a k et h e s a m p l ep o i n t sh a st h ei n f o r m a t i o no fs p a c es t r u c t u r e ，s i n g u l a rv a l u ed e c o m p o s i t i o n , u s i n gf e a t u r es c o r i n gc r i t e r i at of i n do u tt h em a i nc o m p o n e n tt h a tc a nu t m o s t d i s t i n g u i s h e dt u m o rs a m p l e sa n dn o r m a ls a m p l e s ，p u tt h i sc o m p o n e n ta ss a m p l e c h a r a c t e r i s t i c si n t ot h ek n nc l a s s i f i e r t h r o u g ht h e e x p e r i m e n to nl e u k e m i aa n d c o l o nc a n c e re x p r e s s i o nd a t ap r o v e dt h a tt h i sm e t h o di sf e a s i b l ea n de f f e c t i v e k e y w o r d s ：b i o i n f o r m a t i c s ；g e n ee x p r e s s i o nd a t a ；c l a s s i f i c a t i o n ；a d j a c e n c y g r a p h ；p r i n c i p a lc o m p o n e n ta n a l y s i s i v 安徽大学硕士学位论文 绪论 第一章绪论 基因表达谱主要描绘的是特定细胞或组织在特定条件下的基因表达种类和 丰度信息。随着基因微阵列技术的日益发展，基因表达谱数据的获取已经变得越 来越快捷可靠。由于生物体内细胞种类繁多，且基因表达具有时空差异性，因此， 相较于基因数据，基因表达谱数据更为复杂，目前已有的数据挖掘方法已经不能 满足实际的分析需要。如何采集，存储，分析处理这些作为d n a 信息载体的大 量复杂数据，特别是怎样从这些异常复杂，种类繁多的表达数据中提取出有价值 的生物信息，是获取这些数据的最终目的，也是当前生物信息学研究中迫切需要 解决的一个重点课题。 1 1 生物信息学 1 1 1 生物信息学简介 生命系统的运转机制十分复杂。长久以来，科学家们一直在对生命的本质和 基本过程进行研究，但千百年来都未能有人窥得其中的奥秘。近年来，由于人类 基因组计划的启动，基因测序工作取得了飞速的发展，d n a 序列数据正呈指数 级增长，相比之下，人类相关的生物学知识增长却十分缓慢。随着科学技术的不 断发展，大量的计算机和数理科学工作者转入生命科学领域进行研究，一门结合 了计算机科学，人工智能，数学等学科的新兴科学一生物信息学应运而生【1 1 。 上个世纪8 0 年代初，华裔博士h w aa l i r a 将生物学与计算机科学结合，开 展了对该领域的研究，并命名为“c o m p b i o ，而后慢慢演变为“b i o i n f o r m a t i c s 。 至1 9 8 7 年，“生物信息学”这一概念被正式提出，依托生物学，计算机科学以及 数理学科的交叉运用，生物信息学很快得到了蓬勃的发展，近年来广泛应用于生 物医学基础研究，基因序列的对比与分析，分子的进化与演变观察，蛋白质结构 的比对和预测，疾病的诊断与分型以及药物筛选等方面【2 卅。 广义上来说，生物信息学主要是以生物学，医学和遗传学数据为研究对象( 如 核苷酸，蛋白质，d n a 序列，心电图等) ，以应用数学为理论基础，以信息技术， 人工智能为处理手段，以计算机软硬件和互联网络为操作工具，通过对实验数据 进行获取、加工、存储、检索和分析，从而明确其生物意义的交叉科学。从狭义 安徽大学硕士学位论文 基于邻接谱分解的基因表达谱数据分类研究 上说，由于当下生物信息学发展的核心驱动力源于分子生物学，研究大多集中于 基因，蛋白质，核苷酸和氨基酸序列的采集，处理，分类和检索，从某种意义上 来说，生物信息学也可以描述为：将计算机与数学结合并应用于生物大分子信息 的储存，管理，注释，加工和分析，进而对研究对象的生物学意义加以解释的交 叉科学。 1 9 9 9 年，国际人类基因组计划正式启动，中国作为六个正式成员国之一， 承担着基因组测序任务的1 ，主要目标是对第三号染色体短臂上的3 0 0 0 万碱基 对进行测定。2 0 0 1 年春，科学家们发布了第一份人类基因组序列图谱，即人类 基因组的工作草图。如今，人类基因组图谱已经逐渐完善，这意味着对基因组的 研究将由基因序列的测定全面转入到对海量信息数据的提取与分析阶段。基因组 研究的最终目的就是完成生物学问题到数字信号处理的转化问题。 1 1 2 研究意义 恶性肿瘤，是危害人类生命健康的杀手之一，每年地球上约有6 0 0 万人死于 肿瘤疾病，并有1 0 0 0 万人饱受这种疾病所带来的痛苦。据统计，每年有5 0 多万 美国人死于癌症，约1 4 万新癌症病例被确诊【5 1 。据我国卫生部的资料表明，中 国每年新增癌症患者约1 8 0 万，死亡人数为1 6 0 万人，并且以每年1 1 6 的速 度递增，这相当于每4 5 个死亡者中就有一个死于癌症，居死亡原因之首。在过 去2 0 年的时间里，生活在城市的肿瘤患者人数逐年上升并呈现低龄化趋势，死 亡率高居第二位，预防和治疗肿瘤是全世界科学家关注的焦点。 一般来说，肿瘤是由于分子内某些基因突变所致，由此对其它基因的表达造 成了影响，造成细胞内蛋白质分子结构改变，产生了病理学上的差异，在临床诊 断中被确定为不同的类型【6 】。医学家最初是从组织形态学角度出发对肿瘤类型进 行划分，到目前为止，已经发现超过3 0 0 种类型的肿瘤，若加上相同类型不同亚 型则数量更多，肿瘤类型的准确诊断是临床治疗的关键，也是临床上的一个难点， 许多分属不同类别的肿瘤，在形态学上极其相似，临床症状也较为相仿，但却需 要使用不同的方法进行治疗。正因为肿瘤的发生发展机制比较复杂，所以科学家 们仍在对其进行不断地研究探索。肿瘤基因表达谱数据具有样本小而维数高，冗 余噪声多而信息基因少的显著特点，记录的是所测细胞中所有可测基因的表达水 平，但是在这些庞大的数据中，只有少数基因才真正包含与样本分类相关的信息。 2 安徽大学硕士学位论文绪论 如何从这些成千上万的数据中有效分析并且提取出样本的分类特征，一直是肿瘤 基因表达谱数据挖掘中的难点所在，有待于人们对其进行进一步的探索用。 从信息学角度出发，以现代数据挖掘技术为主要手段对肿瘤基因表达谱进行 分析具有重要意义：( 1 ) 目前的肿瘤分类主要是依赖于医务工作者临床对肿瘤症 状的经验判断，具有高度的主观性，准确率不高，缺乏相关的数据支持；( 2 ) 建 立于基因表达谱基础之上的肿瘤分型和分类可以帮助研究人员对肿瘤做出早期 预测，从而实现肿瘤类型的准确诊断，为肿瘤的临床治疗提供重要依据；( 3 ) 医 学家可以通过跟踪基因表达谱的变化，从而区分形态，症状相似的肿瘤，制定配 套的最佳治疗方案。 2 0 0 6 年伊始，以绘制肿瘤致病基因组为目标的肿瘤基因组计划开始付诸实 施，中国也是该项计划的重要成员之一。此计划旨在发现出肿瘤的发生与发展机 制，揭示基因突变的过程，使人们及早发现肿瘤基因的分子标记和药靶目标，为 临床提供可靠的治疗方案，从而将人类战胜肿瘤的梦想变成现实。 总之，基于肿瘤基因表达谱的肿瘤分类研究对探索肿瘤的发生发展机制具有 重要意义，为肿瘤的分子预防，诊断，治疗开辟了新的途径，有助于实现肿瘤的 个性化治疗，是一项十分重要的课题。 1 2 谱图理论 谱图理论( s p e c t r a lg r a p ht h e o r y ) 源自2 0 世纪五、六十年代，是图论研究 的重要组成之一，广泛应用于图像编码，模式识别，遥感图像，生物医学图像等 领域。谱是指一幅图的邻接矩阵或l a p l a c e 矩阵的特征值集合【s , 9 1 。谱图理论是通 过图定义的矩阵的谱，运用几何和代数理论在连续空间和离散空间之间建立联 系，从而进一步挖掘图中所包含的信息【l o 】。谱图理论主要是利用成熟的代数理 论与方法，结合图的拓朴结构性质、组合数学理论和矩阵理论对图的结构性质、 图的各种不变量( 如色数，度序列，直径，连通度等) 之间的关系展开研究。 谱图理论主要以邻接谱，l a p l a c e 谱，q 谱，c 谱，s 一谱等为研究对象，其 中对邻接谱，l a p l a c e 谱的研究最为普遍。近年来，谱图理论呈现出丰富多彩的 形式，并且各种不同定义的谱之间存在着相互联系【1 1 1 。 3 安徽大学硕士学位论文基于邻接谱分解的基因表达谱数据分类研究 1 2 1 谱图理论的发展 图的邻接谱研究最初源于量子化学研究领域，有着相当长时间的历史，经过 几十年的发展，逐渐形成了较为完善的理论体系。1 9 3 1 年，e h t i c k e l t l 2 增次使 用图的特征值来表示特定电子的能量级，其中特征值的最大值即谱半径表示能量 级的最大值，谱图半径的上界即表示能量级的上界，这是谱图理论的最初形态。 但是直到很多年后，人们才逐渐意识到h t i c k e l 模型与谱图的数学理论之间的联 系，由此展开了对谱图理论的研究。1 9 6 9 年，h s a c 心1 3 1 和a j h o f f m a n 1 4 蝴确 提出研究图的邻接谱，并针对此进行了系统的理论研究；1 9 7 1 年，d c v e t k o v i 6 1 5 】 在他的博士论文中系统地总结了其基本理论和基本研究方法；十年后， d c v e t k o v i 6 ，m d o o b 与h s a c h s 合著了( ( s p e c t r ao fg r a p h s ) ) 0 6 】一书，书内参考了 1 9 6 0 年到1 9 7 8 年之间的5 6 4 篇文献，包含了几乎所有的关于图的邻接谱的研究 结论；为了对文献【1 6 】进行补充，由d c v e t k o v i 6 ，m d o o b ，i g u t m a n 和a t o r g a 童e v 合著的( ( r e c e n tr e s u l t si nt h et h e o r yo fg r a p hs p e c t r a ) ) t 1 7 1 二于：19 8 8 年出版，该书 提供了1 9 7 8 1 9 8 4 年问7 0 0 多篇来自于数学和化学领域的相关文献，回顾了邻接 谱研究的最新成果，并且，这本书还收录了物理、机械工程、地理和社会科学等 方面的文献；1 9 9 7 年d c v e t k o v i 6 ，e r o w l i n s o n 和s s i m i 6 合著的( ( e i g e n s p a c e so f g r a p h s ) ) 1 8 1 ，n b i g g s 的 ( a l g e b r a i cg r a p ht h e r o y ) ) 以及19 7 9 年c d g o d s i l 的 a l g e b r a i cc o m b i n a t o r i c s ) ) t i g j ) l 本书中也对图的邻接谱作了详尽的介绍。关于 图的邻接谱理论的最新研究成果，1 9 9 5 年出版的( ( s p e c t r ao fg r a p h s ) ) 第三版的 附录中有详细的叙述。 1 2 2 相关概念 谱图理论是图论研究的一个重要方向，主要研究图的谱分布与图的结构之间 的对应关系，是属于组合矩阵论的一部分。图的邻接矩阵是谱图理论中的一个重 要概念，邻接图的特征值，称为图的邻接谱。下面介绍一些图的相关概念： 1 图 常用图有有向图、无向图、完全图、稠密图和稀疏图等。 4 安徽大学硕士学位论文 绪论 d 1 图1 - 1 有同图和无同图 f i g 1 - 1d i r e c t e dg r a p ha n du n d i r e c t e dg r a p h 图l - 1 中，q 是有向图，q = 以，仁。 ) ，顶点集k = h ，吃，v 3 ，v 4 ，边集 巨= ( h ，屹) ，( h ，吃) ，( 屹，屹) ，( 屹，h ) ) ；砬是无向图，d 2 = ( 砭， 岛) ) ，顶点集 = h ，屹，v 3 ，v 4 ，v 5 ，边集易= ( m ，吃) ，( m ，) ，( 屹，屹) ，( 吃，吩) ，( 嵋，k ) ，( 屹，吃) ) 。刀 表示顶点数目，e 表示边或弧的数目。对于无向图，e 的取值范围是0 到 n ( n - 1 ) 2 ，有刀( 刀一1 ) 2 条边的无向图称为完全图；对于有向图，p 的取值范围 是0 至：l j n ( n - 1 ) ，有n ( n - 1 ) 条边的有向图称为有向完全图。当一个图接近完全图 时，称为稠密图；当一个图含有较少边数，即p “n ( n 一1 ) ，则称为稀疏图。 n = 3e - - - - t i ( n - 1 ) 2 = 3 完全图 n = 3e = n ( n - 1 ) 2 = 6 有向完全图 n = 4e = n r n - 1 ) 2 = 6 稠密图 n = 4e = 3 稀疏图 图1 2 各种图的表示 f i g 1 - 2e a c hl 【i n do f g r a p he x p r e s s i o n 5 安徽大学硕士学位论文基于邻接谱分解的基因表达谱数据分类研究 2 矩阵 谱图理论的主要研究的对象是图的邻接谱和l a p l a c e 谱。 对于有向图d = y ，e ) ，设顶点集y = 啊，v 2 ，屹) ，有向图d 的邻接矩阵 彳( d ) = ( 吩) 脚，其中吻= 聊 k ，吩) ，有向图d 和它的邻接矩阵是一一对应的。若 d 是无向图，则有边( u _ ) 当且仅当有边( 吩u ) 。显然，么( d ) 是对称矩阵。 若我们考虑的有向图d = 矿，e 是聊 k ，_ ) 1 的图，任意e = q ，e 。 ，则 图d 就和一个甩阶邻接矩阵( o ，1 ) 矩阵彳( 功= ( ) 删建立一一对应关系。 i 文单 旷骺燃 可见，我们给出一个( 0 ，1 ) 方阵么，也对应一个有向图d ( 彳) ，d ( 彳) 叫方 阵么的伴随有向图。 设g = y ，e ) ，顶点集v = v l ，屹 ，边集e = q9 * 9 e r a ) ，关联矩阵 b = ( 6 j f ) 。，i = l ，疗，j = l ，所，这里 = g 慧 设g = ( y ，e ；w ) 为玎阶带权无向图，将形定义为在e 上的非负权值函数， j 2 z eee 的权值为形( p ) 。其邻接矩阵彳( g ) = ( 吩) 为，z 阶对称矩阵，其元素定义为： 若 k ，_ ) e ，则嘞= 形( k ，吩) ) ，否则，吩= o 。记d ( g ) = 旃昭 儡，吐，以 为 图g 的度对角矩阵，其中4 = _ 以 吩，冲矿( u ，_ ) ) 为点的度。图g 的l a p l a c e 矩阵定义为三( g ) = d ( g ) 一么( g ) ，三( g ) 为对称半正定矩阵。 3 谱 设方阵a = ( 呸，)，c 为刀阶方阵，a 为彳的特征值，当存在拧维非零列 、v ，n x n 向量x ，使得 ar ：a y( 1 1 ) 6 安徽大学硕士学位论文绪论 那么x 就称为与特征值允相应的么的一个特征向量。 由( 1 1 ) 式可以看出，a 是_ ( a ) = d e t ( z x 一彳) 多项式的根，其中，厶是刀 阶单位方阵，邑( 允) 是彳的特征多项式，也是关于九的”次多项式。 根据高斯定理，特征方程硝( a ) = o 有刀个根，即 ，如，九。 ，如，九不 一定互异，我们把重集 ，如，九) 称为方阵么的谱，记为s p e c a 或 s p e c a = 骶r 1 2 麓 2 ) 其中， ，九，九互异，1 7 ，是 的代数重数，将丑所对应的特征向量和零向 量组合在一起，即构成了与九相应的根子空间，这个子空间是一个线性子空间， 也是魃= a x 所决定的齐次方程的解空间。万一朋础魄厶一a ) 是此空间的维数， 称为特征值九的几何重数。 此外，谱图理论中还包含许多图的重要概念，如图的连通度，色数，度序列 二部宽( b i p a r t i t ew i d t h ) 、最大割( m a x c u t ) 、等周数等，这些不变量反映了图 的结构和性质，广泛应用于量子化学、物理、计算机科学、通信网络及信息科学 等研究领域。 1 2 3 谱图理论在基因表达谱数据中的应用 利用基因表达谱数据对肿瘤进行分类是目前生物信息学研究的热点问题，对 其深入探索有助于人类掌握与自身疾病相关的基因信息，如基因的功能、结构、 基因间的调控关系和疾病易感基因的定位等，从而促进肿瘤的预测，临床诊断和 有效治疗。 基于基因表达谱数据的肿瘤识别研究是通过d n a 微阵列实验获取基因表达 数据，对表达有差异的样本基因做出分析，寻找出与病变组织密切相关的基因， 从而对样本类型做出判断与识别。如今在肿瘤治疗前，越来越多的医学家开始运 用这项技术来确定肿瘤类型，其识别的成功与否将对治疗效果产生直接的影响， 因而迫切需要建立一种快速、准确的肿瘤类型识别方法。这是生物信息学前沿领 域的一个重要课题，也是一个至今尚未得到有效解决的问题。 7 安徽大学硕士学位论文 基于邻接谱分解的基因表达谱数据分类研究 由于基因表达谱数据具有高维度、小样本的特点，给肿瘤的类型识别带来了 新的挑战，针对这一问题，本文将谱图理论引入到肿瘤基因表达谱的类型识别中， 将样本点映射到高维空间，构造结构图，从而使无结构信息的数值变成有结构信 息的图结构，通过描述图的谱及对应的特征向量等固有属性信息，将肿瘤类型识 别问题转化为对图结构相似性的分析，挖掘出图结构的特征，并应用谱图理论获 取图的特征信息，进而实现对样本类型的预测和识别。 基因表达谱中的样本是由一个庞大的数字序列构成的，通常可以用一个高维 向量表示这个数字序列，从而一个样本就可以看作是高维空间中的一个点。当使 用传统的分类方法对这些高维空间中的点进行分类时，将会存在维数灾难问题。 而谱图理论对于空间结构的差异尤为敏感，所以本文将基因表达谱数据构造成具 有不同的空间分布和空间结构的点集，进而挖掘其结构特征进行分类识别，将对 基因表达谱的分析建立在谱图理论之上拥有十分重要的研究价值。此外，针对基 因表达谱的高维度特点，谱图方法在构图时只需对各维数据进行较为简洁的运 算，大大降低了运算复杂度。 谱图理论也可以应用于分析不同种类间基因的表达谱差异。例如，将同属于 某类的样本构造l a p l a c e 图，当用同类的样本去替换图中的任意一个样本时，图 的结构会在一定的范围内保持稳定，并不会发生明显的变化，反之，图的结构将 会发生改变，使用特征点匹配方法对这种改变进行检测，便可以完成对未知样本 的识别工作；从无监督学习的角度看，也可以将不同类别的基因表达谱数据作为 一个整体构造l a p l a c e 图，然后运用图割的方法将整体图划分得到各个不同的子 图以达到样本分离的效果；或者构图后，运用非负矩阵f 2 0 2 2 】分解得到低维度( 几 维至十几维) 的特征表示，结合相关的分类聚类算法便能够对样本类别进行划 分；将l u 分解应用于图的邻接矩阵，使样本点的特征信息得到凸显，冗余信息 得到有效抑制，此方法可以对多种类型的数据集进行识别，且具有对噪声不敏感， 鲁棒性较好的特点。 1 3 本文的研究内容及组织结构 本文将生物信息学理论与谱图理论有机结合，有针对的研究了肿瘤基因表达 谱数据的特征提取及分类问题。具体来说，就是将基因数据表达谱赋以结构性质， 以图的代数不变量和图本身的不变量为基础，结合邻接谱方法，分析研究了肿瘤 8 安徽大学硕士学位论文 绪论 基因表达谱数据集在高维空间中的特征表示与其内在所蕴含的分类信息之间的 联系。 本文基于谱图理论，将基因表达谱数据映射至高维特征空间，构造不同样本 类别结构图的邻接矩阵，达到降低数据维度，获得特征度量信息，正确分类样本 的目的，使得基因表达谱数据由离散点问题转化为结构图问题。此方法的优点在 于：( 1 ) 谱图方法只要对个各个样本的分量进行较为简洁的构图运算，后续处理 只与样本点及连接样本点的边有关，避免了维数灾难；( 2 ) 谱图方法对基因表达 谱数据中的噪声不是十分敏感，具有较高的鲁棒性。 本文章节安排如下： 第一章：绪论 本章对生物信息学的概念做了一个简单的介绍，阐明了研究的必要性以及研 究意义。综述了谱图理论的发展过程，列出了谱图理论相关的基本概念，阐述了 谱图理论应用于基因表达谱数据的可行性，概括了整篇文章的研究理念和创新之 处。 第二章：基因表达谱数据相关研究 立足于本文的研究中心一基因表达谱数据，详细介绍了基因表达谱数据是如 何采集制备，并通过相应的预处理转化为进行数据挖掘所必要的格式。叙述了基 因表达谱数据的特点，阐述了目前国内外的研究现状，并在此基础上分析了现阶 段存在的问题，介绍了基因表达谱数据研究未来的发展方向。 第三章：基于邻接矩阵分解的肿瘤亚型特征提取方法 本章尝试着将一种基于邻接谱分解的算法应用于肿瘤基因表达谱数据的分 类上。首先对肿瘤基因表达谱数据构造高斯权邻接矩阵，将所有样本点抽象到特 征空间中，实现了点到图的构造转变，接着对邻接矩阵进行奇异值分解，获得样 本点的特征表示，最后将得到的特征信息作为分类特征输入支持向量机进行分类 识别。对白血病两个亚型( a l l 与a m l ) 的基因表达谱数据进行了留一法实验， 较传统方法而言，该方法的准确率大范围提高，而运算复杂度却大幅度下降，从 而证明了本方法的优势及有效性。 第四章：基于邻接谱主分量分析的肿瘤分类方法 本章提出一种基于图的邻接谱主分量分析方法分类肿瘤基因表达谱数据。该 9 安徽大学硕士学位论文基于邻接谱分解的基因表达谱数据分类研究 方法将p c a 主分量分析方法与基因表达谱数据有机结合，采用特征记分准则对 s v d 分解后的向量则进行筛选，找出最大限度区分肿瘤样本与正常样本的主分 量作为样本特征，输入k n n 分类器进行分类，实现了分类结果的可视化效果。 使用白血病两个亚型( a l l 与a m i ，) 及结肠癌数据进行实验。实验结果证实本 算法具有较高的分类准确率和鲁棒性。 第五章：总结与展望 本章作为对全篇的结章，对本文的指导理念，研究内容，创新思想以及目前 存在的问题进行了总结，给出了今后研究的可行方向。 1 0 安徽大学硕士学位论文 基因表达谱数据相关研究 第二章基因表达谱数据相关研究 2 1 基因芯片技术 基因芯片，又称为基因芯片技术，d n a 微阵列技术，寡核苷酸芯片，d n a 芯片，d n a 微阵列芯片或表达谱芯片。这一概念出现在上个世纪8 0 年代，由 f o d o r 【2 3 】等研究人员于1 9 9 1 年在( s c i e n c e ) ) 杂志上提出。同年，a f f y m e t r i x 公 司使用半导体平板照相技术，在l c m 2 左右的玻璃片上以原位合成寡核苷酸的序 列片段，制造大规模集成g e n e c h i p ，由此，世界上第一张基因芯片诞生。 基因芯片技术提供了一种高通量和系统性的研究手段。在实际的研究中，基 因芯片技术常被许多肿瘤学家用来分析和比较肿瘤组织与正常组织之间的差异， 以期发现肿瘤病变过程中的分子机制，实现肿瘤的分子诊断，个体化和靶向治疗。 使用基因芯片技术对基因表达谱数据进行分析和建模，已经成为当今生物信息学 的发展趋势 2 4 , 2 5 。 基因芯片是结合多种不同学科和技术产生的，是典型的多学科，多技术的结 晶，它涉及物理、化学、材料科学、分子生物学、电子工程、机械工程、统计学 和计算机科学。其特点是高通量、微型化、自动化、低成本、高度并行，克服了 传统生物实验的缺点，为从分子水平探索细胞结构与功能的变化开拓了全新的空 间，为研究生命本质问题提供了极大的便n t 2 6 j 。利用基因芯片对组织细胞中的 基因表达水平进行跟踪监测，可以有助于鉴别分类已知的肿瘤，还可以预测发现 新的肿瘤亚型，为肿瘤在分子层面上的研究提供了有力的科学依据。每进行一次 基因芯片实验得到的信息数据都是海量的，随着基因芯片技术的不断进步和测试 仪器的不断更新，将会有越来越多的基因数据被人们所掌握，其数据规模也将日 趋庞大。因此，能否对基因表达谱数据进行准确高效的挖掘分析，使其具有可解 释的生物学意义，将成为基因芯片技术发挥其优势的关键所在。 安徽人学硕士学位论文基于邻接谱分解的基因表达谱数据分类研究 2 2 基因表达谱数据 2 2 1 基因表达谱数据的制备采集及预处理 高度的特异性和敏感性是基因芯片的特点之一，它可以对细胞中上千个 m r n a 拷贝的转录情况进行监测，与用单探针分析m r n a 的点杂交技术不同的 是，基因芯片的探针呈阵列形式，使用了大约2 0 对寡核苷酸探针来监测每一个 m r n a 的转录情况。每对寡核苷酸探针都包含一个与所要监测的m r n a 完全吻 合和一个不完全吻合的探针，它们的区别在于其中间位置的核苷酸不同。这种成 对组合的探针设计可以将非特异性杂交和背景信号的水平减少到最低，由此确定 那些低强度的m r n a 。 1 9 5 5 年，美国斯坦福大学率先成功研制e d n a 并将其应用于基因表达分析 中。方法是将细胞或组织中特定的m r n a 提取出来，逆转录成e d n a ，使用自 动点样装置( 阵列仪，a r r a y e r ) 将通过p c r 扩增技术获得的基因片段制成 5 0 0 n 2 0 0 0 b p 长度的探针，按阵列的形式直接点样到事先准备好的玻片或膜尼龙 上以保存备用。每一个点样只包含一种特定的e d n a 分子，这样就制成了e d n a 微阵列。通常情况下，点样直径约为5 0 1 5 0 o n ，点样密度不超过1 0 0 0 0 点c i n 2 比原位合成的寡核苷酸芯片低。 为了从d n a 微阵列中得到基因表达水平，首先选取来自相同组织不同类别 的样本，如正常组织与肿瘤组织，选定一种称为实验样本，另一种样本相应的就 称为参考样本。在逆转录过程中，分别用不同的红，绿荧光基团标记实验样本和 参考样本的m r n a ，并将它们混合，与探针阵列进行杂交，适当洗脱后，用荧 光扫描仪对探针进行监测，获得芯片中对应于不同荧光的荧光强度图像，通过专 用的图像软件进行分析，得到芯片上每个点的红，绿荧光强度( c y 5 和c y 3 ) ， 其比值( c y 5 c y 3 ) 就是我们需要的该基因在实验样本中的表达水平。 经过上述步骤得到的数据反映的是样本基因的相对表达水平，即实验样本与 参考样本之间红绿荧光信号强度的比值( r a t i o ) ，这是一个无量纲的数值。当对 r a t i o 值进行计算时，如果参考样本的信号强度很小，那么r a t i o 值便会很大。如 果一个基因谱中仅仅存在单个特别大的r a t i o 值，这往往是由于噪声造成的，此 1 2 安徽大学硕士学位论文 基因表达谱数据相关研究 类数据很可能是无意义的，常被视为不确定的或异常点，进行后续分析时要根据 需要确定是否保留以及如何纠正其值。 表2 1 基因表达数据 t a b l e2 1g e n ee x p r e s s i o nd a t a 表2 1 为样本文件中的基因表达数据，按照样本和基因的顺序排列成数据集。 其中各行的第一列表示的是基因的标识，各列的第一行表示的是样本的标签，用 于描述样本的属性内容。标识和标签可以是数字，也可以是字符串，其余单元格 是基因表达数据值。例如，第三个基因在第二个a m l 的样本表达值是2 0 0 2 6 1 ， 若数据丢失，则将其设定为空值。 2 2 2 基因表达谱数据的特点 虽然近年来基于基因表达谱的肿瘤识别与分类算法有了长足的发展，但是仍 然面临许多问题：( 1 ) 实验过程中由于实验环境和实验手法的不同，会产生噪声 和异常值，并且在数据处理过程中也难免会产生误差和标记错误，如何设计鲁棒 性强的去噪方法是第一个要面临的难题；( 2 ) 面对庞大的基因表达谱数据，以及 所体现出来非线性特点，传统的机器学习( m a c h i n el e a r n i n g ，m l ) 方法的局限 性逐渐显现，无法很好地发挥作用，如何发展高效实用的基因表达谱数据处理方 法，对肿瘤的临床诊断和治疗具有十分重要的意义；( 3