（计算机应用技术专业论文）一种改进图算法在调控元件预测中的应用.pdf

独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作所取 得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集体，均己在文 中作了明确的说明。本声明的法律结果由本人承担。 学位论文作者签名：荔露茏日期：切t o f 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位敝储虢雀指剥雠：互易7 ，乏 日 期：z z 曼：占 日 期：丝口切 学位论文作者毕业后去向： 工作单位：电话： 通讯地址：邮编： 中文摘要 随着生命科学的快速发展，在分子生物学中的一个主要挑战是揭示基因表达 的调控机制，也就是说要知道基因表达的激活和抑制怎样实现的。面对这个挑战 的一个主要步骤就是识别调控元件，特别是识别d n a 上的转录因子结合位点。转 录因子一般是与d n a 上游序列特别是临近基因转录起始位点结合的蛋白质，通过 调节或抑制转录机制来调节基因的表达。这种调节元件的预测依然是一个问题。 即便是研究的最透彻的生物，关于它的调控元件我们仍然知之甚少。想要准 确识别这些位点难度很大，因为他们一般长度很短，只有1 0 个碱基长度左右。 而一般输入序列长度为1 0 0 0 b p 。使问题更为复杂的是每个转录因子有多种结合 位点，而且位点序列存在变化。 本文借助于赋权图( w e i g h t e dg r a p h ) 理论，利用改进的打分函数建立一个 新的算法，对输入序列每两条片段进行打分，这样在不同的结点之间就可以利用 的权值的不同进而衡量匹配度。同时引入了生物学的先验信息，并与g i b b s 采样 算法相结合。 为检验算法的性能，我们选用线虫5 个转录因子进行测试。并选择其他3 个算法比较性能，分别为a 1 i g n a c e ，c o n s e n s u s ，g i b b s 。该算法在与其他经典 算法的比较中表现出更高的准确度和敏感度，其产生的结果生物学依据更加充 分。而对于不同的物种可调整本方法使用的数据以使其可适用于其他物种，使该 算法适用范围更广。 关键词：调控元件；线虫；g i b b s 采样；图算法；生物信息学 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fb i o i n f o r m a t i c s ，r e v e a l i n gt h er e g u l a t em e c h a n i s m o fg e n ee x p r e s s i o nb e c o m e sam a i nc h a l l e n g ei nm o l e c u l a rb i o l o g y o n eo ft h em o s t i m p o r t a n ts t e p s i st of i n d t h er e g u l a t o r s ，e s p e c i a l l yt h eb i n d i n gs i t e so ft h e t r a n s c r i p t i o n f a c t o l t r a n s c r i p t i o nf a c t o r s a let h e p r o t e i nn o r m a l l yb i n d i n g t h e u p s t r e a md n as e q u e n c e s ，e s p e c i a l l yn e a rt h et r a n s c r i p t i o ns t a r ts i t e t h e yr e g u l a t e t h ee x p r e s s i o no fp r o t e i nb yr e g u l a t i n gt h et r a n s c r i p t i o nm e c h a n i s mo ri n h i b i t i n g 目录 中文摘要i a b s t r a c t i i 目录i i i 第一章引言1 1 1 研究背景l 1 2 研究现状：1 1 3 研究的目的及意义2 1 4 本文主要工作3 第二章生物学背景知识4 2 1d n a 简介4 2 2 基因一般概念5 2 3 转录过程5 2 4 翻译过程j ：6 2 5 转录因子7 2 6 模体7 第三章调控元件预测方法分析9 3 1 相关数据库简介9 3 2 数据库比较1 0 3 3 描述调控元件的模型1 1 3 4 现有预测方法概述1 1 3 5 预测计算方法分类1 2 第四章改进图算法及在调控元件预测中的应用1 4 4 1 图论基础1 4 4 2 图的应用1 4 4 3 改进后的图算法与g i b b s 方法结合1 7 4 4 根据生物学依据进行改进1 8 4 5 计算信息含量方法。1 9 4 6 实验结果与分析2 0 第五章结束语2 3 5 1 本文的主要工作总结2 3 5 2 今后的工作2 3 参考文献2 4 后记2 6 在学期间公开发表论文及著作情况2 7 东北9 币范大学硕士学位论文 第一章引言 1 1 研究背景 1 1 1 生物信息学 传统的生物学是建立在实验的基础之上的，发现问题和解决问题的方法均是 利用实验，然而生物实验往往需要较长的周期，而且一些实验失败率较高，重现 度较差，这些给生物学发展带来了极大地阻碍。生物信息学( b i o i n f o r m a t i c s ) 是最近几十年来新兴起的多学科的交叉学科，在生物信息学的帮助下，研究者可 以从不同的学科的角度进行深入研究，可以利用不同的算法和软件模拟实验和检 测实验，也可以与一些传统实验相结合，甚至完全可以代替一些传统实验。这为 研究者提供了方便，大大的缩短了研究周期，改善了研究现状。正因为此这门学 科必然会促发传统生物学的革新，也为生物学发展翻开了崭新的一页。 生物信息学是伴随基因组研究而发展起来的，它以揭示生物数据的内涵为长 远目标。因为基因组计划产生了大量的生物学数据，而且这些数据具有丰富的内 涵，其中蕴藏着丰富的生物学知识。生物信息学的研究重点就是使用计算方法分 析生物的基因组和蛋白质；理解其中包含的意义；揭示未知的信息。这也使它成 为当今科学发展的前沿和核心领域之一。 1 1 2 生物信息学的研究内容 生物信息学的发展经历了多个阶段，可以粗略的画分为两个时代：测序基因 组时代以及功能基因组时代。 它所研究的方向众多，重点内容可以分为三个方面：收集和管理生物数据； 进行数据处理和分析；开发分析工具和实用软件。 而从基因组学和蛋白质组学两个方面分别来说它的研究内容包括： 基因组学的研究包括进一步识别基因；注释基因产物的功能；研究基因表达 调控机制；比较基因组学研究，等等。 蛋白质组学是研究细胞内所有蛋白质及其动态变化规律的科学，旨在阐明生物体全部蛋 白质表达模式及其功能模式，它的研究主要内容为鉴定蛋白质的表达、存在方式、结构、功 能、和相互作用。 1 2 研究现状 1 2 1 国外研究现状 东北师范大学硕士学位论文 由于生物信息学对于促进生物学基础研究、实验研究、及生物医学发展具有 重大的意义。国际上非常重视它的发展，许多国家开发了相关的数据库，收集相 关的生物资源数据，并通过计算机网络同其他国家共享现有的生物信息资源。 同时许多国际上著名的i t 公司也参与其中，展开了激烈的竞争，比如i b m 、 m o t o r o l a 、h p 和s g i 等公司。仅仅2 0 0 4 年一年，i b m 公司在生物信息学相关领 域的年销售额已达到3 0 亿美元。这些参与的公司在不久的将来必然形成与传统 生物技术业界联合的局面，并肩推动生物信息产业的快速发展n t 钆5 | 。而这一领域 的发展也为经济发展带来了新的增长点。 1 2 2 国内研究现状 我国的生物信息学工作是随着人类基因组研究的展开才逐步发展起来的，近 些年来有了长足的进步，在一些领域取得了一定成绩，而且有一批学术成果在国 际上处于领先的地位。 但是从国内生物信息学研究与应用的整体情况来看，仍然与国外有比较大的 差距，在生物信息分析、基因功能分析等方面的工作还很匮乏。参与研究的公司 和开展研究和的机构仍然较少，研究体系依旧不完善，这与国外有很大的差距。 随着国家的重视，加大这方面投入，以及各高校逐步开展相关领域的研究， 相信这一领域将很快达到国际先进水平。 1 3 研究的目的及意义 1 3 1 研究意义 生物信息学研究是从理论上认识生物本质的有效途径。揭示基因表达调控的 复杂机制是在后基因组时代所面临的重大挑战之一，根据分子生物学的中心法则 可知，转录是基因表达的第一步，而转录过程和后转录过程的调控主要通过d n a 结合蛋白与其在基因组序列中对应的结合位点之间的交互作用来实现。当前，对 大多数转录因子及其结合位点的认识仍然有限，这也给预测带来了难度。 对已知的调控元件进行分析可知，调控元件往往以保守短序列片段形式出 现。与其它的序列模体信号相比，调控元件模体除了长度较短( 一般为6 - 3 0 个 碱基长度) 以外，其序列组成也存在差异，容许较多的错配，这主要是由于功能 上的差异造成的，不同的结合位点要求的结合亲和力不同。这些特征造成元件 信号的保守性偏弱，特异性较弱，很容易与背景序列中随机出现的类似信号混淆 在一起。另外，调控元件在序列中的分布范围非常广，其中大部分位于基因上 游序列的启动子内，也有一些出现在基因的下游序列，甚至有的会在内含子或编 码区内出现。而对于高等生物，比如真核生物，其序列长度范围常常能达到数 千碱基对。基于上述的各种客观因素使得对调控元件的预测识别成为一项及其 东北师范大学硕士学位论文 困难的任务1 川。 1 4 本文主要工作 本文将对现有预测识别模体方法进行学习研究，借助于赋权图( w e i g h t e d g r a p h ) 理论并结合生物学已有的先验知识，利用改进的打分函数建立了一个全 新的算法。将本方法结合了g i b b s 采样晴1 方法，以提高原方法识别模体位点的精 确性和准确性，同时也提高预测的敏感性和预算速度。从而达到解决g i b b s 采样 方法存在局部最优解哺t7 3 及缺乏基于生物学的依据的问题。 为检测本改进方法的可行性与有效性，利用改进后的方法对几种模式研究生 物的调控元件进行了识别预测，将得到的实验结果与其他经典方法进行比较，最 后讨论实验结果，为下一步工作做准备。 东北师范大学硕士学位论文 第二章生物学背景知识 2 1d n a 简介 d n a 是一种长链聚合物，组成单位称为脱氧核苷酸，也被称为脱氧核糖核酸 链，是单体脱氧核糖核酸聚合而成的聚合体。它是借由酯键将糖类与磷酸分子相 连，组成其长链骨架。每个糖分子与一种碱基相连( a 、g 、c 、t ) ，这些碱基沿 着d n a 长链所排列而成的序列，可组成遗传密码，是蛋白质氨基酸序列合成的依 据0 1 。 d n a 是遗传信息的主要载体，那么在繁殖过程中，遗传信息的传递是就是通 过亲代的d n a 复制传递到子代完成的。d n a 贮存的遗传信息包含着决定物种性状 的几乎所有蛋白质和r n a 分子：包含了决定生物有机体发育的所有步骤的信息。 除细胞核内d n a 外，还有少量的d n a 存在于线粒体和叶绿体中。研究也发现大多 数病毒的遗传物质是d n a ，少数为r n a ，极其特别的病毒是以蛋白质做为它的遗 传物质( 阮病毒) 。 d n a 是由4 种脱氧核苷酸形成的线性多聚体，这4 种核苷酸阳j 们分别是： 腺嘌呤脱氧核苷单磷酸( d e o x y a d e n o s i n em o n o p h o s p h a t e ，a ) 、 胸腺嘧啶脱氧核苷单磷酸( d e o x y t h y m i d i n em o n o p h o s p h a t e ，t ) 、 鸟嘌呤脱氧核苷单磷酸( d e o x y g u a n o s i n em o n o p h o s p h a t e ，g ) 、 胞嘧啶脱氧核苷单磷酸( d e o x y c y t i d i n em o n o p h o s p h a t e ，c ) 。 2 1 1d n a 的重要特征：互相配对 d n a 的一个重要特征是线性多聚体可以互相配对，其配对是特异性的，由此 而形成的双链聚合体因其特殊的形状而被称为“双螺旋”( d o u b l eh e l i x ) 。双链 中g 与c 配对，a 与t 或u 配对，其中一链可以作为合成另一链的模板，这就是 d n a 复制以至所有遗传学的基础9 如1 。由d n a 转录为r n a 也使用类似的模板合成 方式，而由r n a 序列转化为蛋白质序列则较为复杂，这是通过三联密码子翻译成 氨基酸的过程完成的，这一过程有转移r n a 和核糖体的参与。 2 1 2d n a 的结构 在发现d n a 是遗传物质之前就阐明了d n a 是多核苷酸结构，d n a 分子是由两 条核苷酸链以互补配对原则所构成的双螺旋结构的分子化合物。双螺旋由两条多 核苷酸相互缠绕在一起组成，两条链相反。d n a 在结构上有灵活性，活体细胞中 4 东北师范大学硕士学位论文 的d n a 被认为主要是b 型，单基因组d n a 分子在结构上不是完全一致的，这主要 是由于螺旋中的每个核苷酸都有柔性，采取稍微不同的分子形状。其他变异体包 括c 型、d 型、e 型、t 型等旧1 圳。被一种d n a 结合蛋白结构识别的一段特异核苷 酸序列如果形成其他构象，该d n a 结合蛋白将不能识别它。 2 2 基因一般概念 基因是遗传的物质基础，是d n a 分子上具有遗传信息的特定核苷酸序列的总 称，是具有遗传效应的d n a 分子片段。基因通过复制把遗传信息传递给下一代， 在一定条件下能够表达这种遗传信息。从分子生物学角度看，基因是合成有功能 的多肽或r n a 分子所必须的所有核酸序列，除了为蛋白质或r n a 编码的序列以外， 还包括控制基因转录的序列。人类大约有几万个基因，储存着生命孕育生长、凋 亡过程的全部信息，通过复制、表达、修复，完成生命繁衍、细胞分裂和蛋白质 合成等重要生理过程。基因是生命的密码，记录和传递着遗传信息。生物体的一 切生命现象都与基因有关。它同时也决定着人体健康的内在因素，与人类的健康 密切相关。 基因有两个特点，一是能存储遗传信息并忠实地复制自己，向后代传递；二 是基因能够“突变”，突变绝大多数会导致疾病，另外的一小部分是非致病突变。 非致病突变给自然选择带来了原始材料，使生物可以在自然选择中被选择出最适 合自然的个体。 基因表达是指生物在全部生命过程中，遗传信息经过转录和翻译两个过程转 变成具有生物活性的蛋白质分子n 垃删。 2 3 转录过程 在r n a 聚合酶的催化下，以d n a 为模板合成m r n a 的过程称为转录，是基因表 达的第一个阶段。存储于d n a 中的遗传物质需通过转录和翻译而表达。在转录 过程中，d n a 的一条链做为模版，在其上合成出r n a 分子，合成以碱基配对的方 式进行，所产生的r n a 链与d n a 模版链互补。在d n a 中编码链，它与转录产物的 差异仅在于d n a 中t 变为r n a 中的u 细胞中的各类r n a 均在r n a 聚合酶的催化 下合成。最开始的转录r n a 产物通常都需要经过一系列加工和修饰才能成为成熟 的r n a 分子。那么也就是说转录后要进行加工，转录后的加工包括以下一些内容 1 j ： ( 1 ) 剪接：转录的产物前m r n a ( 又称核内异质r n a ) 中包含基因的外显子和 内含子。另外它还包括一些编码区上游和下游序列。将这些内含子通过一定的方 式剪切掉，把外显子再重新组装起来，才能产生成熟的m r n a 分子。 5 东北师范大学硕士学位论文 ( 2 ) 加帽：真核的m r n a 端都具“帽子 结构。虽然真核生物的m r n a 的转 录以嘌呤核苷酸三磷酸( p p p a g 或p p p g ) 领头，但在5 端的一个核苷酸总是7 一 甲基鸟核苷三磷酸( m 7 g p p p a g p n p ) 。m n r a 5 端的这种结构称为帽子。不同真核 生物的m r n a 的帽子是有区别的。 m r n a 的帽结构功能仍然不是十分清楚，推测它能在翻译过程中起识别作用 以及对m r n a 起稳定作用；它还可以保护m r n a ，避免受核酸外切酶的降解。 ( 3 ) 加尾：指真核生物的m r n a3 末端的多聚腺苷酸化，它的的功能是： 有助m r n a 从核到细胞质的运输；避免在细胞中受到降解，增强m r n a 的稳定性。 2 4 翻译过程 蛋白质的生物合成是根据m r n a 链上每三个核苷酸决定一个氨基酸的三联体 密码规则，合成出具有特定氨基酸顺序的蛋白质链。蛋白质的合成本质上是遗传 信息的翻译过程，是基因表达的第二个阶段。真核细胞的转录和加工是在细胞核 内进行，而翻译过程是在细胞质中进行。 翻译是以m r n a 作为直接模板，t r n a 作为运载工具，在酶的作用下将氨基酸 装配为蛋白质多肽链的过程，这一过程可分为以下3 个阶段： ( 1 ) 肽链的起始：首先是m r n a 先后与核糖体的3 0 s 和5 0 s 亚基相结合，然后 甲酰甲硫氨酰t r n a 结合上去，构成起始复合物。通过t r n a 的反密码子u a c ，识 别m r n a 上的起始密码子a u g ，随后核糖体大亚基结合到小亚基上去，形成稳定 的复合体，从而完成了起始的作用。 ( 2 ) 肽链的延和长：核糖体上有两个结合点：p 位和a 位，可以同时结合两 个氨酰t r n a 。当核糖体沿着m r n a 从5 - - 3 移动时，便依次读出密码子。首先 是t r n a f m e t 结合在p 位，随后第二个氨酰t r n a 进入a 位。此时，在肽基转移酶 的催化下，p 位和a 位上的2 个氨基酸之间形成肽键。第一个t r n a 失去了所携 带的氨基酸而从p 位脱落，p 位空载。a 位上的氨酰t r n a 在移位酶和g t p 的作用 下，移到p 位，a 位则空载。核糖体沿m r n a5 端向3 端移动一个密码子的距 离。第三个氨酰t r n a 进入a 位，与p 位上氨基酸再形成肽键，并接受p 位上的 肽链，p 位上t r n a 释放，a 位上肽链又移到p 位，如此反复进行，肽链不断延长。 ( 3 ) 肽链的终止：终止信号是m r n a 上的终止密码子。当核糖体沿着m r n a 移 动时，多肽链不断延长，到a 位上出现终止信号后，就不再有任何氨酰t r n a 接 上去，多肽链的合成就进入终止阶段。 ( 4 ) 翻译后加工( p o s t r a n s l a t i o n a lp r o c e s s i n g ) ：从核糖体上释放出来的 多肽需要进一步加工修饰才能形成具有生物活性的蛋白质。翻译后的肽链加工包 括肽链切断，某些氨基酸的羟基化、磷酸化、乙酰化、糖基化等。 6 东北师范大学硕士学位论文 2 5 转录因子 遗传信息从d n a 传递到蛋白质的过程为基因表达，而对这个过程的调节就是 基因表达调控。基因表达调控正调控和负调控之分。比如细菌基因的负调控机制 是通过阻遏蛋白结合在受调控的基因上从而促使基因不能表达；如果从该基因上 移除阻遏蛋白后，r n a 聚合酶就能识别基因的启动子，使基因得以成功表达，这 就是正调控。这种阻遏蛋白就是我们所说的反式作用因子。而顺式作用因子则是 基因上与反式作用因子结合，对基因表达起调控作用的基因序列。 转录因子( t r a n s c r i p t i o nf a c t o r ) 是可激活r n a 聚合酶转录起始的蛋白质， 也是转录起始过程中r n a 聚合酶所需的辅助因子。真核生物基因在无转录因子参 与时r n a 聚合酶自身无法启动基因转录，基因处于不表达状态，只有当转录因子 结合在其特异性识别的d n a 序列上后，激活转录机制，基因才开始表达。 转录因子的结合位点( t r a n s c r i p t i o nf a c t o rb i n d i n gs i t e ，调控元件) 是转录因子调节基因表达时，与转录因子结合的区域。按照常识，转录因子 ( t r a n s c r i p t i o nf a c t o r ，t f ) 的结合位点一般应该分布在基因的上有序列， 实际上，它即可分布于基因的下游序列，也可以出现在基因的内部。比如人的 2 1 和2 2 号染色体上，只有2 2 的调控元件分布在基因的上游非编码区。 ： 真核生物的转录调节与原核生物相比，有较大不同，主要区别为：一是原核 生物功能相关的基因常组织在一起构成操纵子。真核生物每个基因都有自己的基 本启动子和调节元件，单独进行转录。同时相关的基因也存在协同调节，拥有共 同顺式元件和反式因子的基因群。二是原核生物只有少数的调控元件，而真核 生物有众多的上游调节元件。三是真核生物具有染色质结构，基因活化首先需要 改变染色质的状态，使转录因子能够接触启动子d n a ，此过程称为染色质改型。 同一家族的转录因子之间的转录调控区有一些区别。转录调控区包括转录激 活区和转录抑制区。它们一般包含d n a 结合区之外的3 0 1 0 0 个氨基酸残基，有 时一个转录因子包含不止一个转录激活区。典型的植物转录因子激活区一般富含 酸性氨基酸、脯氨酸或谷氨酰胺等。 转录抑制区也是转录因子调控表达的重要位点，对其作用机理仍然不是非常 清楚。可能的作用方式有三种：一是与启动子的调控位点结合，阻止其它转录因 子的结合；二是作用于其它转录因子，抑制其它因子的作用；三是通过改变d n a 的高级结构阻止转录的发生n f9 1 0 川。 2 6 模体 模体( 模式) 一般认为是一段保守序列，可以为有其特征性的氨基酸序列。属 于蛋白质的超二级结构，由2 个或2 个以上具有二级结构的的肽段，在空间上相 7 东北师范大学硕士学位论文 互接近，形成一个特殊的空间构象，并发挥专一的功能。也可以为一段保守的 d n a 或r n a 序列，在基因的表达和调控中发挥着重要作用。 东北师范大学硕士学位论文 第三章调控元件预测方法分析 3 1 相关数据库简介 伴随经过实验验证的生物数据的大量积累，产生了一些收集整理调控元件 数据的数据库，国际上最主要使用的数据库是t r a n s f a c 羽和j a s p a r ，前者提供 研究用免费版t r a n s f a c7 0 ，p u b l i c2 0 0 5 以及专业版。转录因子及其结合位 点相关信息由实验获得后，主要通过建模计算搜索获取更多的转录因子绑定位点 信息。为了获得更加准确的预测结果，主要通过以下两种方法： a 从实验获得序列中最大限度提取信息建模型 b 考虑更多的特征属性( 相互作用、进化保守等) 3 1 1t r a n s f a c 数据库 t r a n s f a c 数据库不仅仅含有调控元件的信息，还提供了转录因子与靶基因 的信息。t r a n s f a c 由s i t e 、g e n e 、f a c t o r 、c l a s s 、m a t r i x 、c e l l s 、m e t h o d 和 r e f e r e n c e 等数据表构成。除此之外，还有几个与t r a n s f a c 密切相关的扩展库： p a t h o d b 收集了可能导致病态的突变的转录因子和结合位点：s m a r t d b 收集了与 染色体结构变化相关的蛋白因子和位点的信息；t r a n s p a t h 用于描述与转录因子 调控相关的信号传递的网络；c y t o m e r 表现了人类转录因子在各个器官、细胞类 型、生理系统和发育时期的表达状况。t r a n s f a c 及其相关数据库可以免费下载， 也可以通过w e b 进行检索和查询。 3 1 2j a s p a r 数据库 j a s p a r 数据库由瑞典k a r o li n s k a 医学院的基因组和生物信息中心建立并维 护，收录的转录因子结合位点的信息以pw m 的形式保存，全部免费开放。 它目 前有三个子数据库：j a s p a rc o r e 、j a s p a rf a m 以及j a s p a rp h y l o f a c t s 。 3 1 2 1j a s p a rc o r e 包含了1 2 3 个经文献证实的，非冗余的，且均由已发表的实验确定了的多细 胞真核生物中目标序列的转录因子结合位点。在数据注释中会表明，这些结合位 点是由哪种实验得到的。到目前为止这一子库是非冗余的，也就是不存在多个模 型描述同一转录因子的情况。这也是它与其他同类型数据库( t r a n s f a c ，t e s s ) 相比的主要不同。 3 1 2 2j a s p a rf a m 9 东北师范大学硕士学位论文 包含了转录因子的结构类中共有的结合特性。它的优点在于：因为许多因子 具有相似的目标序列，我们经常就同一位点进行多次预测，j a s p a rf a m 减少了结 果的复杂度：这也可以用来对新发现的p r o f i l e 进行分类，或者指明它的同源转 录因子属于哪一类型的结构类。 3 1 3t r r d 数据库 t r r d 转录调控区数据库是利用不断积累的真核生物基因调控区结构与功能 特性信息构建的。每一个t r r d 的条目里包含基因相关结构与功能特性：转录因 子结合位点、启动子、增强子、静默子、以及基因表达调控模式等等。t r r d 包 括五个相关的数据表：t r r d g e n e s 包含所有t r r d 库基因的基本信息和调控单元 信息) ；t r r d s i t e s 包括调控因子结合位点的具体信息；t r r d f a c t o r s 包括t r r d 中与各个位点结合的调控因子的具体信息；t r r d e x p 包括对基因表达模式的具体 描述；t r r d b i b 包括所有注释涉及的参考文献。t r r d 的主页提供了对这几个数据 表的相关检索服务。 3 2 数据库比较 j a s p a r 提供可靠验证的非冗余调控元件序列模式；t r a n s f a c 含有冗余信息， 模式质量不一。 与商业数据库t r a n s f a c 不同，j a s p a r 是完全开放的资源；而t r a n s f a c 部 其他相关数据库主要有以下几个：t r r d 通过实验收集t f 调节区；t r e d 包 涵t r 元件信息：d b t s s 通过实验获得转录起始位点；t e s s 提供转录元件搜索署 统( 表1 列出本文提及数据库地址) 。 表1 转录因子结合位点数据库 数据摩网址 t 队n c f a c h t t p ：w w w g e n e r e g u l a t i o n c o m j a s p a r h t t p ：j a s p a r c g b k i s e s e l e x d bh t t p ：w w w m g s b i o n e t n s c r u m g s s y s t e m s s e l e x h 丁p s e l e x h t t p ：w w w i s r e c i s b - s i b c h h t p s e l e x a g r i s h t t p ：a r a b i d o p s i s m e d o h i o s t a t e e d u s c p d h t t p ：r u l a i c s h l e d u s c p d t r e d h t t p ：r u l a i c s h l e d u t r e d 1 0 东北师范大学硕士学位论文 3 3 描述调控元件的模型 最早出现的模型是一致性序列，对于结合位点序列中每个位置用最可能出 现的核苷酸来表示，利用通配符表组成一个序列来表达结合位点序列模式。另一 个描述模型是广泛应用的位置权重矩阵模型，利。矩阵中每个元素为一种核苷酸 在一个位置中出现的概率或者是频率。该描述模型存在两个缺点：一是它的长度 是确定而不发生变化的：二是它假定在不同位置上出现的核苷酸是相互独立的。 几乎所有这方面的研究结果都表明，核苷酸在结合位点的不同位置上表现 出了很明显的相关性。为了提高预测水平，研究者提出利用贝叶斯网络描述调控 元件，提出了广义上的位置权重矩阵( g p w m ) ，该方法考虑了任意两个位置间核 苷酸的相关性。 3 4 现有预测方法概述 随着基因组序列测序数据的大量积累和计算技术的快速发展，目前针对调控 元件计算预测的算法越来越多，可提供使用的软件也越来越多。但是这些方法 绝大多数都是以调控元件的特异保守性作为预测识别的出发点，那么根据所使用 的识别策略和搜索对象的不同，现有的预测方法可分成两类：基于保守模体的方 法和基于比较基因组学的方法，前者主要在同一物种基因组的协同调控基因调控 区域内通过发现或搜索过显现的保守模体来预测可能的结合位点而后者则利用 比较基因组学法，例如系统发生足迹法，通过比对多个相关物种基因组的对应区 域来发现具有公共保守特性的模体位点。转录因子结合位点的研究是研究转录因 子及转录过程的基础，它能够促进对基因非编码区和调控元件的研究对于揭开非 编码区的神秘功能有重要意义；对于研究转录调控网络和基因间相互作用揭示生 命过程具有重要意义； ： 调控元件的预测算法可分为三种：d en o v o 算法；结合c h i p c h i p 的预测 算法：系统发育足迹分析法n 4 13 ”1 。 3 4 1d en o v o 预测算法 d en o v o 预测算法n 盯也就是从头进行预测，它不利用调控元件的先验信息， 仅凭借计算方法在共调控的序列集合搜索模体。其基本方法是，输入一组共调控 的序列，用计算方法搜索在这些序列中的非编码序列中富集的模体。此类方法较 多，如m e m e ；c o n s e n s u s 别；a 1 i g n a c e 引，m o t i fs a m p l e r ，b i o p r o s p e c t o r 等 等。但是由于目前对生物转录调控过程仍然缺乏透彻的了解，也缺乏标准的数据 和合适的评价标准，这些软件的预测效果很难评测。t o m p a 钔对1 3 个使用d e n o v o 方法的软件进行评测，并提出多种统计学指标来评测软件。经过研究也发 东北师范大学硕士学位论文 现如果允许软件同时预测出两个模体结果，那么预测的准确率将有明显提高。 另外，在生物体内很多转录过程是由多个转录因子组合调控的，一些学者 提出了可以预测多个调控元件构成模块的算法。这些算法不仅在模拟数据集以及 真实数据上都能准确的预测出调控元件模块，而且对单独的调控元件的敏感度也 优于一般的d en o v o 预测算法，这也很好的证明利用多个转录因子的相关信息能 够提高预测的效果。 d en o v o 预测算法通常需要利用生物学实验数据对基因功能的分析，比如 c h i p c h i p 产生的数据等等。这使d en o v o 检测算法只能对单独物种进行预测。 3 4 2 结合c h i p - c h i p 的预测算法 c h i p - c h i p 实验7 1 提供了大量的实验数据。这种实验通过结合适当的生物信 息学方法就可以较准确地预测调控元件。 在c h i p c h i p 实验芯片上，每个探针的值表示着对应调控元件与转录因子结 合的能力强弱。这一类中已有方法的区别在于，对这个值与结合能力间的关系作 的假设并不相同：有的软件将探针的强度从高至低排序，并分为高和低两组，高 强度组的结合能力较强；而也有一些软件则将探针依照对应的强度值排序，并用 非参数方法进行统计分析。 3 4 3 系统发育足迹分析法 近几年来，许多物种的基因组完成了测序工作，这也促使系统发育足迹分析 法n t “1 3 3 在调控元件预测中使用的越来越多。此类方法通过比较不同物种的序列 来搜索在多个物种之间保守的模体。这种方法的基本原理是，假设调控元件具有 调控基因的功能，那么在进化中就应该相对的保守，进化速度应该慢于不具功 能的非编码序列。那么预测调控元件就转化为在多个物种的同源基因中搜索对应 基因间序列上保守的模体。一些基于此方法的研究取得了较好的预测结果。 在比较进化相似程度较高的物种时，存在非常多没有调控功能的序列，它们 的保守度也很非常高，这就给调控元件的预测加大了难度。将不同物种的进化关 系和进化距离等信息都考虑进算法当中，为调控元件和背景序列建立不同的进 化模型，而不同软件之间的区别在于，它们选用的进化模型是不同的，选择搜索 模体的算法也是不相同的。 3 5 预测计算方法分类 根据算法的搜索策略，可将算法分为两类n ，1 3 3 ：一类是穷尽式搜索算法，这种 方法比较简单，但是计算复杂的较高，只能应用于较短的调控元件搜索。另一种 是启发式算法，它是一种近似计算，一般的流程是第一步对调控元件进行描述， 1 2 东北师范大学硕士学位论文 然后不断的迭代，直到迭代终止条件满足为止。这类方法的计算复杂度比较低， 比较适合在大的空间搜索，其缺点是不能保证得到想要的最优解。大部分机器学 习方法都属于启发式算法，比如期望最大化算法，g i b b s 采样算法，h m m 算法等 堑 寸0 3 5 1 计数法 计数法统计出所有可能出现的模体，同时对它们进行计数。利用得分函数计 算模体的分数，将分数从大到小排序，排在前面的模体是调控元件的概率最大。 此方法是最直接、最简单的穷尽搜索算法。这是种方法的时间复杂度与模体的长 度呈指数正比，所以只适合于较短的调控元件预测。 3 5 2w o r d u p 算法 w o r d u p 算法是一种在序列中选择显著子序列的方法。调控元件的组成一些 非随机的短寡核苷酸序列。调控元件和蛋白质结合位点的长度是可变的。w o r d u p 方法允许对一组在功能上有一定联系的、而且没有进行过比对的序列进行分析， 选出它们之间共同的具有特定生物学功能的子序列。也可以进一步对找出的单词 进行分类，将所有的显著统计意义单词通过聚类的方法分成不同的模式组。对每 一个组中的序列进行多序列比对，得到每一个类的比对。然后分析每个类的多重 序列比对结果，提取特征，作为一个调控元件所应具备的特征。 3 5 3 删算法 删算法n 4 地蚓是建立在期望最大化算法上的，并进行了改进。此算法的目的 是：在一组没有先验信息的共调控序列中，如果它们中存在着共同的调控元件， 通过此方法可以预测得到调控元件的位置。算法的基本思路是：先对序列集建立 二元有限混合模型，再运用最大似然估计法对模型的参数值进行估计。而对于得 到的调控元件模型，需要确定其统计学的显着性。显着性可以从序列模式的信息 含量、敏感性、与背景序列匹配的概率等不同方面进行评估。 东北师范大学硕士学位论文 第四章改进图算法及在调控元件预测中的应用 4 1 图论基础 一个无向图( u n d i r e c t e dg r a p h ) g 记作g = ，其中y 是一个非空有 限集合，y 中的对象称为结点或顶点( v e r t e x ) ：是由不同顶点的有序对构成的 集合( 元素可重复出现的集合) ，称为g 的边集( e d g es e t ) ，f 中的元素称为 无向边或简称边( e d g e ) 。 一个有向图( d i r e c t e dg r a p h ) 岔记作g = ，其中矿是一个非空的有 限结点( 或顶点) 集；占是笛卡尔积以矿的多重子集，其中的元素称为有向边 ( d i r e c t e de d g e ) ，也简称边或弧( a r c ) 。 设g = 为一无向图，v v ，与顶点v 相关联的边的总数数称为y 的度 数，简称度( d e g r e e ) ，记作的d ( 访。 设g - - 为一有向图，v v ：以顶点y 作为起点的有向边个数，称为矿 的出度( 0 u t d e g r e e ) ，记作d + ( 1 ，) ：顶点y 作为边的终点的次数称为y 的入度( i n d e g r e e ) ；记作d 一( v ) ；y 作为边的端点的次数称为e 的度数，简称度( d e g r e e ) ， 记作d ( v ) ，显然d ( v ) = d + ( v ) + d 一( 1 ，) 。 g = ，g = y ，e ，是两个图。若矿v ，且e e ，则称g 是 g 的子图( s u b g r a p h ) 。g 是g 的母图( c o n t a i n e dg r a p h ) ，记作g 冬g 。 如果y 。cv 或e ce ，那么g7 是g 的真子图( p r o p e rs u b g r a p h ) 。 如果y = v 且辱e ，那么g 是g 的生成子图( s p a n n i n gs u b g r a p h ) 。 4 2 图的应用 借助于赋权图( w e i g h t e dg r a p h ) 理论n 制，给出一组序列，我们在每条序列 选取长度为w 的片段。每个片段作为图中的一个结点，利用打分函数对每两条片 段进行打分，这样在不同的结点之间赋与不同的权值： 首先，对序列片段进行打分，如图1 所示在联配图中从开始结点到终结结点 东北师范大学硕士学位论文 的每条路径就对应一个分数之和。那么序列之间的最优比对就对应于图中从开始 结点到终结结点的一条权值之和( 打分值和) 最大的路径。 agggtgcg a王oo0o 2 5ooo goll王1 g i王 o 2 5王 gol王王0lo 2 5l c0o 2 5o 2 5o 。2 5oo 2 5王o 2 5 coo 。2 50 2 50 2 5oo 。2 5王o 2 5 go王王 王o王o 2 5l coo 。2 50 。2 5 o 2 5o0 。2 5王o 2 5 go王王l0lo ，2 5 王 图1联配图 其中，序列片段比对的打分规则如下：如果两个片段的碱基类型相同那么得 分为l ；如果碱基类型不相同，那么按照大多数算法的类型得分为o ，而我们采 取另一种方法，当a 与t ，g 与c 配对时得分为o 2 5 ，而当a 与g 、a 与c 、g 与 t 配对时得分才为0 。之所以采用这种方式是因为序列在进化过程中会出现碱基 转换和颠换，d n a 分子中某一个碱基为另一种碱基置换，导致d n a 碱基序列异常， 是基因突变的一种类型。可分为转换和颠换两类。转换是同类碱基的置换( a t g c 及g c a t ) ，颠换是不同类碱基的置换( a t t a 或c g ，g c c g 或t a ) 。 碱基置换的后果可能有以下几种阳1 仉1 1 1 ： 1 同义突变，密码子第三位碱基发生的置换，由于遗传密码存在的简并性， 经转录和翻译过程后产生所对应的氨基酸并没有发生变化。 2 错义突变，密码子中的碱基发生置换使它的意义发生改变，经转录和翻译 后所对应的氨基酸也发生了改变。 3 无义突变，密码子中的碱基置换使密码子变为终止密码，导致肽链合成提 前结束。 4 终止密码突变，密码子中的碱基置换使终止密码转变成某一种氨基酸密 码，肽链的合成将延长直到遇到第二个终止密码才会结束。 通过以上生物学知识可以知道转换相对于颠换虽然同样发生了碱基的变换， 但转换碱基类别并没有发生变化，依然是嘧啶或者嘌呤，所以对于序列功能影响 较小，对转录翻译后的氨基酸序列影响也较小。 同时，本文考虑了进化过程中出现的碱基插入与缺失现象。修改了打分函数， 在计算最终的得分值时，根据情况选择的不同的计算路线，如图所示： 东北师范大学硕士学位论文 ag6gt6cg a l oooo 2