（计算数学专业论文）退火进化算法在生物序列比对中的应用研究.pdf

大连理工大学硕士学位论文 摘要 比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的 特性。序列比对是在生物信息学研究中最常用和最经典的研究手段。其意义在于从核酸、 氨基酸的层次分析序列的相似性，推测其结构功能及进化上的联系，是基因识别、分子 进化、生命起源研究的基础。 本文中介绍了生物信息学中的双序列和多序列比对算法的研究现状，并对多序列比 对问题提出了一种基于模拟退火算法和遗传算法相结合的退火进化算法。多序列比对问 题的算法复杂性按指数规律增长，属于n p 问题，根据这一特点，我们采用属于迭代方 法的遗传算法与模拟退火算法相结合的这一算法，这种方法能够很好的处理n p 问题。 由于遗传算法容易导致早熟收敛问题，使得进化无法收敛到最优解。很多基于遗传算法 的多序列比对的算法就存在这一缺点。根据这一特点，我们通过引进模拟退火算法，利 用模拟退火接受准则( 即m e t r o p o l i s 准则) 保持群体中个体的多样性来解决早熟收敛。模 拟退火具有概率突跳的双向搜索能力，既容易跳出局部极值的陷阱，又能确保搜索的全 局优化性。将模拟退火引入到遗传算法策略中，不但丰富了遗传算法的搜索行为，避免 出现早熟收敛，同时又可以利用遗传算法本身强大的并行全局搜索能力。 最后本文进行了一系列数据测试，通过测试结果。我们可以看到本算法在生物敏感 性和运算效率较之传统算法均有所提高。 美麓调。生物佰患攀l 序列比对t 遗传算法i 横拟遇火算法 退火进化算法在生物序列比对中的应用研究 a p p l i c a t i o ns e a r c ho f a n n e a l i n ge v o l u t i o na l g o r i t h mi nb i o l o g y s e q u e n c ea l i g n m e n t a b s t r a c t c o m p a r i s o ni st h em o s tc o m m o nm e t h o di nt h es c i e n t i f i cr e s e a r c 1 ，t h a tt h r o u 血t h e c o m p a r i s i o no fr e s e a r c ho b j e c tw i t he a c ho t h e rr e l a t i v e l yl o o kf o rt h ec h a r a c t e r i s t i ct h a tt a r g e t m i g h tp o s s e s s s e q u e n c ea l i g n m e n ti st h em o s tf r e q u e n t l ya n dc l a s s i c a lr e s e a r c hm e a l l so f b i o i n f o r m a t i c s i t sm e a n i n gr e s tw i t ha n a l y z i n gs e q u e n c ee o m p a r a b i l i t yf r o mt h el e v e lo f n u c l e i ca c i da n da m i n oa c i d ，c o n f e r r i n gi t sr e l a t i o no fs t l u c t u r a lf u n c t i o na n de v o l u t i o n t h e f o u n d a t i o no f g e n ed i s c e r n ，m o l e c u l ee v o l u t i o na n do r i g i no f l i f es t u d y h a v ei n t r o d u c o dt h ec u r r e n ts i t u a t i o no fs t u d yo na l g o r i t h mt h a tp a i r w i s es e q u e n c ea n d m u l t i p l es e q u e n c ea l i g n m e n ti nb i o i n f o r m a t i c si nt h i st e x t t h a nb a s e do ns i m u l a t e da n n e a l i n g a l g o r i t h ma n dg e n e t i ca l g o r i t h m , p r o p o s et o a l l a n n e a l i n ge v o l u t i o na l g o r i t h mi nb i o l o g y s e q u e n c ea l i g n m e n t t h ea l g o r i t h mc o m p l e x i t yo f m u l 印l es e q u e n c ei n c r e a s e si nt h ee x p o n e n t l a w ，i san pp r o b l e m ，a c c o r d i n gt ot h ec h a r a c t e r i s t i cw ea d o p tt h ea l g o r i t h mb e l o n g st o i t e r a t i v ea l g o r i t h mt h a tc o m b i n ew i t hs i m u l a t e da n n e a l i n ga l g o r i t h ma n dg e n e t i ca l g o r i t h m , t r e a t m e n tn pp r o b l e m 也a tt h i sk i n do fm e t h o dc a nb ev e r yg o o d b e c a u s eg e n e t i ca l g o r i t h m c a nb ee a s yt oc a u s ee a r l y - m a t u r i n gt od i s a p p e a rq u e s t i o n ，s oa st oe v o l u t i o nb eu n a b l et og e t o p t i m u mt os o l v e al o to fm u l t i p l es e q u e n c ea l i g n m e n tb a s e do ng e n e t i ca l g o r i t h mh a v et h i s s h o r t c o m i n gm o r e t h a nt h e a l g o r i t h mr i g h t a c c o r d i n gt ot h i sc h a r a c t e r i s t i c ，t h r o u g h i n t r o d u c i n gs i m u l a t e da n n e a l i n ga l g o r i t h m , u t i l i z es i m u l a t e da n n e a l i n ga l g o r i t h m ，a c c e p t i n g c r i t e r i o n ( m e t r o p o l i sc r i t e r i o n ) k e e pc o l o n yv a r i e t yo fi n d i v i d u a lt os o l v ee a r l y m a t u r i n gt o d i s a p p e a rq u e s t i o n s i m u l a t e da n n e a l i n gh a st w o w a ys e a r c ha b i l i t yt h a tp r o b a b i l i t yj u m p s s u d d e n l y ，i ti sa p tt oj u m po u tt h et r a po fs o m ee x t r e m ev a l u e ，t h eo v e r a l lo p t i m i z a t i o nt h a t c a na l s og u a r a n t e et ob es e a r c h e df o r i n t r o d u c i n gs i m u l a t e da n n e a l i n ga l g o r i t h mi nt h e g e n e t i ca l g o r i t h mt a c t i c s ，n o to n l ye n r i c ht h eg e n e t i ca l g o r i t h ms e a r c hb e h a v i o r ，a v o i d d i s a p p e a re a r l y - m a t u r i n g ，b u ta l s oc a nu t i l i z es t r o n gt h eo v e r a l lo p t i m i z a t i o no fg e n e t i c a l g o r i t h mr u n n i n gs i d eb ys i d eo f t os e a r c hf o ra b i l i t y t h i st e x tc a r r i e do nas e r i e so fd a t at e s tf i n a l l y ，p a s s i n g 也et e s tr e s u l t w ec a ns e et h i s a l g o r i t h mi si m p r o v e di nb i o l o g i c a ls e n s i t i v e n e s sa n do p e r a t i o ne f f i c i e n c yt os o m ee x t e n t c o m p a r e dw i t ht h et r a d i t i o n a la l g o r i t h m k e yw o r d s b i o i n f o r m a t i e s s e q u e n c ea l i g n m e n ti g e n e t i ca l g o r i t h m ；s i m u l a t e d a n n e a f i n ga l g o r i t h m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 日期： 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：型 导师签名塞运 2 塑五年月j 卫日 大连理工大学硕士学位论文 引言 2 0 世纪9 0 年代以来，随着各种基因组计划的不断发展，核酸和蛋白质数据迅速增 加，截止2 0 0 0 年2 月，核酸序列数据库中序列总数己近5 7 0 万，约含5 8 亿个碱基对； 蛋白质序列数据库s w i s s p r o t 中的序列总数已达8 万5 千多个，由核酸序列翻译得 到的蛋白质序列总数已经超过2 3 万；三维结构数据库p d b 中已有1 万1 千多套原子坐标。 但是，与这些以指数方式增长的生物学数据相比，生物学数据中所蕴藏的知识却非常匾 乏，而这些知识却是医学、药物学、农学和环保科学所急需的，这就造成了数据与知识 之间的一个极大的矛盾，这个矛盾催生了一门新兴的交叉科学生物信息学 ( b i o i n f o r m a t i c s ) ”。目前，生物信息学已成为生命科学和自然科学研究的重大前沿领域 之一。 生物信息学的研究重点主要体现在基因组学和蛋白质组学两方面，具体地说就是从 核酸和蛋白质序列出发，分析序列中表达的结构和功能的生物信息 2 。生物信息学的基 本任务是对各种生物大分子序列进行分析，也就是研究新的计算机方法，从大量的序列 信息中获取基因结构功能和进化等知识。在从事分子生物学研究的几乎所有实验室中， 对所获得的生物序列进行生物信息学分析已经成为下一步实验之前的一个标准操作【3 】。 而在序列分析中，将未知序列同已知序列进行相似性比较是一种强有力的研究手段，从 序列的片段测定，拼接，基因的表达分析，到r n a 和蛋白质的结构功能预测，物种亲 缘树的构建都需要进行生物分子序列的相似性比较。例如，有关病毒癌基因与细胞癌基 因关系的研究，免疫分子相互识别与作用机制的研究，就大量采用了这类比较分析方法。 这种相似性比较分析方法就称为序列比对( s e q u e n c ea l i g n m e n 0 嗍。目前，国际互联网上 提供了众多的序列比对分析软件。然而，不同的分析软件会得到不同的结果，同时所使 用的参数在很大程度上影响到分析的结果。有时常常会由于采用了不合适的参数而丢失 了弱的但却具有统计学显著性意义的重要信息，导致随后的实验研究走弯路。因此，本 文研究的生物信息学中的序列比对算法具有非常重要的理论与实践意义。 退火进化算法在生物序列比对中的应用研究 1 生物信息学基础 1 1 生物信息学 2 l 世纪是信息科学，生命科学的时代。随着人类基因组计划的实施，有关核酸，蛋 白质的序列和结构数据呈指数级增长，运用计算机对其进行分析是必然的趋势。从2 0 世纪8 0 年代末开始，生物信息学( b i o 证f 0 订n 撕c s ) 开始了蓬勃地发展 5 】o 生物信息学是分子生物学，计算生物学，计算机科学，应用数学和信息技术等学科 交叉和融合形成的- - f 3 新兴学科，它是应用计算机和信息技术搜集，储存，分析和整理 各种生物医学信息，并予以管理和利用的一门科学。生物信息学主要包括以下几个研究 领域 6 】： ( 1 ) 序列比对( s e q u e n c ea l i g n m e n t ) ：比对两个或两个以上的符号序列的相似性或不相 似性，它是生物信息学的基础。 ( 2 ) 结构比对：比较蛋白质分子空间结构的相似性或不相似性。 ( 3 ) 蛋白质结构预测：包括2 级或3 级结构预测，主要是预测和研究蛋白质的结构和 折叠过程。 ( 4 ) 计算机辅助基因( 蛋白质编码基因) 识别：在给定基因组序列后，正确识别基因的范 围和基因组序列的精确位置。 ( 5 ) 分子进化和比较基因组学：利用不同物种中同一基因序列的异同来研究生物的进 化，构建进化树。 ( 6 ) 基于结构的药物设计：研究约l o 万种人的蛋白质的结构、功能、相互作用以及与 各种人类疾病之间的关系，寻求治疗和预防方法，包括药物治疗。 ( 7 ) 生物信息数据库的设计与实现：建立数据库对大量的生物信息数据资源进行管理 和维护，以便做进一步的分析、处理和利用。 ( 8 ) 其它：如基因表达谱分析，基因芯片设计和蛋白质组学数据分析等。 生物信息学的研究目标：认识生命的起源、进化、遗传和发育的本质，破译隐藏在 d n a 序列中的遗传语言，揭示“基因组信息结构的复杂性及遗传语言的根本规律”，揭 示人体生理和病理过程的分子基础，为人类疾病的诊断、预防和治疗提供最合理而有效 的方法和途径。 大连理工大学硕士学位论文 1 2 核酸与蛋白质 虽然自然界中的生物种类有成万上亿，但决定它们形态、特性和生命运动的基本生 物分子都是核酸和蛋白质【6 j 。核酸是遗传信息的携带者，不仅在细胞之间，同时也在生 物个体之间世代相传，而蛋白质是遗传信息转化成生物结构和功能的表达者， 核酸最先是由细胞核提出的一种酸性物质因而得名。实际上核算不仅分布在细胞 核，也分布在细胞质。核酸可分为两大类：核糖核酸( c f i b o n u c l e i xa c i d , r n a ) 和脱氧核 糖核酸( d e o x y r i b o n u c l c i xa c i d ，d n a ) 。d n a 主要分布在细胞核内，少量在线粒体中：d n a 是生物遗传信息的携带者，与生物的繁殖、遗传和变异有密切关系。r n a 大部分分布 在细胞质内，小部分在细胞核内：r n a 与蛋白质的生物合成有密切关系。不论是d n a 还是r n a ，他们的基本构成单位都是核苷酸，多个核苷酸相连形成核酸，所以核酸又 叫多聚核苷酸。核苷酸由核苷加磷酸组成。核苷又是由含氮有机碱( 碱基) 加上戊糖组 成的 7 】。d n a 分子中的主要碱基是腺嘌呤、鸟嘌呤、胞嘧啶和胸腺嘧啶。r n a 分子中 的主要碱基是腺嘌呤、鸟嘌呤、胞嘧啶和尿嘧啶。 蛋白质是一种由2 0 种氨基酸通过肽键连接而成的生物大分子。蛋白质结构和功能 都是由核酸根据三联体密码决定的，并在细胞内合成，它参与生物的一切生命活动。 因此，将一切物种核酸或蛋白质序列看作由4 个或2 0 个元素组成的字母袁中选出 的字母序列( 表1 1 ，表l ，2 ) ，如： a t g g c c a a c t ， f g s s k y p r e t t ) 分别表示一条核酸 序列和蛋白质序列。生物信息就是成千上万条以字符序列形式存储核酸或蛋白质序列， 并以某些特定格式存放在各类生物数据库中。 表1 1 核苷酸代码 t a b i c l 1n u c l e o f i d ea c i dc o d e 符号意义符号意义 i a 腺嘌呤 c 胞嘧啶 g鸟嘌呤 t 胸腺嘧啶 表1 2 氨基酸代码 t a b i e l ，2a i i q oa c i dc o d e 符号意义符号意义符号意义 a 丙氨酸 i 异亮氨酸 r 精氨酸 c半胱氨酸k赖甘氨酸s 丝氨酸 退火进化算法在生物序列比对中的应用研究 d 天冬氨酸 l 亮氨酸 t 苏氨酸 e 谷氨酸m甲硫氨酸v缬氨酸 f本内氪箴n天冬酰胺酸w 色氨酸 g 甘氨酸 p 脯氨酸y酪氨酸 h 组氨酸q谷氨酰胺x任意氨酸 1 3 分子生物学中心法则 1 9 5 3 年，f c r i c k 和j d w a t s a n 8 1 提出了d n a 双螺旋互补结构模型。在此基础上， 五年后c r i c k 提出了中心法则。它很好地说明了核苷酸和蛋白质这两大类生物大分子之 间的信息传递关系。简单地说，d n a 作为遗传信息的携带者，它在一定条件下可以准 确地自我复制。遗传信息只能通过最终产物的蛋白质体现或“表达”出来。为此要先把信 息“转录”到单股的r n a 链上( 把此类传递遗传信息的r n a 称为信使r n a ，简称m r n a ) 。 细胞液中有大量核糖体，它们把m r n a 上的信息翻译成蛋白质。新生的蛋白质要折叠 形成特定的三维形状，才能有生物活性，在生命过程中发挥功能。因此，从d n a 到r n a 然后再到蛋白质的信息表达过程是一个单向信息流，这个单向信息流同d n a 之间的信 息传递一起构成了分子生物学的中心法则。但是后来人们发现有一些病毒里面存在反向 信息流一一r n a 也可以转录成d n a 。这类病毒的遗传信息存储在r n a 中，遗传信息 的传递需要首先从r n a 反转录为d n a ，然后才能进行d n a 复制。中心法则如图1 1 所示。 其中，将4 种核苷酸的编码信息转化为2 0 种氨基酸编码的蛋白质序列的分子机理 就是翻译。在翻译过程中，每3 个核苷酸编码( 称为个密码子) 被翻译成蛋白质中一个 特定的氨基酸。 一一、 簸翎 0d n a 转避 ：= = m r n a 逆转荣 翻i 摹 _ 蛋白康 图1 1 分子生物学中的中心法则 f i g u r e l 1t h ec e n t r a ld o g m a o f m o l e c u l a rb i o l o g y 大连理工大学硕士学位论文 1 4 物种进化与基因突变 生物物种在千万年来不是一成不变的，而是随着时间、环境的变化不断进化的。这 种进化反映在基因上就是基因的脱氧核苷酸序列的排列顺序发生了改变。 当基因通过突变使它的脱氧核苷酸序列( 简称基因序列) 发生改变时，由其控制合成 的蛋白质也发生改变，所表现出来的生物性状也就发生了改变。生物物种的多样性就是 由基因排列的多样性决定的。适应环境的性状改变使得物种得以生存和发展，不适应环 境的性状改变使得物种被淘汰，灭绝。生物物种就是在这样的作用下不断进化，形成了 自然界千姿百态的物种。 如果把基因序列抽象为字符的排列，在一些位置上，一条序列相对另一条序列可能 多出一些字符，也可能少了一些字符，或者某些字符被其他字符替换了。这三种情况分 别被称之为“插入”、“删除”和“替换”。 基因序列的突变可以用这三种情况来概括： 原基因序列：1 a c c g 从g a 一 插入：t a c c g g a a g a 删除：t a c c g a a a 一 替换：t a c g g a a g a 由同一个祖先经过进化而产生的两个物种，它们在生物性状上会有一些相似之处， 这反映在基因水平上就是基因序列的排列具有一定的相似性。亲缘较近，序列排列的相 似度就高，亲缘较远，序列排列的相似度就低。反过来，我们也可以推想，基因序列排 列相似度高，说明这样的序列有可能是同源的，即它们可能是由同一个祖先进化而来的： 而排列相似度低，则可能不是一个祖先进化而来的。 退火进化算法在生物序列比对中的应用研究 2 序列比对基础 2 1 序列比对的目的 我们可以通过对序列之间相似性比较来推断不同物种之间的进化关系。如果两个序 列具有足够的相似性，则可以认为两者具有同源性，那么它们的生物性状会存在很大的 相似性，如果我们知道其中一个物种的基因序列所决定的生物功能信息，就可以推断另 一个物种的基因序列所决定的生物功能信息。 因此，将未知序列同已知序列进行比较分析，进而了解未知序列的生物信息的方法 已成为一种强有力的研究手段，这使得我们可以从核酸以及氨基酸的层次上去分析序列 的相同点和不同点，从而推测它们的结构、功能以及进化上的关系。最常用的比较方法 是序列比对。序列比对是指通过一定的算法，对两个或多个用确定字符表示的d n a 或 蛋白质序列进行比较，找出它们的最大相似性匹配。 2 2 相似性与同源性 序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性，就推测二 者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片断的缺失、以及序列 重组等遗传变异过程分别演化而来。序列相似性和序列同源是不同的概念，序列的相似 性( s i m i l a r i t y 或a n a l o g y ) 是可以量化的参数，是一种直接的数量关系，是量的判断， 可多可少，如百分之几。而同源性( h o m o l o g y ) 指从一些数据中推断出序列在进化上曾 具有共同祖先的结论，是严格定义的进化学词汇，即在进化上起源同一，是质的判断， 要么同源，要么不同源。序列之间的相似程度是可以量化的参数，而序列是否同源需要 由进化事实的验证【9 】。 对于不同的相似性程度，我们采用不同的序列分析方法，如图2 1 所示。一般来说， 序列间的相似程度越低，序列分析结果所得的可靠性就越差1 1 0 ，当相似性低于某一界限 时，就很难得出明确的结论。这一界限通常被称为序列相似性界限，即序列相似性朦胧 区( t w i l i 曲tz o n e ) 。通常这一界限为2 0 左右。 6 大连理工大学硕士学位论文 图2 1 各种相似性程度下所用不同序列分析方法 f i g u r e 2 1d i f f e m n ts e q u e n c ea 玎a 】y t i c a lm e 也o d su s e du n d e r 谢o u ss i 玎n i l 盯m m n s i t y 2 3 序列比对问题描述 将d n a 序列和蛋白质序列抽象成为字符序列，我们就可以用数学方式描述序列比 对问题了。 下面给出和序列比对有关的一些定义： 【定义2 1 】序列是有限长度的字符串，序列中的字符由某个有限字符集合q 确 定。对于d n a ，q = a ，c ，t ，g ) 。对于蛋白质，q 由2 0 种代表氨基酸的字符组成。 【定义2 2 】对序列s ，l s l 表示s 中的字符个数。s i 表示序列的第i 个字符。s 1 i 表示序列的前i 个字符组成的子序列。 ill_li_-_ivi_llj 退火进化算法在生物序列比对中的应用研究 【定义2 3 】我们用“”来表示插入和删除所产生的空位。 【定义2 4 】对于x ，y n u - ) 定义盯( x ，y ) 为计分函数，表示x ，y 比较时的得分。 以下是晟简单的一种： f2x 2 y q 盯( z ，y ) = 一1z y e q ( 2 1 ) 【一2 x = 1 t o r y = i _ 【定义2 5 】s 和t 的一个比对a 用序列s 和t 中字符的一一对应表示，其中 ( d i s i = i t i ， s ，r 去掉空格就是s 和t i s i 【定义2 6 】序列比对a 的得分为s c o r e ( a ) = 仃( f 司，t i 皿，得分越高表示序 i = 1 列的相似程度越高。 【定义2 7 】对序列s 和t ，在它们的所有比对结果中，取得最大s c o r e ( a ) 分值 的比对就是最优比对。 2 4 序列比对基本原理 2 4 1 空位罚分 空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有合适的理论模型能 很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有主观特色。一般的处理 方法是用两个罚分值，给空位的第一个空格分配空位罚分睨，称为“空位设置罚分”， 表示新增一个空位的成本，给后面的每个空格分配罚分矿，称为“空位扩展罚分”，表示 空位延伸一个空格的成本；对于长度等于l 的空位，就给这个空格分配“空位设置罚分”。 对于具体的比对问题，采用不同的罚分方法会取得不同的效果。 空位指序列中任意连续的尽可能长的空格。空位的引入是为了补偿那些插入或缺 失，但是在序列的联配中引入的空位不能太多，否则会使序列的排列变得面目全非。每 引入一个空位，联配的分值都会有所扣除。 我们用# s p a c e 表示空格数，# g a p ，表示空位数。以下是两种常用的空位罚分方法： ( 1 ) 空位权值恒定模型 在每个空位中的空格的分值为零，即：盯( x ，一) = 盯( 一，y ) = 0 联配的分值为： 大连理工大学硕士学位论文 o - ( s t 吐t 鲫+ ( # g a p s ) i = i 其中，暖为开放一个空位的罚分。 ( 2 ) 仿射空位处罚模型( a f f i u eg a pm o d e l ) 用一个附加的罚分比例去乘空位的长度 睨+ q 彬 初始条件联配的分值为： ， 口( 邓 ，t f ) + ( 撑g 印s ) + w ( # s p a c e ) i = 1 v ( 0 ，0 ) = 0 v ( i ，o ) = e ( i ，o ) = + f ； v ( o ，j ) = f ( o ，力= 吸+ j w ； 递归条件联配的分值： v ( i ，j ) = m a x g ( i ) e ( i ，) ，f ( i ，) ) ； g ( i ，) = v ( i 一1 ，j 一1 ) + 盯( s f ，r ， ) ； e ( i ，j ) = m a x e ( ，j 1 ) + 形，v ( i ，j 1 ) + 降名+ 形) ； f ( i ，j ) = m a x v ( i 一1 ，j ) + 虻，v ( i 一1 ，力+ 睨+ 呢) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) 表2 1 空位设置罚分和空位扩展罚分对匹配结果的影响 t a b l e 2 1t h ei n f e c t i o no f m a t c h i n gw h i tg a po p e n i n gp e n a l t i e sa n dg a pe x t e n s i o np e n a l t i e s 空位设置罚分空位扩展罚分说明 极少插入或缺失；适用于非常相 大大 关蛋白之间的匹配 少量大块插入：适用于整个功能 大小 插入的情况 大量小块插入：适用于亲缘关系 小小 较远的蛋白质同源性分析 对于比对计算产生的分值，到底多大才能说明两个序列是同源的，对此有统计学方 法加以说明，主要的思想是把具有相同长度的随机序列进行比对，把分值与最初的比对 分值相比，看看比对结果是否具有显著性。相关的参数e 代表随即比对分值不低于实际 比对分值的概率。对于严格的比对，e 值必须低于一定闽值才能说明比对的结果具有足 够的统计学显著性，这样就排除了由于偶然的因素产生高比对得分的可能。 退火进化算法在生物序列比对中的应用研究 2 4 2 替换矩阵 由于序列比对不仅需要考虑子序列之间的匹配，而且需要对整个序列进行比较。因 此，实际操作中，获得序列之间理想的序列比对并不是一件容易的事。所以，通常用替 换矩阵( 又叫计分矩阵) 赋予序列比对结果以分值，用最高的分数来解释具有显著性生物 学意义的比对结果。替换矩阵可以分为单一矩阵和相似性替换矩阵。 单一替换矩阵就是只考虑两个序列之间完全相同的匹配残基数目，可以把它理解为 1 和0 的矩阵，即：相同残基的分数值为l ，不同残基的分数值为0 。表a 中显示的是d n a 序列的单一替换矩阵。显然，这种单一替换矩阵具有很大的局限性。 表2 2d n a 的单一替换矩阵和相似性替换矩阵 t a b l e 2 2d n a s i n g l es u b s t i t u t i o nm a t r i xa n ds i m i l a rs u b s t i t u t i o nm a t r i x acgt alooo c 01oo g0olo t0o0l ( a ) 单一替换矩阵 ( a ) s i n g l es u b s t i t u t i o nm a t r i x acgt a0 9一o 10 1o 1 c0 10 90 1一o 1 go 1。0 10 9o 1 t0 1。o 1o 10 9 ( b ) 相似替换矩阵 ( b ) s i m i l a rs u b s t i t u t i o nm a t r i x 相似性替换矩阵是基于远距离进化过程中观察到的残基替换率，用不同的计分值表 征不同残基之间相似性程度。相似性替换矩阵改进了单一替换矩阵的表征性能，能揭示 那些潜在的具有生物学意义的最佳匹配。恰当选择相似性替换矩阵，可以提高序列比对 的敏感度，特别是两个序列之间相同残基较少的情况下。表b 中显示的是d n a 序列的 相似性替换矩阵。常用的蛋白质替换矩阵有突变数据矩阵( p o i n ta c c e p t e dm u t a t i o n ， 简称p a m ，d a y h o f f 等，1 9 7 8 ) 【i l j , b l o s u m 矩阵( b l o c k ss u b s t i t u t i o nm a t r i x ，h e n i k o f f 和h e n i k o i f , 1 9 9 2 ) ”，p a m 2 5 0 矩阵和b l o s u m 6 2 矩阵。 经过多年的试验，大多数比对程序均对特定的替换矩阵设定了空位罚分的缺省值， 如果用户希望使用不同的替换矩阵，则原来的空位罚值设定不一定合适。如何设定罚分 并无明确的理论可遁，但大的空位开放罚分配以很小的空位罚值被普遍证实是最佳的设 定思路 1 3 。 大连理工大学硕士学位论文 2 5 序列比对算法的发展 序列比对( s e q u e n c ea l i g n m e n t ) 是生物信息学的主要研究领域之一，也是整个生物信 息学的基础。通过序列比对，可以确定序列之间的相似性关系，从而以足够的可信度确 定序列的遗传和功能信息。 生物的遗传和功能信息都存储在d n a 和蛋白质这些生物大分子当中，它们是由成 千上万的原子按生化规则结合起来的序列，具有复杂的3 维结构。这些序列都是由相对 简单的生物化学物组成的，可以用确定的字符表示，比如：d n a 序列用a ，t ，c g 四个 字符表示。蛋白质序列用2 0 种表示氨基酸的字符表示。 序列比对是指通过一定的算法，对两个或多个用确定字符表示的d n a 或蛋白质序 列进行比较，找出它们的最大相似性匹配。经过多年的研究，比对算法已经形成了比较 成熟的体系，探索出了许多有效的算法。 按照参与比对的d n a 的数量来分d n a 序列比对可分为双序列比对和多序列比 对。双序列比对最早是n e e d l e m a n - w u n s c h 动态规划算法【1 “”l 。在此基础上1 9 8 1 年由 s m i t h 和w a t e r m a n 提出s m i t h w a t e r m a n 算法f l “”】，此算法是双序列比对算法中最基本的 算法。随后于1 9 8 5 年i 刍p c a r s o n 和l i p m a n 提出q f a s t a 算法1 舛。b l a s t 算法必2 1 1 是由 a l t s c h u l 等人在1 9 9 0 年提出的。还有m u m e r 算法田1 及遗传算法等等。多序列对比算法中 f e n g 和d o o l i t t l e 于1 9 8 7 年提出的c l u s t a l 算法弘2 5 1 使用最为广泛。而后还有星比 算法等，近年来，将优化算法应用于序列比对的研究逐渐多了起来。 退火进化算法在生物序列比对中的应用研究 3 多序列比对算法研究 多序列比对就是把两条以上可能有系统进化关系的序列进行比对的方法，实际上是 双序列比对问题的一般化推广。目前对多序列比对的研究还在不断前进中，现有的大多 数算法都基于渐进的比对思想，在序列两两比对的基础上逐步优化多序列比对的结果。 进行多序列比对后可以对比对结果进行进一步处理，例如构建序列模式的p r o f i l e ，将序 列聚类构建分子进化树等等。意义在于通过多个相关蛋白质的相似性( 同源性) ，了解 其在进化上亲缘关系的远近，推断分子起源和进化规律等。同时研究多个序列中的保守 区域，就可以猜测这些区域对蛋白质结构、功能的重要性，从而进行分子设计。 3 1 多序列比对问题的数学描述 与双序列比对问题的表示相对应，多序列比对可以表示为：对多个字符串序列通过匹 配相对应的字符或插入“”来显示插入或删除而得到序列之间的最大相似性排列，使得多 个序列之间所对应的相同字符是多。如果给每一种操作g 雷入、删除、替换) 赋予一定的 权值，则多序列比对问题就是要找出多条序列为最小距离、最大相似度或最小编辑距离 时的一种匹配模式。 为了便于描述，对多序列比对过程给出下面的定义。把多序列比对看作一张二维表， 表中每一行代表一个序列，每一列代表一个残基的位置。将序列依照下列规则填入表中： 1 ) 一个序列所有残基的相对位置保持不变； 2 】将不同序列间相同或相似残基放入同一列，即尽可能将序列间相同或相似残基上 下对齐。 表3 1 表示五个短序列( i v ) 的比对结果。通过插入空位，使五个序列中大多数相同 或相似残基放入同一列，并保持每个序列残基顺序不变。插入空位后五个序列的长度相 等。称比对前序列中残基的位置为绝对位置。如序列i 的第3 位的残基是甘氨酸g ，则 绝对位置l3 就是甘氨酸，而不能变成任何其它氢基酸。相应地，我们称比对后序列中 残基的位置为相对位置。显然，同一列中所有残基的相对位置相同，而每个残基的绝对 位置不同，因为它们来自不同的序列。需要说明的是，绝对位置是序列本身固有的属性， 或者说是比对前的位置，而相对位置则是经过比对后的位置，也就比对过程赋予它的属 或者说是比对前的位置，而相对位置则是经过比对后的位置，也就比对过程赋予它的属 性。 大连理工大学硕士学位论文 表3 1 多序列比对定义描述 t a b l e 3 id e s c r i p t i o no f m u l t i p l es e q u e n c ea l i g n m e n td e f i n e l23456 7891 0 iydgga v eal ydggeal i i ifeg gil v eal i vfdgil v q av v yegga vv q a l 下面给出多序列比对的定义2 6 】： 定义1 ：给定一组序列s l ，s 2 ，s t ，其中s ，= a ，g ，c ，t 或= a ，足，v ) ， 则序列s i ，的比较被认为是一组多序列比对，其中： ( 1 ) l s ? l s ： = s ： ( 2 ) s ? ，分别是在序列s 。，s 2 ，s 。中加入一定的空格所得到的。 若有k 条序列： s l = s l l s 】2 s l 、 s 2 = 足l s 2 2 s h ： s 女= & 1 s s h 对于多条序列的相似性比较，通过插入“- ”字符将这k 条序列补齐并获得一个比对结 果，表示如下： s i s 二s 五 s 二s 三2 - - s 盖 ： s ：。s ：- s 二 比对后的序列长度均为l 。与双序列的比对相同，多序列的比对结果也可用分值来 衡量其相似性。这个相似性分值用公式表示为： f s c o r e ( s ，s ：，一，- 瓢) = p ( s ：，s 二，) ( 3 1 ) 扣l 定义2 ：多序列s 。，是，s 。的最优比对，就是得分值s c o r e 为最大的时候所对应的k 条序列的一个比对。 对于多条序列比对的分值，计算方法一般有： 退火进化算法在生物序列比对中的应用研究 1 ) d i s t a n c ef r o mc o n s e n s u s 如果在多序列比对中某一列上的字符大部分都相同，假设该字符是x ，则x 为 c o n s e n s u s 字符。多序列比对的分值可以用比对中每一列与c o n s e n s u s 字符不相同的字 符个数之和来表示。 2 ) e v o l u t i o n a r yt r e ea l i g n m e n t 每一条序列对应进化树中的一个结点，任意两条序列的比对值( 或距离) 为树中对应 结点之间边的权值。最优序列的比对可通过权值之和最小的进化树来表示。 3 ) s p ( s u m o f p a i r s ) 该方法是最为通常使用的一种分值计算方法。多序列比对的分值为多个序列中任意 两条序列的分值之和，若有k 条序列，则分值表示为： c ； 胆= 巧 ( 3 2 ) i - i 其中巧是两条序列的分值，k 条序列的两两组合总共有q 对。 4 ) c o f f e e ( c o n s i s t e n c yb a s e do b j e c t i v ef u n c t i o nf o ra l i g n m e n te v a l u a t i o n ) “ 若有n 条序列s ，s 2 ，s 。，s c o r e ( a f ) 是两序列墨和s j 的得分值，l e n ( a f ) 是由 s ，和s 产生的比对长度，彬，是与双序列比对相关的权值。c o f f e e 的得分值的计算公 式表示为： 一lnn - i c o f f e e s c o r e = s c o r e ( a “) 1 x l e n ( a 口) 】 ( 3 3 ) i = lj = i + li = 1 ，= ，+ i 在多序列比对的分值计算中，也涉及到记分矩阵及空位罚分，选择方法与双序列比 对相同，在此不再做介绍。 3 2 多序列比对问题的研究现状 己有的多序列比对算法大体分三类：精确比对算法、渐进比对算法、迭代比对算法。 精确比对算法最为经典的是多维n e e d l m a n w u n s c h 算法、但其可行的计算维数为 3 c a r r i l l o l i p m a n 算法f 2 8 】通过减小计算空间，将计算维数提高到1 0 。渐进比对算法由 h o g e w e g 首先提出，f e n g 和t a y l o r 又加以完善。m u l t a l i n 方法【”j 是基于用一系列双序 列比对开始的思想，然后基于双序列比对的打分值进行一个分层次的聚类。当序列都分 成类后，开始进行多序列比对，计算出多序列中的两个序列比对的新值，重新构建一棵 树。这个过程不断进行，直到分值不再上升，此时多序列比对也就结束了。非常著名的、 被广泛使用的多序列比对软件包c l u s t a lw ( 其w i n d o w s 版本为c l u s t a lx ) 基于渐进比对 思想构建，基本思想是基于相似序