（计算机应用技术专业论文）基于数据挖掘的生物序列分析研究.pdf

摘要 摘要 生物序列分析是生物信息学的主要研究领域，其任务是从浩瀚的生物序列数 据中发掘知识和揭示生命的奥秘。生物序列分析的主要研究内容包括序列比对、 蛋白质结构预测、基因组序列分析等。本论文着重研究了双序列比对算法和蛋白 质二级结构的预测方法。 首先，论文详细研究了序列比对方法，其中包括n e e d l e m a n 等人的动态规划 ( d p ) 比对算法、s m i t h - w a t e r m a n 算法、以及部分多序列比对算法，并比较了各自 的优缺点。然后提出一种基于频繁子序列s a f s s ( s e q u e n c ea l i g n m e n tb a s e d f r e q u e n ts u b s e q u e n c e s ) 的比对方法。虽然d p 算法通过复杂的数学计算可以获得 最优或近似最优的精确比对结果，但有可能忽略掉序列本身的生物意义。s a f s s 尝试从序列的生物学意义入手，比对中主要考察序列的高频子序列而不是分离的 单个字符，易于发现隐藏于序列之中的富含生物学意义的序列模式。与d p 算法 相比，s a f s s 显著降低了算法的空间复杂度，减少了计算量，具有较好的性能。 论文的另一个研究主题是蛋白质二级结构的预测方法。在已有的算法中，重 点研究了基于b p 神经网络的预测方法并进行了测试。研究中把对b p 神经网络的 一些常用改进算法，如附加动量法、自适应学习率调整策略以及遗传算法用于b p 神经网络中，这些算法的应用既避免了网络陷入局部极小，同时还提高了系统的收 敛速度和预测精度。其次，在蛋白质二级结构预测中采用了序列模式挖掘方法。 在数据预处理中，主要考虑了氨基酸之间疏水特性邻接关系进行特征提取，因而 提取的特征更能反映生物序列本身的特性，这样使得基于序列模式挖掘的预测方 法具有较好的性能。 本文的研究内容是生物序列分析中两个重要课题，研究中提出的s a f s s 比对 方法和基于序列模式挖掘的蛋白质二级结构预测方法具有一定的研究意义，为作 者进一步进行序列分析研究奠定了基础。 关键词：生物信息学，生物序列比对，数据挖掘，蛋白质二级结构预测 a b s t r a c t a b s t r a c t t h eb i o l o g i c a ls e q u e n c ea n a l y s i si st h em a i nr e s e a r c ha r e ai nb i o i n f o r m a t i c s ，a n d i t sp r i m a r ym i s s i o ni st om i n i n gk n o w l e d g ef r o mt h em a s s i v eb i o l o g i c a ls e q u e n c e s ，a n d t oe x p l o r et h em y s t e r yo ft h el i f e t h eb i o l o g i c a ls e q u e n c ea n a l y s i sr e s e a r c hc o n t e n t m a i n l yi n c l u d e st h es e q u e n c ea l i g n m e n t ，t h ep r o t e i n s t r u c t u r ep r e d i c t i o n ，a n dt h e g e n o m es e q u e n c ea n a l y s i se t c t h et h e s i s s t u d i e dt h ep a i r - w i s es e q u e n c ea l i g n m e n t a l g o r i t h m sa n dt h ep r o t e i ns e c o n d a r y s t r u c t u r ep r e d i c t i o nm e t h o d se m p h a t i c a l l y f i r s t l y , t h i st h e s i ss t u d i e ds e q u e n c ea l i g n m e n ta l g o r i t h m s i n d e t a i l ，s u c h a s n e e d l e m a n w u n c ha l g o r i t h mb a s e do nt h ed y n a m i cp r o g r a m m i n g ( d pa l g o r i t h m ) ， s m i t h - w a t e r m a n a l g o r i t h m e t c ， a n dc o m p a r e dw i t ht h e i r a d v a n t a g e o u s a n d d i s a d v a n t a g e o u s t h e n ，t h e t h e s i s p r o p o s e d an o v e lp a i r - w i s es e q u e n c eg l o b a l a l i g n m e n tm e t h o ds a f s s ，w h i c hi sb a s e d0 1 3 t h ef r e q u e n ts u b s e q u e n c e w i t hm a s s i v e c o m p l e xc o m p u t a t i o n s ，d pa l g o r i t h mc a n o b t a i no p t i m i z e da l i g n m e n tr e s u l t ，b u ti tm a y n e g l e c tt h eb i o l o g i c a ls i g n i f i c a n c ei ns e q u e n c e s s a f s sm a i n l yp r o c e s s e sf r e q u e n t s u b s e q u e n c ei nt h es e q u e n c e ，w h i c hi se a s yt od i s c o v e r yt h eb i o l o g ys i g n i f i c a n c ei nt h e r e d u n d a n tf r a g m e n t s c o m p a r e dw i t hd pa l g o r i t h m ，s a f s si sa na l g o r i t h mw i t hl o w e r s p a c ec o m p l e x i t ya n d h a sh i 曲p e r f o r m a n c e a n o t h e rr e s e a r c hs u b j e c ti st h ep r e d i c t i o no fp r o t e i ns e c o n d a r ys t r u c t u r e s o m e p r e d i c t i o nm e t h o d sw e r ed i s c u s s e d ，w h i c hi n c l u d en e u r a ln e t w o r k ，s e q u e n c ep a t t e r n m i n i n ge t c s o m ei m p r o v e m e n t sh a v eb e e na p p l i e dt ob a s i cb pn e u r a ln e t w o r k ，w h i c h c a r li m p r o v ei t sc o n v e r g e n c er a t ea n da c c u r a c y d u r i n gt h ef e a t u r ee x t a c t i o no f s e q u e n c ep a t t e r nm i n i n g , w em a i n l yt a k ea c c o u n ti n t ot h eh y d r o p h o b i c i t yp r o p e r t ya n d t h ea d j a c e n c yr e l a t i o n s h i po f a c i d s ，a n di ta c h i e v e dg o o dr e s u l t s t h i st h e s i sd i s c u s s e dt w oi m p o r t a n tt o p i c si nt h eb i o l o g i c a ls e q u e n c ea n a l y s i s s a f s sa n dd a t am i n i n gm e t h o d _ f o rp r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o na r eo f i m p o r t a n c e ，w h i c hl a yt h ef o u n d a t i o nf o rt h ef u r t h e rr e s e a r c hf o ra u t h o r k e y w o r d s ：b i o i n f o r m a t i c s ，b i o l o g i c a ls e q u e n c ea l i g n m e n t ，d a t am i n i n g ，p r o t e i n s e c o n d a r ys t r u c t u r ep r e d i c t i o n l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：叠垂连日期：2 。，年岁y j , 二日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：叠垒生导师签名： 女鑫 日期：乒0 0 6i f - 夕月，己e t 第一章绪论 1 1 引言 第一章绪论 2 1 世纪是生命科学和信息科学迅速发展的时代。以人类基因组计划为序幕的 生物信息学研究，是全面认识生命及其发展过程的重要途径，它将从根本上改变生 命科学和生物产业的思维方式和研究体系，成为新世纪国际竞争的关键环节和国 家实力的重要体现。 1 9 9 0 年，美国启动了被誉为生命阿波罗计划”的h g p ( h u m a ng e n o m ep r o j e c t ， 人类基因组计划) ，该计划通过世界上多个国家科学家的共同努力于2 0 0 0 年6 月 2 6 日完成。h g p 工作产生了大量的生物学数据，仅美国g e n b a n k 【1 】数据库中存储 的d n a 序列总量己超过1 0 0 亿碱基对；有两万多种蛋白质的空间结构以不同的分 辨率被测定；基于c d n a 序列所建立起来的e s t 数据库，其记录已达数百万条。同 时，还有越来越多的模式生物和其它生物数据被测定。在这些数据基础上派生、 整理出来的数据库已达5 0 0 余个，这一切构成了一个生物学数据的海洋。这种科 学数据的剧增和海量积累，在人类的科学研究历史上是空前的，这些数据中蕴含 着有关生命本质的大量信息。与正在以指数级数增长的生物学数据相比，人类对 生命认知的相关知识增长却十分缓慢，这构成了一个极大的矛盾。这个矛盾催生 了一门新兴的交叉科学一生物信息学( b i o i n f o r m a t i c s ) ，它为解决这个矛盾提供 了一个强有力的手段。目前，生物信息学己成为生命科学和自然科学研究的重大 前沿领域之一。 1 2 生物信息学的研究内容 生物信息学是2 0 世纪8 0 年代末随着人类基因组计划的启动而兴起的一门新 的交叉学科，也常被称为基因组信息学( 6 e n o m ei n f o r m a t i c s ) 。广义上讲生物信 息2 1 学是指利用先进的数据管理技术、数据分析模型、计算软件对各种生物信息 数据( 特别是分子生物学数据) 进行提取、加工、存储、分类、检索和分析等，以 电子科技大学硕士学位论文 这爨耀臻翻毽簿大麓数据黪蕴含兹曼| 三兹学纛义豹嚣的。藏麓医分攒受瘦嚣言，堡 物信息学主要是指核酸与蛋白质序列数据、蛋白质三维结构数据的计算机处理和 分竣。 生物信息学的研究重点主要是从核酸和蛋白质序列出发，分析序列中滚达的 结构莘强功能戆生物臻患。生物痿患攀戆基零任务是瓣各秘生物大分予疗列遴嚣分 析，也就是研究新的计算机方法，从大量的序列信息中获取基因结构、功能和进 化等知识。在从事分子生掳学矮究瓣几乎艨有实验整中，瓣掰获褥敬生物黪剪逶 行生物信息学分析醌经成为进一步实验之前的一个标准操作。 1 2 。1 生物学背景知谖 现代科学研究表明，生命起源予3 5 亿年前。最初的生命形式非常筒犟，僵在 几十亿年的进化作用下，生命发生了演绎并产生了多样性，从而产生了今天非常 复杂和简单生命体菸闻存在的现象。复杂和简单的艇物体裔着相儆的生物化学遥 程。生物化学中，擐主要研究的对象是蛋囱质( p r o t e i n ) 和核酸( n u c l e i ca c i d ) 分予。简蕈的说，虽舀质决定个室物是什么和傲忭么，两核酸戴受费编码产生蛋 白质所需要的信息，井把这热信息遗传给后代。其中，生物体包含两种核酸：核糖 棱酸r n a ( r i b o n u c l e i ca c i d ) 衽麓戴核糖蔹羧国e o x y r 珀o k “e l e i ea c i d ) 。下蟊简 要介绍蛋白质和核酸的一些基本知识【3 】。 1 ) 蛋毒蔟 生命体的大部分物质都是由各种各样的蛋白质组成，而缓白质则是由2 0 种氨 基酸分子依次链接影藏。奎氨基廖捌组或蠡毒线洼黪捌称之为蛋鸯矮载一缀结橡 ( p r i m a r ys t r u c t u r e ) ，一级序列通过一些折叠和复杂的化学作用形成二级结构 ( s e c o n d a r ys t r u c t u r e ) 、三级结梅( t e r t i a r ys t r u c t u r e ) 彝疆缓绩秘( q u a t e r n a r y s t r u c t u r e ) 等更多复杂的空间结构。蛋白质的空间结构决定其生物活性和功能。 蛋囊袋是在磅称为棱蕤转熬绥塞孛台残懿。在棱糖傣中，缀据售绩r n a 分子获 携带的信息，将氨綦酸分子一个个缀装起来，最终形成蛋白质。 2 ) d n a 分子兹缀藏 d n a 是脱氧核糖核酸的缩写，d n a 是由两条链构成的双螺旋结构。d n a 分子的 基本缀藏单控是棱萤，夏垓耱分子瞧个磷酸蓑分予、一个裁氧核耱帮一秽皴基 组成。这里的碱基有腺嘌呤( a d e n i n e ) 、鸟嘌呤( g u a n i n e ) 、胞嘧啶( c y t o s i n e ) 、 鹃艨缓啶( t h y m i n e ) 靼耪。d n a 结稳懿图卜t 援示： 2 第一章绪论 图1 - 1d n a 结构不意图 3 ) 碱基的配对原则 d n a 分子中，两条链上的碱基是严格互补配对相生的。碱基的配对原则是： a ( 腺嘌呤) t ( 胸腺嘧啶) ，c ( 鸟嘌呤) 一g ( 胞嘧啶) 。一个嘌呤基与一个嘧啶基通 过氢键联结成一个碱基对，称之为一个碱基对( b a s ep a i r ) 。在生物序列分析中通 常用碱基对表示d n a 的长度，缩写为b p ，例如可以说一段d n a 的长度是2 0 0 0 b p 。 碱基配对如图卜1 所示。 4 ) d n a 的双螺旋结构 两条链通过化学键的作用，相互残绕，形成双螺旋结构。d n a 的双链结构示 图卜2 所示。 5 ) 基因 基因：是指d n a 上具有特定功能的一个片断，负责一种特定性状的表达。一 般来讲，一个基因只编码一个蛋白质。 基因组：任何一条染色体上都带有许多基因，一条高等生物的染色体上可能 带有成千上万个基因，一个细胞中的全部基因序列及其间隔序列统称为g e n o m e s ( 基因组) 。d n a 分子上基因分布如图卜3 所示。 1 电子科技大学硕士学位论文 图1 - 2d n a 的双螺旋结构 幽卜3d n a 上的基凼 6 ) 基因的编码 基因编码是一个逻辑的映射，表明存储在d n a 和m r n a 中的基因信息决定什么 样的蛋白质序列。 每个碱基三元组对应编码一种氨基酸，这些三元组称为一个密码子( c o d o n ) 。 碱基组成的三元组的排列共有4 3 = 6 4 种，而氨基酸共有2 0 种类型，所以不 同的密码子可能表示同一种氨基酸。 7 ) d n a 的复制 在d n a 解旋酶的作用下两条链分离开，分别作为一个模板，在聚合酶的作用 下合成一条新链。 8 ) r n a 、转录与翻译 r n a ( 核酸) ：是种单链结构，它是d n a 序列中的基因序列的拷贝。拷贝产 生的r n a 序列其实是与d n a 中的条链相同的序列，只是其中用尿嘧啶u 代替d n a 中的胸腺嘧啶t 。它位于细胞核和细胞质中，它能够携带有与基因相同遗传信息。 而将这个把遗传信息从d n a 碱基序列转变为r n a 链的过程被称作转录。 翻译：是指信使r n a ( m r n a ) 上携带遗传信息在核糖体中合成蛋白质的过程。 9 ) 变异 4 第一章绪论 变异是指进化过程中由于不正确的复制，使d n a 内容发生局部的改变。变异 的种类主要有以下三种： 替代( s u b s t i t u t i o n ) ：在进化过程中生物序列中的某一核苷发生了错误改 变，替代能够改变蛋白质的序列，取决于其发生的位置，当替代发生在遗传信息 编码区时，可能会改变后代蛋白。 插入或删除( i n s e r t i o no rd e l e t i o n ) ：进化过程中在d n a 分子的某些位置 添加或丢失一个或者多个核苷的情况。 重排( r e a r r a n g e m e n t ) ：在生命活动过程中，d n a 或蛋白质序列的某些片断在 连接顺序上发生了混乱的现象。 1 2 2 生物信息学的研究内容 生物信息学的产生和发展是以生命科学研究数据的海量增长和信息科学技术 的迅猛发展为前提的。在生物信息学的研究中，核酸和蛋白质序列是生物信息学 研究的核心内容，人们试图通过研究蕴涵丰富遗传信息的序列数据来揭示生命的 内涵和奥秘。目前生物信息学包括基因组学( g e n o m i c s ) 、结构生物信息学 ( s t r u c t u r a lb i o i n f o r m a t i c s ) 和功能生物信息学( f u n c t i o n a lb i o i n f o r m a t i c s ) 三大方向： 第一是基因组学，其任务是对基因组信息进行提取、存储、处理、解释和发 布，以发现新的基因或已知基因新的功能，它是生物信息学的核心； 第二是结构生物信息学，其任务是研究基因产物即蛋白质和多肽的结构信息； 第三是功能生物信息学，其任务是分析与细胞功能相关的基因动态表达的信 息，以研究相关的蛋白质及其功能。 从目前生物信息学的研究现状来看，它主要包括以下几个主要研究领域【1 1 ： 1 ) 序列比对( s e q u e n c ea 1 i g n m e n t ) 序列比对问题的实质是比较两个或多个字符序列的相似性或不相似性。序列 比对是生物信息学的重要课题，它是很多其它研究课题的基础。动态规划算法是 序列比对中的经典算法，已经有基于动态规划算法的软件包在应用之中，如b a l s t 和f a s t a ，这些软件在数据库查询和搜索中有重要的应用。近年也产生了很多改 进的序列比对算法。目前，双序列的比对已经取得较好地成果，但多重序列比对 目前还缺乏快速而又十分有效的算法。 电子科技大学硕士学位论文 2 ) 结构比对 结构比对的基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或 不相似性，目前已有一些算法。 3 ) 蛋白质结构预测 蛋白质结构预测包括二级结构和三级结构的预测。从方法上来看，通常有演 绎法和归纳法两种途径。前者主要是从一些基本原理或假设出发来预测和研究蛋 白质的结构和折叠过程。分子力学和分子动力学属这一范畴。后者主要是从观察 和总结已知结构的蛋白质结构规律出发来预测未知蛋白质的结构。同源模建和指 认( t h r e a d i n g ) 方法属于这一范畴。虽然经过3 0 余年的努力，蛋白结构预测研 究现状远远不能满足实际需要。 4 ) 计算机辅助基因识别( 仅指蛋白质编码基因) 基本问题是给定基因组序列后，正确识别基因的范围和在基因组序列中的精 确位置。这是最重要的课题之一，而且越来越重要。经过2 0 余年的努力，提出了 数十种算法，有十种左右重要的算法和相应软件上网提供免费服务。原核生物计 算机辅助基因识别相对容易些，结果好一些。从具有较多内含予的真核生物基因 组序列中正确识别出起始密码子、剪切位点和终止密码子，是个相当团难的问题， 研究现状不能令人满意，仍有大量的工作要做。 5 ) 非编码区分析和d n a 语言研究 在人类基因组中，编码部分进展总序列的3 5 ，其它通常称为“垃圾”d n a 。 这些非编码区域也许并不是垃圾，只是我们暂时还不具备判断它们功能的能力。 分析非编码区d n a 序列需要大胆的想象和崭新的研究思路和方法。d n a 序列作为 一种遗传语言，不仅体现在编码序列之中，而且隐含在非编码序列之中。 6 ) 分子进化和比较基因组学 早期的工作主要是利用不同物种中同一种基因序列的异同来研究生物的进 化，构建进化树。既可以用d n a 序列也可以用其编码的氨基酸序列来做，甚至于 可通过相关蛋白质的结构比对来研究分子进化。以上研究已经积累了大量的工作。 近年来由于较多模式生物基因组测序任务的完成，为从整个基因组的角度来研究 分子进化提供了条件。可以设想，比较两个或多个完整基因组这一工作需要新的 思路和方法，当然也渴望得到更丰硕的成果。这方面可做的工作是很多。 6 第一章绪论 7 ) 序列重叠群( c o n t i g s ) 装配 一般来说，根据现行的测序技术，每次反应只能测出5 0 0 或更多一些碱基对 的序列，这就有一个把大量的较短的序列全体构成了重叠群( c o n t i g s ) 。逐步把 它们拼接起来形成序列更长的重叠群，直至得到完整序列的过程称为重叠群装配。 拼接e s t 数据以发现全长新基因也有类似的问题。已经证明，这是一个n p 一完备 性算法问题。 8 ) 遗传密码的起源 一种最简单的理论认为，密码子与氨基酸之间的关系是生物进化历史上一次 偶然的事件而造成的，并被固定在现代生物最后的共同祖先里，一直延续至今。 不同于这种“冻结”理论，有人曾分别提出过选择优化、化学和历史等三种学说 来解释遗传密码。随着各种生物基因组测序任务的完成，为研究遗传密码的起源 和检验上述理论的真伪提供了新的素材。 9 ) 基于结构的药物设计 人类基因组计划的目的之一在于阐明人的约1 0 万种蛋白质的结构、功能、 相互作用以及与各种人类疾病之间的关系，寻求各种治疗和预防方法，包括药物 治疗。基于生物大分子结构的药物设计是生物信息学中的极为重要的研究领域。 为了抑制某些酶或蛋白质的活性，在已知其3 级结构的基础上，可以利用分子对 接算法，在计算机上设计抑制剂分子，作为候选药物。这种发现新药物的方法有 强大的生命力，也有着巨大的经济效益。 1 0 ) 其他 如基因表达谱分析，代谢网络分析：基因芯片设计和蛋白质组学数据分析等， 逐渐成为生物信息学中新兴的重要研究领域。 总之，生物信息学是一种重要的研究开发工具。它是一门研究生物和生物相 关系统中信息内容物和信息流向的综合系统科学，只有通过生物信息学的计算处 理，我们才能从众多分散的生物学观测数据中获得对生命运行机制的详细和系统 的理解，最终破解生命的奥秘。 7 电子科技大学硕士学位论文 1 3 课题来源和研究意义 生物序列一般指的是d n a ，r n a 序列或蛋白质序列，这些序列是采用分子测量 技术对不同生物体在分子水平上进行测定的。在生物序列分析研究中，通常用一 些约定的符号来表示不同的生物分子，因此生物分子之间的位置和顺序等信息可 以用代表这些分子的字符序列来体现。在生物信息学中研究的生物序列数据，通 常都以生物分子字符的线性序列来表达，如d n a 序列由a ，g ，c ，t 四种字符组成。 生物序列分析的任务就是要通过对这些字符序列的研究，发现这些序列中隐藏的 生物学意义及知识。 关于生物序列的结构分析内容有诸多方面，如序列的空间结构分析、序列数 据库内部的语法和词汇结构分析、序列的比对分析等。从最早的原生物分子序列 开始，到当今大量物种和数以千万的不同生物体，生命历了数十亿年的演化。近 代生命科学发现这种演化过程可以归结为生物序列的变异过程。通过对大量数据 的分析，人们发现这种变异过程具有保守性与变异性。保守性使得物种保持相对 的稳定性，而变异性使得生物体具有千差万别的分化。这些变异和保守的成分都 蕴含和体现在生物序列之中。 序列分析研究，其目标就是研究新的计算机算法，从大量的序列数据中获取基 因结构、功能和进化等知识；例如，在发现一个基因或蛋白质序列后，为了推测 这个序列的性质、结构、功能、同源性、变异性、活性位点，作用的机制与疾病 的关系，首先必须应用序列数据库进行相似性搜索，得到与未知序列相似的目标 序列，从而为后续的研究确定初步的方向。现在分子生物学中许多重要的发现， 都有赖于利用计算机所进行的序列同源性比较与分析。在生物学的研究中，将未 知序列同已知序列进行比较分析已经成为一种强有力的研究手段。这种寻找生物 序列相似性的过程就称为序列比对。双序列比对是序列分析的基础。然而，对于 构成基因家族的成组序列来说，要建立多个序列之间的关系，这样才能揭示整个 基因家族的特征。由于可以提高序列比对的信噪比，多序列比对在阐明一组相关 序列的重要生物学模式方面起着相当重要的作用。多序列比对有时用来区分一组 序列之间的差异，但其主要用于描述一组序列之间的相似性关系，以便对一个基 因家族的特征有一个简明扼要的了解。与双序列比对一样，多序列比对的方法建 立在某个数学或生物学模型之上。因此，正如不能对双序列比对的结果得出“正 确或错误”的简单结论一样，多序列比对的结果也没有绝对正确和绝对错误之分， 8 第一章绪论 而只能说某一方法从多大程度上反映了序列之间的相似性关系以及它们的生物学 特征。 由于大量的生命奥秘蕴含于生物序列之中，所以生物序列分析是生物信息学 中一个关键而又基本的问题。本课题是在经过详细查阅资料和广泛调研的基础上， 在导师的指导下自拟的。课题的研究性质属于应用基础理论研究，它既具有理论价 值也具有十分重要的应用意义。本文主要讨论生物序列分析中双序列的全局比对 和蛋白质二级结构预测两方面的问题。 1 3 1 生物序列比对的研究意义 生物序列分析的核心问题之一是各种不同类型的生物体序列的比较，它的最 终目的是寻找与确定不同生物序列的稳定区域和变化规律，并发现它们的功能特 征与区别所在。生物序列的相似性比较即序列比对，就是运用某种特定的数学模 型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果能够 反映序列之间的相似性关系以及它们的生物学特征。 实现生物序列比较的操作通常被称作序列比对，它是生物信息学中一种基本 的信息处理方法，具有非常重要的意义：1 ) 它是其它很多复杂操作的基础；2 ) 它 是发现和鉴别新基因的重要手段；3 ) 它是蛋白质结构预测的基础：4 ) 它是研究 物种进化和属分类的基本方法。从序列的片段测定，拼接，基因的表达分析，到 r n a 和蛋白质的结构功能预测，物种亲缘树的构建都需要进行生物分子序列相似 性的比较。在遗传物质长期的演化过程中，原本相同的d n a 序列由于其中一条序 列缺失了几个片断，或增加了几个片断，或某段子序列发生了位置的变化等，从 而导致他们发生了不同，这两条序列不一定能进行精确的匹配，但是他们有一定 的相似度。序列比对可以发现不同生物序列的演变规律与特性，了解这这些演变 规律以及它们对生命过程的作用，对人类认识生命过程有着重要意义。目前，关 于序列比对效率的研究己成为生物信息学领域中的一个非常重要的研究课题。 1 3 2 蛋白质二级结构预测的研究意义 随着人类基因组计划的完成，生命科学已全面进入了后基因组时代。基因组 学的研究的重心已经由测序转向基因功能的研究。生物体中，基因编码形成氨基 酸序列，氨基酸序列迸一步折叠产生丰富的空间结构进而合成具有生物活性的蛋 9 电子科技大学硕士学位论文 白质。基因所携带的功能信息通过其编码的蛋白质的生物活性体现。蛋白质的功 能与其空间结构有着密切的关系，只有处在一定的空间结构中蛋白质分子才能够 发挥其特定的功能，也就是说蛋白质结构是其行使生物功能的基础。因而，了解 和掌握蛋白质的结构对于探求其功能有着重要的意义。 然而，生物蛋白质结构的测定速度远不如基因组测序速度。x 射线晶体学方法 和多维核磁共振技术是目前测定蛋白质结构的主要方法。用x 射线衍射方法测定 一个蛋白质分子的晶体结构不仅需要首先得到高质量的晶体，还要花相当长的时 间，在技术上也受到一定的限制。虽然核磁共振技术的出现提供了测定蛋白质三 维结构的强有力的手段，但这一方法目前还只限于较小的蛋白质的结构测定而且 效率不高。因此迫切需要一种迅速、简便易行的测定蛋白质结构的方法。根据蛋 白质的一级结构所提供的氨基酸序列信息用理论来进行高级结构预测的方法正是 应这种需要而发展起来的。 1 9 6 1 年c b h n f i n s e n 等在实验的基础上提出蛋白质氨基酸序列决定其空 间结构的原理，这成为预测蛋白质结构的理论基础【4 】，所要解决的关键问题是发 现蛋白质结构形成的规律。近3 0 年来，蛋白质结构预测工作取得相当大的进展， 出现很多好的理论预测方法，在定条件下预测得到的蛋白质结构完全可以和实 验测定的结构相符。随着各种软件及算法的改进，在今后不远的时间里，以计算 为基础来确定蛋白质的高级结构将最终实现，并将在蛋白质组学和药物设计等领 域中发挥具大作用嘲。 1 4 论文的研究内容 生物科学数据的爆炸性增长，给生物序列分析工作带来了更为严峻的挑战。 生物科学工作者对序列比对算法的敏感性和时空复杂度提出了更高的要求，开发 兼有高敏感性和高效率的算法成为序列比对研究中的瓶颈问题。由于比对的结果 说明了相应算法在多大程度上反映了序列之问的相似性关系以及它们的生物学特 征，因此，设计一个合理高效的序列比对算法是生物信息学领域中的一个非常重 要的研究课题。另一方面，在已知的蛋白质结构数据库的基础上，去预测一个未 知结构的序列的结构，对进一步了解未知序列的功能有着重要的意义。而蛋白质 二级结构预测算法的优劣直接影响着预测结果的准确性，因此高精度的结构预测 算法是人们在蛋白质结构预测研究中追求的目标。本课题研究目的之一是，在基 1 0 第一章绪论 于前人研究成果分析基础上，对生物信息学中现有序列比对算法进行改进与提出 新的算法；同时对蛋白质二级结构预测算法作深入地研究，并将数据挖掘技术应 用到其中。研究内容和拟采用的方法主要包括以下几方面： 1 ) 深入地研究各种经典的生物序列比对算法，对各种算法进行比较和测试， 分析各自的优缺点，全面地了解生物序列比对的研究现状以及相关技术和方法。 2 ) 提出一种基于频繁子序列的生物序列比对方法s a f s s ( s e q u e n c ea iig n m e n t b a s e df r e q u e n ts u b s e q u e n c e s ) 。频繁集是数据挖掘中的一个概念，本文将数据 挖掘中频繁集的思想用于序列比对。通过频繁集的发掘，找出相似序列之间的共 频繁子序列，然后以频繁子序列为主要考察对象进行序列比对。这种方法有利于 挖掘出具有生物学意义的一些频繁保守子序列，从而使得产生的序列比对结果更 符合生物进化的内在规律。 3 ) 深入研究蛋白质二级结构预测的常用方法。本文主要研究基于神经网络的 蛋白质二级结构预测方法。其中以标准b p 神经网络为基础，将附加动量法应用于 网络权值的调整中，避免网络陷入局部极小；在学习速率的选择上，将采用自适 应学习速率调整策略来提高系统的收敛速度。另外拟将遗传算法引入到神经网络 中，用于增强其搜索能力。 4 ) 拟将序列模式数据挖掘应用于蛋白质二级结构的预测中。 电子科技大学硕十学位论文 2 1 生物序列比对 第二章序列分析的研究基础 在生物学的研究中，一个常用的方法就是通过比较分析获取有用的信息和知 识。达尔文正是研究比较了不同物种的形态学特征，从而提出了自然选择学说。 因此，我们对基因和蛋白质序列进行比较，从本质上来讲是同达尔文一样，进行 同样的分析，只不过更加精细，更加详尽。在这个意义上，我们从核酸以及氨基 酸的层次去分析序列的相同点和不同点，以期能够推测它们的结构、功能以及进 化上的联系。最常用的比较方法是序列比对，它为两个或更多个序列之间的相互 关系提供了一个非常明确的图谱。 序列比较是生物信息学中最基本、最重要的操作，通过序列比对可以发现生 物序列中的功能、结构和进化的信息。序列比较的根本任务是：通过比较生物分 子序列，发现它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差 异。在分子生物学中，d n a 或蛋白质的相似性是多方面的，可能是核酸或氨基酸 序列的相似，可能是结构的相似，也可能是功能的相似。一个普遍的规律是：序 列决定结构，结构决定功能。研究序列相似性的目的之一是，通过相似的序列得 到相似的结构或相似的功能。另一个目的是通过序列的相似性，判别序列之间的 同源性，推测序列之间的进化关系。 生物信息学中，对序列的比较需要进行对位排列等操作，也叫做序列比对。 目前，在序列比对方面已有较多的算法，互联网上很多软件包已经融合了这些算 法。但是，随着序列数据的增加，人们对比对算法的效率提出了更高的要求。因 此，设计一个合理高效的序列比对算法已成为生物信息学领域中的一个非常重要 的研究课题。 1 2 第二章序列分析的研究基础 2 1 1 序列比对的基本概念 2 1 1 1 相关定义 序列比对，实际上是序列比较的具体实现方法，它运用某种特定的数学模型 或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了 序列之间的相似性关系以及它们的生物学特征。序列比对在生物信息学中的应用 和需求大致有下列几个方面： i ) 两个生物序列长度接近，并且二者非常相似，仅有一些微小差别，要求找 出差别； 2 ) 判断两条序列中是否条序列的前缀与另一条的后缀相似，若是，则提取 出前缀和后缀。这常应用于大规模基因测序中序列片段的组装( 拼接) 。 3 ) 判断一条序列是否是另一条序列的子序列，这常用于搜索特定的序列模 式。 4 ) 判断两条序列是否具有相似的子序列，这常用于分析保守序列。 5 ) 找出多条序列的共性，常用于研究一个家族中的相关蛋白，发现其结构、 功能和进化关系。 相似性和同源性是序列比对中经常使用的两个术语，二者的意义容易混淆， 需要澄清的它们的基本概念： 1 ) 相似性 相似性是指一种很直接的数量关系，比如部分相同或相似的百分比或其它一 些合适的度量。比如说，a 序列和b 序列的相似性是8 0 ，或者4 5 ，这是个量 化的关系。 2 ) 同源性 同源性是指从一些数据中推断出的两个基因或蛋白质序列具而共同祖先的 结论，属于质的判断。就是说a 和b 的关系上，要么二者是同源序列，要么二者 非同源两种关系。因此，说a 和b 的同源性为7 0 是不恰当的。 序列的相似性和序列的同源性有一定的关系。一般来说，如果两个序列问的 相似性越高，那么它们是同源序列的可能性就越大，所以经常可以通过序列的相 似性来推测序列是否同源。 2 1 1 2 比对操作 1 3 电子科技大学硕士学位论文 生物序列的比对，抽象出来以后就是字符串之间各个字符的一种一一对应关 系，它反映出序列之间在什么部位相似，在什么部位存在差别。为了找出两个序 列之间的相似区域以及相似度，通常需要在两个之间进行各种相关操作。为了获 得两个序列间更多的相似区域，可以在序列中增加空位以改变两个序列间字符的 对应关系。 在双序列比对中，通常通过对序列的“编辑”操作让两个序列对应的字符尽 可能的多。常用的编辑操作有m a t c h ( 匹配) s u b s t i t u t i o n ( 替换) i n s e r t ( 插 入) 和d e l e t e ( 删除) 。利用这些操作可以使两个序列达到相同的长度以及更多 对应位字符匹配。图2 1 是对序列a g c a c a c a 和a c a c a c t a 的两种比对结果以及对 应的字符编辑操作。 对不同类型的编辑操作定义函数w ，它表示“代价”或“权重”，也可以叫做 “罚分”。对表示d n a 或蛋白质序列字母表中的任意字符x 和y ，有如下罚分定义： 1 l r ( x ，x ) = o表示对应位置的字符相同，罚分记为0 ； w ( x ，y ) = l表示对应位置的字符不同，罚分记为1 w ( x ，一) ：w ( 一，y ) = l 表示在其中一个序列中插入了空格，罚分记为1 5 ：a g c a c a c - aa g - c a c a c a t ：a - c a c a c t aa c j c a c t - a m a t c h ( a ，a )m a t c h ( a ，a ) d d e e ( c ，- )r e p l a c e ( g ，c ) m a r c h ( c ，c )i m e d ( 一，a ) i v h t c h ( a ，a )m a t c h ( c ，c ) m a t c h ( c ，c )m a t c h ( a ，a ) m a t c h ( a ，a )m a t c h ( c ，c ) m a t c h ( c ，c )r e p l a c e ( a ，t ) i n s 州- ，t ) d e l e t e ( c ，- ) m a t c h ( a 。a )m a t e i 】( a ，a ) 图2 1 两种不同编辑操作的比对结果 在上述罚分定义中，简单的用数值表示序列比对中编辑操作的代价，罚分越 小的编辑操作结果对应的序列相似度越高，而罚分越大说明代价越高，相应的序 列问的相似度越低。而在实际应用中还需使用更复杂的代价模型。一方面，可以 改变各编辑操作的代价值，例如，在蛋白质序列比较时，用理化性质相近的氨基 酸进行替换的代价应该比完全不同的氨基酸替换代价小。 另一种衡量比对编辑操作的方法是用得分函数( s c o r e ) 。得分函数是对不同 1 4 第二章序列分析的研究基础 的对应关系奖励不同的分值，得分越高，序列就越相似。下面给出一种基本的得 分函数： p ( x ，x ) = 1表示对应位置的字符相同，得1 分 p ( x ，y ) = o表示对应位置的字符不同，得0 分 p ( x ，一) = p ( 一，y ) = 一1表示在其中一个序列中插入了空格，得一1 分 在序列比对中，可以选择罚分机制，也可以采用得分函数，二者只是衡量比 对中编辑操作结果的不同方法，可以根据实际情况选择。 下面给出在进行序列比对时常用的规则： 1 ) 两条序列m 和n 的比对的得分( 或代价) 等于将m 转化为n 所用的所 有编辑操作的得分( 或代价) 总和； ， 2 ) m 和n 的最优比对是所有可能的比对中得分最高( 或代价最小) 的一个 比对； 3 ) m 和n 的真实距离应该是在得分函数p 值( 或代价函数w 值) 最优时的 距离。 代价函数和得分函数都是简单相似性评价方法，在计算比对的代价或得分 时，对字符替换操作只进行统一的、粗糙的处理。这两种方法仅仅从存字符的角 度考察序列，忽略了这些字符所代表的生物学意义，即没有没有考虑“同类字符” 替换与“非同类字符”替换的差别。实际上，不同类型的字符替换，其代价或得 分是不一样的，特别是对于蛋白质序列。某些氨基酸可以很容易地相互取代而不 用改变它们的理化性质。例如，考虑这样两条蛋白质序列，其中一条在某一位置 上是丙氨酸，如果该位点被替换成另一个较小且疏水的氨基酸，比如缬氨酸，那 么对蛋白质功能的影响可能较小；如果被替换成较大且带电的残基，比如赖氨酸， 那么对蛋白功能的影响可能就要比前者大。直观地讲，比较保守的替换比起较随 机替换更可能维持蛋白质的功能，且更不容易被淘汰。因此，在为比对打分时， 我们可能更倾向对丙氨酸与缬氨酸的比对位点多些奖励，而对于丙氨酸与那些大 而带电氨基酸( 比如赖氨酸) 的比对位点则相反。理化性质相近的氨基酸残基之 间替换的代价显然应该比理化性质相差甚远的氨基酸残基替换得分高，或者代价 小。同样，保守的氨基酸替换得分应该高于非保守的氨基酸替换。这样的打分方 法在比对非常相近的序列以及差异极大的序列时，会得出不同的分值。这就是提 出打分矩阵( 或者称为取代矩阵) 的原由。在打分矩阵中，详细地列出各种字符 替换的得分，从而使得计算序列之间的相似度更为合理。在比较蛋白质时，我们 可以用打分矩阵来增强序列比对的敏感性