（计算机应用技术专业论文）群体智能算法研究及其在生物序列比对中的应用.pdf

摘要 本文首先对群体智能算法做了概述，深入研究了群体智能算法的原理和特点，在此 基础上提出了改进智能优化算法，引入交叉算子到量子粒子群算法来保持算法在搜索后 期的多样性，使算法具有更好的优化效果，通过对标准测试函数优化，实验结果显示新 算法的优化效果较原算法大幅提高，表明了算法改进的有效性。 然后本文对生物信息学中的多序列比对问题进行了研究，这是一个n p 完全问题。 文中对序列比对概念和关键知识做了介绍，分析了基于隐马尔科夫模型的多序列比对的 原理，介绍了h m m 的三个基本问题和基于隐马尔科夫模型的多序列比对原理，针对 h m m 算法中b a u m - w e l e h 算法容易陷入局部最优解、全局搜索能力差的问题，本文结 合了有较强全局搜索能力的群体智能算法q p s o 和具有快速局部搜索能力的b w 算法对 h m m 进行训练，并进一步用v i t e r b i 算法根据训练出的模型进行多序列比对。新算法兼 备了q p s o 的全局搜索能力和b a u m w e l c h 算法的快速逼近局部最优解能力。 用标准多序列比对库b a l i b a s e 中的测试序列对文中提出的比对算法进行测试，通 过和原算法的结果对比，表明文中提出的新比对算法的有效性。最后总结，根据n of r e e l u n c h 对于不同的优化问题，单一的优化算法往往在执行速度或者优化精度方面无法获 得满意的效果，因此综合考虑多种优化算法的优势，取长补短能够获得较好的效果。 关键词：优化算法、群体智能算法、隐马尔科夫模型、多重序列比对 a b s t r a c t a b s t r a c t f i r s to fa l l ，t h i sp a p e rp r o v i d e sa no v e r v i e wo fs w a r mi n t e l l i g e n c ea l g o r i t h m s ，a n d s t u d i e st h ep r i n c i p l e sa n df e a t u r e so fs w a r mi n t e l l i g e n c ea l g o r i t h m si n - d e p t h o nt h i sb a s i s ，a n i m p r o v e di n t e l l i g e n to p t i m i z a t i o na l g o r i t h mi sp r o p o s e d ，a n dt h ei n t r o d u c t i o no fc r o s s o v e rt o t h eq u a n t u mp a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h mc o n t r i b u t e st om a i n t e n a n c eo ft h e d i v e r s i t yi nt h el a t e rp e r i o do ft h es e a r c hw h i c hm a k e st h ea l g o r i t h mh a sb e t t e ro p t i m i z a t i o n r e s u l t s a f t e rt h eo p t i m i z a t i o nt ot h es t a n d a r dt e s tf u n c t i o n s ，t h ee x p e r i m e n t a lr e s u l t ss h o w t h a tt h eo p t i m i z a t i o ne f f e c to ft h en e wa l g o r i t h mi ss i g n i f i c a n t l yi m p r o v e do v e rt h eo r i g i n a l a l g o r i t h mt h a ti m p r o v e st h ee f f e c t i v e n e s so ft h ea l g o r i t h m s e c o n d l y , t h em u l t i p l es e q u e n c ea l i g n m e n tp r o b l e m si nt h eb i o i n f o r m a t i c si ss t u d i e d ， w h i c hi san pc o m p l e t ep r o b l e m i nt h i sp a p e r , t h ec o n c e p ta n dk e yk n o w l e d g eo fa l i g n m e n t h a sm a d et h ei n t r o d u c t i o n t h ea n a l y s i so fh i d d e nm a r k o vm o d e lb a s e do nt h ep r i n c i p l eo f m u l t i p l es e q u e n c ea l i g n m e n ta n dt h ei n t r o d u c t i o no ft h et h r e eb a s i cq u e s t i o n so fh m ma r e a l s op r o v i d e d b e c a u s eo ft h ee a s yf a l l i n gi n t ol o c a lo p t i m a ls o l u t i o na l g o r i t h ma n dt h ep o o r c a p a b i l i t i e si ng l o b a ls e a r c hp r o b l e m s ，t h i sp a p e rc o m b i n e si n t e l l i g e n ta l g o r i t h mq p s ow i m s t r o n gg l o b a ls e a r c ht oag r o u p 谢mb w 谢t l lf a s tl o c a ls e a r c ha l g o r i t h mf o rh m mt r a i n i n g ， w h o s em o d e lw i l lb et h eb a s eo nt h ef u r t h e rm u l t i p l es e q u e n c ea l i g n m e n t t h en e wa l g o r i t h m h a v eb o t ht h eq p s o sg l o b a ls e a r c ha b i l i t ya n dt h eb a u m - w e l c ha l g o r i t h m sf a s ta p p r o a c h i n g c a p a c i t yo fl o c a lo p t i m a b yt h ec o m p a r i s o no fr e s u l t sb e t w e e nt h eo r i g i n a la l g o r i t h ma n dt h ep r o p o s e da l i g n m e n t a l g o r i t h mw i t ht e s ts e q u e n c ef r o mt h es t a n d a r dl i b r a r yb a l i b a s e ，w ec a ns e et h a tt h en e w a l i g n m e n ta l g o r i t h mi nt h i sp a p e ri se f f e c t i v e a l li na j l ，t h en of r e el u n c hs h o w st h a tw e c a n to p t i m i z et h ee x e c u t i o ns p e e da n dt h ep r e c i s i o na tt h es a m et i m ew i las i n g l e o p t i m i z a t i o na l g o d t l u n , s o - c o n s i d e r i n gt h ea d v a n t a g e so fav a r i e t yo fo p t i m i z a t i o na l g o r i t h m s a n dm a k i n gt h e m w o r k t o g e t h e rc a nd ob e t t e r k e y w o r d s ：o p t i m i z a t i o na l g o r i t h m ，s w a r mi n t e l l i g e n c ea l g o r i t h m ，h i d d e nm a r k o v m o d e l ，m u l t i p l es e q u e n c ea l i g n m e n t l i 目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 优化问题概述1 1 2 经典优化算法1 1 3 进化计算2 1 4 群体智能算法：3 1 4 1 群体智能简介3 1 4 2 群体智能的基本特征4 1 4 3 常见群体智能算法及其进展5 1 5 生物序列比对6 1 5 1 生物序列比对的意义6 1 5 2 序列比对算法研究的进展与存在的问题6 1 5 3 智能优化算法在m s a 中的应用8 1 6 本文内容安排8 第二章群体智能算法一1 1 2 1 基本微粒群算法1 l 2 1 1 粒子群算法起源一1 l 2 1 2 粒子群算法原理1 1 2 1 3 粒子群算法流程1 2 2 2 改进粒子群算法1 3 2 2 1 带有惯性因子的改进p s o 一13 2 2 2 带有收缩因子的改进p s o 。1 3 2 3 量子粒子群算法1 4 2 3 1 量子力学基础一1 4 2 3 2 算法的提出1 4 2 3 2 量子行为粒子群优化算法1 4 2 3 2 q p s o 算法流程1 5 2 4 本章小结l5 第三章改进的群体智能算法c q p s o 1 7 3 1 引言1 7 3 2 遗传算法17 3 2 1 遗传算法1 7 3 2 2 交叉算子。1 9 3 3 带有交叉算子的量子粒子群算法1 9 目录 3 3 1q p s o 交叉操作1 9 3 3 2 群体多样性度量2 0 3 3 3 改进q p s o 算法流程小2 0 3 3 2 实验设置2 0 3 3 3 实验结果分析。2 1 3 4 本章小结3l 第四章隐马尔科夫模型在序列比对中的应用3 3 4 1 生物序列比对3 3 4 1 1 生物序列比对概述。3 3 4 1 2 生物序列比对定义3 3 4 1 2 生物多序列比对的时间复杂性3 3 4 2 序列相似性3 4 4 2 1 序列相似性打分矩阵3 4 4 3 生物序列比对评判准则3 5 4 3 1s p ( s u mo f p a i r s ) 打分函数3 5 4 3 2c o f f e e 打分函数3 6 4 3 3 比对结果评判3 6 4 4 隐马尔科夫模型3 7 4 4 1h m m 原理3 8 4 4 2h m m 三个基本问题3 9 4 4 3 实现h m m 的算法3 9 4 5h m m 在生物序列比对中的应用4 2 4 6 本章小结4 3 第五章基于混合优化算法和h m m 的生物多重序列比对4 5 5 1 基于h m m 多序列比对4 5 5 1 1 h m m 模型初始化4 5 5 1 2h m m 训练4 5 5 1 3 序列比对过程4 6 5 2h m m 在多重序列比对中的讨论4 6 5 3 混合优化算法介绍4 6 5 3 1 量子粒子群算法和b a u m - w e l e h 混合的h m m 优化4 6 5 4 混合训练算法框架4 7 5 4 1 混合训练算法4 7 5 5 实验结果及分析4 8 5 5 1 实验比对结果数据4 8 5 5 2h m m 训练得分曲线：。4 9 5 5 3 序列比对结果4 9 i i 目录 5 5 4 序列比对结果分析一5 l 5 6 本章小结5 1 第六章总结与展望5 3 6 1 全文总结5 3 6 2 未来工作展望5 3 致谢一5 5 参考文献5 6 附录：作者在攻读硕士学位期间发表的论文6 0 i i i 第一章绪论 第一章绪论 1 1 优化问题概述 最优化概念反应了人类实践活动中十分普遍的现象，即在尽可能小的花费代价下争 取获得在可能范围内的最佳效果。因此最优化问题成为现代数学的一个重要课题，设计 多种不同学科，其应用涉及多种不同学科，比如系统控制、人共智能、模式识别、生产 调度和计算机工程等各种领域。优化方法的理论研究对改进算法、拓宽算法应用领域和 完善算法体系具有重要作用，所以优化技术已作为一个重要的科学分支受到众多学者的 关注，已经出现了各种各样的最优化问题的优化算法。 解决优化问题的优化算法可以分为经典优化算法和启发式优化算法。经典算法单纯 形法是1 9 4 7 年美国数学家d a n t z i g 提出的，此算法是求解线性规划问题的一种较为方便的 方法。随后k a m a k a 提出了椭球算法和内点法。对于非线性问题，起初人们试图用线性 优化理论去逼近求解非线性问题，但是效果并不理想。后来的非线性理论大多都建立在 二次函数的基础上，也就是用二次函数去逼近其他非线性函数。在此基础上提出了许多 经典的优化算法。无约束的优化算法包括：最速下降法、共轭梯度法、牛顿法、信赖域 法。 随着社会的发展，实际问题越来越复杂，如全局最优化问题。经典算法一般都使用 局部信息，如初始点及其导数相关信息，这使得经典算法无法避免局部极小值问题。受 大自然的启发，人们从大自然的运行规律找到了许多解决实际问题的方法。对于那些受 大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，称之为启发式算法。 启发式算法起源于2 0 世纪4 0 年代，发展到7 0 年代，计算复杂性理论被提出，n p 完全理论 表明许多实际问题不可能在合理的时间范围内找到全局最优解。由此必须引入新的搜索 机制和策略，才能有效地解决这些困难问题。模拟生物进化规律的遗传算法、模拟退火 算法、人工神经网络和禁忌搜索相继出现。最近演化算法、种群算法和量子算法等相继 兴起。由于这些算法简单有效且具有某种智能，因此成为科学计算有利工具。 最优化问题也就是在一定条件限制下，确定一组参数值，使得目标出现最好效果， 也就是使系统的性能达到最优( 最大或者最小) ，最优化问题的通用数学描述为： m i n t r = 厂( x )( 1 1 ) s t x s = xi ( x ) 0 ，f = 1 ，m 其中，o = f 0 0 是优化算法的目标函数，g t 为约条件，s 为约束域，艉n 维变量。( 1 1 ) 中描述的是最小化问题，最优化还有另外一个问题即最大化可以通过数学方法转换为最 小化问题。 1 2 经典优化算法 最速下降法又称为梯度法，他是解析法中最为古老的一种，是1 8 7 4 年法国科学家 c a u c h y 提出的，其他解析优化算法多是其变形或是由此启发而来，因此最速下降法是最 优化方法的基础。它是以负梯度方向作为下降方向的极小化算法，最速下降法是无约束 江南大学硕士学位论文 最优化中最简单的方法，其优点是计算量小，对初始参数不敏感；缺点就是依赖于函数 的解析特性，收敛速度慢，有时无法求得最优解。 共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息， 但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算h e s s e 矩阵并求逆 的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性 最优化最有效的算法之一。 共轭梯度法最早是h e s t e n e s 和s f i e f l e ( 1 9 5 2 ) 提出来的，用于解正定系数矩阵的线性方 程组，在这个基础上，f l e t c h e r 和r e e v e s ( 1 9 6 4 ) 首先提出了解非线性最优化问题的共轭梯 度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现 在共轭梯度法已经广泛地应用与实际问题中。 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些 搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方 便。 1 3 进化计算 进化策略( e s ) 、进化规划( e p ) 、遗传算法( q 吣和遗传程序设计( g p ) 等进化算法在过 去的一段时间里得到的快速发展，形成了完备的模拟生物进化的计算理论，也就是进化 计算，进化计算的具体实现称为进化算法( e v o l u t i o n a r ya l g o r i t h m ) 。它们是求解最优化 问题的一种随机优化算法，它是从生物进化论和遗传学等理论萌发形成的，当前进化计 算已经出现了几个有代表性的分支，基本思想都是来源于生物进行和遗传学，但是各自 都有自己关注的方面，各具特点。 进化算法是一种全局概率搜索算法，它也是通过迭代进行，这和诸如m e n t oc a r l o 方法、模拟退火、爬山法等大多数优化算法一样。但是不同的是进化算法是基于达尔文 进化论，即以遗传变异、自然选择等生物进化机制为基础形成的优化算法。 进化算法从给定的初始候选解开始，通过不断地迭代改进解的质量，直到搜索到最 优解或者满足结束条件为止。 1 ) 从一组初始点开始。 进化算法是从一组初始解开始迭代，而不是从一个初始点。 2 ) 不需要目标函数解析信息。 进化算法在迭代过程中进行优胜劣汰，评价的标准是目标函数值，而不使用目标函 数的解析特性，因此进化算法具有更广泛的应用空间。 3 ) 具有并行性。 4 ) 算法简单。 5 ) 稳定性好。 进化算法具有很好的稳定性，虽然它是一种随机算法，但是对于同样的条件下多次 求解统一问题，他能够获得稳定的解。 在进化计算的诸多分支中遗传算法是进化算法中产生最早、影响最大、应用也比较 广泛。1 9 7 5 年之后，遗传算法作为函数优化器不但在各个领域得到广泛应用，而且还丰 2 第一章绪论 富和发展了若干遗传算法的基本理论。1 9 8 0 年，b e t h k e 对函数优化g a 进行了研究1 5 】， 包括应用研究和数学分析。s m i t h 在1 9 8 0 年首次提出使用变长位串概念【6 】，这在某种 程度上为以后的遗传规划奠定了基础、g o l d b e r g t l l 、d a v i s 【7 1 、g r e f e n s t e t t e 【引、b a u e r 【9 】、 s r i n i v a s 和p a t n a i k 1 0 】等大批研究人对于遗传算法理论的基本框架和遗传算子进行了构建 和改进，并将遗传算法分别应用于工程设计、自动控制、经济金融、博奕问题、机器学 习等诸多领域之中。 1 4 群体智能算法 1 4 1 群体智能简介 自热界不仅有智能的集大成者和统治者，同时还存在一些让人类同样叹为观止的生 物群体智能现象。蜂巢之精美，蚁群之有序，大雁队伍之和谐，这些群居生物所体现的 社会性和分布式智能实现模式确实值得我们人类学习。在这些群居生物中虽然每个个体 的智能不高，行为简单，也不存在集中的指挥，但由这些单个的个体组成的群体，似乎 在某种内在规律的作用下，可表现出异常复杂而有序的群体行为。 作为协作实现群体智能的每个悠闲智能体，如果要是群体智能的实现更有意义，他 在运动和计算过程中所感知的信息和所遵循的知识提取规则、局部的屯讯交互模式及总 体行为规则应该具有简单性的特点，同时期总体智能化的实现程度还取决于智能协作的 成熟程度。群体智能的研究工作主要包括群体智能心想的行为模拟、群体智能计算模式 研究和分布式问题求解策略等方面。群体智能计算模式研究的具体内容主要包括群体智 能算法设计与改进和群体智能算法在优化问题求解一级工程领域宏的应用。相关研究框 图如下图所示。 群体智能研究 群体智能现象的行为模拟 体实 模现 型仿 真 具 群体智能计算模式研究 改算 进法 设 计 及 算 法 应 用 分布式求解策略研究 策分 萋橐 解 。图1 - 1 群体智能算法研究图 f i g l 1 t h ea r c h i t a c t u r eo f s w a r mi n t e l l i g e n ta l g o r i t h m s 群体生物表现出来的智能现象受到很多学者的关注与重视，诸多计算机专家、仿生 学家、生物学家开始研究这些具有社会特性动物( 蚂蚁、鱼群、鸟群) ，力图创建能够 用于解决人类社会总一些难题的模型。比较有影响力的研究有19 8 6 年c r e y n o l d s 建立 江南大学硕士学位论文 的b o i d 模型，该模型对鸟类的聚集行为、群体飞行行为进行了模拟，在计算机中复制 和重现了实现世界中鸟类飞行、聚集性行为。 生物学家f h e p p n e r 等也开发了一种鸟群飞行模型，该模型与b o i d 在反应群体行 为方面有许多相同之处，不同之处在于它更注重对鸟群趋同行行为的研究。 1 9 8 9 年s g o s s 等进行了著名的双桥实验，实验表明蚂蚁总能够找到距离巢穴与食 物之间的最短路径。1 9 9 1 年m d o r i g o 等根据双桥实验提出了著名的蚂蚁算法，标志着 群体智能研究的诞生。此后19 9 5 年j k e n n e d y 与r c e b e r h a r t 在r e y n o l d s 和f h e p p n e r 的鸟群聚集模型基础上提出了p s o 算法；群体智能算法研究已经成为一门热门的研究 领域。 虽然从提出群体智能概念至今已有2 0 年，但是它仍然是一个新兴的领域，还有更 多的理论等待后人去开发，还有更多的领域等待我们去应用。 1 4 2 群体智能的基本特征 1 、自组织 自组织理论最早由哈肯教授提出，他是- i - j 涉及物理学、生命科学、化学甚至社会 科学的新兴基础学科。自组织是相对他组织而言的，所谓他组织就是要有一个系统以外 的组织者，通常表现为事前有一个既定的目标，有一定的计划和方案等。在由众多分散 的结构简单有高度自治的个体组成的群体智能系统中，我们无法在系统外找到组织者， 实际过程是在一定的外界条件下，个体通过遵循一定的规则自发地组织起来的，形成一 定的结构。在蜜蜂、黄蜂、白蚁等生物群体虽然没有一个统一的协调领导者，每个个体 按照相对简单的行为机制运作，整个群体却能形成及其复杂的结构，完成筑巢、做清扫、 搞运输等复杂的社会活动。 群体智能自组织的特征主要涵盖两个方面的内容：( 1 ) 强调系统内部元素相互作用 与相互影响，内部元素在群体智能系统中是指个体与个体，个体与环境。( 2 ) 系统内部 规则不受外界影响，通过发展进程中随机事件凸显整体系统特性，是一种宏观层面上规 律性现象。 2 、自适应 从生物学的角度，所谓自适应是指生物能改变自己的习性以适应新的环境的一种特 征。自适应是对自己组织过程的一种描述，在一定的环境下，个体通过自组织过程适应 环境，而出现新的结构、状态或功能。 在目前研究的群体智能系统中，由于每个个体自身知识的不足以及不同个体所面临 的问题之间具有相互依赖性，所以有时并不能单独地解决某个问题，而需要一个系统中 多个个体之间的协作。正是出于这种考量，当系统中某个个体出现故障时，他所承担的 任务可由其他个体负责，整个系统具有较好的适应性。这种适应性在群居行社会生物系 统中体现的非常明显。 群体生物的这种自适应性是生物与环境长期以来相互制约相互影响的结果，是自然 选择与进化的结果，他保证了生物的生存和发展。群体的这种自适应性，使得群体智能 较之传统人工智能具有更好的健壮性、容错性、鲁棒性。 4 第一章绪论 3 、间接通信 在蜜蜂觅食的过程中，当工蜂返巢时会在蜂房的一侧表演舞蹈，以此向同伴传递信 息。其他工蜂通过舞蹈动作的变化能够得知食物来源的方向距离和丰富程度。蚂蚁在觅 食过程中，当蚂蚁发现了一条通往食物的路径，他就会向该路径上释放一定量的化学物 质信息素，随后的蚂蚁具有感知信息素浓度的能力，他会根据信息素的浓度来选择他 将要移动的方向。将这种生物用来调整它们行为的一种特殊的间接交流方式称为间接通 信。间接通信中涉及到个体的行为与相关的刺激信号两部分。正是因为群体智能中个体 间间接通信的存在，智能群体随着个体数目的增加整个系统的通信开销的增幅比较小， 以此群体智能系统具有较好的可扩充性。 4 、涌现 涌现e m e r g e n c e 又称突现，它主要阐述的激励就是为什么1 + 1 2 即整体大于部分之 和。涌现作为生活中的普遍现象存在我们的生活周围，单个蚂蚁其智能非常简单，然而 多个蚂蚁形成一个群体的时候，就表现出了智能。蚁群不仅能够找到食物，而且能够找 到距离食物最近的路径，还能够形成有序的社会学秩序。 涌现可以说是群体智能的本质特征，没有涌现现象的系统就不是群体智能系统。在 群体智能系统中，涌现是作为总体系统行为从多个个体间相互作用中产生出的系统论的 泛称，是一种从个体的鼓励行为中无法预见，甚至无法想象的行为，它是一种由小生大， 由简入繁的过程。所以对于涌现的研究必须既要研究群体单个个体的行为，又要研究个 体与个体间的相互作用。 群体智能用线性是由规模效应和结构效应共同产生的结果。规模效应是指群体智能 系统中，必须要有一定规模的个体，对他的数量有一定的要求。结构效应是指群体智能 系统组织结构。群体智能都要具有中央基础控制的体系结构，群体智能中个体的地位是 平等的，个体间不存在控制与被控制的关系。 1 4 3 常见群体智能算法及其进展 基于群体智能的思想，学者先后提出了多种群体智能算法，比较典型的蚁群算法和 p s o 算法。 模拟生物蚁群智能优化算法蚁群算法是m d o r i g o 等人在1 9 9 0 年首先提出。他充分 利用了生物蚁群能通过个体间简单通信传递，搜索从蚁穴到食物间最短路径的集体寻优 特征，以及该过程与旅行商问题之间的相似性，得到了具有n p 难度的旅行商问题的最 优解答，同时该算法还被用于求解j o b s h o p 调度问题，二次指派问题以及背包问题等， 显示了其适用于组合优化类问题求解的优越特征。蚁群算法之所以能引起相关领域研究 者的注意，是因为该种求解模式能将问题求解的快速性、全局优化特征以及有限的时间 内答案的合理性结合起来。而其分布式计算的特征又避免了算法的早熟性收敛。 模拟鸟群运动的智能微粒群算法是j a m e sk e n n e d y 和r u s s e l le b e r h a r t 于19 9 5 年提 出，其基本思路是在问题的定期空间内，首先将一定数量的等位微粒作随机分布，然后 根据各个微粒在解空间中所处地位的相关信息，将微粒依次排序，对单个微粒运动的最 优历史信息做好记录，直到微粒群找到了问题的最优解或者满足其它相关的停止条件。 5 江南大学硕士学位论文 目前对群体智能的研究尚处在初始阶段，但是由于其所具有的分布式、自组织、协 作性、鲁棒性和实现简单方便等特点，使其在没有全局信息的情况下，为寻找次优解决 方案提供了快速可靠的基础，为典型系统复杂性问题的求解开辟了新的途径。因此群体 智能的研究具有重要的意义和广阔的应用前景。 1 5 生物序列比对 1 5 1 生物序列比对的意义 生物序列比对问题是生物信息学的一个基本问题，也是数学与生物学的一个重要汇 合点，他是数学理论在生物学中得到成功应用的典范。然而随着d n a 测序方法的飞速 发展，生物序列信息量急速上升，使得可供比较的序列数量呈现爆炸式增长。而为了发 现这些序列之间的进化关系、预测基因和蛋白质的功能与结构，就需要对这些序列进行 分析。生物序列一般分为d n a 、r n a 、蛋白质序列，其中蕴含了大量的生命现象。生 物序列分析的最终目的就是发现不同生物序列的保守区域和变化的规律，进而发现这些 d n a 和蛋白质的功能特征。比如：序列机构变化与病变的关系问题、基因的定位问题、 重复序列的搜索问题、基因组的拼接问题。同时其在遗传病、生物进化、流行病毒的研 究中也举足轻重，比如通过序列比对可以了解不同物种的进化与遗传过程，也可以了解 流行病的病原发展传播情况，从而为开发病毒疫苗和治疗药物提供帮助。可见，生物序 列比对在医学、生物学的研究中有重要意义，是近代医学、生物学研究中的利器。 另外生物实验室确定一个生物大分子的结构或功能最直接可靠的方法就是在实际上 得到一条与r n a 或蛋白质相对应基因的d n a 序列，远比通过实验确定它的结构或功能 要容易的多，这就强烈地促使我们去发展一些计算学方法，使得研究者们仅仅从生物序 列就可以推断其生物学的信息，比如进化关系，功能结构等等。伴随着各种基因组计划 的到来，计算学方法变得尤其重要据估计，仅人类基因组计划就能产生7 0 0 0 0 到 1 0 0 0 0 0 条人类基因的原始序列，而其中已经通过实验研究的仅占一小部分。从本质上 讲，大多数计算序列分析问题都是统计学问题随机进化力作用于基因组，并对其产生 影响。序列在随机突变、自然选择和遗传漂变的混沌之中长期分化，因此就如何辨识序 列间的显著相似性提出了一个严重的信号噪声问题。许多强大的现有分析方法都使用概 率论。因此很多基于概率论的生物计算模型被人们提出。 综上所述，生物信息学中的序列比对算法的研究具有非常重要的理论意义和实践意 义。 1 5 2 序列比对算法研究的进展与存在的问题 多重序列比对的最优解问题在一些文献中被称为一个非易计算问题或者说是生 物计算中第一未解决的问题，文献 1 6 , 1 7 , 1 8 】把它归为n p 难题与m a x s n p 难题，把它的计 算复杂度确定在0 ( 2 “i n n ) 范围( 其中，m ，n 分别为多重序列的重数与长度) ，因此理论上实现 多重序列的比对最优解的计算是一个非常困难的问题。由于多重序列比对在生物信息学 中的重要性，近些年出现了很多的比对算法和软件比如m u l a l i n ，c l u s t a l w , h m m e r ， p o a ，t c o f f e e 等，但是这些算法或者软件大多数只针对少量的长序列或者大量的短序 列，比如经典的c l u s t a l w , h m m e r ，m u l a l i n 和新出现的p o a ，t c o f f e e 是针对大量的l k b p 6 第一章绪论 左右的短基因序列，如果序列长度达到l o k b p ，则计算时间长的不能接受( 超过一周) ， 针对大量的长序列目前尚没有有效的算法和软件出现，问题就在于多序列比对求最优解 复杂度太高。人们每天都要进行成千上万次的序列比对和数据库搜索，而不断增大的数 据库容量、序列长度等给人们带来了新的的挑战【1 1 , 1 2 。因此我们有必要对序列比对算法 研究的进展与目前所存在的问题做一下介绍。 1 、序列比对算法研究进展 序列比对的动态规划算法最早由n e d l e m a n 与w u n s c h 提出，其基本思路是把需要比 对的两条序列按纵、横坐标方向排列，再把每个纵、横坐标的罚分数或得分数做出标记， 在用设当补充的插入虚拟符号给以连接，从而改成不同的比对方案，在从这些不同的比 对方案中选取罚分最小或者得分最多的最优方案为序列比对的最优解决方案。2 0 世纪 8 0 年代，s m i t h 与w a t e r m a n 提出了另外一种基于动态规划的序列比对算法【1 3 , 1 4 , 1 5 】，但是 和n c e d l l c m a n - w a t e r m a n 算法有所不同，s m i t h 的算法是一种局部比对算法。它可以对 局部比对结果进行连接，从而形成全局最优比对。但是其基本思想都是基于动态规划算 法。 n e c d l l e m a n w a t e r m a n 算法的出现使得比对算法的研究成为生物信息学中的一个热 点，大量文献研究了对s m i t h w a t e r m a n 算法的改进讨论，同时研究了蛋白质序列比对 算法的应用。蛋白质序列的比对问题比基因序列比对要复杂，主要是相似性的得分函数 举证的确定，存在多个得分函数举证系列，如p a m 系列与b l o s u n 系列。其中p a i v l 系列的得分矩阵按相同氨基酸得分为最高，其次是同源蛋白和保守区所对应的氨基酸， 再次是同源蛋白质非保守区对应的氨基酸。而b l o s u n 系列的得分恶略与p a m 基本相 同，但是取样数据来自b l o c k s 数据库。采用不同的得分矩阵有时会得出不同的比对 结果。 比对算法除了向蛋白质比对方向发展外，他们的应用，特别是在数据搜索等领域中 的应用，并由此产生的大型软件包特别引人注意。目前国际上所发展的大型软件包有数 十种之多，如著名的b l a s t 与f a s t a 等已经是全世界共同能用，且在网络上公开、免 费使用。利用数据库搜索而发现的病毒肿瘤基因v s i s 是细胞中编码血小板遗传因子的 变体，这就是比对搜索在生物学中功应用的一例。 s m i t h w a t e r m a n 算法虽然比n e e d l l e m a n w u n s c h 算法简单，但其基本思路都出自动 态规划，因此他们时间复杂度也是关于序列长度的二次函数，当序列长度比较小的时候， 算法是有效的，但是当序列的长度在1 0 m b p 以上，此类算法将耗费大量时间，如序列 长度超过1 0 m b p 序列的比对就非常困难，而对这样长度规模序列的搜索就不可能了。 2 、序列比对算法存在的问题 序列比对算法与分析目前主要存在以下问题，通过对比说明如下： ( 1 ) 多序列比对 多重序列比是生物信息学中的一个非易计算问题，文献 1 6 , 1 7 , 1 8 】把它归为n p 难题与 m a x s n p 难题，把它的计算复杂度确定在o ( 2 n m n ) 范围( 其中，m ，n 分别为多重序列的 重数与长度) ，因此理论上实现多重序列的比对最优解的计算是一个非常困难的问题。目 7 江南大学硕士学位论文 前能够进行比对的软件大多有条数和长度的限制，至今没有算法可以有效处理大量长序 列的序列比对，因此寻找多重序列比对的快速算法是其中第一问题。 ( 2 ) 不同比对算法评优 目前有大量的序列比对软件出现，如何对这些软件效果进行评优也是一个重要的问 题。要对比就要有一个评价准则和标准，因此需要从算法的多个方面进行综合评价，比 如算法的时间复杂度、空间复杂度、算法的比对结果的准确程度等等都是评价标准应该 反映的问题。建立一个评价标准能够准确说明算法好坏，在生物信息学中的最常用的准 则是进行实际测试，把几种算法在某种数据库中进行实际计算所获得的各种不同类型的 度量指标的大小比较作为对这些算法好坏或者特点比较的主要依据。对不同比对算法的 各种度量指标进行实际测试，是不可缺少的一种度量方法，但是仅这一种方法还是不够， 还需要有需要理论分析的支撑，因为理论分析要求对算法的设计、所针对的目标对象与 算法的建立有一个理论可行或者合理的结论论述，这些结论不仅为该算法本身的合理 性、所使用的范围、运用时所需要注意的问题等进行说明，也为该算法的使用者如何使 用及如改进所需要。对于序列突变与比对的数学模型也不是完全没有规律可循，这还有 待于学者们进一步研究发现其中隐藏的客观规律。 1 5 3 智能优化算法在m s a 中的应用 由于多重序列比对在生物信息学中的重要性，近些年出现了很多的比对算法和软件 比如m u l a l i n ，c l u s t a l w , h m m e r ，p o a ，t c o f f e e 等待，但是这些算法或者软件大多数是只能 对少量的长序列或者大量的短序列，比如经典的c l u s t a l w , h m m e r ，m u l a l i n 和新出现的 p o a ，t c o f f e e 是针对大量的l k b p 左右的短基因序列，如果序列长度达到1 0 k b p ，则计 算时间长得不能接受( 超过一周) ，针对大量的长序列目前尚没有有效的算法和软件出 现，问题就在于多序列比对求最优解复杂度太高。 智能算法是解决最优化的一种新途径，它能够在在有限的时间内获得比较满意的次 优解，因此近年来，将优化算法应用于序列比对的研究逐渐多了起来。 c d d f i cn o t r e d a m e 和d e s m o n dg h i g g i n s 于19 9 6 首次将遗传算法用于多序列比对， 并开发出了基于该遗传算法的多序列比对软件s a g a 1 9 】。蚁群算法是群体智能算法中的 一种，它适合求解大规模复杂的组合优化问题，文献【2 0 】中将蚁群算法用于多序列比对， 表现出了智能算法在该问题中的优点