（计算机科学与技术专业论文）双序列比对算法研究.pdf

国防科学技术大学研究生院学位论文 摘要 生物信息学是一门综合利用生物学、计算机科学、数学等学科知识的新兴交叉学科， 其主要任务是利用信息处理方法揭示海量生物学数据中蕴含的生物学意义，探索生命活 动的奥秘。比对是生物信息学中一种基本的序列分析方法，对于发现核酸和蛋白质序列 所蕴含的功能、结构和进化信息具有非常重要的意义。随着生物序列数据的激增，开发 高效率的比对算法就显得非常迫切。本文研究了生物信息学中的双序列比对算法，主要 研究内容和取得的成果如下： 1 基于经典的u k k o n e a 快速序列比对算法，借鉴f a 算法( f a s ta l i g n m e n ta l g o r i t h m ) 在计算得分矩阵时记录元素来源关系的存储方法，运用在矩阵中寻找c h e c k p o i n t 点的 c h e c k p o i n t 技术，提出一种基于动态规划思想的较为实用的双序列全局比对算法。 2 对几种经典的双序列比对算法进行了分析介绍，并将其中一些算法与本文提出的 新算法进行了性能比较。 3 在深入分析b l a s t 算法的基础上，基于序列划分策略，提出并实现新的并行双序 列比对算法，数值试验表明算法是高效的。 4 以本文提出的双序列比对算法为基础，设计并实现了一个基于w i n d o w s 操作系统 的序列比对应用平台。 本文的研究内容是序列比对算法，经试验表明，新算法计算效率较之传统算法有提 高，在此算法基础上开发的应用软件可以为生物信息学的研究及实践提供一定支持。 关键词生物信息学，双序列比对，动态规划算法 第1 页 国防科学技术大学研究生院学位论文 a b s l r a c t b i o i n f o r m a t i c si san e ws c i e n c ef i e l d r e s e a r c hi nt h i sf i e l di n v o l v e sm u l t i d i s c i p l i n e s s u c ha sb i o l o g y , c o m p u t e rs c i e n c e ，m a t h e m a t i c s ，e r e b i o i n f o r m a t i c si ss u b j e c tt oe x p o s et h e b i o l o g i c a ls i g n i f i c a t i o no fl a r g ea m o u n to fb i o l o g i c a ld a i aa n de x p l o r et h em y s t e r yo fl i f e a c t i v i t i e s s e q u e n c ea l i g n m e n ti sab a s i ci n f o r m a t i o nd i s p o s a lm e t h o di nb i o i n f o r m a t i c s i ti s u s e f u lf o rd i s c o v e r i n gf u n c t i o n a l ，s t r u c t u r a l ，a n de v o l u t i o n a r yi n f o r m a t i o ni nd n aa n dp r o t e i n s e q u e n c e s b e c a u s es e q u e n c ed a t ai n c r e a s er a p i d l yi nb i o l o g ys e q u e n c ed a t a b a s e ，i ti sy e w e x i g e n tt od e v e l o pa l g o r i t h m st h a th a v eh i 曲b i o l o g ys e n s i t i v i t ya n de f f i c i e n c y p a l r w i s e s e q u e n c ea l i g n m e n ta l g o r i t h m so f b i o i n f o r m a t i c sa r es t u d i e di nt h i sp a p e r t h em a i nc o n t e n t s a n d p r o d u c t i o nc a l lb eb r i e f l ys u m m a r i z e da sf o l l o w s ： 1 b a s e do nf a s tp a i r w i s es e q u e n c ea l i g n m e n ta l g o r i t h mn a m e da su k k o n e n ，ah i 业 e f f i c i e n ta p p l i e dg l o b a lp a i r w i s es e q u e n c ea l i g n m e n ta l g o r i t h mi sp r e s e n t e di nt h i sp a p e r t h e a l g o r i t h mu s e dt h em e m o r ym e t h o do ff a ( f a s ta l i g n m e n oa l g o r i t h mf o rr e f e r e n c e t h ef a a l g o r i t h mr e c o r d se l e m e n t so r i g i nr e l a t i o nw h i l ec o m p u t i n gs c o r e m a t r i x a n dt h ea l g o r i t h m a d o p e dt h ec h e c k p o i n tt e c h n o l o g yt oo b t a i ns o m ec h e c k p o i n tp o i n t si nr e p l a c e m e n tm a t r i x 2 s e v e r a lc l a s s i cp a i r w i s es e q u e n c ea l i g n m e n ta l g o r i t h mw e r ea n a l y s i z e d t h e s e a l g o r i t h m sw e r eo f f e r e dc o n t r a s te x p e r i m e n tc o n d i t i o nf o r t h ep a i r w i s es e q u e n c ea l i g n m e n t a l g o r i t h mp r e s e n t e di nt h i sp a p e g 3 a f t e ra n a l y z i n gb l a s ta l g o r i t h m , b a s e do nm e t h o do fs e q u e n c eb e i n gd i v i d e d ，a n o v e lp a r a l l e la l g o r i t h mo fp a l r w i s es e q u e n c ea l i g n m e n ti sp r e s e n t e d t h et e s t i n gr e s u l t s i n d i c a t et h a tt h ep r o p o s e da l g o r i t h mi so f h i 曲e f f i c i e n c y 4 o nt h eb a s i so f t h es e q u e n c ea l i g n m e n ta l g o r i t h mp r e s e n t e di nt h i sp a p e r ，as e q u e n c e a l i g n m e n ts o f t w a r es y s t e mw a sd e s i g n e da n di m p l e m e n t e d t h en o v e la l g o r i t h m sa r eb e t t e rt h a nt r a d i t i o n a la l g o r i t h m si ns e n t i v i t ya n dc o m p u t i n g e f f i c i e n c y t h es o , w a r es y s t e mb a s e d o nt h e s ea l g o r i t h m sc a no f f e rs u s t a i n m e n tf o r b i o i n f r o m a t i c sr e s e a r c h k e yw o r d s ：b i o i u f o r m a t i c s ，p a i r w i s es e q u e n c ea l i g n m e n t ，d y n a m i cp r o g r a m m i n g a l g o r i t h m s 第1 i 页 国防科学技术大学研究生院学位论文 表目录 表1 1g e n b a n k 核酸序列数据库增长情况3 表2 1 得分矩阵1 7 表2 2 空位设置罚分和空位扩展罚分的序列比对的影响”2 0 表2 - 3 一种核酸的替换矩阵”2 0 表3 - 1 动态规划方法的得分矩阵2 7 表3 2u 矩阵的元素来源关系”3 1 表3 3 算法运行时间比较( d n a 序列) 3 6 表3 - 4 算法空间需求比较( d n a 序列) 3 7 表3 5 算法运行时间比较( 蛋白质序列) 3 7 表3 - 6 算法空间需求比较( 蛋白质序列) ”3 8 表4 1f a s t a 算法中的术语3 9 表4 2b l a s t 算法中的术语4 0 表4 3 计算节点配置情况”4 7 表4 4 加速性能测试结果( 含输入、输出时间) ”4 7 表5 1 核苷酸代码表”5 l 表5 - 2 单一记分矩阵 表5 - 3p a m 2 5 0 矩阵 5 3 5 4 表5 - 4b l u s o m 6 2 得分矩阵5 5 第i j i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 两条序列最优比对结果的例子4 图2 1d n a 的双螺旋结构、碱基配对1 0 图2 2d n a 的复制“l l 图2 3 中心法则”1 2 图2 4 两两序列比对的点矩阵一1 8 图2 5 一个典型的序列比对计分公式”1 9 图3 - 1 序列s 到t 的编辑过程2 3 图3 - 2 序列s 到t 的比对结果“2 3 图3 3 动态规划算法描述图2 6 图3 - 4 获得多个c h e c k p o i n t 的运行示意图3 2 图3 5n e e d l e m a n w u m c h 算法的得分矩阵3 3 图3 - 6h i r s c h b e r g 比对示例3 4 图3 7u k k o n e n 比对示例3 4 图3 - 8d i v i d e a n d - e o n q u e 比对示例 图3 - 9o g p 算法比对示例” 图4 - 1t w o - h i t s 策略 图4 - 2x - d r o p 动态规划 3 5 3 6 ”4 l 4 2 图4 - 3f o r m a t d b 结果4 4 图4 - 4m e g a b l a s t 比对结果“ 图4 5 静态分配任务的并行方法 图4 - 6 集中式动态负载平衡示意图 4 4 - - 4 5 - - 一- - 4 6 图5 1 系统的工作流程图 图5 2 由两个d n a 序列组成的序列文件 - 4 9 5 0 图5 3 参数输入窗口”5 2 图5 - 4 系统主界面5 6 图5 5 双序列比对结果5 7 第j v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签名：圣弘 日期：争卯年占月6 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：瑟度列出殖篡洼珏窥 作者指导教师签名： ， 日期：0 刃石年翻多日 国防科学技术大学研究生院学位论文 第一章绪论 人类基因组计划( h u m a ng e n o m ep r o j e c t ，h g p ) 是由美国科学家于1 9 8 5 年首先提 出的一项希望解开人类生老病死的奥秘，并彻底破解控制各种疾病基因密码的国际科学 研究工程，也是人类生命科学史上最伟大的工程。1 9 8 8 年，美国全国卫生协会和能源部 开始组织和实施这项计划，1 9 9 0 年l o 月正式启动，耗资3 0 亿美元。人类基因组大约有 3 万 4 万个基因，约3 0 亿个碱基对。人类基因组计划旨在通过测定人类基因组d n a 约 3 0 亿个碱基对的序列，搜寻所有人类基因并确定它们在染色体上的位置，明确所有基因 的结构和功能，解读人类的全部遗传信息，使得人类第一次在分子水平上全面认识自我。 人类基因组计划的初步成功，表明了以生物信息学为先导的生物信息资源开采是发 现、鉴别新基因最有效、最经济的方法，也意味着人类基囚组的研究将全面进入信息提 取和数据分析阶段，即生物信息学发挥重要作用的阶段，生物信息处理已经成为信息技 术领域面临的巨大的挑战之一。- f 3 新兴的交叉科学一生物信息学( b i o i n f o r m a t i c s ) 【1 】 应运而生。目前，生物信息学已成为生命科学和自然科学研究的重大前沿领域之一。 生物信息学的研究重点主要体现在基因组学和蛋白质组学两方面，具体地说就是从 核酸和蛋白质序列出发，分析序列中表达结构和功能的生物信息田。生物信息学的基本 任务是对各种生物大分子序列进行分析，也就是研究新的计算方法，从大量的序列信息 中获取基因结构、功能和进化等知识。在从事分子生物学研究的几乎所有实验室中，对 所获得的生物序列进行生物信息学分析已经成为下一步实验之前的一个标准操作。而在 序列分析中，将未知序列同已知序列进行相似性比较是一种强有力的研究手段，从序列 的片段测定，拼接，基因的表达分析，到r n a 和蛋白质的结构功能预测，物种亲缘树 的构建等都需要进行生物分子序列的相似性比较。 1 1 课题背景 在生物学的研究过程中，生物学家的主要任务是解释实验所产生数据的生物学意义 随着现代分子生物学的发展以及实验技术的不断改进，分子生物学数据不断产生，这些 数据数量庞大、关系复杂，以至于人们很难再凭借传统研究方法完成如此海量数据的分 析。特别是自1 9 9 0 年美国启动人类基因组计划以来，人类与各种模式生物基因组的测序 工作相继展开。迄今已有大约6 0 个微生物和若干真核生物，如：酵母、线虫、果蝇、 拟南芥的完整基因组已经完成测序工作2 0 0 2 年1 0 月，我国科学家也率先完成了水稻 基因组4 3 0 m 碱基的测序工作【z 】。根据国际数据库的统计，1 9 9 9 年1 2 月d n a 碱基数 目为3 0 亿，2 0 0 0 年4 月d n a 碱基数目是6 0 亿。截止2 0 0 2 年为止，仅美国g e r d 3 a n k 数据库中的d n a 序列总量已超过1 9 0 亿碱基对。生物学数据的积累并不仅仅表现在d n a 序列方面，与其同步的还有蛋白质的一级结构，即氨基酸序列的增长。此外，迄今为止， 第1 页 国防科学技术大学研究生院学位论文 已有一万多种蛋白质的空间结构被测定，基于d n a 序列测序所建立起来的表达序列标 签( e x p r e s s i o ns e q u e n c et a g ，e s t ) 数据库，其纪录也已达1 0 0 0 多万条【1j 。在这些数据 基础上派生、整理出来的数据库已达7 0 0 余个。这一切构成了一个生物学数据的海洋。 不但如此，数据仍以每1 4 个月翻一番的速度增长 生物信息学是通过综合运用数学、计算机科学与工程和生物学等的工具与技术对大 量复杂的生物数据进行分析、加工和再处理，从而揭示出这些数据所蕴含的生物学奥秘 的- - f 7 学科。它通过对生物学实验数据的获取、加工、存储、检索与分析，进而达到揭 示数据所蕴含的生物学意义的目的。由于当前生物信息学发展的主要推动力来自分子生 物学，生物信息学的研究主要集中于核苷酸和氨基酸序列的存储、分类、检索和分析等 方面，所以目前生物信息学可以狭义地定义为：将计算机科学和数学应用于生物大分子 信息的获取、加工、存储、分类、检索与分析，以达到理解这些生物大分子信息的生物 学意义的交叉学科。 生物信息学的兴起引起了众多公司或组织以及国际计算机巨头的强烈关注，世界各 国纷纷成立相应的研究机构，美国的一些著名大学走在了最前列，像哈佛大学、普林斯 顿大学、斯坦福大学、加州大学伯克利分校等都先后成立了生物学、计算机、数学、物 理学等多学科交叉的新中心。许多大公司例如m o t o r o l a 公司、h p 计算机公司以及s u n m i c r o s y s t e m 公司等都建立了生命科学部，投资生物信息公司以谋求一席之地。美国i b m 公司于2 0 0 1 年8 月公布“蓝色基因”研究计划，该计划将耗资l 亿美元，用5 年时间完 成世界上运算能力最强的巨型计算机的设计安装工作，为科学家们分析研究从人类基因 到全球气候变化等各种复杂课题提供强有力的武器。i b m 还将计划建立一个虚拟r d 的解决方案：b i o g r i d c o m p u t i n g ，藉由g r i d c o m p u t i n g 技术与公用的运算共享平台，可 提供给b i o t e c h 用户共享资源并协同合作，以期降低生物科技公司的资本投入，加快产 品研发与测试周期。 我国的众多研究机构也纷纷参与了生物信息学的研究领域。1 9 9 6 年，北京大学加入 欧洲分子生物学网络组织( e m b n e t ) ，成为该组织的中国国家节点，并成立生物信息中心， 为生物、医学、制药、农业、环境等领域的研究开发提供生物信息资源服务，并开展二 次数据库构建、软件集成、基因组分析等研究。1 9 9 8 年8 月，中科院基因组信息中心暨 北京华大基因研究中心成立。2 0 0 0 年3 月，中科院上海生命科学研究院生物信息中心成 立，2 0 0 1 年7 月3 日起正式运作。2 0 0 1 年4 月，中国首届生物信息学大会在北京召开， 其盛况空前与会人员来自各个研究领域，所作报告内容涉及生物信息学的各个方面。 随着基因组计划的实施，核酸和蛋白质一级结构序列数据迅速增长( 如表1 1 ) ，序 列数据的激增，使结构数据在数量上无法与其匹配。序列分析己经成了这一领域的首要 任务生物信息学的中心任务，是从浩如烟海的序列数据中提取理性知识。生物信息学 家所面临的任务，不仅是解决高效的数据储存手段，而且需要开发有效的数据分析工具 因为只有利用新的、有效的数据分析工具，才能将序列信息转换成生物学知识，并弄清 第2 页 国防科学技术大学研究生院学位论文 它们所蕴含的结构和功能信恩，进而彻底了解它们所代表的生物学意义。 表1 1g e n b a n k 核酸序列数据库增长情况 碱基数 6 8 0 3 3 8 2 2 7 4 0 2 9 3 3 6 8 7 6 5 5 2 0 4 4 2 0 9 6 1 5 3 7 1 1 5 5 1 4 7 7 6 2 3 8 0 0 0 0 0 3 1 7 6 2 5 8 5 4 9 1 7 9 2 8 5 7 1 9 4 7 4 2 6 碱基数 1 0 1 0 0 8 4 8 6 1 5 7 1 5 2 4 4 2 2 1 7 1 0 2 4 6 2 3 8 4 9 3 9 4 8 5 6 5 1 9 7 2 9 8 4 1 1 6 0 3 0 0 6 8 7 2 0 0 8 7 6 1 7 8 4 3 8 4 1 1 6 3 0 1 1 1 1 1 0 1 0 6 6 2 8 8 1 4 3 9 6 8 8 3 0 6 4 + 引自2 0 0 1 年1 2 月发布的g e r t b a n k 第1 2 7 版说明 显而易见，序列测定本身不是最终目的，弄情序列数据所包含的生物学意义才是我 们的目标。揭示序列数据所代表的生物学意义，是一门深奥的科学。难度之大，不亚于 破译一部“天书”如同我们所熟悉的自然语言一样，这部“天书”是由一个个句子、一 个个单词甚至一个个字母组成的。若把蛋白质比作句子，把序列基序( m o i f 有人译为“模 体”) 比作单词，那么，组成蛋白质的基本元素这部“天书”，是生物信息学所面临的 艰巨任务。 序列比对，是生物信息学的核心研究内容之一，也是进行各种序列分析任务的基本 方法嘲。在生物学研究过程中，为了确定新测序列的生物属性，经常需要进行序列同源 性分析，就是将新序列加入到一组与之同源，但来自不同物种的序列中进行多序列同时 比较，以确定该序列与其他序列间的同源性大小。这是理论分析方法中最关键的一步。 完成这一工作通常使用序列比对的方法。不仅如此，在蛋白质结构预测等其他研究领域， 序列比对也是最为重要的一种方法咧。 1 。2 国内外研究现状 序列比对的理论基础是进化理论，如果两个序列之间具有足够的相似性，就推测二 者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片段的缺失以及序列重 组等遗传变异过程分别演化而来。序列相似和序列同源是不同的概念，序列之间的相似 程度是可以量化的参数，而序列是否同源需要有进化事实的验证闭。 序列比对实际上就是运用某种特定的数学模型或算法，找出两个或多个序列之间的 第3 页 列螂坦扔饼饼脚聊舢讹挑 蒯一一一一一一一一一一 份蛇蚣舛钙卯鳃眵年侈侈侈侈侈侈侈侈加加列乃鸺泓渺m粥讲蒯觚凇彻删嗍般姗姗嬲馓 争2 3 4 5 6 7 8 9 o l 铫螂墩燃螂燃螂雠燃崂搠 国防科学技术大学研究生院学位论文 最大匹配碱基数1 4 】。序列比对算法( s 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 ) ，就是根据一个给定 的记分矩阵或函数计算得到两个或多个字符串序列的最优比对。即对两个或多个序列通 过匹配相对应的字符和在某些位置插入相应的空位而得到序列之间的最大相似性排列。 如对两个序列a t a c t a g a 和a a c t t g g a 进行排列后得到的最优比对结果( 如图1 1 ) ： j ：i a c t a g 一一a a 一一a c t r g g a 图1 1 两条序列最优比对结果的例子 序列比对的基本思想是找出检测序列和目标序列的相似性。比对过程中需要在检测 序列或目标序列中引入空位，以表示插入或删除。序列比对的最终实现，必须依赖于某 个数学模型。不同的模型，可以从不同角度反映序列的特性，如结构、功能、进化关系 等。很难断定一个模型一定比另一个模型好，也不能说某个比对结果一定正确或定错 误，而只能说它们从某个角度反映了序列的生物学特性此外，模型参数的不同，也可 能导致比对结果的不同 5 】。 目前的序列比对算法很多，它们大多基于运筹学中动态规划的算法思想【6 】【7 】f 8 j 。只 是在此基础上进行了不同程度的改进而己。根据同时进行比对的序列个数，可以将序列 比对算法分为双序列比对( p a i r w i s es e q u e n c e a l i g n m e n t ) 算法和多序列比对( m u l t i p l e s e q u e n c e a l i g n m e n t ) 算法。 ( 一) 双序列比对算法 双序列比对分为全局比对( g l o b a l a l i g n m e n t ) 和局部比对( l o c a l a l i g n m e n t ) ，典型的全 局比对算法是n e e d l e m a n - - w u n s c h 算法【9 】【10 l ，这种算法适用于全局水平上相似性程度较 高的两个序列的比对研究：局部比对算法的基础是s m i t h - - w a t e r m a n 算法【1 1 2 1 ，这种算 法适用于亲源关系较远、整体上不具有相似性而在一些较小的区域上存在局部相似性的 两个序列以下简单介绍几种典型的，得到广泛应用的比对算法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 、f a s t a l l 3 】1 14 】和b l a s t l l 5 】1 1 6 1 。 n e e d l e m a n - - w u n s c h 算法 n e e d l e m a n - - w u n s e h 算法是n e e d l e m a n 和w u n s c h 于1 9 7 0 年提出的的一个全局序列 比对算法，它是最早的序列比对算法，在其后的三十多年中得到了广泛的应用，成为生 物信息处理中的一个最基本的算法。其基本思想是利用动态规划思想计算两条序列之间 的全局最优比对 根据动态规划算法的原理，其基本思想可描述为：使用迭代方法计算出两个序列的 相似分值，存于一个得分矩阵中，然后根据这个得分矩阵，通过动态规划的方法回溯寻 找最优的比对序列 s m i t h - w a t e r m a n 算法 第4 页 国防科学技术大学研究生院学位论文 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 于1 9 8 1 年提出的一种用来寻找并比较 具有局部相似性区域的动态规划算法，在识别局部相似性时，具有很高的灵敏度，一直 是局部序列比对算法的基础，后来的许多算法都是基于这一算法开发和改进的。 其算法过程简单描述为： 1 ) 为每一碱基对或残基对赋值。相同或类似的赋予正值，对于不同的或有空位的赋 予负值： 2 ) 用0 对矩阵边缘单元初始化； 3 ) 矩阵中得分值相加，任何小于0 的得分值均用0 代替； 通过动态规划的方法，从矩阵中的最大分值单元开始回溯寻找，一直到分值为0 的 单元停止，此回溯路径的单元即为最优比对序列。 s m i t hw a t e r m a n 算法是生物信息学中最重要最基本的算法之一但是，随着生物数 据的急剧膨胀，s m i t hw a t e r m a n 算法的效率越来越不适于当前生物信息学研究的需求。 中科院计算机技术研究所生物信息学实验室实现了两种s m i t h w a t e r m a n 并行算法，并在 s m p 机群系统( 曙光3 0 0 0 ) 上实现了其中的并行算法1 1 7 1 。 f a s t a 算法和b l a s t 算法是目前应用最广的启发式比对算法，在第四章将有详尽 叙述。 ( 二) 多序列比对算法 多序列比对问题实际上是两条序列比对f 司题的一般化推广，但是由于d n a 或蛋白 质数据库容量的指数级增长。当比对的序列数目大大超过两个时，基于基本动态规划法 的多序列比对算法的计算量是非常惊人的，这使得多序列比对问题变得更加复杂。为了 解决这一问题，人们提出了许多近似算法和启发式算法算法。以下介绍几种典型的多序 列比对算法：动态规划算法、中心星比对算法和迭代比对算法等。 动态规划方法；给定k 条长度均为n 的序列，根据在两条序列比对中的动态规划算 法的思想，我们需要计算一个k 维的超级立方体，该立方体的尺寸为( n + 1 ) 3 。在双 序列比对的动态规划解决方案中，每一项( i j ) 要由( i l ，j - 1 ) ，( i q , j ) 和锄- 1 ) 这三项来 决定，在这个超级立方体中的每一项要有2 。一1 个相邻的项未决定这样，该问题的时 间复杂度是o ( ( 2 n ) k ) ，空间复杂度0 ( 2 十) 。 中心星比对算法：是一种多项式时间的算法，该算法所产生的比对要比最优算法所 得到的结果小近2 倍。算法过程是： 1 ) 首先在输入的k 条序列中找出一个序列s t ，s t e q ，使得。d ( s i ，s 1 ) 的值最小， 令a ； s t ) ； 2 ) 逐次添加s j q s 【) 到a 中，并使s i 与s t 的比对值最小，假设s l s 2 ，s i i 己添 加到a 中，由于在分别和s 。进行比对的过程中需要加入一些空格，故此时a 为： a = s l , s 2 ，s i 1 。，s 。) 。添加s i 到a 中，按照两条序列比对的动态规划算法比较s 。和 s i 分别产生新的序列s t ”和s j ，再按照s 。一中添加空格的位置调节序列s 1 ，s 2 ，s i + l 为 s l ”，s 2 。，s i 1 ”，并用s t ”替换s 第5 页 国防科学技术大学研究生院学位论文 迭代比对方法：这种方法是使用比对记分函数反复添加一个附加的序列到已比对的 比对序歹忡，首先在所有的双序列比对中找出距离值最小的一组，组成最优比对，然后 反复地找出与最优比对距离值最小的序列。与最优比对的表头文件进行匹配，并且根据 所得的结果相应地修改最优比对和表头文件。 最初的多序列比对算法基于动态规划法，由于实际数据利用多维的动态规划矩阵计 算量非常惊人，进行序列比对不太现实。上述两种近似算法和启发式算法可以提高算法 的运行速度，但也只是在算法的计算速度和获得最佳比对结果的敏感性之间寻找一种权 衡的策略。因此目前大多数实用的多序列比对程序采用基于渐进思想【18 】的启发式算法， 以降低运算复杂度。渐进比对的方法假设参与比对的序列存在亲缘关系。这类方法中使 用最广泛的是c l u s t a l 算法【19 】，是由f e l l g 和d o o l i t t e 于1 9 8 7 年提出的，它的基本思 想是：基于相似序列通常具有进化相关性这一假设。比对过程中，先对所有的序列进行 两两比对并计算它们的相似性分值，然后根据相似性分值将它们分成若干组，并在每组 之间进行比对，并计算相似性分值。根据相似性分值继续分组比对，直到得到最终比对 结果。比对过程中，相似性程度较高的序列先进行比对，而距离较远的序列添加在后面。 作为程序的一部分，c l u s t a l 可以输出用于构建进化树的数据。c l u s t a l 程序有许多 版本，可以基于u n d ( 、d o s 、w i n d o w s 平台。c l u s t a l 是免费软件，可以从互联网 上下载并和其它软件一起广泛用于序列分析。c l u s t a l 所支持的数据格式包括e m b l s w i s s p r o t 、n b r f r p i r 、p e a r s o n f a s t a 、g c g m s f ，以及c l u s t a l 本身定义 的格式。它的输出格式可以是c l u s t a l 格式，也可以是可用于g d e 、p h y l i p 、g c g 等 软件的格式。 降低算法复杂性，是研究多序列比对的一个重要方面。为此，产生了不少很有实用 意义的多序列比对算法。这些方法的特点是利用启发式( h e u r i a i c s ) 算法降低算法复杂 性，以获得一个较为满意但并不一定是最优的比对结果，用来构建进化树、查找保守序 列或序列模扳，以及进行聚类( c l u s t e r i n g ) 分析等。有的算法将动态规划和启发性算法 结合起来。例如，对所有的序列进行两两比对，将所有的序列与某个特定的序列进行比 对，根据某种给定的亲源树进行分组比对，等等。必须指出，上述方法求得的结果通常 不是最优解，并且结果的产生至少需要经过n 1 次双序列比对，其中n 为参与比对的序 列个数。 在国内，清华大学自动化系的计宏凯等提出了针对基因选择性剪接的多序列比对算 法i z 8 】，该算法是为了准确，快速、有效地研究真核基因的选择性剪接形式而提出的一种 启发式多序列比对算法。它借助引导树启发序列之间的两两段对段比对，通过建立序列 相似性估计模型，给出了一种由序列问相同词数估计序列相似程度的方法。利用这种方 法构造引导树，大大缩短了其构造时间。通过采用序列间的段对段比对，克服了空隙罚 分问题，更准确地反映了真核基因的选择性剪接形式。引导树构造方法的改迸和快速局 部比对算法的采用。使得算法运行速度大大高于一般算法。该算法为真核基因的选择性 第6 页 国防科学技术大学研究生院学位论文 剪接研究提供了一种新的有效途径，它能够很好地解决针对记忆内选择性剪接的多序列 比对问题。与一般的多序列比对算法相比，它能更准确地反映序列的不同剪接形式。它 既能在基因组信息尚不完全的情况下对一族选择性剪接产物进行研究，又能在基因组已 知的情况下，迅速把以前的结果与基因组建立联系。它的运行速度大大快于一般的多序 列比对算法，是用于研究基因选择性剪接的一种准确、快速、有效的算法。该算法己被 用于建立人类和小鼠基因的选择性剪接数据库a s m a m d b 。此外，该算法针对蛋白质序 列的推广正在研究之中。 华中科技大学计算机科学与技术学院的袁激光提出了基于a 算法的启发式算法【2 0 】 来求解多序列比对问题。通过分析动态规划算法及a 算法的特点，针对多序列比对问题 提出一种基于a 算法的启发式算法。该算法采用了多个优化搜索机制。通过对此算法的 理论分析，证明了它能够有效地减小搜索空间和节约搜索时间的同时，得到比较好的比 对结果。此算法不仅能够在多序列比对问题中得到应用，还能够用于其它有向无环图的 最短路径问题的求解 以上介绍的序列比对算法的研究现状中，国外在这方面的研究起步比较早，有很多 相对成熟的软件产品出现，而国内对于生物信息学方面的研究处于起步阶段，基因组信 息服务现在主要是一些国外的镜像( 包括数据和信息处理) ，比如北京大学的e m b l 镜 像；或者是一些比较简单的功能移植和开发，如广东金溯生物信息软件有限公司在网上 提供的限制性酶切分析、b l a s t 简单分析等，而自主开发的成熟的生物信息软件还很少 见对于序列比对算法的研究，中科院计算技术研究所与华大测序中心合作，基于曙光 3 0 0 0 超级计算机系统，开发了b l a s t ，p h r a p ，s m i t h - - w a t e r m a n 的并行算法，并应用 于华大测序中心的数据处理流程中。通过验证，当数据库的规模达到一定大小时，并行 b l a s t 程序能够大大减少检索时间，尤其在四个节点的情况下，可以降低大约5 0 的 检索时间，还有，中科院计算所的李昭等人提出了能存储约束条件下的序列比对算法 f a ( f a s t a l i g n m e n t ) 幽j ，在l i n u x 系统下试验，f a 算法的时间复杂度大大减小因此， 在国内大力开展生物信息学的研究势在必行。 从以上可以看出，生物信息学研究中对序列比对的算法研究具有非常重要的意义 一般来说，评价生物序列比对算法有两个标准，一为算法的运算速度，二为获得最佳比 对结果的敏感性。目前，己经存在很多序列比对软件，但仍存在一些问题。双序列比对 中常见的算法是s m i t h - - w a e r m a n 算法、b l a s t 算法与f a s t a 算法，它们是序列局部 比对算法的基础，后来的许多其它算法都是基于这些算法开发和改进的三者比较而言， s m i t hw a t e r m a n 敏感性强，但算法的复杂度最高，需要在具有极高计算能力的超级计算 机上实现；后两种则以敏感性的下降来换取速度上的提高，如b l a s t 运算速度最快， 可以在普通计算机上运行，但敏感性最差。对于多序列t e 对算法，有多维动态规划、多 维对角线法、渐迸多序列比对、交互多序列比对、模拟退火和系统发育分析等方法，其 中最为通用有效的主要是c 1 u s t a l ，除此之外，目前还缺乏快速而又十分有效的算法。 第7 页 国防科学技术大学研究生院学位论文 由此可见，目前序列比对中的主要困难就是如何研究和设计同时具有高敏感性和高速度 的算法。序列比对算法研究仍然是生物信息学中一个非常重要且具有挑战性的研究课题。 l - 3 课题任务及主要研究内容 随着生物学数据的大量积累，对序列比对算法的敏感性和时空复杂皮提出了更高的 要求，开发兼有高敏感性和高效率的算法成为序列比对的研究热点。由于比对的结果表 明了相应算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征，因此， 设计一个合理高效的序列比对算法是生物信息学领域中的一个非常重要的研究课题。本 文的研究目标是，在对前人研究成果分析的基础上，提出序列比对的改进与创新算法 主要研究内容如下： 1 学习分子生物学的有关知识，了解基因组、d n a 、比对的有关工艺流程和数据 处理过程，建立序列比对问题的背景知识； 2 研究序列比对问题的实质和技术特点，深入分析动态规划算法的理论基础、数 学模型及计算复杂性。 3 研究快速优化的动态规划算法。 4 在深入分析b l a s t 算法的基础上，基于序列划分策略，提出并实现高效的双比对 并行算法。 本文取得的成果如下： 1 基于经典的l p k k o i l e n 快速序列比对算法，借鉴f a 算法( f a s t a l i g n m e n t a l g o r i t h m ) 在计算得分矩阵时记录元素来源关系的存储方法，运用在矩阵中寻找c h e c k p o i n t 点的 c h e c k p o i n t 技术，提出一种基于动态规划思想的较为实用的双序列全局比对算法。 2 对几种经典的双序列比对算法进行了分析，并将其中一些算法与本文提出的新算 法进行了性能比较 3 在深入分析b l a s t 算法的基础上，基于序列划分策略，提出并实现新的并行双序 列比对算法，数值试验表明算法是高效的。 4 以本文提出的双序列比对算法为基础，设计并实现了个基于w i n d o w s 操作系统 的序列比对应用平台。 在攻读硕士学位期间，在核心期刊上发表论文2 篇，第一作者论文“b l a s t 算法及 t u r b o b l a s t 系统分析”发表于计算机科学与实践( 核心期刊) 2 0 0 5 年第5 期。 1 4 论文结构 论文共分五章结构如下： 第一章绪论介绍课题的研究背景，国内外序列比对的研究现状。 第二章序列比对相关知识介绍生物信息学中几个常识性的概念，以及序列数据 第8 页 国防科学技术大学研究生院学位论文 库、序列的相似性与同源性、全局比对和局部比对、比对分数矩阵和空位罚分等与序列 比对相关的概念。 第三章动态规划算法的分析及o g p 算法的设计较详细地描述了双序列比对的数 学模型，详尽阐述动态规划算法的思想，分析了几个较为常用的算法，并提出一种优化 的全局双序列比对算法( o g p ) 。 第