(计算机应用技术专业论文)单基因扰动的自适应灰关联聚类算法.pdf_第1页
(计算机应用技术专业论文)单基因扰动的自适应灰关联聚类算法.pdf_第2页
(计算机应用技术专业论文)单基因扰动的自适应灰关联聚类算法.pdf_第3页
(计算机应用技术专业论文)单基因扰动的自适应灰关联聚类算法.pdf_第4页
(计算机应用技术专业论文)单基因扰动的自适应灰关联聚类算法.pdf_第5页
已阅读5页,还剩46页未读, 继续免费阅读

(计算机应用技术专业论文)单基因扰动的自适应灰关联聚类算法.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

单基因扰动的自适应灰关联聚类算法 单基因扰动试验的 自适应灰关联聚类算法 摘要 随着人类基因组计划的完成,对基因功能的揭示成为后基因组时代的研 究热点。而基因调控网络的研究正是从全局的变化中探索基因功能,研究基 因之间的相互调控表达关系。 研究基因调控网络的方法一般包括计算机方法和生物学方法。计算机方 法包括聚类分析建立模型和通过“逆向工程方法推断基因调控网络。其中 聚类方法使用广泛,且已有方法较多,通过聚类找出具有相似功能,表达模 式也相似的基因集合,这是研究基因调控网络的有效的重要得方法之一。 生物学方法一般使用基因扰动实验,它通过操纵一个基因或其产物来控 制基因活动,从中获得基因相互调控关系的信息,从而重构基因调控网络。 由于生命组织的基因组规模巨大,而单个基因扰动一般需要1 3 个月,且花 费高昂,因此单基因扰动实验的对象一般为局部组织。单基因扰动实验采取 全基因扰动方法,即每个参与实验的基因都进行一次扰动,一旦选取的实验 基因数量过大,而其中存在一些对于构建基因调控网络没有太大影响的基 因,就会造成实验成本的不必要上升和实验周期的无端增加。因此,甄别这 些不必要基因成为降低实验成本、缩短试验周期的关键。 本文在狄关联聚类方法的基础上提出了自适应参数灰关联聚类算法,将 其与单基因扰动实验相结合,计算实验证明,该方法能有效减少不必要的扰 动实验,在基本不影响基因调控网络构建的前提下,减少实验成本和缩短实 验周期。 关键字:自适应参数;狄关联聚类;基因;扰动;基因调控网络; 单基w 扰动的自适应灰关联聚类算法 a b s t r a c t w i t ht h ec o m p l e t i o no ft h eh u m a ng e n o m ep r o j e c t ,t h er e v e l a t i o no ft h eg e n e f u n c t i o nb e c o m et h er e s e a r c hh o t s p o to ft h ep o s t - g e n o m ee r a a n dt h es t u d yo f g e n er e g u l a t o r yn e t w o r kd i s c o v e r yt h er e l a t i o n s h i po ft h em u t u a l - r e g u l a t i o n b e t w e e nt h eg e n ef u n c t i o na n dg e n er e s e a r c h t h ew a yo ft h eg e n er e g u l a t o r yn e t w o r ki sc o m p u t e rm e t h o d sa n db i o l o g i c a l m e t h o d s c o m p u t e rm e t h o d st h r o u g hc l u s t e ra n a l y s i st oc r e a t et h e m o d e la n d r e v e r s ee n g i n e e r i n gt od e d u c et h eg e n er e g u l a t o r yn e t w o r k c l u s t e rm e t h o d si s w i n d l yu s e da n dt h e r ea r el o t so fw a y s ,w ec a nf i n dt h eb o t hs i m i l a rf u n c t i o na n d s i m i l a re x p r e s s i o np a t t e r nt h r o u g ht h i sw a y i ti so n eo ft h em o s te f f i c i e n ta n d i m p o r tw a y t os t u d yt h eg e n er e q u l a t o r yn e t w o r k b i o l o g i c a lm e t h o d sa l w a y s u s eg e n ep e r t u r b a t i o n se x p e r i m e n t s g e n e p e r t u r b a t i o n se x p e r i m e n t sc a nr e b u l i dt h eg e n er e q u l a t o r yn e t w o r kb a s eo nt h e i n f o r m a t i o no ft h eg e n em u t u a l r e q u l a t i o nw h i c hg e tf r o mt h eg e n ea c t i v i t yb e c o n t r o l e db ys t e e r i n gag e n eo ri t sp r o d u c t i o n b e c a u s eo ft h eh u g eg e n o m es c a l e o ft h ep r o l i f eg r o u p s a n dt h ep e r i o df o re a c hg e n ep e r t u r b a t i o n si sa b o u t1t o3 m o n t h sa n dt h e e x p e n c ei sv e r yh i g h s ot h es b j e c t so ft h es i n g l e - g e n e p e r t u r b a t i o ne x p e r i m e n t si sp a r t i a lt i s s u e i fa d o p tt h ew i d e - g e n ep e r t u r b a t i o nf o r t h eg e n ep e r t u r b a t i o n se x p e r i m e n t s ,e v e r ye m p i r i c a lg e n en e e dt ob ep e r t u r bf o r o n c e i ft h ea m o u n ti st o ob i gt h ec o s ta n dt h ee x p e r i m e n tc y c l ew i l lb ei n c r e a s e d f o rt h eg e n er e q u l a t o r yn e t w o r kb e c a u s eo fs o m eu s e l e s sg e n e s ot h em o s t i m p o r t a n tt h i n gi st oi d e n t i f yt h o s eu s e l e s sg e n et or e d u c et h ec o s ta n dt h ep e r i o d t h i sa r t i c l ep r o p o s et h ea p g r c mb a s eo nt h eg r a yr e l a t i o nc l u s t e rm e t h o d w h i c hc o m b i n ew i t ht h e s i n g l e g e n ep e r t u r b a t i o ne x p e r i m e n t s c a l c u l a t i o n r e s u l t ss h o w st h i sw a yc a nr e d u c et h eu s e l e s sp e r t u r b a t i o ne x p e r i m e n te f f i c i e n t l y a n dr e d u c et h ee x p e r i m e n tc o s ta n dt h ep e r i o dw i t h o u ti m p a c tt h eb u l i do ft h e k e yw o r d s :a u t o - s e l e c t e dp a r a m e t e r ;g r e yr e l a t i o nd u s t e ra n a l y s i sm e t h o d ; g e n e ;d i s t u r b a n c e ;g e n er e g u l a t i o nn e t w o r k 单基因扰动的白适应灰关联聚类算法 原创性声明 本人声明:所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外,论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名:握日期:邕z 。主馏 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定,即:学 校有权保留论文及送交论文复印件,允许论文被查阅和借阅;学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名:伽师签名:遮趟日期:垒丝蟹 上海大学硕十学位论文 第一章绪论 1 1 课题背景 人类基因组计划( h u m a ng e n o m ep r o j e c t ,h g p ) 【1 1 由美国科学家率先提 出,随着人类基因组计划的实施,人类基因组和其它生物基因组的测序工作 进展极为迅速。迄今为止己完成了约4 0 多种生物的全基因组测序工作,人类 基因组约3 1 0 9 个碱基对的测序工作也接近完成。至2 0 0 0 年6 月2 6 日,被 誉为生命“阿波罗计划 的人类基因组计划,经过美、英、日、法、德和中 国科学家的艰辛努力,终于完成了工作草图,这是人类科学史上又一个里程 碑式的事件。它预示着完成人类基因组计划己经指日可待,生命科学进入了 后基因组时代( p o s t g e n o m ee r a ) 。在后基因组时代,生命科学研究的重点 不再是对单个基因的研究,而是整个基因组的功能和动态变化规律的研究。 对基因调控网络的研究是后基因时代的核心内容,是系统生物学的主要研究 内容。 基因调控网络的构建就是基于已知的生物实验数据,对基因之间其表达 关系相互依赖程度的一种仿真或重建。研究方法一般包括生物学方法和计算 机方法。生物学方法一般用基因扰动实验。基因扰动实验通过操纵一个基因 或其产物来控制基因活动,从中获得基因相互调控关系的信息,从而重构基 因调控网络。计算机方法包括:聚类分析建立模型和通过“逆向工程 方法 推断基因调控网络。 单基因扰动方法一般要求全部基因扰动,即每次实验选取一个基因进行 扰动,等到所有基因达到稳定状态后记录下各基因的表达数据,再选择另一 个基因继续实验,直到所有参与实验的基因都被扰动后,实验结束。通常, 单个基因的扰动需要1 3 个月,费用也相当高,而参与实验的基因中,可能 有一些基因与其他的基因不存在调控表达关系,因此,对于这些基因的扰动 实验完全可以省略。 基于以上几点,本文的主要目的是通过生物学方法与计算机方法相结 合,通过计算机方法来知道生物学方法,从而克服生物学方法的不足,达到 降低实验成本和缩短实验周期的目的。 1 2 基因调控网络基本概念 上海人学硕上学位论文 基因组学出现于上世纪8 0 年代,随着几个物种基因组计划的启动,基因 组学取得长足发展。在1 9 9 0 年,由美国科学家提出的人类基因组计划正式 实施,标志着生命科学进入了后基因时代。对基因的研究也从针对单个基因 的研究转到对整个基因组的功能和动态变化规律的研究。基因调控网络的研 究成为热点。 基因调控网络研究是数学、信息学、计算机科学向分子生物学渗透形成 的交叉点,基因组学和蛋白质组学相关技术的发展和应用,汇聚了大量的表 达谱和生物大分子相互作用网络图谱信息,下面介绍一些和基因调控网络相 关的生物学概念: 1 基因 从分子生物学角度看,基因是合成有功能的多肽或r n a 分子所必须的所 有核酸序列,除了为蛋白质或r n a 编码的序列之外,还包括控制基因转录 的序列。一般来说,基因是负载特定生物遗传信息的d n a 分子片段,在一 定条件下能够表达这种遗传信息,产生特定的生理功能。有的生物基因是 r n a 分子。 2 基因表达 细胞在生命过程中把蕴藏在d n a 中的遗传信息经过转录和翻译,转变 为具有功能的蛋白质分子的过程。 3 基因表达调控 围绕基因表达过程中发生的各种各样的调节方式都统称为基因表达调 控。主要表现在染色质水平上的调控,转录水平上的表达调控,转录后调控, 翻译水平上的调控,蛋白质活性的调节。基因表达调控网络的机制很复杂。 目前主要研究的转录水平的基因调控。 4 基因表达谱数据 基因表达谱数据是本文研究所采用的样本数据。一次微阵列实验能获得 细胞在某一条件下的全基因组表达数据,包含成千上万个基因在细胞中的相 对或绝对丰度,不同条件下的全基因组表达数据就构成了一个g x n 的数据 矩阵,通常情况下g n ,行表示基因,列表示条件。数据格式如下: 上拇大学顿+ 学位论史 叫誓: 。;:。j :1 。: + :崔:,: + ;: :。 :誊:k : :强:一 :j :! : :。+ :- :“:i j :。:,:; :;:t :i : 。j _ ” :“ :;:掌:i ? 。: :;:一:。: :- := :。: i 。n :o :事:味: -一:- + 一 : :曩:j :i :- :;j :。:三一一: 图12 l 【4 8 5 基因调控网络 基因表达调控网络的定义:一组调控因子如何调控一套基冈表达的过程 称为基因表达调控网络。基凼表达调控网络是基因调控网络的一个重要部 分。参与基因表达调控网络的元素主要包括c d n a 、m r n a 、蛋白、小分子 等。从元素间相互联系的角度柬看,基因表达调控网络足一个由节点( 调控 元素) 、边( 调控作用) 组成的一个有向图结构。如图12 2 圈122 简单的基因网络结构示意图 罔中每一个圆圈代表一个节点也就足调控网络的兀素,如基凼。有向 上海人学硕士学位论文 箭头表示表达增强作用,末端断线表示表达抑制作用。在基因网络中,存在 基因对自身表达的自调控现象。 6 基因序列 基因序列由一串字母组成的,可能的字母只有a 、c 、g 、t 四个,分别代表 组成d n a 的四种核苷酸一腺嘌呤,胞嘧啶,鸟嘌呤,胸腺嘧啶。 1 3国内外研究现状 1 3 1 基因调控网络研究现状和意义 基因调控网络模型分析和重建的研究,是生物信息学研究中的一个很重 要的方向,在国外己引起了的高度重视,同时运用到十分广泛的领域。很多 大学,研究机构,软件公司甚至政府机构纷纷成立生物信息机构,建立自己 的生物信息集成系统,研制这方面的软件,重金招聘人才,期望从中获取更 多的生物信息和数据加以研究和利用,缩短药物开发周期,抢注基因专利, 获取更大利润。 在国外,迄今为止,关于基因调控网络研究的模型已经有很多种,分类 方法也不尽相同,主要有离散网络模型和连续网络模型;确定型网络模型和 随机网络模型;定性网络模型和定量网络模型等。现有的主要模型有布尔网 络模型、随机布尔网络模型、线性组合模型、加权矩阵模型、互信息关联网 络模型、贝叶斯模型、神经网络模型、微分方程模型等。 在国内,对生物信息学的研究才刚起步,许多科研单位已经开始或准备 开始从事这方面的研究工作。北京大学研究建立起一个e m b l 的镜像数据库, 并提供数据检索服务。在复旦大学遗传学研究所,为克隆新基因而建立的一 整套生物信息系统也已初具规模。中科院上海生化所在结构生物学和基因预 测研究方面也有相当的基础,中科院计算所作为我国计算机科学的顶尖机构, 利用自身优势,也开始在生物信息方面投入大量的人力物力,从事相关的研 究。目前,在国内虽然关于生物信息学已经做了大量研究工作,取得了显著 的成就,但基因调控网络的研究在许多方面尚处于尝试和探索阶段。 随着生物信息学的发展,人们现在也越来越意识到基因调控网络这个课 题的重要性,转向这个方向的科研人员也在逐渐增多,对生物信息学的理解 也在深入,相信在不久的将来,人类将从基因表达调控网络中解读更多的遗 上海人学硕士学位论文 传密码。 基因网络研究的目的是通过建立基因转录调控网络模型对某一个物种或 组织中的全部基因的表达关系进行整体的模拟分析和研究,在系统的框架下 认识生命现象,特别是其中涉及的复杂的分子调控过程,支配基因表达和功能 的基本规则,信息流动的规律和在整体的框架下研究基因的功能,分子生物 学的进步,生物信息学的发展,分析和计算技术已能使我们系统地研究生物 系统中复杂的分子过程,尤其高通量的基因表达鉴定可以测量基因调控网络 的输出。建立不同的网络模型来描述生物系统的行为,有助于搞清协同工作 的基因的作用机理,阐明复杂的基因调控过程,为研制和识别疾病治疗中的 潜在靶标提供预测工具。 通过对基因调控网络的研究,有助于理解支配基因表达和功能的基本规 则。理解决定哪个基因什么时候表达的机制是许多基因操作的关键。目前致 力于发现联合调控的基因的研究,实际上是用生物信息学的方法揭示基因的 潜在调控机制;通过对基因调控网络的研究,有助于揭示基因表达过程中的 信息传输规律基因通过表达传输遗传信息。基因调控网络的研究可以用量化 的方法从一个侧面对基因表达过程中的信息进行挖掘。通过信息提取、分析, 了解基因功能,理解遗传网络,弄清疾病发病机制;通过对基因调控网络的研 究,更有助于从整体的框架下研究基因的功能。不仅要从结构层次上研究基 因的功能,更要从网络层次上发掘和认识基因的功能。基因在错综复杂的网络 关系中互相影响,协同工作,这必然蕴涵着d n a 序列无法完全揭示的新功能。 基因从表达中展示其功能,但基因的表达是一个彼此相互作用和调控的过程。 通过网络研究哪种疾病与哪个基因或过程有关,在药物设计上有很重要的意 义。 1 3 2 生物数据聚类方法研究现状 计算机科学中的聚类技术是在数据集中将具有某种相似性的对象聚合 在一起的一种方法,这种方法在生物信息处理方面有直接的意义。聚类方法 应用最多的是基因表达数据。采用聚类算法分析基因表达数据的一个重要原 因是基因表达数据非常庞大,而生物学里已知功能的基因相对很少。要利用 相对很少的己知知识去推断未知的知识,分类方法并不非常适合,因为用相 卜海人学硕士学位论文 对少的数据训练出来的模型不一定能代表整个数据空间的分布。聚类则不需 要先验知识,直接将具有相似表达性质的基因聚在一起。这对分析基因的功 能是一个非常简便有效的特性。 目前,国内外许多机构与学者都开展了针对基因表达数据的分析研究, 其中聚类分析应该说是目前基因表达数据最广泛使用的统计技术。作为知识 发现技术的重要手段之一,聚类分析技术被赋予了广泛深人的研究,并涌现 出一系列具有重要应用价值的有效算法。它们不同于传统的源于统计学的聚 类分析方法。不仅考虑了数据对象的数值属性,而且在数据的存储与访问、 数据语义、数据的巨量性和高维性、聚类结果的解释与可视化表达方面也进 行了深入的探索。所有这些努力使得聚类分析成为具有丰富理论基础和广泛 应用价值的数据分析技术。例如,m i c h a e le i s e n 开发的芯片数据分析软件 c l u s t e r 。它采用聚类方法,将每个不同的基因与其它的基因比较,鉴定最 相关的基因对。这种基因对的数据用平均数替代,再重新计算关系矩阵,不 断重复这个过程可以获得满意的聚类结果。 一 另外,大量的聚类算法应用到了基因表达数据中,产生了许多有效的算 法,k 均值聚类、自组织映射聚类、模糊聚类以及两种或两种以上聚类方法 的组合等,都取得了很好的效果。 s u g i y a m a 2 】等将自组织映射和k 均值方法相结合,用k 均值方法对s o m 结果进行聚类边界划分。他们将这种方法运用于酵母基因表达数据,取得了 优于单纯使用k 均值方法的实验结果。l e p i n gl i 3 】等将遗传算法与k n n 方法 相结合,运用此方法进行特征提取,选择最具表达的信息基因子集。他们运 用此方法从白血病基因表达数据训练集中提取出最具表达的5 0 个基因,然后 对测试集进行分类,3 4 个测试样本中,3 3 个样本得到正确分类。j u n g w o n 4 】 等人在2 0 0 2 年提出了一体化的分类器的思想,即把多层感知器( m l p ) 、k 最邻近方法( k n n ) 、支持向量机( s v m ) 等方法融合在一起,以这些分类 器的输出再做为神经网络的输入,来构造分类器分类。 模糊聚类的使用主要是由于基因表达谱数据噪音的存在,所以一般的聚 类分析可能会产生一些偏差。从生物学角度看,某些基因可能与多个类别高 度相关,普通聚类对基因进行非此即彼的严格划分不符合自然规律。为了解 i :海大学硕上学位论文 决这个问题,一些学者将聚类的方法与模糊数学相结合,将模糊聚类应用于 基因表达数据的分析。比如e m a t t h i a s 等运用模糊c 均值( f c m ) 聚类方法, 对酵母基因表达数据集进行了实验。实验表明该方法在噪音存在的条件下, 具有较强的鲁棒性。并且该方法能识别出具有多个类别特征的基因。 在国内,清华大学、华中科技大学、第三军医大学、东南大学也开展了 基因表达数据聚类及其相关方面的研列5 】【6 】1 7 】。 随着越来越多的聚类算法和基因表达数据分析模型的诞生,一些隐藏在 数据中的信息都被挖掘出来,这也预示着基因表达调控网络将成为生物信息 学研究的新热点。 1 4 课题任务及主要研究内容 单基因扰动方法要求全基因扰动,因此一些不必要的基因也参与扰动, 导致时间与金费的不必要投入。本课题的任务是寻找一种有效的方法,寻找 出不必进行扰动的基因,从而指导单基因扰动实验,减少实验成本。 本文的主要研究内容是针对基因扰动实验数据的特点,研究适合该数据 的聚类算法和相关问题,具体包括: 适用于基因表达数据分析的常用聚类算法的比较、聚类相关问题讨论、 聚类评分方法研究和最终算法验证。 1 5 论文结构 第一章绪论主要介绍课题背景、本课题国内外研究现状及课题的主要研 究内容。 第二章基因调控网络主要介绍一些相关知识和技术的基本内容,包括生 物学知识、常用聚类方法及比较、序列比对算法等。 第三章自适应灰关联聚类算法( a p g r c m ) 介绍了该算法的各个步骤及该 算法在具体数据上的应用结果及结果分析。 上海大学硕上学位论文 第二章a p g r c m 相关方法概述 2 1 基因调控网络研究方法 2 1 1 基因调控网络研究方法概述 基因网络的研究是一个新兴的领域,各种模型不断涌现,各种数学工具 不断引进,这使得其发展空间在不断扩大。基因调控网络的研究方法主要包 括生物学方法和计算机方法。 a ) 生物学方法 生物学方法一般用基因扰动实验【8 1 。基因扰动实验通过操纵一个基因或 其产物来控制基因活动,从中获得基因相互调控关系的信息,从而重构基因 调控网络。由于生命组织的基因组规模巨大,而单个基因扰动一般需要1 3 个月,且花费高昂,所以一般的实验往往从子网( 局部组织) 着手分析研究。 然后与其他文献上的参考网络比较,研究交叠情况,推断基因调控关系,揭 示内在规律【9 1 。 b ) 计算机方法 近几年,利用数学、统计学、神经网络、人工智能等方法在计算机上分 析模拟表达调控机理,是计算分子生物学方面一个飞速发展的方向,目前, 利用计算机进行基因调控网络的研究,采用的主要方法一般有:( 1 ) 聚类分 析建立模型;( 2 ) 通过“逆向工程”方法推断基因调控网络。 ( 1 ) 聚类分析建立模型【1 0 】 聚类是探索性数据分析和模式发现的一种基本手段,主要是对采自微阵 列的数据进行聚类,分析基因表达谱,辨明基因表达模式其目的是提取数据中 隐含的类别结构。已知有几十种聚类算法和大量的专门聚类程序被用于基因 表达数据的分析,其类型涵盖了各种连锁分层方法、k m e a n s 聚类、自组织 特征映射算法、主成分分析等。通过聚类找出具有相似功能,表达模式也相 似的基因集合,这是研究基因调控网络的有效的重要得方法之一。 ( 2 ) “逆向工程 方法推断网络 d n a 微阵列的广泛应用提供了海量的基因表达谱数据,即细胞内m r n a 的相对或绝对数量,反映了基因转录的调控机制,而基因转录在基因表达环 上海人学硕士学位论文 节中起着非常重要的作用。基因在转录过程中,转录因子( 蛋白质) 与d n a 的结合以激活基因的转录,而基因的表达产物有可能是转录因子,它又能激 活或抑制其它基因的转录,如此继续下去,就形成一个基因调控路径。一条 路径中的基因在表达水平上存在某种相关性,例如受同一个转录因子调控的 基因往往是共表达的,这些生物学原理可以用于指导基因调控路径的构建。 从表达谱数据出发,可以建立基因相互作用的网络模型,这种方法也称反向 工程( r e v e r s ee n g i n e e r i n g ) 。“反向工程 方法就是从基因表达的大量数据反向 推断未知的或隐含的基因网络拓扑结构的技术它需要选定合适的参数模型, 并用适当的算法推断网络参数,确定输入输出规则,预测网络对时间变化的反 应。l i a n g 等人于19 9 8 年在太平洋计算生物学学术讨论会上提出了r e v e a l 算法,采用布尔网络模型和信息熵计算结合的方法进行基因调控网络模型的 预测和分析,随后,大量用于基因调控网络建模的模型不断涌现,如有向图模 型、贝叶斯网络、布尔网络、微分动力模型、随机微分方程、神经网络模型 等,参数优化的方法也越来越多,如遗传算法,梯度下降,模拟退火,进化 策略,遗传规划,人工免疫方法等等。 2 1 2a p g r c m 算法的提出及基本思路 生物学方法一般采用单基因扰动实验获得所需的数据,但由于单个基因 扰动需要较长时问和较高费用,而以往的单基因扰动实验必须对所有参与实 验的基因全部进行扰动,即全基因扰动,因此实验成本比较高、实验周期长。 然而,在所有参与实验的基因中,往往存在这样一些基因,它们与其他基因 的调控表达关系相对较少,甚至不存在调控表达关系,对这些基因的扰动实 验结果完全可以忽略,也就是说它们对于构建基因调控网络没有太大影响。 因此,找到一种方法来选择基因扰动实验的对象( 基因) ,从而省略对不必 要基因的扰动并得到与全基因扰动基本相同的基因调控网络,可以大大降低 扰动实验的成本,并缩小实验周期。 基于以上问题,本文提出了a p g r c m 算法,通过在生物学实验的中加 入计算机方法来克服基因扰动实验的周期长、成本高的缺点,从而达到对部 分实验基因扰动而得到与全基因扰动基本相似的基因调控网络。 算法的基本思路如下:在单个基因扰动实验结束后,对实验结果进行聚 上海大学硕十学位论文 类分析,聚类参数从参数区问最大值开始,对得到的聚类结果进行评分并记 录,然后参数递减并继续聚类分析,最后选择评分结果最高的聚类结果,通 过验证评分方法,从中选择评分最高的相应的基因作为下一个实验对象。 2 2 聚类方法介绍及比较 2 2 1 常用聚类算法概述 聚类算法有多种不同的分类方式【l i 】:根据其是否使用先验知识,可分为 非监督聚类( u n s u p e r v i s e dc l u s t e r i n g ) 和监督聚类( s u p e r v i s e dc l u s t e r i n g ) ;根据聚 类过程中是否假定内在的概率框架,又可分为启发式聚类( h e u r i s t i c b a s e d c l u s t e r i n g ) 和基于模型的聚类( m o d e l - b a s e dc l u s t e r i n g ) 。此外,还可分为等级体 系聚类( 又称系统聚类) 和直接划分聚类两种。系统聚类利用基于相似度的标 准来合并或分割簇,产生嵌套的层次系统树图。其通用性好,使用最为广泛, 但计算复杂度高,如层次聚类。直接划分聚类产生一个单一的分割而不是嵌 套的树图,可以避免数据集很大时的计算复杂性。其分类是以最优化局部或 者整体的标准函数为依据。根据采用最优化方法的不同又派生出多种方法, 如:k 均值聚类,自组织映射和基于图论的聚类等【1 2 】。 基因表达数据的探索性分析旨在发现一些未知的细胞状态或者一类功能 相似的基因,核心问题是如何鉴别基因的共同表达模式,并把基因按共同表 达模式分成不同的类别以提供对其生物机能及其关联性的深入理解。此时, 因缺乏已知的先验知识,只能进行非监督分析( u n s u p e r v i s e da n a l y s i s ) 。非监 督聚类没有一个事先定义的向量集或类别集【1 3 1 ,使用递归的分割方法来划分 类,把具有相似特征的目标数据归入相对同源类。对于先验知识难获得或者 不完全的情况下,这种方法显得特别重要。目前,基因表达阵列实验尚处于 早期阶段,绝大多数正是这种状况。因此,已有大量的非监督聚类算法应用 于基因表达分析,如层次聚类,k 均值聚类,自组织映射和主成分分析等【1 4 1 。 如果存在一些有关数据的先验信息或假设,如基因功能的种类、样品归 属的疾病( i e 常) 状态等,则可以进行监督分析( s u p e r v i s e da n a l y s i s ) 。在监督聚 类中,依据数据的先验知识,聚类基于一个给定的参考向量集或类别集进行。 常用的监督聚类工具包括不同形式的线性判别分析、最近邻分类法、决策树、 支持向量机和人工神经网络等,用于建立模型,并预测特定样本的分型,发 卜海大学硕上学位论文 现分型的标志基因。 下面介绍一下分析基因调控表达数据时常用的几种聚类算法: 曲层次聚类【1 5 】【1 6 1 一个层次聚类方法将数据对象组成一棵聚类的树。根据层次分解是自底 向上还是自项向下形成,层次聚类方法可以进一步分为凝聚的 ( a g g l o m e r a t i v e ) 和分裂的( d i v i s i v e ) 层次聚类。 凝聚的层次聚类:这种白底向上的策略首先将每个对象作为一个簇,然 后合并这些原子簇为越来越大的簇,直到所有的对象都在一个簇中,或者某 个终结条件被满足。绝大多数层次聚类方法属于这一类,它们只是在簇间相 似度的定义上有所不同。 分裂的层次聚类:这种自顶向下的策略与凝聚的层次聚类相反,它首先 将所有对像置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自 成一簇,或者达到了某个总结条件,例如达到了某个希望的簇数目,或者两 个最近的簇之间的距离超过了某个阈值。 : 假设有1 1 个混合抽样实验的样本,我们不确知每个样本的类别属性,在 极端的情况下,先把每个样本各自视作一类,共有n 类,然后根据类间相似 性大小逐级聚合,每级只把相似性最大的两类聚合成一类,最终把所有样本 聚合为一类。这样就得到从1 1 类到l 类的类型数目序列,又被称为分级划分, 见图2 2 一l 。类型数目为c ,第1 级,每个类型只包含1 个样本,萨n ;第2 级,只有一个类型包含两个样本,c - - - 1 1 1 ;第3 级,嗍2 ;依次类推,第k 级,c - - - - n k + 1 ;最后,第n 级,c = l ,全部样本聚合为一类。这样就形成一棵完 整的树。可以看出这种算法的一个特点,即若某些样本在较低的水平级上被 聚合为同一类,则它们在较高的水平级上永远属于同一类,即不可逆。 上海大学硕上学位论文 图2 2 1 层次聚类算法的缺点: 层次聚类的性能随待分类的基因数的平方下降,因其需要计算每一对基 因表达谱间的距离,若分析大量的基因,计算工作量将非常大。选择不同的 类间距离定义可能影响类的构成并导致不同的注释。系统树图也只是原始数 据的一维排列,其中每一项有两个邻项,多种关系无法在单一维数上得到表 现。更重要的一点是由于层次聚类过程中,每一步总是将相似度最大的两个 点最先聚合成为一个点,这就导致了该算法有可能陷入局部最优,而不能得 到最好的结果。 b ) k - 均值聚判1 刀 k - 均值聚类属于划分方法。划分方法即给定一个包含n 个数据对象的数 据库,以及要生成的簇的数目k ,一个划分类的算法将数据对象组织为k 个 划分( k n ) ,其中每个划分代表一个簇。通常会采用一个划分准则( 经常 使用相似度函数) ,例如距离,以便在同一个簇中的对象是“相似的 ,而不 同的簇中的对象是“相异的 。 k 均值算法以k 为参数,把n 个对象分为k 个簇,以使簇内具有较高的 相似度,而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值( 被 看作簇的质心) 来进行。k 均值算法的处理流程如下。首先,随机地选择k 个对象,每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象, 级 级 级 级 级 级 2 3 4 5 6 上海大学硕十学位论文 根据其与各个簇中心的距离,将它赋给最近的簇。然后重新计算每个簇的平 均值。这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则, 其定义式( 2 1 ) : i 2 e = ip - m i ( 2 1 ) i = 1p e q 这里的e 是数据库中所有对象的平方误差的总和,p 是空间的点,表示 给定的数象,m i 是簇c i 的平均值( p 和m i 都是多维的) 。这个准则试图使生 成的结果簇尽地紧凑和独立。 k 均值算法的过程描述如下【1 8 】: 任意选择k 个对象作为初始的聚类中心; r e p e a t 根据聚类中对象的平均值,将每个对象( 重新) 赋给最类似的聚类; 更新聚类的平均值; u n t i l 对于每个输入的对象,每个聚类的平均值都不再发生变化 这个算法尝试找出使平方误差函数值最小的k 个划分。当结果簇内对象 是紧密而簇与簇之间区别明显时,它的效果较好。对处理大数据集,该算法 是相对可伸和高效率的,因为它的复杂度是o ( n k t ) ,其中,n 是所有对象的 数目,k 是簇的,t 是迭代的次数。通常地,k n ,且t n 。这个算法往往 以局部最优结束。 k - 均值聚类算法的优缺尉1 9 】: k 均值聚类的优点在于计算速度快,消耗资源小,即使数据量很大也能 很快的完成聚类。缺点在于分类的结果很可能陷入局部极值,无法找到全局 最优解。将模拟退火和遗传算法与k 一均值聚类方法结合可有效解决这个问 题;还有一个缺点就是聚类的个数必须事先确定,这对基因芯片数据处理是很 大的问题。 c ) 自组织映射聚类【2 0 】 人工神经网络技术在模式识别方面有着独特的优势,神经网络能够进行 非线性数据处理,发现复杂的数据关系。其中,自组织映射神经网络是人工 神经网络应用于聚类分析中的例子,可以对模式数据进行自动聚类。它采用 上海人学硕十学位论文 的是结构简单的单层竞争性神经网络。自组织特征映射是k o h o n n e 2 1 1 在1 9 9 0 年提出的类似大脑思维的一种人工神经网络方法,它是一种竞争学习算法, 是一种从n 维模式空间各点到输出空间少数点的映射。这一映射由系统本身 完成,没有外部的监督,即聚类是以自组织的方式实现的。 自组织映射算法中:输入信号用输入向量x ( t ) 来表示。对于基因表达谱 来说,就是基因向量。组织图上的节点包含一个模型向量m ( t ) 。模型向量和 输入向量同维。自组织映射计算是一种回归过程,模型向量的值随机选取, 在实际应用中,模型向量的值可由输入向量中主要的特征向量决定。每个输 入向量都和所有的模型向量比较,距离( 比如说欧氏距离或泊松相关系数) 最 近的模型向量胜出。根据学习原理,组织图上该模型向量的节点和它相邻的 节点向输入向量移动。学习过程的基本思想就是对于每个输入向量胜出的模 型向量节点和它的相邻节点都向输入向量移动,在学习过程中,个别变化可 能互相矛盾,但当网络输出后有序的模型向量就出现在组织图上。如果输入 向量有限的话,就必须重复输入学习。学习过程就是对于每个属于n c ( t ) 节点 的模型向量m i ( t + 1 ) = ( f ) + 口( f ) z ( f ) 一他( f ) 】,否则m ,o + 1 ) = m f ( f ) 。其中 0 a = 0 ,令气= t k - t k 一1 ( 七= 2 ,3 ,1 ) , a ,b = u 气,a t kr 、& 一。= 矽,x c 寸- :v k ,两原始时间序列在 a ,b 区间各点的 k = 2 取值分别为: 其增量序列为: k = ( ( ) ,而( 乞) ,而( 乙) ) 置= ( 而( ) ,薯( 乞) ,t ( 乙) ) ( 气) = x o ( t k ) 一x o ( t k 1 ) ,( 后= 2 ,3 ,以) 焉( 气) = x i ( t k ) 一薯( 气一1 ) ,( 后= 2 ,3 ,刀) 首先计算各个时段的关联系数: 孝( 腩) :s 印( 瓴( 钞她( 秒忑m i n 可( i6 瓦x o 丽( t k ) 可i , ia 而x i ( t k ) 1 ) ) ,雠( 钞缸( ) 。 【o ,a x o ( q ) 缸( 气) = 0 上式中:当缸( 气) 咄( 气) 0 时,关联系数孝( 气) 0 ,否则,当 ( ) 而( ) 0 时,孝( 气) m a x l 。,l 2 ,l n ) ) ,a j 是序列集s 的 一个比对结果。 其中:矩阵的第i 行是参与比对的第i 个序列的最优比对序列( 即插入空 位的序列,如果移去所有的“”将得到原来的序列) ;矩阵中的每一列不允 许同时为“; 4 ) ,是比对a 的相似性度量函数,用来表示比对a 中各最优比对序列 的相似度; 5 ) 序列比对问题m s a 就是通过适当的空位插入,构建一个使得相似性 度量函数f ( a ) 达到最大的比对彳。 序列比对问题实质上是个组合优化问题,为了容易处理,目标函数通常 选用w s p ( w e i g h t e ds u m - o f - p a i r s ) 度量f ( 彳) = s ( s ,t ) ,其中: i = lj = l 是第i ,j 两个序列间的权重,s ( s ,s ,) 是两个比对序列比对的相似分值。 由上述定义可知:序列比对问题就是通过适当的空位插入来模拟生物分 子进化过程中的突变现象,寻找保守区域,以反映它们间的进化关系,为两 个或多个序列的碱基之间的相互关系提供一个非常明确的关系图谱( 图 2 3 1 ) 5a a c a att c c g a ct a c ta ct a c ct 一一一c 6 c 一一 图2 3 1 双序罗l l b 匕对 2 3 2 序列比对算法分类 t 海大学q ,l 学位论女 序列比肘类型可以从两个不同角度米划分:一是从序列个数,序列比对 可分为双序列比对( p a i r w i s e s e q u e n e e a l i g n m e n t ) 和多序列比对( m u l t i p l e s e q u e n c ea l i g n m e n t ) ;另 个是从比对范围,可分为从头到尾的全局比对 ( g l o b a l a l i g n m e n t ) 和只考虑部分区域相似性的局部l l x 寸_ ( l o c a l a l i g n m e n t ) 。 a 1 双序列比对算法 到目前为止双序列比对问题已基奉解决+ 标准方法是采用t 以保汪得 到一个数学优化的比对结果的动态规划比对算法。双序列的动痞舰划比对算 法是多序列比对的重要理论基础。 动态规划比对算法具体如下【”i :对于长度分别为 ,卅的序列ard , a 2 ,w 一和口r 6 b 2 ,出叫,其比对过程i u 用个以序列a 为列,b 为 行的r n + r 珥+ 二维矩阼来表示,如图23 - 2 。 :嚣。日 h 嘶1 t b ! - c _ t 妇t c - 日8 圳 劬 b “崛t - 图2 3 2 两个摹因序列a 和b 的动态规划序列比对删 每个单元的评价值町由公式2 2 递归计算,其中g 似- u + k v 是连续k 个g a p 的空位罚分,fr q ,”足两个残基的相似度,具体公式请参考第章公式 3 1 4 。 m 。= m a x m a x m 。g ( i ) ,m a x m 川一g ( f ) ) ,m h 川+ ,( q ,q ) j ( 2

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论