（计算机应用技术专业论文）基于一种图方法识别转录因子结合位点.pdf

独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究 工作所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡 献的个人和集体，均已在文中作了明确的说明。本声明的法律结果由本人 承担。 学位论文作者签名：赵凤会日期：o 6 d 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的 复印件和电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其它复制手段保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：叁鱼玺 日 期：趁f 垒：6 ：0 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： _ _ 。 一 摘要 生物信息学自上世纪9 0 年代人类基因组计划全面开展以来，已成为2 1 世纪自然科 学的重要前沿领域之一。随着越来越多的模式生物测序完成，开始进入后基因组时代。 其中转录调控是后基因组时代的一个重要研究课题。大量研究表明，基因的表达是相互 影响相互制约的。研究这种复杂的相互关系已经成为科研工作者们一个重要的研究领 域。其中，转录因子结合位点是位于基因上游区域控制基因转录的一段d n a 序列。转录 因子结合位点的识别对构建转录调控网络具有不可替代的作用，能够高质量的预测转录 因子结合位点已经成为无法回避、亟待解决的研究课题。 目前，已经有大量的方法用于识别转录因子结合位点，大致可分为基于保守模体和 比较基因组学两种方法。本文使用一种基于图的方法识别转录因子结合位点。大量的研 究发现一般在转录因子结合位点中都存在一段高度保守的长度为3 - 5 b p 的短序列，我们 称之为核。本文根据这一特性，首先在一组共调控基因上游区域搜索共同存在的高度保 守的核；然后，根据用户的要求向两边扩展得到转录因子结合位点序列。本文使用啤酒 酵母基因组数据进行实验。实验结果表明，该方法能在现有的实验条件下得到比较好的 结果。并与3 个经典的算法进行比较，在3 个性能统计参数上都有明显优势。结果显示， 本文的方法是有效的。 关键词：生物信息学；转录因子结合位点；图方法；似然比检验；信息含量 a b s t r a c t s i n c et h el a s t9 0 sc e n t u r y , t h ed e v e l o p m e n to fh u m a ng e n o m ep r o j e c ti n d i c a t e dt h a t b i o l o g yh a ss t e p p e di n t ot h ea g eo fg e n o m e ，b i o i n f o r m a t i c sh a sb e e no n eo ft h ei m p o r t a n t f i e l do fs c i e n c e t h ep o s tg e n o m ee r as t a r t sw i t hm o r ea n dm o r e m o d e lo r g a n i s m ss e q u e n c e d a n dt h et r a n s c r i p t i o n a lr e g u l a t i o ni sa ni m p o r t a n tr e s e a r c ht o p i ci nt h ep o s t - g e n o m i ce r a a l a r g en u m b e ro fs t u d i e sh a v es h o w nt h a tg e n ee x p r e s s i o ni se f f e c t e de a c ho t h e r s t u d yo ft h i s c o m p l e xr e l a t i o n s h i ph a sb e c o m ea ni m p o r t a n tf i e l d 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 si sa s e g m e n to fd n aa n dl o c a t e di nt h eu p p e ra r e ao fg e n ea n dc o n t r o l t h et r a n s c r i p t i o n i d e n t i f y i n gt 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 sh a v ea ni r r e p l a c e a b l er o l eo nt h ec o n s t r u c t i o no f t r a n s c r i p t i o n a lr e g u l a t o r yn e t w o r k s p r e d i c t i n gh i g h l y - q u a l i t yt r a n s c r i p t i o nf a c t o rb i n d i n g s i t e sh a sb e c o m ea nu n a v o i d a b l ea n du r g e n t l yr e s e a r c ht o p i c s t h e r ea r ea l a r g en u m b e ro fm e t h o d sf o ri d e n t i f y i n gt 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 s ，a n d i tc a nb ed i v i d e di n t ot w ow a y s ：c o n s e r v a t i v em o t i fb a s e da n dc o m p a r a t i v eg e n o m i c s 、t h e m a pm e t h o di sm o r ep o p u l a ri nr e c e n ty e a r s i nt h i sa r t i c l eag r a p h b a s e da p p r o a c hi su s e dt o i d e n t i f yt 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 s t h es c i e n t i s t sf o u n dt h a ti ng e n e r a lt r a n s c r i p t i o n f a c t o rb i n d i n gs i t e sh a v eah i g h l yc o n s e r i , e ds h o r ts e q u e n c eo f3 - 5 b pa sc o r e b a s e do nt h i s f e a t u r e ，f i r s t l yi nt h eu p s t r e a mr e g i o no fag r o u po fc o - r e g u l a t e dg e n eh i g h l yc o n s e r v e dc o r ei s s e a r c h e d ；t h e n ，a c c o r d i n gt ot h e u s e r sr e q u e s t ，t h e ya r ee x t e n d e do nb o t hs i d e s t ob e 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 s t h i sa r t i c l em a k e se x p e r i m e n t sw i t hy e a s tg e n e t i cd a t a e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dc a no b t a i nm o r eg o o dr e s u l t si n t h el i m i t e d e x p e r i m e n t a lc o n d i t i o n s a n dc o m p a r e 、析n lt h r e ec l a s s i ca l g o r i t h m s t h e r ei saf e wb e t t e r p e r f o r m a n c e s t h er e s u l t ss h o wt h a tt h em e t h o di sv a l i d k e yw o r d s ：b i o i n f o r m a t i c s ；t r a n s c r i p t i o n a lf a c t o rb i n d i n gs i t e s ；g r a p hm e t h o d ；l i k e l i h o o d r a t i ot e s t ；i n f o r m a t i o nc o n t e n t 目录 摘要i a b s t r a c t ：i i 目勇之i i i 弓i言1 第一章绪论2 1 1 生物信息学2 1 2 课题背景3 1 3 国内外研究现状。3 1 4 本文主要研究工作4 1 5 本章小结5 第二章转录因子结合位点识别方法简介6 2 1 引言6 2 2 基于共调控基因启动子序列的方法6 2 2 1 基于单词的方法6 2 2 2 概率算法7 2 2 3 机器学习算法9 2 2 4 其他算法9 2 2 5 集成方法1 0 2 3 基于系统发生足迹的方法1 0 2 4 基于共调控基因的启动子序列和系统发生足迹的方法1 1 2 5 本章小结1 1 第三章背景知识简介1 2 3 1 位置频率矩阵1 2 3 2 似然比检验1 3 3 3 马尔科夫模型1 4 3 4 信息含量1 4 3 5 本章小结1 4 第四章基于图的方法识别t f b s 1 5 4 1 引言。1 5 4 2 寻找核1 5 4 2 1 建图15 4 2 2 搜索子图1 6 4 3 似然比检验1 7 4 4 合并18 4 5 扩展模式j 18 4 6 排序19 4 7 本章小结1 9 第五章算法实现和结果分析。2 0 5 1 引言2 0 5 2 算法实现2 0 5 2 1 实验数据2 0 5 2 2 实验环境：2 4 5 3 对比实验2 4 5 4 性能参数2 4 5 5 结果分析2 4 5 5 1 实验结果2 4 5 5 2 结果对比2 7 5 6 本章小结。2 8 总结。2 9 参考文献：3 0 致谢3 3 在学期间公开发表论文及著作情况。3 4 东北师范大学硕士学位论文 引言 生物信息学( b i o i n f o r m a t i c s ) 是一门新兴学科，是计算机科学及生命科学高 度发展而产生的交叉学科。它是2 1 世纪最前沿的领域之一【l j 。它的发展已渐渐 进入到人们的生活当中，吸引着越来越多的有识之士加入到研究之中。高度膨胀 的不计其数的生物分子数据包含着怎样的信息，是人们迫切想知道的。从如此纷 杂的分子序列中研究结构及功能，已经经历了一个漫长的过程。虽然已经取得了 毋庸置疑的成绩，但已清晰的认识到摆在人类面前的将是更严峻的挑战。越来越 复杂的问题摆在这里，就需要更具创新的技术的发展和应用。 在对基因进行大量研究之后，科学家们又把目光转向了在真核生物中占大多 数的非编码d n a ，非编码区到底有没有用呢? 答案是肯定的。其潜力正在慢慢的 展现在人们的眼前。其中对非编码区中包含的对基因表达进行调控的区域已经得 到公认。对基因的调控是一系列的不同功能的蛋白质分子及各种分子结构以一定 的规则在恰当的时空与d n a 序列相结合来达到调控的目的。由中心法则可知， 转录是基因表达成蛋白质的第一步，是生物信息表达的第一步，对整个生物机体 的活动是至关重要的。理解基因间的调控机理是分子生物学的重要挑战。重新构 建调控网络有助于理解基因间复杂的调控机制，有助于探索生命的本质。生物的 调控网络的构建是一个重大挑战【2 1 。 转录因子是基因转录起始过程中与r n a 聚合酶相结合的辅助蛋白质因子。转 录因子与d n a 序列结合的部分称为转录因子结合位点( t r a n s c r i p t i o nf a c t o r b i n d i n gs i t e s ，简称t f b s ) ，它的识别是构建调控网络的第一步。已经有大量的方 法用于识别转录因子结合位点，但转录因子结合位点序列通常都很短，特异性不 是很强，为识别工作带来了很多的困难。目前的方法尚不能很有效的识别出大量 的转录因子结合位点。有效且高效的方法亟待开发。 本文在大量算法进行研究的基础上，使用了一种基于图的方法1 3 】来识别转录 因子结合位点。使用啤酒酵母的基因数据进行实验得到了很不错的结果。 东北师范大学硕士学位论文 1 1 生物信息学 第一章绪论 上个世纪9 0 年代以来，在人类基因组计划的带动下，各种基因组测序计划 蓬勃开展起来，分子结构测定技术得到突破，与此同时i n t e r n e t 的普及，不计其 数的生物数据迅速膨胀起来。数以亿计的序列包含着生物体的生命本质。通过分 析这些数据得到数据所包含的深刻内涵，是人类面临的巨大挑战。生物信息学 ( b i o i n f o r m a t i c s ) 应运而生，它是利用计算机这一工具，结合数学理论，分析生 物数据来完成科研课题的一门新兴学科。 在这一交叉领域中，各个不同领域的科学家都参与其中，各自发挥自己的作 用、相互合作，取得了很大的成绩。传统的生物学解决问题的方法是利用实验， 然而生物实验需要很长的周期，在生物信息学的帮助下，生物学家可以从理论出 发，利用生物信息学提出假设，然后再回到实验中来验证自己的假设，节省了大 量的宝贵时间，也缩短了科研周期。具体来说，生物信息学就是通过计算机存储 d n a 和蛋白质序列，研究科学的算法，对序列进行分析、比较和预测，从中发现 生物分子信息组织和表达的规律，从而认识生物分子的作用，探索生命的起源和 进化，进而加深对生物世界的认知。 目前生物信息学主要包括基因组学和蛋白质组学。在短短的近2 0 年的生物 信息学的发展中，基本上形成了下面几个研究重点方向：序列比对( s e q u e n c e a 1 i g n m e n t ) 、结构比对、蛋白质结构预测、计算机辅助基因( 蛋白质编码基因) 识别、非编码区分析和d n a 语言研究、分子进化和比较基因组学、功能基因组学 和功能蛋白质组学、基于结构的药物设计、生物信息数据库的设计与实现及其它。 生物信息学虽然取得了长足的发展，但是仍有不可避免的问题摆在眼前。生 物信息学是基于分子生物学与多种学科交叉而形成的一门新学科，由于各学科之 间的联系并没有达到特别紧密的程度，现有的形势仍表现为各种学科的简单堆 砌。在处理大规模数据方面，尚没有行之有效的一般性方法；而对于大规模数据 内在的生成机制也没有完全明了，这使得生物信息学的研究短期内很难有突破性 的结果。要完全破译生物序列以及相关的内容，我们还有相当长的路要走。 2 东北师范大学硕士学位论文 1 2 课题背景 转录调控是生物信息学的一个重要研究领域h 1 。转录调控是站在更高层次上 分析基因间的作用，为理解生物的生命过程提供更直观的参考，具有重要的作用。 转录过程开始于转录因子结合于待转录基因附近的转录因子结合位点的复杂过 程。因此转录因子结合位点的识别具有重要的意义。 目前已经有大量的方法用于识别转录因子结合位点。由于转录因子结合位点 通常都很短，只有几个到几十个碱基，特异性不强，通常预测结果精度不高。亟 需预测准确率更高的方法。近年来图的方法被广泛使用，此种方法能够更直观的 表示生物数据，从而也就更可能准确的预测各种生物结果。此类方法在不同的领 域都有成功的应用。本文利用一种基于图的方法，基于保守模体，使用位置频率 矩阵表示转录因子结合位点，在比较低端的实验条件下得到了不错的实验结果。 1 3 国内外研究现状 转录因子结合位点识别方法大致可分为基于模体和基于比较基因组学两种 方法1 5 】。比较基因组学认为物种在进化过程中共同保留下来的保守序列是具有某 种重要的功能的。可以通过比较不同物种的同源基因的非编码区来发现公共保守 模体，作为候选的转录因子结合位点。此类方法对物种的选取要求很高，进化距 离太长或者太短都可能使实验失败。 基于模体的方法主要是在一个物种基因组的共调控基因的调控区域内搜索 或发现过表达的保守模体来预测可能的转录因子结合位点。此类方法基于共调控 基因具有相似的调控序列这一假设开展的。常用的模体表示方法有以下几种： 1 ) 一致性序列模型，代表为c o n s e n s e ，在每个位置上使用该位置上出现 碱基次数最多的碱基表示。此种方法只能粗略的表示每个位置上碱基出 现的情况，对碱基分布描述的不够完整。 2 ) 比对谱模型，位置频率矩阵及位置权重矩阵被广泛使用。此种模型更精 确的表示了碱基分布情况。此种模型为一个4 * n 的矩阵，行列分别为序 列和在序列每个位置上出现的碱基( 即a 、c 、g 、t ) ，矩阵的元素为在 3 东北师范大学硕士学位论文 每个位置上该个碱基的出现频率。位置权重矩阵为位置频率矩阵的变 种。 3 ) 隐马尔科夫模型，以隐马尔科夫模型为基，用隐马尔科夫模型的各个概 率分别表示不同碱基的相关。这在某种意义上也体现了t f b s 的生物学 意义，因此而被广泛的使用。不同的结合方式得到不同的模型。且已经 有很大的发展。 4 ) 其他，包括贝叶斯网络以及字典模型等诸多模型也有较多应用。 另一类为基于比较基因组学的方法，鉴于越来越多的模式生物基因组被测 序，在基因组层面上在多个物种之间进行序列比较分析的可能性也越来越大。基 于比较基因组学的方法越来越多的被科研人员使用，且取得了骄人的成绩。但此 类方法通常运算量很大，对数据选取要求较高。 1 4 本文主要研究工作 本文的t f b s 识别方法主要是基于一种图的方法。转录因子结合位点模型选 择位置频率矩阵( 即p f f m ) 。使用似然比检验进行检验。建立一种打分方法对所 得候选p f f m 进行排序。最后根据个人需要选择所需的转录因子结合位点。 大量的研究表明，转录因子结合位点通常有一小段高度保守的序列，通常称 之为核。本文利用一种图的方法在一组共调控基因的上游区域搜索这样的核作为 转录因子结合位点的基础，再向两边扩展，根据用户输入参数来确定扩展的长度。 所得的p f f m 作为转录因子结合位点的候选，此时得到的候选必定有很多假阳性 存在，使用似然比检验进行过滤，之后所得作为最后的候选转录因子结合位点。 由于扩展过程中会出现交叠的p f f m ，需要对交叠的p f f m 进行合并，作为转录 因子结合位点的候选集。最后使用打分函数对候选集中的p f f m 进行打分排序， 可以根据用户需要选择预测转录因子结合位点的个数。 从数据库中随机选取多组实验数据进行实验，并与传统方法进行比较，所得 结果显示了本文所研究方法的优越性。 文章的内容安排如下： 第一章：简要介绍生物信息学背景知识，阐述了转录因子结合位点识别的研 究目的和意义，国内外研究现状，本文的主要研究内容及文章框架。 第二章：该章内容对现有转录因子结合位点的识别方法进行较详尽的介绍。 第三章：这一章对本文所使用的基础知识进行详尽的介绍。 4 东北师范大学硕士学位论文 第四章：本章对本文所做的工作进行详尽的叙述。 第五章：详细介绍了实验环境、数据选取以及对比实验，给出实验结果，证 实了本文的方法在识别转录因子结合位点的有效性。 1 5 本章小结 本章简要的介绍了生物信息学中转录调控及转录因子结合位点识别方法的 发展，以及识别转录因子结合位点的意义。介绍了基于模体及基于比较基因组学 两种识别方法。最后扼要的介绍了本文主要研究工作及本文的结构框架。 5 东北师范大学硕士学位论文 2 1 引言 第二章转录因子结合位点识别方法简介 识别转录因子结合位点的方法很多，按照分析对象的不同可分为基于共调控 基因启动子序列和比较基因组学的方法( 即系统发生足迹法) 。本章将概括性地介 绍几种典型方法以对此类方法有个大致的了解。 2 2 基于共调控基因启动子序列的方法 早期的大多数方法都是基于这种方法的，在共调控基因的启动子区域识别在 统计上过表达的模体。下面分别介绍几种此类方法。 2 2 1 基于单词的方法 此类方法是穷尽搜索所有序列并精确的计算单词的出现次数，使用概率统计 的方法计算过表达的单词为预测结果。 ： v a nh e l d e ne ta i 基于此类方法开发了最简单的识别方法【2 0 】。对于简单的并且 保守性很高的模体有较好的效果。该方法的缺点是模体的长度是固定的。t o m p a 解决了这个问剧2 1 1 。他提出了一种精确的基于单词的方法，在d n a 序列中找到 短的模体。文章中使用了z 分数的概念。x 是长度l 的随机序列，即序列中的碱 基是随机的独立的来自于背景序列，或者是符合背景核苷酸分布的马尔科夫链得 到的序列。假设p 。是x 中至少出现一次允许c 个替换的k - m e r 的概率。在n 条 相互独立的随机序列x 中至少出现一次s 的期望值是e p 。z 分数计算如下： z = ( u s e p , ) 4 e p , ( 1 一凤) 公式2 1 z 分数用于表示序列s 超过期望值的标准化。可以表示序列s 的过表达程度。通 过计算每个短序列s 的z 分数来判断是否符合要求，最终达到预测的效果。 s i n h aa n dt o m p a 使用相似的方法提出了y m f 算法( y e a s tm o t i ff i n d e r ) 1 2 2 1 。 6 东：l l ：l j 币范大学硕士学位论文 该算法从已知的酵母的转录因子结合位点得到模体的模型。该算法能够保证得到 有最大z 分数的模体。并在实验中也取得了不错的实验结果。 基于单词的方法还有很多，与其他方法的结合能取得很好的效果。 该方法与图方法的结合也取得了一些突破。 2 2 2 概率算法 该类方法区别于穷尽方法。大多数概率模体发现算法应用统计技术，如e m 算法和g i b b s 采样及其扩展。 ( 一) e m 算法及其扩展 e m 算法即期望最大化算法，是概率统计中经典的算法。是不断迭代使期望值 最大化以达到最终目的的算法。最初e m 算法引进到模体识别中用于蛋白质模体 识别，但也可以用于d n a 模体的识别。 h e r t ze ta 1 开发的模体发现算法是对贪婪算法的一种扩展【2 3 1 。在该算法中， 位点不需要对齐。建立模型的基本假设是每条序列都至少包含一个公共的位点。 但是位点在序列中的位置是未知的，使用e m 算法对位点的位置进行预测。 m e m e 算法【2 4 】是对e m 算法的推广。该算法用于在一组序列中发现未知的模 体。包括以下三方面的改进： 1 ) 使用出现在序列中的子序列作为e m 算法的起点，从而增加找到全局最 优模体的概率。 2 ) 去掉了每个序列都包含至少一个位点的限制。 3 ) 在已经得到的模体中以一定的概率去掉其中的一部分，因此当不同的模 体出现在不同的序列以及一条序列包含多个模体的时候能够在一组相 关的序列中发现不同的模体。 ( 二) g i b b s 采样算法及其扩展 g i b b s 采样算法【2 5 1 是一种得到广泛应用的概率算法。该算法最初也是应用于 蛋白质序列。它是一种马尔科夫蒙特卡洛算法( 1 i pm c m c 算法) ，每一步得到的结 果仅依赖于上一步得到的结果，下一步又是不确定的。下面简要介绍一下该算法。 假设n 条序列s 1 ，s 2 ，s n ，在该组序列中寻找宽度为w 的相似的短序列片段。在 迭代的过程中维护两个数据结构，长度为w 的短序列片段组成的p f f m ，以及模 式在每个序列中出现的位置。最终要寻找最可能和最公共的模式。所使用的打分 函数即相关模式的概率与背景概率的比值最大化。算法初始化为随机的位置。在 迭代的过程中进行以下两个步骤： 1 ) 更新：选择一条序列z ，在所有序列中( 不包括z ) 从当前的位置开始更新 7 东北师范大学硕士学位论文 p f f m 以及背景序列的概率。 2 ) 采样：对于序列z 中每一个宽度w 的序列片段，使用p f f m 和背景的概率 分布分布计算概率，计算二者的比值。 以每个片段的比值在所有片段比值总和的比重为概率随机选择一个序列片 段。新的片段的位置代替原来的位置。重复这两个步骤直达达到一定的迭代次数 或者结构不再更新为止。 g i b b s 采样算法的变种有很多。a l i g n a c e 【2 6 】是一个基于g i b b s 采样算法开发 的模体发现算法。算法的结果返回一系列在输入序列中过表达的用位置权重矩阵 表示的模体。该算法中用到信息含量的概念，在一组联配的序列中每一列都是信 息含量的最大值。与原始的g i b b s 采样算法的区别主要如下： 1 ) 模体的模型不同，a l i g n a c e 中的背景序列中碱基的比例来自于预测生物 的生物基因组。 2 ) 同时考虑d n a 的双链，并且不允许出现重叠的位置。 3 ) 每一次只搜索一个模体并且重复，而不是同时搜索多个模体。 4 ) a l i g n a c e 使用了一个改进的接近最优化的采样方法。使用m a p ( m a x i m u m 口p r i o r il o g 1 i k e l i h o o d ) 打分来判断不同的模体。m a p 度量一个模体的过表 达的程度。m a p 的主要缺点是对于基因组中分布广泛的模体打分很高， 其他情况则表现不佳。 m o t i f s a m p l e r 冽是另一个经典g i b b s 采样算法的扩展。与经典g i b b s 采样算法 相比较有以下2 处改进： 1 ) 使用了一个概率分布来估计一个模体在一条序列中出现的次数。 2 ) 包括了高阶的马尔科夫链背景模型。 用该方法进行了大量的实验，都能够预测出预期的模体。 b i o p r o s p e c t o r 2 8 1 是运用g i b b s 采样的策略使用共调控基因启动子序列的算 法。它与原始g i b b s 采样算法的区别如下： 1 ) 使用了0 3 阶的马尔科夫链背景模型。模型的参数可以由用户给定或者 由一个序列文件计算得到。 2 ) 模体的显著性是用根据蒙特卡洛方法估计得到的模体得分分布来计算 的。 3 ) 它考虑到了为有一个空格的模体和回文结构的模体建模。 该算法的作者成功的利用该算法找到了几个蛋白质的结合位点。 8 东北师范大学硕士学位论文 2 2 3 机器学习算法 f m g a 算法【2 9 】是基于遗传算法g a 开发的，它在转录起始位点的2 0 0 0 b p 到 1 0 0 0 b p 区域范围内查找潜在的模体。遗传算法中的主要两个过程是交叉和变异。 在f m g a 算法中，交叉是使用一种特殊的空位罚分来产生优秀的下一代，变异是 通过使用位置权重矩阵p w m 来保持完全保守的位置完成的。算法也使用重排的 方法避免算法陷入局部最小化。陷入局部最小化是机器学习算法的通病，之后就 不能继续向全局最优化发展，即不能产生更优的子代。作者称该算法要优于 m e m e 算法和g i b b s 采样算法。 l i u 甜讲开发了一种自组织神经网络结构用于d n a 和蛋白质序列的模体发 现曙o 】。神经网络包括多层，每一层在不同的水平上进行分类。使用层次结构使得 每个模式在整个输入空间的小的子空间里被分类，从而可以维持一个低的计算复 杂性。通过使用自组织的神经网络维持搜索算法高的可靠性，这是因为当输入数 据增大时，神经网络将会自动增长以考虑到所有的模式以及每个模式都有相同的 关注。在某些方面该算法超过m e m e 算法和g i b b s 采样算法。同样算法也适用于 长的d n a 序列。 2 2 4 其他算法 k i n g s f o r de t 讲使用一种数学编程的方法搜索d n a 模体，搜索给定长度的子 序列并且两两之间的距离和最小【3 。i l p ( i n t e g e rl i n e a rp r o g r a m m i n g ) 禾l j 用了序列对 之间的距离离散的特性。为了降低l l p 的计算复杂性，增加了线性规划的限制的 指数集，并且使用了一个能找到违反限制的有效的分离算法，从而获得了多项式 时间。为了证明算法的有效性，作者对e c o i l 基因组进行了识别d n a 模体实验， 该算法的性能可与部分基于g i b b s 采样的算法相媲美。 k a p l a n 甜a 正使用了一种基于结构的方法在没有任何d n a 结合先验知识的情 况下识别d n a 模体【3 2 1 。该算法结合d n a 序列数据和转录因子蛋白质结构信息来 推断氨基酸核苷酸的识别倾向。这些信息用于预测同一家族的转录因子的结合 位点。作者研究了c v s 2 h i s 2 锌指结构蛋白质家族并显示得到的d n a 识别倾向与 实验结果是兼容的。 在大量识别方法对酵母和其他组织有效预测的同时，对高等组织也显示了很 坏的性能。h o na n dj a i n 开发了一个确定性的模体发现算法用于人类基因组数 据【3 3 】。该算法依赖于优化搜索数据的索引技术。一个简单的打分函数，对结合 输入数据中的保守倾向和相对于基因组不具代表的倾向进行打分。快速的搜索过 9 东北师范大学硕士学位论文 程对它起到双倍的效果。 2 2 5 集成方法 h ue t 讲开发了一种集成算法用于提高d n a 模体发现算法的预测精度【3 4 1 。 e m d 算法【3 5 】是基于聚类的集成的模体发现算法，它将一个或多个的基础模特发 现算法的多次运行的预测结果进行综合。e m d 算法的潜力在于它能利用各个基 础模体算法得到的好的结果，从而得到更好的预测结果。作者在研究中使用了5 个基础模体发现算法，包括a l i g n a c e ，b i o p r o s p e c t o r ,【3 引，m d s c a n m e m ea n d m o t i f s a m p l e r 。并且在同一个数据平台上进行测试，在核苷酸预测水平上的预测 精度提高了2 2 4 。该算法的优势在于，算法的性能总是能超过至少也不会低于 单个基础算法的预测精度。 2 - 3 基于系统发生足迹的方法 基于系统发生足迹的方法优于基于共调控基因的主要优势在于不需要一个 可靠的算法来识别共调控的基因。使用系统发生足迹的方法，只要在同源序列中 模体充分的保守，那么识别一个基因的模体都是可能的。该类算法的标准做法是 首先构建一个同源启动子序列的全局多序列联配，然后使用工具来识别保守的区 域。如果选择的同源序列的物种进化距离太近，得到的序列联配会太明显而不具 有太多的信息，从而功能单元的保守程度就不能明显好于背景序列。另一方面， 如果选择物种的进化距离太远，序列的联配就变得很困难甚至是不可能了。所以 基本的方法总是不能有很好的效果。为了克服物种选择的问题，很多的现有的算 法被应用到系统发生足迹方法中。 c o n r e a l 算法【3 刀是一个基于系统发生足迹法的算法。该算法使用用位置权 重矩阵表示的潜在的模体在同源序列之间建立一个锚来指导启动子序列的联配。 该算法与两个全局联配算法l a g a n 和a v i d 使用参考数据比较性能，c o n r e a l 发现了其他两个算法没有发现的保守的转录因子结合位点。 c l i f t e ne t 口，使用系统发生足迹法在酵母基因组中发现了模体【3 剐。该文章在 六个酵母物种的基因组序列中使用序列联配工具c l u s t a lw 搜索系统发生足迹。 使用这个简单的联配技术，找到了很多统计上显著保守的序列模体。这主要是因 为选择了具有最佳进化距离的物种来比较多个基因组序列。 p h y l o n e t l 3 9 j 通过分析几个相关基因组所有的启动子序列并定义了组织的 调控位点的网络系统地识别系统发生地保守模体。该算法为每个启动子构建系统 东北师范大学硕士学位论文 发育谱的然后用b l a s t - l i k e 算法在所有启动子的完整谱空间中搜索来识别保守模 体。作者使用了该算法分析了3 5 2 4 个酵母启动子，识别了包含3 3 1 5 个启动子和 2 9 6 个模体的高度有组织的调控网络。该网络几乎包含了所有当时已知的模体和 超出9 0 的己知的转录因子结合位点。 p h y l o s c a n 是一个扫描算法，它结合了在不同相关物种的同源数据中发现的 匹配位点的证据和基因间区的多个位点的证据，从而更好的发现调控子【删。同源 序列数据可能是多联配，不联配，或者两者的结合。在联配数据中，p h y l o s c a n 统计为数据联配做出贡献的物种的系统发育依赖关系，在非联配数据中，物种的 系统发育独立性作为位点的证据。该算法应用到七个肠杆菌目的物种的真实序列 数据并识别出了新奇的转录因子结合位点。 2 4 基于共调控基因的启动子序列和系统发生足迹的方法 该类算法结合了模体两方面主要的特性，包括过表达及相关物种间的保守 性。将两种算法有机的结合起来有助于提高算法的性能。 2 5 本章小结 本章以数据对象为分类方法对模体发现算法进行了概述。模体发现算法大致 分为基于共调控基因启动子的方法和基于系统发生足迹的方法。由于实验数据量 小而且不需要谨慎地选择物种，因而前一种方法得到了广泛的研究。后一种方法 由于加入了进化信息，因而在某种意义上增加了识别算法的生物意义。本文的方 法就是基于第一种方法进行的。 东北师范大学硕士学位论文 3 1 位置频率矩阵 第三章背景知识简介 位置频率矩阵为一个4 * n 的矩阵，通常行是碱基出现的位置，列是不同的碱 基，矩阵元素为该位置上该个碱基出现的频率。举例如下： 表3 1 序列 acgcaagta ac cc aa c ta tcgc tagta a ggc at g ta acggaagaa acccaac a a tagcatgta a cgctagtt 表3 2 位置次数矩阵 123456789 a6100660 2 7 c062700200 g016100600 t200022061 表3 - 3 位置频率矩阵 123 4 56789 a酶埔00驰酶0 2 87 8 c0 6 8湘7 8 00确00 g0墟 酶 】届 00 6 8 00 t 2 胆 000 2 8拍 0 6 8埔 上述位置频率矩阵为一阶，是一种基本的表示方法。大量的研究表明，d n a 东北师范大学硕士学位论文 序列的碱基之间存在相关性，最常见的为相邻两个之间的依赖关系。根据这一特 性，可以建立二阶的位置频率矩阵。此类位置频率矩阵较一阶的大的许多，行仍 然是出现的位置，但是每个元素为两个位置，列为四种碱基的任意两种组合。仍 以上面一组序列为例来构建二阶位置频率矩阵，结果如下： 表3 - 4 二阶位置频率矩阵 1 、22 、33 、44 、55 、66 、77 、88 、9 a a 0000 4 1 6 00 2 1 6 a c轴60000矾600 a g 1 1 61 1 6 000 4 1 6 00 a t0000 矾6 000 c a000 轴6 0 0班60 c c0矾6 讥6 00000 c g0 4 1 6 00o 000 c t00 0饥600 1 1 6 0 g a0 00 1 1 6 00 1 1 6 0 g c 00轴600000 g g0 1 1 6 ! 2 6 00000 g t000000轴60 t a ! 1 6 000 1 1 6 00轭6 t c 1 1 6 0000000 t g00000 饥6 00 t t0000000 1 1 6 本文的数据模型采用一阶位置频率矩阵，在计算似然比打分的时候使用的是 二阶位置频率矩阵，使用二阶位置频率矩阵计算整个啤酒酵母基因组的碱基之间 的相关性以及所有转录因子结合位点数据的碱基之间的依赖关系。因此在此分别 介绍此两种位置频率矩阵。 3 2 似然比检验 似然比检验是进行假设检验的一种方法。对于原假设h o 和备择假设h 1 ，使 用决策规则表达式“如果f l ( x ) f o ( x ) k ，则拒绝原假设h o ”。k 值由检验的显著性 水平决定。f o ( x ) 、f l ( x ) 分别为样本x 在假设h o 、h 1 下的概率值。此类检验为最 基本的单边检验。本文所用检验即为此种检验。 本文中样本x 为搜索过程得到的一组可能为待预测转录因子结合位点的核 组成的位置频率矩阵。样本概率值的计算过程，使用下面将要介绍的隐马尔科夫 】3 东北师范大学硕士学位论文 模型进行计算。 3 3 马尔科夫模型 马尔科夫过程是具有马尔科夫性的过程。马尔科夫性指过程在时刻t 0 所处 的状态为已知的条件下，过程在时刻t t o 所处状态的条件分布与过程在t 0 时刻 之前所处的状态无关的特性。 马尔科夫过程一个重要的参数就是条件转移概率，多步转移构成转移概率矩 阵，根据这个矩阵可以计算由这一过程得到的观察结果出现的概率。即 f = f ( x o ) f ( x 11 ) f ( x m + 1x j l ，) 公卉穹1 3 4 信息含量 信息含量的定义来源于信息论中的香农提出的熵的概念。信息论的理论认为 具有最大不确定性的是等概率系统，此时系统的熵为最大值1 ；相对则具有最小 熵值0 的系统最为稳定。生物系统中的信息含量与熵是相反的概念。越是保守的 序列，不确定性越低，信息含量越高。 转录因子结合位点在进化过程中保留下来，生物上认为具有功能的序列在进 化过程中是保守的。使用信息含量可以度量结合位点的保守性。本文计算每个位 置的信息含量，相加之和得到一个候选转录结合位点的位置频率矩阵的信息含 量，从而比较可以得到预