（计算机软件与理论专业论文）蚁群算法在生物序列比对中的应用.pdf

摘要 摘要 序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推 断基因的结构、功能和进化关系。 蚁群算法是一种新型的模拟进化算法，它通过模拟蚁群在觅食过程中寻找最 短路径的方法来求解优化问题，目前在旅行商问题等组合优化问题中有成功的应 用。 本文在分析了国内外序列比对算法的发展状况的基础上，将蚁群算法应用于 序列比对，针对序列比对的特点进行改进，提出了基于蚁群算法的序列比对算法， 并应用该算法进行d n a 序列和蛋白质序列的比对，通过实验证明了该算法的可行 性和有效性。 根据蚁群算法易于陷入局部最优解的缺陷，本文提出了一种改进算法，它根 据人工蚂蚁搜索到的解，自适应地调整信息素的增量，使得算法不易陷入局部最 优解，扩大了搜索空间，增大了收敛到全局最优解的可能性。实验结果表明改进 算法可以明显改善比对效果。 关键词：蚁群算法，序列比对，信息素 a b s t r a c t a b s t r a c t s e q u e n c ea l i g n m e n t i st h eb a s e m e n to fb i o i n f o r m a t i c s w i t ht h ew e a l t ho f s e q u e n c e i n f o r m a t i o no b t a i n e dt h r o u g hs e q u e n c ea l i g n m e n to n ec a l li n f e r st h es t r u c t u r e ，f u n c t i o n a n de v o l u t i o n a r yr e l a t i o n s h i po f g e n e s a n t c o l o n ya l g o r i t h mi san o v e ls i m u l a t e de v o l u t i o n a r ya l g o r i t h m ，w h i c hi su s e dt o s o l v et h eo p t i m i z a t i o np r o b l e m st h r o u g h s i m u l a t i n gt h ew a y o fa n t sf i n d i n gt h es h o r t e s t p a t h f o rf o o d t h i s a l g o r i t h m h a sb e e n a p p l i e ds u c c e s s f u l l y t oc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m ss u c h a s t r a v e l i n gs a l e s m a np r o b l e m i nt h i sp a p e r , a n tc o l o n ya l g o r i t h mi s a p p l i e dt os e q u e n c ea l i g n m e n tb a s e do nt h e s t u d y o ft h e d e v e l o p m e n to fs e q u e n c ea l i g n m e n t an e wa l g o r i t h m f o r s e q u e n c e a l i g n m e n tb a s e do na n tc o l o n ya l g o r i t h mi sp u tf o r w a r da n di si m p r o v e df o ra d a p t i n gt o i t sn e wa p p l i c a t i o n t h i sn e w a l g o r i t h mi sa p p l i e dt od n as e q u e n c ea l i g n m e n ta n d p r o t e i ns e q u e n c ea l i g n m e n ti nt h ee x p e r i m e n t t h er e s u l t so fe x p e r i m e n td e m o n s t r a t e t h a tt h en e w a p p r o a c h i sr e a s o n a b l ea n de f f i c i e n t a c c o r d i n gt ot h el i m i t a t i o no fr u n n i n gi n t ol o c a lo p t i m u mi na n tc o l o n ya l g o r i t h m ， a ni m p r o x 7 e d a l g o r i t h m ，w h i c hi s b a s e do na d a p t i v e l ya d j u s t i n gt h ei n c r e a s eo ft h e r o u t e s p h e r o m o n ea c c o r d i n gt ot h es o l u t i o n st h a ta r t i f i c i a la n t sh a v ef o u n d ，i sp r o p o s e d t h i sm e t h o dw i l ln o te a s i l yf a l li nt h el o c a lo p t i m u m ，t h u si t c a r le x p a n dt h es e a r c h s p a c ea n di n c r e a s et h ep r o b a b i l i t yo f c o n v e r g i n ga tt h eg l o b a lo p t i m u m t h er e s u l t so f e x p e r i m e n ts h o wt h a tt h ei m p r o v e da l g o r i t h mc a na c h i e v eb e t t e rp e r f o r m a n c et h a nt h e b a s i ca n t c o l o n ya l g o r i t h md o e s i ns e q u e n c e a l i g n m e n t k e y w o r d s ：a n tc o l o n ya l g o r i t h m ，s e q u e n c e a l i g n m e n t ，p h e r o m o n e 创新性声明 y 5 8 3 4 0 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：錾叠!日期! ! 竺竺 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名 望筮 星! 兰兰 日期! ：! 兰竺! - 歹 日期丝! 生：竺 第一章绪论 第一章绪论 1 1 生物信息学 2 1 世纪是信息科学，生命科学的时代。随着人类基因组计划的实施，有关核 酸，蛋白质的序列和结构数据呈指数级增长，运用计算机对其进行分析是必然的 趋势。从2 0 世纪8 0 年代末开始，生物信息学( b i o i n f o r m a t i c s ) 开始了蓬勃地发展。 生物信息学是分子生物学，计算生物学，计算机科学，应用数学和信息技术 等学科交叉和融合形成的一门新兴学科，它是应用计算机和信息技术搜集，储存， 分析和整理各种生物医学信息，并予以管理和利用的一门科学。生物信息学主要 包括以下几个研究领域： ( 1 ) 序列比对( s e q u e n c e a l i g n m e n t ) ：比对两个或两个以上的符号序列的相似性 或不相似性，它是生物信息学的基础。 ( 2 ) 结构比对：比较蛋白质分子空间结构的相似性或不相似性。 ( 3 ) 蛋白质结构预测：包括2 级或3 级结构预测，主要是预测和研究蛋白质的 结构和折叠过程。 ( 4 ) 计算机辅助基因( 蛋白质编码基因) 识别：在给定基因组序列后，正确识别 基因的范围和基因组序列的精确位置。 ( 5 ) 分子进化和比较基因组学：利用不同物种中同一基因序列的异同来研究生 物的进化，构建进化树。 ( 6 ) 基于结构的药物设计：研究约1 0 万种人的蛋白质的结构、功能、相互作 用以及与各种人类疾病之间的关系，寻求治疗和预防方法，包括药物治疗。 ( 7 ) 生物信息数据库的设计于实现；建立数据库对大量的生物信息数据资源进 行管理和维护，以便做进步的分析、处理和利用。 ( 8 ) 其它：如基因表达谱分析，基因芯片设计和蛋白质组学数掘分析等。 可以看出，生物信息学的研究内容包括生物学数据的搜索、处理和利用，各 种算法的理论研究，相关软件的开发和研制等。它从核酸和蛋白质序列出发，分 析序列表达的遗传结构和功能信息，以解释和认识生命的起源、进化、发育和遗 传的本质，破译隐藏在序列中的遗传语言及其意义。此外，它也研究分析同人体 细胞、组织和器官的生理、病理、药理过程相关的各种生物信息，为人类疾病的 预测、诊断、预防和治疗提供有效的途径。 在国外，生物信息学的研究起步较早。美国在2 0 世纪6 0 年代就丌始建立用 手工搜索的蛋白质数据库。1 9 7 9 年美国洛斯阿拉莫斯国家实验室开始建立核酸序 蚁群算法在生物序列比对中应用 列数据库g e n b a n k ，现在由1 9 8 8 年成立的美国国家生物信息中心叫c b i ) 管理和维 护。1 9 8 2 年欧洲分子生物学实验室的e m b l 数据库开始提供服务，随后又建立了 欧洲分子生物学网( e m b n e t ) 。1 9 9 4 年开始e m b l 数据库由建在英国剑桥的欧洲生 物信息研究所( e b i ) 管理。1 9 8 4 年日本着手建立国家级核酸数据库d d b j ，1 9 8 7 年 正式对外服务。目前绝大部分核酸和蛋白质数据有美国，欧洲和日本三家产生， 以上三家共同组成了d d b 】，e m b l ，g e n b a n k 国际核酸序弼数据库2 4 小时交换数 据，同步更新口1 。其他国家如德国，法国，意大利，澳大利亚，丹麦，以色列等， 在分享网络资源的同时还纷纷建立自己的生物信息中心，为本国的科研服务。 我国对生物信息学的研究始于2 0 世纪末。1 9 9 9 年3 月，清华大学生物信息研 究所，国家人类基因组北方研究中心和北京生物技术和新医药产业促进中心共同 举办了“北方生物信息学学术研讨会”。1 9 9 9 年4 月，北京大学举办了“国家生物 信息学讲习班”。2 0 0 0 年1 1 月，中国科学院和华大基因中心举办了“北京生物信 息学研讨会”。目前北京大学生物信息中心建立了7 0 多种分子生物信息镜像系统 和数据库，有些数据库可以每同更新。中国科学院上海生命科学研究所建立了我 国核酸序列公共数据库。广州中山大学生物信息中心开通了法国巴斯德亚洲信息 网。总的来说，国内在生物信息学上的研究尚处于起步阶段。 1 2 序列比对算法的发展 序列比对( 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 或蛋白 质序列进行比较，找出它们的最大相似性匹配1 3 j 。经过多年的研究。比对算法已经 形成了比较成熟的体系，探索出了许多有效的算法。 点阵 虱( d o t p l o t ) 是双序列比对的基本方法。1 9 7 0 年g i b b s 和m c i n t y p e 采用矩 阵点阵图方法寻找序列中的相似匹配片断【4 1 。 1 9 7 0 年n e e d l e m a n 和w u n s c h 提出了基于动态规划思想的双序列比对算法 5 l ， 该算法的比对结果反映了两个序列中所有碱基的整体相似性。 1 9 8 1 年s m i t h 和w a t e r m a n 基于仿射空位罚分模型开发了局部比对算法，使得 动态规划比对算法能够寻找两条序列当中的局部高相似度片断1 6 】。 第一章绪论3 1 9 7 5 年，h i r s c h b e r g 根据分治策略提出一种基于动态规划算法的改进算法， 降低了空间复杂度，但远行时间增加了，这实际上是一种以时间换取空间的策略l _ ”。 基于此种考虑，c h a r t e r 和s c h a e f f e r 所提出的f a s t l s a 算法则在降低空间复杂度和 减少远行时间上进行了权衡j 。 1 9 7 8 年，d a y h o f f 等人在研究蛋白质序列的进化后，建立了队m 替换矩阵1 9 j 。 1 9 9 2 年，h e n i k o f f 等人将后来被广泛采用的b l o s u m 替换矩阵引入比对算法【l 。 对新发现的序列需要在核酸或蛋白质数据库中进行相似性搜索，寻找与之相 似的己知序列，通过己知序列推断新序列的结构和功能。f a s t a 和b l a s t 目前最为 著名的两个搜索算法，它们都是基于局部相似性的算法。f a s t a 算法是由p e a r s o n 和l i p m a n 于1 9 8 5 年提出的，他们开发了快速比对软件包，可以在d n a 、蛋白质数 据库中进行查找 1 0 , 1 1 1 。而b l a s t 算法则是由a l t s e h u l 等人于1 9 9 0 年提出【1 3 】，并 成为数据库搜索中最流行的工具为基于公共服务器的数据库搜索带来了革命性 的转变。此后经过改进b l a s t 允许空位的插入【i ”。而u m b l a s t 工具包可以从查到 的大量序列中过滤掉没有意义的序列i l ”。 近年来，将优化算法应用于序列比对的研究逐渐多了起来。 m o l o g n i 和s h i n o d a 提出一种用遗传算法进行双序列比对的算法，将一批序列 比对结果组成初始种群，选择较为优秀的比对结果进行复制，并利用交叉和变异 算子产生下一代种群，通过多代进化，收敛到最优比对结果1 1 6 】。c e d r i c ，e m m e t 和d e s m o n d 于1 9 9 7 年提出了一种应用于多序列比对的遗传算法，并实现了基于该 算法的软件包r a s a l ”j 。 模拟退火算法是一种适合于求解大规模组合优化问题的算法。用该算法求解 序列比对问题是优化算法在该领域的一种尝试，比如2 0 0 2 年梁爽等人描述了用于 多序列比对的模拟退火求解方法8 1 。 1 3 蚁群算法概述 过去，人们对蚂蚁的关注大多是关于“蚂蚁搬家，天要下雨”这样的民谚。随 着现代仿生学的发展，人 f 逐渐对它产生了浓厚的研究兴趣。 蚂蚁这种群居昆虫。虽然单个个体的行为十分简单，但是由其组成的群体却 能完成比较复杂的活动，比如可以找到从巢穴到食物源的最短路径，这种群体智 能特性引起了科研工作者强烈的兴趣。经过研究，人们提出了模拟蚂蚁寻找最短 路径的行为的蚁群算法。 蚁群算法在许多组合优化问题( 如旅行商问题) 当中有较深入的研究，在电信路 由管理，经济运作管理，道路交通管理方面都有许多成功的应用。 下面是蚁群算法的仿生学原理： 蚁群算法在生物序列比对中的应用 仿生学家发现，每只蚂蚁在走过的路径上会留下一种称为信息素( p h e r o m o n e ) 的化学物质，蚂蚁之间就是靠感知这种物质的浓度进行信息传递的。蚂蚁倾向于 朝浓度高的方向移动。这样就形成了一种正反馈机制：由于外激素会随着时间的 流逝而挥发，蚂蚁在短路径上往返耗时少，信息素还没挥发完又有新的留下来， 因而短路径上的信息素浓度高于长路径，从而吸引更多蚂蚁选择短路径，然后又 留下新的信息索，如此反复，造成最短路径上的信息素浓度高于其他路径，随着 时间推移，整个蚁群最终聚集到最短路径上。图1 1 显示了这一过程。 图1 1蚂蚁选择路线的过程 图a 显示蚂蚁从巢穴a 经过一条通路前往食物源e 。图b 显示如果这条通路 上出现了障碍物时，蚂蚁在位置b 要选择行进的方向。刚开始路线b h d ，b c d 上的 信息素浓度为零，因此蚂蚁选择两条路线的概率是一样的，因此两条路线上的蚂 蚁数目相当。图c 显示。由于b c d 路线比b h d 路线距离短，蚂蚁往返耗时较少， 留下的信息素较多，随后赶来的蚂蚁在位置b 选择路线b c d 的概率比选择b h d 的 概率大，所以b c d 路线上的蚂蚁数目逐渐增多。最终，蚂蚁会放弃b i d 路线而全 部选择b c d 路线j 。 人工蚁群算法模拟了这一过程，该算法的思想是：用蚂蚁的行走路线表示待 求解问题的可行解，每只蚂蚁在解空间中独立地搜索可行解，解的质量越高，在 “行走路线”( 即可行解) 上留下的信息素也就越多，随着算法的推进，代表较好 的解的路线，其上的信息素逐渐增多，选择它的蚂蚁也逐渐增多，最终整个蚁群 在正反馈机制的作用下集中到代表最优解的路线上，也就找到了最优解。 1 4 本文主要内容 蚁群算法经典的应用是解决组合优化问题，国内外有很多关于蚁群算法求解 旅行商( t s p ) 问题的研究。 本文在研究了生物序列比对的发展现状，以及蚁群算法的特性之后，尝试将 第一章绪论5 蚁群算法应用到序列比对当中，并根据序列比对的特点对算法进行改进，提出了 用于求解序列比对问题的蚁群比对算法，并对d n a 序列，蛋白质序列做了比对实 验。根据蚁群算法容易陷入局部最有解的缺陷本文提出了用动态自适应调整信 息素的方法对基本蚁群比对算法进行改进，实验结果说明改进的蚁群比对算法能 够明显地改善比对效果。 文章的内容安排如下： 第一章简要介绍了生物信息学的背景，序列比对算法的发展概况，以及蚁群 算法的仿生学原理。 第二章对生物序列比对问题进行了详细介绍，包括序列比对的定义、数学模 型、空位罚分和替换矩阵的使用，经典比对算法的原理等内容。 第三章介绍了蚁群算法的原理、特性和应用，并根据旅行商( t s p ) 问题对蚁群 算法的设计思想进行了详细介绍。 第四章阐述了蚁群算法求解序列比对的算法模型，详细介绍了蚁群比对算法 的设计，实现过程和序列比对的实验结果。 第五章介绍了自适应蚁群比对算法，阐述了蚁群算法易于陷入局部最优解的 缺陷和克服的方法，以及改进算法进行序列比对的实验结果。 第二章生物序列比对7 第二章生物序列比对 2 。1 生物学背景知识 2 i 1 遗传信息的传递与表达 科学家们发现在生物细胞核中存在大量的酸性大分子物质：脱氧核糖核酸 ( d e o x y r i b i o n u c t e i ca c i d ，简称d n 舢，核糖核酸( r i b i o n u c l e i ca c i d ，简称r n a ) 。这 两种大分子在组成上十分相似，它们都是由“磷酸”，“脱氧核糖”或“核糖”，以 及“有机碱”组成的。此外，细胞核中还存在大量的蛋白质。这三种生物大分子 中只有d n a 的含量十分稳定，是遗传的物质基础。 d n a 是一种高分子有机化合物，它的基本单位是脱氧核苷酸。脱氧核菅酸由 三部分组成：磷酸、脱氧核糖和含氮碱基。d n a 分子是由很多不同的脱氧核苷酸 组成的多脱氧核苷酸链。图2 1 显示了d n a 的双螺旋结构。脱氧核椿与磷酸相间 排列在外侧，形成两条主链，构成d n a 的基本骨架。两条主链之间的横档是碱基 对，排列在内侧。相对应的两个碱基通过氢键连接形成碱基对，把两条主链连接 起来。共有四种碱基：腺嘌呤、胸腺嘧啶、鸟嘌呤、胞嘧啶，分别用a 、t 、c 、 g 表示。碱基配对有一定的规律：a 与t 配对，c 与g 配对。 图2 ，1d n a 分子的双螺旋结构 d n a 分子可以在解螺旋酶的作用下使双链分离，再将每条单链作为一个模 板，在聚合酶的作用下，按碱基配对的规律合成两条新的双螺旋结构，就完成了 d n a 分子的复制。 现代遗传学的研究认为，生物的性状是由基因控制的。基因是遗传物质的功 能单位和结构单位，是具有遗传效应的d n a 片断。比如：茉莉红花基因控制红花 性状，开红花，豌豆白花基因控制白花性状。开白花。每个基因含有成千上万个 脱氧核苷酸，其排列顺序就决定了生物性状的显现，蛋白质是形成生命体的基本 8蚁群算法在生物序列比对中的应用 物质，生物的性状主要是由蛋白质来体现的，我们能吃出牛肉和鸡肉味道的不同 就是因为它们的蛋白质结构不同，因而体现了各自不同的性状。而基因控制性状 就是通过控制蛋白质的合成来实现的。 d n a 双链中的一条单链可以作为模板，按照碱基互补配对的原则合成r n a ， 这个过程称为转录。转录的过程如下： d n a t - a ，c c - g a a g - a l | liiji r n a a u g g c - u u c u 图2 2d 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 。在细胞质当中。以m r n a 为模板，就可以合成具有一定氨基酸顺 序的蛋白质，这个过程称为翻译。组成蛋白质的2 0 种氨基酸可以用2 0 个字母表 示，包括a 、r 、n 、d 、c 、q 、e 、g 、h 、1 、l 、k 、m 、f 、p 、s 、t 、w 、y 和v ：m r n a 中每三个相邻的碱基( 称为密码子) 决定了一种氨基酸，比如：c t t 就决定了“亮氨酸”( 用字符l 表示) 的合成。遗传信息通过如图2 3 显示的过程就 完成了传递和表达。 转录翻译 d n a 片断( 基因) - r n a + 一定的蛋白质结构( 性状) 图2 3 遗传信息的传递和表达 因此归根结底，决定生物性状的遗传信息是由d n a 的脱氧核营酸的排列顺序 确定的，d n a 有两个基本功能：( 1 ) 复制：在生物的传宗接代中传递遗传信息：( 2 ) 表达：在后代个体发育中，将遗传信息表达为与亲代相似的性状。 2 1 2 物种进化与基因突变 生物物种在千万年来不是一成不交的，而是随着时间、环境的变化不断进化 的。这种进化反映在基因上就是基因的脱氧核苷酸序列的排列顺序发生了改变。 当基因通过突变使它的脱氧核苷酸序列( 简称基因序列) 发生改变时，由其控制 合成的蛋白质也发生改变，所表现出来的生物性状也就发生了改变。生物物种的 多样性就是由基因排列的多样性决定的。适应环境的性状改变使得物种得以生存 和发展，不适应环境的性状改变使得物种被淘汰，灭绝。生物物种就是在这样的 作用下不断进化，形成了自然界千姿百态的物种。 如果把基因序列抽象为字符的排列，在一些位置上，一条序列相对另一条序 列可能多出一些字符，也可能少了一些字符，或者某些字符被其他字符替换了。 第二章生物序列比对 9 这三种情况分别被称之为“插入”、“删除”和“替换”。基因序列的突变可以用这 三种情况来概括： 原基因序列：t a c c g a a g a 插入：1 a c c g g a a g a 删除：1 a c c g a a a 替换：t a c g g a a g a 由同一个祖先经过进化而产生的两个物种，它们在生物性状上会有一些相似 之处，这反映在基因水平上就是基因序列的排列具有一定的相似性。亲缘较近， 序列排列的相似度就高，亲缘较远，序列排列的相似度就低。反过来，我们也可 以推想，基因序列排列相似度高，说明这样的序列有可能是同源的，即它们可能 是由同一个祖先进化而来的；而排列相似度低，则可能不是一个祖先进化而来的。 2 2 1 序列比对的目的 2 2 生物序列比对 我们可以通过对序列之间相似性比较来推断不同物种之间的进化关系。如果 两个序列具有足够的相似性，则可以认为两者具有同源性，那么它们的生物性状 会存在很大的相似性，如果我们知道其中一个物种的基因序列所决定的生物功能 信息，就可以推断另一个物种的基因序列所决定的生物功能信息。 因此，将未知序列同已知序列进行比较分析，进而了解未知序列的生物信息 的方法已成为一种强有力的研究手段，这使得我们可以从核酸以及氨基酸的层次 上去分析序列的相同点和不同点，从而推测它们的结构、功能以及进化上的关系。 最常用的比较方法是序列比对。序列比对是指通过一定的算法，对两个或多个用 确定字符表示的d n a 或蛋白质序列进行比较，找出它们的最大相似性匹配。 基因突变共有三种情况：插入、删除和替换。如果从前一条序列中插入一个 字符可以得到后一条序列的话，那么从后一条序列中删除相应的字符也可以得到 前一条序列。一般很难确定是从前一条序列插入了一个字符，还是从后一条序列 当中删除了一个字符。在序列比对问题的描述当中，我们把在序列中插入或删除 一个字符的情况用一个空位( 一) 表示。一般判断空位是插入还是删除造成的也 是比较麻烦的。因此，我们将插入和删除字符产生空位的情况台称为“插删 ( i n d e l ) ”，这并不影响最后的比对结果。图2 4 显示了插删和替换的情形。 序列s ：t a l c l c l q g 4 1 g a 序列t ：t 州g t q l g 州a i g a 图2 4 序列比对中的插删和替换 o蚁群算法在生物序列比对中的应用 替换和插删( 空位引入) 都会降低序列间的相似度，因此，我们可以规定一种计 分方法，序列对应位置上如果字符相同就加分，发生替换和插删就减分，将所有 的分数相加，根据分数高低判断序列的相似度。目前的序列比对一般都是基于这 样的计分方法实现的。 蛋白质序列也可以反映定的生物功能和结构信息，除了对基因即d n a 序列 进行比对外，对蛋白质序列进行比对也是序列比对的重要内容。经研究发现，蛋 白质序列比对的灵敏度较高，更容易发现亲缘关系较远的序列。 对于新发现的序列，需要在核酸和蛋白质序列数据库中进行相似性搜索，寻 找与之相似的已知序列，通过已知序列推断新序列的功能和结构信息。这是序列 比对晟广泛的应用和重要的分析方法。数据库搜索通过特定的相似性比对算法， 找出在序列库中与新序列具有一定相似性的序列，这些序列数量很多，可以根据 相似程度高低进行排序，这样可以找到最有可能同源的已知序列，进一步推断新 序列的功能和结构信息。 2 2 2 序列比对问题的描述 将d n a 序列和蛋白质序列抽象成为字符序列，我们就可以用数学方式描述序 列比对问题了。 下面给出和序列比对有关的一些定义： 【定义2 1 】序列s 是有限长度的字符串，序列中的字符由某个有限字符集 合q 确定。对于9 n a ，q = a ，c ，t ，g 。对于蛋白质，q 由2 0 种代表氨基酸的字符 组成。 【定义2 2 1 对序列s ，l s j 表示s 中的字符个数。s 【f 】表示序列的第i 个字 符。s 1 i 】表示序列的前f 个字符组成的子序列。 【定义2 3 】我们用“”来表示插入和删除所产生的空位。 【定义2 4 】对于x , y q u 一) ，定义a ( x ，y ) 为计分函数，表示x ，y 比较 时的得分，以下是最简单的一种： f 2x = y q c r ( x , j y ) = 一1 x y q ( 2 1 ) 【一2 x ：一，o r y ：r 一 【定义2 5 】s 和r 的个比对a 用序列s 和r 中字符的一一对应表示， 其中l 卅爿州，s 。t 去掉空格就是s 和r 。 【定义2 6 1 序列比对a 的得分为s c o r e ( 一) = 瞽a ( s 【f 1 ，r f 】) ，褥分越 高表示序列的相似程度越高。 【定义2 7 1 对序列s 和了，在它们的所有比对结果中，取得最大s c o r e ( 小分 第二章生物序列比对 值的比对就是最优比对。 如果采用以上的定义和公式( 2 1 ) 表示的计分函数，序列s = “t a c c g g a g a ” 和序列t = “t a g c g a a g a ”的一种比对结果是： 序列s ：ta c cg gaga 序列t ：tagcgaaga 22一l2222222 s c o r e ( a 1 22 + 2 - 1 + 2 - 2 + 2 + 2 - 2 + 2 + 2 = 9 序列比对的任务就是在序列之间的所有比对当中，找到取得最大比对得分的 最优比对。一般来说，最优比对就是两个序列匹配( 相同) 字符数目最多的情况。 穿列s 和t 的长度有可能不同，在比对过程中比对算法尝试将空位插入到s 或了当中，以表示插入或删除字符( 基因序列中的碱基) 。上面的比对结果可以理解 为，在第5 个位置s 中插入了字符g ，或r 中删除了字符g 。在第8 个位置s 中删 除了字符a ，或r 中插入了字符a 。在第一个位置是相同的匹配t 。在第三个位置s 中的字符c 被丁中的字符g 替换，从而形成了f 和丁的比对结果。 利用插入空位可以获得最优序列比对。比如下面的例子： 插入空位前： 序列l ( 待检序列) 序列2 ( 目标序列) 插入空位后； 序列1 ( 待检序列) 序列2 ( 目标序列) a g g v l i q v g iilii i a g g v l i q v g a g g v l i i q v g i ili | ii i a g g v l i q v g 圈2 5 利用插入空位的方法获得最优比对序列 对于相似度很高的序列来说，基因序列发生突变的碱基是较少的，因而插删 的情况是较少的，所以，对于以寻求序列间最大相似程度为目的的序列比对来说， 应当尽量减少空位的数目。因此公式( 2 1 ) 除了对替换进行罚分以外( 替换降低了相 似程度) ，对插入空位也要进行罚分，空位罚分根据实际情况有多种方案，比如公 式( 2 1 ) 中的空位罚分值可以是“1 ”或其它值。 2 2 3 序列比对的分类 ( 1 ) 双序列比对和多序列比对 双序列比对( p a i r w i s es e q u e n c ea l i g r t m e n t ) ：是指两个d n a 或蛋白质序列进行 的比对。多序列比对( m u l t i p l es e q u e n c ea l i g n m e n t ) ：是指三个或三个以上的d n a 1 2蚁群算法在生物序列比对中的应用 或蛋白质序列进行的比对。 双序列比对是为了找出两个序列之间的最大相似性匹配。用于对两个序列进 行同源性分析。是多序列比对的和数据库搜索的基础吼动态规划算法是最为经典 的双序列比对算法。 多序列比对可阱用来区分组序列之间的差异，或者描述一组序列之间的相 似性关系，以便了解一个基因家族的共同特征，以及定量估计序列间的关系，由 此推断它们在进化中的亲缘关系。多序列比对的计算量非常大，如果采用 n e e d l m a n w u n s c h 算法空间和时间复杂度都很高，巨大的计算量使得该算法变得 不切实际。传统的动态规划算法在三个以上的序列比对当中就很难实现了。一般 采用渐进式算法或迭代算法。 f 2 ) 全局比对和局部比对 全局比对是对整个序列进行的比对，反映的是序列在全长范围内的相似程度。 如果相似度高，说明序列之间可能具有同源性。局部比对是对序列的子序列进行 的比对，反映的是序列在局部范围内某些片断的相似程度口l 。 生物序列中某些重要的功能片断，往往比较保守，变异的概率很低，而序列 其他部分的变异概率相对较高，如果只强调全局比对，可能会漏掉些高招似度 的局部片断，而这些片断往往更有效地揭示了生物的同源关系。因此寻找这些高 分的局部相似片断就是局部比对的任务。 ( 3 ) 精确比对和近似比对 序列比对算法从比对结果来说可以分为精确比对和近似比对。精确比对算法 每次都可以找到序列之闯的最优比对。而近似比对算法则不一定每次都能找到最 优比对，可能只找到了近似最优的比对。 一般都希望得到精确的比对结果，但是这样做可能耗费大量时间，对机器性 能要求很高，难以实现。在效率占主要位置，而对结果的要求可以不非常精确的 场合，比如在序列的数据库搜索中，近似结果是允许的。现在比较流行的搜索算 法f a s t a ，b l a s t 就不保证找到所有或最优的比对，在数据库大量的序列中搜索 相似序列这样做对分析工作没有什么影响，但是搜索速度却加快了许多。在多 序列比对当中。精确比对算法代价很高，近似比对算法是非常有用的。 对于传统的动态规划算法，总是可以找到序列之间最优比对，这是一种精确 的比对算法。动态规划算法在双序列比对中的应用非常有效，但在多序列比对方 面由于计算量非常巨大而难以实现。 很多优化算法都是近似比对算法，它们不一定每次都能找到最优解。比如遗 传算法。模拟退火算法等。但是这些算法收敛速度快，效率较高。目前在序列比 对算法的研究当中，优化算法受到越来越多的关注，比如，遗传算法在解决多序 列比对问题中显示了很好的性能。 第二章生物序列比对1 3 2 2 4 空位罚分 序列比对算法都是基于某一种计分方法的，公式( 2 1 ) 是最简单计分方法，而 其它一些反映不同生物学意义的计分方法比公式( 2 1 ) 要复杂的多。 空位的引入反映了序列在突变过程中碱基插删的情况。插删可能只涉及一个 碱基，也可能涉及几个连续的碱基。空位的引入有时不仅要考虑它们的位置，空 位数目，还要考虑空位的长度，这和具体的应用场合有关。在一些罚分模型当中， 连续的插删操作的总罚分不等于单个插删操作的罚分的总和。 我们用# s p a c e 表示空格数，# g a p 表示空位数。以下是两种常用的空位罚分 方法： ( 1 ) 恒定空位罚分( c o n s t a n tg a p p e n a l t i e s ) ： 每个空位罚分w g ，则比对得分这样计算： s c o r e ( 一) = m a x 口( s 【f 】 t 【邝+ w g # g a p ( 2 2 ) ， ( 2 ) 仿射空位罚分( a f f i n eg a pp e n a l t i e s ) ： 对于长度大于1 的空位，给空位的第一个空格分配空位罚分w g ，称为“空位 设置罚分”，表示新增一个空位的成本，给后面的每个空格分配罚分w s ，称为“空 位扩展罚分”表示空位延伸一个空格的成本；对于长度等于1 的空位，就给这个 空格分配“空位设置罚分”。则比对得分这样计算： s c o r e ( a ) = m a x a ( s i l ，t 【，】) + w g # g a p + w s x # s p a c e ) ( 2 3 ) i 仿射空位罚分模型更容易反映序列比对的生物学意义。表2 1 说明了空位设置 ( g a po p e n i n g ) 和空位扩展( g a pe x t e n s i o n ) 对序列比对结果的影响。 表2 1空位设置罚分和空位扩展罚分的序列比对的影响 空位设置罚分位扩展罚分作用 极少插入或删除，适用于亲缘接 大大 近的蛋白质序列比对 少量较长空位插入，用于可能在 大小 整个功能域插入空位的情况 大量短的空位插入用于亲缘关 小小 系疏远的蛋白质序列比对 如果空位罚分与字符替换的罚分相比太大，那么比对结果中会极少出现空位； 如果空位罚分相对较小，那么比对结果中会出现大量空位，这样有可能找到高分 匹配，也可能因空位太多而得到低分匹配。 蚁群算法在生物序列比对中的应用 2 2 5 替换矩阵 计分方法中除了空位罚分外，最常见的就是替换矩阵。简单的计分函数，如 公式( 2 1 ) ，只反映了序列中的碱基相同和不相同两种匹配情况。这种只考虑碱基同 性的计分方法对于d n a 序列来说还算适合，但对于复杂的蛋自质序列来晚，碱 基之间除了相同和不相同外，还存在不同等级的相似程度，因此基于统计结果和 生物学意义的相似性矩阵就产生了。 比如蛋白质中某些氨基酸很容易相互取代而不改变其生化性质，我们称之为 保守替换。从试验和统计上也发现某些碱基替换的频率高于其它替换。因此需要 根据统计分析，构建不同的替换矩阵，相同碱基的匹配打分高于相似碱基的匹配， 保守替换的匹配打分高于非保守替换的匹配，出现概率高的匹配，打分也较高。 表2 , 2 一种核酸的替换矩阵 a1 3 6 g一3 71 3 6 c一1 6 0一1 6 01 3 6 t1 5 0一1 6 03 71 3 6 agct d n a 的替换矩阵相对简单，表2 2 显示了一种典型的d n a 替换矩阵，它是根据 碱基匹配出现频率的统计数据设计的。 拥有2 0 种氨基酸的蛋白质就复杂多了。目前最常用的两类替换矩阵是p a m 和 b l o s u m 。p a m 在发现全局比对时效果较好，丽b l o s u k f 在局部比对上作用更明显。 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 c e s ) 是从蛋白质模块数据库找出的 一组替换矩阵，用于解决序列远距离相关比对，如b l o s u m 5 0 ，b l o s u m 6 2 ，数字越 大关系越近。 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 进化距离对应残基突变的概率依照每1 0 0 个碱基中有一个可接 受的单点突变。将1 个p a m 迸化距离的矩阵多次自乘，可得到迸化距离较远的p a m 矩阵，如p a m l 0 0 ，p a t 2 5 0 ( 数字越大，进化距离越远) i9 1 。p a m 2 5 0 矩阵如表2 3 所示。 是不是全局比对算法一定产生全局最优匹配序列，局部比对算法定产生局 部最优匹配序列呢? 对于局部比对来说，如果选择的空位罚分太小。而替换矩阵 对序列碱基平均打分为正值时，容易因空位的过多加入使局部序列通过质量不高 的区域延伸，从而产生全局匹配。而全局比对也会在过重的空位罚分下，由于难 以产生空位，匹配序列不容易延伸而得出局部匹配的结果。因此应当谨慎的选择 计分方法，以求获得高质量的比对结果。 第二章生物序列比对1 5 表2 ，3p a m 2 5 0 矩阵 c1 2 s02 t2l3 p- 3lo6 a2l ll2 g3 l01 i5 n，4 101002 d500- l0i24 e50o- 100i34 q - 5 i- 100- l l224 h3一1 101221136 r40- l0230 11i26 k5o0- l- l- 2lo01035 m一52- l- 2i3- 23。2 120o6 i2io一2一1322222 2225 l632- 3243- 432233426 v 2- l010i22- 22- 2222424 f一4- 3t 3- 5- 45- 46 55 - 24 - 5o i219 yo3- 35- 352- 44- 4o44- 2 i127l o w82- 56- 6 7 47- 75323- 45- 26o o1 7 cstpag nde q hrkmilv fyw 2 3 用动态规划算法求解序列比对问题 2 3 1 动态规划算法的思想 动态规划算法( d y n a m i cp r o g r a m m i n g ，d p ) 是解决多阶段决策最优化问题的一 种算法，在这类问题中，可能会有许多可行解。每个可行解都对应着一个值，而 我们希望找到具有最优值的解，即最优解。它的基本思路是将复杂问题分解成与 之相似的子问题，再通过求解各个子问题来得到整个问题的解决方案。 如果我们能够保存已解决的子问题的答案，在需要时再拿出来使用，这样就 可以避免重复计算，节省时间。我们可以用一个表来记录所有已求解的子问题的 答案。无论这些子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 1 6蚁群算法在生物序列比对中的应用 这就是动态规划算法的基本思路。具体的动态规划算法