（计算机软件与理论专业论文）基于自适应免疫遗传算法的多序列比对方法研究.pdf

摘要 序列比对是生物信息学中基本的信息处理方法，随着人类基因组计划的推进得到了 广泛的重视和深入的研究，但是目前还没有一个最佳的多序列比对算法。 近年来，遗传算法的卓越性能引起了人们的关注，并成功地被应用到各种领域的优 化问题中。如何改善遗传算法的搜索能力和提高算法的收敛速度，使其更好地应用于实 际问题的解决中，是各国学者一直探索的一个主要课题。免疫算法作为一种新近受到重 视和发展的计算智能，与其他理论的融合还有很多潜力期待挖掘。免疫算法和遗传算法 结合时，遗传算法的全局搜索能力及免疫算法的局部优化相配合，可大大提高搜索效率。 本文通过对多序列比对算法的研究以及对遗传算法和免疫算法特点的分析，提出了 基于自适应免疫遗传算法的多序列比对算法m s a a i g a ( m u l t i p l es e x i u e n c * a l i g n m e n t b a s e do na d a p t i v ei n l n l u l l eg e n e t i ca l g o r i t h m ) 该算法将自适应遗传算法与免疫算法相 结合，运用遗传算法实现多序列比对问题的遗传操作，该算法中生成初始群体时采用了 星比对算法，这样可以充分利用序列自身的信息，要优于盲目的在序列中插入空位生成 的初始群体，虽然在比对初期会增加时间开销，但是会大大提高比对后期的搜索效率。 遗传算法是全局收敛的，但是遗传算法的交叉算子和变异算子却相对固定，在求解 问题时，可变的灵活程度较小，这样易使遗传算法产生早熟现象，陷入局部极值。因此 本文采用自适应遗传算法，在进化过程中根据种群的实际情况，动态调整交叉概率和变 异概率。自适应遗传算法在保持群体多样性的同时，保证了遗传算法的收敛性，提高了 算法的寻优能力。另外将免疫算法中的免疫算子应用于自适应遗传算法，在保留原算法 优良特性的前提下，更加有效地抑制了优化过程中出现的退化现象。 本文给出了算法的具体步骤，并结合实例证明了其全局收敛性，理论分析及实验结 果证明了这种融合的有效性。 关键词：生物信息学；多序列比对；自适应遗传算法；免疫算法：算子 a b s t r a c t s e q u e n c ea l i g n m e n ti so n eo ft h eb a s ei n f o r m a t i o nd i s p o s a lm e t h o d si nb i o i n f o r m a t i c s r 雠a r c h , w h i c ho b t a i n e da b r o a dr e c o g n i t i o na n dt h o r o u g hs t u d yw i t ha d v a n c eo fh u m a n g e n e sp l a n , b u ta tp r e s e n t , t h e r ei sn o ta l lo p t i m a la l g o r i t h mo f m u l t i p l es e q u e n c ea l i g n m e n t i n “x 脚y e a r s e x c e l l e n tp e r f o r m a n c e so fg e n e t i ca l g o r i t h ma r o u s ea t t e n t i o no fal o to f p e o p l ea n da p p l i e ds u c c e s s f u l l yi nd i f f e r e n td o m a i nw h i c hc a ns o l v eo p t i m i z ep r o b l e m s h o w t oa m e n dr e s e a r c hc a p a c i t ya n d i m p r o v ec o n v e r g e n c es p e e do fg e n e t i ca l g o r i t h m , m a k i n gi t w e l la p p l i e di np r a c t i e a lp r o b l e m ss o l v i n g i ti sam a s t e fp r o b l e mt h a td i f f e r e n tc o u n t r y s c h o l a r sr e s e a r c ha l la l o n g i m m u n ea l g o r i t h mg e ta t t e n t i o na n dd e v e l o p m e n tf l e s h l ya n d p o s s e s s e ss o m e c h a r a c t e r i s t i cd i s t i n g u i s hf r o mo t h e r a l g o r i t h m s c o m b i n i n gi m m u n e a l g o r i t h mw i t hg e n e t i ca l g o r i t h m ，g l o b a lr e s e a r c hc a p a b i l i t yo fg e n e t i ca l g o r i t h ma n dl o c a l o p t i m a lc a p a b i l i t yo f i m m u n ea l g o r i t h ma r ea l li n c r e a s e d t h i sp a p e re d u c e sm 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 na d a p t i v ei m m u n eg e n e t i c a l g o r i t h mb ys t u d y i n gm u l t i p l es e q u e n c ea l i g n m e n ta n da n a l y z i n gt r a i to f g e n e t i ca l g o r i t h m 、 i m m u n ea l g o r i t h m i nt h ea l g o r i t h m , ie d o p t i n gs t a r - a l i g r u n e n ta l g o r i t h mt og e n e r a t ei n i t i a l p o p u l a t i o n , i nt h i sw a y , w em a ym a k et h eb e s to fs e q u e n c e ss e l fi n f o r m a t i o n , w h i c hi sb e t t e r t h a ni n s e r tg a pi n t os e q u e n c er a n d o m l y i tw i l ls p e n dm o t i m ei ni n i t i a l s t a g e s b u t i m p r o v i n gs e a r c h i n ge f f i c i e n c yg r e a t l yi nl a t e ra l i g n m e n t g e n e t i ca l g o r i t h mi sg l o b a lc o n v e r g e i 止b u tc r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o ra r e 丘x e dr e l a t i v e l y ，s ol a c k sa l t e r a b l ea 0 1 i t yd e g r e e ，w h i c hm a k eg e n e t i ca l g o r i t h mg e n e r a t i n g e a r l i n e s sp h e n o m e n o na n dg e t t i n gi n t ol o c a le x t r e m u mm o r ee a s i l y t h e r e f o r et h i sp a p e r a d j u s t sc r o s s o v e rp r o b a b i l i t ya n dm u t a t i o np r o b a b i l i t yd y n a m i c a l l yi nc o u r s eo fe v o l u t i o n b a s e0 1 1p r a c t i c eh l s 舡m 。co fp o p u l a t i o n a d a p t i v eg e n e t i ca l g o r i t h mk e e p sd i v e r s i t yo f p o p u l a t i o n 、e n s u r e sa s t r i n g e n c ya n da d v a n c e so p t i m i z a t i o na b i l i t yo fa l g o r i t h m i na d d i t i o n , i m m u n eo p e r a t o ri sa p p l i e dt oa d a p t i v eg e n e t i ca l g o r i t h m ，i np r e c o n d i t i o no fr e s e r v e c h o i c e n e s sc a p a h i l i t yo fo r i g i n a la l g o r i t h m , r e s t r a i n i n gd e g e n e r a t i o np h e n o m e n o ni np r o c e s s o f o p t i m i z a t i o nm u c hm o r ea v a i l a b l y t h i sp a p e rp r e s e n t sm a t e r i a ls t e p s , p r o v i n gg l o b a lc o n v e r g e n c eb ye x a m p l e s 。it e s t i f yt h e c o m b i n a t i o ni sv a l i db yt h e o r ya n a l y s i sa n de x p e r i m e n to u t c o m e k e yw 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 ；a d a p t i v eg e n e t i ca l g o r i t h m ； i m m u n ea l g o r i t h m ；o p e r a t o r n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 蓟哑 日期：坳。妄丛 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即：东北师范大学有权保留并向国家有关部门或机构送交学位论文的复 印件和磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：虱! ! 尘指导教师签名：蚕骛墨 日 期：碰够日期：竺z 厶= 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 引言 从2 0 世纪8 0 年代末开始，生物信息学这一由生物、数学、物理、化学、计算机科 学、信息科学等多学科交叉产生的新兴学科蓬勃发展，并且逐渐成为2 l 世纪自然科学 的核心领域。生物信息学是一门交叉学科【l 】，它包含了生物信息的获取、处理、存储、 分发、分析和解释等在内的所有方面，它综合运用数学、计算机科学和生物学的各种工 具，来阐明和理解大量数据所包含的生物学意义。 随着人类基因组计划的实施，通过基因测序、蛋白质序列测定和结构分析实验，分 子生物学家提供了大量有关生物分子的原始数据，需要利用现代计算机网络技术对这些 原始数据进行收集、整理、管理，以便于检索使用；而且为了解释和理解这些数据，还 需要对数据进行对比、分析，建立计算模型，进行仿真、预测与验证，这些都促进了生 物信息学的产生和发展。生物信息学已经成为生物医学、农学、遗传学、细胞生物学等 学科发展的强大推动力量。信息学在基因功能发现、疾病基因诊断、蛋白质结构预测、 基于结构的药物设计、药物合成和制药工业中也起着极其重要的作用1 2 1 。因此近年来， 生物信息学这方面的研究取得了较快的发展，并己成为一个热点研究领域。 生物信息学当前的主要研究对象和任务是基因组、蛋白质组、蛋白质结构、数据获 取、数据解释、三维结构预测、数据库构建和检索、药物设计、仪器设计、基因预测、 同源比较、分子建模、分予进化等。目前，绝大部分的核酸和蛋白质数据库由美国、欧 洲和日本的三家数据库系统产生，他们共同组成了d d b j e m b l g e n b a n k 国际核酸序列 数据库，每天交换数据，同步更新。其他一些国家，如德国、法国、意大利、瑞士、澳 大利亚等，在分享网络共享资源的同时，也分别建立了自己的生物信息学机构、二级或 更高级且具有各自特色的专业数据库以及自己的分析技术，服务于本国生物研究和开 发，有些服务也向全世界开放。 我国的生物信息学研究起步较晚，许多机构已经开始从事生物信息学的研究工作。 比如清华大学成立了生物信息学研究所；北京大学建立了一个e m b l 的镜像数据库( 即 完整地将e m b l 的数据库移植过来) ，并提供部分检索服务；复旦大学遗传学研究所， 为克隆新基因而建立的一整套生物信息系统也已初具规模。相信我国生物信息学研究必 将迅速发展壮大。 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是近几年发展起来的一种崭新的全局优化算法， 它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的 适应性的提高。这一点体现了自然界中“物竞天择、适者生存”的进化过程。1 9 6 2 年 h o l l a n d 教授首次提出了遗传算法的思想，从而吸引了大批的研究者，迅速推广到优化、 搜索、机器学习等方面，并奠定了坚实的理论基础。遗传算法现在己被应用到很多领域， l 并取得了很多研究成果，但该算法也存在一些缺点，如早熟和收敛速度慢等。因此随着 遗传算法应用的深入开展，如何对遗传算法进行改进也交得十分重要。 人工免疫系统是由免疫学理论和观察到的免疫功能、原理和模型启发而生成的适应 性系统。这方面的研究最初从2 0 世纪8 0 年代中期的免疫学研究发展而来。1 9 9 0 年， b e r s i n i 首次使用免疫算法来解决问题。免疫算法作为一种最优算法、仿生智能算法， 在计算、网络、控制、学习等方面都有许多应用，具有很大的应用潜力。本文在遗传算 法的策略中引入免疫算法中的免疫算子，可达到搜索过程快速稳定收敛的效果。 多序列比对就是将一组序列同时进行比对，主要用于描述一组序列之间的相似性关 系，以便对基因家族的特征有一个基本了解，揭示这个基因家族的保守性。它是生物信 息学的重要分析工具之一，在分子序列分析中起到至关重要的作用。国内外对多序列比 对的研究一直在不断前进中，虽然在理论上基于动态规划的同步算法可以求得多序列的 精确解。但是，随着序列数量的增加，算法复杂度也不断增加，呈指数规律增长，因此 这类方法对于计算机的系统资源要求较高。 近年来有些人提出用迭代法来求解多序列比对问题，如模拟退火算法和现今研究的 热点遗传算法等。遗传算法作为一类解决优化问题的随机方法，更适合于求解大规模的 优化问题。现在比较成熟的采用遗传算法解决多序列比对问题的方法有s a g a 和 p h g a ，但也都存在一些局限性。比如s a g a 运算速度太慢。p h g a 算法采用并行遗 传算法大大提高了运算速度，但由于编码方法的限制，只能求解少于3 2 条序列的比对， 另外它采用同步通信机制，需要同步等待，并且造成主进程的瓶颈问题。 2 第一章绪论 1 1 序列比对研究背景及意义 2 0 世纪末期以来，生物科学技术迅猛发展。随着人类基因组计划的实施，通过基 因测序、蛋白质序列测定和结构分析实验，分子生物学家提供了大量有关生物分子的原 始数据，无论从数量上还是从质量上都极大地丰富了生物科学的数据资源，需要利用现 代计算机网络技术对这些原始数据进行收集、整理、管理，以便于检索使用；而且为了 解释和理解这些数据，还需要对数据进行对比、分析，建立计算模型，进行仿真、预测 与验证，发现蕴藏在这些生物学数据资源中大量的生物学规律，这些都促进了生物信息 学的产生和发展。 生物信息学己经成为生物医学、农学、遗传学、细胞生物学等学科发展的强大推动 力量，也是药物设计、环境监测的重要组成部分。生物信息学在基因的功能发现、疾病 基因诊断、蛋白质结构预测、药物合成和制药工业中起着极其重要的作用，并已成为一 个热点研究领域。序列比对是生物信息学研究的重要方法之一，它通过对d n a 和蛋白 质序列进行相似性比较，指出序列间的保守区域和不同之处，为进一步研究它们在结构、 功能以及进化上的联系提供了重要的参考依据。 序列比对，尤其是多序列比对在生物信息工程实践中起着至关重要的作用。例如： 遗传疾病的诊断和基因治疗。众所周知遗传病是由于染色体上的某些核苷酸被取代、丢 失或变异造成，通过对正常人与患病者的基因进行序列比较，可以确定病变基因位置， 进一步进行有针对性的基因治疗 4 1 。序列比对还可以帮助我们建立系统的染色体进化 树，通过同已知功能和结构的序列相比较，能预测未知序列的某些机构特征和功能。 序列比对还是数据库搜索的基础，将查询序列与整个数据库的所有序列比对，从数 据库中获得与其最相似序列的已有数据，能最快速的获得有关查询序列的大量有价值的 参考信息，对于进一步分析其结构和功能都会有很大的帮助。近年来随着生物信息学数 据大量积累和生物学知识的整理，通过比对方法可以有效地分析和预测一些新发现基因 的功能。 双序列比对是序列分析的基础。然而，对于构成基因家族的序列来说，我们要建立 多个序列之间的关系，这样才能揭示整个基因家族的特征。多序列比对在阐明一组相关 序列的重要生物学模式方面起着相当重要的作用，同时d n a 多序列比较对研究蛋白质 序列的同源性也是很重要的。蛋白质序列的同源性是蛋白质空间结构预测的基础，对蛋 白质进行同源性分析的常用方法就是多序列比对。所以一种速度快、精确度高的多序列 3 比对算法，对于生物学研究具有非常重大的意义。已经证明多序列比对问题从根本上说 是一个n p 完全问题，因此多序列比对问题的求解至今仍是计算分子生物学中尚未解决 的一个难题，这是一个极富有挑战性的工作。 1 2 序列比对研究现状 自从1 9 9 0 年美国启动人类基因组计划以来，d n a 和蛋白质序列数据库的规模已里 指数增长，单纯依靠实验手段研究、理解这些生物大分子的生物意义已远远不能满足目 前分子生物学发展的要求。生物信息学为阐明和理解这些海量数据所包含的生物意义提 供了可能，而信息技术为生物信息学的研究和应用提供了非常好的支撑。序列比对是生 物信息学研究的重要方法之一，序列比对算法随着人类基因组计划的推进得到了广泛的 重视和深入的研究。目前生物信息学主要的研究领域包括： ( 1 ) 序列比对( a l i g n m e n t ) ； ( 2 ) 蛋白质结构比对和预测： 基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或不相似性。蛋白质 的结构与功能是密切相关的，一般认为，具有相似功能的蛋白质结构一般相似。 ( 3 ) 计算机辅助基因识别( 仅指蛋白质编码基因) ； 基因识别的基本问题是给定基因组序列后，正确识别基因的范围和在基因组序列中 的精确位置。 “) 非编码区分析和d n a 语言研究； 非编码区由内含予( i n t r o n s ) 组成，一般在形成蛋白质后被丢弃，但从实验中，如果 去除非编码区，又不能完成基因的复制。显然。d n a 序列作为一种遗传语言，既包含 在编码区，又隐含在非编码序列中。分析非编码区d n a 序列目前没有一般性的指导方 法。 ( 5 ) 分子进化和比较基因组学； 分子进化是利用不同物种中同一基因序列的异同来研究生物的进化，构建进化树。 比较基因组学通过比较来分析和解读核酸和蛋白质序列中所表达的结构与功能的生物 信息。 ( 6 ) 序列重叠群( c o n t i g s ) 装配； 根据现行的测序技术，每次反应只能测出5 0 0 对或更多一些碱基对的序列，如人类 基因的测量就采用了短枪( s h o r t g u n ) 方法，这就要求把大量的较短的序列全体构成了重 叠群。逐步把它们拼接起来形成序列更长的重叠群，直至得到完整序列的过程称为重叠 群装配 。从算法层次来看，序列的重叠群是一个n p 完全问题。 ( 7 ) 遗传密码的起源； 通常对遗传密码的研究认为，密码子与氨基酸之间的关系是生物进化历史上一次偶 然事件而造成的，并被固定在现代生物的共同祖先里，一直延续至今。不同于这种“冻 结”理论，有人曾经分别提出过选择优化、化学和历史等三种学说来解释遗传密码【l l 。 4 ( 8 ) 基于结构的药物设计以及基因表达谱分析、代谢网络分析、基因芯片设计和蛋 白质组学数据分析等。 有关序列比对的发展历史已有4 0 多年了，其中较早的要数g i b b s 于1 9 7 0 年提出的 点阵法，点阵法是一种图像显示方法，之后m a i z e l 利用带颜色的点阵法来识别各种相 似区域。1 9 8 1 年s m i t h 和w a t e r m a n 提出了动态规划算法，该算法是一种最优算法，但 所需的时问和空间复杂度太高，不适应于数据库的搜索。随后出现了各种启发式算法， 其中应用最为广的要数f a s t a 和b l a s t 算法【5 1 。随着人类基因组计划的进行，各种模式生 物的全基因组序列不断涌现，对序列比对的算法提出了更高的要求，其中以m im 蛔e r 为代表的后缀树算法应运而生，但后缀树算法对序列相似性有一定的要求。最近b i nm a 等人在2 0 0 2 年提出了p a t t c m h u n i e r 算法f 6 】，该算法利用序列进化特点提出了一种优化 模型，大大提高了搜索效率。 目前，绝大多数方法是基于渐进比对和动态规划的方法，典型的工具有r o f i l es c a n 、 s m i t h - w a t e r m a n 、f a s t a 、b l a s t 等。这些方法在序列较多和较长的情形，效果不好且计 算量大。因此，如果多序列比对问题得到有效解决，蛋白质序列的同源性识别也就得到 了很好的解决，蛋白质空间结构的预测也有了较好的研究基础。两个以上序列的多重序 列比对目前还缺乏快速而又十分有效的算法【5 】。 序列比对是生物信息学的一个基础而又重要的问题，也是生物信息学中的一大难 题。虽然人们已提出大量的比对方法，但是对于分歧较大的序列，比对的准确率以及算 法的时间复杂度都有待于提高。 1 3 序列比对研究内容 遗传算法既是一种自然进化系统的计算模型，也是一种通用的求解优化问题的适应 性搜索方法。遗传算法是应用比较广泛的一个研究方向和领域，它不仅包含了进化算法 的基本形式和全部优点，同时还具备若干独特的性能f “，它可以有效地处理传统上非常 复杂的优化函数求解问题。 免疫算法是模仿生物免疫学和基因进化机理，通过人工方式构造的一类优化搜索算 法，是对生物免疫过程的一种数学仿真，是免疫计算的一种最重要形式。由于问题的复 杂性以及人们对问题认识的不断深化，人们发现仅靠一门学科很难比较完美地解决实际 工作中遇到的问题，因而出现了交叉学科。本文将免疫理论应用于遗传算法，、在保留原 算法优点的前提下，力图有选择、有目的地利用待解问题中的一些特征信息或知识来抑 制其优化过程中出现的退化现象。 本文首先对生物信息学的概念进行了概括性的介绍，分析了目前生物信息学的研究 现状及序列比对中的基本概念。然后深入介绍了序列比对的相关算法及发展现状。在对 序列比对、遗传算法、自适应遗传算法和免疫算法深入研究的基础上，提出并实现了一 种基于自适应免疫遗传算法的序列比对方法，结果证明了该算法不仅是有效的，也是可 行的。用改进的遗传算法来解决多序列比对问题不仅有效避免了遗传算法提前退化的缺 陷，同时使收敛速度明显提高，算法具有全局收敛性 本文在对大量的相关文献资料进行研究的基础上，对基于遗传算法的序列比对方法 进行了改进，论文内容具体安排如下： 第一章主要介绍生物信息学中序列比对的研究背景、意义、研究现状及研究内容。 第二章介绍序列比对中的一些基本概念及进行序列比较时用到的基本知识。 第三章详细介绍了基本的序列比对方法，并对不同的算法进行了分析。 第四章介绍遗传算法、自适应遗传算法、免疫算法的原理，将自适应遗传算法和免 疫算法相结合运用到多序列比对中，并对该算法进行了详细的分析与设计，详细阐述了 算法的步骤。 第五章分析了遗传算法的主要缺陷，并用免疫算法及通过调整参数对遗传算法进行 了改进。本文给出了具体的实例来证明该算法的有效性，并对算法的收敛性进行了详细 的分析。 最后对本文进行总结并指出不足之处和今后的研究方向。 6 第二章生物序列比对 2 1 生物信息学中的基本概念 生物信息学以计算机、网络为工具，采用数学和信息科学的理论、方法和技术去研 究生物大分子，其研究重点主要落实在核酸和蛋白质两个方面，包括它们的序列、结构 和功能。生物信息学以基因组d n a 序列中的信息分析作为出发点，破译遗传语言，认 识遗传信息的组织规律，辨别隐藏在d n a 序列中的基因。d n a 是遗传信息的载体，遗 传信息存储在d n a 四种字符组成的序列中。因此，可以说d n a 序列包含着最基本的 生命信息。 2 1 1 核酸 虽然自然界中的生物种类有成万上亿，但决定它们形态、特性和生命运动的基本生 物分子都是核酸和蛋白质。核酸是遗传信息的携带者，不仅在细胞之间，同时也在生物 个体之间世代相传，而蛋白质是遗传信息转化成生物结构和功能的表达者。 核酸是遗传物质，它是由四种单体聚合成的一维高分子链，其中每个单体又称为核 苷酸。遗传信息就编码在这些单体的不同排列次序列上。核酸根据单体类型的不同，可 以分为脱氧核糖核酸( d n a ) 和核糖核酸( r n a ) ，这两类核酸分布于生物体的细胞之中。 其中，d n a 是主要的遗传物质。核酸经核酸酶水解可生成核苷酸。核苷酸还可以进一 步分解成核苷和磷酸，核苷进一步水解生成碱基( b a s e ) 和戊糖。所以，核酸的基本结构 单位是核苷酸，其组成方式为碱基一戊糖一磷酸i s 】。碱基包括嘌呤碱和嘧啶碱两类。d n a 中的嘧啶为胞嘧啶( c ) 和胸腺嘧啶( t ) ：嘌呤为腺嘌呤( a ) 和鸟嘌呤( g ) 。尿嘧啶( u ) 也 是一种常见的嘧啶，仅存于r n a 中。脱氧核糖核酸是由a 、c 、g 、t 四种脱氧核苷酸 组成的多聚核苷酸链；核糖核酸是由a 、c 、g 、u 四种核苷酸组成的多聚核营酸链。 其中，d n a 上核酸的特定序列决定了生物体的结构和功能，并以其半保留复制机制， 保证世世代代准确地传递下去。 2 1 2 蛋白质 蛋白质在细胞中含量最丰富，人体蛋白质含量达人体干重的4 5 ，蛋白质种类众多， 功能复杂，它几乎参与所有的生命活动，生物体的生长、发育、繁殖、遗传等生命活动 7 都离不开蛋白质，它是各种生命活动的物质基础。 蛋白质是一种由2 0 种氨基酸通过肽键连接而成的生物大分子。蛋白质结构和功能 都是由核酸根据三联体密码决定的，并在细胞内合成。氨基酸是蛋白质的基本结构单位， 自然界中的氨基酸种类很多，但参与蛋白质组成的常见氨基酸只有2 0 种。这2 0 种氨基 酸，除脯氨酸外，均可用图2 1 的通式表示。 n h 2 i h c o 。h i r 图2 1 氨基酸通式( 其中c 。为中心碳原子) 其中r 代表侧链基团，侧链r 基团的不同导致了各种氨基酸的不同。 2 2 生物序列分析 序列比对又叫序列联配，它是生物信息学中最基本、最重要的操作，通过序列比较 可以发现生物序列中的功能、结构和进化信息。序列比较的根本任务是：通过比较生物 分子序列，发现它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差异1 9 j 。 我们用一个简单的例子来说明序列比对的基本原理。图2 2 所示是对两个蛋白质序列片 段进行比对的一般方法，基本思想是将两个序列上下排列，若上下对应的残基相同，则 用竖线表示。可以通过插入空位( g a p ) 使它们具有最好的匹配，即两个序列之间所对应 的相同残基最多。 插入空位前： 序列1 ( 待检序列) 序列2 插入空位后： 序列1 ( 目标序列) ( 待检序列) 序列2 ( 目标序列) a g g v l i i q v g l | ii ii a g g v l i q v g a g g v l i i q v g iii | iifii a g g v l iq v g 图2 2 利用插入空位的方法获得最佳序列匹配 图中竖线表示相同残基之间的匹配，插入空位前共有6 个相同残基，插入空位后共 有9 个相同残基。 8 2 2 1 多序列比对问题的描述 一切物种的核酸或蛋白质序列可以看作由4 个或2 0 个元素组成的字母表中选出的 字母序列，如： t g - c c a c t 、 s w g y v r e t r g n 表示一条核酸序列或蛋白质序列。 生物信息就是成千上万条以字符序列形式存储的核酸或蛋白质序列，并以某些特定格式 存放在各类生物数据库中。 序列比对算法就是根据一个给定的计分函数计算得到两个或多个字符串序列的最 优比对，比对的结果反陕了算法在多大程度上表达序歹l j 之间的相似性关系以及它们的生 物学特征。这个过程往往需要通过数据库搜索，找出具有相似性的同源序列，对于d n a 序列，可推测该未知序列可能属于哪个基因家族，具有哪些生物学功能。而对蛋白质序 列来说，有可能找到已知三维结构的同源蛋白质，而推测其可能的空间结构与功能。 序列数据包括d n a 序列数据和蛋白质序列数据。由于d n a 序列是由4 种碱基a ，g ， c 。t 组成，蛋白质序列由2 0 种氨基酸残基组成，可以将一条序列数据看作是由特定的字 母组成的字符串。有效的残基类型集合用表示，对于d n a 序列= a , c c , t ，对于r n a 序列= a ，g c ，u ，对于蛋白质序列，芑= g a ，l ，m ，f ：w ，k , s n ，d ，p v i ，c ，y h ，t , q ，e ) 。 另外，在长期进化过程中，有些残基相对保守，而有些则可能发生变异，另外，有少数 残基会发生缺失( 删除) 或插入现象。因此，在比较几个相关序列时会出现中断( b r e a k ) 现象，这就产生了“间隙( g a p ) ”问题，间隙用字符“一”表示，多序列比对问题描述如 下f l o l ： 定义l ：设为字符表，a ，4 2 ，瓜为字符表上的字符串，且k 1 2 ，设不 包含字符虬”，“一”表示输出串中的空格。 一个序列比对是字符表z = u 卜 上的一个字符矩阵，且满足如下3 个条件： ( 1 ) 矩阵共有k 行； ( 2 ) 矩阵中的衍f 去掉“一”后，即得到字德串a ； ( 3 ) 矩阵中不包含字符全是空格的列。 定义2 ：序列s 和r ，isi 表示s 中的字符长度，表示序列的第i 个字符。如果说 序列s 和序列r 相同，必须满足如下条件： ( 1 ) ls 1 i r l ； ( 2 ) = 2 3 ，( o 0 & & j o ；) i f ( d 【i ，j l = d 驻- 1 ，j - 1 1 + p ( s i l l ，t d 】) ) i 一- ；j 一_ ；， v i s ei f ( d i ，j 】= d i l ，j 】+ p ( s 嘲，一) ) i 一i n s e r g 一，t ，j ) ； e l s ei f ( d 【i ，j 】= d i ，j - i + p ( _ ，t 【i 】) ) j 一_ i n s e r t ( 一，s ，i ) ； s m i t h - w a t e r m a n 算法是一个局域比对算法，它与基于动态规划的n e e d l e m a n - w u n s c h 算法相似。s m i t h - w a t e r m a n 算法规定矩阵单元值为负者一律取0 ，加入这一项 是为了确保计算中丢弃得分为负值的子序列的比较，因为分值为负的比对丧失了比对的 生物学意义。在计算完矩阵后，找出矩阵的最大分值，再通过回溯法，从最大分值单元 开始回溯到分值为0 的单元为止，确定局域比对路径，构建局部最优比对。 局部比对与全局比对不同的是初始化打分矩阵时第一行和第一列初值均为0 ，即； d 柚= 0 ，d o 。= 0 。而矩阵中各单元值由式( 3 3 ) 计算得出。 d j j2 m a x o d “- 1 + p ( s i , t j ) ，、 d j + p ( 墨- ) ( 3 3 ) d l ，i - l + p 卜，t i l 3 1 3f a s t a 算法和b l a s t 算法 两个序列比对常采用动态规划算法，这种算法在序列长度较小时适用，然而对于海 1 8 量基因序列，这一方法就不太适用。并且序列比对更为常见的用途是用来搜索具有大量 序列的数据库，数据序搜索是指通过特定序列相似性比对算法，找出核酸或蛋白质序列 数据库中与待检序列具有一定程度相似性的序列。动态规划算法所需的时间和空间复杂 度太高，不适应于数据库的搜索，因此出现了各种启发式算法，其中应用最广的有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 年提出，并在1 9 8 8 年做了进一步改进。用 于数据库搜索【1 1 1 。基本思想是：一个能揭示出真实序列关系的比对至少包含一个两个序 列都拥有的字( 片断，即由连续字符组成的子序列) ，把查询序列中的所有字编成哈希表， 然后在数据库搜索时查询这个哈希表，以检索出可能的匹配，这样那些命中的字就能很 快地被鉴定出来。 f a s t a 程序并不研究每一个选中的字，而是寻找包含若干个相邻的选中片段，将这 些片段组合起来予以评价；然后，那些最有可能的匹配序列将会通过局域比对而被进一 步评分，并对每一个检索到的比对提供一个统计学显著性的评估鲫。 算法过程简单描述为： ( 1 ) 根据点阵图逻辑，从比对的所有结构中计算出最佳的对角线； ( 2 ) 使用字符方法寻找查询字符和测试序列之间的精确匹配： ( 3 ) 当所有的对角线发现之后，通过增加空位来连接对角线。 ( 4 ) 在最佳对角线区域中计算出比对结果。 b l a s t 算法是由a l t s c h u l 等人在1 9 9 0 年提出，采用了一种短片段匹配算法和一种有 效的统计模型来找出目的序列和数据库之间的最佳局部比对效果。b l a s t 算法的基本思 想是：通过产生数量更少的但质量更好的匹配片段来提高搜索速度。 算法过程简单描述如下： ( 1 ) 在数据库中找出与查询序列相同的匹配字串( h i t ) ，且这一局部字串中不含空位； ( 2 ) 一个匹配字串选中后，以此作为内核向两端延伸，以找出尽可能长的相似序列 片段，也即高分片段对h s p 嘶g hs e q u e n c ep a i r s ) ： ( 3 ) 设定一个统计显著性阀值e ，统计显著性大于占的h s p 将被舍弃，剩下的h s p 即为高质量的匹配片段对，由此在数据库中搜索出具有一定可信度的同源序列。 3 2 多序列比对算法 双序列比对是序列分析的基础。然而，对于构成基因家族的成组序列来说，必须阐 明多个序列之间的关系，才能揭示整个基因家族的特征。多序列比对就是把两条以上可 能有系统进化关系的序列进行比对的方法，它是双序列比对的自然推广。目前对多序列 比对的研究还在不断前进中，现有的大多数算法都基于渐进的比对思想，在序列两两比 对的基础上逐步优化多序列比对的结果。进行多序列比对后可以对比对结果进行进一步 处理，例如构建序列模式的p r o f i l e ，将序列聚类构建分子进化树等等。意义在于通过多 个相关蛋白质的相似性( 同源性) ，了解其在进化上亲缘关系的远近，推断分子起源和进 化规律等。同时研究多个序列中的保守区域，就可以猜测这些区域对蛋白质结构、功能 的重要性，从而进行分子设计。 现有实用的多序列联配方法还不能保证一定给出最优比对结果，只能给出一个近似 值往往人为的修正可以使比对结果更佳。同源序列的多序列比对是生物信息学的一 个重要课题，目前还没有一个最佳的多序列比对方法，自动比对程序给出的结果往往可 以通过人为的分析而得到改进。 3 2 1 多重序列的动态规划算法 对于两条序列得分矩阵相当于二维平面，面对于3 条序列，每一种可能的比对可类 似地用三维晶格中的一条路径表示，而每一维对应于一条序列，如图3 4 所示。多重序 列比对的基本思想是将一个二维的动态规划矩阵扩展到三维或多维【2 1 1 。如果存在多条序 列，则形成的空间是超晶格。 多序列的动态规划法是把给定的所有序列同时进行比对，而不是两两比对或分组进 行比对。以三个短序列 v s n s 、 s n a 、 a s 为例，通过动态规划算法找出了比对 的最佳路径。结果如图3 5 所示【2 l 。 。 么彳 i 7 ， | ， 图3 5 三条序列所对应的三维晶格 在超晶格中，序列的当前点计算是从左下角进行的，而不是得分矩阵中的左上角。 在图3 6 中，当前点的得分计算取决于与它相邻的7 条边( 当前点前趋节点的个数等于 2 ”- l ，l 为待比较序列条数) ，分别对应于匹配、替换或引入空位3 种编辑操作。整个 算法的初始、终止和迭代步骤与双序列比对的动态规划算法完全相同。若一条序列的长 度分别为m l ，j ，1 2 ，m 。，则该算法需要建立一个聊lx 2 趣规模的矩阵。随着 待比较的序列数增加，计算量和所要求的计算空间猛增，时间复杂度为0 ( m m ， m ) 。 s s a a n h s s v 一 一 当前计誓点 图3 6 三维晶格节点计算依赖关系 动态规划算法是一种最优算法，但该种算法的缺点是所需的时间和空间复杂度高， 因此在实际的序列相似性比较中很少使用动态规划算法，除非所需比对序列较少或需碍 到较好的比对结果。 3 2 2c l u s t a i 算法 最佳多序列比对问题是一个n p 难题，因此只能求得近似解。常用的方法有渐进比 对和迭代比对算法。渐进比对的基本思想是：要比对的序列是进化相关的，因此可以按 着序歹l j 的进化顺序，由近至远将序列或子比对结果按双重比对算法逐步进行比对，即将 序列多重比对转化为序列两两比对，逐渐将两两比对组合起来，最终形成完整的多序列 比对。常用的算法有c l u s t a l w 、t - c o f f e e 、d i a l i g n 等。 c l u s t a l 算法是利用启发式进行比对的方法，是由d g h i g g i n s 和p m s h a r p 在1 9 8 8 年首次提出的。启发式方法不一定保证最终能得到最优解，但在大多数情况下，其计算 结果接近于最优结果；并且重要的一点是，这类方法能够大大减少所需的计算时间，加 快计算速度。目前的大多数多序列比对算法是基于渐进思想的启发式算法，以降低运算 的复杂度。渐进法中使用最广泛的是c l u s t a i w ( 它的p c 版本是c l u s t a l x ) 算法 2 2 2 3 1 ，这 种算法在任何主要的计算机平台上都可以免费使用。它的基本思想是基于相似序列通常 具有进化相关性这一假设，其算法过程简单描述如下： ( 1 ) 对多个序列两两比对构建距离矩阵，反映序列之间的两两关系； ( 2 ) 根据距离矩阵产生系统进化指导树； ( 3 ) 对关系密切的序列进行加权，从最紧密的两条序列开始，逐步引入临近的序列 并不断重新构建比对，直至所有的序列都被加入为止。 c l u s t a l w 根据对亲缘关系较近序列间的空位情况，确定如何在亲缘关系较远的序列 之间插入空位。同样，相似性较高的序列比对结果中的残基突变信息，可用于改变某个 特殊位置空位罚分值的大小，推测该位点的序列变异性【1 s 1 。c l u s t a l w 对于亲缘关系较近 的序列比对效果较好，但是对于分歧较大的序列，比对的准确率明显降低。 c l u s t a l w 的程序可以自由使用，在n c b i 的f t p 服务器上可以找到下载的软件包。 c l u s t a l w 程序用选项单逐步指导用户进行操作。用户可根据需要选择打