（计算机软件与理论专业论文）基于集群式超级计算机的三序列比对算法的并行实现及研究.pdf

上海大学硕士学位论文 摘要 序列比对算法用在许多不同的领域。当前，这些领域里面的一个重要应用就 是比对大分子，例如比对d n a ； u 蛋白质序列，以及蛋白质结构比较。基本上，所有 的序列比对算法，或多或少都会用到n e e d l e m a n 和w u n s c h ( 1 9 7 0 ) 的动态规划算 法。虽然从理论上来说用两两比对的方法来实现多序列比对是非常简单方便的， 但是，尽管目前人们做了大量的工作和努力，对于6 条以上的多序列比对，用两 两比对的方法是不现实的。而且对于属于n p 难问题的多序列比对问题，任何试图 找到一种快速的计算优化比对的方法的企图都很有可能要失败的。为了提高优化 比对的算法，全世界的科技工作者都马不停蹄地在辛苦地工作。这样就产生了许 许多多的近似优化比对的伪算法，同时也开发出一大堆应用程序。 许多情况下，都有必要同时比对三序列。d a v i dr p o w e l l 提出了一种新的使 用线性空位罚分的优化的三序列比对算法。这个算法最早是m u k k o n e n 基于两序 列和简单打分而提出的。本文基于分治法的原理通过引入“检查点法”对其进行 改进，并充分利用近期蓬勃发展的高性能计算技术，将其在c l u s t e r 机上并行实 现。 本文的主要贡献有以下四点： 1 ) 讨论了各种序列比对算法的优缺点，分析了一种基于线性空位罚分 年h u k k o n e n 算法的三序列比对算法的并行化问题。 2 ) 引入“检查点法”对这种三序列比对算法进行优化。 3 )利用分治法的原理将其在c l u s t e r 机上并行实现。 4 )提出了将现有序列比对算法并行化使之适应网格的分布式环境的研 究方向。 关键词：d n a 序列比对；三序列比对算法：算法并行化 上海大学硕士学位论文 a b s t r a c t s e q u e n c ea l i g n m e n ta l g o r i t h m sa r eu s e di n an u m b e ro fd i f f e r e n t a r e a s c u r r e n t l y ，o n eo ft h e s ei m p o r t a n ta r e a si st h ea li g n i n go fm a c r o m o l e c u l e ss u c ha sd n as e q u e n c e sp r o t e i ns e q u e n c e sa n dp r o t e i ns t r u c t u r e a l i g n m e n t b a s i c a l l y ，a l lm e t h o d sf o rs e q u e n c ea l i g n m e n ta r eb a s e d ，o n e w a yo ra n o t h e r ，o 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 mo fn e e d l e m a na n d w u n s c h ( 1 9 7 0 ) y e t ，w h i l ei ti s ，i nt h e o r y ，v e r ys i m p l ea n de l e g a n t ，t h e g e n e r a l i z a t i o no ft h ep a i r w i s em e t h o dt os i m u l t a n e o u sm u l t i p l es e q u e n c e a l i g n m e n ti sc o m p u t a t i o n a l l yd e m a n d i n ga n db e c o m e s - - d e s p i t em u c hw o r ko n i m p r o v i n gt h i ss i t u a t i o n - - i m p r a c t i c a b l ef o ra b o u ts i xa n dm o r es e q u e n c e s o fr e l e v a n t1 e n g t h m o r e o v e r ，w i t ht h en pc o m p l e t e n e s so fm u l t i p l e s e q u e n c ea li g n m e n t ，a n ya t t e m p ta td e v e l o p i n gaf a s ta l g o r i t h mf o rt h e c o m p u t a t i o no fo p t i m a la l i g n m e n t so fm a n ys e q u e n c e si se x p e c t e dt of a i l t oi m p r o v ea n do p t i m i z es e q u e n c ea l ig n m e n ta l g o r i t h m ，r e s e a r c h e sn e v e r s t o pw o r i d w i d e l y c o n s e q u e n t l y ，t h e r ei s ag r e a tn e e df o rh e u r i s t i c a l g o r i t h m sp r o d u c i n gn e a r o p t i m a la l i g n m e n t s ，a n da na b u n d a n c eo f p r o c e d u r e sh a v eb e e nd e v e l o p e d f o rm a n ya p p l i c a t i o n s ，i tisd e s i r a b l et oa l i g nt h r e es e q u e n c e sa t at i m e a na l g o r i t h mi sp r e s e n t e db yd a v i dr p o w e l lt oa l i g no p t i m a l y t h r e es e q u e n c e su s i n g1 i n e a rg a pc o s t s t h i sa l g o r i t h mi sa ne x t e n s i o n o ft h et w os e q u e n c e s i e s i m p l ec o s tu k k o n 6 n sa l g o r i t h m ( 1 9 8 3 ) i n t h ep a p e r ，w ef i r s tm o d i f yt h ea l g o r i t h mb yu s i n gc h e c kp o i n tt e c h n o l o g y b a s e do nt h ed i v i d ea n dc o n q u e ra l i g n m e n tm e t h o d ，a n di m p l e m e n ti to n c l u s t e r i n gc o m p u t e r sa n dp a r a l l e l i z et h ea l g o r i t h ms ot h a tt om a k eg o o d u s eo ft h eh i g h p e r f o r m a n c ea n dm a s s i v e l y p a r a l l e lc o m p u t i n gt e c h n o l o g y a p p e a r e dt h e s ey e a r s t h em a i nc o n t r i b u t i o n so ft h et h e s i sa r e ： 1 ) d i s c u s s i n gt h ep e r f o r m a n c eo fk i n d so fs e q u e n c ea l i g n m e n t a l g o r i t h m ，a n da n a l y z i n gt h ep a r a l l e l i z a t i o no fat h r e es e q u e n c e s a l i g n m e n tu s i n gl i n e a rg a pc o s t sa n db a s e do nu k k o n e na l g o r i t h m 2 ) m o d i f yt h ea l g o r i t h mb yu s i n gc h e c kp o i n tt e c h n o l o g y 3 ) i m p l e m e n ti to nc l u s t e r i n gc o m p u t e r sa n du s i n gd i v i d ea n dc o n q u e r m e t h o dt op a r a l l e l i z et h ea l g o r i t h m 4 ) b r i n gf o r w a r dt h er e s e a r c hd i r e c t i o n ：p a r a l l e l i z et h es e q u e n c e a l i g n m e n ta l g o r i t h mt of i ti nw i t ht h ed i s t r i b u t i n gs p e c i a l i t y o ft h eg r i d k e y w o r d s ：d n as e q u e n c ea l i g n m e n t s ；t h r e e 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 l g o r i t h mp a r a l l e l i z a t i o n 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：血导师签名：盟日期： h 海大学硕士学位论文 绪论 人，是我生中所遇到的最为美妙的迷高尔基 跨过了科技和工业高度发展的二十世纪，我们迎来了崭新的二十一世纪一 一信息时代。在这知识和科技高速膨胀的新时代里，我们将挥舞“信息”这一 魔棒，去尽情的探求物质和生命的本原。 爱因斯坦相对论的创建和量子力学的研究，将人们对物质世界的认识提升 到了一个新的高度。同样，信息时代的到来也将对人类自身的研究带入了定量 和微观。自文明开创以来一直困扰人类的两大问题：我们从哪里来? 要往何处 去? 人这一世界上最大的谜团也将在我们这一代人手中得出崭新的答案。 生命科学的研究核一i l , 就是对基因的研究。生命体表现出来的一切性状都能 归结到基因的控制。随着世界各地生物学家们不断地提交实验成果，产生了一 个庞大复杂的生物数据库。截止2 0 0 4 年4 月，g e n b a n k 中的d n a 碱基数目已达 3 8 9 亿8 千万 1 。并且还在以每隔一年翻一倍的速度增长。 率先完成水稻基因组工作框架图从而享誉国际的我国科学家，中科院遗传 所人类基因组中心副主任于军在2 0 0 4 年4 月1 6 日召开的国际人类基因组大会 上预测说：“未来5 年科学家将测出世界上几乎所有重要物种的基因序列。随着 基因测序成本逐年降低，各国在获取基因测序原始资料上的竞争将更加激烈” 2 。 在取得了这样的巨大成就后，一个新的问题摆在我们面前：如何解读这些 数据，从中提取出有用的信息? 在后基因组时代，完整基因组数据越来越多，有了这些资料人们就能对若 干重大生物学问题进行分析研究，如：生命是从哪里起源的? 生命是如何进化 的? 遗传密码是如何起源的? 估计最小独立生活的生物体至少需要多少基因? 这些基因是如何使生物体活起来的? 等等。这些重大的问题只有在基因组水平 l 二才能回答。举例来说，鼠和人的基因组大小相似，都含有约3 0 亿碱基对，基 因的数目也类似，且大部同源。可是鼠和人差异却如此之大，这是为什么? 同 样，有的科学家估计不同人种间基因组的差别仅为0 1 ；人猿间差别约为1 上海大学硕士学位论文 。但他们表型间的差异十分显著。因此，这种差异不仅应从基因、d n a 序列 找原因，也应考虑到整个基因组、考虑染色体组织上的差异。 生物信息学的发展在很大程度上是由人类基因组计划所推动的。该计划于 1 9 9 0 年启动，耗资3 0 亿美元，目的是测定人类基因组的全序列信息，2 0 0 3 年 4 月1 4 日人类基因组序列图绘制成功，人类基因组计划的所有目标全部实现。 国外一向都很重视生物信息学的发展。在1 9 8 7 年生物信息学 ( b i o i n f o r m a t i c s ) 词提出后，各种相关公司或研究机构雨后春笋般地涌现， 并且在许多大学和研究机构也都相继成立了自己的生物信息学部门或中心。例 如，1 9 8 8 年，美国国家生物技术信息中心( n c b i ) 在美国国会的支持下成立； 1 9 9 3 年3 月，欧洲生物信息学研究所( e b i ) 获准成立；1 9 9 5 年4 月，日本信 息生物学中一t i ( c l b ) 成立；1 9 9 8 年3 月，瑞士生物信息学研究所( s i b ) 成立。 其实，在这以前，国外在生物信息方面就已有较长时间的积累。例如：早 在6 0 年代，美国就建立了手工搜集数据的蛋白质数据库。而美国洛斯阿拉莫斯 国家实验室1 9 7 9 年就已经建立起g e n b a n k 数据库，欧洲分子生物学实验室于 1 9 8 2 年就已经提供核酸序列数据库e m b l 的服务，日本也于1 9 8 4 年着手建立国 家级的核酸序列数据库d d b 并于1 9 8 7 年开始提供服务。 生物信息学是一门交叉学科，它所研究的材料是生物学的数据，它进行研 究所采用的方法是从各种计算技术衍生出来的。而生物学数据的复杂性和海量 性决定必然要由计算机来帮助解读其中的信息。如今大型计算机的数据处理能 力已经发展到每秒数万亿乃至数十万，上百万亿次计算的水平。有了这一技术 支持条件，连同计算方法的创新和发展，基因组研究和其他生物学研究所产生 的海量数据，才能够得到有效地管理和处理，生物信息学才得以形成和发展。 如今，充分利用现有的资源，提出高效、精确的算法来处理庞杂的生物学数据 成了一项重要的研究课题。 高性能计算技术已经广泛应用于生物科学、空间科学、天文学、人工智能、 气象学和图像处理等各个研究领域。 为了在生物信息学领域能够更好的运用现有资源，发挥特长，就要对这些 领域内的算法进行一定的并行优化，将串行算法优化后移植到高性能并行机上 充分利用到“高性能”、“高效率”。 上海大学硕士学位论文 本文就是在研究了多种序列比对算法之后，选择了一种优秀的并且适合于 并行计算的三序列比对算法d a v i dr p o w e l l 算法，引入“检查点法”进行 了优化，使其可以在集群式高性能并行机上进一步得到高效的运用。同时，也 充分发挥了我校自强2 0 0 0 的优势，使其成功的运用在生物信息研究领域。 上海大学硕士学位论文 1 1 引子 第1 章基因与生物信息学 科技f | 报为纪念国庆5 5 周年，特别策划隆重推出了中国科技5 5 周年 5 5 个第一次。其中的第一名是“载人航天飞行获得圆满成功”，第二名是“第 一张人类基因组序列图成功绘制，我国承担1 项目”。下面是科技h 报2 0 0 4 年9 月2 8 同的部分原文摘录 3 ： 2 第一张人类基因纲序列圈成功绘制，我国承担1 项目 8 第张水稻基因组精细图绘制完成 1 9 体细胞克隆牛降生 2 5 第一次成功克降大鼠 2 7 第一株转基闲抗螟虫品系克螟稻 3 0 第- 个杂交早稻不育系成活 3 8 第次运用基因方法重组人胰岛索 3 9 第一例癌症检测生物芯片率先开发 驯第一个s a r s 疫苗研制成功 4 6 第。头转人岩藻糖转移酶基因克隆牛 5 ( ) 基因治疗药物在我国获准正式上市 5 3 大豆杂交种在吉林诞生 5 4 笫一次揭开人类衰老之迷 5 5 第次绘制完成家蚕基i 羽组”框架图” 5 5 项中就有1 4 项与基因有关。在这些举世瞩目的成就中，我们总是能看 见“基因”的影子。这些成就的取得固然与我国生物工作者的聪明爿智和辛勤 劳动息息相关，它同时也从另外个角度证实了生物学科的厂+ 阔的发展前景。 2 0 0 0 年6 月2 6 日，美国总统克林顿和英困首相布莱尔在联合新闻发布会 上宣告人类基因组“工作框架图”绘制完成。人类历史上还从未有过两个国家 的诗脑同时把自己与一项科学进展如此拉近 4 。 2 0 0 3 年4 月1 4 日人类基因组序列图绘制成功，人类基因绢计划的所有 t 海大学硕士学位论文 标全部实现。我国是唯+ 参与人类基因组测序的发展中国家。 人类基因组计划( h u m a ng e n o m ep r o j e c t ，简称h g p ) 是美园科学家在i 9 8 5 年率先提出的，其目的在于阐明人类基因组d n a ( 脱氧核糖核酸) 核营酸序列， 破译人类全部遗传信息 5 。基因组讨划与1 9 9 0 年1 0 月在美国正式启动，其核 心内容是构建d n a 序列图，即分析人类基因组d n a 分子的基本成分碱基的排列 顺序，绘制成序列图。英、曰、德、法等固随后积极响应，使人类基冈组计划 逐步演变成为一项大型国际科技合作计划。备国在该计划中所承担的工作比例 大致为美国5 4 、英国3 3 、日本7 、法国2 8 、德国2 2 、中国1 。我国于 1 9 9 9 年起开始参与人类基因组计划这重大科学工程。承担的工作区域位于人 类3 号染色体短臂卜。该区域约占人类基因组的1 ，因此简称“1 项目”。 随着h g p 产生的数据爆炸，一门新兴学科一一生物信息学应运而生。生物 信息学是以训算机为主要工具，开发各种软件，对翻益增长的d n a 和蛋白质序 列和结构等相关信息进行收集、储存、发行、提取、加工、分析和研究，同时 建立理论模型，指导实验研究。它由数据库、计算机网络和应用软件三大部分 构成，在基因组计划中发挥不可替代的作用。 。 美国人类基因组讨伐0 中给基因组信息学的定义是：它是一个学科领域，包 含着基因组信息的获取、处理、存储、分配、分析和解释的所有方而。该定义 包含两方面的内容：一方面是发展强大有效的信息分析工具，构建适合于基闲 组研究的数据库，用于搜索、管理、使用人类基因组和模式生物基因组的巨量 信息；另一方面是配合实验研究，确定约3 0 亿个碱基对的人类基因组完整核苷 酸顺序，找出人类全部约1 0 万个基因在染色体上的位置以及包括基因在内的各 种d n a 片段的功能，即”读懂”人类基因。 如此海量目又复杂的生物学数据，对计算机科学和信息技术无疑是一种压 力和挑战。值得庆幸的是，人类基因组计划一开始就与信息高速公路和数据库 技术形成了同步发展。在现有的形势下，世界各国政府和民间都不遗余力的加 大对生物信息学的研究力度，把巨大的人力物力投入进来，培养具有跨学科能 力的人才，建立大规模的生物信息学服务系统，以求彻底解读所有的遗传信息。 如今，国际上的三大生物信息中心即美国的国家生物技术信息中心 ( n c b i ) 、欧洲生物信息学研究所( e b i ) 和日本d n a 数据库( d d b 7 ) 已经建立 上海大学硕士学位论文 和维持了源自数百种生物的d n a 序列的大型数据库。大量的数据被产生并管理 起来，包括核酸序列库、蛋白质序列库、分子建模数据库等级和= 级数据库。 同时，一大批管理和分析生物数据的软件被开发出来，比如由n c b i 开发和维护 的e n t r e z 分子检索系统、b l a s t 、s m it h w a t e r m a n 、c l u s t a l w 算法等，作为信 息检索、序列比对、分子建模和预测的工具。基因组学的研究从结构基因组学 过渡到功能基因组学，即从“是什么”过渡到“为什么”的研究 6 。 生物信息学的发展，不仅导致生物学、物理学、数学、计算机科学等多种 科学文化的融合和相互促进，也必将造就一批新的从事交叉学科研究的科学工 作者。科学家们普遍相信本世纪初的若干年是人类基因组研究取得辉煌成果的 时代，也是它创造巨大的经济效益和社会效益的时代。 1 2 生物信息学研究的意义 生物信息学的研究结果不仅具有重要的理论价值，也可直接应用到工农业 生产和医疗实践当中去。因此，生物信息学相关的分析与应用算法、软件和数 据库，都具有重要的经济价值，最终都会形成商品，提供经济和社会效益 7 。 很多疾病与基因突变或基因多态有关，有人估计与癌症相关的原癌基因约 有1 0 0 0 个，抑癌基因约有1 0 0 个。约有6 0 0 0 种以上的人类疾患与各种人类基 因的变化相关联。更多的疾病是环境( 包括致病微生物) 与人类基因( 基因产 物) 相互作用的结果。随着人类基因组计划的深入，当我们解读了人类全部基 因特征以后，人们就可以有效地判定各种疾患的分子机制，进而发展合适的诊 断和治疗手段。 根据不同物种间的进化距离和功能基因的同源性，可以比较容易地找到各 种家畜、经济作物与其经济效益相关的基因，并进一步认识它们发育、生长和 抗逆的各种途径和机制。在此基础上，利用相关的基因组分子标记，就可以加 快育种的速度，将它们按照人们的愿望加以改造，为人类造福。 人类基因组学是生物技术产业和健康产业的知识核心，蕴藏着无比巨大的 产业化潜能和商业利益。基于基因组研究成果的基因工程药物，基因治疗、生 物芯片诊断技术等，有着极其广阔的应用前景；基于基因组知识为基础的药物 设计，尤其是基于药物基因组学的个体化药物治疗等，将会大大提高治疗效果 的同时最大限度地降低药物毒性。这些成果和进展已经显示出基因组的研究将 上海大学硕士学位论文 会从根本上改变疾病诊断，提高其质量，带来巨大的社会、经济效应。 1 3 国内外研究现状 国际一k 生物信息学研究在各个发达囡家中比较受熏视。近年来，美国一些 最著名的大学，如哈佛大学、普林斯顿大学、斯坦福大学、加州大学伯克利分 校等都投资几千万到一亿多美元成立了生物学、物理学、数学等学科交叉的研 究中心。美国n i h ( n a t i o n a li n s t i t u t e so fh e a l t h ) 的一个顾问小组建议在 生物计算领域设立总额为数亿美元的重大科研基金，并成立5 到2 0 个计算中心 以处理海量的基因组相关信息。 基因组研究潜在的巨大商业利润使得国际上一批大型制药公司和化学公 司向该领域大规模的进军。各大计算机公司也纷纷投巨资加强高性能计算机的 研制工作。为了满足人类基因组计划的研究需要，i b m 至今在生物科技领域已 经投资2 亿美元，集中了不同领域的5 0 名研究员专门从事计算机应用于生物科 技领域的研究，投入1 亿美元开发有i 0 0 万个c p u 、每秒运算速度高达千万亿 次的超级计算机“蓝色基因”，专为生物信息学研究服务。 随着破译生命密码的人类基因组计划接近尾声，科学家们又全力以赴投入 到了生物学下一个挑战性领域的研究：蛋白质组学( p r o t e o m i c s ) 。人体内真正 发挥作用的是蛋自质，蛋自质扮演着构筑生命大厦的“砖块”角色，其中藏着 开发疾病诊断方法和新药的“钥匙”。由于生物功能的主要实现者是蛋白质， 而蛋白质又有自身特有的活动规律，所以仅仅从基因的角度来研究是不够的。 美国米里亚德遗传学研究所、甲骨文公司和日本日立公司组成联盟，计划在3 年内完成人体所有蛋白质的图谱。美国塞莱拉公司现已进入蛋白质组研究阶段， 目的是每天对数百万个蛋白质片段进行识别和分类，最终绘制出一张蛋白质组 图。 这些研究掀起了一场寻找新蛋白质以及确定它们功能的竞赛。美国加州前 线战略管理咨询公司的一项研究显示：蛋白质组学已逐步形成产业和市场，目 前这个市场的规模已经有巨大发展，有望从2 0 0 0 年的5 6 亿美元扩大到2 0 0 5 年的2 7 7 亿美元。 国际上生物信息学发展异常迅猛，大大带动了我国生物信息学的发展。在 我国，生物信息学随着人类基因组研究的展开才刚刚起步，但已最露出蓬勃发 上海大学硕士学位论文 会从根本上改变疾病诊断，提高其质量，带来巨大的社会、经济效应。 1 3 国内外研究现状 国际e 生物信息学研究在各个发达国家中比较受熏视。近年来，美国一些 最著名的大学，如哈佛大学、普林斯顿大学、斯坦福大学、加州大学伯克利分 校等都投资几千万到一亿多美元成立了生物学、物理学、数学等学科交叉的研 究中心，美国n i l l ( n a t i o n a li n s t i t u t e so fh e a l t h ) 的一个顾问小组建议存 牛物计算领域设立总额为数亿美元的重大科研基金，并成立5 到2 0 个计算中心 以处理海量的基因组相关信息。 基因组研究潜在的巨大商业利润使得围际上一批大型制药公一j 和化学公 司向该领域大规模的进军。各大计算机公司也纷纷投巨资加强高性能计算机的 研制工作。为了满足人类基因组计划的研究需要，1 b m 至今在生物科技领域已 经投资2 亿美元，集中了不同领域的5 0 名研究员专门从事计算机应用于生物科 技领域的研究，投入1 亿美元开发有i 0 0 万个c p u 、每秒运算速度高达千万亿 次的超级计算机“蓝色基因”，专为生物信息学研究服务。 随着破译生命密码的人类基因组计划接近尾声，科学家们又全力以赴投入 到了生物学下一个挑战性领域的研究：蛋白质组学( p r o t e o m i c s ) 。人体内真正 发挥作用的是蛋白质。蛋白质扮演着构筑生命大厦的“砖块”角色，其中藏着 开发疾病诊断方法和新药的“钥匙”。由丁生物功能的主要实现者是蛋白质， 而蛋白质又有自身特有的活动规律，所以仅仅从基因的角度来研究是不够的。 美国米里亚德遗传学研究所、甲骨文公司和目本日立公司组成联盟，计划在3 年内完成人体所有蛋白质的图谱。美国塞莱拉公司现己进入蛋白质组研究阶段， 目的是每天对数百万个蛋白质片段进行识别和分类，最终绘制出一张蛋白质组 图。 这些研究掀起了一场寻找新蛋白质以及确定它们功能的竞赛。美国加州l j i 线战略管理咨询公司的一项研究显示：蛋白质组学已逐步形成产业和市场，目 前这个市场的规模已经有巨大发展，有望从2 0 0 0 年的5 6 亿美元扩大到2 0 0 5 年的2 7 7 亿美元。 国际上生物信息学发展异常迅猛，大大带动了我国生物信息学的发展。在 我国，牛物信息学随着人类基因组研究的展开才刚刚起步，但已娃露出蓬勃发 我国，生物信息学随着人类基斟组研究的展奸才刚刚起步，但已显露出蓬勃发 上海大学硕士学位论文 展的势头。许多科研单位已经开始或准备开始从事这方面的研究工作。北京大 学建立起一个e m b i ，的镜像数据库，提供数据检索服务。在复旦大学遗传学研究 所，为克隆新基因而建立的一整套生物信息系统也已初具规模。中科院上海生 化所、生物物理所等在结构生物学和基因预测研究方面也育相当的基础，中科 院计算所也开始在生物信息方面投入大量的人力物力，从事相关的研究。南、 北方人类基冈组中一t l , 的相继建成，北大生物城的建立等，标志着我国对生物信 息学的重视。我们有理由相信，我国的生物信息学在2 1 世纪会有巨大的飞跃。 中科院计算所生物信息学试验室创立的p r o m o t o r 生物信息处理平台是一 个基于”曙光3 0 0 0 ”高性能计算机的生物信息并行处理平台，该平台集成大量幽 际通用算法以及我们自己开发的原创性算法，具有高度并行化、运行速度快、 功能丰富的特点。适于海量数据处理，l 司时具有用户友好界面以及可视化功能， 可以为生物学家提供良好的、高效的计算服务。 杭州华大基因研究发展中，t l , 提供了一系列的高性能计算资源服务。曙光 2 0 0 0 、曙光3 0 0 0 、s u n 系列服务器可以提供最好最快的高性能计算服务。能够 存贮和处理海量的数据，服务于具有特殊要求的单位和研究团体。现在已经利 用这个资源提供包括蛋白质三维结构预测、新药模拟开发在内的高要求数据计 算服务。 在此基础上我国科研人员取得了可喜的成果。开发出了达到国际先进水平 的软件，比如基因的电脑克隆软件包、d n a 序列综合特征信息分析软件包、蛋 白质组数据分析研究软件包等。围绕高性能计算机系统开展大计算量算法与软 件的并行化工作，例如把b l a s t ，p h r a p ，s m i t h w a t e r m a n 和p r o s p e c t o r 等软件的 并行化，实现最大限度地发挥大规模并行计算机的效率。其巾最引人关注的是 由国家杂交水稻研究中心、华大基因研究中心和中科院遗传所植物生物技术实 验室三家单位联合开展的研究项目”超级杂交水稻基因组计划”，2 0 0 2 年4 月4 只，中国科学院和美国科学杂志在京联合举行通报会宣布：地球上一半以 上的人类所赖以生存的粮食作物水稻的基因序列不仅被中国科学家独立绘 制完成，而且获得成功“解读”，从而使人类第一次在基因组层面“认识”水 稻。期间共测了近五亿个碱基对，目前正在对有关数据进行整理，对己定位的 基因进行深入的功能鉴定和分析，并构建d n a 库。值得一提的是，通过测序发 上海大学硕上学位论文 现了与光合作用相关的基因位点，而光合作用与超高产密切相关，从而使我们 的水稻品种得到更大改良，产量更高，品质更好成为可能。由此可见，基因工 程和传统育种技术的结合，在中国农作物品种改良研究中将大有可为。 1 4 本章小结 本章主要介绍了生物信息学的背景知识。包括生物信息学的概念、研究的 意义和国内外的研究现状等三个方面。阐明了计算机科学特别是高性能计算机 在生物信息学研究中的巨大作用。 上海大学硕士学位论文 第2 章序列比对算法 “比较”是科学研究中最常见的方法，通过将研究对象相互比较来寻找对 象可能具备的特性。在生物信息学研究中，“比对”是最常用和最经典的研究手 段，是实现同源比较的方法。 比对还是数据库搜索算法的基础，将查询序列与整个数据库的所有序列进 行比对，从数据库中获得与其最相似序列的已有的数据，能最快速的获得有关 查询序列的大量有价值的参考信息，对于进一步分析其结构和功能都会有很大 的帮助。近年来随着生物信息学数据大量积累和生物学知识的整理，通过比对 方法可以有效地分析和预测一些新发现基因的功能。 2 1 生命科学知识简介 在生物体的每一个体细胞核中都包含了一种叫“染色体”( c h r o m o s o m e ) 的物质 8 。比如说：人的每个体细胞中都含有4 6 条染色体，它们成对出现， 其中2 2 对是常染色体，一对是性染色体( x x 或者x y ) 。染色体主要由蛋白质 和d n a ( 脱氧核糖核酸) 这两种物质组成。d n a 是由a ，c ，g ，t ( 腺嘌呤、 胞嘧啶、鸟嘌呤、胸腺嘧啶) 四种碱基连接而成的聚合物。四种碱基互相连接 的氢键有严格的互补关系：a t 、g c 。如下所示： aacggtttccggagctggattc t t g ccaaaggcc t c g a c c t a a g iiiiiiil lli 图2 1d n a 的组成 1 9 5 3 年w a t s o n 和c r i c k 提出了d n a 的双螺旋结构模型，揭示了d n a 作 为遗传信息携带者的本质。二十世纪六十年代遗传密码被破译：四种碱基的每 三个碱基组成一个密码，共有6 4 种排列方式( 4 4 x 4 ) 。进一步发现密码是简 并的，即两种以上的三联体决定一个氨基酸，一共可以表示2 0 种氨基酸。这些 氨基酸不同顺序的排列以肽链连接就构成了蛋白质。生物体的所有“部件”， 包括皮、毛、骨骼、脏器都是由蛋白质构成的。蛋白质扮演着构筑生命大厦的 “砖块”角色。绝大多数生物的遗传物质都是d n a ，而且每种生物d n a 的化 学组成和碱基配对规律都是一样的。但是物种之间的差异如此之大，使我们不 j n 上晦大学硕士学位论文 a a c u u g u c c u u u g g a c u a c c g u u g c a a u c g g 图2 4 附 的组成 因此得到的三联体密码子是u c a 、u a g 、g a c 、a a c 等，分别对应一种 氨基酸。m r n a 上携带的遗传信息指导蛋白质的合成过程，称为翻译 ( t r a n s l a t i o n ) 。在另外两种r n a ：核糖体r l q a ( r i b o s o m a lr n a ，r r n a ) 、转运 r n a ( t r a n s f e rr n a ，t r n a ) 的共同作用下，碱基序列按照密码子的对照被翻译 成氨基酸多肽链，这个氨基酸的序列决定了蛋白质的三维空间结构，从而导致 了生命表现形式的多样性。 2 2 序列两两比对 序列比对的理论基础是进化学说，如果两个序列之间具有足够的相似性， 就推测二者可能有共同的进化祖先，经过序列内残基的替换、残基或序列片段 的缺失、以及序列重组等遗传变异过程分别演化而来。序列相似和序列同源是 不同的概念，序列之间的相似程度是可以量化的参数，而序列是否同源需要有 进化事实的验证。在残基一残基比对中，可以明显看到序列中某些氨基酸残基 比其它位置上的残基更保守，这些信息揭示了这些保守位点上的残基对蛋白质 的结构和功能是至关重要的，例如它们可能是酶的活性位点残基，形成二硫键 的半胱氨酸残基，与配体结合部位的残基，与金属离子结合的残基，形成特定 结构m o t i f 的残基等等。但并不是所有保守的残基都一定是结构功能重要的， 可能它们只是由于历史的原因被保留下来，而不是由于进化压力而保留下来。 因此，如果两个序列有显著的保守性，要确定二者具有共同的进化历史，进而 认为二者有近似的结构和功能还需要更多实验和信息的支持。通过大量实验和 序列比对的分析，一般认为蛋白质的结构和功能比序列具有更大的保守性，因 此粗略的说，如果序列之间的相似性超过3 0 ，它们就很可能是同源的。 早期的序列比对是全局的序列比较，但由于蛋白质具有的模块性质，可能 由于外显子的交换而产生新蛋白质，因此局部比对会更加合理。通常用打分矩 阵描述序列两两比对，两条序列分别作为矩阵的两维，矩阵点是两维上对应两 个残基的相似性分数，分数越高则说明两个残基越相似。因此，序列比对问题 变成在矩阵里寻找最佳比对路径，目前最有效的方法是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 算法和s i m 算法。在 上海大学硕士学位论文 f a s t a 程序包中可以找到用动态规划算法进行序列比对的工具l a l i g n ，它能 给出多个不相互交叉的最佳比对结果。 在进行序列两两比对时，有两方面问题直接影响相似性分值：取代矩阵和 空位罚分。粗糙的比对方法仅仅用相同不同来描述两个残基的关系，显然这种 方法无法描述残基取代对结构和功能的不同影响效果，缬氨酸对异亮氨酸的取 代与谷氨酸对异亮氨酸的取代应该给予不同的打分。因此如果用一个取代矩阵 来描述氨基酸残基两两取代的分值会大大提高比对的敏感性和生物学意义。虽 然针对不同的研究目标和对象应该构建适宜的取代矩阵，但国际上常用的取代 矩阵有p a m 和b l o s u m 等，它们来源于不同的构建方法和不同的参数选择，包括 p a m 2 5 0 、b l o s u m 6 2 、b l o s u m 9 0 、b l o s u m 3 0 等。对于不同的对象可以采用不同的 取代矩阵以获得更多信息，例如对同源性较高的序列可以采用b l o s u m 9 0 矩阵， 而对同源性较低的序列可采用b l o s u m 3 0 矩阵。 空位罚分是为了补偿插入和缺失对序列相似性的影响，由于没有什么合适 的理论模型能很好地描述空位问题，因此空位罚分缺乏理论依据而更多的带有 主观特色。一般的处理方法是用两个罚分值，一个对插入的第一个空位罚分， 如l o 一1 5 ；另一个对空位的延伸罚分，如1 2 。对于具体的比对问题，采用不 同的罚分方法会取得不同的效果。 对于比对计算产生的分值，到底多大才能说明两个序列是同源的，对此有 统计学方法加以说明，主要的思想是把具有相同长度的随机序列进行比对，把 分值与最初的比对分值相比，看看比对结果是否具有显著性。相关的参数e 代 表随机比对分值不低于实际比对分值的概率。对于严格的比对，必须e 值低于 一定闽值才能说明比对的结果具有足够的统计学显著性，这样就排除了由于偶 然的因素产生高比对得分的可能。 g e n b a n k 、s w i s s p r o t 等序列数据库提供的序列搜索服务都是以序列两两 比对为基础的。不同之处在于为了提高搜索的速度和效率，通常的序列搜索算 法都进行了一定程度的优化，如最常见的f a s t a 工具和b l a s t 工具。f a s t a 是 第一个被广泛应用的序列比对和搜索工具包，包含若干个独立的程序。f a s t a 为了提供序列搜索的速度，会先建立序列片段的“字典”，查询序列先会在字典 里搜索可能的匹配序列，字典中的序列长度由k t u p 参数控制，缺省的k t u p = 2 。 上海大学硕士学位论文 f a s t a 的结果报告中会给出每个搜索到的序列与查询序列的最佳比对结果，以 及这个比对的统计学显著性评估e 值。f a s t a 工具包可以在大多提供下载服务 的生物信息学站点上找到。 b l a s t 是现在应用最广泛的序列相似性搜索工具，相比f a s t a 有更多改进， 速度更快，并建立在严格的统计学基础之上。n c b i 提供了基于w e b 的b l a s t 服 务，用户可以把序列填入网页上的表单里，选择相应的参数后提交到数据服务 器上进行搜索，从电子邮件中获得序列搜索的结果。b l a s t 包含五个程序和若 干个相应的数据库，分别针对不同的查询序列和要搜索的数据库类型。其中翻 泽的核酸库指搜索比对时会把核酸数据按密码子按所有可能的阅读框架转换成 蛋白质序列。b l a s t 对序列格式的要求是常见的f a s t a 格式。f a s t a 格式第一行 是描述行，第一个字符必须是“ ”字符；随后的行是序列本身，一般每行序列不 要超过8 0 个字符，回车符不会影响程序对序列连续性的看法。序列由标准的 i u b i u p a c 氨基酸和核酸代码代表；小写字符会全部转换成大写；单个“一”号代 表不明长度的空位；在氨基酸序列里允许出现“u ”和“ ”号；任何数字都应该被去 掉或换成字母( 如，不明核酸用“n ”，不明氨基酸用“x ”) 。此外，对于核酸序列， 除了a 、c 、g 、t 、u 分别代表各种核酸之外，r 代表g 或a ( 嘌呤) ；y 代表t 或 c ( 嘧啶) ；k 代表g 或t ( 带酮基) ；m 代表a 或c ( 带氨基) ：s 代表g 或c ( 强) ；w 代表a 或t ( 弱) ；b 代表g 、t 或c ；d 代表g 、a 或t ；h 代表a 、c 或t ；v 代表 g 、c 或a ；n 代表a 、g 、c 、t 中任意一种。对于氨基酸序列，除了2 0 种常见 氨基酸的标准单字符标识之外，b 代表a s p 或a s n ；u 代表硒代半胱氨酸；z 代 表g l u 或g i n ；x 代表任意氨基酸；“”代表翻译结束标志。 2 3 多序列比对 顾名思义，多序列比对就是把两条以上可能有系统进化关系的序列进行比 对的方法。目前对多序列比对的研究还在不断前进中，现有的大多数算法都基 于渐进的比对的思想，在序列两两比对的基础上逐步优化多序列比对的结果。 进行多序列比对后可以对比对结果进行进一步处理，例如构建序列模式的 p r o f i l e ，将序列聚类构建分子进化树等等。 目前使用最广泛的多序列比对程序是c l u s t a l w ( 它的p c 版本是 上海大学硕十学位论文 c l u s t a l x ) 。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 程序用选项单逐步指导用户进行操作，用户可根据需要选择打分矩 阵、设置空位罚分等。e b i 的主页还提供了基于w e b 的c l u s t a l w 服务，用 户可以把序列和各种要求通过表单提交到服务器上，服务器把计算的结果用 e m a i l 返回用户。c l u s t a l w 对输入序列的格式比较灵活，可以是前面介绍过 的f a s t a 格式，还可以是p i r 、s w i s s p r o t 、o d e 、c l u s t a l 、g c g m s f 、r s f 等格式。输出