（控制理论与控制工程专业论文）基于带变异算子粒子群的多序列比对算法研究与应用.pdf

摘要 摘要 序列比对是生物信息学中一项重要的基础性研究课题，多序列比对则是其最基本任务之 一。由于各种原因，目前还没有一个最佳的多序列比对算法。在研究比较了现有的多序列比 对算法的基础上，本文首次提出了使用带变异算子粒子群优化算法来解决多序列比对问题。 本文首先分析了空位罚分、替换矩阵和目标函数对序列比对的影响，具体实现s p 和 c o f f e e 目标函数。然后通过对多序列比对算法的现状的研究以及对粒子群优化算法特点等 的分析，实现了基于粒子群优化算法的多序列比对算法m s a p s o ( ap a r t i c l es w a r m o p t i m i z a t i o nd e d i c a t e df o rm u l t i p l es e q u e n c ea l i g n m e n t s ) ，提出了基于带变异算子粒子群优化 算法的多序列比对算法m s a v p s o ( av a r i a t i o n - o p e r a t o rp a r t i c l es w a r mo p t i m i z a t i o nd e d i e a t e d f o r m u l t i p l es e q u e n c e a l i g n m e n t s ) ，并分别实现了基于s p 和c o f f e e 目标函数的m s a p s o 和 m s a v p s o 。最后用基准多序列比对库b a l i b a s e l 0 中的用例对算法进行测试，结果表明 m s a v p s o 算法在解决基因序列比对问题上是有效的。 关键词：生物信息学多序列比对目标函数粒子群优化算法变异算子 a b s t r a e t a b s t r a c t s e q u e n c ea l i g n m e n to fb i o i n f o r m a t i c si s a ni m p o r t a n tf u n d a m e n t a ls u b j e c ti nb i o i n f o r m a t i c s r 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 a l s ot h e r ei sn o ta no p t i m a l a l g o r i t h mo fm u l t i p l es 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 p o s e sam e t h o d , w h i c hu s ep a r t i c l e s w a r mo p t i m i z a t i o na n d v a r i a t i o n - o p e r a t o r p 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 m o f e v o l u t i o n a r ya l g o r i t h m ，t 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 , t h ee f f e c to ns 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 xa n d o 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 ef u n c t i o na r e i m p l e m e n t e d t h e nt h ed y n a m i cp r o g r a m m i n ga l g o r i t h mt h a ti so n eo fa c c u r a t ea l g o r i t h m so f p a i r w i s ea l i g n m e n ti ss t u d i e da n di m p l e m e n t e d 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 e m 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 ma n dt h ea n a l y s i st ot h ep r i n c i r l ea n dc h a r a c t e r i s t i co ft h e g e n e t i ca l g o r i t h ma n 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 ds oo n , p r e s e n tt h em u l t i p l e s e q u e n c ea l i g n m e n t sa l g o r i t h mb a s e do np 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 mm s a p s o ( a p a r t i c l es w a r mo p t i m i z a t i o nd e d i c a t e df o rm u l t i p l e s e q u e n c ea l i g n m e n t ) a n dt h em u l t i p l e s e q u e n c ea l i g n m e n t sa l g o r i t h mb a s e do nv a r i a t i o n - o p e r a t o rp 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 v p s o ( av a r i a t i o n - o p e r a t o rp a r t i c l es w a r mo p t i m i z a t i o nd e d i c a t e df o rm u l t i p l es e q u e n c e a l i g n m e n t ) a l s ot h et w oa l g o r i t h m sb a s e do ns 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 ni si m p l e m e n t e d f i n a l l y , t w oa l g o r i t h m sa r eu s e dt ot e s tb e n c h m a r km u l t i p l es e q u e n c e a l i g n m e n t sd a t a b a s eb a l i b a s e l 0 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 v a p s oa l g o r i t h mi s f e a s i b l et os o l v et h ep r o b l e mo fs e q u e n c ea l i g n m e n t k e y w o r d s ：b i o i n f o r m a t i c 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 ，p a r t i c l es w a r m o p t i m i z a t i o n ，v a r i a t i o n - o p e r a t o r i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：是兰：垫：日期：沙印年；月，矿日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 日期。如一7 年弓月，矿日 第一章绪论 1 1 问题的提出 第一章绪论 本课题的依托项目是教育部科技基础条件平台建设计划( 5 0 5 0 0 6 ) 和国家科技部科技资源 平台建设计划( 2 0 0 5 d k a 2 1 2 0 8 4 ) “工业微生物资源数据库”项目。该平台旨在建设一个数据 结构统一的、公益性的、开放性的和交互式的工业微生物资源数据库。本课题组主要负责项 目中数据库和网络的设计和实施，并设计制作一些具有自主产权的生物信息学相关软件，其 中包括多序列比对软件和信号肽查询软件。目前，中国高校工业微生物资源数据平台已经顺 利运行。同时，针对课题实施进程中出现的一些问题我们从理论和实际两个方面进行了深入 研究，并得出了具体的解决方案。 生物信息学( b i o i n f o r m a t i c s ) 【l j 从2 0 世纪8 0 年代末逐渐兴起并蓬勃发展。近年来，计算机 和i n t e m e t 的发展为生物信息学的发展和传播提供了硬件基础和条件。生物信息学是在生命科 学的研究中以数学和计算机科学为依据手段对生物信息进行存储、检索和分析的学科，它是 当今生命科学与自然科学的重大前沿领域之一，同时也将是2 1 世纪自然科学的核心领域之一。 生物信息学的研究重点主要体现在基因组学和蛋白质学两个方面。随着生物技术的提高，功 能基因组和蛋白质组的大量序列数据己开始涌现，目前基因组学的研究己转到基因序列的研 究上。在生物信息学中得到生物序列仅仅是第一步，如何分析这些序列，从中获得生物结构、 功能的相关信息是基因组研究取得成果的决定性步骤。 自从1 9 9 0 年美国启动人类基因组计划( h g p ，h u m a ng e n o m ep r o j e e t ) 以来，人类模式生物 基因组的测序工作进展极为迅速。截止目前为止，仅登录在美国g e n b a n k 数据库中的d n a 序列 总量已超过7 0 亿碱基对。今后d n a 序列数据的增长将更为惊人。生物学数据的积累并不仅仅 表现在d n a 序列方面，与其同步的还有蛋白质的一级结构，即氨基酸序列的增长。迄今为止， 己有一万多种蛋白质的空间结构以不同的分辨率被测定。基于d n a 序列测序所建立起来的 e s t 数据库其纪录己达数百万条。在这些数据基础上派生、整理出来的数据库已达5 0 0 余个。 这一切构成了一个生物学数据的海洋。这种科学数据的急速增加和海量积累，在科学研究历 史中是空前的。如何分析这些数据，从中获得生物结构、功能的相关信息是基因组研究取得 成果的决定性步骤。美国人类基因组计划实施五年后的总结报告中，对生物信息学作了以下 定义：生物信息学是一门交叉科学，它包含了生物信息的获取、处理、存储、分发、分析和解 释等在内的所有方面，它综合运用数学、计算机科学和生物学的各种工具，来阐明和理解大 量数据所包含的生物学意义 2 1 。 比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。 序列分析在基因工程和分子生物学研究中一直是一项重要的手段，也是该领域最重要的技术 之一，是了解基因组结构和功能的基础途径。而在序列分析中基本的方法是序列比对，而多 序列比对又是分析生物序列的最重要的工具之一。序列比对是两个或者多个蛋白质序列之间 或核酸序列之间的比较，分析他们的相似性和同源性，寻找有进化关系的序列之间共同的保 1 江南大学硕士学位论文 守区域、位点和p r o f i l e ，从而探索导致它们产生共同功能的序列模式。此外，还可以把蛋质 序列与核酸序列相比来探索核酸序列可能的表达框架；把蛋白质序列与具有二维或三维结构 信息的蛋白质相比，从而来预测蛋白质的二级或者三级结构。近年来随着生物信息学数据大 量积累和生物学知识的整理，通过序列比对可以有效地分析和预测一些新发现基因的功能。 序列比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进行比较， 从数据库中获得与其最相似的己有的序列数据，能最快速的获得有关查询序列的大量有价值 的参考信息，对于进一步分析其结构和功能都会有很大的帮助。 对于构成基因家族的成组的序列来说，我们要建立多个序列之间的关系，这样才能揭示 整个基因家族的特征。由于可以提高序列比对的信噪比，多序列比对在阐明一组相关序列的 重要生物学模式方面起着相当重要的作用。 从某种意义上来说多序列比对是生物序列分析的最重要工具，甚至可以说是生物信息学 的基础。 1 2 研究现状 多序列比对是进行生物序列分析的最基本的任务之一，它在发现序列模( m o t i f ) 和保守区 域、系统发育分析、结构预测等方面具有重要的作用，是生物信息学当前研究的热点问题之一。 已有的多序列比对算法大体可以分三类：精确比对算法、渐进比对算法、迭代比对算法。精确 比对算法最为经典的是多维n e e d l m a n w u n s c h t 3 l 算法，但其可行的计算维数为3 ，c a r r i l l o l i p m a n1 4 1 算法通过减小计算空间，将计算维数提高到1 0 。渐进比对算法i 扫h o g e w e g q 首先提出， f e n g i q 和t a y l o r | 7 1 又加以完善。非常著名的、被广泛使用的多序列比对软件包c l u s t a l w l s l ( 其 含窗口界面的版本c l u s t a l x ) 基于渐进比对思想构建。 近年来，迭代比对算法被越来越多地用于求解多序列比对问题，基于模拟退火、遗传算法、 h m m s 、g i b b s 抽样等的多序列比对算法被广泛应用于多序列比对问题的求解，其中多序列比 对软件包s a g a 9 1 基于遗传算法构建，算法中共设计了2 2 种不同的遗传算子，采用动态调度 的策略控制2 2 种遗传算子的使用。p h g a ”1 采用了并行的混合遗传算法来求解问题，将问题表 示成求解k 维带权有向图的最短路问题，而设计了与之相应的一维染色体编码方式。文献【l l 对 多种多序列比对方法和与之相应的软件的性能进行了详细的比较。 由于多序列比对自身的特点和难点，结果精确的多序列比对很难得到。在多个长序列比 较时候尤其难以得到，主要有以下两个原因： 首先，我们很难对多序列比对的质量进行评估，因为多序列比对不存在一个最优值。对 同一组序列进行比较，同样的参数也可能出现不同的结果，所以在设计算法的时候我们要对 这个问题做一些处理。在多序列比对的过程中，可以说是“没有最好，只有更好”。 其次，即使有一个函数可用来评估，算法上又很难构造出有最好的可能得分的比对( 最佳 的比对) 。多序列比对的方法是建立在某个数学或生物学模型之上。因此我们不能对双序列比 对的结果得出“正确或错误”的简单结论，多序列比对的结果也没有绝对正确和绝对错误之 2 第一章绪论 分，而只能认为所使用的模型在多大程度上反映了序列之间的相似性关系以及它们的生物学 特征。 在过去的2 0 年里，多序列比对的算法一直在不断增加。但是要指出的是，在文献中描述 的算法中只有其中的一小部分现在经常使用，大部分都失败了。这有很多原因，其中一个主 要原因是来自一个简单的事实：序列比对没有一个合适的理论框架，在这个意义上一个算法 的好坏就只能由结果来决定。在多序列比对领域算法得到改进的动力是结果而不是理论，以 至于那些没有很好的界面和移植性的程序被自然淘汰，而它们核心的算法却在后来被重复的 提出。 在过去的几年里多序列比对领域由于几个新的算法和方法的出现而经历了较大的改变。 有两个个主要的趋势： 越来越多的算法用到迭代的优化策略( 包括随机的和非随机的) ； 基于一致性的评价体系的应用。 目前多序列比对仍然缺乏快速而又十分有效的算法。对于具有较高相似性的一组序列之 间的比对，自动比对算法是很有效的。但一旦序列的亲缘关系变得较远，所得结果就不那么 可信。 1 3 本课题主要研究内容 本课题的主要内容是带变异算子粒子群算法在多序列比对算法中的研究与应用，课题主 要做了以下几个方面的工作： 首先，比较研究了现在经常使用的一部分序列比对算法，对它们的核心算法做了有针对 性的比较和研究，分析了现有算法存在的问题，并且就这些问题做了讨论并提出了改进的方 案。 然后，在以上研究的基础上实现了基于粒子群优化算法的多序列比对算法，分别使用即 日标函数和c o f f e e 目标函数实现上述法，使用基准多序列比对库b a l i b a s e 中的用例对 提出的算法进行测试，对其实验结果进行比较和分析，在分析了其优缺点之后，有针对性的 引进了带变异算子粒子群优化算法，利用带变异算子粒子群优化算法可以改良粒子群优化算 法局部收敛问题的优点对以前的多序列比对算法加以改进。 最后，通过实验结果对算法进行评价，并结合其它经典算法与之进行比较并做出了具体 的分析。 在课题进行的同时，本人负责了中国高校工业微生物资源数据平台的设计和实施，并制 作了多序列比对软件和多肽查询软件。 论文内容具体安排如下： 第一章主要介绍课题的背景、研究现状及立题依据，提出了笔者的课题计划，并简要说 明了笔者所做的主要工作。 第二章首先分析了序列比对中所涉及到的一些问题、概念以及对序列比对的影响，包括： 江南大学硕士学位论文 空位罚分、替换矩阵和目标函数等。然后深入分析了序列比对的双序列比对和多序列比对问 题。对序列比对的经典算法和近年来比较新的比对算法及其发展动态做了深入研究和比较， 指出了各种算法的优点和缺点，并分析了带变异算子粒子群优化算法在多序列比对研究中应 用的可行性。 第三章首先介绍了基本粒子群优化算法的背景和程序设计步骤。然后在此基础上介绍了 带变异算子粒子群优化算法，并对其特点和程序设计步骤做了详细的介绍。 第四章本章主要分两部分。首先实现了基于粒子群优化算法的多序列比对算法，并对其 比对结果做了对比分析。然后在此基础上设计了带变异算子粒子群多序列比对算法，然后使 用基准多序列比对库b a l i b a s e l 0 中的用例对所提出的算法进行测试，最后通过试验结果对 算法进行评价分析。 第五章全文进行总结并指出不足之处和今后的研究方向。 参考文献 【1 】a t w o o dt k e la 1 l u oj i n - c h ue t a 1 t r a n s l a t e i n t r o d u c t i o nt ob i o i n f o r m a t i c s b e i j i n g ：p e k i n g u n i v e r s i t yp r e s s ，2 0 0 1 ( i nc h i n e s e ) ( a t t w o o dt kp a r r y s m i t hd j 著，罗静初等译生物信息 学概论北京：北京大学出版社，2 0 0 2 ) 2 】尚彤，张丹生物信息学概论，北京大学学报( 医学版) ，2 0 0 1 ，3 3 ( 1 ) ：9 2 9 5 3 】n e e d l e m a ns u ，bw u n s c hc d ag e n e r a lm e t h o da p p l i c a b l et ot h es e a r c hf o rs i m i l a r i t i e si n t h ea m i n oa c i ds e q u e n c eo f t w op r o t e i n s 阴j o u r n a lo f m o l e c u l a rb i o l o g y , 1 9 7 0 ，4 8 ( 3 ) ：4 4 3 - 4 5 3 4 】c a r r i l l oh ，l i p m a nd j 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 nb i o l o g y j s i a m j o u r n a lo na p p l i e dm a th e m a t i c s ，1 9 8 8 ，4 8 ( 5 ) ：1 0 7 3 1 0 8 2 5 】h o g e w e gp ，h e s p e rb t h ea l i g m n e n to fs e t so fs e q u e n c e sa n dt h ec o n s t r u c t i o no f p h y l o g e n e t i e t r e e s ：a ni n t e g r a t e d m e t h o d 阴j o u r n a l o fm o l e c u l a r e v o l u t i o n , 1 9 8 4 ， 2 0 ( 2 ) ：1 7 5 1 8 6 6 】f e n gd 。f d o o l i t t l er f p r o g r e s s i v es e q u e n c ea l i g n m e ma sap r e r e q u i s i t et oc o r r e c t p h y l o g e n e t i ct r e e s j j o u r n a lo f m o l e c u l a re v o l u t i o n ，1 9 8 7 ，2 5 ( 4 ) ：3 5 1 3 6 0 【7 】t a y l o rw r af l e x i b l em e t h o dt oa l i g nl a r g en u m b e r so fb i o l o g i c a ls e q u e n c e s j 】j o u r n a lo f m o l e c u l a re v o l u t i o n , 1 9 8 8 ，2 8 ( 1 2 ) ：1 6 1 1 6 9 【8 】t h o m p s o nj d ，h i g g i n sd g a n dg i b s o nt j c l u s t a l w ：i m p r o v i n gt h es e n s i t i v i t yo f p r o g r e s s i v em u l t i p l es e q u e n c ea l i g n m e n tt h r o u g hs e q u e n c ew e i g h t i n g ，p o s i t i o n s p e c i f i cg a p p e n a l t i e sa n dw e i g h tm a t r i xc h o i c e j n u c l e i ca c i d sr e s e a r c h , 1 9 9 4 ，2 2 ( 2 2 ) ：4 6 7 3 - 4 6 8 0 【9 】n o t r e d a m ec ，h i g g i n sd g s a g a ：s e q u e n c ea l i g n m e n tb yg e n e t i ca l g o r i t h m 叨n u c l e i c a c i d sr e s e a r c h ，1 9 9 6 ，2 4 ( 8 ) ：1 5 1 5 1 5 2 4 1 0 】n g u y e nh d ，y o s h i h a r al 。a l i g n i n gm u l t i p l ep r o t e i ns e q u e n c e sb yp a r a l l e lh y b r i dg e n e t i c a l g o r i t h m j t o k y o ，j a p a n ：u n i v e r s a la c a d e m yp r e s s ，2 0 0 2 ，1 2 3 1 3 2 11 】t h o m p s o nj d p l e w n i a kf ，p o c h0 ac o m p r e h e n s i v ec o m p a r i s o no fm u l t i p l es e q u e n c e a l i g r m a e u tp r o g r a m s j 】n u c l e i ca c i d sr e s e a r c h , 1 9 9 9 ，2 7 ( 1 3 ) ：2 6 8 2 - 2 6 9 0 1 2 】d a v i db s e a r l s ，u s i n gb i o i n f o r m a t i c s i n g e n ea n dd r u gd i s c o v e r y j ，d d t ，2 0 0 0 4 第一章绪论 5 ( 4 ) ：1 3 5 1 3 9 【1 3 】t j i a n ga n dl w a n g o nt h ec o m p l e x i t yo fm u l t i p l es e q u e n c ea l i g n m e n t j j c o m p b i 0 1 ， 1 9 9 4 ，( 1 ) 3 3 7 3 4 8 【1 4 】k a n e h i s a , p o s t - g e n o m ei n f o r m a t i c s ，o x f o r du n i v p r e s s ，2 0 0 0 ，6 - 9 【1 5 】m o d a y h o f , r m s c h w a r t z ，a n db c o m u t t am o d e lo fe v o l u t i o n a r yc h a n g ei np r o t e i n s a t l a so f p r o t e i ns e q u e n c ea n ds t r u c t u r e j ，1 9 7 8 ，5 ：3 4 5 3 5 2 【1 6 】a k r o g h , 1 m i a n , a n dd h a u s s l e r ah i d d e nm a r k o vm o d e lt h a tf i n d sg e n e si ne c o l id n a 阴 n u c l e i ca c i d sr e s e a r c h , 1 9 9 4 2 2 ：4 7 6 8 - 4 7 7 8 1 7 】j d t h o m p s o m ，d g h i g g i n s ，a n dt j g i b s o n , c l u s t a l w ：i m p r o v i n gt h es e n s i t i v i t yo f p r o g r e s s i v em u l t i p l es e q u e n c ea l i g n m e n tt h r o u g hs e q u e n c ew e i g h t i n g ，p o s i t i o n - s p e c i f i cg a p p e n a l t i e sa n dw e i g h tm a t r i xc h o i c e j ，n u c l e i ca c i d sr e s e a r c h , 1 9 9 4 ，2 2 ：4 6 7 3 - 4 6 8 0 【18 】d f f e n ga n dr f d o o l i t l e ，p r o g r e s s i v es e q u e n c ea l i g n m e n ta sap r e r e q u i s i t et o c o r r e c t p h y l o g e n e t i ct r e e s j ，j o u r n a lo f m o l e c u l a re v o l u t i o n , 1 9 8 7 ，2 5 ：3 5 1 - 3 6 0 【1 9 】v a nd e nb e r g hf ，e n g e l b r e c h ta p e f f e c t so fs w a r ms i z eo nc o o p e r a t i v ep a r t i c l es w a r m o p t i m i z e r s 【c 】i n ：p r o eo f t h et l l i r dg e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ( g e c c o ) ， s a nf r a n c i s c o ，u s a , 2 0 0 1 2 0 】k e n n e d yj ，e b e r h a r tr ad i s c r e t eb i n a r yv e r s i o no f t h ep a r t i c l es w a r ma l g o r i t h m i c i e e ei n t c o n f o nc o m p u t a t i o n a lc y b e m e t i c sa n ds i m u l a t i o n , 1 9 9 7 ：4 1 0 4 - 4 1 0 8 【2 1 】c l e r em d i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o ni l l u s t r a t e db yt h et r a v e l i n gs a l e s m a n p r o b l e m c p r o t e i ne x p r e s s i o n & p u r i f i c a t i o n2 0 0 0 ( 1 4 ) 2 4 6 - 2 5 1 【2 2 】v a nd e nb e r g hf ，e n g e l b r e c h ta p an e wl o c a l l yc o n v e r g e n tp a r t i c l es w a l t f lo p t i m i z e r 【a 】 p r o c e e d i n g so fi e e ec o n f e r e n c eo ns y s t e m s ，m a n , a n dc y b e r n e t i c s c h a m m a m e t , t u n i s i a , 2 0 0 2 ：9 6 1 0 1 【2 3 】s h iyh ，e ta 1 e x p e r i m e n t a ls t u d yo fp a r t i c l es w a r mo p t i m i z a t i o n r p r o c e e d i n g so fs c i c o n f e r e n c e ，o r l a n d o ，f l ，2 0 0 0 2 4 】e b e t h a r tr c ，s h iy h e v o l v i n g a r t i f i c i a ln e u r a ln e t w o r k s r p r o c e e d i n g so fi n tc o n f e r e n c e o nn e u r a ln e t w o r k sa n db r a i n , b e i j i n g ，1 9 9 8 ( a ) 【2 5 】e b e r h a r trc ，h ux h u m a nt r e m o ra n a l y s i su s i n gp a r t i c l es w a r mo p t i m i z a t i o n r p r o c e e d i n g so f c o n g r e s so ne v o l u f i o r r a r yc o m p u t a t i o n , w a s h i n g o n , d c ，1 9 9 9 ，1 9 2 7 1 9 3 0 2 6 】f u k u y a m ay ，y o s h i d ah a p a r t i c l es w a r mo p t i m i z a t i o nf o rr e a c t i v ep o w e ra n dv o l t a g e c o n t r o li ne l e c t r i cp o w e rs y s t e m s r p r o c e e d i n g so fc o n g r e s so ne v o l u t i o r r a r yc o m p u t a t i o n ， s e o u l ，k o r e a ，2 0 0 1 【2 7 e b e r h a r trc ，s h iyh p a r t i c l es w a r mo p t i m i z a t i o n ：d e v e l o p m e n t ，a p p l i c a t i o n sa n d r e s o u r c e s r p r o c e e d i n g so f c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n ，s e o u l ，k o r e a ，2 0 0 1 【2 8 】杨粱，徐保国基因工程菌高密度发酵过程中p h 值模糊控制的实现阴计算机工程， 2 0 0 5 ( 1 ) ：3 7 _ 4 1 e i 检索号：0 5 0 9 8 8 6 6 7 5 1 【2 9 】吴晓鹏，徐保国带变异因子粒子群算法在生物发酵中的应用研究叨电测与仪表， 2 0 0 5 ( 7 1 ：4 8 5 2 5 江南大学硕士学位论文 【3 0 熊伟丽，徐保国，孙俊改进的q d p s o 算法在b p 神经网络训练中的应用 j 】系统仿真学 报，2 0 0 5 ，1 7 ( 9 ) ：2 0 7 8 2 0 81 e l 检索号：0 5 3 9 9 3 8 8 9 1 0 6 第二章多序列比对 第二章多序列比对 随着科学的进步，技术的发展，人类对世界的了解越来越多。现在我们对生物的认识已 经进入了一个全新的时代基因组时代。目前，科学家已经破译了人类基因组。这部由3 0 亿个字符组成的庞大的人类遗传密码本已活生生地摆在了我们面前。与此同时，来自其它生 物的基因组信息源源不断从自动测序仪中涌出，堆积如山，浩如烟海。这些海量的生物信息 是用特殊的“遗传语言”染色体的四个碱基字符和蛋白质的2 0 个氨基酸字符写成。如何 分析这些数据，从中获得生物结构、功能的相关信息是基因组研究取得成果的决定性步骤。 一方面是巨量的数据；另一方面是我们在医学、药物、农业和环保等方面对新知识的渴求， 这些新知识将帮助人们改善其生存环境和提高生活质量。两方面构成了一个矛盾，从而催生 了一门新兴的交叉科学生物信息学。 2 1 生物信息学基础知识 生物信息学是一门新兴学科，以获取、加工、储存、分配、分析和释读生物信息为手 段，综合运用数学、计算机科学和生物学工具，以达到理解数据中的生物学含义的目的。下 面简单介绍一下本文所要用到的一些相关知识。 2 1 1 核酸和蛋白质 虽然自然界中的生物种类有成万上亿，但决定它们形态、特性和生命运动的基本生物分 子都是核酸和蛋白质。核酸是遗传信息的携带者，不仅在细胞之间，同时也在生物个体之间 世代相传，而蛋白质是遗传信息转化成生物结构和功能的表达者。 核酸是由四种单体聚合成的一维高分子链，其中每个单体又称为核苷酸。核酸是携带遗 传信息的有机大分子，遗传信息就编码在这些单体的不同排列次序上。核酸根据单体类型的 不同，可以分为脱氧核糖核酸( d e o x y r i b o n u c l e i xa c i d ，d n a ) 和核糖核酸( r i b o n u c l e i xa c i d ，r n a ) 。 脱氧核糖核酸是由腺嘌呤( a ) 脱氧核苷酸、鸟嘌呤( g ) 脱氧核苷酸、胞嘧啶( c ) 脱氧核苷酸、胸 腺嘧啶f r ) 脱氧核苷酸4 种脱氧核苷酸组成的多聚核苷酸链。其中，d n a 核酸的特定序列决 定了生物体结构和功能( 包括蛋白质的种类、结构和功能) ，并以其半保留复制机制，保证世 世代代准确地传递下去。 蛋白质是一种由2 0 种氨基酸通过肽键连接而成的生物大分子。蛋白质结构和功能都是由 核酸根据三联体密码决定的，并在细胞内合成，它参与生物的一切生命活动。因此，将一切 物种核酸或蛋白质序列看作由4 个或2 0 个元素组成的字母表中选出的字母序列( 表2 1 ，表 2 2 ) ，如： a t g g c c a a c t ) ， g s s k y p r e t t 分别表示一条核酸序列或蛋白质序列。生物信 息就是成千上万条以字符序列形式存储核酸或蛋白质序列，并以某些特定格式存放在各类生 物数据库中。 7 江南大学硕士学位论文 表2 1 核苷酸代码 t a b 2 1n u c l e o t i d ec o d e 表2 - 2 氨基酸代码 t i b 2 2a n i m oa c i dc o d e 2 1 2 分子生物学的中心法则 1 9 5 8 年，f r a n c i sc r i c k 首先提出了分子生物学的中心法则1 2 1 ，它很好地说明了核苷酸 和蛋白质这两大类生物大分子之间的信息传递关系。简单地说，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 复制。 2 1 3 空位罚分 基因在进化过程中往往会产生残基的插入或缺失等。有时1 个或者2 个残基的插入或缺 第二章多序列比对 失，有时则是大片段( 如一个结构域) 的插入或缺失。这样，在进行序列比对时，为了更好 地反映序列的相似性，也就必须考虑在序列比对时插入空位，并进行罚分( p e n a l t y ) 。也就是 说，序列比对过程中弓i 入空位时设置的负分，罚分大小可由用户在运行程序时设定，以控制 空位插入的合理性以及达到总体上更好的比对效果。 空位罚分时涉及到两个参数，一个是空位开放罚分( g a po p e n i n gp e n a l t y ) ，一个是空位延 伸罚分( g a pe x t e n s i o np e n a l t y ) 。顾名思义，前者为新空位产生时进行的罚分，而后者则为空 位延伸时进行的罚分。也就是说，每当第一次插入空位时，要进行一定的空位开放罚分，而 连续插入空位时，通常按比例给以稍小的空位延伸罚分。因此，计算一组连续空位罚分( 哌) 公式如2 1 ： 2 口+ b k( 2 - 1 ) 其中，口和b 分别表示空位开放罚分和空位延伸罚分，七是连续空位的总个数。 具体使用时，常数a 和b 的值与所比较的是核酸序列