（计算机应用技术专业论文）基于二阶z变换的转录因子结合位点识别方法研究.pdf

摘要 本文采用二阶z 变换对转录因子结合位点序列进行建模。在建模的过程中充分考虑 了d n a 序列中各位点碱基之间的依赖性，对以往所采用的经典模型进行了一定的改进。 在建模过程中采用二阶z 变换来表示各个碱基之间的依赖性。此方法先把多条具有相同 长度的转录因子结合位点序列转化为一个2 4 维的向量模型，同时把待识别的各条序列 也转化为相应的2 4 维向量，然后计算待识别序列对应的向量与模型向量之间在各个分 量上的角度，从而得到一个2 4 维的角度向量。最后利用训练集训练b p 人工神经网络， 对真正的转录因子结合位点进行识别。对大肠杆菌的四类转录因子结合位点数据进行实 验得到的结果表明，此方法可以有效地提高转录因子结合位点识别的准确性和特异性。 关键词：二阶z 变换；转录因子结合位点；b p 神经网络；敏感性；特异性 a b s t r a c t t h i sp a p e rm o d e l st r a l l s c f i p t i o nf a c t o rb i n d i n gs i t e s ( t f b s ) u s i n gt w o s t e pz t r a n s f o r m w ei m p r o v et h ec l a s s i c a lm e t h o db yc o n s i d e r i n gt h ed e p e n d e n c eo f b a s ei nd i f f e r e n ts i t e si nt h e p r o c e s so fb u i l d i n gm o d e l w er e p r e s e n tt h ed e p e n d e n c eo fb a s ei nd i f f e r e n ts i t e su s i n g t w o - s t e pz t r a n s f o r mi nt h ep r o c e s so fm o d e l i n g f i r s t ，w et r a n s f o r mm a n yt f b ss e q u e n c e s w i t ht h es a m el e n g t hi n t oam o d e lo f2 4 一d e m e n s i o nv e c t o r s e c o n d ，t h et f b st h a tw i l lb e i d e n t i f i e da l et r a n s f o r m e di n t o2 4 - d i m e n s i o nv e c t o r , t o o t h i r d ，w ec a l c u l a t ea na n g l ev e c t o r b e t w e e nv e c t o ro ft h et f b sa n dm o d e lv e c t o ri nd i f f e r e n td i m e n s i o n f i n a l l y , w et r a i nab a c k p r o p a g a t i o na r t i f i c i a ln e u r a ln e t ( b p - a n n ) u s i n g t h ea n g l ev e c t o rt oi d e n t i f yt h er e a lt f b s w ed oe x p e r i m e n tw i t hf o u rk i n d so ft f b so fe c o l i12 t h er e s u l ti n d i c a t e st h a tt h e a l g o r i t h mc a ne f f e c t i v e l yi m p r o v et h es e n s i t i v i t ya n ds p e c i f i c i t yo fi d e n t i f i c a t i o n k e yw o r d s ：t w o s t e pzt r a n s f o r m ；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 f b s ) ；b a c k p r o p a g a t i o n a r t i f i c i a ln e u r a ln e t ( b p - a n n ) ；s e n s i t i v i t y ；s p e c i f i c i t y i i 独创性声明 本人郑重声明：所提交的学位论文是本人在导师指导下独立进行研究工作 所取得的成果。据我所知，除了特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果。对本人的研究做出重要贡献的个人和集 体，均已在文中作了明确的说明。本声明的法律结果由本人承担。 学位论文作者签名： 日期：盟：堑! 学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定， 即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段 保存、汇编本学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者毕业后去向： 工作单位： 通讯地址： 勉 5 7 i 占li i 电话： 邮编： 东北师范大学硕士学位论文 第一章引言 1 1 生物信息学 生物信息学是2 0 世纪8 0 年代末开始，随着基因组测序数据迅猛增加而逐渐兴起的 - - i q 学科，是利用计算机对生命科学研究中的生物信息进行存储、检索和分析的科学。 【l 】随着人类基因组计划的完成，我们获得了大量的原始生物序列数据和注释信息。研究 人员需要利用现代计算技术对这些数据进行收集、整理、存储、注释、搜索、建模和使 用，这就促成了一门新兴的交叉学科生物信息学的诞生。可以说，生物信息学是与 基因组计划一同发展起来的。它是多学科交叉、相互渗透的产物，涉及分子生物学、数 学、信息科学以及计算机科学等诸多学科的知识。1 9 9 5 年，在人类基因组计划的第一个 五年总结报告中，对生物信息学作了如下定义：生物信息学是一门交叉科学，它包含了 生物信息的获取、处理、存储、分发、分析和解释等所有方面，它综合运用数学、计算 机科学和生物学的各种工具，来阐明和理解大量生物序列数据所包含的生物学意义。从 生物信息学研究的具体内容上看，生物信息学应包括3 个主要部分，即新算法的研究； 各类数据的分析和解释；研制有效利用和管理数据的新工具。 生物信息学的核心是基因组信息学。基因组信息学作为一个学科领域，包括基因组 信息的获取，处理，存储，分配和解释。基因组信息学的关键是“读懂”基因组的核苷 酸顺序，即全部基因在染色体上的确切位置及与之表达相关的各种功能位点。具体说其 内涵包括：( 1 ) 要发展有效的，能支持大量数据信息处理需要的软件和数据库；( 2 ) 需产生若干数据库工具； ( 3 ) 要研究算法和分析技术，用于解释基因表达的信息，即 基因的转录调控。 1 2 基因的转录调控 生物遗传的中心法则告诉我们遗传信息主要包含在d n a 中，这些包含在d n a 中的遗 传信息只有通过它编码的蛋白质才能被表达出来。在遗传信息从d n a 向蛋白质传递的过 程中，经过两个主要过程：d n a 转录成m r n a 的转录过程和以m r n a 为模板合成蛋白质的 翻译过程。这两个过程都是在多种酶的综合催化作用下完成的。利用d n a 作为模板，由 r n a 聚合酶来合成r n a ，这个过程称为转录。与这个过程有关的分子部件被命名为r n a 聚合酶，个基因转录到m r n a 是被严格控制的，并不是所有的基因总是在表达蛋白质。 【2 】 d n a 的转录需要一种叫做r n a 聚合酶的酶和多种转录调控因子共同作用才能完成。 r n a 聚合酶和这些转录调控因子都属于蛋白质，它们必须结合在d n a 上才能调控d n a 的 转录过程。这些蛋白质与d n a 的结合位置在d n a 上不是随机分布的，而是具有定的特 l 东北师范大学硕士学位论文 异性。能与转录因子进行结合的d n a 上的短的片段在序列和结构上具有一定的保守性， 它们被称为转录因子结合位点。转录因子结合位点的长度在1 0 3 0 b p 之间。【3 】转录因子 结合位点大多数都位于被调控基因上游的启动子区域中，当然也有一些位于被调控基因 的下游甚至位于基因内部的内含子中。 人类已经步入后基因组时代。随着对基因研究的不断深入，了解基因表达调控机制 特别是转录调控机制的需求就显得尤为迫切起来。这是因为，基因是细胞生命活动的基 础。在同一生物体内，每个细胞都有一套完全相同的基因组。但是在不同的条件下，基 因的表达水平不尽相同，这种行为限定了细胞中的r n a 组成，进而影响到最终所能产 生出的全部蛋白质，从而决定了该细胞的功能。转录过程即是d n a 翻译成蛋白质的关 键一步，同时也是调控基因表达的关键阶段。转录调控通常是在转录起始步骤实现的。 除了启动子以外，在几乎所有基因的上游区域中都还存在着激活基因所需的一段特定的 d n a 序列( 转录因子结合位点) 。这些序列本身并不执行任何功能，只有当其被调控蛋 白( 转录因子) 识别、结合后才能发挥作用。它们共同控制着基因的转录。转录因子与 其结合位点的结合具有高度的专一性。研究转录因子就是研究转录调控的分子机制，研 究一类特定的蛋白质分子与d n a 序列的结合特性，研究与d n a 结合的蛋白质是如何调 控基因转录等问题。因此，鉴别出全部与特定转录因子结合的d n a 序列的特征，有助 于对转录因子性质的进一步研究。 1 3 转录因子结合位点的识别 1 3 1 与转录因子结合位点相关的基本概念 转录因子结合位点是一段长度在1 0 3 0 b p 的d n a 序列，它在调控基因表达方面具有 重要作用。不同的基因表达时需要特定的转录因子结合到它的结合位点上。因此，识别 转录因子结合位点对于研究基因表达的调控具有重要意义。一种转录因子可以调节一组 基因的表达，这一组基因叫做共表达基因。大多数转录因子结合位点都位于被调控基因 上游的启动子区域，共表达基因的结合位点在序列模式上具有保守性但又不完全相同， 所以识别转录因子结合位点的问题就是在共表达基因的上游序列中寻找一组在模式上 具有一定保守性的短的d n a 序列。 1 3 2 转录因子结合位点识别涉及的基本问题 转录因子结合位点的分析主要涉及三类问题：在给定基因组序列中寻找已知的转 录因子的结合位点；在一系列共表达或者共调控基因的上游区域中发现未知的转录因 子结合位点；寻找由一个已知转录因子调控的未知基因。本文主要讨论第一类问题， 即通过对同一个转录因子的一组已知结合位点的分析建模来发现属于这个转录因子的 未知结合位点。嘲 1 3 3 转录因子结合位点的建模 转录因子与结合位点的特异性结合主要是通过分子间的氢键发生作用的，与同一种 转录因子作用的结合位点在序列的碱基组成上可能存在着差异，而造成这种差异的主要 2 东北师范大学硕士学位论文 原因是由于功能上的差异，不同的结合位点要求的结合力是不同的。另外，结合位点中 的有些碱基对于结合起着至关重要的作用，而结合位点中某些位置上的碱基变化不影响 与转录因子的作用。然而，不管差异性程度有多高，相对于随机序列片段而言，对应同 种转录因子的结合位点仍然具有较高的保守性，正是这种保守性构成了用计算的方法 来识别转录因子结合位点的理论基础。嘲 目前主要有三种方法对转录因子结合位点进行建模：一致性序列模型、矩阵模型以 及可视化模型。 一致性序列模型是使用通配符表中的字符组成的单一字符串来表示序列模式。一致 性序列是关于序列特征的种定性描述。对于d n a 序列，它能够说明序列每个位置可能 出现的碱基类型，但是不能定量地说明各个位置上不同类型碱基出现的可能性的大小。 因此需要定量的序列描述方式。 基于矩阵的序列模式表示方法是一种类似于序列特征统计图谱的方法。最基本的序 列模型是一个4 x n 矩阵，4 代表碱基的种类数目，n 代表模式序列的长度。矩阵的行表 示4 种碱基，列表示模式序列中的各个位置，矩阵元素为行对应的碱基在列对应的位置 上出现的频数。这种模型最常用的一种是位置特异性得分矩阵，这是本文中将要使用的 模型。 可视化模型中最有名的是由s c h n e i d e r 和s t e p h e n s 于1 9 9 0 年提出的l o g o 模型， 该模型是依据一些信息论知识，用形象、直观的图形方式来表示结合位点的特征。 1 3 4 常用的转录因子结合位点识别方法 ( 1 ) 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，h m m ) h m m 是一类智能化算法，在生物学应用上其结构合理且容易解释，它成功定义的量 度标准对于任何形式的机器学习都是很必要的。h m m 具有牢固的统计学基础和有效的训 练算法，因此广泛应用于生物序列的数学建模和分析，尤其在转录因子结合位点识别问 题上有着突出的优势。 ( 2 ) z 曲线 该算法来源于人与其他高等真核生物基因组的i s o c h o r e ( 马赛克现象) ：整个基因 组是由一系列g + c 含量相当均匀的大片断所组成，从一个片断到另一个片断过渡，其g + c 含量是突变的，而不是渐变的。利用这个现象，张春霆院士创造了z 曲线，z 曲线方法 研究起始于对组成d n a 序列的腺嘌呤a ，乌嘌呤g ，胞嘧啶c 和胸腺嘧啶t 这四种碱基 的对称性的观察。按双环或单环、是否存在氨基或酮基、碱基对形成氢键的数目或强弱， 将这四种碱基进行划分，并用正六面体来表示它们的对称性，从而导出了z 变换，然后 利用z 变换将d n a 序列转化为三维空间的点，得到z 曲线。z 曲线分布图中z 分量的升 降近似对应了d n a 序列的非编码区与编码区，从而对d n a 序列的研究也就转换为对相应 的z 曲线的研究。 ( 3 ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 支持向量机简称s v m ，是统计学习理论中年轻的内容，也是最实用的部分。其核心 内容于1 9 9 2 到1 9 9 5 年间提出。目前仍处在不断发展阶段。【7 】 3 东北师范大学硕士学位论文 ( 4 ) 基于图论的方法 图模型在很多领域得到了广泛的应用。它用一个顶点的集合和一个与顶点相关联的 边的集合来表示客观事物。因为图的结构富于变化，所以它很适用于表示那些彼此之间 存在密切联系并且联系方式变化多端的事物。因为转录因子结合位点是一条短的d n a 序 列，跟同一种转录因子作用的结合位点之间不管是序列模式上还是结构上都存在密切联 系，所以很适合用图对它们进行建模。此外，还可以利用图来表示转录因子结合位点内 部不同位置之间碱基之间的依赖关系，而这种依赖关系用别的方法建模会非常复杂。目 前图论的方法在生物信息学相关领域中都的到了广泛的应用，特别是对转录因子结合位 点的识别更是被广泛应用。1 8 j 1 4 研究现状 因为每种转录因子在序列组成和结构方面都具有特异性，因此与之结合的d n a 序列 即转录因子结合位点也都具有特异性，所以不可能找到适用于所有物种和所有转录因子 的普适方法来对转录因子结合位点进行识别，因此针对不同的转录因子以及不同的物种 产生了许许多多的识别算法。其中比较经典的有利用e m 算法的m e m e ，利用g i b b s 采样 算法的m o t i f s a m p l e r 和利用位置特异性得分矩阵的m a t i n s p e c t o r 等。【9 】这些经典的对 转录因子结合位点进行识别的方法普遍存在识别的敏感性不高，特异性过低等问题，在 得到的结果中往往存在大量的假阳性结果。因此对转录因子结合位点进行识别的问题在 今后很长一段时间内将是生物信息学领域一个最具挑战性的任务，需要生物学信息学工 作者研究更多的算法来解决这个难题，其中如何提高识别的特异性是所有算法必须注重 的一个问题。 本文采用二阶z 变换对转录因子结合位点序列进行建模。在建模的过程中充分考虑 了d n a 序列中各位点碱基之间的依赖性，对以往所采用的经典模型进行了大胆的改进。 此方法先把多条具有相同长度的转录因子结合位点序列转化为一个2 4 维的向量模型， 同时把待识别的各条序列也转化为相应的2 4 维向量，然后计算待识别序列对应的向量 与模型向量之间在各个分量上的角度，从而得到一个2 4 维的角度向量。最后利用训练 集训练b p 人工神经网络，对真正的转录因子结合位点进行识别。对真实的转录因子结 合位点数据进行实验得到的结果表明，此方法可以有效的提高转录因子结合位点识别的 准确性和特异性。 4 东北师范大学硕士学位论文 第二章转录因子结合位点识别方法简介 2 1 概述 转录因子结合位点的识别主要分两大类问题：在给定基因组序列中寻找已知的转 录因子的结合位点；在一系列共表达或者共调控基因的上游区域中发现未知的转录因 子结合位点。 对于第一类问题，一般都会给定一组已知的转录因子结合位点序列，然后对这组序 列建立模型，用这个模型对待识别的序列中每一条子序列进行打分，然后利用分类的方 法确定被打分的序列是否属于这组转录因子结合位点。常用的对转录因子结合位点进行 建模的模型有共有序列模型，矩阵模型以及隐马尔可夫模型。 对于第二类问题，通常会给定一组待识别的序列，最终要在这组序列中找到每一条 序列都包含的子序列，这些子序列在序列模式上具有高度保守性，把找到的组序列作为 一种新的转录因子结合位点。在发现这组序列之前我们不知道这组转录因子结合位点所 具有的一切特征，包括序列长度，序列模式等。解决这类问题常用的方法是启发式搜索 算法，包括吉布斯采样算法，遗传算法以及图论算法等。 2 2 寻找已知的转录因子结合位点 对于寻找已知的转录因子结合位点问题，通常需要输入一组同样长度的已知的真正 的转录因子结合位点序列和一条待识别的序列，问题的目标是在待识别序列中找到一条 属于已知转录因子结合位点的子序列。 为了完成这个目标，首先需要对已知的转录因子结合位点进行建模，用合适的模型 来表示这组序列，然后用这个模型对待识别序列中每一条长度和已知转录因子结合位点 相同的子序列进行打分，然后运用分类的方法从这些子序列中找到真正属于这组转录因 子结合位点的序列。 下面介绍几种常用的对转录因子结合位点进行建模的工具。 2 2 1 共有序列模型 共有序列模型是指用通配符表中的字符组成的单一字符串来表示序列模式的模型。 共有序列是藐视核酸序列中功能位点的最常用的方法，它描述了功能位点每个位置上核 苷酸的保守性，而这种保守性是与功能相关的。在共有序列中，既有保守的位置，在这 些位置上仅允许出现特异类型的核苷酸；也有可变的位置。任何位置上的核苷酸可以用 通配符表中的1 5 中字符之一表示，通配符表如表一所示。旧 5 东北师范大学硕士学位论文 表1 通配符表 符号含义 说明 gg 鸟嘌呤 aa腺嘌呤 tt 胸腺嘧啶 cc 胞嘧啶 rg 或a嘌呤 yt 或c 嘧啶 ma 或c 氨基 kg 或t酮基 sg 或c 强氢键( 三个氢键) wa 或t 弱氢键( 两个氢键) ha 或c 或t非g bg 或t 或c非a vg 或c 或a非t ( 非u ) dg 或a 或t非c ng 或a 或t 或c 任意碱基 例如，有如下核酸序列： a t c c g c t a g t c g a c c a g t c c g c g a a t c c g c g a g t c g a c a a c t c g g c 从 g t c g a c c a a t c g ( 五t a 则它对应的一致性序列为：v t c s r c n a 。 一致性序列是关于序列特征的一种定性描述。对于d n a 序列，它能够说明序列每 个位置可能出现的碱基类型，但是不能准确的说明各个位置上不同类型碱基出现的可能 性大小。因此需要定量的序列特征描述方式。 2 2 2 矩阵模型 一致性序列模型直观地表示了模式序列的碱基组成情况，但它却不能定量的表示出 每个位置每种碱基出现的频率。因此，一个更好地表示模式序列的模型是类似于序列特 征统计谱的方法，即基于矩阵的方法。 矩阵模型中最常用的一种叫做位置特异性得分矩阵。位置特异性得分矩阵是一个 6 东北师范大学硕士学位论文 4 x n 的矩阵，其中r l 代表序列长度。4 行分别对应a ，c ，g ，t 四种碱基，每一列对应于 序列中的一个特定位置，矩阵元素为行对应的碱基在列对应的位置的特异性程度。【1 0 】 对于给定的一组长度为r l 的转录因子结合位点序列，它对应的位置特异性得分矩阵是用 如下的公式( 1 ) 计算的得到的。 6 = 等邸e 孔幺。， 其中厶为矩阵中碱基b 所对应的行中第i 列位置的元素值，为序列中第i 列碱基 b 所占的比例，p b 为整组序列中碱基b 所占的比例。 p b = 喏 6 a ，c ，g ，t ) j = l 其中m 为序列的条数。 p 6 = q 6 爿，c ，g ，t 1i = 1j = l m ；l ：n 喏爿1 如果第绦脚“的第i 位为碱基b l 0 如果第j 条序列的第i 位不为碱基b ，f1 如果第j 条序列的第i 位为碱基b 噶= l 0 如果第j 条序列的第i 位不为碱基b 其中m 为序列条数，n 为序列长度。 例如，有如下核酸序列： a t c c g c t a g t c g a c c a g t c c g c g a a t c c g c g a g t c g a c a a c t c g g c a a g t c g a c c a a t c g g c t a 则它对应的位置特异性得分矩阵为： 东北师范大学硕士学位论文 a 1 5 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 1 5 0 0 0 00 0 0 0 0 01 0 0 0 0 04 0 0 0 0 0 c 0 0 0 0 0 04 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 01 0 0 0 0 00 0 0 0 0 0 g2 0 0 0 0 00 0 0 0 0 00 0 0 0 0 02 5 0 0 0 02 5 0 0 0 00 0 0 0 0 01 0 0 0 0 00 0 0 0 0 0 t0 5 0 0 0 00 0 0 0 0 04 0 0 0 0 01 5 0 0 0 00 0 0 0 0 04 0 0 0 0 01 0 0 0 0 00 0 0 0 0 0 如果按照上述方法构建矩阵模型的话，则矩阵中会出现0 的情况，而事实上可能该 碱基并不是真的没有出现，而是由于比对时没有观察到所有的结合位点而造成的缺失。 为了避免这种情况，通常在建模时会引入一些数值相对非常小的伪数目。【1 1 】 2 3 发现未知的转录因子结合位点 对于发现未知的转录因子结合位点问题，通常是先给定一组启动子序列，最终要在 这组序列的每一条序列中都找到一条子序列，使找到的这些子序列在序列模式上具有最 大的相似性。为了完成这个目标，通常采用搜索算法，主要分为两大类，穷尽式搜索算 法和启发式搜索算法。【1 2 】 穷尽式搜索算法是考察所有的可能序列组成，然后把相似性最高的序列作为我们要 找的转录因子结合位点。这种方法能保证找到最优结果，但是随着序列条数和序列长度 的增加，计算量将按指数增加，在计算速度上得不到保证，因此实际上很少使用这种方 法，而是使用下面要介绍的启发式搜索算法。 启发式搜索算法就是在状态空间中对每一个搜索的位置进行评估，得到最好的 位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提 到了效率。但是启发式搜索不保证能得到最优解，只能得到一个与最优解相近的 次优解。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以 有不同的效果。 启发过程中的估价是用估价函数表示的，如： f ( d ) = g ( n ) + h ( n ) 其中f ( n ) 是节点n 的估价函数，g ( n ) 是在状态空间中从初始节点到n 节点的 实际代价，h ( n ) 是从n 到目标节点最佳路径的估计代价。在这里主要是h ( n ) 体现 了搜索的启发信息，因为g ( n ) 是已知的。如果说详细点，g ( n ) 代表了搜索的广度 的优先趋势。但是当h ( n ) g ( n ) 时，可以省略g ( n ) ，而提高效率。 常用的启发式算法有：吉布斯采样算法，遗传算法、模拟退火算法等。下面 分别对这些算法进行介绍。 2 3 1 吉布斯采样算法 吉布斯采样算法是一种特殊的马尔可夫蒙特卡罗方法，该算法最早是由l a w r e n c e 等引入蛋白质序列中的序列模式识别。后来l i u 等将吉布斯采样整合进贝叶斯模型并应 用于多重序列比较，获得了较好的效果。目前，吉布斯采样算法以及一些改进算法被广 8 东北师范大学硕士学位论文 泛应用于转录因子结合位点的识别，并出现了一些较为成熟的软件以供用户在线或下载 使用，如m o t i fs a m p l e r 、a 1 i g n a c e 、b i o p r o s p e c t o r 和g i b b sm o t i fs a m p l e r 等。吉 布斯采样算法识别转录因子结合位点的基本原理是通过随机采样不断更新转录因子结 合位点模型和在各条序列中的出现位置以优化目标函数，当满足一定的迭代终止条件时 就得到了最终的候选调控元件。下面具体介绍最基本的吉布斯采样算法的流程。算法流 程图如图1 所示。 1 3 1 图1 吉布斯采样算法流程 基本的吉布斯采样算法可归纳为如下的步骤： ( 1 ) 初始化：包括转录因子结合位点模型和背景模型的建立。转录因子结合位点 通常采用位置特异性得分矩阵，背景序列采用独立性模型。 ( 2 ) 更新：从输入序列中集中顺序选取一条序列，从转录因子结合位点模型中删 除这条序列，重新计算位置特异性得分矩阵，然后分别根据调控元件模型和背景模型计 算选取序列中所有可能的候选转录因子结合位点的得分。 ( 3 ) 采样：计算两种得分的比值，并按照轮盘赌原理选取新的候选转录因子结合 位点，即以较大的概率选取比值较高的候选结合位点，将其加入到真正转录因子结合位 点中。 ( 4 ) 终止：若得分连续多次没有改进或达到最大迭代次数，则终止程序，否则转 ( 2 ) 。【1 4 】 随着计算机技术和分子生物学技术的发展，已经出现非常多的其他的识别转录因子 结合位点的方法，把它们和吉布斯采样算法结合起来，识别能力得到了大幅度的提高。 2 3 2 遗传算法 遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索 算法，从某种程度上说，遗传算法是对生物进化过程进行的数学方式仿真。遗传 算法由霍兰德在a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m 一书中首次提 出，并由他的学生加以发展。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经 过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。 染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体 中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基 因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化， o 东北师范大学硕士学位论文 如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化 产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体， 并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种 群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境， 末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法作为一种组合优化算法可以应用于发现转录因子结合位点。使用遗传 算法进行转录因子结合位点的识别主要涉及编码，遗传算子的设计以及适应度函 数的选取等问题。 在遗传算法中对转录因子结合位点的编码主要分两类，一类是一致性序列方 法，另一类是矩阵方法。使用一致性序列方法时首先把从待识别序列中选取的一 组子序列转化为一条一致性序列，然后把这个一致性序列作为一个个体参见遗传 操作；使用矩阵的方法是把选取的一组子序列直接作为一个个体参与运算不需要 转变。经证明这两种编码方法都是n p 难题，但是使用一致性序列时需要计算一致 性序列，浪费时间，所以大多数应用遗传算法的程序都采用矩阵方法对转录因子 结合位点进行编码。【l 副 在定义个体的适应度函数时，根据不同的编码方法，有两种主要的方法，在使 用一致性序列时使用如下的公式( 2 ) 。 n 厂( 聊) = “( 瓯，聊，) i - - 1 ( 2 ) 其中f ( m ) 是个体m 所对应的适应度值，最是个体m 对应的一致性序列，是个体 1 1 1 中第i 条序列，n 是序列条数，九( 晶，) 是到一致性序列的海明距离。 使用矩阵方法时使用信息量作为个体的适应度值，信息量按如下的公式( 3 ) 计算。 i c = 主以( 川。g 华，= c ，g ， ( 3 ) j = l6z上6 其中，配是信息量，石( j ) 是碱基b 在位置j 上出现的频率，既是碱基b 在背景序 列中出现的频率。w 是指序列的长度。 在进行遗传操作时，主要用到的遗传算子有选择，交叉和变异。其中选择操作有很 多中方法，经常使用的有，适应度比例选择，b o l t z m a n n 选择，排序选择，联赛选择， 精英选择和稳态选择。交叉操作经常按照如图2 的方法进行。变异操作经常使用的方法 是随机选择一条序列，然后使用滑窗技术，在这条序列上选择一个适应度最大的子序列 作为候选转录因子结合位点。 1 0 东北师范大学硕士学位论文 2 3 3 模拟退火算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却， 加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有 序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 根据m e t r o p o l i s 准则，粒子在温度t 时趋于平衡的概率为e 一e ( k t ) ，其中 e 为温度t 时的内能，e 为其改变量，k 为b o l t z m a n n 常数。用固体 t r g a t t g c c a a t g c a t r g t a g g c a t g g t g a c c t t g g t a g g c t ：a g c t t g 筒n g c c a a t g c n 兀g t 八g g c 汀g g t g a c c t t g g t t g a t t g c c aa t g c a t t g t a g g c a r g g t g a c c t t g g t 1 g a t t g c c a a t g c a t r g t a g g c a t g g t g a c c 丌g g t a g g c t a g c 一 - 一 t t g 戌r r g c c a a t g c a t r g t a g g c a t g g t g a c c r r g g t t g a 丌g c c a a t g c 兀g t a g g c a t g g t g a c c t t g g t a g g c t a g c t t g a r r g c c a a t g c a t r g t a g g c a t g g t g a c c t r g g t a g g c t a g c t t g a t t g c c a a r g c a t r g t a g g c a r g g t g a c c t t g g 图2 遗传算法的交叉操作 退火模拟组合优化问题，将内能e 模拟为目标函数值f ，温度t 演化成控制参数t ， 即得到解组合优化问题的模拟退火算法：由初始解i 和控制参数初值t 开始，对 当前解重复“产生新解一计算目标函数差一接受或舍弃 的迭代，并逐步衰减t 值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的 一种启发式随机搜索过程。退火过程由冷却进度表控制，包括控制参数的初值t 及其衰减因子t 、每个t 值时的迭代次数l 和停止条件s 。 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想： ( 1 ) 初始化：初始温度t ( 充分大) ，初始解状态s ( 是算法迭代的起点) ，每 1 1 东北师范大学硕士学位论文 个t 值的迭代次数l ( 2 ) 对k = l ，l 做第( 3 ) 至第6 步： ( 3 ) 产生新解s 7 ( 4 ) 计算增量t7 = c ( s7 ) 一c ( s ) ，其中c ( s ) 为评价函数 ( 5 ) 若t o ，然后转第2 步。 模拟退火算法和遗传算法都属于启发式组合优化算法，只是在启发策略上不 同，它们都具有陷入局部最优解的问题。 1 2 东北9 币范大学硕士学位论文 第三章常用的生物分子数据库 3 1 概述 生物分子数据库是生物信息学工作者取得实验材料的重要手段，对生物信息学研究 至关重要。随着分子生物学与计算机技术的飞速发展，国际上已陆续建立起许多生物分 子公共数据库，包括基因组图谱数据库、核酸序列数据库、蛋白质序列数据库及生物大 分子结构数据库等。这些数据库由专门的机构建立和维护，他们负责收集、组织、管理 和发布生物分子数据，并提供数据检索和分析工具，想生物学研究人员提供大量有用的 信息，最大限度地满足他们研究和应用的需要，为他们的研究服务。 分子生物信息数据库是种类繁多。归纳起来，大体可以分为4 个大类，即基因 组数据库、核酸和蛋白质一级结构序列数据库、生物大分子( 主要是蛋白质) 三维 空间结构数据库、以上述3 类数据库和文献资料为基础构建的二次数据库。基因 组数据库来自基因组作图，序列数据库来自序列测定，结构数据库来自x 一衍射和 核磁共振结构测定。这些数据库是分子生物信息学的基本数据资源，通常称为基 本数据库，初始数据库，也称一次数据库。根据生命科学不同研究领域的实际需 要，对基因组图谱、核酸和蛋白质序列、蛋白质结构以及文献等数据进行分析、 整理、归纳、注释，构建具有特殊生物学意义和专门用途的二次数据库，是数据 库开发的有效途径。近年来，世界各国的生物学家和计算机科学家合作，已经开 发了几百个二次数据库和复合数据库，也称专门数据库、专业数据库、专用数据 库。一般说来，一次数据库的数据库量大，更新速度快，用户面广，通常需要高 性能的计算机硬件、大容量的磁盘空间和专门的数据库管理系统支撑。例如，欧 洲生物信息学研究所用o r a c l e 数据库软件管理、维护核酸数据库e m b l 。而基因组 数据库g d b 的管理、运行则基于s y b a s e 数据库系统，即使是安装其镜象。也需要 有s y b a s e 支撑。o r a c l e 和s y b a s e 均为流行的数据库管理商业软件。而二次数据 库的容量则要小得多，更新速度也不像一次数据库那样快，也可以不用大型商业 数据库软件支撑。许多二次数据库的开发基于w e b 浏览器，使用超文本语言h t m l 和j a v a 程序编写的图形界面，有的还带有搜索程序。这类针对不同问题开发的二 次数据库的最大特点是使用方便，特别适用于计算机使用经验并不丰富的生物学 家。 建立生物分子数据库的动因是由于生物分子数据的告诉增长，而另一方面也是为了 满足分子生物学及相关领域研究人员迅速活的最新实验数据的要求。生物分子信息分析 已经成为分子生物学研究必备的一种方法。如果说理论分析和算法模拟是生物信息学的 实验方法的话，那么来自于具体实验的原始数据和来自于数据库的数据则是生物信息学 1 3 东北师范大学硕士学位论文 的实验材料。数据库及其相关的分析软件是生物信息学研究和应用的重要基础，也是分 子生物学研究必备的工具。 从数据库使用的角度来看，生物分子公共数据库应满足如下五个方面的主要需求。 ( 1 ) 时间性对于新发表的数据，应该能够在很短的时间内通过国际互联网访问。 ( 2 ) 注释对于每一个基本数据，应该加一致的、深层次的辅助说明信息。 ( 3 ) 支持数据在有些情况下，数据库使用者需要得到原始的实验数据，因而要提 供访问原始数据的方法。数据库中应包含原始数据，或者能够通过交叉索引访问实验数 据库中的原始数据。 ( 4 ) 数据质量必须保证数据库中数据的质量，数据库管理机构应对数据来源进行 检查，并且关注数据库用户和专家提出的意见。 ( 5 ) 集成性三种基本生物分子数据库( 核酸序列、蛋白质序列、蛋白质结构) 的 集成对于用户来说是非常重要的。对于数据库中的每一个数据对象，必须与其他数据库 中的相关数据联系起来，这样可以从某些分子数据出发得到一系列的相关信息。例如， 从某个核酸序列出发，通过交叉索引，可以进一步得到对应的基因、蛋白质序列、蛋白 质结构，甚至得到蛋白质功能。下面介绍几种常用的生物分子数据库。 3 2g e n b a n k 数据库 g e n b a n k 是一个有来自于7 0 ，0 0 0 多种生物的核苷酸序列的数据库。每条纪录 都有编码区特征的注释，还包括氨基酸的翻译。g e n b a n k 属于一个序列数据库的国 际合作组织，包括e m b l 和d d b j 。【1 6 j 完整的g e n b a n k 数据库包括序列文件，索引文件以及其它有关文件。索引文 件是根据数据库中作者、参考文献等建立的，用于数据库查询。g e n p e p t 是由 g e n b a n k 中的核酸序列翻译而得到的蛋白质序列数据库，其数据格式为f a s t a 。 g e n b a n k 中最常用的是序列文件。序列文件的基本单位是序列条目，包括核苷酸碱 基排列顺序和注释两部分。目前，许多生物信息资源中心通过计算机网络提供该 数据库文件。下面，我们介绍序列文件的结构。 g e n b a n k 序列文件由单个的序列条目组成。序列条目由字段组成，每个字段由 关键字起始，后面为该字段的具体说明。有些字段又分若干次子字段，以次关键 字或特性表说明符开始。每个序列条目以双斜杠“”作结束标记。序列条目的 格式非常重要，关键字从第一列开始，次关键字从第三列开始，特性表说明符从 第五列开始。每个字段可以占一行，也可以占若干行。若一行中写不下时，继续 行以空格开始。 链接1 2 3 1 卜1 。序列条目的关键字包括l o c u s ( 代码) ， d e f i n i t i o n ( 说明) ，a c c e s s i o n ( 编号) ，n i d 符( 核酸标识) ，k e y w o r d s ( 关键词) ， s o u r c e ( 数据来源) ，r e f e r e n c e ( 文献) ，f e a t u r e s ( 特性表) ，b a s ec o u n t ( 碱 基组成) 及o r i g i n ( 碱基排列顺序) 。先版的核酸序列数据库将引入新的关键词s v ( 序列版本号) ，用“编号版本号 表示，并取代关键词n i d 。l o c u s ( 代码) ：是 1 4 东北师范大学硕士学位论文 该序列条目的标记，或者说标识符，蕴涵这个序列的功能。该字段还包括其它相 关内容，如序列长度、类型、种属来源以及录入日期等。说明字段是有关这一序 列的简单描述，a c c e s s i o n ( 编号) ：具有唯一性和永久性，在文献中引用这个序 列时，应该以此编号为准。k e y w o r d s ( 关键词) 字段：由该序列的提交者提供，包 括该序列的基因产物以及其它相关信息，s o u r c e ( 数据来源) 字段：说明该序列 是从什么生物体、什么组织得到的。次关键字o r g a n i s m ( 种属) 指出该生物体的分 类学地位。r e f e r e n c e ( 文献) 字段：说明该序列中的相关文献，包括a u t h o r s ( 作 者) ，t i t l e ( 题目) 及j o u r n a l ( 杂志名) 等，以次关键词列出。该字段中还列出医 学文献摘要数据库m e d l i n e 的代码。该代码实际上是个超文本链接，点击它可以 直接调用上述文献摘要。一个序列可以有多篇文献，以不同序号表示，并给出该 序列中的哪一部分与文献有关。f e a t u r e s ( 特性表) ：具有特定的格式，用来详细 描述序列特性。特性表中带有d b x r e f 标志的字符可以连接到其它数据库。 翻译所得信号肽以及最终蛋白质产物也都有所说明。 3 3 转录调控区域数据库t r r d 转录调控区域数据库t r r d 是有俄罗斯科学院细胞和遗传学研究所建立的。t r r d 是一个关于基因调控信息的集成数据库，该数据库搜集真核生物基因转录调控区 域结构和功能的信息。每一个t r r d 的条目对应于一个基因，包括特定基因的各种 结构和功能特征，如：转录因子结合位点、启动子、影响基因转录水平的增强子 和静默子、5 一端和3 一端扩展的转录调控区域、基因表达调控模式、完整的基 因表达调控系统等。【1 。7 】 t r r d 6 0 包括7 个相关的数据表： ( 1 ) 基因描述表t r r d g e n e s ，包括所有t r r d 库基因的基本信息和调控单元信 息，它是t r r d 最主要的表，设有与其他表的链接； ( 2 ) 控制