（模式识别与智能系统专业论文）特征筛选在原核生物基因从头预测中的应用.pdfVIP

签 签 西南科技大学硕士研究生学位论文第1 页 摘要 基因识别是生物信息学领域的一个重要研究内容。虽然现在有9 0 以上 a b s tr a c t g e n e t i ci d e n t i f i c a t i o ni nb i o i n f o r m a t i c si sa ni m p o r t a n tr e s e a r c hs u b j e c t a l t h o u g hm o r et h a n9 0 o ft h eg e n e sc a nb ea c c u r a t e l ya n n o t a t e d ，b u tb e c a u s e o ft h ec o m p l e x i t yo fg e n ee x p r e s s i o nr e g u l a t i o na n dc o m p l e xd i s e a s er e s e a r c hi t m a k e st h eg e n ei d e n t i f i c a t i o ns t i l lb eac h a l l e n g i n gt a s k a i m i n ga t i m p r o v i n g t h ep r o k a r y o t i cg e n er e c o g n i t i o nr a t eb yf e a t u r es e l e c t i o n ，t h i sp a p e rr e s e a r c h e s t h et h e o r ya n de x p e r i m e n tm e t h o d sb o t ha tt h eg e n e r a t i o na n dt h eo p t i m i z a t i o n o ft h et r a i n i n gs e ta n dt h ec l a s s i f i c a t i o ns e l e c t i o n f i r s t l y ，t h i sp a p e r r e v i e w st h eh o m ea n da b r o a d p r o k a r y o t i cg e n e i d e n t i f i c a t i o na l g o r i t h m ，a n d a c c o r d i n gt o t h ec h a r a c t e r i s t i c so fp r o k a r y o t i c g e n o m e ，t h i sp a p e rp r e s e n t sas c h e m eo fi m p r o v i n gt h eg e n er e c o g n i t i o nr a t eb y m a k i n gu s eo ff e a t u r es e l e c t i o n s e c o n d l y , t h i sp a p e rs t u d i e st h ef e a t u r es e l e c t i o nm e t h o dt h a ti d e n t i f yt h e p r o k a r y o t i cg e n e s o p e nr e a d i n gf r a m e s ( o r f ) s a t i s f i e ds e a r c h i n gc o n d i t i o n s w e r ef o u n do u tf r o me c o l ik - 12w h o l e - g e n o m es e q u e n c e ，a n dt r a i n i n gs a m p l e s e t sw e r eg e n e r a t e db yc o m p a r i n go r fs e t sw i t hr e l i a b l eg e n el o c u sd o c u m e n t ， t h e ng cc o n t e n ta n dzc u r v e sw e r ee x t r a c t e d t h r o u g ht h ec o m b i n a t i o no ft h e s e f o u rf e a t u r e sa n dt h ei n f o r m a t i o nc o n t e n to ftt e s t ，d i f f e r e n tc l a s s i f i e r sw e r e d e s i g n e d f o rd i f f e r e n t i n f o r m a t i o n ，i n c l u d i n g f i s h e rc r i t e r i o n ，l i n e a ra n d n o n l i n e a rl 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 ec l a s s i f i e r e x p e r i m e n tr e s u l t s s h o wap o s i t i v ec o r r e l a t i o nb e t w e e ni n f o r m a t i o na n dr e c o g n i t i o nr a t e ，a n dt h e r e c o g n i t i o nr a t eo fn o n l i n e a rl 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 ei sh i g h e rt h a n t h ef i s h e rl i n e a rd i s c r i m i n a t ea n dl i n e a rs u p p o r tv e c t o rm a c h i n e f i n a l l y ，t h eg e n er e c o g n i t i o na l g o r i t h mb a s e do nn o n l i n e a rl e a s ts q u a r e s s u p p o r tv e c t o rm a c h i n ei si m p l e m e n t e d t h e2 2p r e f e r r e dc h a r a c t e r i s t i cv a l u e s a r ec o n f i r m e dt h r o u g hs c r e e n i n gt h e3 3zc u r v ei d e n t i f i e dv a r i a b l e sc o n s i d e r i n g t h ec o d o nw i t h i n a d ja c e n tb a s ep a i r ss h o r t r a n g ec o r r e l a t i o n t h e n b y e l i m i n a t i n go v e r l a p p i n go r f sa n ds t a r ts i t e sr e p r e d i c t i n gt r a i n i n gs a m p l es e ti s g e n e r a t e dc l o s e rt ot h et r u ep r o t e i nc o d i n gg e n e s t h en o n l i n e a rl e a s ts q u a r e s s u p p o r tv e c t o rm a c h i n ec l a s s i f i e rb a s e do nt h i st r a i n i n gs e tc a nr e a c ht h e r e c o g n i t i o nr a t em o r et h a n9 4 西南科技大学硕士研究生学位论文第1 i i 页 k e yw o r d s ：n o n l i n e a rl 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 ； f e a t u r es e l e c t i o n ；g e n ei d e n t i f i e r ；p r o k a r y o t e s 西南科技大学硕士研究生学位论文第页 目录 1 绪论1 1 1 引言i 1 2 生物信息学及其主要研究内容1 1 3 研究背景及意义3 1 4 国内外研究现状4 1 5 本文的主要研究内容和组织结构5 1 5 1 本文的主要研究内容5 1 5 2 本文的组织结构6 2 原核生物基因识别算法7 2 1原核生物基因组和原核生物基因识别7 2 2 基于模式识别方法的基因识别8 2 2 1 f i s h e r 判别法8 2 2 2 最小二乘支持向量机理论9 2 2 3非线性最小二乘支持向量机理论1 1 2 3本章小结1 2 3基于g c 含量和z 曲线的特征筛选和识别13 3 1引言1 3 3 2d n a 序列的z 曲线理论1 3 3 2 1z 变换公式1 3 3 2 2 z 曲线方法的应用。1 4 3 3寻找开放阅读框1 5 3 4 训练集产生1 7 3 5 特征提取和筛选1 8 3 5 1t 检验方法1 8 3 5 2 特征提取和筛选1 9 3 6 结果与讨论2 0 3 6 1 算法的评价指标2 0 3 6 2 三种分类器对比的结果与讨论2 0 3 7 本章小结2 2 4对z 曲线的3 3 个识别变量的特征筛选2 3 4 1z 曲线的3 3 个特征参数2 3 西南科技大学硕士研究生学位论文第v 页 4 2 特征筛选2 4 4 3 特征筛选的准确率2 5 4 4 本章小结2 8 5基于优化z 曲线特征的基因识别2 9 5 1 引言2 9 5 2 排除重叠o r f s 的方法2 9 5 3 起始位点预测的方法31 5 4 与g l i m m e r 3 0 2 对比3 3 5 5 本章小结3 4 结论3 5 致谢3 7 参考文献3 8 攻读学位期间发表的学术论文及研究成果4 l 西南科技大学硕士研究生学位论文第1 页 1绪论 1 1 引言 自19 5 3 年d n a 双螺旋结构模型的提出和19 7 2 年d n a 重组技术的诞生以 来，科学家们就围绕d n a 的结构和作用，不断地开展研究。随着生物信息学 的迅速发展和“人类基因组计划”的逐步实施，人与模式生物基因组的测序 工作进展极为迅速。被誉为生命“阿波罗计划”的人类基因组计划将是人类 科学史上的又一个里程碑。 数据并不能代表知识和信息。面对如此海量的数据，如何在大量生物大 分子数据中挖掘知识，如何揭示生物大分子蕴含的生物信息，如何认识生命 的本质是现阶段急需深入研究的课题。这就衍生出一门新的学科：生物信息 学他】o 1 2 生物信息学及其主要研究内容 美国人类基因组计划实施五年后的总结报告中，对生物信息学作了以下 的定义：生物信息学是一门交叉科学，它包含了生物信息的获取、处理、储 存、分发、分析和解释等在内的所有方面，它综合运用数学、计算机科学和 生物学的各种工具、来阐明和理解大量数据所包含的生物意义。在研究分子 生命科学的许多关键问题中，生物信息学显得尤为重要旧，。 基因组是生物信息中最基本的表达形式，以基因组、核酸、蛋白质等生 物大分子数据库及其相关资料作为主要研究对象，利用计算机对原始数据和 资料进行存储、管理、注释、加工，使之成为具有明确生物学意义的生物信 息。这是获取基因知识、探索生命起源、发现生物进化规律等生命科学中重 大问题。它的发展对基因工程的发展有重要的意义。目前，生物信息学的主 要的研究领域有以下几个方向h ”： ( 1 ) 生物学数据库 生物学数据库是一切生物信息学工作的基础，它是生物学数据的收集、 存储、管理与分发的重要渠道。现有的生物学数据库大体可以分为以下四类： 基因组数据库；序列数据库；生物大分子结构数据库；以及在以上三类数据 库基础上构建的二次数据库。基因组数据库来自基因组作图；序列数据库来 自序列测定；结构数据库来自x 射线衍射和核磁共振技术，这些数据库是生 西南科技大学硕士研究生学位论文第2 页 物信息学的基本数据资源，通常称为基本数据库。根据生命科学不同研究领 域的实际需要，对基因组图谱、核酸和蛋白质序列、蛋白质结构以及文献等 数据进行分析、整理、归纳、注释，构建具有特殊生物学意义和专门用途的 二次数据库，是生物学数据库开发的必然方向。 ( 2 ) 计算机辅助基因识别 基因识别是指在给定基因组序列后，计算机能正确识别蛋白质编码基因 的范围和在基因组序列中的位置，这是最重要的课题之一。目前，基因识别 算法已有近百种，并且许多算法提供网上免费的服务，如：g e n e m a r k s ，、 g l i m m e r n l 等。 ( 3 ) 蛋白质结构预测 “后基因组”时代的终极目标是理解并预测生物大分子的序列、结构与功 能之间的关系。核酸的序列是极其复杂的，不弄清基因最终的表达产物一蛋 白质，就难以真正理解核酸序列中所存储的信息。于是，人们启动了蛋白质 组解析计划( h u m a np r o t e o m ep r o j e c t ，h p p ) ，以此提供人类完整的蛋白质序列 与结构的资料阳，。蛋白质结构预测包括与基因组信息相关的核酸、蛋白质空 间结构的预测和模拟；基因表达调控网络的研究以及蛋白质功能预测的研 究。 ( 4 ) 基因组序列信息的提取和分析 包括基因的发现与鉴定；基因组中非编码区的信息结构分析；模式生物 完整基因组的信息结构分析和比较研究；利用生物信息研究遗传密码起源、 基因组结构演化、基因组空间结构与d n a 折叠的关系以及基因组信息与生 物进化关系等重大问题。 ( 5 ) 生物大分子结构模拟和药物设计 包括r n a 的结构模拟和反义r n a 的分子设计；蛋白质空间结构模拟和 分子设计；生物活性分子的结构预测与设计；纳米生物材料的模拟与设计； 基于d n a 结构的药物设计等。 ( 6 ) 分子进化和比较基因组学 分子进化和比较基因组学是对结构和功能相似的蛋白质或编码蛋白质 的基因进行比较，进而来研究分子的进化。近年来由于较多的模式生物全基 因组序列的完成，为从全基因组的角度来研究分子进化提供了条件。分子进 化和比较基因组学的分析对揭示生命起源有着非常重要的意义。 ( 7 ) 其它课题 西南科技大学硕士研究生学位论文第3 页 如调控因子识别、基因表达谱研究、基因代谢网络分析和基因芯片设计 等，逐渐成为生物信息学中新兴的重要研究领域。 1 3 研究背景及意义 基因识别是生物信息学的一个基本问题。以蛋白质编码基因和r n a 基 因为主要识别对象，通过对全基因序列的分析，提取基因的有效特征，设计 识别算法建立理论模型实现计算机辅助基因识别的目的。传统的生物学确定 基因的方法是通过生物实验的方法，这种方法的缺点是周期长，费用高，而 且需要人力来完成。发展到现在可以用非实验的方法定位基因、确定基因的 结构，并且可以利用计算机自动地在d n a 序列中发现基因，这对生物基因 组的发展具有重要的意义旧1 。 在生物基因组不断的发展中，微生物基因组是尤为引人注目的。自从 1 9 9 5 年完成第一个细菌一流感嗜血杆菌( h a e m o p h i l u si n f l u e n z a er d ) 的全基因 组测序”，微生物基因组测序计划发展非常迅速，到目前为止，美国公共数 据网站n c b i 已经公布了数百个细菌的基因组序列，并且，许多未知的微生 物基因组的测序工作还在进行中。 如今，关于d n a 的测序工作已不再成为难题，并且已经积累了大量的 d n a 序列，而现在的首要任务就是从这些d n a 序列中识别编码蛋白质的基 因及调控基因表达的各种信号，其次是从已经积累的数据和知识出发预测蛋 白质的结构和功能“。基因识别的研究就是围绕着第一问题展开的。对于未 知的基因序列，如何找到正负样本建立训练集、如何提取有效的分类特征、 建立何种分类器对未知基因进行识别、如何提高系统的识别率和运行速度， 这已经成为一个重要的课题，也是本课题的研究意义所在。 因此有效的特征提取和选择是致关重要的，也就是说特征值的有效性直 接关系着分类器最后的分类效果和效率。一些信息含量小的特征对分类器而 言不仅影响其识别率，还影响其运行的速度。因此在进行特征提取之后，要 对特征进行筛选，在备选特征中剔除一些信息含量小的特征，保留信息含量 较大的特征，以达到优化分类器和提高识别率的效果。 西南科技大学硕士研究生学位论文第4 页 1 4国内外研究现状 应用模式识别方法通过分析d n a 序列从而获取蛋白质的某些信息的研 究方法是多种多样的。目前，常用的方法包括线性判别分析、遗传算法、人 工神经网络、隐式马尔可夫模型和支持向量机。其中应用最广泛的方法是隐 式马尔可夫模型，。利用隐式马尔可夫模型来识别基因的外显子和内含子， 可以获得准确的识别效果飞此外一种新的隐半马氏模型的提出，也使剪切 位点的识别率有所提高n 0 另外还可以把隐式马尔可夫模型与人工神经网络 结合起来，这样不仅克服了隐式马尔可夫模型本身难以解决的模式类别间的 相互重叠问题，而且弥补了神经网络在获取时序信息方面的不足“。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是v a p n i k 等人提出的一种新 的机器学习方法t 1 6 , 17 ，它基于结构风险最小化原则，能较好的解决小样本学 习的问题和过学习问题，并且能够适用于高维的特征空间，因此在模式识别 和生物序列分析中得到了广泛地应用。其中，应用支持向量机的方法来识别 真核生物，能更好地提取剪切位点附近保守序列的统计特征，获得了较好的 识别效果，。国外利用支持向量机进行基因识别的也有很多。如m i c h a e l p s b r o w n t ”】、i s a b e l l eg u y o n t 2 州等人，都分别产生了很好的分类性能和效果。 国外的研究还包括对线性支持向量机分类器的研究，主要是讨论了基于最小 二乘法的支持向量机分类器。通过解决一组线性方程组而不是经典的二次方 程组来达到逼近的效果妇”。 总的来说，基因识别方面的程序在国外已经比较成熟。对于原核基因组， 现有的著名的基因识别从头预测( a bi n i t i o ) 算法和程序有g e n e m a r k s 瞳“， g l i m m e r2 引和g e n e h a c k e rp l u s 心等。其中，目前使用最为广泛的程序是 g l i m m e r 。这些算法以高阶马尔科夫模型或隐马尔科夫模型为基础。许多基 因识别算法使用的是5 阶马尔科夫链对应于k = - 6 ，共有1 6 3 8 5 个独立参数， 这是针对齐次马尔科夫模型的，主要刻画d n a 序列中核苷酸六聚体的统计 特征。若模型为非齐次则参数的数目还会增加。一般说来，参数越多，需要 的训练集就越大。虽然其识别率已经相当高。但是也存在明显的缺点：使用 隐马尔科夫算法，需要对已知的基因结构信号进行学习或训练，对那些与学 习过的基因结构不大相似的基因，其预测效果不佳心“。 国内在基因识别方面的研究比较滞后。近几年发展较为迅速的、应用较 为广泛的是上个世纪9 0 年代中期由天津大学的张春霆院士提出的z 曲线方 法汜“。这种方法是从几何学的角度显示和分析d n a 序列的直观工具。它将 西南科技大学硕士研究生学位论文第5 页 d n a 序列与三维空间中的曲线一一对应起来，无论基因组多大，该基因组 的z 曲线都可以在计算机屏幕上或一张纸上显示出来，使人们可以直观、快 速地捕捉到基因组碱基组成的全局和局部特征。这种方法一经提出，特别是 近几年里收集并显示了真核、细菌、古细菌和病毒等1 0 0 0 多个基因组的三 维z 曲线，得到了人们的普遍关注【2 “。此外，z 曲线还具有参数少的优点， 所以z 曲线运行速度快且平稳，对计算机要求低，不仅适用于较大的基因组， 而且对于小基因组也同样适用。 1 5 本文的主要研究内容和组织结构 1 5 1本文的主要研究内容 本文简单介绍了生物信息学及其主要的研究内容，深入分析了原核生物 基因组和原核生物基因识别算法，并着重介绍了特征筛选在原核生物基因从 头预测中的应用。 本课题的研究目的是通过分析已知的基因序列，构建一种方法对未知的 基因序列进行具有较高识别率的基因识别。基因识别系统的设计包括寻找开 放阅读框、产生训练集、特征提取和构建分类器这四个模块。其中，为了提 高系统的识别效果，还需进行以下几个方面的工作： ( 1 ) 特征筛选。在进行特征提取之后要对所选特征进行筛选，这样做的 目的是排除一些信息量小的特征，达到提高程序识别率的效果。我们在基因 识别的每个环节中都利用特征筛选前后的两种特征分别构建分类器并进行 比较，以验证特征筛选在基因识别中的有效性和重要性。 ( 2 ) 排除重叠o r f s 。由于原核生物基因组的结构比较紧凑，所以o r f s 的重叠现象很常见，而基因的重叠并不常见，这样就会发生误判心“。因此要 对o r f s 进行排除重叠o r f s ，以提高系统的识别率。 ( 3 ) 起始位点预测。在找到的最长o r f s 内部有许多和终止密码子同相 位的起始密码子，而这些起始密码子都有可能作为翻译蛋白质的起始位点， 但真正的起始位点只有一个【2 “。所以要对起始位点进行预测，来提高系统的 识别效果。 ( 4 ) 基因识别算法的选择。通过比较分析f i s h e r 判别、最小二乘支持向 量机和非线性最小二乘支持向量机这三种分类器，实验结果表明非线性最小 二乘支持向量机具有很好的识别率及推广性。因此采用非线性最小二乘支持 向量机算法也可以使程序的识别率有所提高。 西南科技大学硕士研究生学位论文第6 页 通过上述方法得到的训练集的正样本越接近于真正的编码蛋白质基因， 利用这个训练样本集设计的分类器对未知基因进行识别，将具有较高的可信 冉 j 哆己o 1 5 2本文的组织结构 全文共分为五章，具体的章节安排如下： 第一章是绪论，首先介绍了生物信息学的概念以及其主要的研究内容， 其次介绍了本课题的研究背景及意义和国内外基因识别的研究现状，最后阐 明了本文的主要研究内容和目标。 第二章介绍了原核生物基因组和原核基因识别算法，并且对几种基于模 式识别方法的基因识别算法进行了简单的介绍。 第三章介绍了基于g c 含量和z 曲线的特征筛选和识别。首先寻找开放 阅读框，建立训练集，然后进行特征的提取和筛选，最后对于不同特征分别 设计三种分类器，并对其实验结果进行对比与讨论。 第四章介绍了关于密码子内部相邻碱基近程相关性的z 曲线理论及其 3 3 个识别变量，着重介绍了对z 曲线的变量进行特征筛选的结果。 第五章介绍了基于优化z 曲线特征的基因识别。在对z 曲线识别变量进 行特征筛选之后，进一步的使用了排除重叠o r f s 和起始位点预测的方法。 最后与g l i m m e r 识别结果进行比较得出结论。 最后总结了本课题所做工作，指出了目前存在的问题和今后需要改进的 地方。 西南科技大学硕士研究生学位论文第7 页 2原核生物基因识别算法 2 1原核生物基因组和原核生物基因识别 每个生物的基因组都携带着它的所有遗传信息，除少数病毒具有r n a 基因组外，绝大部分基因组由d n a 组成。d n a 的基本单位是核苷酸，它是 由两条碱基互补的单链反向平行围绕中心轴而形成的双螺旋结构。不同的核 苷酸是通过包含的碱基的不同来区分的，碱基包括腺嘌呤( a ) 、鸟嘌呤( g ) 、 胞嘧啶( c ) 和胸腺嘧啶( t ) ，碱基互补配对原则是指a 与t 和g 与c 进行配 对，构成双螺旋结构的两条链分别称为正链和反链。由于d n a 是主要的遗 传物质携带者，所以基于d n a 序列的预测以及识别的工作是非常重要的【3 “。 随着生物基因组测序工作的发展，基因识别程序已经从最初识别细菌基 因组编码蛋白质区域向预测具有多外显子脊椎动物基因的详细结构发起挑 战，。很多基因研究都是从原核生物开始，原核生物主要包括细菌和古细菌， 其基因组的结构与真核生物基因组有很大的区别。原核生物基因结构比较简 单，其蛋白质编码区是从起始密码子( a t g , g t g , c t g , g t g ) 开始到终止密码子 f t a a ，t a g ，t g a ) 结束，长度为三的整数倍的一段连续的d n a 片段，并且符 合开放阅读框( o p e nr e a d i n gf r a m e ，o r f ) 的结构”。原核生物基因组的特点 是其结构紧密，基因间隔很少，编码区在基因组中所占的比例很高，并且几 乎没有类似真核生物基因组中那样广泛分布的重复序列。 原核生物基因识别算法主要分为两大类：基于序列同源性和基于序列组 成统计学特征。基于序列同源性的基因识别程序是使用序列比对方法来搜索 数据库中的已知序列，其缺点是依赖数据库中的已知序列，基因识别率低， 对于一个新测序的细菌基因组，只有约6 0 7 0 的基因在目前数据库中有同 源序列，大量未知的新基因就可能被舍弃。而基于序列统计特征的基因识别 算法，又称为从头预澳t j ( a bi n i t i o ) 方法，主要利用蛋白质编码区组成特性和一 些功能位点的保守信号，其基因识别率常常可达到9 8 阳“，但仍存在一些问 题：对于重叠的基因，翻译起始位点难以预测；短基因的基因组特征不明显 时，统计模型很难识别；分类器的性能过度依赖训练集，因此也会影响识别 率；对于一些基因组，识别率和附加预测率很难同时取得优秀的成绩。虽然 从头预测的方法有一些难题有待解决，但是它确是一种更符合新基因识别的 方法。 西南科技大学硕士研究生学位论文第8 页 2 。2基于模式识别方法的基因识别 近年来，许多学者提出了许多基于统计模式识别的基因识别算法。基本 的方法包括线性判别分析、遗传算法、人工神经网络1 、隐式马尔可夫模 型和支持向量机。本文只选取了线性判别分析和支持向量机这两种方法进行 基因识别。 2 2 1fis h er 判别法 f i s h e r 线性判别的思想就是把d 维空间的样本投影到一条直线上，形成 一维空间，在一维空间里各类样本尽可能分得开些，即希望两类均值之差越 大越好；同时希望各类样本内部尽量密集，即类内离散度越小越好1 。 在基因识别的问题中，假设有个d 维基因特征样本x l ，x ：，h ：其中1 个属于w 1 类，代表编码蛋白质基因序列的特征样本；2 个属于w 2 类，代表 非编码序列组成的特征样本。则两个样本集的均值向量为： m ，：上争州：1 , 2 ( 2 - 1 ) ，篇 两个样本集的离散度矩阵之和为： s ，= 芝艺( x - 聊，) ( x 一砖) 7 ( 2 2 ) 从而得至l j f i s h e r 权向量： = 1 ( 砚一m ：) ( 2 3 ) w 就是d 维空间到一维空间的最好投影方向。基于训练集中的数据，找 到合适的阈值y 。就可以用于编码和非编码序列的判别，这里我们采用下面的 式子来确定此： y 。：旦堕塑( 2 4 ) 玮= - o k 么一q ， 。 2 这样，对于任意给定的未知基因序列特征样本x ，根据决策规则 f ( x 1 = w 7 x y o ( 2 5 ) 如果f ( x ) 0 ，那么这个样本就是一个编码蛋白质序列；否则，就认为 这个序列是一个非编码蛋白质序列。 西南科技大学硕士研究生学位论文第9 页 2 2 2最j x - - 乘支持向量机理论 支持向量机方法是从线性可分情况下的最优分类面提出的m ，。考虑二维 两类线性可分情况，如图2 1 ： 置 o o o o o编码基因 口非编码基因 ： 支持向量 1 7 搏i n i 啊 ”“5 图2 1支持向量机最优分类示意图 f i g 2 1 s c h e m a t i cd ia g r a mo fs u p p o r tv e c t o rm a c h in eo p t i m a ic l a s s i f ic a t i o n 图中，h ，致分别为各类样本中离分类线最近的点且平行于分类线的 直线，它们之间的距离叫做分类间隔( m a r g i n ) 。所谓最优分类线就是要求分 类线不但能将两类无错误的分开，并且要是两类的分类间隔最大。 对于基因识别的问题，设线性可分基因特征样本集为 ( x t ，只) ，f - 1 ，r , x r d , y + 1 ，- 1 ) 是类别标号，“+ 1 ”代表编码蛋白质基因，“1 ” 代表非编码蛋白质基因。基因识别的分类面方程为： w x + b = 0 ( 2 6 ) 如图，q ，鸠之间的距离为志，为了使间隔最大等价于使i | w l | ( 或i 酬2 ) i l w l l 。 最小。因此构建最小二乘s v m 分类器最佳分界面的问题可以表示为： d ( w ，b ，p ) = 剞叫f 2 + y e ? ( 2 7 ) 厶 厶t = l 线性分类约束条件为等式： w 。x i + 6 】- 1 一e l ，待1 玎 ( 2 - 8 ) 定义拉格朗日函数： 西南科技大学硕士研究生学位论文第1 0 页 三( w ，口) = 劲w f | 2 + y l t e 7 一窆口一，誓+ 6 卜1 托) ( 2 - 9 ) 其中，a l 0 为拉格朗日系数。分别对w 和求偏微分并令它们等于零，把原 (口)掣型-w-只薯：oow= 鬻却 ( c ) 掣业：膨一q ：o 。 ( d ) a l ( i w 一, a ) ：只 w ，五+ h i - 1 + p 。：0 令z = x l y l ；儿】，】厂= m ；以】，e = 1 ；1 ，p = 【p l ；e 。】，口= 【a l ；】，厶。 10 0 z t v w 个 0 00 一y b 0 0 o 芦” z y10 怕 j l 0 0 o e ( 2 1 1 ) 即： ( a ) w z 7 a = 0 (b)yr口=0(2-12、 ( c ) y e a = 0 ( d ) z w + y b + e = e 将( 2 1 2 a ) 和( 2 1 2 c ) 代入( 2 1 2 d ) 得： 砀+ z z l a + 7 , - j a = e ( 2 - 1 3 ) 式( 2 - 1 3 ) 可改写为求解线性方程组： r 0 _ y r z z r + 厂1 阱l e l j ，厂_ 让口j 2 j 蟛1 刨 由此，求解后得到z 和b 为最优解且是唯一解，则对于多数样本z 将为 零，取值不为零的a 疆口支持向量，它们通常只是全体样本中的很少一部分。 解上述问题后得到的最优分类函数是： 厂( x ) = s g n ( x z 只( 一，x ) + 6 ) ( 2 1 5 ) 西南科技大学硕士研究生学位论文第11 页 总之，将原核生物基因的特征样本训练集代入式( 2 1 4 ) 求出最优解z 和 b + ，设计出最优分类器，然后将待识别的基因特征样本集代入式( 2 15 ) 进行 判别，当判别式大于0 时判别为编码基因，否则为非编码基因。 2 2 3非线性最小二乘支持向量机理论 在很多情况下，原核生物基因的特征样本训练集是线性不可分的，这时 可以通过一个非线性函数 ) 将训练集数据x 映射到一个高维线性特征空 间，在这个高维线性空间中构造最优分类超平面，并得到分类器的决策函数 m ，。事实上，如果把原特征空间变换到了高维的特征空间，就相当于用内积 代替最优分类面中的点积，此时优化函数变为： q ( 口) = q i 1 口i a s y , y s k ( x , ，_ ) ( 2 1 6 ) t = l ，j = l 其中，k ( x ，m ) = 矽( x ，) ( y ，) 称为核函数。根据泛函的有关理论，只要一种核 函数满足m e r c e r 条件，它就对应着某一变换空间中的内积。对于任意的对 称函数k ( x ，一) ，它是某个特征空间中的内积运算的必要条件是对于任意的 ( x ) 0 且l 矽2 ( x x & 0 ( 2 1 7 ) 采用不用的内积函数将导致不同的支持向量机算法，目前得到研究的内 积函数形式主要有三类： ( 1 ) 采用多项式形式的内积函数 k ( 薯，y i ) = ( 誓 ) - t - 1 】9 ( 2 1 8 ) 此时得到的支持向量机是一个g 阶多项式分类器。 ( 2 ) 采用高斯函数型内积函数 r1 21 斛) - e x 十学 1 9 ) 得到的支持向量机是一种径向基函数分类器。这里每一个基函数的中心 对应于一个支持向量机，它们以及输出权值都是由算法自动确定的。 ( 3 ) 采用s 型内积函数 k ( 一，只) = t a n h ( v ( x , 只) + c ) ( 2 2 0 ) 则支持向量机实现的就是一个两层的多层感知器神经网络，这里网络的 西南科技大学硕士研究生学位论文第1 2 页 权值和网络的隐层节点数目都是由算法自动确定的。 求解上述问题后，若a ：为最优解，则得到最优分类函数是 ( 班= s g n ( 口? 只k ( x ，x ) + 6 + ) ( 2 2 1 ) t = l 所以，对于一个非线性问题，可以设法将它通过非线性变换转化为高维 空间中的线性问题，在这个变换空间中，只需要进行内积运算即可，这种内 积运算可以用原空间中的函数实现，甚至不需要知道它的变换形式，则即使 变换空间的维数增加很多，在其中求解最优分类面的问题并没有增加多少计 算复杂度。 2 3 本章小结 本章介绍了原核生物基因组的结构和特点，分析了两类原核生物基因识 别算的优缺点，着重介绍了应用模式识别方法如何进行基因识别，特别是 f i s h e r 线性判别法、线性最小二乘支持向量机和非线性最小二乘支持向量机 方法。 西南科技大学硕士研究生学位论文第13 页 3基于g c 含量和z 曲线的特征筛选和识别 3 1引言 d n a 序列是用四个字母符号表达的一维序列，这是一种简单抽象的表 达形式。但是，为了更直观的辨认d n a 序列，尤其是较长的序列，近年来 出现了许多d n a 序列的几何表示方法，其基本思想就是把d n a 序列转换 成三维空间的一条曲线来表示。到目前为止，z 曲线理论是这些几何表示方 法中使用最为广泛的一种，它已经发展成为研究d n a 序列的比较完整的和 系统化的理论。其中，z 变换公式是z 曲线的三个分量，是其主要的基因识 别特征n “。此外，g c 含量也是基因识别的一个有效特征。那么本章将基于 g c 含量和z 曲线这4 个特征进行特征筛选，并设计非线性最小二乘支持向 量机分类器，与f i s h e r 判别和线性支持向量机的识别率进行比较。 3 2 d n a 序列的z 曲线理论 3 2 1z 变换公式 z 曲线方法是具有丰富的折叠结构的三维空间曲线，对应着z 变换三个 分量，它反映了d n a 序列中碱基分布的局部细节和总体特征，因而，z 曲 线是显示和分析d n a 序列的直观工具h 。 d n a 序列是由四种碱基连续排列组成。如果按照双环还是单环结构来 划分，碱基可以分为两类：嘌呤和嘧啶。可表示为 碱基 喜羹：；三三萎妻 同样，按环中对应位置上是否存在氨基或酮基来划分，碱基又可以分为 另外两类： 碱刮纂i 墨碧妻 同样，在双螺旋结构中，按碱基对形成氢键的数目或强弱，碱基又可以 分为另外两类，即： 碱刮黧：；曩 上面这三种划分都包含了化学的成分，而z 变换也正是描述了这三种碱 西南科技大学硕士研究生学位论文第1 4 页 基的划分，下面简单介绍一下z 曲线理论。对于一个长度为的d n a 序列， z 曲线由一序列节点只，鼻，最，r 组成。这些节点的3 维坐标唯一地由d n a 序列的z 变换来确定。如公式( 3 1 ) 。 i 以= ( 4 + q ) 一( g + t o ) 匕= ( 以+ c j ) 一( g o + 乙) ，n = 1 , 2 ，n ( 3 一1 ) 【乙= ( 以+ 瓦) 一( q + g ) 其中，4 ，q ，e 和五分别表示从第1 个碱基到第甩个碱基的子序列中四种碱基 么，c ，g 和r 的各自出现次数。定义4 = g o = c o = t o = 0 ，从而x o = y o = z o = 0 。 把这些节点异，只，最，最依次用直线联起来就组成了z 曲线。注意z 曲线总是 从3 维坐标的原点起始。 z 曲线在3 个坐标轴上的投影形成了它的3 个独立的分量。z 曲线的三个分 量疋，e 和乙分别描述了d n a 序列的三种独立的碱基分布。 ( 1 ) 以分量表示嘌呤嘧啶碱基( 彳+ g c + 丁o rr 聊沿序列的分布。对于从 第1 个碱基到第，2 个碱基的d n a 子序列，当嘌呤碱基( 彳o rg ) 多于嘧啶碱基( c o r 乃时，疋 0 ，否则以 0 ，否则e 0 ，否则z n o ，当 两者相等时，z n = o 。这三个独立的分布完整地描述了所对应的d n a 序列。 这样一来，对于给定的d n a 序列就唯一地决定了这三种分布；同时，这 三种分布也唯一的决定了d n a 序列。那么对d n a 序列的研究就可以转化成 为对z 曲线的研究。 基于z 曲线理论，考虑密码子内部相邻碱基之间的近程相关性，可将z 曲线方法进一步发展得n 3 3 个特征，这部分将在第四章介绍。 3 2 2z 曲线方法的应用 近几年来z 曲线的应用比较广泛，主要包括基因识别、基因组的序列分 析和蛋白质编码基因的碱基频率分析等方面，此外，还可以通过研究z 曲线 的三个分量所代表的三种分布来研究d n a 序列的碱基的局部模式和总体特 征 4 2 - 4 4 ，。下面具体介绍一下z 曲线方法在基因识别领域的应用。 z 曲线方法在基因识别领域中是非常重要的。现在国际上著名的细菌和 西南科技大学硕士研究生学位论文第1 5 页 古细菌的基因识别程序都是基于高阶马尔科夫模型或者因马尔科夫模型的， 这些算法都具有较高的识别率，但是由于这些算法都要训练大量的统计参 数，对于小基因组就不能保证训练出准确的参数，就会影响预测结果的可靠 性。而z 曲线的最显著的优点就是参数少，并且可以直观的反映d n a 序列 的特征。在把zc u r v e 版本1 0 与g l i m m e r 3 0 2 做了全面比较之后发现： 在识别准确率方面两者旗鼓相当，均为9 8 以上；但在附加预测率方面z c u r v e 要比g l i m m e r 低得多，尤其对于高g c 含量的细菌和古细菌基因组， zc u r v e 比g l i m m e r 显示出了绝对的优势；在基因起始密码子识别准确率 方面zc u r v e 方法明显优于g l i m m e r ；在短基因的识别方面zc u r v e 略优 于g l i m m e r 。总之，z 曲线的优异表现引起了国际生物信息学与基因组学界 的广泛重视，并被誉为是当前国际上最优秀的微生物基因组基因识别软件之 一。 下面就以z 曲线的三个分量作为备选特征，与g c 含量一起进行特征筛 选，并设计分类器对原核生物基因进行识别。 3 3寻