（计算机科学与技术专业论文）基于图形表示的蛋白质编码区识别方法研究.pdf

r e c o g n i t i o no fp r o t e i nc o d i n gs e q u e n c e sb a s e do ng r a p h i c a l r e p r e s e n t a t i o n b y 肠nj u n b e ( c e n t r a ls o u t hu n i v e r s i t yo ff o r e s t r ya n dt e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e ra p p l i c a t i o nt e c h n i q u e s i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl u 0j i a w e i m a y , 2 0 1 1 湖南大学 学位论文原创性声明 l m i i iii i ii i1 1 1 1l i i ii l l l l l l w v 19 0 6 12 7 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 雾久孳 日期：扣i 年岁月弓口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“ ) 作者签名： 荔乏 日期： 扣f f 年岁月多。日 新徽：况研醐：砂符朋杪日 l 、 幕：j 二图形表乃；的生i 二| 质编码【) ( 识别方法研究 摘要 随着人类基因组计划的实施和基因组测序技术的快速发展，生物学家已得到 几百种生物的全基因组序列，这些序列的背后隐藏着丰富的生物学知识和生物学 规律。基因组序列测定之后，识别序列中的蛋白质编码基因是进行基因组分析首 先要解决的问题，本论文致力于蛋白质编码区( 特别是短编码区) 的识别，论文从 图形特征和分类算法两个方面对蛋白质编码区的识别进行研究。 针对短编码序列的识别问题，论文根据碱基在密码子三个位置的偏性和碱基 自身物理化学性质的分类，提出新的序列图形表示方法，然后在新图形上，提取 了9 1 , - 有效的面积矩阵特征，并使用支持向量机对人类的短蛋白质编码区进行识别 实验。在识别过程中，为了提高识别率通过递增特征选择算法添加了4 个统计特征 到面积特征中，使识别特征表达的信息更加完备，并采用p c a 方法对这1 3 个特征 进行降维。实验结果表明，与其他方法相比，该方法使用较少的特征( 7 个或4 个) 取得了更好的识别结果。 针对传统支持向量机计算量大，对孤立点和噪声数据太敏感的特点，论文使 用最小二乘模糊支持向量机代替传统支持向量机进行编码区识别。论文为最小二 乘模糊支持向量机设计了一种新的充分考虑了样本与样本之间关系的样本隶属度 计算方法，实验结果表明，与传统支持向量机和最小二乘支持向量机相比较，该 方法的识别精度更优。 关键词：图形表示；编码区非编码区；蛋白质短编码区识别；基因识别；d n a ； 最小二乘模糊支持向量机；隶属度函数；支持向量机 硕i j 学位论文 a b s t r a c t g e n o m es e q u e n c e sr i c hi nb i o l o g i c a lk n o w l e d g ea n db i o l o g i c a lp r i n c i p l e s w i t h t 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 ) a n dt h ef a s ti n c r e a s i n gp a c eo ft h e g e n o m e - s e q u e n c i n gp r o je c t s ，b i o l o g i s t sh a v eg o tg e n o m es e q u e n c e so fh u n d r e d so f s p e c i e s r e c o g n i t i o no fp r o t e i nc o d i n gg e n e si st h ef i r s tp r o b l e mi ng e n o m ea n a l y s i s a f t e rt h eg e n o m e - s e q u e n c i n g t h i sp a p e rd e s c r i b e ss o m en e wa p p r o a c h e sf o r r e c o g n i t i o no fp r o t e i nc o d i n gs e q u e n c e s ，e s p e c i a l l ys h o r tc o d i n gs e q u e n c e s ，a n d a n a l y z e si tf r o mg r a p h i cf e a t u r e sa n dc l a s s i f i c a t i o na l g o r i t h m a c c o r d i n g t ob a s eb i a si nt h et h r e ep o s i t i o n so fc o d o na n db a s ec h e m i c a l p r o p e r t i e s ，n e wg r a p h i c a lr e p r e s e n t a t i o n so fg e n es e q u e n c e s ，a r ei n t r o d u c e df o r r e c o g n i z i n gs h o r tc o d i n gs e q u e n c e so fh u m a ng e n e s n i n ee f f e c t i v ef e a t u r e so fa r e a m a t r i xa r ee x t r a c t e di nt h en e wc u r v e sa n ds u p p o r tv e c t o rm a c h i n e s ( s v m ) i su s e dt o i d e n t i f y t h es h o r tp r o t e i nc o d i n gs e q u e n c e si nh u m a ng e n e s i nt h ep r o c e s so f i d e n t i f y i n g ，t h ei n c r e m e n t a lf e a t u r es e l e c t i o na l g o r i t h mi su s e dt oa d df o u rs t a t i s t i c a l f e a t u r e st o e x p r e s sm o r ei n f o r m a t i o na n di m p r o v et h ea c c u r a c y t h e np r i n c i p a l c o m p o n e n ta n a l y s i s ( p c a ) i s w o r k e df o r r e d u c i n gd i m e n s i o n s f i n a l l y , t h e 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 du s e sf e w e rf e a t u r e s ( s e v e no rf o u r ) a n dg e t s b e t t e rr e c o g n i t i o nr e s u l t st h a no t h e rm e t h o d s t r a d i t i o n a ls u p p o r tv e c t o rm a c h i n e ( s v m ) i ss e n s i t i v et oi s o l a t e dp o i n ta n d n o i s ed a t a ，a n dh a sh u g ec a l c u l a t i o n t oi m p r o v et h i sw e a k n e s s ，l e a s ts q u a r e sf u z z y s u p p o r tv e c t o rm a c h i n e s ( l s f s v m ) i sa p p l i e df o rc l a s s i f y i n gt h ec o d i n g u n c o d i n g s e q u e n c ei n s t e a do fs v m an e wc a l c u l a t i o nm e t h o do ft h es a m p l em e m b e r s h i pf o r l s f s v mi sp r o p o s e d ，i nw h i c ht h er e l a t i o no fs a m p l e sh a sb e e nt a k e ni n t oa c c o u n t c o m p a r e dw i t hs v ma n dl e a s ts q u a r e ss u p p o r tv e c t o rm a c h i n e s ( l s s v m ) ，t h i s m e t h o do b t a i n sb e t t e rr e c o g n i t i o na c c u r a c y k e yw o r d s ：g r a p h i c a lr e p r e s e n t a t i o n ；c o d i n g n o n c o d i n gr e g i o n ；i d e n t i f i c a t i o no f s h o r tp r o t e i nc o d i n gr e g i o n ；g e n ei d e n t i f i c a t i o n ；d n a ；l e a s ts q u a r e s f u z z ys u p p o r tv e c t o rm a c h i n e ；m e m b e r s h i pf u n c t i o n ；s u p p o r tv e c t o r m a c h i n e i 接寸二图形表，j ：的生 j 质编码【x 识别方法研究 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引v i 附表索引v i i 第1 章绪论1 1 1 项目来源一1 1 2 研究背景和意义1 1 3 国内外研究现状2 1 4 本文的主要工作和结构安排4 1 5 硝、结6 第2 章基因图形表达及编码区识别方法7 2 1 与论文相关的生物学知识7 2 2d n a 序列的图形表示8 2 2 1 典型的d n a 序列的图形表示方法8 2 2 2 图形的特征矩阵1 1 2 2 3 矩阵不变量1 2 2 2 4 向量之间的距离1 3 2 3 蛋白质编码区的识别方法1 3 2 3 1 特征提取1 3 2 3 2 分类方法1 7 2 4 j 、结2 0 第3 章基于图形表示的人类基因短编码序列识别方法2 1 3 1 概j 丕2 1 3 2 数据库2 1 3 3 新的序列图形表示2 1 3 3 1 定义2 2 3 3 2y k w 及y k w v 2 2 3 3 3 新图形的性质2 5 3 4 特征提取与特征降维一2 5 3 4 1 特征矩阵及矩阵特征的提取2 5 i v 硕f j 学位论艾 3 4 2 特征选择2 8 3 4 3p c a 降维2 9 3 5 基于图形表示的编码区识别算法流程2 9 3 6 实验及讨论3 0 3 6 1 实验结果检验标准3 0 3 6 2 基于面积特征的基因识别3 1 3 6 3 基于s 及s ( i ) 的基因识别3 1 3 7 小结3 3 第4 章基于最d x - - 乘模糊支持向量机的编码区识别方法3 4 4 1 引言3 4 4 2 最小二乘模糊支持向量机3 5 4 3 隶属度函数一3 6 4 3 1 常见的隶属度函数3 6 4 3 2 新的隶属度函数。3 7 4 4 基于l sf s v m 的算法流程3 8 4 5 实验及讨论3 9 4 5 1 实验环境3 9 4 5 2 数据库3 9 4 5 3 基于l sf s v m 的基因识别3 9 4 6d 、l ；4 2 1 ； i论4 3 参考文献4 5 致j 射5 1 附录a ( 攻读学位期间所发表的学术论文和参加的项目) 5 2 v 基于图形表示的蛋臼质编妒5 区识别方法研究 插图索引 图2 1 真核生物基因结构及基因表达示意图7 图2 2 二维图形的三种坐标1 0 图2 33 n n 示意图1 8 图2 4s v m 模型示意图1 9 图2 5b p 模型示意图2 0 图3 1q 序列的y k w 图形2 4 图3 2q 序列的y k wv 图形2 4 图3 3 向量p 与z 轴的夹角2 5 图3 4y k w 下外显子的e a 特征的拟和图2 6 图3 5y k w 下内含子的e a 特征的拟合图2 6 图3 6y k w 下外显子的a g 特征的拟和图2 7 图3 7y k w 下内含子的a g 特征的拟和图一2 7 图3 8y k wv 下外显子的e a 特征拟和图2 7 图3 9y k wv 下内含子的e a 特征拟合图2 7 图3 1 0y k wv 下外显子a g 特征拟和图2 7 图3 1 1y k wv 下内含子a g 特征拟和2 7 图3 1 2 基于图形表达的编码区识别算法流程3 0 图4 1 样本工i 对应的阈值玎f ) 3 8 图4 2 基于l sf s v m 的编码区识别算法流程3 9 硕f j 学位论文 附表索引 表3 1x y ( x y = r y 、m k 或w s ) 序列的的a v g d 嘶a v g l n 拶值2 3 表3 2 面积特征与l i e w 方法的识别率的比较3 1 表3 3 本文方法和l i e w 方法的识别率比较3 2 表3 4 本文方法和g a o 方法的识别率比较3 2 表4 1 基于不同特征集的实验结果对比4 0 表4 21 6 2 b p 长度的实验数据上的实验结果对比4 1 表4 31 2 9 b p 长度的实验数据上的实验结果对比4 1 表4 41 0 8 b p 长度的实验数据上的实验结果对比4 1 表4 5 三个子数据集上使用s v m 的实验结果4 2 v i l 硕l ：学位沦文 1 1 项目来源 第1 章绪论 本学位论文的研究工作主要得到以下项目的资助： ( 1 ) 国家自然科学基金资助项目( 6 0 8 7 3 1 8 4 ) ：新型表达模式下的功能基因分析 算法研究。 ( 2 ) 湖南省自然科学基金资助项目( 0 7 j j 5 0 8 6 ) ：基于聚类的基因功能预测方法。 1 2 研究背景和意义 为了更深入地了解和认识自身，人类制定了宏伟的人类基因组计划( h u m a n g e n o m i cp r o j e c t ，h g p ) ，随着人类基因组计划和基因组测序技术的快速发展，产 生了大量的生物学数据，这些数据是信息和知识的源泉，其背后隐藏着丰富的生 物学知识和生物学规律【lj 。据权威机构统计，生物学数据以每1 5 个月翻一翻的速 度急速增长，与之相矛盾的是人类对生物学知识的认识非常缓慢，这个矛盾催生 了一门新兴的交叉学科生物信息学( 又称之为计算分子生物学) 。生物信息学 运用数学、生物学和计算机科学等学科的理论和方法研究生物信息的获取、处理、 存储、分发、分析和解释，发展数据分析方法。目前生物信息学的主要研究对象 是d n a 和蛋白质，其主要研究内容包括1 2 j ：序列比对；蛋白质结构预测；计算机 辅助基因识别；非编码区分析和d n a 语言研究；分子进化和比较基因组学；序 列重叠群装配；基于结构的药物设计；其他( 如基因表达谱分析，基因芯片设计等) 。 通过对生物信息学的研究和探索，可以更加全面、深刻地破译基因组信息和认识 生命科学中的本质问题i 。 基因识别、基因发现和基因预测是等同的概念。早期的时候基因识别是指预 测d n a 的蛋白质编码区，现在指正确识别基因的完整结构，基因识别已成为当 今最有挑战的课题之一。随着基因组研究和信息技术的发展，现代生物学研究方 法在生物研究中发生了深刻的变化，早期主要依靠实验的方法识别基因，然而由 于人力、无力和时间等条件的限制，基因识别仅仅依靠实验的方法远远不能达到 认识和分析生物学数据的目的，因此，越来越多的研究人员借用计算机工具对数 据进行分析与处理i lj ，计算机辅助基因识别因而成为生物信息学的核心课题之一。 基因识别的对象主要是蛋白质编码基因和具有一定功能的调控因子。由于d n a 测序技术的迅速发展，已经得到一些完整的基因组序列，有效地解决基因识别问 题显得越来越迫切。通常从两个方面在基因组序列中寻找基因，一种是识别与基 桀十图形表j ：的蟹亡j 质编码区识别方法研究 因相关的特殊信号，根据信号大致确定基因的位置，另一种是预测基因的编码区 域或预测外显子所在的区域【引。基因识别帮助人类更好地破译遗传密码、解析基 因的功能和了l 7 遗传机制，并且推动了生物学、生物信息学等相关学科的发展。 蛋白质编码区的识别是基因识别中最关键的步骤，也是最重要的内容。蛋白 质编码区是指编码蛋白质的d n a 序列片段，即基因的外显子部分，它决定着基 因产物的结构和功能，因此，测定基因组序列之后，首先要解决的问题就是预测 序列中的蛋白质编码基因 4 - 6 】。目前的蛋白质编码区识别算法，特别是真核基因 短编码区识别算法的识尉率有待提高。 1 3 国内外研究现状 基因识别工作开始于上世纪八十年代初期，经过二十多年的努力，已提出几 十种预测蛋白质编码基因的算法，其中十余种重要的算法已开发成软件，并提供 网上免费服务1 6 r 1 。 根据识别对象的不同，现有的基因识别方法可分为原核生物基因识别算法和 真核生物基因识别算法。按照识别方法的不同，基因识别方法可以分为两类：第 一类是间接识别方法，该类方法基于序列同源性，利用已知的e s t ( e x p r e s s e d s e q u e n c et a g ) 、m r n a 或蛋白质序列为线索，通过比较和分析在序列中搜索相似 序列或者同源序列，根据相似序列通常具有相似功能和结构的原理，获得序列的 信息，并给出标注的结果。其基本算法是序列比对算法，如s m i t h w a t e r m a n 的动 态规划算法、启发式搜索算法b l a s t 和f a s t a 。基于序列同源性的方法非常多， 比女i a l n 引，g e n e s e g e r 9 1 ，t a p 1 0 】和p r o c r u s t e s 1 1 1 等。基于序列同源性方法的搜索 工作比较容易，但方法的效率有待提高，其困难在于需要已知的序列信息，但测 定序列的成本高昂，而且序列的不精确或不完整会对结果造成误差，大部分物种 由于缺乏实验数据，不能使用基于序列同源性的基因识别算法。第二类方法是从 头计算方法( a bi n i t i o ) ，利用编码区与非编码区统计特性差异和功能位点附近的保 守信号，在d n a 序列上直接进行基因识别。该类方法主要基于两个发现：一是编 码区具有一些特别的保守信号，如真核基因的5 端外显子一定在核心启动子的下 游，而3 端外显子包含终止编码，根据这些保守信号，可以确定编码区的大致位 置，从而达到识别编码区的目的【，但是这些信号的强度太弱，仅通过检测保守 信号的方法不能准确地识别基因；另一个是基因在蛋白质编码区比非编码区更加 保守，因而存在明显的统计特性差异，如密码子在编码区和非编码区的使用频率 并不相同，某些密码子在编码区的使用频率较高，而在非编码区的使用频率偏低， 目前的很多编码区识别算法就是基于这种思想。上世纪八十年代以来，s h e p h e r d 1 7 j ， f i c k e t t l l 3 】s t a d e n 和m c l a c h l a n 1 4 】等人先后发现d n a 序列的非编码区和编码区表 现出明显不同的统计学特性【6 】，此后基于统计的方法就被广泛应用于基因编码区 2 顺l j 学位论文 的识别中【引，代表程序有g l i m m e r 15 1 ，g e n e m a r k l l 6 1 和z c u r v e l l7 1 。其主要的识别特 征包括密码子含量【1 3 , 1 8 l 、六核苷酸频率f 19 1 、g c 和a t 含量【2 0 1 、编码区的功率谱【2 1 1 、 傅立叶变换【2 2 】等。相对于基于同源性的基因识别方法，基于统计特征的基因识别 方法不需要数据的辅助，其识别速度更快，因而更多的研究人员选择基于统计特 征的基因识别方法进行基因识别。目l j 基因识别的发展方向是将基于同源性方法 和基于序列组成统计学特征的方法联合起来，从而提高基因识别的识别效果。 目前的基因识别算法使用多种分类模型【2 3 1 ，包括决策树( d e c i s i o nt r e e ) 、曲线 判别分析( q u a d r a t i cd i s c r i m i n a n ta n a l y s i s ) 、神经网络模型( n e u r a ln e t w o r k s ) 、隐马 尔科夫模型( h i d d e nm a r k om o d e l ) 等，其中隐马尔科夫模型是当前许多基因识别算 法的基础，以隐马尔科夫模型为基础的软件有多种，如g e n i e l 2 4 1 ，h m m g e n e 2 5 l 和 v e i l 2 6 j ，隐马尔科夫模型将d n a 序列看成是一个随机过程，编码区和非编码区使 用不同的马尔科夫模型，通过隐马尔科夫模型能够自动找出序列背后隐藏的规律， 隐马尔科夫模型有三个基本问题，分别是评估问题、解码问题和学习问题，这三 个问题由不同的算法来解决：向前算法解决评估问题，韦特比算法解决解码问题， 向前向后算法解决学习问题。 目前，基因识别领域已产生了大量基因识别方法，但仍有很多问题尚待解决。 原核生物基因中重复序列较少，没有内含子，其基因结构比较简单，且大部分d n a 序列参与编码蛋白质，所以对原核生物基因的识别相对容易，目前已经产生许多 识别率比较高的原核基因识别算法。相对于原核生物基因识别算法，真核基因识 别算法的识别效果较差1 6 j ，主要原因是真核基因的结构复杂，基因中含有大量的 重复序列，编码序列被非编码序列分隔开来，而且基因中编码序列要比非编码序 列少很多，如在人类基因组中，基因的编码序列所占比例仅为3 左右，其余序列 都是非编码序列拉7 。，并且非编码序列具有表达调控的作用，对人类的生命活动有 着重要的意义，但由于非编码区序列不参与编码蛋白质，人们对它的了解较少， 给真核基因的识别带来了困难。另外，短蛋白质编码序列的识别效果较差，主要 是因为d n a 序列长度越短，统计特征越不明显，导致序列的统计模型难以正确识 别，因此，提出有效的短蛋白质编码区识别算法是一个非常具有研究意义的课题， 本论文主要研究蛋白质编码区特别是短编码区的的识别问题。 近几年，d n a 序列图形表示方法发展非常迅猛，与传统的统计方法不同， d n a 序列图形表示方法将抽象的d n a 序列与图形紧密联系起来，然后利用几何 学知识发现和挖掘d n a 序列的信息。d n a 序列图形简单、直观，能够充分调动 人类在模式识别中的形象思维，越来越受研究人员的关注，目前已经涌现了许多 d n a 序列图形表示，被广泛的应用到基因相似性分析、构造进化树和基因识别等 问题中。基于碱基对称性在d n a 序列中的重要性，我国的张春霆院士提出了一 种d n a 序列的几何表示方法z 曲线，利用z 曲线理论对d n a 序列进行了分 3 慕：t 二图形表豕的蛋仁j 质编码区识别方法研究 析和研究，应用到真核和原核基因组的若干问题中，包括酿酒酵母基因组基因识 别【2 引、细菌与古细菌基因组a bi n i t i o 基因识别【17 1 、基因翻译起始位点的识别【2 9 1 、 冠状病毒基因组基因识另 t 3 0 l 、古细菌基因组复制起始位点的识别【3 1 】和人与其他高 等真核生物基因组的i s o c h o r e 结构的研究1 3 2 1 ，并开发了一系列的基因识别软件， 在互联网上提供免费服务，德国g o t t i n g e n 大学微生物研究所的学者曾著文指出z 曲线软件是国际上最优秀的细菌、古细菌基因识别软件之一。z 曲线识别方法使 用的较少参数并能取得不错的识别效果，g a o 等人使用z 曲线特征，f i s h e r 判别 法对人类基因编码区进行识别【”l 。针对z 曲线特征，l i e w 等人提出了一种仅包 含三个特征的s z 特征【3 4 1 ，并从最常用的2 2 个特征中选出7 个特征，对人类短编 码进行识别，取得了不错的识别结果1 3 5 】。除z 曲线之外，还有一些图形表示方法 被应用到基因识别问题中。p e n g 运用随机游动的方法，在2 d 空间上建立一种简 单的模型，具体过程是：将d n a 序列转换成嘌呤和嘧啶构成的序列，遇到嘌呤 沿y 轴的负方向跨一步，遇到嘧啶则沿y 轴正方向跨一步，并用z 坐标表示碱基 的个数。分析d n a 序列在该模型上的长程关联性质，p e n g 得到一种区别外显子 和内含子的方法，遗憾的是，一些学者指出这种方法不是一种区别外显子和内含 子的一般性方法【3 6 j 。根据外显子和内含子的c g r 图具有不同的特点，郑捷在c g r 图上提取特征对外显子和内含子进行识别1 3 7 】。在n a n d y 等人提出的d n a 序列2 d 图形表示上，n a n d y 发现外显子和内含子显示不同的模式，外显子的结构呈密集 的点丛，内含子区域呈细丝状结构。基于这个发现，n a n d y 定义了图形块的斜率 和簇密度刻画外显子和内含子的不同特点，并结合聚类技术对人类3 号染色体进 行了基因识别1 3 8 】。根据编码区和非编码区周期三行为表现的差异，杨莉从d n a 序列图形上给出一种共频系数，实现编码区与非编码区的识别，与傅立叶变换相 比较，杨的方法计算更加简单1 3 9 l 。j i a m g 等人将序列转化成双曲线，通过谱分析 对编码区进行识别1 4 。l u o 和“提出一种新的图形特征，根据d n a 序列的g c 含量对实验数据进行分组，使用s v m 进行人类短编码序列的识别【4 ，取得了较 好的效果。 1 4 本文的主要工作和结构安排 生物信息学的内容非常丰富，本文重点研究d n a 序列图形表达和基于d n a 序列图形的基因识别算法，并着力于蛋白质编码区( 特别是短编码区) 的识别，本 文的主要工作有： ( 1 ) 根据已有的d n a 序列图形表示，并考虑碱基在编码区非编码区的性质， 提出新的d n a 序列图形表达：y k w 图形和y k w v 图形，并证明新图形具有不 退化的性质。 ( 2 ) 在新图形上提取2 个特征矩阵：面积矩阵层口和夹角矩阵a g ，从这两个矩 4 硕l ：学位论文 阵上提取矩阵不变量作为识别特征。 ( 3 ) 结合特征矩阵不变量和统计不变量，构建组合特征，并用于人类短编码区 非编码区的识别，取得了不错的结果。 ( 4 ) 为最小二乘模糊支持向量机构建一种新的隶属度函数，以此提出一种基于 最小二乘模糊支持向量的编码区识别算法。 本文主要从两个方面研究蛋白质编码区的识别问题：一个是提出新的d n a 序列图形表达，然后在图形上提取矩阵特征；另一个是对分类器进行改进。全文 主要包含4 章，各章内容安排如下： 第1 章绪论。主要介绍论文的项目来源、研究背景和意义、国内外研究现状、 论文的主要工作和结构安排。 第2 章基因图形表达及编码区识别方法。首先简单介绍了论文中涉及的生物 学知识，然后详细介绍几种经典的基因序列图形表达，包括c g r 图、z 曲线、三 种相似的曲线等，之后总结了图形的特征矩阵，以及从矩阵上提取的不变量及求 向量距离的方法。最后从特征和判别方法两个方面详细阐述了蛋白质编码区的识 别方法，包括基于统计特征识别方法、基于图形特征的识别方法和基因识别问题 中用到的几种判别方法。 第3 章基于d n a 图形表达的人类基因短编码序列识别方法。针对人类短编 码序列的识别问题，根据碱基在密码子三个位置的偏性和碱基自身物理化学性质 的分类，提出种新的图形表示方法：y k w 图形和y k wv 图形，新图形不存在 环；在新图形上，构造2 种特征矩阵：面积矩阵e 口和夹角矩阵a g ；从特征矩阵 上提取不变量作为编码区识别的特征，通过比较矩阵特征的识别效果，选择面积 矩阵口的特征进行人类短编码区非编码区识别实验，并比较不同图形表达( y k w 图形和y k wv 图形) 下面积矩阵助特征的识别效果；为了进一步提高识别率， 提出递增特征选择算法，通过该算法添加统计特征到面积矩阵e a 的特征中，识 别过程中为了减少特征个数，以p c a 方法降维，使用支持向量机对人类基因短编 码序列进行了编码区非编码区识别，实验结果表明，该方法在取得了较优的识别 结果。 第4 章基于最小二乘模糊支持向量机的编码区识别方法。首先详细介绍传统 支持向量机分类器的优缺点，针对其应用的局限性，简单介绍了两种改进的支持 向量机( 最小二乘支持向量机和模糊支持向量机) ；然后为这两种支持向量机的结 合体最小二乘模糊支持向量机构造一种新的样本隶属度计算方法，并使用第 3 章中基因序列的特征，提出一种新的基于最小二乘模糊支持向量机的编码区识 别算法；在数据库上，使用该算法进行编码区非编码区识别，并与最小二乘支持 向量机、传统支持向量机的结果进行比较和分析。 最后，对全文的研究工作进行总结，并对下一步的研究工作进行了展望。 5 基于图形表，j 的蛋r i 质编码区识别方法研究 1 5 小结 本章是论文的绪论部分，主要介绍了项目来源、本文的主要工作、研究背景 和意义、国内外研究现状和论文的结构安排。 第1 节介绍了论文的项目来源。 第2 节简单介绍了研究背景和意义，包括生物信息学、基因识别和蛋白质编 码区的概念与意义。 第3 节阐述了基因识别的国内外研究现状。 第4 节介绍了论文的主要工作及结构安排。 6 硕f ：学位论文 第2 章基因图形表达及编码区识别方法 2 1 与论文相关的生物学知识 d n a 是遗传物质的基础，是由许多核苷酸组成的生物大分子。每个核苷酸由 戊糖、碱基和磷酸组成l lj ，戊糖和磷酸是永远不变的，所以不同的核苷酸通过所 包含的碱基来区分。组成d n a 的碱基有四种，即胞嘧啶、腺嘌呤、鸟嘌呤和胸 腺嘧啶，分别表示为c 、a 、g 、t ，碱基的不同顺序排列，构成了d n a 分子的 多样性。1 9 5 3 年w a s t o n 和g r i c k 提出了著名d n a 的双螺旋模型，即两条碱基互 补的单链以碱基配对方式形成氢键，反向平行围绕中心轴而形成d n a 双螺旋结 构【。组成d n a 的四种碱基有两种配对，胸腺嘧啶与腺嘌呤配对，形成两条氢键； 胞嘧啶与鸟嘌呤配对，形成三条氢键【6 】。 基因是编码一个r n a 分子或蛋白质的完整序列片段，是具有特定生物功能的 遗传基本单位。少部分生物( 如一些病毒的基因) 由r n a 组成，但大部分生物的基 因由d n a 组成。基因组是指一种生物所有遗传信息的总和，或载有遗传信息的 全体核酸。原核生物基因组与真核生物基因组有着明显的区别，原核生物的基因 结构比较简单，基因间隔很少，基因是不包含内含子一段连续的d n a 编码序列， 且基因组内没有高拷贝的、全基因组范围分布的重复序列 2 3 l 。与原核生物相比， 真核生物的基因结构要复杂得多，真核生物的基因一般为断裂基因，内部存在很 多插入序列，这些插入序列并不编码蛋白质，称之为内含子，编码蛋白质的序列 称为外显子1 2 3 1 ，图2 1 显示了真核生物的基因结构和基因表达过程1 4 1 , 4 2 】。 筏d 泣n 窿a 。 | ，审i r a r z r l p ta a na | 申 。叠g 站弘g a 谊a a l c g 矗n 越a g 犍基 0 气搿1：f m o 咀，l o nl 咐滞e x a n o _ o ：辩 图2 1 真核生物基因结构及基因表达示意图 7 基了二图形表示的苴f j 质编码区识别方法研究 基因表达是抬在基因的指导下，经过转录、剪接和翻译，合成蛋白质的过程。 d n a 序列经转录广：生与其互补的单链r n a ( p r e m r n a ) ，p r e m r n a 的内部含有 内含子，在剪接过j ：，内含子被剪掉，并将外显子连接得到m r n a ，然后利用 m r n a 翻译成特定功能的蛋白质i 酬，蛋白质氨基酸的组成和排列由m r n a 的密码 子组成和排列决定。密码子是一个三联体核苷酸，共有4 3 = 6 4 种，其中有6 1 种构 成氨基酸，剩余三种( t a a 、t a g 和t g a ) 是终止密码子，基因从起始密码子开始， 终止密码子结束1 6 j 。 2 2d n a 序列的图形表示 d n a 序列的4 个碱基通常用a 、c 、g 、t 表示，这种传统的表示形式在d n a 序列的发表、信息存储、统计分析和序列比对等方面，有着重要的作用，因此被 广泛使用。如果直接从序列本身寻找信息，需要通过大量的数学计算，而且该种 表示方式具有最高解像力，其解像力是不可调节的【4 引，即d n a 序列的每个碱基 的排列顺序非常清楚，序列的局部特征明显，但不能很明显地观察序列的总体特 征。为克服这种缺陷，人们提出另一种d n a 序列表示方法：图形表示方法，图 形表示比字符表示更加直观，能够调动人类在模式识别中的形象思维，并且其解 像力可调，d n a 序列转换成图后，可以利用几何学、图论中诸多方法对图形进行 分析。近几年，基因的图形表示已经成为研究基因的重要途径之一，已经提出了 许多二维和多维d n a 序列图形表示，被广泛应用于序列相似性分析、构造系统 进化树、基因突变、基因识别等领域。 d n a 序列的图形表示按维数来分，可分为二维、三维和多维图形表示，相对 于多维图形，二维和三维的图形可视化更加方便，所以在提出的图形表示方法中 二维和三维的图形表示方法居多。d n a 序列图形的每一维往往代表一定的含义， 如一联核苷酸、二取核苷酸、三联核苷酸本身；碱基所在的位置；核苷酸、双核 苷酸、密码子的累计数目或频率；一定的生物化学性质，如z 曲线，第一维表示 嘌呤嘧啶的分布，第二维表示氨基酮基的分布，第三维表示强氢键弱氢键的分 布。 2 2 1 典型的d n a 序列的图形表示方法 ( 1 ) c g r 图 j e f f r e y 于1 9 9 0 年提出的c g r ( c h a o sg a m er e p r e s e n t a t i o n ) 是一种d n a 序列的 图形表示和数学表达相结合的方法【4 引。这种方法基于混沌理论，将原始序列转换 成一张揭示其固有分形结构的图，研究发现，不同物种的基因序列的c g r 图形具 有不同的分形模式。c g r 在几何上得到了应用，还在处理基因组分析问题上显示 了很好的结果【4 5 1 。由d n a 序列到对应的c g r 图，算法可以简单描述如下：构造一 8 硕l ：学位论义 个正方形，定义正方形的四个顶点分别表示a 、c 、g 、t 四种碱基：连接正方形 的中心和代表d n a 序列中第一个碱基的顶点，用该条线段的中点表示d n a 序列中 的第一个碱基；之后，取d n a 序列第f “的初始值为2 ) 个碱基，就将该碱基对应的 顶点与代表f 1 个碱基的点连接起来，线段的中点