（计算机应用技术专业论文）免疫遗传算法在生物序列比对中的应用.pdf

摘要 序列比对是生物信息学中最常见的问题之一，也是一种重要的生物信息处理技术。 它通过对生物序列数据进相似性比较，来发现生物序列中的功能、结构和进化等信息， 是基因识别、分子进化、生命起源等生物信息学研究的基础。 免疫遗传算法是一种混合型改进遗传算法。它将遗传算法与免疫原理结合起来考 虑，在传统遗传算法的框架之上，引入了免疫系统的诸多特性如免疫调节机制、多样性 保持策略等，有效地防止了搜索过程中的未成熟收敛等问题，是一种更加有效的优化算 法。 本文在分析了国内外序列比对算法及序列比对的优化问题本质的基础上，设计了一 种适用于双序列比对可行解的编码方案，提出了一种应用于双序列比对的新算法基 于免疫遗传算法的双序列比对方法口s 触g a ，p a 诳w i s es e q u e n c e 舢i 印m c n tb a s e do n i m m u n eg e n e t i c 9 0 r i t h m ) 。并应用上述算法分别进行了d n a 和蛋白质序列的比对，通 过实验证明了其可行性和有效性。 本文p s 触g a 算法的实现采用的是c + + 语言。同时，对n e e d l e m 趿w u n s c h 算法、 基于遗传算法的双序列比对方法p s a g a 也进行了实现。前者为评价p s a g a 及p s 越g a 算法结果的优劣提供了判定依据；而后者的比对实验结果说明了与其相比p s 越g a 能够 明显改善比对结果，提高比对效率。此外，还采用w i n d o w s a p i 函数对进行序列比对的 用户交互界面进行了实现。 关键字：序列比对；遗传算法；免疫调节机制；未成熟收敛；免疫遗传算法 a b s t r a c t s e q u e n c e 越i 萨m e n ti so n eo f t h ec o m m o np r o b l e m sa n da l s 0o n eo ft t l em o s ti m p o n a i l t t o o l si nb i o i n f o m a t i c sr e s e 甜c h a st h eb a s eo fb i o i n f o 衄a t i c sr e s e a r c hs u c h 勰g e n e i d e m i f i c a t i o n ，m o l e c u l ee v o l u t i o na n dl i f co r i 西n ，i tc o m p 缸e st h es i i n i l a r i t yo fb i o l o g yd a t at o i n f e rt h e i rf h n c t i o n s s t n l c “l i t sa n de v o l u t i o ni n f b n n a t i o 璐 i m m l l l l eg e n e t i c 越g o r i t l l m ( i g 砷i sah y b r i di m p r o v e dg c n e t i ca l g o r i t h m ( g a ) i t c o m b i l l e st h eg aa i l di m m u n ct h e o r yb yi n t r o d u c i n gt t l ei n 】m u n es y s t e m sc h a r a c t e r i s t i c s ( s u c ha si i i l m u n er c g l l l a t i o nm e c h 卸i s m ，d i v e r s i t yk e e p i n gs t r a t e g i ce t c ) i n t oc a i l o n i c a ig a n c a l lp r e v e n tt h ep r e m a t u r c n v e r g e n c ea n do 也e rp r o b l e m si nt h ep r o c e s so fs c a r c h s oi ti sa b e t t e ro p t i m i z a t i o ns e a r c ha l g o f i t 王l n l i n t h i sp a p e r ，b a s e do nt l l es t u d yo ft l l ed e v e l 叩m e n to fs e q u e n c ea l i 弘m e m 锄di t s e s s e n c e ，t 1 1 ea u t h o rd e s i g n sac o d i n gm e t h o df o rt h ep o s s i b l es o l u t i o no fp a i 卜w i s es e q u e n c c a l i 肛m e n ta n dp 嘲p o s e sap a i f 、们s es e q u c n c ea 1 i 母衄e n t 寻p p 日c hb a s e d0 ni g a ( p s m g a ) 1 1 l i sn e wa l g o r i t h n li sa p p l i e dt od n a 卸dp r o t e i ns e q u c n c ca l i g 哪e n ti nt l l ee x p e r i m e n t t h e r e s i l l t sd e m o n s t r a t et h a tt h en e wa p p r o a c hi sr c a s o n a b l e 柚de f e i c i e n t i i lt l l i sp a p e r p s 趟g aw a sw r i t t e ni nc + + m e a n w l l i l e ，n e e d l e m 柚一、u n s c h ( n 叼 a 1 9 0 r i t h ma i l dp a i r w i s es e q u c n c em i 印m e n tb a s e do ng c n e t i c 趾g o r i t h m ( p s a g a ) w c r c r e a l i z e dt 0 0 n wr e s u l tp r o v i d e dt h eb a s i st od c t e m i n et l l eq u a l i t y0 ft h ep s 越g ar e s u l t sa n d t h ee x p e r i m e n tr e s u l t0 fp s a g ai l l u s t r a t e dt h a tp s m g ac a ni n l p r o v et h ea l i 萨m e n tr e s u l t a n de 位d e n c ya p p a r e n t l y i na d d i t i o n ，t l l eu s e ri m e r f a c et oa l i 印s e q u e n c e sw a sw r i t t e nb y 、 h n d o wa p i k e yw o r d ：s e q u e n c e 舢i 印m e n t ； g e n e t i ca l g o r i t h m ；i m m l l l l er e g t l l a t i o nm e c h a n i s m ； p r e m a t u r ec o n v e r g e n c c ；i m m u n e g e n e t i ca l g o r i t 胁 i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名： 圣茎墨日期：迎：堇：丛 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即：东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王盔墨指导教师签名：要墨i ! 日 期：塑：茎：丕日期：趣1 6 ：篁：兰 学位论文作者毕业后去向： 工作单位：基毫互星工! 釜避盘奉菪随电话： 通讯地址： 邮编： 1 1 生物信息学 第一章引言 1 9 9 0 年1 0 月人类基因组计划正式启动，随着该计划的顺利实施，涌现出了海量的 生物分子数据。这些生物分子数据具有丰富的内涵。充分利用这些数据，通过数据分析， 揭示其内涵，得到对人类有用的信息，是科学家们所面临的一个严峻的挑战。生物信息 学( b i o i n f o m a t i c s ) 就是为迎接这种挑战而发展起来的一门新型学科，它是由生物学、 数学、计算机科学相互交叉所形成的学科。 在生物信息学这样一个交叉学科研究领域中，各学科的科学家们共同研究生物分子 信息的获取、管理、分析和利用。具体而言主要是利用计算机存储核酸和蛋白质序列， 研究科学的算法，编制相应的软件对序列进行分析、比较与预测，从中发现生物分子信 息组织和表达的规律，从而认识生物分子的作用，探索生命的起源和进化，进而加深对 生物世界的认识。在生物学、医学领域中利用生物分子数据及其分析结果，可以大大 提高研究和应用的科学性及效率。总而言之，生物信息学是一门研究生物系统中信息现 象的学科，它主要包括以下几个研究领域m ： 1 )序列比对( s e q u e n c e 舢i 印m e n t ) ：比对两个或两个以上的生物序列的相似 性或不相似性，是生物信息学的基础。 2 ) 结构比对：比较蛋白质分子空间结构的相似性或不相似性。 3 ) 蛋白质结构预测：包括二级或三级结构预测，主要是预测和研究蛋白质的结 构和折叠过程。 4 )计算机辅助基因( 蛋白质编码基因) 识别：在给定基因组序列后，正确识别基 因的范围和基因组序列的精确位置。 5 )非编码区分析和d n a 语言研究。 6 ) 分子进化和比较基因组学：利用不同物种中同一基因序列的异同来研究生物的 进化，构建进化树。 7 ) 基于结构的药物设计：研究人的约1 0 万种蛋白质的结构、功能、相互作用以及 与各种人类疾病之间的关系，寻求治疗和预防的方法，包括药物治疗。 8 ) 生物信息数据库的设计与实现：建立数据库对大量的生物信息数据资源进行管 理和维护，以便做进一步的分析、处理和利用。 9 )其它：如基因表达谱分析，基因芯片设计和蛋白质组学数据分析等。 1 2 序列比对算法的发展 序列比对是生物信息学的主要研究领域之一，也是一种重要的生物信息处理技术。 它通过对序列数据进行相似性比较，来发现生物序列中的功能、结构和进化的信息，是 基因识别、分子进化、生命起源等生物信息学研究的基础0 1 。 生物的遗传和功能信息都存储在d n a 和蛋白质这些生物大分子当中，它们是由成 千上万的原子按生化规则结合起来的序列，具有复杂的三维结构。然而这些序列都是由 相对简单的生物化学物质组成的，可以用确定的字符表示，比如：d n a 序列可以用a 、 t 、c 、g 四种核苷酸字符表示，而蛋白质序列可以用2 0 种表示氨基酸的字符表示。 序列比对通过一定的算法，对两个或多个用确定字符表示的生物序列进行比较，匹 配相对应的字符或插入“”来显示插入或删除，找出它们之间的最大相似性匹配。经 过多年的研究，人们已探索出了许多有效的算法。 点阵图( d o t p l o t ) 是双序列比对的基本方法。1 9 7 0 年g i b b s 和m c m t y p e 采用矩阵点 阵图方法寻找序列中的相似匹配片断m 。 1 9 7 0 年n e e d l e m a i l 和w u n s c h 提出了基于动态规划思想的双序列比对算法“1 ，该算 法是一种全局比对方法，其比对结果反映了两个序列中所有残基的整体相似性。 1 9 7 5 年，h i r s c h b e r g 根据分治策略提出一种基于动态规划算法的改进算法“3 ， 降低了空间复杂度，但运行时间增加了，这实际上是一种以时间换取空间的策略。 1 9 8 1 年s m i t h 和w a t e m a n 基于仿射空位罚分模型开发了局部比对算法，使得动态 规划比对算法能够寻找两条序列当中的局部高相似度片断”3 。 尽管序列比对是比较两条已知序列的极为重要的工具，然而序列比对更为常见的用 途是用来搜索具有大量序列的数据库，以寻找与新发现的序列相似的已知序列，通过已 知序列推断新序列的结构和功能。在数据库搜索过程中，由于被搜索序列很长，而且数 量巨大，用简单而直接的方法将数据库中每条序列与查询序列进行比对并返回比对得分 最高的序列难以奏效。作为替代方法，各种索引方法与启发式方法被用来加快搜索的过 程。f a s 魄和b l a s t 是目前最为著名的两个数据库搜索算法，它们都是基于局部相似 性的算法。f a s 魄是由p e a r s o n 和u p m 趾于1 9 8 5 年提出的0 3 ，而b l 峪t 是1 9 9 0 年由 s f ：a l t s c h u l 等人于提出的。1 。 近年来，将优化算法应用于序列比对的研究逐渐多了起来。 1 9 9 6 年，c 6 d r i cn o t r e d a m e 和d e s m o n dgh i g g i i l s 提出了一种应用于多序列比对的 遗传算法，并实现了基于该算法的软件包s a g a “”。 蚁群算法是一种适合于求解大规模组合优化问题的算法。用该算法求解序列比对问 题是优化算法在该领域的一种尝试，比如2 0 0 3 年梁栋、霍红卫等人描述了用于序列比 对的自适应蚁群求解方法m ，。 无论利用何种比对算法，都需要对比对进行打分以判断比对结果的优劣。1 9 7 8 年， d a y h o f 等人在研究蛋白质序列的进化后，建立了p a m 替换矩阵“，作为比对的计分函 数。1 9 9 2 年，h e n i k o e 等人将后来被广泛采用的b l o s u m 替换矩阵引入了比对算法“”。 2 1 3 免疫遗传算法概述 早在2 0 世纪5 0 年代和6 0 年代，就有少数几个计算机科学家独立地进行了所谓的“人 工进化系统”的研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。 早期的研究形成了遗传算法的雏形。到了6 0 年代中期，美国m i c h i g 如大学的j o l l l l h o l l 柚d 在f r a s e r 和b r e m e 衄猢等人工作的基础上提出了位串编码技术，并强调将交配 作为主要的遗传操作。后来，他与他的学生们将该算法加以推广并应用到优化及机器学 习等问题之中，并正式命名为遗传算法。在一系列研究工作的基础上，8 0 年代由g o l d b e r e 进行归纳总结，形成了遗传算法的基本框架。2 0 多年来，人们广泛地应用遗传算法解决 各种实际优化问题，如组合优化设计、系统工程、自适应控制，规划设计等“。 传统的遗传算法虽然自成体系且使用广泛，但是依然有许多不足，例如对于局部空 间的搜索问题不是很有效、个体的多样性减少得很快等。这些缺陷的存在限制了遗传算 法的应用。于是，人们开始研究如何改进算法以及采用合适的算法加快寻优速度和改善 寻优质量。 免疫遗传算法是近几年来发展起来的一种改进型遗传算法，它是将生物学中生物免 疫机制和遗传算法相结合而形成的一种优化算法“”。生物进化和生物免疫从不同角度说 明了适者生存的自然规律。进化是从总体上生物种群的进化，而免疫则通过“疫苗”的 作用，更注重提高个体的环境适应能力。将进化与免疫结合起来考虑，能得到更有效的 优化算法。另一方面，多样性是免疫系统的重要特征之一，利用抗体多样性保持机制改 进传统的遗传算法，可提高算法的群体多样性，有效地抑制早熟现象，使免疫遗传算法 具有较好的全局收敛性，有效地提高寻优能力。 1 9 9 3 年，美国新墨西哥大学的s f o e s t 和洛斯阿拉莫斯实验室的a p e r e l s o n 首 先提出了免疫系统的遗传建模方法。之后，有很多学者都提出了混合的免疫遗传算法， 它们在很多领域中都取得了很好的应用。根据人们在遗传算法中引入的免疫机制的不 同，免疫遗传算法大致可以分为利用疫苗的免疫遗传算法和利用抗体多样性的免疫遗传 算法等。 1 4 本文主要内容 本文在研究了生物序列比对的发展现状，以及免疫遗传算法的特性之后，尝试将免 疫遗传算法应用到序列比对当中，根据序列比对的特点对其进行了适当的编码，提出了 基于免疫遗传算法求解序列比对问题方法p s 越g a 口a i r - w i s es e q u e n c c 舢i 驴_ m e n t b a s e do ni l n m u n eg e n e t i c g o r i t h m ) 。同时，为检验算法的有效性，作者利用c + + 语言分 别进行了卜c e d l e m a n w u n s c h ( 简称n w ) 、p s 朋g a 和p s a g a 算法的实现，并基于以上 方法对d n a 序列及蛋白质序列进行了比对实验。结果表明，p s a i g a 能够在占用少量 内存的情况下获得近似于n w 算法结果的最优解，是求解双序列比对问题的有效方法。 文章的内容安排如下： 3 第一章简要介绍了生物信息学的背景，序列比对算法的发展概况，以及免疫遗传算 法的基本原理。 第二章对生物序列比对问题进行了详细介绍，包括序列比对的定义、数学模型，空 位罚分和替换矩阵的使用，经典比对算法的原理等内容。 第三章介绍了免疫遗传算法的原理、特性，并对免疫遗传算法的设计思想及算法流 程进行了详细描述。 第四章阐述了利用免疫遗传算法求解序列比对的算法模型，详细介绍了基于它的序 列比对方法的设计。 第五章主要对算法的实现方法进行了介绍，并对算法实验结果进行了分析和比较。 最后总结全文，归纳工作要点，给出建议和展望。 4 2 1 生物学背景知识 第二章生物序列比对 2 1 1 遗传信息的传递与表达 储存、利用、传递和表达信息是生物最显著的特征。 科学家们发现在生物细胞中存在大量的酸性大分子物质：脱氧核糖核酸 ( d e o x 硼b o n u c i e i ca c i d ，简称d n a ) ，核糖核酸( r f b o n u d e i ca c i d ，简称i u 呛) 。这两种大 分子在组成上十分相似，它们都是由“磷酸”，“脱氧核糖”或“核糖”，以及“有机碱” 组成的，因而又被统称为“核酸”。此外，细胞核中还存在大量的由氨基酸链接而成的 蛋白质。这两种生物大分子存在于现在已知的所有的生命体中，是生命的标志。其中 d n a 的含量十分稳定，是遗传的物质基础。而蛋白质则是细胞组织成分中含量最丰富、 功能最多的物质。它执行的任务种类繁多，变化多端。 d n a 分子是由很多不同的脱氧核苷酸组成的多脱氧核苷酸链，脱氧核苷酸由三部分 组成：磷酸、脱氧核糖和含氮碱基。其中共有4 种不同的碱基：鸟嘌呤、腺嘌呤、胸腺 嘧啶和胞嘧啶( g 、a 、t 和c ) 。d n a 是由两条脱氧核苷酸链组成的双螺旋结构，脱氧 核糖和磷酸相间排列在外侧，形成两条主链，构成d n a 的基本骨架。两条主链之间的 横档是碱基对，排列在内侧。相对应的两个碱基通过氢键连接形成碱基对，把两条主链 连接起来。碱基配对有一定的规律：a 与t 配对，c 与g 配对。d n a 一条链中的信息 内容相对于另一条链中的信息是冗余的，通过双链分离并且分别以两条链为模板而合成 新链，从而形成新的d n a 分子，这样，d n a 可以忠实地代代传递。 现代遗传学的研究认为，生物的性状是由基因控制的。基因是遗传物质的功能和结 构单位，是具有遗传效应的d j a n 片断。每个基因含有成千上万个脱氧核苷酸，其排列 顺序就决定了生物性状的显现。而蛋白质是形成生命体的基本物质，生物的性状主要是 由蛋白质来体现的。生物体蛋白质结构的不同，体现了它们各自不同的性状。而基因控 制性状就是通过控制蛋白质的合成来实现的。 蛋白质是由氨基酸组成的，在自然界中，氨基酸有3 0 0 余种，但组成蛋白质分予的 氨基酸仅有2 0 种，且它们都有一个共同的特点，即在口碳原子上均联结一个氨基和一 个羧基，因此称为口氨基酸。一种口氨基酸有别于其它口氨基酸的性质是由其残基或 侧链决定的，通常认为这些残基是r 基团。组成蛋白质的2 0 种氨基酸可以用2 0 个字母 表示，包括a 、r 、n 、d 、c 、q 、e 、g 、h 、i 、l 、k 、m 、f 、p 、s 、t 、w 、y 和v 。 信息从基因的核苷酸序列中被提取出，以用来指导蛋白质的合成，这被分子生 物学家称为中心法则( c c n t r a ld o g m a ) 。该过程很简单，首先由d n a 中储存的信息指导 合成一条寿命较短的单链核苷酸，即m ( 核糖核酸) ，然后利用产生的鼢蛆指导蛋 s 白质的合成( 如图2 2 所示) 。合成基因的r n a 拷贝的过程叫做转录，它是以d n a 双 链中的一条单链作为模板，按照碱基互补配对的原则合成的。其过程如下： d n a a g a o g g c - a - t r n a u c - u u - c - u u u - a 图2 1d n a 转录成r n a r n a 的碱基中用“尿嘧啶u ”替换了d n a 中的“胸腺嘧啶t ”，变成了a 、u 、c 和g 。 d n a 在细胞核当中经过转录过程合成了r n a 链，称为信使r n a ( m r n a ) 。在细胞质中，以 m r n a 为模板，就可以合成具有一定氨基酸顺序的蛋白质，这个过程称为翻译。m r n a 中 每三个相邻的碱基( 称为密码子) 决定了一种氨基酸，比如：g c a 就决定了“丙氨酸a ” 的合成。 转录翻译 d 1 蛆片断( 基因) r n a + p r o t e i n ( 性状) 图2 2 分子生物学中心法 遗传信息通过如图2 2 显示的过程便完成了传递和表达。 2 1 2 物种进化与基因突变 生物物种在千万年来不是一成不变的，而是随着时间、环境的变化不断进化的。进 化的第一原因是基因突变，即基因的脱氧核苷酸序列的排列发生了改变。由核苷酸替代、 插入缺失、重组和基因转换等引发的突变基因即d n a 序列，通过群体水平的遗传漂变 和或自然选择进行扩散，并最终在物种中得以固定。 当基因通过突变使它的d n a 序列发生改变时，由其控制合成的蛋白质也发生改变， 所表现出来的生物性状也就发生了改变。生物物种就是在这样的作用下不断进化，形成 了自然界千姿百态的物种。 基因突变的种类主要有以下三种： ( 1 ) 替代( s u b s t i t u t i o n ) ：在进化过程中生物序列的某一核苷发生了错误改变，替 代能否改变蛋白质序列，取决于其发生的位置。当替代发生在遗传信息编码区时， 可能会改变后代蛋白质序列。 ( 2 ) 插入或删除( i n s e r t i o no rd e l e t i o n ) ：在进化过程中添加或删除一个或多个核 苷，两者常简记为i n d e l 。 ( 3 ) 重排( r e a r r a n g e m e n t ) ：d n a 或蛋白质的一些序列片段的合成过程中在连接的顺 序上发生了改变。 在很多方面对基因突变的研究是很重要的：遗传的乱序和一些疾病都是由于基因突 变造成的。另外基因突变是造成物种多样性的基本原因之一，例如人类的基因组和老鼠 的基因组是非常相似的，它们的主要区别在于d n a 片段的内部序列的不同。 由同一个祖先进化而产生的两个物种，它们在生物性状上会有一些相似之处，这反 6 映在基因水平上就是基因序列具有一定的相似性。亲缘越近，序列的相似度越高；反之， 相似度就越低。反过来，我们也可以根据基因序列的相似度来推测两个物种间的进化关 系。 2 2 生物序列比对 2 2 1 序列比对问题 生物序列比对又称序列联配，其意义在于从核酸、氨基酸的层次分析序列的相似性， 推测其结构功能及进化上的联系，是基因识别、分子进化、生命起源研究的基础。序列 比队的理论基础是进化学说，如果两个序列之间具有足够的相似性，可以推测二者有共 同的进化祖先经过序列内残基的替换、残基或序列片段的缺失、以及序列重组等遗传变 异过程分别演化而来。如果一个新测定的d n a 序列与一个已知的基因序列很相似，那 么该基因序列含有与已知基因序列相似的结构和功能。因此，序列比对方法的应用对于 基因结构和功能的研究具有较大的实际意义。 最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两个序列之 间的相似区域和保守性位点，寻找二者可能的分子进化关系。进一步的比对是将多个蛋 白质或核酸同时进行比较，寻找这些有进化关系的序列之间共同的保守区域、位点和 p m f i l c ，从而探索导致它们产生共同功能的序列模式。此外，还可以把蛋白质序列与核 酸序列相比来探索核酸序列可能的表达框架：把蛋白质序列与具有三维结构信息的蛋白 质相比，从而获得蛋白质折叠类型的信息。 序列比对也是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进行比 对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关查询序列的大 量有价值的参考信息，对于进一步分析其结构和功能都会有很大的帮助。随着生物信息 学数据大量积累和生物学知识的整理，通过比对方法可以有效地分析和预测一些新发现 基因的功能”1 。 2 2 2 序列比对问题的数学模型 序列比对实际上就是运用某种特定的数学模型或算法，找出两个或多个序列之间的 最大匹配碱基或残基数。 将d n a 序列和氨基酸序列抽象成为字符序列，我们就可以用数学方式来描述序列 比对问题了。从数学的角度来看，序列比对实质上是一个优化问题“。 假设现在有两条生物序列： s 1 = s l l s l 2 s 1 s 2 = s 2 ，2 2 s 执 7 其中s “尺，= 1 ，2 ，f 。，i 一1 ，2 。这里r 为核苷酸或氨基酸字符集，对于d n a 序列 r 忸lc g ；对于蛋白质序列，r 包含了2 0 个字符，每个字符代表一种氨基酸。 在长期进化过程中，有些核苷酸残基相对保守，而有些则可能发生变异，如t 变成 g ，c 变成a 等。另外，少数残基会发生缺失或插入现象。因此，在比较两条相关序列 时会出现中断现象，这就产生了“间隙”问题，间隙用字符“一”表示。令r t r u 一) ， 则序列s ，s ：的一个比对a l i 髓如下所示： 墨= s 1 1 墨2 畦 s ：= s ：。s ：s ：。 其中尺，f 一1 ，2 ，j 一1 ，2 ，l ，m a x f f ) s l s + z 2 。同时，如果移去，s ：中的“”， 将得到相对应的原来的序列s ，s ：，并且不允许，s i 中对应的列同时为“一”。 所有比对方法都是将序列间残基的相似与不相似转换成数值后进行比较，即给相同 或相似的残基对赋以正分，对不同的配对进行罚分。同时，对于相似度很高的序列来说， 基因序列发生插入删除的情况是较少的，所以对于以寻求序列间最大相似度为目的序列 比对来说，应当尽量减少空位的数目。因此，除了对替换进行罚分以外( 替换降低了相 似程度) ，对插入空位也要进行罚分。然后再计算总得分。所以，为了评价一个比对质 量的优劣，需要定义一个计算比对得分的适当的目标函数。一种常用的目标函数定义如 下： 工 跏陀。锄) = 盯“s ：，) ( 2 1 ) 其中函数盯 ，y ) o ，) ，r ) 是一计分函数，表示残基对( x ，y ) 比较时的得分，以下是最 简单的一种： f 2x _ y r 仃 ，) ，) 一 一1工y r ( 2 2 ) i 一2 工罩一d r _ ) ，l 一 对于序列s ，s ：，在它们的所有比对结果中，取得最大d 陀o f f 朋) 分值的比对就是 最优比对。 例如假设有两条序列分别为： s l = “a r g g c 姗” s 2 = “ m c g t a g t ” 它们的一种比对结果是： 8 序歹0 s ：a t g g c tatga 序列s ：a t g c g tagtg 22211z 2- 222 - 1 兜d r p 口她弘) = 2 + 2 + 2 1 1 + 2 + 2 2 + 2 2 1 = 5 序列比对的任务就是在序列之间的所有比对当中，找到取得最大比对得分的最优比 对。一般来说，最优比对就是两个序列匹配( 相同) 字符数目最多的情况。 这样，具有生物学意义的双序列比对问题就成为了如下的优化问题： 罂a 圣d ，e 似f 切) l i z 积 一。 其中r 表示序列s ，是的所有可能比对的集合。 2 2 3 序列比对的分类 从不同的角度考虑，序列比对可以被分为不同的种类： ( 1 ) 从一次性参加比对的序列的数目考虑，可分为双序列比对和多序列比对。 双序列比对( p a i 州v i s es e q u e n c e 烈i 驴m e n t ) ：两个d n a 或蛋白质序列进行的比对； 多序列比对( m u l t i p l es e q u e n c e i 鲫m e n t ) ：三个或三个以上的d n a 或蛋白质序列进行 的比对。 双序列比对是为了找出两个序列之间的最大相似性匹配，用于对两条序列进行同源 性分析，是多序列比对和数据库搜索的基础。动态规划算法是最为经典的双序列比对算 法。 多序列比对可以用来区分一组序列之间的差异，或者描述一组序列之间的相似性关 系，以便了解一个基因家族的共同特征，以及定量估计序列间的关系，由此推断它们在 进化中的亲缘关系。多序列比对的计算量非常大，传统的动态规划算法在三个以上的序 列比对当中很难实现，一般采用渐进式算法或迭代算法。 ( 2 ) 根据对序列进行相似度比较的范围，可分为全局比对和局部比对。 全局比对是对整个序列进行的比对，反映的是序列在全长范围内的相似程度：局部 比对是对序列的子序列进行的比对，反映的是序列在局部范围内某些片断的相似程度。 局部比对的生物学基础是蛋白质功能位点往往是由较短的序列片段组成的，这些部 位的序列具有相当大的保守性，尽管在序列的其它部位可能有插入、删除或替换。此时， 局部相似性比对往往比全局比对具有更高的灵敏度，其结果更具生物学意义。 ( 3 ) 根据序列比对结果的精确度，可分为精确比对和近似比对。 精确比对算法每次都可以找到序列之间的最优比对，而近似比对算法则不一定每次 都能找到最优比对，可能只找到了近似最优的比对 一般都希望得到精确的比对结果，但有时这样做可能要耗费大量时间，对机器性能 9 要求也很高，难以实现。在效率占主要位置，而对结果的要求可以不非常精确的场合， 比如在序列的数据库搜索中，近似结果是允许的。现在比较流行的数据库搜索算法 f a s 俄，b l a s t 就不能保证找到最优的比对。在多序列比对中，精确比对算法的代价很 高，主要也是采用近似比对算法。 传统的动态规划算法，总是可以找到序列之间最优比对，是一种精确的比对算法。 它在双序列比对中的应用非常有效，但在多序列比对方面由于计算量非常巨大而难以实 现。 很多优化算法都是近似比对算法，它们不一定每次都能找到最优解。但这些算法收 敛速度快，内存需求量较低，效率较高。因此，在序列比对算法的研究中，优化算法受 到了越来越多的关注“”o “。 2 2 4 空位罚分 在进行序列比对时，如果考虑到插入与删除事件发生的可能性，我们有时可能需要 通过插入空位( g a p ) 使其具有最佳匹配。序列比对中确定空位的过程十分复杂。最简 单的办法是通过不加限制地插入空位的办法获得相同残基的最大匹配数。但是如果对引 入空位不加限制，所得的比对结果即使分值较高，也缺乏生物学依据。因此，必须有一 种机制，对空位的引入加以限制。常用的方法就是空位罚分。 对含有空位的比对打分时，空位罚分( g a pp e n a l t y ) 就必须包含到打分函数中。公 式( 2 2 ) 是最简单的计分方法，它只是简单地将空位罚分设定为一2 。 使用简单空位罚分对两条序列进行比对时，经常能找到若干个同是最优的比对。进 一步区分这些比对的方法是找出哪些比对包含较多的不连续空位，哪些比对包含数量较 少而长度较长的空位片段。这是因为在生物进化过程中，多联核苷酸的插入删除事件相 对于单个核苷酸来说会较经常发生。考虑到竞争假说，从定义上讲，那些不可能事件出 现最少的比对就最可能是正确的比对。统计结果表明，两条序列长度上的差异更可能是 单个三联核苷酸的插入删除事件导致的，而多个不连续核苷酸插入删除的可能性较小。 比起那些在非空位位点间加入新空位序列的比对来讲，具有较长连续空位的比对更能体 现进化的观点，所以建立比对打分函数偏向于通过降低空位罚分来奖励后者。空位罚分 也因此被分为两部分：由序列中产生新空位串引起的起始罚分( o r i 舀n a t i o np e n a l t y ) 和 根据缺少的字符数而定的长度罚分( 1 e n 垂hp e a l t y ) 。 现在，我们将在单个序列中任意连续的尽可能长的间隔称为一个空位，用撑印口c 嚣来 表示在空位中的间隔( _ ) 个数称为空位的长度，用撑g ? 眇来表示序列中空位的个数。 则通常的空位罚分函数( 又称为仿射空位罚分) 可表示为： 只明口砂一- 魄p g 印s ) + 胁件印4 c 部) ( 2 3 ) 其中砌l 口缈为空位的总罚分，w 留表示为初始化一个空位的罚分，腑表示空位延伸一 1 0 个间隔的罚分。 2 2 5 打分矩阵 正如空位罚分可以奖励与进化最相关的比对，失配罚分也可以用来进一步区分相似 比对。简单的计分函数，如公式( 2 2 ) ，只反映了序列中碱基相同和不相同两种匹配情 况，但事实上序列中某些替换比其他替换要常见的多。因此，在为比对打分时，我们可 能更倾向于给常见的替换相对应的比对位点多些奖励，而对于不常见的替换则相反。 一旦核苷酸或氨基酸残基可能的两两比对得分都确定了，那么我们就得到了用来为 比对中每个非空位位点进行评分的打分矩阵( s c o r i n gm a t r i x ) 。 对于核苷酸序列的比对，打分矩阵一般很简单，表2 1 显示了一种典型的d n a 打分 矩阵。它对于匹配的核苷酸打分不高，对于转换( t r a n s i t i o n ) 嘌呤与嘌呤的替换 或嘧啶与嘧啶的替换，罚分也很少，但是对于颠换( t r a n s v e r s i o n ) 嘌呤替换成嘧 啶或者反向的替换，罚分却很严厉。 表2 1 转换一颠换矩阵 atcg al一551 t一51 一l 一5 c一5 115 gl一55l 为由2 0 种氨基酸组成的蛋白质序列的比对设计打分矩阵就复杂多了，要考虑若干个 因素。化学物理的相似性以及替换率是最常见的两个。基于相似度的矩阵可以根据残 基的物理、化学以及遗传编码的相似度来得到，而其存在的问题便是如何将以上各种打 分原则统一到一个单独且有意义的矩阵中。 为了得到打分矩阵，更常用的方法是统计自然界中各种氨基酸残基的相互替换率。 目前基于统计替换率的两个常用打分矩阵是p a m 和b l o s u m 。 p a m 矩阵( p o i n ta c c e p t e dm u t a t i o np e r1 0 0r e s i d u e s ) 基于单点可接受突变概 念“。对于p a m l ，就是每1 0 0 个残基发生1 次替换。p a m 一1 矩阵中的概率值回答了如 下一个问题：“假设在t 时刻给定一个多肽序列m ，于是开始观察序列中的进化动态，在 t + n 时刻，整条序列有1 的残基发生了替换。我们称此时的序列叫m 。那么序列m 中 j 类残基被替换成序列m 中i 类残基的可能性是多少? ”这个问题的答案可以根据 p a m 一1 矩阵的元素r 。得到。将p a m 一1 矩阵与自身相乘，我们可以近似得到高阶p a m 单位 的替换率。p a m 一1 矩阵适于用来比较亲缘关系非常近的序列，而p a m 一1 0 0 0 矩阵可以用来 比较亲缘性非常远的序列。实践中用的最多的且比较折衷的矩阵是p a m 一2 5 0 b l o s u m 矩阵也是通过统计相似蛋白质序列的替换率而得到的“。在b l o s u m 中，通 过统计聚类技术来对相关蛋白质的无空位比对进行分类，并且计算类间的替换率。与p a m 矩阵类似，可以根据亲缘关系的不同来选择不同的b l o s u m 矩阵进行序列比较。然而， b l o s u m 矩阵的阶数的意义与p a m 矩阵正好相反。换句话说，低阶p a m 适合用来比较亲缘 较近的序列，而低阶b l o s u m 矩阵更多是用来比较亲缘较远的序列。 2 3 基于动态规划的序列比对算法 2 3 1 动态规划算法 动态规划算法“”的基本思想是：将待求解的问题分解成若干个相互联系的子问题， 先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在 第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案， 不必重新求解。 动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性 质和子问题重叠性质： ( 1 ) 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称 该问题具有最优子结构性质( 即满足最优化原理) 。最优子结构性质为动态规划算法 解决问题提供了重要线索。 ( 2 ) 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时， 每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是 利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在 一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结 果，从而获得较高的解题效率。 2 3 2 用动态规划算法进行序列比对 序列比对问题具备应用动态规划算法进行求解的两个重要性质，因而非常适合用动 态规划的思想进行求解。 给定两条序列s 、t ，动态规划算法不是直接确定s 和t 的整体相似性，而是建立在 确定两个序列任意前缀的相似性上。是从最短前缀开始，利用先前的计算结果求解更大 前缀的相似性。基本思想是：使用迭代方法计算出两个序列的相似分值，存于一个得分 矩阵中；根据这个得分矩阵，回溯寻找最优的比对序列。具体过程如下： 假设序列s 和t 的长度分别为m 和开，s 【1 。埘】和z 【1 。j l 】表示s 和t 的全长序列； s 【1 。】和r 【1 j 】( 1 s f 历，1 s ，n ) 表示s 和t 的由前l 和前，个字符组成的前缀子序列。 首先，我们要构建一个大小为+ 1 ) o + 1 ) 的得分矩阵。矩阵中的元素 m f ，州0 s l 肼，0 sjs 玎) 记录了前缀子序列s 【1 】和h 1 j 】的最优比对得分。则根据递 归关系，m 【小，州就是s 和t 的最优比对得分。 1 2 为确定矩阵中各个兀素的值，我们百先萤对矩阵和第一行和第一歹u 的僵迸仃初始化。 因为它们表示的是一个子序列同空字符序列的比对分值，所以可以初始化为： m 【o o 】= o m 【f ，o 】= 荟岱阵】，一) ( 1 s fs m ，1 s ，s 门) ( 2 4 ) 肘m 2 荟盯( 一，啦】) 要得到非空子序列s 【1 。j 】和r 【1 门之间的比对，只有如下三种选择： ( 1 ) 研f 】与一个空位的匹配得分，加上s 【1 。j 一1 】和r 【1 ，】的最优比对得分； ( 2 ) ， 与一个空位的匹配得分，加上s 【1 j 】和r 【l j 一1 】的最优比对得分； ( 3 ) 研f 】和研，】的匹配得分，加上子序列研1 。j 一1 】和r 1 j 一1 】的最优比对得分。 如图2 3 所示： 图2 3 矩阵元素m p ，力的得分来源 因此最优比对得分m 【f ，】应由下面的递归关系式来确定： f 膨【f 一1 ，j 】+ 丁( s d 】，一) m p ，j 】= m a x m 【f ，一1 】+ ( ，( 一，研力) ( 1 s f s m ，1 s ，s 以) ( 2 5 ) i f f 一1 ，一1 】+ ( r ( s f 】，z 【力) 采用公式( 2 3 ) ，( 2 4 ) ，我们可以计算出得分矩阵所有元素的值。当计算到右下角元 素m 【m ，n 】时，就得到了序列s 和t 的最优比对得分。 接下来，我们就可以根据得分矩阵，采用回溯技术来构造最优比对。 回溯算法从矩阵右下角的元素开始，直到到达矩阵左上角的元素时结束，得到的两 条序列就是最优比对。 回溯函数如下所示，其输入参数为s 、t 与m 。其中s 和t 分别表示待比对的两条 序列，m 为预先计算出的得分函数。 f u n c t i o n 舢蜘 i n p u t ：s e q u e n c es 姐dt a m ym o b t a i n e db yt h ea b o v ef o 珊u l a e i = m ； j = n ； l e n = 0 ： w