（计算机应用技术专业论文）生物同源序列比对算法研究及其实现.pdf

摘要 摘要 序列比对是生物信息学中一项重要的基础性研究课题，它的最基本任务之一是进行 多序列比对，多序列比对可用于蛋白质的功能域识别、二级结构预测、基因识别以及分子 系统发育分析等方面的研究。由于多序列比对问题是一个n p 完全问题，它的求解至今 仍是生物信息学中的一个难题。本文提出使用量子粒子群优化算法以及隐马尔可夫模型 来解决多序列比对问题。 首先分析了空位罚分、替换矩阵和目标函数对序列比对的影响，具体介绍了s p 和 c o f f e e 目标函数。对经典的多重序列比对算法：s a g a 算法和c l u s t a l 算法及隐马尔可 夫模型多重序列比对算法进行了研究，对几种算法的性能进行了比较和评估。 接着通过对粒子群优化算法的特点进行分析提出了基于二进制粒子群优化算法的 多序列比对算法m s ab p s o ( m 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 d0 1 1b i n a r yp a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h m ) 。然后通过对量子粒子群优化算法与隐马尔可夫模型的分 析研究提出了基于隐马尔可夫模型和量子粒子群优化算法的多重序列比对算法 m s a _ h m m _ q p s o ( m 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 nh i d d e nm a r k o vm o d e la n d q u a n t u m - b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ) 。 以本文提出的算法为基础，利用m i c r o s o f t v i s u a ls t u d i o n e tc # 2 0 0 5 为开发工具设 计并实现了一个基于w i n d o w s 操作系统的多重序列比对的软件。用基准多序列比对库 b a l i b a s e 中的用例对算法进行测试，并与经典多重序列比对方法进行对比分析，结果表 明m s ah m mq p s o 算法在解决蛋白质序列比对问题上是有效的。最后论述了 m s ah m m q p s o 算法在序列分析方面的发展前景。 关键词：多序列比对，目标函数，二进制微粒群优化算法，量子粒子群优化算法， 隐马尔可夫模型( h m m ) a b s t r a e t a b s tr a c t s e q u e n c ea l i g n m e n t o fb i o i n f o r m a t i c si sa n i m p o r t a n t f u n d a m e n t a l s u b j e c t i n b i o i n f o r m a t i c sr e s e a r c h o n eo fi t sm o s tb a s i ct a s ki st om u l t i p l es e q u e n c ea l i g n m e n t s s e q u e n c ea l i g n m e n t i su s e dt or e s e a r c ho ft h ed o m a i np r o t e i ni d e n t i f i c a t i o n ，s e c o n d a r y s t r u c t u r e p r e d i c t i o n ，g e n ei d e n t i f i c a t i o n , a n d m o l e c u l a rp h y l o g e n e t i c a n a l y s i s m u t t i p l e s e q u e n c ea l i g n m e n ti sn p - h a r dp r o b l e m , s t i l lt h e r ei sn o ta no p t i m a la l g o r i t h mo fm u l t i p l e s e q u e n c ea l i g n m e n t s t h i sp a p e rp r o s e s e sam e t h o d ，w h i c hu s eq u a n t u m - b e h a v e dp a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h ma n dt h eh i d d e nm a r k o vm o d e lt os o l v et h ep r o b l e m so f m u l t i p l es e q u e n c ea l i g n m e n t s f i r s t l y ，t h ee f f e c t0 1 1s e q u e n c ea l i g n m e n tc a u s e db yt h eg a pp e n a l t y ，s u b s t i t u t i o nm a t r i x a n do b j e c t i v ef u n c t i o na r ea n a l y z e d ，a n dt h es po b j e c t i v ef u n c t i o na n dc o f f e eo b j e c t i v e f u n c t i o na l ei n t r o d u c e d f o rt h ec l a s s i cm u l t i p l es e q u e n c ea l i g n m e n ta l g o r i t h m ，s t u d yt h e s a g aa l g o r i t h ma n dc l u s t a lp r o g r a m m i n ga n dh m ma l g o r i t h m m a k ec o m p a r i s o na n d a s s e s s m e n tf o r t h ep e r f o r m a n c eo ns e v e r a la l g o r i t h m s l a t e rt h r o u g ht h es t u d yo nc u r r e n ts i t u a t i o no ft h em u l t i p l es e q u e n c ea l i g n m e n t s a l g o r i t h ma n dt h ea n a l y s i s t ot h ep r i n c i p l ea n dc h a r a c t e r i s t i co ft h e p a r t i c l e s w a r m o p t i m i z a t i o na l g o t i t h m ，p r e s e n tt h em u l t i p l es e q u e n c ea l i g n m e n t sa l g o r i t h e mb a s e do nb i n a r y p a r t i c l e f f w a r l i lo p t i m i z a t i o na l g o r i t h mm s a _ b p s o ，a n dt h e nt h r o u g ht h es t u d ya n dt h e a n a l y s i so nt h eq u a n t u m b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h ma n dt h eh i d d e n m a r k o vm o d e l ，p r e s e n tm 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 nh i d d e nm a r k o vm o d e la n d q u a n t u m - b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ( m s a _ h m m _ q p s o ) b a s eo nt h ea l g o r i t h mo ft h i sp a p e rb r i n g i n gf o r w a r d ，d e s i g na n di m p l e m e n tt h e s o f t w a r ef o rm u l t i p l es e q u e n c ea l i g n m e n t sb a s e do i lw i n d o w so p e r a t i o ns y s t e mb ym i c r o s o f t v i s u a ls t u d i o n e tc # 2 0 0 5 a l s o ，t h ea l g o r i t h m sw e r eu s e dt ot e s tb e n c h m a r km u l t i p l e s e q u e n c ea l i g n m e n t sd a t a b a s eb a l i b a s e ，a n dm a k ec o m p a r a t i v ea n a l y s i s 谢mc l a s s i c a l p r o t e i ns e q u e n c ea l i g n m e n tm e t h o d t h er e s u l t ss h o wt h a tt h ep r o p o s e dm s a _ h m m _ q p s o a l g o r i t h ma r ef e a s i b l et os o l v et h ep r o b l e m o fs e q u e n c ea l i g n m e n t s f i n a l l y ，t h ef u t u r ew o r ko f m s a _ h m m _ q p s oa l g o r i t h mi i ls e q u e n c ea n a l y s i sw a s d i s c u s s e di nt h i sp a p e r k e y w o r d s ：m u l t i p l es e q u e n c ea l i g n m e n t s ，o b j e c t i v ef u n c t i o n ，b i n a r yp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m ，q u a n t u m b e h a v e dp a r t i c l es w a r n lo p t i m i z a t i o na l g o r i t h m ，h i d d e n m a r k o vm o d e l ( h m m ) u 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名：纪文娟 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件争磁- 盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容鳊入有关数据库 进行检索可以采用影印、缩印或扫描等复制手段保存、汇鳊学位论文， 并且本人电子文档的内容乖纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签 名：一纽塞亟 导师签名： ! 兰兰! 堡 日 期：丝9 1 ：丘：i 第一章绪论 第一章绪论 1 1 序列比对的背景以及意义 生物序列一般指d n a 或蛋白质序列或r n a 序列，大量生命现象的奥秘蕴含其中， 对它们的研究是近代生命科学研究中的一个关键而又基本的问题。生物序列分析问题的 内容很多，其核心问题之一是各种不同类型的生物体序列关心的相互比较问题，它的最 终目的是寻找与确定不同生物序列的稳定区域和变化规则，并由此发现它们的功能特征 与区别。无论是基因序列还是蛋白质序列，它们的相互关系都是十分复杂的，根据生物 学界的估计，从最早的原生分子序列开始，生命过程已经经历了3 5 亿多年的演变与进 化，才形成了当今世界数以千万计的各种物种，而且在同一类的生物体中还有各种不同 类型的性状的区别。近代生命科学的重大发现就是这种演化过程，也可以归结为生物序 列的变异过程，这些不同物种与生物体的千差万别的根源就来自于这些生物序列的区 别。 序列比对是生物信息学中最基本、最重要的操作，通过序列比对可以发现生物序列 中的功能、结构和进化的信息。序列比对的根本任务是：通过比较生物分子序列，发现 它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差异。在分子生物学中， d n a 或蛋白质的相似性是多方面的，可能是结构的相似，可能是功能的相似，也可能 是核酸或氨基酸序列的相似。一个较为普遍的规律是序列决定结构，结构决定功能。研 究序列相似性的目的之一是通过相似的序列得到相似的结构或相似的功能。 进化学说是序列比对的理论基础。大量生物学的事实表明：不同的蛋白质或核酸序列 可能源于同一原始序列，经过序列内残基( 把构成核酸或蛋白质的核苷酸或氨基酸统称 为残基) 的取代、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。 在残基一残基比对中，可以明显看到序列中某些残基比其它位置上的残基更保守，这些 信息揭示了这些保守位点上的残基对序列的结构和功能是至关重要的。因此，序列比对 可用于蛋白质的功能域识别、二级结构预测、基因识别以及分子系统发育分析等方面的 研究【l 】o 通过大量生物数据的分析发现，这些变异过程同时具有保守性与变异性的特点。由 于保守性，使不同物种在外部环境不发生重大变化的条件下能保持相当长的生存与繁殖 时间；而由于变异性才使生物体具有进化演变的过程，这种变异过程可在生物分子内部 随机的发生，也可在外部环境影响下发生，在这数十亿年的演变与进化过程中，各种不 同类型的序列片段相互交叉与组合，形成十分复杂的序列结构。因此，序列比对的根本 目的是对不同的生物体( 或序列) 寻找它们的演变规律与特征，了解这种演变规律与特 征及这个过程对生命过程的作用。因此，序列比对问题最初是因研究生物体的进化而提 出【2 3 1 。 我们从基因组计划的实施得到了大量的序列数据。拿g e n b a n k 序列为例，1 9 9 5 年 的数据量为5 0 0 0 万个碱基对，到2 0 0 0 年已达到1 0 0 亿个碱基对。如此庞大的数据量的 分析，使序列分析成了计算机与生物学相结合的热点。当务之急是能够研究出新的计算 江南大学硕士学位论文 方法，从序列数据中提取有用的生物信息。通过序列比较，能够检测新测定序列与数据 库中已知结构和功能的序列之间的相似性关系，从而以足够的可信度确定新序列的结构 和功能信息。目前，序列比对中存在的比较突出的问题如下： a 基因组的拼接问题：在人类基因组对所有染色体的测定过程中，存在对已测定 的小序列片段进行拼接的问题，常规的基因拼接的处理方法是取同一型号的多条染色体 进行打断与测定，再利用不同片段的交叉部分进行拼接，因此，在这个拼接的过程中序 列的比对计算是其中重要的一个环节【4 】。 b 重复序列的搜索问题：由于人类基因组计划等各种不同类型的基因组计划的实 施，发现在同一生物体( 尤其是在高等生物体) 的基因组中，存在大量基因的交叉与重 复问题。而在同一生物体的基因组中还存在大量d n a 片段的重复现象。基因的交叉就 是由同一基因的不同片段或不同基因的不同片段的组合可产生多种不同类型的蛋白质。 对这种交叉与重复现象如何进行解释，重复现象到底有多少，它们的发生规律与后果如 何，能否全部把它们归纳出来，这些问题只有在进一步了解这些基因信息的情况下才能 解决，这也正是后基因组计划将会着重解决的问题，而序列的比对正是解决这些问题的 重要手段。 c 基因的定位问题：就是在某个生物体中发现某一个基因a ，如何在其他生物体 中寻找与该基因相似的d n a 或r n a 序列。基因的定位问题目前已经发展成为基因库的 搜索问题，然而，由于g e n b a n k 数据库数据规模庞大，而且几乎每两年都要翻一翻。因 此序列比对的运算速度已成为至关重要的问题，如果没有快速的比对算法，对长序列的 搜索是完全不可能的。因此，国际上多种大型软件包，如b l a s t ，f a s t a 等都把寻找快速 算法放在重要地位。 由此可见，序列的比对问题已不再是对简单的生物进化问题进行研究，而是涉及到 了整个生命系统的基因、蛋白质与各种生物大分子结构的信息关系的分析。因此我们把 序列比对问题看作是近代生命科学与生物信息学一个重要的基本问题。 1 2 序列比对的研究现状 目前，被誉为“生物学史上划时代工程 的人类基因图谱测序已经基本完成，对人 类基因组来说，得到序列仅仅是第一步，下一步我们将进入更加艰巨的“后基因时代 口o s t g e n o m i ce r a ) ，即收集、整理、检索和分析序列中表征蛋白质结构与功能的信息。 因此研究新的计算方法，从序列数据库中提取有用物信息，非常重要。寻找序列相似性 的过程称为序列比对，序列比对是序列分析的基本手段，通过序列比较，检测新测定序 列与数据库己知结构和功能的序列之间的相似性从而以足够的可信度确定新序列的结 构和功能信息。这一过程需要通过搜索，找出具有相似性的同源序列，对于d n a 序列， 可推测该未知序列可能属哪个基因家族，具有哪些生物学功能：而对蛋白质序列来说， 有可能找到已知维结构的同源蛋白质，而推测其可能的空间结构与功能。然而，就目前 的数学和计算机科学的能力而言，对数据容量达到上十亿字节的数据库进行生物计算仍 然是一项很艰巨的任务。虽然最简单的序列比对可以被简化成字符串匹配的算法，但是 2 第一章绪论 扩展的和多重的序列比对仍处于实验摸索中。近期，生物信息学的目标有以下几个方面： ( 1 ) 生物大分子的结构模拟，仅是阐明了其一级结构，然而作为生命本质的生物信息 流所包含功能的实现，必须要经过空间重构( 蛋白质的折叠) ，才能表现出生命的功能。 反之，从已知功能的蛋白质结构出发，研究这蛋白质功能的分子基础及其变化对蛋白质 的三维重构和功能的影响，从而为基疗法设计相应的蛋白质受体药物，这些是摆在生物 医学科学家面前的紧迫任务。 ( 2 ) 大规模基因功能表达谱的分析：基因组测序工作完成以后，虽然弄清了核酸序列， 但不知道它们的功能如何，或者说它们是如何按照特定的时空进行表达的，表达量有多 少等。 ( 3 ) 完整基因组的比较和分子进化研究：通过多种同元比较和分析方法，可以测出一个 基因可能具有的功能。 ( 4 ) 新基因和新的单核苷酸多态性( s n p s ) 的发现与鉴定：使用基因组信息学的法通 过超大规模计算是发现新基因的重要手段，可以说大部分新基因是靠理论方法预测出来 的。构建s n p s 及其相关数据库是基因组研究走向应用的重要步骤。 ( 5 ) 大规模基因组测序中的信息分析：大规模测序是基因组研究的最基本任务，它的 每一个环节都与信息分析紧密相关。 1 3 论文的结构和主要工作 论文的结构如下： 第一章：描述了序列比对的背景，分析了目前进行多序列比对算法研究的必要性， 介绍了多序列比对问题研究的现状，最后给出论文中所做的工作及各章节的安排。 第二章：介绍了与序列比对有关的基础，包括基本概念、比对算法中要考虑的因素 ( 空位罚分、相似性替代矩阵和目标函数) 及如何评价比对结果。 第三章：介绍了序列比对的相关工作，列出了六种序列比对策略，着重介绍了两种 比较经典的序列比对算法。 第四章：本章首先介绍了粒子群优化算法的基本原理，接着分析了基于二进制的微 粒群优化算法，然后将该算法应用到多序列比对中，分析了该算法用于序列比对的优缺 点，并且介绍了q p s o 算法相关知识以及用于序列比对的优点。 第五章：本章首先介绍了隐马尔可夫模型的基本知识，接着分析了隐马尔可夫模型 用于序列比对的流程以及特点，提出了基于量子粒子群优化算法与隐马尔可夫模型的多 序列比对算法，并对其进行了一些改进。 第六章：介绍了基于量子粒子群优化算法与隐马尔可夫模型的多序列比对算法软件 的设计与实现过程，详细描述了算法实现流程以及实现过程中遇到的问题。实验部分用 该算法测试了部分b a i i b a s e 比对库，并将测试结果和目前应用较多的多序列比对算法 的测试结果作了比较、分析和评价。 第七章：对全文所做工作的总结与展望。 江南大学硕士学位论文 第二章序列比对基础 序列比对是生物信息学的焦点问题之一。本章从序列比对的基本概念讲起，然后介 绍影响序列比对的基本要素：空位罚分、相似性替换矩阵和目标函数，最后给出评判序 列比对结果优劣的标准。 2 1 序列比对的基本概念 核苷酸或氨基酸的多序列比对是生物信息学中最重要、也最具有挑战性的任务之 一。多序列比对问题是一个将不等长的多个序列通过插入空位变成等长的过程，这些位 置上的空位代表着相比对的序列从共同的祖先通过插入删除操作的进化过程。利用多序 列比对算法得到的最优比对，可用于预测蛋白质的结构和功能；可用于证明新序列和已 经存在的序列组的相似性，也可用于构造系统发生树，找出蛋白质的家族序列。 多序列比对就是把两条以上可能有系统进化关系的序列进行比对的方法，一条长度 为m 的生物序列是由m 个字符组成的字符串，字符串中的字符取自于一个有限的字母 表，对于d n a 序列，包含a ，t ，c ，g 四个字母，分别代表4 种不同的核苷酸，将其 统称为碱基。对于蛋白质序列，包含2 0 个不同的字母，分别代表2 0 种不同的氨基酸， 将其统称为残基。给定n 条序列组成的序列组s = ( s l ，s 2 s n ) ，其中：s i = s i l s i 2 s i i i ( 1 i m ， s i j ( 1 j - 孵，幸s c o r e ( a ) 】 职， l e n ( a ，3 1 ( 2 1 2 ) a = lj = t + li = 1j = i + l 式2 1 2 中n 表示序列个数，彳“为多序列比对中的双序列比对，l e n ( a j ，) 为双序列比 对的序列的长度，s c o r e ( a ，) 是多序列比对中的彳和数据库中的彳“双序列比对结 果的一致性分数。即：s c o r e ( aj ，) 为多序列比对中彳j 和数据库中彳“双序列比对结 果的匹配残基的数目。助。j 为双序列比对相关的权值，最简单的彤，j 等于两个比对序列 的相似度的百分比。从式2 1 2 可以看出c o f f e e s c o r e 是在0 1 之间的数。 2 5 多序列比对结果的评判 2 5 1b a i i b a s e 测试集 b a l i b a s e ( t h o m p s o n ，1 9 9 9 b ) 是一个蛋白质多序列比对库，该比对库中有1 4 4 个比对 用例( 包含1 0 0 0 多条蛋白质序列) ，这1 4 4 个比对用例都是经过许多程序的测试和手 工验证的【1 3 l 。根据序列的长度、相似度以及插入的出现和n c 末端的延伸，这些比对用 例被分为以下五类1 1 4 j ： 第一类：该类中包含了8 0 多个序列长度相当的比对，每一个比对所包含的序列数 为3 7 个，测试用例中的比对序列相似度差异较小，这8 0 多个比对用例又根据比对序 列的长度分为三个子集，第一个子集是短序列比对，长度为1 0 0 左右，第二个子集是中 长序列比对，长度为2 0 0 3 0 0 之间，第三个子集是长序列比对，其长度为3 0 0 1 0 0 0 之间。 第二类：该类包含了2 3 个比对，这些比对中至少有1 5 个亲缘关系较近的序列和 一个孤儿序列( 相似度小于2 5 ) ，每个比对包含的序列条数为2 0 个左右，长度为1 0 0 0 以内。 第三类：该类中包含的是分歧较大的序列比对，比对中包含多个子组，组与组之间 的残基相似度小于2 5 。每个比对包含的序列条数为3 0 以内，长度在1 0 0 0 以内。 第四类：该类中包含n c 末端延伸超过4 0 0 个残基的序列，该子集是唯一一个适合 局部比对的子集。 第五类：该类中包含需要大量插入空位的序列。 l o 第二苹序列比对基础 2 5 2 评价比对结果 为了评价多序列比对方法所测的比对结果与b a l i s c o r e 库中的参考比对的相似性， 采用s p s ( s u mo fp a i r ss c o r e ) 和c s ( c o l u m ns c o r e ) 分值来衡量多序列比对程序的性能【1 5 】。 s p s 分值表示残基对准确对齐的比率，c s 分值表示所有序列准确对齐的比率( 即对齐多 少列) 。使用b a l i s c o r e t l 6 】程序来计算s p s 和c s 分值。b a l i b a s e 和b a l i s c o r e 可从 f t p ：f t p 2 i g b m c u 2 s t r a s b g f i p u b b a i i b a s e 下载。下面分别介绍如何计算t l l es u mo fp a i r s c o r e ( s p s ) 和t h ec o l u m ns c o r e ( c s ) 两个分值。假定实验所得序列个数为n ，每条序列有 m 列，而参考序列的列数为m ，第i 列的碱基表示为c i ，i ，c i 2 ，c 讽则这两个值的计算方 法分别描述如下：s p s 对一列上的每一个碱基c i j 和c i , k ，定义p 独，如果c i j 和c u , 比对 上即相同，则p i 业为1 ，反之为0 。则每一列的值s i 的计算公式如式2 1 3 所示。 s i = - 。：。眦 ( 2 1 3 ) 假设s ，值为参考数据对应的s i 值。则s p s 值计算公式见式2 1 4 。 跚= y 。s i y ： ( 2 1 4 ) l a l = i l - d i 互l c s 如果每一列上的所有碱基都相等，则c ，- 1 ，否则c 卢0 ，则c s 计算公式如式2 1 5 所示。 c s = y 肘c f m ( 2 1 5 ) 但是，如果没有标准比对库做参考，s p s 可按如式2 1 6 的方法计算( 这种计算方法适合 多种方法对于同一输入数据之间的比较，不能用来绝对判断比对结果的优劣) ： s p s = y s i ( m 幸( 一1 ) 2 ) ( 2 1 6 ) 一j = l 、 显然，s p s 是残基对准确对齐的比率，而c s 值是所有序列准确对齐的比率。 在进化计算中，目标函数不仅是评价一个结果( 个体) 的好坏( 适应度f i t n e s s ) 的 标准，而且目标函数的值还反映这个比对的生物信息并且预示序列的结构或者比对序列 之间存在的进化关系。下面两个函数是广泛使用的评价多序列比对结果的标准，基于 s p ( s u mo fp a i r ) t l s l 计分的目标函数和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 r a l i g n m e n te v a l u a t i o n ) 目标函数。根据s p 目标函数，在比对结果的每一列中，将每对碱 基给定一个分值氏帆( 例如：p 踮帆( x ，x ) = 2 ，p 呲( x ，y ) = 氏叭( x ，- ) = 氏叭( 一， x ) = 1 和p 。m ( ，) = 0 ，其中：“”代码空位；x 和y 代表两个不同的碱基) ，然后 将这些p m 分值累加起来，得到每列的分值c 叭，最后将每列的分值累加，即可得到 s p s c o r e 。假定比对结果为s ，( j 0 ) ，1 i n ，l j l ，则s p s c o r e 的计算公式如式 2 1 7 和式2 18 所示。 s p s c o r e ( s 7 ) = 芝：g 一( s 7 l ，j 2 ，j ，i ) ( 2 1 7 ) 百 川，u 札如：而s q o( 2 1 8 ) 坞陋酬 如果输入数据是标准比对库( 如b a l i b a s e ) 中的序列，即有一个标准的比对结果，我 们可以计算相对的s p s c o r e ，定义为s p s 。假定对于标准库的输入序列，标准库中比对 江南大学硕士学位论文 结果为s ，某方法的比对结果为s ，则s p s 定义如式2 1 9 所示。 s p s = s p s c o r e ( ) s p s c o r e ( s )( 2 1 9 ) 如果没有标准比对库，s p s 的定义如式2 2 0 所示。 s p s = s p s c o r e ( ，) ( l n ( 一1 ) 2 ) ( 2 2 0 ) 从以上公式可以看出，s p s 分值反映的是碱基对准确对齐的比率，为了反映所有序列准 确对齐的比率，通常使用c s ( c o l u m ns c o r e ) 值来计算，c s 值计算方法为：如果一列 上的所有碱基都相等，则c i = l ：否则c i = 0 同样，对于比对结果j ”，c s 值计算公式如式 2 2 l 所示。 c s = _ d 三 ( 2 2 1 ) _ 一，一i 基本上，s p s 值和c s 值越高，说明比对结果越准确，越能反映序列的生物特性。在下 面的实验中将采用s p s 打分方法来评估本算法的比对结果。 1 2 第三章经典多序列比对算法 第三章经典多序列比对算法 目前主要有下列五种策略用于多序列比对【2 牡略7 j 。 第一种策略是基于动态规划的算法，代表算法有最优全局比对的n e e d l e m a n w u n s c h 算法【1 7 1 ，最优局部比对的s m i t h - w a t e r m a n 算法【1 8 】等，虽然动态规划算法能够达到精确 比对，但是该算法局限于少数短序列的比对，对于多个长序列的比对，计算能力受到限 制，为了克服这个缺点，产生了许多基于不同策略、不同算法的多序列比对方法，主要 有渐进的和迭代的多序列比对方法； 第二种策略是基于概率模型的方法，该方法的代表有隐马尔可夫模型【2 3 8 1 等； 第三种策略是使用随机优化算法，代表算法有模拟退火算法( s a ) 1 1 】，遗传算法 ( g a ) 【2 0 - 2 1 2 2 1 等； 第四种策略是迭代比对，它基于一个能产生比对的算法，并通过一系列的迭代方式 改进多重序列比对，直到比对结果不再改善为止。代表算法有( w a n g & l i ，2 0 0 4 ) ， d i a l i g n 3 6 j 、s a g a 叫、s a m s a 和p s o m s a 等； 第五种策略是渐进的多序列比对方法，其基本思想是：基于相似性序列通常具有进化 相关性这一假设，比对过程中，先对所有的序列进行两两比对并计算它们的相似性分数 值，然后根据相似性分数值将它们分成若干组，并在每组之间进行比对，计算相似性分 数值，根据相似性分数值继续分组比对，直到得到最终比对的结果。基于该思想的序列 比对算法有：m u l n 虬i g n 、m u l t a l 、p i l e u p 、c l u s t a l x 玉心j 等； 近几年来，又有很多基于图论的多序列比对算法提出：基于欧拉路径的全局多序列 比对算法和基于最大权值路径的多序列比对算法 2 8 , 2 9 。目前的序列比对算法主要存在以 下三大问题： ( 1 ) 多重序列的比对问题：序列比对问题目前所存在的问题就是多序列的比对问 题，该问题在计算生物学与生物信息学中仍被列为未解决的重大问题或非易计算问题， 有的文献把它列为n p 完全问题，计算复杂度为双指数问题，也就是计算复杂度为0 0 ， 其中m 为序列比对的重数，1 1 为序列长度。因此目前所能进行的多重序列的比对只能在 很小规模上进行，这与目前所出现的庞大数据是极不相称的，如何构造多序列比对的快 速算法是计算机生物学与生物信息学中的重大问题。 ( 2 ) 比对结果的分析问题：同源序列比对的根本目标是确定它们的进化演变关系， 在生物学界常通过序列比对来构造进化树，并由此确定它们的进化关系。但是，比对与 进化的关系到底如何，如何由大量序列的比对结果来构造进化树的逻辑过程是生物学家 所关心的问题。如何由序列比对来确定序列的突变与进化关系，如何建立它们变化关系 的数学模型与分析规则是序列比对理论中不可缺少的一个重要部分。 ( 3 ) 不同比对算法的效果分析问题：目前无论是双序列比对还是多序列比对都有 大量算法出现，对这些比对算法结果也有许多度量性的指标如计算复杂度( 时间复杂度 与空间复杂度) ，比对相似度，搜索相似度等。目前，生物信息学中还是以进行实际测 试计算为最一般的考核方法，要对所设计的比对算法的各项度量指标做出理论上的说明 江南大学硕士学位论文 是一个十分困难的问题，因为这涉及到序列突变的总体或局部模型问题，这是一个十分 复杂的问题，不仅序列数据庞大，而且突变现象千变万化，所以不可能用一种或几种模 型就可把它们概括说n t 2 , 4 j 。 由于多序列比对问题是一个n p 完全问题，它的求解至今仍是生物信息学中的一个 难题。在蛋白质家族的保守模式序列中包含了更多信息，例如在整个序列家族中或多或 少保守的残基及其位置信息，残基插入和删除的概率等。用来描述相关序列共有的保守 特征的方法，如序列谱、可变模式和嵌段都可视为隐马尔可夫模型的具体应用，因而利 用隐马尔可夫模型作为多序列比对的工具也越来越多地引起了人们的兴趣。如何利用有 限的训练数据建立最稳定、最可靠的h m m 模型，就成了最关键、最困难的问题，而且 至今仍没有确定性的算法能保证在合理的时间内找到理想的h m m 模型。 最常用的训练h m m 模型的方法是基于统计和重估的方法，比如b a u m w e l c h 算法 2 4 】。本文结合q p s o 算法，构建了新的h m m 模型训练算法用于多序列比对。所提出的 学习算法具有随机优化算法的随机性，可以解决非线性系统的最优化问题，同时具有生 物信息学中的隐马尔可夫模型与量子粒子群优化算法的容易实现与三维空间搜索等特 点。下面将在3 1 和3 2 中介绍两种经典算法的代表。 3 1s a g a 算法 s a g a 是基于遗传算法的多序列比对方法【3 7 1 ，属于随机迭代策略的多序列比对方 法。s a g a 和基本的遗传算法的原理是一样的，即：为给定的序列组随机的产生多个比 对，然后在一定的选择概率下进行进化。每一个个体赋予一个适应度，这里适应度是依 赖于目标函数的得分，根据自然界适者生存的进化规律，在一代代的进化过程中，具有 较高适应度的个体能够生存下来，而较低适应度的个体则被淘汰，这些个体也可以通过 随机变化策略来产生新的个体，随机变化策略有变异和交叉，变异是随机的插入或移动 空位，而交叉是重新组合两个比对的内容。 s a g a 中有2 2 个操作符：1 6 个块移动操作符、2 个交叉操作符、1 个块查找操作符、 1 个空位插入操作符和2 个局部重排操作符。s a g a 用一种动态调度的过程来调用这些 操作符。该动态调度模型是由d a v i s 提出来的，s a g a 程序初始化的时候每一种操作符 的概率都是相等的，即1 2 2 ，在运行的时候使用动态调用过程来调用这些操作符。在这 个动态调用模型中，每一个操作符的概率是最近几代提高比对效率的函数，一个操作符 优化的得分会与前一个起相同作用的操作符共享这个得分，因此，每一次产生一个新的 个体。假如它对父代有一定的优化作用，那么直接产生它的操作符将获得一大部分的分 数( 例如：5 0 ) ，然后是产生父代的操作符得到剩余分数的一部分( 剩余分数5 0 ， 例如原始分数的2 5 ) ，这些分数的纪录保持一个给定的代数( 例如4 代) 。在一个给 定代数( 例如1 0 代) 之后，会为每一个操作符总结结果。一个操作符的得分等于总得 分除以它产生的孩子个数，这个值用作概率并且保持不变直到下一次评价( 1 0 代之后) 。 为了避免一些后来会有用的操作符早期失去作用，所有的操作符都赋予了一个最小的概 率【2 1 1 。 1 4 第三章经典多序列比对算法 3 2c l u st al 算法 c l u s t a l 是一个系列程序，前后有四个版本，最早的版本是在1 9 8 8 年由d e s h i g g i n s 提出并实现的，目前的版本是c l u s t a l w 引，它对前一版本作了较大的改进，该版本又有 一个界面化的版本c l u s t a l x ，其操作结果和c l u s t m w 完全一样。基本c l u s t a l 算法由三 部分组成： ( 1 ) 建立距离矩阵：用完全动态规划方法比对每一对序列，将比对后相同的残基 数除以比较的残基对数，得到一个分值，这个值除以1 0 0 ，然后从1 0 中减去所除的值 即为距离值。 ( 2 ) 构造指导树：这颗树是用来指导多序列比对的整个过程。它是根据距离矩阵 用“加入近邻的方法”计算所得的。这个过程产生一个无根树，该树中每一个分支的长 度正比于延分支所估计的分歧。也可根据这些树来推导每一个序列的权值，这个权值依 赖于从根到序列的距离，但是共享相同分支的序列也共享来自于这个分支的权值。 ( 3 ) 渐进比对：在这一阶段，基本程序中是用一系列的双比对来比对越来越多的 序列组，比对过程是依据指导树的分支顺序，从带根树的末端到树根来进行。 3 3 本章小结 无论是双序列比对还是多序列比对都是建立在某种数学或生物学模型之上。因此， 我们不能对序列比对的结果得出“正确或错误”的结论。只能认为所使用的模型多大程 度上反映了序列之间的相似性关系以及它们的生物学特征。进行序列比对的目的之一是 让人们能够判断序列之间是否具有足够的相似性，从而判定序列之间是否具有同源性。 如果某种比对的打分值不会因为增加或减少比对的数量而增加时，我们称这种比对就是 最佳的。 序列比对算法的研究已经发展了4 0 多年，因此出现了许多经典的且广泛使用的比 对算法。比如，本章介绍的s a g a 动态规划算法和c l u s t a l 算法。目前，动态规划算法 已经成为d n a 序列和蛋白质序列比对的精确算法。因此我们选择动态规划算法来构建 c o f f e e 目标函数的双序列比对库。动态规划算法计分主要依靠替换矩阵。动态规划的 核心是要将各个最佳子路径连接起来，最终构成具有最优结果的路径，而得到比对结果。 利用动态规划算法最后需要采用回溯技术，并根据空位罚分等参数比较达到高分比对的 不同路径。目前使用最广泛的多序列比对程序是c l u s t a l w ，c l u s m l w 是一个高度地专 业化的多序列比对算法，它基于渐进的比对思想。根据亲缘树的分支对序列两两比对。相 似性程度高的先比对，相似度程度低的后加入。通过分析可能的进化关系，评估集合中 所有序列两两之间的进化距离，然后创建一棵进化树，这种方法可以处理一定规模的数据 量。c l u s a t l w 程序可通过互联网免费得到。s a g a 使用自动的调度方案去控制2 2 个不 同算子的使用，这2 2 个不同的算子用于两代之间的交叉和变异操作，当目标函数是s u m s o fp a i r s 时，s a g a 优于其他广泛使用的多序列比对软件包t c o f f e e 是基于渐进的方 法进行多序列比对的，但是它避免了这个算法贪婪的特征导致的严重的缺陷d i a l i g n 能够定位到小的保守的区域，而这些区域是不能被其他标准的比对程序检测到的。 江南大学硕士学位论文 第四章基于p s o 的多序列比对 4 1 粒子群优化算法( p s o ) p s o 3 3 1 算法是在1 9 9 5 年由美国社会心理学家j a m e sk e n n e d y 和电气工程师r u s s e l l e b e r h a r t 共同提出的，其基本思想是受他们早期对鸟类群体行为研究结果的启发，并利 用了生物学家f r a n kh e p p n e r 的生物群体模型。微粒群优化算法与其他算法相类似，也 采用“群体”和“进化”的概念，同样也是依据个体( 微粒) 的适应值大小进行操作。所不 同的是，微粒群优化算法不像其他进化算法那样对于个体使用进化算子，而是将每个个 体看作是d 维搜索空间中的一个没有重量和体积的微粒，并在搜索空间中以一定的速 度飞行。该飞行速度由个体的飞行经验和群体的飞行经验动态调整。每个粒子代表d 维 空间中的一个位置，朝着下面两个方向调整粒