（计算机应用技术专业论文）生物序列模式发现算法的研究.pdf

摘要 2 0 世纪9 0 年代以来，生命科学研究取得了突破性的进展，随着人类基因组计 划的开展与现代生物技术的发展，人类积累的大量的生物信息数据为揭开生命奥 秘提供了数据基础。而怎样从海量的生物数据中提炼出有用的生物学知识，弄清 楚他们所蕴涵的结构和功能信息，是目前生物信息学领域中的一个重要的研究方 向。模式发现技术正是揭示生物序列数据中所蕴涵的生物学意义的基本方法之一， 它通过寻找不同序列间的相似片段来归结出这些序列片段中所蕴涵的特征模式。 近年来，在模式发现的算法研究方面，人们已经探索出了一些有效的算法，这些 算法在解决较小规模的生物序列模式发现问题时都表现出了良好的性能。但是， 随着数据规模的不断扩大，很多算法都己无法适应问题的需要。所以，积极探索 更加有效的模式发现算法已成为目前生物序列模式发现研究领域中的重大课题， 并受到越来越广泛的关注。 本文首先对在模式发现算法中所常用的模式模型进行了分析，并且对基于不 同模式模型的模式发现算法进行了研究和分析；然后在分析已有的序列模式发现 算法的基础上，又提出了一种基于图的模式发现算法，该算法首先通过一些约束 条件将生物序列数据集转化为一系列的子图，假如数据集中存在某一个模式，那 么模式实例必然可以通过子图中某个团的节点来表示，然后在这些子图中查找有 效团，并从有效团中恢复出模式的一致序列。通过对算法进行的理论分析和仿真 试验研究表明，它能够很好得发现序列中所蕴涵的模式。 关键词：模式发现序列图算法 a b s t r a c t s i n c ct h e9 0 si nt h e2 叫lc e n t u r y ，t h e r ci sa 黟e a t b r c a k t h r o u g hi l it h ep m 伊e 鼹o f l i f es c i e n c er c s c a r c h w “ht h eb e 酉衄i n go ft l l eh u m a ng e n o m ep 加j e d 锄dt h e d c v e l o p m e n to fm o d e mb i o t c c h n o l o g y ，p e o p l ea c c i l m u l a t ea l o to fd a t aa b o u t b i o l o 酉c a l i n f o 帆a t i o l l w h i c hp r o v i d ef o u n d a t i f o rc x p l o r i n gt h el i f cs e c r c t y b u t ，h o wt 0e x t m d u f i i lb i o l o 舀c a lk n o w l e d g ef m mm a s s i v eb i o l 呼c a ld a t a 柚dc l a r i f yt h es t m c t u 坤柚d f i l n d i o nh j d e di nt h c mi s 姐i m p o n a mr c s e a r c hf i e l di i lb i o j n f b n l l a t i c s 1 n h em o t i f d i s v e yt c c h n o l o g yi se x a c t l yo n eo ft h eb a s i cm e t l l o d sw h i c h 托v e a lt h eb j o l o g i c a l m e 锄i n gh i d e di nt h es e q u e n c c n 莎t st h ec h a f a c i e r i s t i cm o t i f h i d c di nt i l e q u e n c cb y f i n d i n gt h es i m i l a rs e g m e mi nt h ed i f e f e n t 辩q u e n c e s hr e c e n ty c a 瑙，p e o p l eh 弱 p f e s c n t e ds o m ee 侬埘i v ea l g o r i t l l i i i si nm es t l l d yo fm o t i fd i 咖e r ) ，a l g o f i t l l i n s ，l h e s e a l g o r i t h m sh a v es h o w nab c t t c rp e d o 眦柚c ci n l v i n gt h em o t i fd i s c 0 v e r yp m b l e m s 岫d e fs m a l ld a t as c a l e h o w c v e r ，a l o n gw i t ht h ee x p a n s i 吨o ft h ed a t as c a l e ，m 卸y a l g o r i t h m s 啪n o t l v et h em o t i fd i 洲e r yp r o b l e m si n t h i sc a s o ，s t i l d y i n gm o r c e f f c c t i v ea l g o r i t h m sf o rm o t i fd i s v e r yi l il a f g cs c a l eh 嬲b c c o m e 锄i l i i p o n 卸t 哦乒o n i nt h eb i o q u e n c cr e a r c ha l l da t t r a c t c dm o 比卸dm o r ca t t e n t i o 璐i nt h ew o d d h lt h i st h e s i s ，w ef i r s n yf c v i e w 山em o t i fm o d e l sw h i c ha r cu s e di nd i 拖r e mk i n d s o fm o t i fd i s c o v c r ya l g 嘶t h n 坞砧s o ，w es t u d y 蛳d 咖p 盯ct h em o t i fd i s c o v e f y a l g o r i t h m s b a s c d d i 虢r e n tm o d e l s t h c nw ep f e s t 锄a p p m a c hf o rm o t i fd i s o o v e r y b a do nt h eg r a p ht l l e o r y t h e 印p r o a c hc o n v e n st h c q u e n c c sd a t a b 舔et oas e r e so f s u b 舯p hu n d e rs o m ef e s t r i c t i o n s i ft h e r ci sab n do fm o t i fi nd a t a b 镐e ，t l l em o t i f i n s t a n c cc a nb e 陀p r e s e n t c db yt h ev e n e x e so fc l i q u ei l it h cs u b 一伊a p h t h ec o n s e n s u s m o t i fc a l lb eg o tt h r o u g i it h ee f ! f i c i e mc l i q u ef i n d i n gi nt h es u b 一伊a p h f i n a l l y ，w ch a v e t l l e o 北t i c a l 柚a l y s i s 姐dc x p e f i m e ms i m u l a t i o n s ，w h i c hs h o w t h a tt h ea l g o r i t h mc a l if i n d m o t i f 卸dh a v e9 0 0 dp c f f o 珊柚c ci nt h es e q u e n c e s k e y w o r d s ：m o t i fd i s c o v e r ys e q u 蚰g 豫p ha l g o r i t h m 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：起丽争日期2 缈z z z 矛 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： 起葡珲 确琳 日期 2 ，节7 2 2 扩 日期细7 2 寥 第一章绪论 第一章绪论 1 1 研究背景 生物信息学( b i o i n f o 】胁a t i 岱) 是一门新的交叉学科，在2 0 世纪5 0 年代生物信 息学的萌芽初步形成，2 0 世纪7 0 年代产生了生物信息学的基本思想，2 0 世纪8 0 年代末随着人类基因组计划( h 岫强g e n o m ep r o j c c t ，h g p ) 的启动，在人类基因组 计划1 1 j 的推动下，生物信息学迅速兴起，真正发展则是在2 0 世纪的9 0 年代。生 物信息学涉及生物学、数学、计算机科学和工程学，依赖于计算机科学、工程学 和应用数学的基础，以及生物实验和衍生数据的大量储存。 近年来，生命科学研究【2 j 取得了突破性的进展，随着人类基因组计划的开展 与现代生物技术的发展，人类积累的大量的生物信息数据为揭开生命奥秘提供了 数据基础。现代生物学研究方法也伴随着基因组研究、信息技术的发展及其在生 物研究中越来越广泛深入的应用而发生了深刻的变化。从生物学、细胞生物学到 分子生物学，现代生物研究更多地依赖于信息技术的分析结果来提供进一步研究 的线索和依据，强有力的数据处理分析工具成为现代生物科学研究发展的关键。 生物信息或基因数据挖掘1 3 】和通常的数据挖掘相比，生物信息或基因的数据挖掘 在数据的复杂程度、数据量以及分析和建立模型的算法等方面都要复杂得多。在 这个过程中，需要对实验数据进行处理和理论分析，在此基础上解释实验现象， 认识实验现象发生的本质，探索固有的生物学规律，进而了解和掌握生命的物质 基础和生命的本质。随着生物科学和技术的迅速发展，生物数据积累速度不断加 快，因此也就对生物数据的科学分析方法和实用分析工具提出了更新、更高的要 求，生物信息学这门交叉学科迅速发展并受到越来越多的重视。 作为一门交叉学科，生物信息学的发展依赖于计算机科学技术和生物技术的 发展，而生物信息学的研究成果又促进了生物学特别是分子生物学的发展。人类 基因组计划产生的生物分子数据是生物信息学的源泉，而人类基因组计划所需要 解决的问题则是生物信息学发展的动力。 生物信息学通过对生物学实验数据的获取、加工、存储、检索与分析，进而 达到揭示数据所蕴含的生物学意义的目的。由于当前生物信息学发展的主要推动 力来自分子生物学，生物信息学的研究主要集中于d n a 和蛋白质序列1 4 l 的存储、 分类、检索和分析等方面，所以目前生物信息学可以狭义地定义为：将计算机科 学和数学应用于生物大分子信息的获取、加工、存储、分类、检索与分析，以达 2 生物序列模式发现算法的研究 到理解这些生物大分子信息的生物学意义的交叉学科【5 】o 国外一直非常重视生物信息学的发展，各种专业研究机构以及公司的数量与 日俱增。目前国外许多大学和研究机构也已经各自成立了自己的生物信息学部门 或中心。就专业机构的角度来讲，美国于1 9 8 8 年在国会的支持下成立了国家生物 信息中心( n c b i ) ，欧洲于1 9 9 3 年3 月就着手建立欧洲生物信息学研究所( e b i ) ， 日本也于1 9 9 5 年4 月建立了自己的生物信息学中心( c i b ) 。这三个专业机构共同 的目的是进行计算分子生物【6 】基础研究，构建和发布分子生物学数据斟”。 国内对生物信息学领域也越来越重视。在一些著名院士和教授的带领下，在 各自领域取得了一定的成绩，有的在国际上还占有一席之地，如北京大学在生物 信息学网站建设方面，中科院生物物理所在e s t 序列拼接研究方面，天津大学在 d i q a 序列的几何分析嘲方面，都有了新的达到国际最先进水平的研究成果。国内 如中科院理论物理研究所、清华大学、复旦大学、东南大学等等都开展了生物信 息学的相关课题，并成立了专门的生物信息学研究机构。其中北京大学于1 9 9 7 年3 月成立了生物信息学中心，中科院上海生命科学研究院也于2 0 0 0 年3 月成立 了生物信息中心，这两个机构分别维护着国内两个专业水平相对较高的生物信息 学网站。复旦大学数据挖掘讨论组对生物信息学中的数据挖掘技术进行了探讨， 并开设了相关课题。但从国内总体水平上来看，与国际水平还有一定的差距。 目前生物信息学的主要任务是研究生物分子数据的获取、存储和查询，发展 数据分析方法，主要包括三个方面：第一是收集和管理生物分子数据。生物分子 数据来自于生物学实验，应用信息学技术搜集和管理这些数据，将各种数据以一 定的表示形式存放在计算机中，建立数据库系统，并提供数据查询和数据通讯工 具；第二是进行数据处理和分析。通过信息分析，发现数据之间的关系，发现本 质规律，进而上升为生物学知识。随着生物技术特别是分子生物学技术的发展， 人们目前己经积累了大量的生物信息学数据，尤其是国际分子生物学的三大核心 数据库g e n b 勰k 核酸序列数据库、s w i s s p r o t 蛋白质序列数据库和p d b 生物 大分子结构数据库1 9 l ，围绕这三大核心数据库还有众多面向各种特定应用的衍生 数据库和分析软件，这些数据库分别从不同角度、以不同方式对各类生物信息学 数据进行归纳、总结和注释，而各种分析软件则为挖掘这些数据提供了有力的工 具；第三是开发分析工具和实用软件，解决具体的问题，为具体的生物信息学应 用服务。如生物分子序列比较工具、基因识别工具、生物分子结构预测工具、基 因表达数据分析工具等。序列比对是生物信息学中最基本、最重要的操作，通过 序列比对可以发现生物序列中的功能、结构和进化的信息。序列比对的根本任务 是：通过比较生物分子序列，发现它们的相似性，找出序列之间共同的区域，同时 辨别序列之间的差异。在分子生物学中，d n a 或蛋白质的相似性是多方面的，可 能是核酸或氨基酸序列的相似，可能是结构的相似，也可能是功能的相似。 第一章绪论 3 1 2 研究的意义和目的 生物信息学研究的任务不仅是要解决高效的数据存取问题，更要发现高效的 数据挖掘和分析工具。只有利用新的、有效的数据挖掘和分析工具才能从海量的 生物学数据中提炼出有用的生物学知识，才能弄清楚它们所蕴涵的结构和功能信 息。而如何从生物序列数据或结构数据中提炼出含有生命特征信息的模式，又如 何从目标序列或结构数据中辨别出内含的模式，这就是模式发现【1 0 j 问题。由于模 式在基因的结构和功能方面扮演着极其重要的角色，因此发现模式序列成了揭示 基因秘密的重要途径。现在，模式发现已成为生物信息学研究的重要领域并受到 了广泛的重视。 模式发现技术是揭示核酸和蛋白质序列数据中所蕴涵的生物学意义的基本方 法之一，其出发点是找出不同序列间的相似性片段，从而归结出序列片段中蕴涵 的特征模式，进而推断出该特征模式与己知的结构和功能之间的内在联系。人们 把这种具有某种特征模式的序列片段称为模式。模式不仅在核酸序列中存在，如 启动子序列、转录起始( 终止) 位点1 1 1 j 等，在蛋白质序列中也存在这种特征模式 的序列片段，如锌指模体、a 螺旋一转折q 螺旋( 唧) 模体【1 2 】等。对于蛋白质 序列而言，模式( 模体) 发现就是利用蛋白质序列或结构中的某些特征模式识别 相关蛋白质的性质。若某一蛋白质序列或结构中的一部分具有保守性，而这种保 守性可能与蛋白质的生物活性、折叠方式等有关，则这种特征模式可以用来识别 蛋白质家族i 切中的新成员。换言之，若将已知蛋白质的特征序列和特征结构构建 成数据库，则可以利用这类数据库来确定新测定的蛋白质序列中是否具某种特征 模式，从而可以推断出目标蛋白质所属的家族以及其可能的功能和结构。同样模 式发现方法在核酸序列【1 4 1 分析中也发挥着重要作用，如启动子识别、d n a 结合 蛋白质的靶基因和靶位的识别等。另外，模式发现还可以用于_ 些相似性较低的 相关序列检测。 1 3 本文研究的主要内容和结构 本文主要对生物序列中模式发现算法进行了研究，具体的工作如下： 1 、对模式发现算法中所使用的模式模型进行了系统的分析，并且在此基础上 对常用的算法思想进行了研究。 2 、在对模式发现算法研究的基础上提出了一种基于图的模式发现算法。该算 法通过将n 条序列序列的数据集转化为图集，然后针对不同的子图去查找大小为 n 的团，从而恢复出序列中的模式。对算法进行的理论分析和试验测试表明，该 4 生物序列模式发现算法的研究 算法能够很好的发现序列中存在的真实模式，同时由于子图之间的不相关性，因 而可以将算法分成子任务在不同的处理器上并行运行。 本论文共分为五章，具体结构如下： 第一章对模式发现的研究背景、目的及意义进行了介绍。 第二章对模式序列建模及模式度量方法进行了介绍，研究了各种模型的优 缺点并对各种度量函数的具体应用进行了分析。 第三章基于两种不同的模型对各种目前常用的模式发现算法进行了系统的 介绍和研究，同时对各种算法的性能进行了分析比较。 第四章提出了一种新的基于图的模式发现算法，分析了该算法的复杂度， 并进行了性能测试。试验表明本算法在性能和运行时间上都明显优于常用的其它 算法，特别是对于长序列的模式发现问题。 第五章总结了论文的主要工作，并对下一步的研究工作提出了一些建议。 本文的研究工作得到国家自然科学基金项目：生物分子网络数据分析中相关 图问题的研究( n o 6 0 5 7 4 0 3 9 ) 的资助。 第二章d n a 序列模式的建模 5 第二章d n a 序列模式的建模 细胞的差异和生长变化基本上都是由基因来决定的，细胞的不同特征都是基 因组中的一小部分子集中在特定的时间、特定的条件下的表示结果。这种基因子 集的防同是由调控蛋白质和d n a 的特定的调控边来确定的。d n a 的特定调控边 有增强子、起动子、切边等，在协同作用的基因的调控区中存在一致的保守序列 模式，我们把d n a 中这样的区域的称为模式，在d n a 序列中实际存在的这样的 序列片段称为模式的实例。识别出这些模式和相应的实例非常重要，生物学家可 以根据它们来研究和分析基因和蛋白质之问的关系、基因调控以及细胞在病理和 生理条件下的发展变化的规律。 ， 模式序列的分析主要涉及三类问题：( 1 ) 在给定基因组序列中寻找已知的模 式序列；( 2 ) 在一系列共表达或者共调控基因中发现未知的模式序列；( 3 ) 寻找 由一个已知模式序列调控的未知基因。在这三类问题中，无论是搜索己知的模式 序列，还是预测新的模式序列，都会遇到三个基本问题，一是应该用什么样的语 言来描述模式序列，即为模式序列建立什么样的特征模型1 5 】；二是要定义一个衡 量序列片段是否为模式序列的度量或得分；三是当给定了模式序列模型和得分函 数【1 6 】后，如何从待分析的序列中找到得分最高的候选模式实例，这就是算法设计 问题。下文将对目前模式序列识别中常用的模型及得分函数进行研究。 2 1 模式序列的建模 转录因子与结合位点的特异性结合主要是通过分子间的氢键而发生作用的， 与同一种转录因子作用的结合位点在序列组成上可能存在着差异，而造成这种差 异性的主要原因是由于功能上的差异，不同的结合位点要求的结合亲和力不同。 另外，结合位点中的有些碱基对结合起着至关重要的作用，而结合位点中某些位 置上的碱基变化并不影响与转录因子的作用。然而，不管差异性程度有多高，相 对于随机序列片段而言，对应同一种转录因子的结合位点仍然具有较高的保守性， 正是这种保守性构成了用计算的方法来识别模式序列的理论基础。对于结合位点 序列的保守性，目前主要有三类描述模型。 2 2 1 一致序列模型 一致序列模型( n s e n s u sm o d e l ) 是最早出现也是最常用的序列模式表示方 法，它也称共有序列，是指用通配符表( w i l d c a r dc h a m c t e 娼，见表2 1 ) 中的字符 6生物序列模式发现算法的研究 组成的单一字符串来表示序列模式。 共有序列是描述核酸序列中功能位点的最常用方法。它描述了功能位点每个 位置上核苷酸进化的保守性旧，而这种保守性是与功能相关的。在共有序列中， 既有保守的位置，在这些位置上仅允许出现特定类型的核苷酸，也有可变的位置， 任何位置上的核苷酸可以用下表中1 5 种字符之一来表示。例如，c a a t 转录因子 结合的核酸序列表示为g c c a a t ( 了，热休克因子结合的核酸序列【1 8 】表示为 c n n g a a - 仆r i c n n g 。 表2 1 扩展的遗传学字母表或i u p a c 编码 符号含义说明 gg 鸟嘌岭 a腺嘌岭 t t 胸腺嘧啶 cc胞嘧啶 rgo ra 嘌呤 yto rc 嘧啶 mao rc 氨基 kgo rt 酮基 sg0 rc 强氢键( 3 个氢键) o rt 弱氢键( 2 个氢键) h o rco rt 非g bgo rto rc非a v go rco ra 非t ( 非u ) d6o r o rt非c ngo rao rto rc 任意碱基 利用共有序列进行功能位点分析牵涉到两个方面的问题，一是如何构造共有 序列，二是如何利用共有序列在给定的核酸序列上搜索寻找功能位点，并计算所 找到的功能位点的可靠性。 一种简单的共有序列的构建过程图如2 1 所示。假设已经建立一组相关结合 位点的序列多重比对，要求构造反映这类结合位点共同特征的一致性序列，具体 的构造过程如下： 第二章d n a 序列模式的建模 7 ( 1 ) 初始化共有序列为一系列可变位置，以“n ”代表。 。 ( 2 ) 在多重序列比对的可变位置寻找出现次数最多的核苷酸，并将该位置转 化为保守位置。 ( 3 ) 对当前所得到的共有序列进行特异性检查，若通过检查，转步骤( 5 ) 。 否则转步骤( 4 ) 。 ( 4 ) 形成与当前共有序列一致的位点子集，转步骤( 2 ) 。 ( 5 ) 从原位点集合中删除与当前共有序列一致的位点，若还有剩余位点，则 转步骤( 1 ) ，构造另外的共有序列。 图2 1 是一个简单的示例，对于给定的5 条序列的样本数据集，通过分析， 我们可以得到两个一致性序列，分别是t n s n c 和n t 1 n 。图中的编号代表算 法对应的步骤。 【l 】 【2 】【3 】【4 】 【2 】 【3 】 胎勰塌一嬲+ 嬲+ 嬲+ t a c g c t a c g ct t g t c t 1 1 g 1 t t g t ct t g t c t c c a c 丛： tccac工q!叁tnnnc 【4 】 f 2 】【3 1 【5 l 【5 】 鬻+ 纂+ 嬲+ 藏纛c 器。t n s n c m 。m m 1 “1 ” 图2 1 共有序列构造示例 一致序列是关于序列特征的一种定性描述。它能够说明序列每个位置可能出 现的碱基类型，但是不能准确地说明各位置上不同类型碱基出现的可能性大小。 因此需要定量的序列特征描述方式。 2 2 2 统计模型 虽然一致序列模型直观地表示了模式序列的碱基组成情况，但它却一定程度 上掩盖了各个位置上碱基出现的差异性。因此，一个更好地表示模式序列的模型 是类似于序列特征统计图谱的方法，即基于统计的方法。最基本的统计模型如表 2 2 ，其大小为4 n ，4 代表碱基的种类数目，n 代表模式序列的长度。矩阵的行 表示4 种碱基，列表示模式序列中的各个位置，矩阵元素为行对应的碱基在列对 应的位置上出现的频数。将碱基频数除以所在列的碱基总数所得到的矩阵即为位 置特异性频率矩阵( p o s i t i 咖一s p c c 墒c 仃c q u c n c ym a t r i x ，p s f m ) ，如表2 3 。p s f m 及其变异( 如l o 分o d ds r c 等) 是目前使用最广泛的模式序列模型。值得注意的 8生物序列模式发现算法的研究 是，在实际应用中，有些碱基在比对的某些位置上可能不出现，如果按照上述方 法构建统计模型”】的话，则矩阵元素会出现。的情况，而事实上可能该碱基并不 是真的没有出现，而是由于比对时没有观察到所有的结合位点而造成的缺失( 这 是可能的，因为现代生物学并没有发展到把所有的转录因子和对应的结合位点都 完全了解透彻) 。为了避免这种情况，通常在建模时会引入一些数值相对非常小 的伪数目。 一致序列模型和统计模型各有优缺点，使用者可以根据自己的需要而选择使 用不同的模型，当然，将两者结合起来不失为一个更合理的方法，如在算法识别 过程中可采用统计模型，而最后的结果用一致序列模型来表示。 表2 2 最简单的统计模型 l23456 a1 0o0oo3 t1oooo9 goo1 2o1 2o cl1 2o1 2oo 其中矩阵元素由该位置上对应的碱基出现的数目构成。 表2 3 对应图2 2 的p s 刚 l23456 o 8 3 3ooo0o 2 5 to 0 8 3ooooo 7 5 goolol0 c o 0 8 3l0loo 其中矩阵元素由该位置上对应的碱基出现频率构成。 2 2 3 可视化模型 可视化模型中最有名的是由s c l i i l e i d c r 和s t e p h e n s 【刎于1 9 9 0 年提出的l o g o 模 型，该模型是依据一些信息论的知识，用形象直观的图形方式来表示结合位点的 特征。图2 2 给出了一个l o 罾0 模型的例子。在l o g o 模型中，每个位置上由出现在 该位置的所有碱基堆叠而成，碱基堆的总高度对应于该位置上总的信息含量，而 第二章d n a 序列模式的建模9 各碱基按照信息量大小按其出现比例从上而下排列。因为某一位置的信息含量能 反映该位置上碱基的保守性，所以i j d g o 模型可以非常直观地表示出结合位点的 保守程度以及哪些位置上的哪些碱基起着相对重要的作用。 图2 4m c b 结合位点的l o g o 图 2 3 模式序列的得分函数 在计算方法中衡量一个模式是否为候选模式序列，首先要基于一定的标准对 该模式进行打分。目前广泛使用的得分函数主要有以下几种： 1 z 分数 给定模式5 ，它的z 分数可定义为： z 。丝= 兰丝2 口以) 其中，m 表示模式s 在序列x 中的实际出现次数，( 五，) 和盯( 置) 分别表示 模式s 在序列工中期望出现数目和方差。很显然，互被归一化成均值为o 、方差 为1 的标准量，它可从统计意义上来比较不同长度、不同出现次数的模式的重要 性，值越大则对应的模式越重要。 2 卡方统计量 z 。等 c t 五， 该统计量衡量了模式s 的实际出现次数与基于统计假设得到的模式期望出现 数目之间的差异性。 3 信息含量 该得分函数是采用信息论中不确定性的降低来描述模式的保守性。与随机序 列相比，模式的不确定性降低得越大，则对应的信息含量越高，因此该模式越保 守，就越有可能是候选模式序列。给定以矩阵形式表示的长度为撑的模式，则信 生物序列模式发现算法的研究 息含量可定义为： 彤。妻荟脚：尝 其中，吼是碱基b 背景序列中的出现频率，如则是模式序列中第i 个位置上 碱基6 的出现频率。 4 一致性得分 这也是衡量模式保守性的指标。假设以矩阵形式表示模式，定义一致性得分 为： 口- 2 + 昙妻磊础g ：魄， 当模式是完全保守时，一致性得分为最大值2 ，当模式完全不保守( 即所有 位置上各个碱基出现的频率完全相同) 时，该得分为o 。因此一致性得分的大小 刻画了模式的保守性。 5 对数似然值 通常以似然估计法来识别模式序列时，候选模式序列及其出现位置是最大似 然估计的结果，因此，用似然值来表示模式的得分是合理的，取对数是为了计算 的方便。对数似然值( 1 0 9 l i k e l i h o o d ) 可定义为： o l o g 一舭e 砌d 甜一1 0 9 ( y 。p o1 4 ，钆吃归。七i 吼，吃) ) 式( 2 5 ) 雨 其中，c 。表示模式s 在序列中最大实例数目，心表示每个实例的出现概率， 4 表示模式实例在序列中的出现位置，见和e 分别表示模式模型和背景分布。 前两种方法是根据模式出现的统计重要性计算其得分的；后三种是基于模式 的保守特性而设计的得分函数。因此，前两种得分函数常被应用于基于统计的模 式序列识别方法中，而后三种是以序列比对为核心的算法常采用的得分函数。 2 4 本章小结 在模式序列的分析过程中，对模式的描述和度量是最基本的问题之一。本文 就模式序列建模所采用的方法进行了介绍，对一致序列模型、统计模型和可视化 模型的思想和优缺点进行了研究。同时还介绍了目前模式发现算法中广泛使用的 度量函数，并且对各种函数的具体应用进行了分析。 第三章d n a 序列模式发现算法 h 第三章d n a 序列模式发现算法 在d n a 序列中，模式( m o t i f ) 就是指d 1 叮a 序列中保守的序列片段。通常人 们认为d n a 序列总是处于不断的突变过程中，而其中的某些区域，比如启动子 区域，由于对生物体的生存具有至关重要的意义，因而在进化的过程中更保守一 些，并表现为d n a 序列中的的模式。而从d n a 序列中发现这些模式的过程就是 模式发现( m o t i f d i s c o v e r y ) ，它是生物信息学中的一个重要研究内容。 根据算法搜索策略的不同，研究d n a 序列模式发现的方法主要分为两大类： 一类是穷尽式搜索算法1 2 l j ，该类算法对问题所有的解进行考察，最后给出满足某 种条件的解，因此能找到问题的最优解；另一类是启发式算法【捌，它是一种近似 算法，首先对序列模式的信息进行某种近似描述，然后通过不断迭代的过程对模 式信息进行调整优化，直至满足迭代终止条件。 3 1 模式发现算法 模式发现的问题可以描述为： 已知：一条d n a 序列数据集s 一谯l f 一1 ，2 ，挥 ，其中第f 条序列表示为 毛一 ，墨：，屯 ，表示序列长度，q 。，q 。- 4 ，c ，g ，n 表示q a 碱 基的集合。求在各序列中长度为f 的、并在各序列中最有可能发生的子序列片段。 模式发现问题是一个n p 完全问题。 根据算法使用的模式序列模型，人们对模式发现的研究算法也主要分为两 种，一种是基于统计模式模型的概率算法，另一种是基于一致序列模式模型的一 致序列算法。 3 1 1 基于统计模型的算法 此类方法有两个模型，一个是背景模型，一个是模式模型。目前最为广泛使 用的方法有g i b b s d n “2 3 1 、m e m e 【2 4 1 、c o n s e n s u s 瞄】等。 1 g i b b s d n a 一吉布斯采样算法 g i b b s 采样算法是一种特殊的马尔可夫链蒙特卡罗方法( m 缸k o vc h a i nm o n t c g 盯l o ，m c m c ) ，该算法最早是由i a w r c n c c 等提出的序列模式发现方法。后来， l i u 等将g i b b s 采样整合进贝叶斯模型并应用于多重序列比较，获得了较好的结 果。目前，g j b b s 采样算法以及一些改进算法被广泛应用于模式发现问题中，并 出现了一些较为成熟的软件以提供用户在线和下载使用，如m o t i fs 锄口l e r 、 1 2生物序列模式发现算法的研究 a l i 驴a c e 、b i o p m s p c c t o r 和g i b b sm o t i fs a m p l e r 等。g i b b s 采样算法模式发现的 基本原理是通过随机采样不断更新模式模型和其在各条序列中的出现位置以优化 目标函数，当满足一定的迭代终止条件时就得到了最终的候选模式。为了描述方 便，我们假设所要解决的问题为序列模式在每条序列中出现且仅出现一次。基本 的g i b b s 采样算法可归纳为下面三步，流程图如下图3 1 。 图3 1 简化的g i b b s 采样算法流程幽 具体的算法过程如下： ( 1 )初始化：包括模式模型和背景模型的建立。其一，采用位置频率矩阵 ( p s f m ) 来表示模式模型( m m ) 。首先合理地随机生成模式在各条序列中的起始位 点，记为s p b 。i f 一1 ，竹) 根据起始位点和用户定义的模式长度得到候选 模式，并根据这些候选模式建立位置频率矩阵。其二，背景模型( b m ) 通常采 用独立性模型，记为删一幻，鼋。，口。，q ，) ，表示各碱基在背景序列中的出现频率。 ( 2 ) 更新：从d n a 序列集中顺序选取一条序列s ；o 一1 ，_ ，1 ) ，从s p 中删除 属于该序列的起始位点，根据变化后的s p 重新计算删。然后分别根据候选 模式模型和背景模型计算s ；中所有可能的候选模式模型s ；【，j + f 一1 】( 其中 ，一1 2 ，厶一f + 1 ) 的得分s 。( f ，j ) 和s 。( f ，) ，即计算序列s ；中从第j 位到第 ，+ z 一1 位的序列片段是候选模式的可能性及是背景序列的可能性。这里： & 瓴d 强疃u 一卜川删。罂 岛” f + 力式( 3 - 1 ) s 一。s a 叫，小1 】i 肼) 。加门 ( 3 ) 采样：计算两种得分的比值j ，并按照轮盘赌原理选取新的侯选模 式，即以较大的概率选取比值较高的侯选模式，将其起始位点加入到s p 。根据新 的起始位点集s p 和模式长度得到候选元件并按照下式计算得分f ，若大于前一 次得分，则转到步骤( 2 ) ，继续迭代；否则重复步骤( 3 ) ，直至重复次数大于一个预 设定值( 如1 5 次) 。若所有序列都处理完，则转步骤( 4 ) ，否则转步骤( 2 ) 。 第三章d n a 序列模式发现算法 s 。( f ，) n 。i 而 式( 3 2 ) n 崧一恻l o 颤掣l 姗) 其中q 。指字符集中第j 个字符。 ( 4 )终止：若得分连续多次没有改进( 如1 5 次) 或达到最大迭代次数，则 终止程序，否则转步骤( 2 ) 。 g i b b s 采样算法中背景模型的建立是以单核苷酸独立分布为基础的，这种简 单的模型不足以反映基因组序列的复杂结构。d n a 序列某一位置上出现的核苷酸 受到其上下文核苷酸的影响，而描述这种相关性的一种较理想的模型就是马尔可 夫模型( m a 血0 vm o d d ，m m ) 。m m 能表示出历史状态对当前状态的影响，使分 析生物序列数据经常采用的模型。n i i s 等采用固定阶数的m m ( f m m ) 建立系 统背景模型来改进g i b b ss 柚p l i n g 算法，并应用于模拟数据和a r a b i d o p s i st h a l i 柚a 序列数据集，结果表明改进后的算法识别序列模式的能力得到了提高，他们在文 章中也表明不同阶数的m m 对算法的改进程度也不同，并且通过实验的方法确定 了阶数的最优值。然而f m m 模型存在两个缺点：一方面，对于特定的数据，阶 数过低的m m 不能完全反映历史状态对当前状态的影响；另一方面，由于m m 待 估计的参数数目与阶数呈指数增长，阶数过高，部分参数估计的可信度会因为数 据量的不足而降低，这就要求寻找两者之间的最佳结合点。内插马尔可夫 ( h l t e r p o l a t c dm m ，i m m ) 是指多个不同阶数的m m 插值组合模型。i m m 已被 成功应用于解决基因识别问题，这说明聊m 是解决这种矛盾的优秀模型。下面对 如何构建蹦m 来建模背景序列进行介绍。 马尔可夫模型 。 d n a 序列墨一如， 可看成是一条随机变量序列，的概率分布取 决于周围碱基的组成。对序列建立k 阶马尔可夫模型( k m m ) 是指序列中的的 取值由其前k 个变量饥 ，。 ( 称为k - m m 单词) 决定，l m m 可以用矿“转 移概率参数p ( 1 。，。) 来描述。记单词的出现次数为( ) ，在数据量足够 多的情况下，转移概率的最大似然估计为： 酬铲。舳) = 带戮 引3 4 ) “ 生物序列模式发现算法的研究 则根据k - m m 产生序列s 的概率为： ) 。2 ：，) p ( ? i 翟_ ，翟、 式( 3 - 5 ) p ( i 。，一) p 1 。，一t ) 。 插值马尔可夫模型 理论上希望用高阶m m 来建模，因为模型阶数越高越能体现出历史数据对现 有状态的影响，而且高阶模型也完全能够模拟低阶模型。例如，当 p ( l 墨：，墨。) 一p ( l 墨：，毛。，) 成立时，3 阶模型等价于2 阶模型。但是m m 的参 数是随阶数k 呈指数增长的，在实际应用中常常没有足够多的数据来对参数进行 有效估计。因此在实际数据集中，当某些长度的单词出现次数很少不足以估计模 型参数时，需要用低阶模型来表示，但是也有些相同长度的单词出现频率完全可 以用于估计模型参数。这就需要在数据量和上下文相关性间寻找一种权衡策略。 插值马尔可夫模型正好满足这种需求。k 阶差值马尔可夫模型( k i m m ) 是指： 当前变量的出现频率不仅决定于前面出现的k m m 单词，而是由前m m m 到k m m 共t + 1 种单词按某种插值规律组和而决定的。本改进方法中采用最简单的线性插 值来构建i m m ，数学表达式为： 她h 嘞- l 卜2 嚣乏i z 删 加神 + f p fi - 1 ) + 凡，p ( ) 可转化为递归形式如下： 碱h 十嘞j 。勰篆裂嘶， 加棚 + ( 1 一) 只- ( i 呀。，岛。) 。 其中，表示- ( 岛。，勺。) ，并且- 1 。 背景模型可以根据选定模式生物的全基因组非编码序列来构建，也可以直接 根据输入序列来建立，还可以用亲缘关系较近的模式生物基因组序列来代替。主 要包括确定转移概率和插值系数。转移概率可根据公式( 3 - 4 ) 计算，而插值系数 采用g l i m m c r 中的方法确定，具体步骤如下： 嘞。，勖。) 为k - m m 单词勖。，勤一，的出现次数，当嘞- i ，。) 大于某 一阈值6 时，定义九- 1 。 否则，考虑序列集中瓴4 ，。，6 ) 与嘞- t 。，。，6 ) ，其中6 q m 。 用z 2 统计来衡量这种差异性，当自由度一定时z 2 值越大则差异性也就越明显， 也就越说明不能用低阶模型来代替高阶模型。 令： 第三章d n a 序列模式发现算法 1 5 存五监焉东瓮铲学 加渤 上述公式中有3 个自由参数，因此z 2 统计的自由度为3 ；定义口为对应的z 2 统计重要性水平，当盯z 0 5 时，令： 掣 式( 3 9 ) 否则气一0 。 由于背景模型建立以后，在g i b b s 采样算法的迭代过程中不再变化，所以背 景模型可以在初始化阶段建立，然后在采样阶段被用于计算位点由背景序列产生 的概率。 2 m e m e e m 算法 m e m e 首先是由t i m o t h yl b a n e y 和c h a l l e se l k 卸提出来的，由两个子程序 m e m e 和m a s t 组成。m e m e 用来发现模式，而m a s t 能够利用m e m e 所 发现到的模式进行序列比对和数据库搜索。m e m e 算法是建立在e m ( e x p c c t a t i m a i m i z a t i o n l 算法【捌的基础上的，应用e m 算法，m e m e 方法能够从没有任何 优先假设的不比对的序列中识别出没有空格的模式。e m 算法是一种迭代算法，交 替执行两个步骤：即e 步骤( 求期望值) 和m 步骤( 最大化) 。在e 步骤中，通 过估计观测到的数据和模型参数，计算隐变量分布。在m 步骤中，利用e 步骤计 算所得分布，计算参数最优可能值。这两个步骤交替执行直到最后收敛。其基本 算法思想为：先对序列集建立二元有限混合模型旧，再运用最大似然估计法对模 型的参数值进行估计。 设序列集为s - 谯i f - 1 ，2 ，n ，丘l 墨l ，取墨中所有长度为f 的子序列构成 新的序列集x 一“，而，h ，其中- 二d 以一f + 1 ) 。由于毛可能是序列模式，也 可能是非模式序列( 称为背景序列) ，因此x 可看成是一个随机向量。当薯是模 式序列时，可用每个位置上碱基出现的概率来表征，即五一( 厶，厶，允，岛) ， f 一1 2 ，f ；当鼍为背景序列时，所有位置上的碱基用概率分布来表示。 ，0 一( 厶。，厶。，帖，0 ) 。二元有限混合模型是建立在序列集合x 的基础上的