（计算机系统结构专业论文）smith＆waterman算法在脉动阵列上的实现及分析.pdf

摘要 摘要 生物信息学是在数学、计算机科学和生命科学的基础上形成的。门新型交叉学科， 是指为理解各种数据的生物学意义，运用数学、计算机科学与生物学手段进行牛物信息 的收集、加工、储存、传播、分析与解析的科学。 序列相似性是生物信息学处理中的最基本的问题。如何获得结果更准确，时间和空 间效率更高的序列相似性比较算法是生物信息学研究中的一个重要课题。序列比对就是 通过一定的算法对两个或多个序列进行比较，找出序列间最大的相似性匹配。s m i t h & w a t e r m a n 算法是一种经典的序列比对算法，在双序列比较的情况卜具有比较好的速度 和结果，但是在进行序列数据库搜索时则显得处理速度不足。 论文主要讨论了s m i t h & w a t e r m a n 算法以及在脉动式阵列上的加速。通过对 s m i t h & w a t e r m a n 比对算法的并行化方法的考察，引出细粒度并行化方法和定制硬件， 特别是脉动式阵列；通过对脉动式阵列的结构和特点的分析，结合龙芯i 号处理器的结 构，设计了龙芯i 号新的协处理器c p 2 为一个脉动式阵列，并设计了相关的一组指令集； 通过对龙芯i 号的模拟器的修改，实现了该协处理器和指令集：在算法和系统结构互相 制约的基础上，描述了算法在脉动式阵列上的实现，明确了算法实现过程中的一些实现 细节：最后通过在新的模拟器和原模拟器上的性能比较，针对实验数掘中体现的协处理 器的优势和不足，总结了脉动式阵列结构在各个方面对算法性能提高的影响，最后总结 了己完成的实验内容以及未来工作的一些方向。 关键词：脉动式阵列、共享寄存器、序列比对、s m i t h & w a t e r m a n 算法 a b s t r a c t t h e i m p l e m e n t a t i o na n da n a l y s i so fs m i t h & w a t e r m a na l g o r i t h mo ns y s t o l i ca r r a y w a n gd o n g ( c o m p u t e ra r c h i t e c t u r e ) d i r e c t e db y t a n gz h i m i n b i o i n f o r m a t i c si sa na r e ab a s e do nm a t h e m a t i c s ，c o m p u t e rs c i e n c ea n db i o l o g y ，i t e m p l o y st h em e t h o d sf r o mt h e s ea r e a st oc o l l e c t ，p r o c e s s ，m a n a g e ，s p r e a d ，a n a l y z ea n d r e s o l v et h ed a t af r o m b i o l o g yi no r d e rt ou n d e r s t a n di t sb i o l o g i c a lm e a n i n g o n eb a s i cp r o b l e mi nb i o i n f o r m a t i c si st of i n dt h es i m i l a r i t yb e t w e e n s e q u e n c e s t og e t m o r ea c c u r a t er e s u l t s y e tr e q u i r i n gl e s ss p a c ea n dt i m ei sa ni m p o r t a n ts u b j e c t s e q u e n c e a l i g n m e n t u s e ss o m ek i n do f a l g o r i t h mt oc o m p a r et w oo rm o r es e q e n c e st of i n dt h es i m i l a r i t y b e t w e e nt h e m t h ea l g o r i t h mo fs m i t h & w a t e r m a ni so n eo ft h ec l a s s i c a ls e q u e n c e a l i g n m e n t a l g o r i t h m s i ts h o w sg o o ds p e e da n dr e s u l tw h e nc o m p a r et w os e q u e n c e s ，b u tc o n s u m e st o o m u c ht i m ew h e n c o m p a r e as e q u e n c et os e q u e n c e si nad a t a b a s e t h i sd i s s e r t a t i o nm a i n l yf o c u s e so nt h ea l g o r i t h mo fs m i t h & w a t e r m a na n da c c e l e r a t i n g i to nt h es y s t o l i ca r r a y i td i s c u s s e st h ea l g o r i t h mo fs m i t h & w a t e r m a na n dt h eg e n e r a lm e t h o d t op a r a l l e li ta tf i r s ta n dl e a d st ot h em e t h o do ft h ef i n eg r a n u l a r i t yp a r a l l e la n dc u s t o m i z e d h a r d w a r e ，e s p e c i a l l yt h es y s t o l i ca r r a y t h e n ，i ta n a l y z e st h ea r c h i t e c t u r eo ft h es y s t o l i ca r r a y , a n di n t r o d u c e dt h et h en e w l y d e s i g n e ds y s t o l i cs t y l e dc o p r o c e s s o ro fg o d s o n ib a s e do nt h e u n d e r l y i n gp a r a l l e lr e q u i r e m e n to ft h es m i t h & w a t e r m a na l g o r i t h m a f t e r w a r d s ，i tf i n a l i z e s t h ei m p l e m e n t a t i o no ft h ea l g o r i t h mo nt h ea r r a y ，t h e n ，i tc o m p a r e st h ep e r f o r m a n c eo nt h e o r i g i n a la n dr e v i s e ds i m u l a t o r so fg o d s o ni ，a n dc o n c l u d e st h ei m p a c to fe a c ha s p e c to n a c c e l e r a t i n gt h ea l o g r i t h ma n dt h ea d a v a n t a g e sa n dd i s a d v a n t a g e so ft h ea r r a y , a tl a s t i t p r e v i e w ss o m es u b j e c t st ob ei n v e s t i g a t e di nt h ef u t u r ew o r k k e y w o r d s ：s y s t o l i ca r r a y , s s r ，s e q u e n c ea l i g n m e n t ，s m i t h & w a t e r m a na l g o r i t h m 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究t 作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同一卜作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：鳅 日期：2 # 0 3 石、，。 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 储鹕：嗷剔隘轹缈飙一”2 第一牵引言 第一章引言 本章简单介绍生物信息学相关的一些基本概念。为后面的内容提供背景知识，然后 介绍论文的主要内容和组织结构。 1 1 生物信息学简介 现代生命科学使人们知道了d n a 是携带生命遗传密码的物质，它决定了生命物种 的形态特征，d n a 的差异是导致生命多样性的根本原因，想要了解生物进化和发展的 本质，就要了解d n a 。随着d n a 测序技术以及计算机技术的飞速发展，生物学特别是 分子生物学在过去的十几年中经历了革命性的发展。获得了大量可供研究的d n a 及其 他生物大分子的数据。生物信息学是在数学、计算机科学和生命科学的基础上形成的一 门新型交叉学科，是指为理解各种数据的生物学意义，运用数学、计算机科学与生物学 手段进行生物信息的收集、加工、储存、传播、分析与解析的科学。生物信息学通过对 生物大分子的测序、分析并发现基因等对生物遗传密码和基因产物的基因组研究，最终 目的是要揭示生物大分子和生物进化的机制、搞清蛋白质结构的机理、探索蛋白质结构 和功能的关系和设计新型的药物等生命科学中一系列重大问题；通过将d n a 序列信息 分析作为源头，从中提取出蛋白质编码区的信息，进行蛋白质空间结构预测和模拟，然 后依据蛋白质的功能进行药物设计及实验。 生物信息学由相互依赖、相互渗透的两个研究领域所组成：信息基础研究及基于计 算机技术的研究，其中前者是构筑现代生物学所必需的，而后者旨在解析生物学基本问 题。基因组信息学、蛋白质豹结构模拟以及药物设计必将有机的结合在一起，成为今后 生物信息学的三个重要组成部分。当前生物信息学研究主要集中在如下几个方面： 1 ) 基因组相关 在进行生物信息学研究中首先是要对生物大分子进行测序来获得研究对象及数掘。 现在测序通常是用鸟枪法( s h o t g u ns e q u e n c i n g ) ：首先使用生物或者其他手段按不同方式 将大量相同的序列切为相互重叠的片断，每个片断大约有五百个碱基对，片断的内容可 以由测序仪直接读出，然后根据片断间重叠的信息，利用计算机将片断组合起来成为 条完整的序列。但是序列片断的拼接是一个n p 完全的问题，而且由于序列中存在的比 如重复序列等特殊现象现阶段的程序和算法的结果还不能达到令人非常满意的程度。 获得d n a 序列数据后就需要对序列进行分析和标注，区别d n a 序列中编码基因 的区域和非编码基因的区域。发现编码区域后，会得到了新的基因。虽然目前还不知道 非编码区的生物意义，但是由于菲编码区往往占到d n a 里大部分空问，比如人类的非 编码区占到9 5 ，其中必然有重要的生物学功能，现在一般的观点认为非编码区的功能 主要体现在对基因表达的时空调控上，也就是说虽然生物体中每个细胞都有完整的套 基因但是这些基因并不是同时在表达，环境和时问的不同会导致细j 地中禁些基因的丌 s m i t h & w a t e r m a n 算法在脉动阵列上的实现及分析 启或关闭，以合成或停止合成某些蛋白质，从而体现对环境的适应、表现为不i _ j 的组织 或者行使不i 司的功能。 目前生物信息学只能做到单个或几个基因之间关系的分析，但是仪仪孤立地掌握生 命体中单个基因的功能和表达调控是不够的，生物体中基因的数量也是非常庞大的，可 能基因表达之间会存在关系，而且未编码区域的存在使得分析更加困难。生命现象是基 因组中所有部分共同作用的结果，完整的分析整个基因组对更好的了解生物进化和生命 现象起到非常重要的作用。 序列的分析还有一个方面就是基因组演化和物种演化。生物的遗传物质是怎么进化 的，这一直是生物学研究中的一个重要问题。智人和黑猩猩之间有9 8 一9 9 的结构基因 和蛋白质是相同的，但是表形上却相差甚多，主要的原因是基因的组织方式不同，是基 因组整体及组织方式而不仅仅是个别基因在研究物种演化历史中的重要作用。从基因组 整体结构组织和功能调节网络方面入手，结合相应的生理表征现象，进行完整基因组的 演化研究，才能揭示出物种真实演化历史的。 2 ) 蛋白质组相关 基因的作用是通过它所表达的蛋白质来体现的，在从d n a 转录为r n a 到从r n a 翻译为蛋白质的过程中，会受到很多因素的影响，研究基因组所有蛋白质产物表达情况 的蛋白质组研究和前面提到的完整基因组研究都是了解生命运转和调控这个整体系统 的分子机制的重要手段。 基因组和蛋白质组研究的迅猛发展，使得许多新蛋白质序列涌现出来。和d n a 不 同，蛋白质的功能是和其三级结构相关的，而且蛋白质的三级结构也不一定是静态的， 其结构也会在行使功能的过程中相应的有所改变。因此要想了解蛋白质的功能，光有氨 基酸序列是远远不够的，更需要了解他们的结构。目前除了x 射线晶体结构分析、多维 核磁共振删m r ) 波谱分析和电子显微镜二维晶体三维重构( 电子晶体学e c ) 等物理方法 得到蛋白质三级结构之外，另外一种广泛使用的方法就是通过计算机辅助预测的非物理 方法。一般认为蛋白质的折叠类型只有数百到数千种，远远小于蛋臼质所具有的自由度 数目，而且蛋白质的折叠类型与其氨基酸序列相关，这样就有可能直接从蛋白质的氨基 酸序列通过计算机辅助方法预测出蛋白质的三级结构。 表格1 蛋白质结构层次【1 】 一缴绍嗣玺日原甲明虱基酸一维j 予夕 二级结构蛋白质多肽链中有规则重复的区域，如a - 螺旋、d 一折叠、p 一转角等 超二级结构凳? 主霁耋誓差元组成的结构单位常为蛋白质三级结构构件，如陋。单 三级结构由二级结构和超二级结构组成，是蛋白质的基本功能单位 四级结构由几条多肽链组成的蛋白质分子，每条多肽链是一个雄 五级结构 墨蓁喜篡生物大分子组成的聚合体如蛋臼质- 蛋臼质聚合体、蛋白质一核 第一章引言 计算机辅助的蛋白质结构预测的目的是利用已知的蛋白质序列米构建出蛋白质的 高维结构模型，目前预测蛋白质空间结构的方法可以分为两大类：第一种是利用分子动 力学的物理知识来计算出所有原子的自由度，获得物理上能量最低的序列结构，从而得 到分子的三级结构。第二种是利用结构和序列相关的特性，通过已知的三级结构的序列 和未知结构的序列进行比较，减少分子中的原子或片断的自由度的取值范围来减少计 算。目前的蛋白质三级结构预测在预测同源蛋白质方面精度比较高，而在预测非同源蛋 白质方面则不如人意。 3 1 药物设计 分子生物学以其特有的方式被应用于药物研究过程：疾病分子机制的阐明、药物作 用靶的确定、生物活性筛选模型的建立都与分子生物学密切相关：同时，分子生物学为 酶、受体的等药物作用靶蛋白的结构模建提供物质基础。但是和计算化学一样，因为结 构已确定的蛋白数量太少，分子生物学在药物设计中的作用也受到限制。 近年来随着结构生物学的发展，相当数量的蛋白质以及一些核酸、多糖的三维结构 获得精确测定，基于生物大分子结构知识的药物设计成为当前的热点。生物信息学的研 究不仅可提供生物大分子空间结构的信息，还能提供电子结构的信息，如能级、表面电 荷分布、分子轨道相互作用等以及动力学行为的信息，如生物化学反应中的能量变化、 电荷转移、构象变化等，理论模拟还可研究包括生物分子及其周围环境的复杂体系和生 物分子的量子效应。 传统的药物研制主要是从大量的天然产物，如动物、植物、微生物和合成有机、无 机化合物以及矿物中进行筛选，得到一个可供临床使用的药物，要耗费大量的时间与金 钱。生物信息学的发展使得基于蛋白质和核酸结构的药物设计成为可能，这种设计途经 与蛋白质工程有着深刻和广泛的联系，为药物设计研究提供了崭新的研究思路和手段， 可以在新药研究的各个环节，如初始阶段、生物活性筛选、合理药物设计等阶段，以及 新药开发阶段发挥重要的作用。 生物信息学的任务远不止于此，在以上工作的基础上，最重要的是如何运用数理理 论成果对生物体进行完整系统的数理模型描述，使得人类能够从一个更加明确的角度和 一个更加易于操作的途径来认识和控制自身以及其他的生命体。 生物信息学更多的具备研究领域的特征，虽然现在还不具备一套完整的科学概念与 原理，但是它具有独特的开放性和应用途径的多样性等特征，作为建立于应用数学、计 算机科学、生物学、物理学、化学等多学科加查结合基础之上的生物信息学，必将具有 坚实的理论基础和广泛的应用前景，开辟了生物学研究的新方向。特别是人类基因组计 划以及水稻基因组计划等计划的成功，为后续的研究提供了准确的数据资料，为研究生 物的本质提供了方法和数据依据，将成为生命科学研究中重要的罩程鹂! 。 s m i t h & w a t e r m a n 算法在脉动阵列上的实现及分析 1 2 论文主要内容 本文主要集中讨论在生物信息学中的最基本的运算一一序列比对上，介绍了序列比 对的常用算法、一般的并行化方法和简单的性能分析，特别是脉动式阵列对 s m i t h & w a t e r m a n 算法的加速，并通过为龙芯i 号处理器上设计了一个脉动式阵列的c p 2 协处理器以及对s m i t h & w a t e r m a n 算法的修改，取得了在脉动式阵列上运行的实验数据， 并进行了详细的分析，总结了脉动式阵列在各个方面对s m i t h & w a t e r m 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 等。 但是由于经典的序列比对算法在大规模的序列数据库搜索过程中速度显得不足，需 要通过并行化或改进算法来提高效率，论文第三章主要介绍了序列比对时一般的并行化 方法。并对其中的一些方法作了简单的复杂度分析。 对序列比对的方法中，可以使用并行化硬件及细粒度的方法对算法提供加速，脉动 式阵列就是一种并行化硬件。脉动式阵列和脉动式算法是相辅相成的，脉动式阵列在运 行脉动式算法的程序上有着得天独厚的优势，而s s r 又是脉动式阵列结构中提供通讯的 一种很好方式。第四章主要介绍脉动式阵列的基本结构、s s r 结构和使用举例，以便于 描述后面龙芯i 号协处理器实现的特例。 夺脉动式阵列和s m i t h & w a t e r m a n 算法的实现 通过分析，论文决定采用脉动式阵列和s s r 结构作为主要的实现方向，而龙芯i 号处理器的模拟器提供了一个很好的模拟实验环境。论文的第五章介绍怎样将脉动式阵 列实现在龙芯i 号模拟器上作为它的协处理器，主要描述了龙芯i 号的基本结构，如何 将脉动式阵列和龙芯i 号连接起来，协处理器的指令设计，以及实王见过程中的困难和解 决方案。 当龙芯i 号处理器经过一系列修改可以运行脉动式阵列的指令后，就要实现 s m i t h & w a t e r m a n 算法为脉动式算法，这一过程中存在一些具体的问题需要解决。论文 第六章主要实现过程中的一些问题和选择，并给出了算法的具体实现。 夺模拟实验的数据和分析 模拟实验所采用的龙芯i 号模拟器和测试程序都可以正常运行，得到了性能数据后， 通过对结果数据进行分析，了解脉动式阵列各个方面的因素对提i 蕾效率的贡献，以及还 有那些方面存在着可能改进的空间，并总结所做的工作和预计将来的：【作。 4 第二章序列眈对 第二章序列比对 生物信息学中通过实验直接获得的数据中最多的就是序列数据，做好序列分析，从 序列数据中发现其含义和揭示生物学的秘密的意义就显而易见了。在序列分析过程中， 序列比对作为序列分析研究的最底层处理之，即是要确定序列之| 日j 的相似程度，是序 列拼接、模体提取、搜索新基因、数据库搜索、蛋白质分子结构和功能预测、分子演化 和演化树的构造等其他序列分析过程的基础，为深入研究提供了基本数据，在生物信息 学中起了重要的不可替代的作用。本章对序列、序列分析和序列比对先做了概述，介绍 序列分析和序列比对的意义和一些概念，然后介绍序列比对中的几个常用的算法： s m i t h & w a t e r m a n 、f a s t a 和b l a s t 等。 2 。1 序歹l j 、序列分析及序列比对 生物信息学中经常处理的生物大分子有d n a 、r n a 和蛋白质等，它们都是由小分 子如核苷酸或氨基酸分子等通过相互之间的化学键连接组成的。如果将这些小分子用符 号表示则大分子的主链可以表示为一个字符串，这样就可以利用计算机米很好的处理， 这样的字符串就称为序列( s e q u e n c e ) 。 d n a 分子的基本元素通常为4 种核苷酸分子，分别是腺嘌呤( a d e n i n e ) 、鸟嘌呤 ( g u a n i n e ) 、胸嘧啶( c y t o s i n e ) 和胸腺嘧啶( t h y m i n e ) ，表示成缩写符号也就是通常所说的 a c g t ，其中a t 和c g 之问可以形成稳定的化学键，两条d n a 链就是通过这种化学 键连接在一起并形成了双螺旋结构：r n a 基本组成元素和d n a 有点差别，尿嘧啶( u r a c i l ) 替代了胸腺睦啶成为基本组成元素，简写就是u ，因为是单链，r n a 只有在从d n a 转 录为r n a 时候才形成a u 和c g 的共价键，而从d n a 上转录完成脱离后则保持单链 形式。因为d n a 的结构原理和键比较简单，所以它的空间结构比较简单单一，是简单 的双螺旋结构，而且当d n a 行使功能翻译为r n a 时，需要将其双螺旋的结构展开，所 以它的结构和其功能并没有什么关系。蛋白质中常见的基本元素为2 0 种氨基酸分子， 这些分子之间可以互相形成化学键，构成一个以氨基酸链为基础的复杂的三维结构体， 蛋白质中复杂的化学键导致了其空间结构呈现多样性，而且蛋白质的功能通常和其结构 有着相关性，所以更突出其结构的重要性。尽管核苷酸和氨基酸的种类比较有限，但是 由于序列中包含了大量的小分子，从而序列种类是很丰富的。 因为序列中这些字符有其生物学上的意义，代表了其中的小分子而不再是简单的字 符，所以虽然可以利用已有的关于字符串的算法和工具来管理和处理这些数据，但是需 要增加一些基于生物学意义的新算法和新工具来得到正确的有意义的结果，以及将序列 信息和序列分析结果转换为生物学上有意义的信息，弄清它们的生物学意义，从而揭示 生物现象发生的秘密。 将新序列同数掘库中的已知序列进行比较分析是对新序列进行分析很有效的个 5 s m i t h w a t e r m a n 算法在咏动阵列上的实现及分析 研究手段。随着数据库中已知的序列数据和对应的标注信息的增长，通过和己知的序列 信息进行比较，可以从新序列中提取更多的信息，比如序列的演化、结构、基因和功能 等一些信息。序列比对( s e q u e n c ea l i g n m e n t ) 作为序列分析的最底层处理之一，即是要确 定序列之间的相似程度，是其他序列分析过程的基础，为深入研究和分析提供了基本数 据，在序列分析中起了重要的作用。 对于两条字符串序列s e q l 和s e q 2 ，确定它们之间字符匹配问题己经比较成熟了， 但是在生物信息学中，序列比对所采用的算法并不是要求精确匹配，而是希望发现两条 序列之间的相似性和内在的关系。自从n e e d l e m a n 和w u m c h 在1 9 7 0 年提出最初的动态 规划方法【2 】至今，序列比对的方法有了长足的进步：吸取了新的模型、构建了新的方法、 利用了新的环境，在提高比对速度和比对结果等方面成绩显著。而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 算法的改进，提供了很好的比对性能。但是在数据库迅速增 长的情况下，常规的算法程序自身越来越跟不上序列数据库增长的步伐，需要新的算法、 并行化算法或专用的机器。 2 2 序列比对中的概念 本节对后面将要使用到的一些概念进行定义，便于后面章节的描述。 字符是指生物大分子表示为序列时，作为大分子的基本组成元素的小分子在序列中 所使用的标识符。在一类序列中每种字符代表一种小分子相同的字符出现在不同类序 列中，比如分别在d n a 序列中和蛋白质序列中的含义并不相同，在d n a 序列中字符 表示核苷酸，在蛋白质序列中字符表示氨基酸。论文中有时候也使用符号这个词来表示 和字符相同的意思。 序列就是由一串线性的字符所组成的，用来描述d n a 链或蛋白质链的字符串。序 列是生物大分子的一种最简单的结构，也是这些大分子的最容易描述的结构。 待检序列( q u e r ys e q u e n c e ) 是指在进行数据库搜索时将要和数据库中的序列进行比 较的序列。该序列可能是刚刚从测序仪上得到或者刚刚拼接完成，是这次搜索的主要研 究对象。目标序列( s u 巧e c ts e q u e n c e ) 是指进行数据库搜索时在数据库中得到的与待检序 列相似性比较高的d n a 或蛋白质序列。在论文中有时候也笼统地指在进行序列比对中 从数据库中提取的将要和待检序列进行比对运算的序列或者可能有着一定相似度的备 选序列。 插入( i n s e r t ) 是指序列比对中一条序列在该位置上比其他序列多了一个字符。缺失 ( d e l e t e ) , t j 正好相反，指比对中一条序列在该位置上比其他序列少了一个字符。插入和缺 失通常是相对的，一条序列的插入，意味着比对结果中，其他序列比这条序列缺穴了一 个字符，所以插入和缺失经常被一起使用，表示为插入，缺失( i n d e l l 。替换( s u b s t i t u t e ) 是 指序列比对结果中不| 一j 序列在相同位置上具有不同的字符，可以看作是一条序列在该位 置使用了其他字符来代替另一条序列中该位置的字符。从另一个角度来看，当两条序列 在相同的位鼍具有相同字符时，也可以认为它们之间发生了一种特殊的替换，这样就可 第二章序列比对 以将不同字符之间的替换和相同字符的匹配看作相同的现象，便于统一计分系统。论文 里有时也使用置换来表示相同的意思。在序列比对结果中一条序列总可以通过若干插入 缺失和替换来得到另一条序列。空位指的是在发生插入缺失时，出现缺失的那条序列 中为了补齐序列长度在缺失位置插入了”一”字符，则插入”字符的位崔即是一个字位。 而连续空位则是指发生插入缺失时在发生缺失的序列中连续出现了多个字符的缺失，为 了补齐序列长度连续插入了多个”一”字符。 点突变( p o i n tm u t a t i o n ) ，有时简写为突变，是统指生物大分子演化过程中变异的主 要三种形式：插入、缺失和替换。生物大分子的变异还有其他复杂的形式，比如重复序 列等变异，但是发生的概率比点突变的概率要小得多，在本文的序列比对算法里则没有 考虑这些复杂的突变以及解决这些突变形式的算法。 序列比对( s e q u e n c ea l i g n m e n t ) 是指通过一定的算法对两个或多个序列通常是d n a 序列或蛋白质序列进行比较找出序列问最大相似性匹配，为进一步研究提供相似性数 据。这种相似性可能是全局的，也可能是局部的，因此存在全局比列和局部比对算法。 全局和局部的比对算法之间没有本质的区别，局部比对可以在全局比对算法的基础上修 改构建，但是需要在适当的时候抛弃前面坏的结果，从新的位置重新比对。双序列比对 就是两条序列进行比对，得到两条序列之间的相似性，是序列分析中最基本的方法，而 且也是多序列比对和数据库搜索的基础。多序列比对则是同时有多条序列参与运算，发 现多条序列之间的相似性，特别是同源序列和家族序列。序列比对过程是基于一定的算 法，这些算法通常只是基于序列本身字符串信息，以及一定的计分系统。而不使用序列 的注释信息。常用的序列比对算法有s m i t h & w a t e r m a n 、c l u s t a l w 等算法。 数据库查询( d a t a b a s eq u e r y ) 是指对序列、结构以及各种二次数据库中的标注信息迸 行关键词匹配查找。因为互联网的迅猛发展，一些机构和组织在网络上提供序列及标注 信息的数据库以供查询和下载，比如美国的n c b i ，这些数据的共享为生物信息学的发 展起到了推动作用，研究人员可以从网络上通过数据库查询得到其他研究人员已经完成 的工作的成果，减少了重复工作，提高了效率。数据库搜索( d a t a b a s es e a r c h ) 指通过特 定的算法，找出d n a 或蛋白质序列数据库中和待检序列具有一定相似性的序列。当通 过实验获得了新序列的数据时，为了从序列本身得到更多的信息，就i 丁以进行数据库搜 索，来查找和它相似的序列，然后参考和它相似的序列的标注信息可以推测新序列可能 具有的结构、功能等信息。因为通常数据库搜索需要有序列数据库，而且数据里的序列 又是非常多，所以数据库搜索也是需要高性能的计算机系统才能完成任务，也有机构和 组织提供数据库搜索，比如美国的n c b i 。常用的数据库搜索算法有f a s t a 、b l a s t 算 法等。 灵敏度( s e n s i t i v i t y ) 是指进行数据库搜索时发现真正目标序列的能力，而选择性 ( s e l e c t i v i t y ) 贝, t j 是指进行数据库搜索时抛弃非真正目标序列的能力。它们是评估序列搜索 算法好坏的两个重要参数。这两个参数表面上是相同的，实现中是互斥的。因为为了提 高算法的速度，通常并不是按照序列比对的最后得分来选择哪个序列作为目标序列的备 s m i t h & w a t e r m a n 算法在脉动阵列上的实现及分析 选序列，而是根据一些局部特征和分值来估计可能的最后的分，然后选择出一些备选序 列再做完整的序列比对过程，这样提高选择性可能会减少备选序列数日，则在搜索过程 中会导致相似的目标序列被抛弃的可能性增加，而提高灵敏度则会扩火备选序列数目， 则可能在搜索过程中会导致不相似的各选序列数目的增加，因此需要在这两个参数之间 进行折衷，以产生可接受的好算法。 2 3 经典序列比对原理 对刚测序完成的序列进行序列分析的第一步通常就是将该序列作为待检序列进行 数据库搜索，找到和该序列相似的序列，从目标序列的标注信息中发现待检序列可能具 有的性质、结构和功能等，为理解新序列的生物学意义提供一些简单的预测。序列比对 贯穿序列分析过程的始终，为复杂的序列分析过程提供基本的参考数据。 2 3 1 字符串匹配 由于序列是字符串的形式，因此利用计算机科学中成熟的字符串匹配算法似乎是简 单可行的。但是计算机科学中原有的字符串匹配算法通常是精确匹配，即是两个字符串 必须在相同位置具有完全相同的字符才表明这两个字符串是匹配的，如果有不同则表明 这两个字符串不是匹配的，而不需要表明这两个字符串有多少个字符是相同的，多少个 是不同的，不同的字符之间替换的可能性是多少等信息。而序列比对中则需要知道两条 序列之间有多少相似程度，而不是布尔值的相同或不同。虽然有的字符串匹配算法也给 最终结果有个分值，但是这些分值的意义直接使用在序列比对算法中并不能完全表达生 物分子中所有可能的突变。 例如海明距离就是一种简单的计算字符串匹配的算法，它的计算方法就是简单的数 两个相同长度的字符串在相同位置为不同字符的次数，也就是发生字符替换的次数。最 初海明距离是用在计算两个二进制数字串之间，这样可以用来检错和纠错，可以将它延 伸到了其他标记系统，比如字符串之间。比如1 0 1 1 1 0 1 和1 0 0 1 0 0 i 之f n j 的海明距离为2 ， 因为在第3 和5 位置两者之间的字符不同。而2 1 4 3 8 9 6 和2 2 3 3 7 9 6 之间以及t o n e d 和r o s e s 之间的海明距离都是3 。海明距离首先要求字符串长度一样，不一样长度的，无法进行 比较，或者需要增加多出的字符如何进行计分的规则。其次字符替换的计分规则是和字 符无关，而在序列比对过程中，这两点都是需要考虑的问题。 2 3 2 双序列比对简例 一般的字符串匹配算法不能体现序列比对在生物学上的意义上，凶此字符串匹配算 法并不能被完全照搬到序n l ：t 对中。下面用个简单的例子来介绍序列比对： 第二章序列比对 表格2 序列比对方案1 表格3 序列比对方案2 l 序列1acgtac l fiiij l 序列2ac ct c 1 l 序列1acgtac i ilii l 序列2acctc 如上面所示的方案l 和方案2 都可能是这两个字符串比对的结果，比对的基本作法 就是将两个序列上下排列，按照一定的规则组织两个序列中的字符上下对应及插入空 位，如果上下的字符相同，则用竖线表示，当上下两个字符不同时即发生替换，则不进 行标记，如果出现空位，则在序列缺失位置增加一个符号“一”以标识该处缺失了一个 字符。比对过程通过空位和替换使得两条序列具有了相同的长度。 比对完成后，按计分系统中的定义给每个位置一定的分值，并将所有位置的分值加 起来得到序列之间比对得分。计分系统不仅包括了相同字符匹配的得分，还应包括插入 ，缺失以及替换的得分。不同的计分系统会给相同的比对不同的结果得分，例如设相i 司字 符匹配的得分为0 ，插入缺失的得分为一一，替换的得分为1 ，则两个相同长度的字符串 通过上述方法计算得到的最高得分即为海明距离的得分。如果设两序列该位置字符相 同，则得分为l ，而插入缺失和替换的分值为0 ，则方案1 和方案2 的得分都为4 。方 案l 和方案2 的比对结果明显不同，至于最终结果采用那种方案则需要根据计分系统来 选择，使得最终的得分在所有比对的可能中最高，因此随意使用插入缺穴和替换即使使 得序列匹配上了也不一定能作为结果输出。总体上来说，在序列比对中，比对的结果中 如果有更多的字符在相同的位置相匹配上，则比对的得分可能越高，两条序列则可能 更相似。计分系统决定比对的得分以及比对的结果，通常所采用的计分系统中对于匹配 上和替换会使用替换矩阵，而对于插入缺失则根据插入，缺失的字符个数来使用一定的 函数例如仿射函数来计算罚分值。 2 3 3 计分系统 前面的例子简单的说明了两个序列之间比对以及计分，但是那只是示例了结果，序 列比对是一个动态的过程在这一过程中，允许替换以及插入，缺失使得比对过程变得复 杂，插入1 缺失也不能毫无限制的，而且需要最终的结果在生物学上的意义比较明显，最 终结果要是所有可能比对中的最大值作为比对结果。从前面例子似乎汁分系统系统只有 。得分越高的意思是指序列之问扪似性更高因为分值的计算可能依赖于计分方法而秆的r 1 分d 泣一叮能分恤越低舯 似成趣好，比如海哪距离就址这种情况。 9 s m i t h w a t e r m a n 算法在脉动阵列上的实现及分析 在得到所有比对的可能后才被使用，而实际上两条序列的所有比对可能性和序列的长度 成指数关系 3 】，所以计分系统在比对过程中就要起到筛选的作用。 生物体在进化过程中会不断地产生突变，这样才产生了多样的生命，突变的存在也 是要求比对算法存在的生物学基础。因为不同的计分系统会影响比对的分值以及结果， 所以如何选择适当的计分系统，使得根据该计分系统所计算出来的结果是有很好的生物 学意义，而且被实现为很商效的计算机算法是个很重要的问题。 插入缺失比较通行的计分方法是采用空位罚分，即给予每个空位一定的罚分值，当 出现空位时则使得总分值减少。一种简单的空位罚分方式就是给仟何空位都相i 司的罚 分值，表示成公式就是g ( k ) = k g ( 1 ) ；另一种仿射罚分方式，表示成公式就是g ( k ) = + d x ( k 一1 ) ，这种计分系统分为两个部分：起始空位罚分a 和延伸空位罚分b 。起始空位 是指序列比对过程中为了使得比对结果更好，引入了一个空位，而日引入这个空位的序 列在这个空位的前一个位置不是空位，这样新引入的空位即为起始空位：而延伸空位是 指序列比对过程中为了使得比对结果更好，在已经插入了一个或多个空位后，继续引入 一个空位且这些空位连续的位于相同的序列上，这样新引入的空位即为延伸空位。通 常仿射罚分系统中l a l 1 1 3 1 ，表示序列比对中偏向于一个连续的较长的插入缺失序列，而 不是很多插入和缺失的交替。 表格4 起始空位和延伸空位简倒 位置i1f 2i3l4i5f67 序列1la lc i 1g ltiac l c 序列2la lc ici i i 举例说明空位罚分，上面是比对的一种结果。其中序列l 的位置3 和序列2 的位置 4 是起始空位，而序列2 的位置5 和位置6 是延伸空位。序列2 的位置4 并不是序列1 位置3 的延伸空位，因为他们并不是在相同的序列上出现的缺失，而分别是两个起始空 位。 而对于替换，通用的方法是采用替换矩阵来计分，即给不同字符之间发生替换提供 一个分值，这种计分方式可以描述为矩阵的形式，矩阵上的每一格都表示它所对应的行 和列所表示的字符之间发生替换时的得分。如前所述，相同的字符匹配上也可以看作是 一种替换，也一起表示在矩阵中，主对角线上的分值即为相同字符匹配上时的分值。通 常替换矩阵是对称矩阵，也就是a 替换b 和b 替换a 具有相同的分值，所以也可以用 矩阵右下或者左上三角表示。一般来说，两个字符之间越相似，在自然界中越容易相互 发生突变，则两字符之间的替换分值越高。如下为d n a 中字符发生替换的一个分值方 案： 表格5 序列比对中使用的替换矩阵简倒 1l a i clg i t l 0 第二章序列比对 a1ooo coloo goolo tooo1 上面这个替换矩阵例子是一个单位矩阵，在计算中也就是数有多少字符匹配上了的 一种计分方式。在生物信息学中通常使用的计分矩阵有p a m ( p o i n ta c c e p t e dm u t a t i o n ) 和b l o s u m ( b l o c k s s u b s t i t u t i o nm a t r i x ) 等矩阵。 突变数据矩阵p a m 的产生是基于序列可接受点突变。1 个p a m 的进化距离表示1 0 0 个字符中发生一个字符突变的概率，一次突变的矩阵p a m 一1 的产生基于相似性较高( 差 异在1 5 以下) 的序列比对，随着取样数据库的不断增大，数据中取样的偏差的逐渐改 善，所求得的p a m - t 矩阵也更具有代表性。更大进化距离间隔的突变概率矩阵，可以 通过对初始矩阵进行适当的数学处理得至l j 4 1 ，例如如果一次突变的发生和该位置以前发 生的突变没有关系，即两次突变之间互为独立不相干事件，则经过多次突变导致一个字 符突变为其他字符的概率可以通过一次突变矩阵连续自乘得到。常用的p a m 2 5 0 相似性 分数矩阵相当于在两个序列之间具有2 0 的字符匹配它的主对角线上的分数值是指相 同字符的替换分数值，有些字符的分值较高，说明它们比较保守，不易突变；有的字符 的分值较低则比较容易突变。不同字符之间的替换分数值越高，则它们之间的相似性 越高，进化过程中容易发生互相突变。而相似性分数值低的字符之间的相似性则较低， 它们在进化过程中不易发生互相突变。 而模块替换矩阵b l o s u m 则以序列片段为基础，它是基于蛋白质模块数据库 b l o c k s ，h e n i k o f f 夫妇【5 】从蛋白质模块数据库b l o c k s 中找出一组替换矩阵，用于 解决序列之间的远距离相关。在构建矩阵过程中，通过设置序列片段的最小相同字符数 占序列片断的百分比将序列片断整合在一起，以避免由于同一个字符对被重复计数而引 入的潜在的偏差。在每一片段中，计算出每个字符位置的平均贡献，使得整个片段可以 有效地被看作为单一序列。通过设置不同的百分比，产生了不同矩阵。由此，例如高于 或等于8 0 相同的序列组成的串可用于产生b l o s u m 8 0 矩阵：那些有6 2 或以上相同 的串用于产生b l o s u m 6 2 矩阵，依此类推。 计分系统是一个完整的系统，因此空位罚分通常是和替换矩阵相关的，相互协调的， 比如b l o s u m 6 2 中就定义了起始罚分和延伸罚分分别为1 2 和一2 ，这样计分系统才是完 备和一致的。由于自然界中发生替换的概率要高于发生插入缺失的概率，通常替换分值 要高于空位罚分值。 2 3 4 序列比对相关的定理 双序列全局比对用数学形式描述如下： 有限字符集上q 中包含了i q l 个元素，两个基于q 的字符串s e q t 和s e q 2 ，长度分 s m i t h w a t e r m a n 算法在脉动阵列上的实现及分析 别为i e l l i = l e n g t h ( s e q l ) 和l e n 2 = l e n g t h ( s e q 2 ) ，双序列比对问题就是鉴求允许在字符串中 插入字符”一”的情况下得到的新的两条基于q + 卜” 序