（计算机科学与技术专业论文）图形表示在dna基因序列识别算法中的应用.pdf

硕l ! 学化论文 摘要 随着人类基因组计划的实施，生物基因序列数量和碱基个数呈指数级增长。 如何对这些基因数据进行开发、分析和利用，并从中挖掘出潜在的生物学信息是 目前急需解决的重要问题，也是生物信息学的主要研究内容。基因识别是基因组 分析的基础，其首要任务是从已测序列中找出所有的蛋白质编码基因，再进一步 预测基因的结构和功能。剪接是基因转变为蛋白质的重要步骤，剪接错误是许多 疾病的根源。因此，识别序列编码区非编码区和剪接位点的重要性不言而喻。 本文使用图形的方法表示基因序列，主要对人类基因蛋白质编码区识别以及剪接 受体位点识别进行了研究。 本文在d n a 基因序列图形表达的基础上提出了d n a 序列新的特征表示p z 曲 线，并使用支持向量机做为判别器对人类基因短编码序列进行了编码区和非编码 区识别。为提高识别效率，将序列样本按照g c 含量分为三组，对每组数据分别 训练支持向量机模型。在此过程中，针对负样本缺少的问题提出了一种改进的自 相似映射的方法生成了足够数量的负样本用于识别。实验结果表明，本文提出的 识别方法使用较少的参数获得了较高的准确率。 目前序列图形表示在真核生物剪接位点的识别中的应用很少，还需要进一步 发展。由于剪接位点两侧序列分别是编码区和非编码区，二者在密码子偏好、碱 基近程相关性等方面存在较大的差异。本文使用p z 曲线提取出剪接受体位点序 列及受体位点上下游自序列的特征，将其用于受体位点识别，并使用支持向量机 做为判别器。实验结果证明了图形方法在受体位点识别中的可行性，且此方法计 算简单，识别准确率与已有的位点识别方法相当。 关键词：d n a ；图形表达；基因识别；编码区非编码区；剪接位点；受体位点； 支持向量机 i i 图形表，j ij l ：d n a 基冈序列识别算法中的应用 a b s t r a c t c u r r e n t ly ，t h en u m b e ro fd n as e q u e n c e sa n db a s e si nn u c l e o t i d es e q u e n c e d a t a b a s ei si n c r e a s i n ge x p o n e n t i a l l yw i t ht h ed e v e l o p m e n to fh u m a ng e n eg r o u p s ( h g p ) i ti sn e c e s s a r yt od e v e l o pa n a l y s i sa n dc o m p u t a t i o nm e t h o d so fg e n o m ed a t a g e n ei d e n t i f i c a t i o ni sa ni m p o r t a n ta n db a s a lp a r to fb i o i n f o r m a t i c s r e c o g n i t i o no f c o d i n g n o n c o d i n gs e q u e n c e si st h ef i r s ti m p o r t a n tt a s ko fg e n ei d e n t i f i c a t i o n i n g e n o m i cr e s e a r c hi t s ad e c i s i v es t e p s p l i c i n gi s a ni m p o r t a n tp r o c e s so fg e n e e x p r e s s i n g 1 垤a n yd i s e a s e sw o u l db ec a u s e di ft h es p l i c i n gp r o c e s sh a sam i s t a k e s o ， r e c o g n i t i o no fs p l i c es i t e si sa n o t h e ri m p o r t a n ts u b j e c t i nt h i sp a p e rw ef - o c u so n t h e s et w op r o b l e m s ，a n dp r o p o s ea l g o r i t h m so fr e c o g n i z i n gc o d i n g n o n c o n d i n g s e q u e n c e sa n da c c e p t o rs i t e s i nt h i sp a p e r ，w ep r e s e n tan o v e lf e a t u r er e p r e s e n t a t i o no fd n as e q u e n c e sb a s e d o nt h eg r a p h i c a lr e p r e s e n t a t i o nc a l l e dp z - c u r v e s u p p o r tv e c t o rm a c h i n e ( s v m ) i s a p p l i e dt oc l a s s i f yt h ec o d i n g u n c o d i n gs e q u e n c ei ns h o r th u m a ng e n e s i nt h e p r o c e s so fi d e n t i f y i n g ，w ep r o p o s ea ni m p r o v e ds e l f 二s i m i l a rm a pm e t h o dt oa v o i dt h e l a c ko fn e g a t i v es a m p l e ss e q u e n c e a c c o r d i n gt ot h eg cc o n t e n tw ed i v i d et h e d a t a s e ti n t os e v e r a lg r o u p sa n di d e n t i f l yt h e s es e q u e n c e sr e s p e c t i v e l y t h er e s u l t s s h o wt h a tt h ep r o p o s e dm e t h o do b t a i n sah i g h e ra c c u r a c yw i t hf e w e rp a r a m e t e r s m e t h o d so fg e n es p l i c es i t e r e c o g n i t i o nu s u a l l yb a s e do ns t a t i s t i c s g e n e g r a p h i c a lr e p r e s e n t a t i o ni sa p p l i e di nt h i sp a p e rt oi d e n t i f ya c c e p t o rs i t e si nh u m a n g e n e s f o re a c hs e q u e n c e st ob er e c o g n i z e d ，w eu s et h ep z - c u r v et oe x t r a c tf 宅a t h e r s f r o mt h ew h o l es e q u e n c e sa n dt h es u b s e q u e n c e sa r o u n da c c e p t o rs i t e s ，a n dc a l c u l a t e t h ed i f f e r e n c e sb e t w e e ne x t r o n sa n di n t r o n s t h e s ef e a t h e r sc o n s i d e ft h ef e q u e n c i e s o fp h a s e i n d e p e n d e n to fm o n o n u c l e o t i d e s ，d i n u c l e o t i d e sa n dt r i n u c l e o t i d e s s v m i sa p p l i e da sc l a s s f i e r t h er e s u l t ss h o wt h a to u rm e t h o di sf e a s i b l e a n do u rm e t h o d g e t sa na c c u a r ya l m o s te q u a lw i t he x i s t i n gs p l i c es i t er e c o g n i t i o nm e t h o d ，w h i l eo u r m e t h o di se a s yt ou n d e r s t a n da n dc a l c u l a t e k e yw o r d s ：d n a ；g r a p h i c a lr e p r e s e n t a t i o n ；g e n er e c o g n i t i o n ；c o d i n g n o n - c o d i n g s e q u e n c e ；s p l i c es i t e ；a c c e p t o rs i t e ；s u p p o r tv e c t o rm a c h i n e i i i 硕i j 学位论文 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图3 1 图3 2 图3 3 图3 4 图4 1 图4 2 图4 3 图4 4 插图索引 真核生物基因结构及剪接示意图8 二维图形的三种坐标1 0 人类d 球蛋白第一个外显子序列的d n a2 dm a p 表示1 l 基于图形表达的基因识别步骤1 2 隐马尔可夫模型示意图1 7 b p 神经网络模型示意图1 7 支持向量机模型示意图一1 8 最优超平面示意图2 7 对g c 含量在0 4 5 的数据训练a n n 的收敛过程2 9 对g c 含量在4 5 5 5 的数据训练a n n 的收敛过程2 9 对g c 含量在5 5 1 0 0 的数据训练a n n 的收敛过程2 9 h s 3 d 真实受体位点序列样本3 5 h s 3 d 虚假受体位点序列样本3 5 剪接受体位点序列截取示意图3 5 特征及l 的选取与识别准确率的关系3 8 v i 图形表示在d n a 基冈序列识别算法中的应用 附表索引 表3 1按照g c 含量分组序列数量统计2 4 表3 2使用a n n 对分组数据识别的s n 、s 。和a 。值3 0 表3 3使用不同的u 、v 值进行识别的s n 、s p 和a c 值3 0 表3 4 使用s v m 对分组数据识别的s n 、s p 和a c 值3 1 表3 5使用不同的负样本生成算法的识别结果对比3 1 表3 6几种基因识别方法准确率对比一3 2 表4 1对序列特征集a 1 l 的剪接受体位点识别结果3 7 表4 2对序列特征集d i f 的剪接受体位点识别结果3 7 表4 3对特征集l i n k 的剪接受体位点识别结果3 8 表4 4使用不同的u 、v 对不同比例正负数据集进行识别的q 9 值4 0 表4 5对不同比例正负样本集的剪接受体位点识别结果一4 1 表4 6正负样本比例为1 ：1 的剪接受体位点识别方法准确率对比4 1 表4 7正负样本比例为1 ：4 的剪接受体位点识别方法准确率对比4 2 表4 8正负样本比例为1 ：10 的剪接受体位点识别方法准确率对比4 2 v i l 硕 ：学位论文 1 1 研究目的 第1 章绪论 本文主要研究基于d n a 序列图形表达及其在基因识别问题中的应用，设计 并实现识别效果较好的真核生物基因识别算法，并着力于识别基因编码区非编 码区和剪接受体位点。主要研究内容有： 1 、综合已有的d n a 序列图形表示方法，提出合适的图形表达方法，并以此 为基础提取新的d n a 序列特征向量。 2 、利用提取到的新d n a 序列特征向量，找出合适的分类器对人类基因短编 码序列进行编码区非编码区识别。 3 、使用基于图形的方法分析真实虚假剪接位点特征差异，使用合适的分类 器实现对人类基因剪接受体位点的预测。 1 2 本文的项目来源 本学位论文的研究工作主要得到以下项目的资助： ( 1 ) 国家自然科学基金资助项目( 6 0 8 7 3 1 8 4 ) ：新型表达模式下的功能基因分 析算法研究。 ( 2 ) 湖南省自然科学基金资助项目( 0 7 j j 5 0 8 6 ) ：基于聚类的基因功能预测方 法。 1 3 研究背景和意义 随着人类基因组计划( h u m a ng e n o m i cp r o i e c t ，h g p ) 实施的迸一步深入， 生命科学已步入后基因组时代，国际三大核酸序列数据库g e n e b a n k 、e m b l 和 d d b j 的序列数量和碱基个数正在呈指数级增长。大规模的基因测序仅仅是对数 据的获取和积累，面对如何开发、分析和利用巨大而复杂的生物信息数据的问题， 一门新的学科生物信息学( b i o i n f o r m a t i c s ) 应运而生，发展到现在已成为研 究生命科学发展的重要组成学科。生物信息学是一门交叉学科，其主要研究对象 是核酸和蛋白质，将生物学与数学、信息科学和计算机科学等学科综合利用，以 获得生物基因结构并进行基因功能注释和分析。将生物基因研究与计算机技术相 结合是基因组研究取得成果的决定性步骤，也是解决基因数据量巨大，遗传机制 复杂等问题的有效手段。生物信息学的主要研究内容包括【l 】：收集、存储、管理 与提供生物信息；提取和分析基因组序列信息；对功能基因组待相关信息进行分 析；模拟生物大分子结构并研发新药；以及对生物信息分析技术与方法的研究等 方面。 基因识别【2 】是指对已经完成测序的基因序列，通过生物实验或计算机等途 径，识别生物基因序列的内在结构，找出具有生物学特征和功能的片段。基因识 别是生物信息学的一个重要分支，也是基因组研究和生物进化关系的基础。基因 识别的对象主要是蛋白质编码基因，以及具有一定生物学功能的调控因子，如 r n a 基因、剪接位点和调控因子等。由于基因数据规模庞大，基因内部各种机 制极为复杂，仅依靠生物实验的方法识别出全部基因相当困难，因此急需找出快 速、准确的序列识别、分析和注释算法来解决这一问题。计算机辅助基因识别 ( c o m p u t e 卜a i d e dg e n er e c o g n i t i o n ) 因而成为生物信息学的核心课题之一。其研究 内容是对于给定的基因组序列，正确识别基因的范围、结构和功能以及基因在基 因组中的准确位置。以d n a 基本序列为出发点，结合使用计算机技术，实现对 生物基因的识别和注释，可以帮助研究者们更好的了解遗传机制、解析基因功能、 破译遗传密码，推动医学、生物学、遗传学、生物信息学、计算分子生物学等各 个相关学科的发展并提供更多的研究基础。寻找效率高、效果好的基因识别算法 已成为研究的关键所在。 蛋白质编码区是d n a 序列的重要组成部分，它决定着基因产物的结构及功 能，直接影响生物性状和外在表征，因此当完成一个物种基因组序列的测定后， 首先要解决的问题就足从所测序列中找出所有的蛋白质编码基因【2 ，3 】，随后才能 更进一步预测基因的各种结构和功能。就目前研究状况来说，d n a 序列编码区 的识别，尤其是对真核生物短编码区的识别效果不够高，仍需要进一步丌发精度 较高的识别算法。 剪接位点识别是基因识别的另一项重要内容。剪接( s p l i c i n g ) 是指将非编 码序列，也称为内含子( i n t r o n ) 从原初r n a ( p r e m r n a ) 的最初转录产物中 除去，并将编码序列，也称为外显子( e x t r o n ) 连接起来形成一个连续的r n a 分子的过程。剪接是真核生物细胞基因表达的重要阶段【4 】，剪接的正确与否依赖 于剪接位点，剪接错误是引起许多遗传病和肿瘤发生的重要原因【5 】。但迄今为止 仍未有识别率足够高的剪接位点识别软件，人们对剪接机制的了解还不十分清 楚，仅依靠g t a g 规则会产生大量误判，因此寻找基因剪接位点识别方法是 基因识别中急需解决的问题。 综上，尽管基因组研究已经进入后基因组时代，d n a 序列数据仍是生物信 息学的主要研究对象之一。其中，编码区非编码区识别是进一步研究d n a 基因 结构的基础，对d n a 序列编码区的识别，尤其是真核生物短编码区的识别还需 改进，对真核生物剪接位点的识别仍有待进一步的发展。 2 硕f j 学位论文 1 4 国内外研究现状 早期基因识别的主要方法是进行活细胞或生物实验。但由于基因组信息数量 巨大、基因结构复杂，依靠较慢的生物实验方式根本无法满足基因识别的需要。 自上世纪八十年代初以来，计算机辅助基因识别算法研究已取得很大的进展，研 究者们提出了几十种预测蛋白质编码基因的算法，已有其中十几种识别结果较好 的算法开发成生物学软件，并提供网上免费服务【6 】。 按照识别方法的不同，基因识别算法可分为两类【6 】：基于序列同源性的方法 ( h o m o l o g y b a s e dm e t h o d s ) 和基于序列组成统计学特征的方法( s t a t i c s b a s e d m e t h o d s ) 。其中，基于序列同源性的基因识别方法主要利用序列比对工具( 如 b l a s t 、f a s t a 等) 搜索基因数据库中已知序列在生物实验中的数据，这些已 知序列包括e s t 序列、m r n a 序列、蛋白质数据库等。再利用实验上的数据与要 识别的d n a 序列进行相似性比对，从而筛选出可能的基因，预测出可能存在的 功能因子。如经典的s g p 1 算法【7 1 ，就是利用同源生物的基因序列相似性推测基 因模型。由于多数物种实验数据的缺乏，使得基于序列同源性的基因识别算法准 确率普遍偏低。因此更多的研究人员选用基于序列统计学特征的方法进行基因识 别。基于序列组成统计学特征的识别方法也可称为从头预测( a bi n i t i o ) 的方法， 它的主要思想是使用统计学的方法寻找蛋白质编码区和非编码区碱基组成的特 征差异以及功能位点附近的保守信号，以此实现基因识别的目的。从上个世纪八 十年代以来，s h e p h e “8 1 ，f i c k e t t 【9 】，s t a d e n 和m c l a c h l a n 1 0 1 等人先后发现，在d n a 序列的编码区和非编码区存在着明显的统计学差异，此后基于统计的方法就被广 泛应用于基因编码区的识别中，主要使用的识别变量包括氨基酸使用【9 】、密码子 使用【9 ，1 们、编码区的三周期性和功率谱【1 1 ，12 1 、傅立叶变换【13 1 、六核苷酸频率【1 4 】 等。基于统计的基因识别的优点是，它既不需要实验数据的辅助、也不需要进行 大规模的序列数据比对，因此其识别速度更快，识别准确率也大大提高，但仍有 提升的空间。 近年来，基因序列的图形表示方法j 下在逐步发展，图形的直观性使得基于图 形的方法已经成为研究基因的重要途径之一。一个好的序列图形表示方法不但能 够包含序列内部存在的各种信息特征，而且计算容易，可以广泛用于基因识别的 各个方面。我国的张春霆院士基于正四面体的对称性，提出了序列的z 曲线表示 【1 5 】，并将其广泛用于d n a 和r n a 基因识别，包括真核生物蛋白质编码区识别【j 、 i s c h o r e 结构识别 17 1 、细菌编码区识别【1 8 1 等，并开发出一系列基因识别软件【19 1 ， 在互联网上提供免费服务。z 曲线的典型应用有很多，如使用z 曲线对一种链霉 菌进行核苷酸分布分析【l 引，把序列中核苷酸出现的频率映射成9 维空间的一个 点。为了实现可视化，使用了主成分分析的方法把对所有的0 r f 映射得到的点投 图形表j ：n jd n a 慕冈序列识别算法中的廊用 影到一个二维空间内，而后对这些点进行模糊c 均值聚类，有趣的是，可以观察 到这些点聚成了7 个明显分开的区域，其中一个区域正对应了编码区，另外六个 区域则是根据序列阅读方式的不同而得到的对应的点。使用此方法对该链霉菌编 码区的识别率达到了9 7 7 。除此之外，很多研究者提出了不同的序列图形表达 方式【2 0 ，2 1 1 ，并与统计学、频谱、小波变换等方法相结合，在序列编码区识别中 也获得了较好的结果 2 2 砣4 1 。 尽管目前已经开发出许多基因识别算法，但仍存在很多问题【6 】。相比较于原 核生物基因识别算法来说，真核基因识别算法效果较差。这是由原核生物和真核 生物基因存在的组成差异造成的。对原核生物来说，由于基因组规模比较小、 d n a 的含量较低，且在原核生物中d n a 基本上都参与蛋白编码活动，基因中不 存在分裂现象，因此，原核生物的基因识别相对简单，识别结果也比较好。而真 核生物基因是由编码序列和非编码序列组成的，编码序列所占的比例很少，且编 码序列由非编码序列分隔开来，此外还存在了大量的假基因和重复序列。结构的 复杂性使得真核生物基因识别算法结果较差。另外，对于短基囚的识别结果也较 差。基因长度过短也就意味了统计特征不明显，难以找出适合识别的统计模型。 同时，已有的算法在识别高g c 含量基因组时的伪正率过高。因此，如何从基因 序列中提取新的特征或信号，开发更有效的基因识别算法尤为重要。 在剪接位点识别中，由于在剪接位点附近一般存在较为明显的序列特征，因 此，识别剪接位点的主要思想是对剪接位点及其两侧的编码特性进行综合分析， 如寻找p r e m r n a 的保守序列模型【2 5 1 、分析m r n a 与s n r n a 碱基配对的自由能 【2 6 1 ，比较剪接位点两侧编码区与非编码区序列的统计差别 2 7 1 等。目前己开发出 的剪接位点识别工具有n e t g e n e 27 1 、d g s p l i c 【2 9 1 等。已有的剪接位点识别算法大 多数使用基于统计的方法、信息论方法以及模式识别方法。广泛使用的剪接位点 识别算法有权重矩阵模型【2 9 】( w e i 曲ta r r a ym o d e l ，w a m ) 、隐马尔科夫模型【3 1 】 ( h i d d e nm a r k o vm o d e l ，h m m ) 、人工神经网络【3 4 3 6 】( a r t i f i c i a ln e u r a ln e t w o r k ， a n n ) 、支持向量机【3 7 “o 】( s u p p o r tv e c t o rm e c h i n e ，s v m ) 等。识别时用来表 示序列数字特征的方法一般有两种：一种是使用统计和模式识别的方法提取序列 特征【39 1 ，将剪接位点附近的保守序列作为识别信号来进行剪接位点识别，并进 行特征选择，同时对判别器进行改进寻找最佳判别器参数，取得了较好的识别效 果。另一种则是对a 、c 、g 、t 进行二进制编码【3 4 ，35 1 ，如a = 1 0 0 0 ，c = 0 1 0 0 ， g = 0 0 1 0 ，t = 0 0 0 l 。将这些只由0 和l 组成的向量直接输入判别器或与权重矩阵 模型相结合进行判别。这种方法不考虑特征的提取，由判别器自动进行学习、分 类，得到的结果一般低于第一种方法。总体来看，目前已有的剪接位点识别效率 都不高，供体位点识别效率低于受体位点，但大都不超过9 5 ，仍需寻找更好 的位点识别方法，提高识别准确率。 4 硕十学位论文 除了使用传统的统计或信息论的方法表示序列特征之外，也有人把图形表示 用于基因识别。这些方法多是利用图形的直观性观察发现序列区域的图形差异， 进而设计识别算法。如n a n d y 等人使用他们所提出的图形表示序列内含子和外显 子区域时，观察发现图形显出不同的特点，通过对图形的密度、斜率等特征的提 取，并结合聚类的思想针对人类3 号染色体进行了基因识别1 4 1 1 。z c u r v ee 【4 2 】是另 一个基于z 曲线方法的真核生物基因识别软件，它使用了图形的方法来识别基因 编码区，但对各个功能位点的识别是采用了位置权重矩阵等传统的方法。近几年， 张春霆等将z 曲线理论进一步发展，提出了d n a 基因序列分段新算法【4 3 1 ，并将其 应用于脊椎动物剪接位点识别中，但识别效果不够好，灵敏度较低。因此，能否 用基于图形的方法，如何使用基于图形表示的方法寻找高识别率的剪接位点识别 算法仍是需要解决的问题。 1 5 论文主要工作及结构安排 本文主要研究d n a 序列的图形表达及其在基因识别问题上的应用，设计并 开发识别效果较好的真核生物基因识别算法。主要研究内容有： 1 、结合已有的d n a 序列图形表示方法，分析它们的优缺点，提出合适的图 形表达d n a 序列p z 曲线，并在图形的基础上提取出新的d n a 序列特征向量。 2 、利用找出的d n a 序列特征向量来进行基因识别，使用支持向量机实现了 对人类短基因编码区非编码区的识别。为提高识别精度，按照序列g c 含量对样 本分组，对每一组数据分别训练支持向量机模型。鉴于分组时出现了负样本数量 不足的问题，提出了一种改进的自相似映射的方法以生成足够数量的负样本，并 将其用于基因识别。实验结果表明，该识别方法使用了较少的参数，却取得了较 好的识别效果。 3 、使用基于图形的方法分析剪接位点两侧序列差异，对每条序列使用与编 码区识别方法中相同的序列图形表示法提取出一系列特征，主要考虑了终止密码 子在编码非编码区上各个相位分布的差异。使用支持向量机对人类基因剪接受 体位点进行了预测，实验结果不但证明了基于图形的方法在剪接受体位点识别中 具有可行性，而且与已有的方法相比，这种方法不但有相当的识别效果，而且基 于图形提取出的特征简单明了，易于计算。 全文共包含4 章，各章内容如下： 第l 章绪论。介绍本论文的项目来源、研究背景和意义、生物信息学的主 要研究内容、基因识别的定义及其研究发展现状，最后介绍了论文的主要工作内 容和结构安排。 第2 章基因序列图形表示及其在基因识别中的应用。首先介绍了几种主要 的基因序列图形表示：g 曲线、h 曲线、二维表示方法、z 曲线等，并总结分析 图形表j ：4 ：d n a 基冈序列识别算法中的心用 它们的优缺点。然后介绍了基于图形的基因识别方法的一般步骤，列举了一些典 型的基于图形的基因识别应用，详细说明了几种主要的判别方法及原理。 第3 章基于d n a 序列图形表达的人类短基因编码非编码区识别。对z 曲 线进行了改进得到p z 曲线，它既消除了z 曲线中可能存在的环，也保持来z 曲 线原有的生物学意义。在此图形表达的基础上，提出了d n a 序列新的特征表示。 使用支持向量机对人类基因短编码序列进行了编码区和非编码区识别。在识别过 程中，针对负样本缺少的问题提出了一种改进的自相似映射的方法生成了足够数 量的负样本，并按照g c 含量将数据进行分组识别。实验结果表明，该识别方法 使用较少的参数获得了较高的准确率。 第4 章基于图形表示的人类基因剪接受体位点识别。使用第三章中的p z 曲线对剪接位点序列及其子序列提取出一系列的特征，计算子序列的特征差异。 组合不同的特征，考虑了序列中单核苷酸、双核苷酸以及三核苷酸的使用偏好及 近程相关性。使用支持向量机作为判别器对人类基因剪接受体位点进行了预测。 实验结果表明，基于图形的方法在剪接受体位点识别中的可行性，与已有的方法 相比具有相当的识别率。 最后，总结了全文的研究工作并对未来的研究工作进行展望，提出了下一步 需要改进的问题。 6 硕 学位论文 第2 章基因序列图形表示及其在基因识别中的应用 2 1 真核生物基因结构 2 1 1d n a 和基因 d n a 是存在生物细胞核内的遗传物质，是绝大部分生物的基因组的组成部 分。d n a 由包含不同含量碱基的核苷酸组成，多个核苷酸通过不同排列形成多 聚核苷酸，多聚核苷酸再进行排列，组成d n a 大分子。组成核苷酸的碱基有四 种，即腺嘌呤、鸟嘌呤、胞嘧啶和胸腺嘧啶，分别表示为a ，g ，c ，t 。目前已 知d n a 为双螺旋结构，即在d n a 分子中由两条碱基单链上的碱基配对形成氢键， 由氢键连接两条单链围绕中心轴反向平行排列。这种碱基配对的现象被称为碱基 互补。其中腺嘌呤( a ) 与胸腺嘧啶( t ) 配对，形成两条氢键；鸟嘌呤( g ) 与 胞嘧啶( c ) 配对，形成三条氢键。对于d n a 双链来说，由于互补现象的存在， 我们只需研究其中一条单链即可，在研究中每条序列即为由a 、g 、c 、t 四个字 符组成的字符串。 基因组中的遗传信息主要由核苷酸序列编码体现。这些核苷酸序列所组成的 在d n a 序列中具有遗传效应的片段单元称为基因。基因表达指的是在某一基因 指导下，通过一系列生物化学反应蛋白质的合成过程，共包括转录和翻译两个阶 段。合成的蛋白质中包含了该基因中所有的遗传信息，可以说基因是控制生物性 状的基本遗传单位。生物体通过基因的复制、表达及修复完成细胞分裂等重要生 理过程。本文中我们所提到的基因仅指编码蛋白质的基因序列。 2 1 2 真核生物基因结构和剪接 大多数真核生物( 包括人类) 的主要遗传信息存在于蛋白质编码序列，这些 序列通常是不连续的，由一些非编码序列打断，如图2 1 。其中，编码序列被称 为外显子( e x o n ) ，非编码序列被称为内含子( i n t r o n ) 。 在基因表达过程中，d n a 序列通过转录产生一条r n a 链，这条r n a 链与d n a 的一条单链的组成完全相同，称之为p r e m r n a 。在由初始转录物p r e m r n a 产生 成熟的m r n a 过程中，内含子首先被清除掉，外显子随后被连接起来，这一过程 称为r n a 剪接( r n as p l i c i n g ) ，也可以直接称做剪接( s p l i c i n g ) 。m r n a 通过翻译 即成为蛋白质。m r n a 上每三个相连的核苷酸组成了三联体密码，称之为密码子。 密码子共有4 3 = 6 4 种，其中6 1 种密码子构成氨基酸，余下三种密码子t a a 、t a g 和t g a 是终止密码子。基因从起始密码子处开始，于终止密码子结束。在蛋白 图形表示在d n a 皋凼序列识别算法中的应用 质编码区和非编码区中，终止密码子分布存在很大的差异。终止密码子是我们 第三章中识别编码非编码区的重要判别依据。 在基因中，以三个碱基为一组编码蛋白质，易知编码序列具有3 周期性。因 此，基因序列可分为3 个相位，我们把第1 、4 、7 、碱基所在的位置称为第 一相位：把第2 、5 、8 、碱基所在的位置称为第二相位；把第3 、6 、9 、 碱基所在的位置称为第三相位【1 6 】。第1 、2 、3 相位也就对应于密码子的第1 、2 、 3 位。 一一一一- 一l 一一一一- 、 i t r a n s c r i p t i o n ) 、- - - 一工一 ，一一一一一i 一一一，、 - p r o c e s s i n g 二j 、- - - 一工一_ ，一一一一一一l 一一- - - 、 、- _ 一一工一一- _ ，7 a g a c g a g a t a a a t c g a t t a c a g t c a e x o ni n t r o ne x o ni n t r o ne x o n 。- j | ，7 ，7 p r o t e i n p r o t e l ns e q u e n c e 图2 1 真核生物基因结构及剪接示意图【4 4 】 从对序列的碱基统计中发现，剪接位点附近存在很短但是却高度保守 ( c o n s e n s u ss e q u e n c e ) 的序列。基本上每个5 端剪接位点都含有g t ，这个剪接位 点被称为供体( d o n o r ) 位点；3 端剪接位点都含有a g ，这个剪接位点被称为受体 ( a c c e p t o r ) 位点。这一现象被称为“g t a g 法则”，这是普遍存在的剪接位点识 别信号。但是g t 与a g 碱基也会经常出现于基因的其它位点，仅依靠g t a g 法 则来判断剪接位点会得到大量错误的结果。 2 2 基因序列图形表示 目前普遍使用的d n a 序列是由四种碱基( a 、g 、t 、c ) 所表示的字符串形 式，对于这种单一的字母序列来说其意义并非一目了然，想要直接从原始序列中 寻找有用的识别信号需要经过大量的数学统计和计算，较为困难。近年来，基因 序列的图形表示方法j 下在逐步发展，已成为研究基因的一条重要途径。基因序列 图形表示的基本思想是把d n a 序列表示成一条空间曲线。图形表达方法具有很 硕l ：学位论文 强的直观性，也更有利于对基因和基因组进行进一步分析。基因序列的图形表示 可应用于生物信息学中很多方面，如：序列相似性比对、系统发生树的构造、识 别基因功能区等。 2 2 1g 曲线和h 曲线 e h a m o r i 于19 8 3 年首次提出了表示d n a 序列的图形方法g 曲线和h 曲 线【4 5 1 。g 曲线的四个坐标方向代表四种核苷酸( a 、g 、t 、c ) ，另一个方向表 示d n a 序列核苷酸的位置特征，但g 曲线是5 维曲线，无法实现可视化。 若在三维平面上，使用两个坐标轴的四个方向代表四种核苷酸( a n w ： c n e ；g s e ；t s w ) ，使用另一个维的方向表示核苷酸位置位置特征，曲线 就可以在三维空间内画出，称之为h 曲线。e h a m o r i 和r u s k i n 使用h 曲线发现 了在几种病毒b a c t e r i o p h a g em 13 、h i v 以及e b v 中的碱基含量存在着剧烈变化的 区域【4 6 1 。 2 2 2c g r 图 在1 9 9 0 年由j e f f r e y 提出了c g r 图4 7 1 ( c h a o sg a m er e p r e s e n t a t i o n ) 。c g r 图基 于混沌理论，并结合了图形表示和数学表达，将一条序列对应于一张具有固有分 形结构的图。如果序列是完全随机的，则其c g r 图分布均匀，而d n a 序列一般 都具有自身的结构，则该序列的c g r 图就会表现出不同的外形( 如珊瑚、云、山 等) 。 c g r 图在基因组分析中取得了较好的成果【47 1 。但在1 9 9 3 年，g 0 1 d m a n 指出， 使用序列的单核苷酸、双核苷酸及三核苷酸频率就可以解释c g r 图的各种分形结 构【4 引。 2 2 3 三种相似的二维曲线 ( 1 ) m a g a t e s 于l9 8 6 年提出了最早的二维图形表示4 9 1 ，定义+ x 轴方向对 应于碱基c ，x 轴方向对应于碱基g ，+ y 轴方向对应于碱基t ，y 轴方向对应于碱 基a 。 ( 2 ) a n a n d y 于l9 9 4 年提出了一种二维图形表示【5 0 1 ，定义+ x 轴方向对应于 碱基g ，一x 轴方向对应于碱基a ，+ y 轴方向对应于碱基c ，y 轴方向对应于碱基t 。 ( 3 ) p m l e o n g 和s m o r g e n t h a l e r 于19 9 5 年给出了另一个二维图形表示5 1 1 ， 定义+ x 轴方向对应于碱基a ，x 轴方向对应于碱基c ，+ y 轴方向对应于碱基t ，y 轴方向对应于碱基g 。 这三种图形如图2 2 所示。这三种序列图形表示法大同小异，都是以坐标原 点为起始点，随着序列长度的增加，按照碱基所对应的方向增加一个单位向量。 且这三种表示方法都有一个共同的缺点：它们都可能出现自交和重叠，即存在图 9 图形表，j 柏：d n a 攮冈序列识别算法中的应用 形退化。如，对于不同的序列a t ，a 1 r a ，a t a t 和a t a t a ，使用这些图形表示 方法得到的图形是相同的，将难以区分。另外，这三种图形也并未包含了明确的 序列生物学意义。 jl ， - t g -j l 1 r c x jl ， ic 一 1 r g x t i _l ， t c 一- tir l x g 图2 2 二维图形的三种坐标 2 2 4z 曲线 z 曲线理论是由我国的张春霆院士提出的d n a 序列的几何化表示方法。z 曲线是显示和分析d n a 序列的直观工具，z 曲线的提出开创了一个利用几何学 方法分析和研究d n a 序列的崭新领域【15 1 。对于长度为n 的单链d n a 序列，z 曲线每一节点的直角坐标可表示为： i 以= ( 4 + g ) 一( e + z ) 以= ( 4 + e ) 一( q + z ) ，毛，以，乙 一】，n 2 0 ，1 ，2 ，n( 2 1 ) 【z 。= ( 4 + z ) 一( q + e ) 其中，4 ，q ，e ，乙分别表示碱基a 、g 、c 、t 在从l 到n 子序列中出现的 次数。设p o 为三维空间内的坐标原点，p 。( x 。，y 。，z n ) 表示d n a 序列中第n 个碱基的 坐标，将所有的点p o ，p l ，p 2 ，p n ，p n 连接起来即为长度为n 的d n a 序列的z 曲线。经证明，z 曲线具有一一对应性、等步性、对称性、唯一性等特点。此外， z 曲线的三个分量有着明确的生物学意义【1 5 1 ： ( 1 ) 表示嘌呤( a + g ) 嘧啶( c + t ) 沿d n a 序列的分布情况。当序列中嘌呤数 量大于嘧啶数量时，吒 o ，否则吒 0 ，否则以 0 ，否则乙 o ，若两者数量相等则乙= o 。 同样的，z 曲线的缺陷也是存在退化现象，即图形中存在环( c i r c u i t ) ，如对 于两条不同的序列a t g a g t c c 和a t g a g t c c a t g a g t c c 的区别无法从图形中 表现出来。 2 2 5 其他曲线 为了避免出现图形退化现象，g u o 对g a t e s 等人的三种类似的二维曲线进行了 1 0 硕十学位论文 改进【5 2 1 ，引入适当的参数d 使得4 个碱基对应的方向稍微偏离x 、y 坐标轴，消除 了退化。r a n d i c 将四种核苷酸用二进制数表示：a = 0 0 ，g = o l ，c = l o ，t = 1l ， 这样可以得到一个d n a2 dm a p 【5 3 1 ，用d n a2 dm a p 表示人类p 球蛋白第一个外 显子序列如图2 3 所示。l i a o 等提出了一系列二维【5 4 ，55 1 、三维【5 6 6 0 1 、四维图形表 示【6 1 ，6 2 1 ，张惜珍 6 3 】基于l i a o 的引入参数的3 d 图形表示法和z 曲线提出了一种新的 n 曲线，都很好的解决了退化现象。 h u u n o 0oo24l1 0 图2 3 人类d 一球蛋白第一个外显子序列的d n a2 一dm a p 表示【5 列 2 3 基于序列图形表示的基因识别方法 基于图形表示的可视性优势，一些研究者利用曲线的方法，通过几何直观的 工具来进行基因识别的相关研究。如，e h a m o r i 利用h 曲线发现几种病毒中存 在碱基的含量变化剧烈的区域f 4 6 1 ，又从抗菌素m 1 3 中观察到所有序列起始位点附 近都有富含嘌呤的短引导序列，这些都是从图形中直观得出的可用于基因识别的 敏感特征。目前已有很多人将直观的图形特征与图形内在的统计特征结合用于基 因识别，取得了较好的效果。 基于序列图形表达的基因识别方法的一般步骤如下图2 4 所示。原始的基因序 列可看成由碱基组成的字符串。我们首先找出合适的图形对序列进行描述。观察 序列图形，或者对图形进行一些数学变换，找出可以作为识别信号的数字特征， 每条序列的n 维特征组成了一个特征矩阵。以编码区非编码区识别举例，我们要 将序列分为两类。设编码区序列为正样本，非编码区序列为负样本，取其中一部 分做为训练集，余下的为测试集。与机器学习方法相同，我们先将已知分类的正 负样本序列的特征矩阵( 训练集) 输入给分类器学习，训练分类模型。接着使用 测试集进行测试，统计识别结果的准确率和误差，以衡量该基因识别方法的好坏。 幻 2 o 童 。 蠢 4 钧 图形表