（计算机软件与理论专业论文）蛋白质数据库去冗余程序的研究与开发.pdf

华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 论文摘要 许多生物序列数据库中都含有大量的冗余序列，这些冗余序列通常不利于对数据库 的统计分析和处理，而且它们要占用更多的计算机存储和处理资源。去除这些冗余信息 具有很高的实用价值，不但可以减小数据库的大小提高序列搜索的速度，而且有助于对 数据库的统计分析。目前存在不少蛋白质去冗余程序，它们多数采用h o b o h m 和s a n d e r 的算法来生成代表序列以达到去除冗余序列的目的。然而，这种算法生成的代表序列集 合不是足够大的，某些非冗余的蛋白质序列也被去除了。 在本文中，我们对蛋白质去冗余问题进行了深入的分析和研究，主要研究内容和取 得的成果如下： 1 改进了h o b o h m 和s a n d e r 的算法：我们基于图论最大独立集的概念来生成非冗余序 列集合，对目前存在的蛋白质去冗余程序如c d - h i t 、p i s c e s 等所采用的由h o b o h m 和s a n d e r 最早设计的一种首先将序列集合分成若干个簇然后取出每个簇的代表序 列的算法进行了改进，使得生成了更大的非冗余代表序列集合，避免了一些非冗余 的序列也被去除。 2 基于上述改进算法，我们开发了两个版本的f a s t c l u s t e r ：第一个版本基于全局比 对算法来确定序列之间的相似度，提供了一种从全局比对角度来去除冗余序列的程 序，其缺点在于运行速度较慢，不太适合处理大规模的数据集；第二个版本采用了 b l a s t 来确定序列之间的相似度，提高了运行速度，可以在较短的时间内处理较大 规模的蛋白质数据库。f a s t c l u s t e r 的下载地址是： h t t p ：p c a l b i o s i n o o r g f a s t c l u s t e r h t m l 3 建立了蛋白质序列数据库的无向图模型，并开发了相应的程序b l a s t c u l l e r ：一个 蛋白质序列集合可以看作是一个无向图，序列对应图中的顶点，如果两个序列之间 的相似度超过某个设定的阈值则这两个序列之间存在一条边。基于该模型开发的 b l a s t c u l l e r 不仅具有很高的实用价值，能够处理较大规模的蛋白质序列数据库，而 且为去冗余问题提供了一个有效的可扩展的程序框架，可以加入新的算法来更好地 解决去冗余问题。b l a s t c u l l e r 的下载地址是：h t t p ：p c a l b i o s i n o o r g b l a s t c u l l e r h t m l 测试数据证明，本文所设计的生成非冗余代表序列的改进算法具有很强的实用性， 有效地避免了一些非冗余的序列也被去除，生成了更多的非冗余代表序列集合；基于无 向图模型所开发的8 1 a s t c u l l e r 程序具有较好的通用型和扩展性，可以在其基础上对去 冗余问题做进一步的研究。 【关键词】生物信息学；图论：代表序列；去冗余；b l a s t 华东师范大学2 0 0 8 届硕七学位论文蛋白质数据库去冗余程序的研究与开发 a b s t r a c t m a n yb i o l o g i c a ls o q u e n c ed a t a b a s e sh a v er e d u n d a n ts e q u e n c e sw h i c ha r en o th e l p f u lt o s t a t i s t i c a la n a l y s i sa n dr e q u i r em o r ec o m p u t a t i o n a lt i m ea n dr e s o u r c e st op r o c e s s s i n c et h e s e r e d u n d a n ts e q u e n c e so f t e nd on o tp r o v i d em o r ei n f o r m a t i o n , i ti sv e r yu s e f u la n dp r a c t i c a lt o r e m o v et h e m i nt h i sp a p e r , w eh a v er e s e a r c h e do nt h ei s s u eo f r e m o v i n gr e d u n d a n t p r o t e i n sa n d t h e a c h i e v e m e n t sw eh a v em a d ea g ea sf o l l o w s ： 1 m a d ea ni m p r o v e m e n tt oh o b o h ma n ds a n d e r sa l g o r i t h m ：w ed e s i g n e dai l e wa l g o r i t h m u s i n gm a x i m u mi n d e p e n d e n ts e to f g r a p ht h e o r yt og e n e r a t ear e p r e s e n t a t i v es e t o u r a l g o r i t h mc a na v o i dr e m o v i n gn o n r e d u n d a n ts e q u e n c e se f f e c t i v e l ya n dt h u sg e n e r a t e m o r er e s u l ts e q u e n c e s 2 d e v e l o p e dp r o g r a mf a s t c l u s t e rw i t ht w od i f f e r e n tv e r s i o n s ：f a s t c l u s t e ri m p l e m e n t e do i l l i m p r o v e da l g o r i t h ma n di th a d t w ov e r s i o n s t h ef i r s tv e r s i o nu s e sg l o b a ls e q u e n c 圩 a l i g r u n e n tt od e t e r m i n et h es e q u e n c es i m i l a r i t yw h i c hm n ss l o wa n di sn o t 锄i t a b l et o p r o c e s sl a r g ed a t a b a s e ，w h i l et h es e c o n dv e r s i o nu s e sb l a s t t od e t e r m i n et h es i m i l a r i t y b e t w e e nt w os e q u e n c e si no r d e rt og e tb e t t e rs e q u e n c es i m i l a r i t ya n df a s t e rs p e e da n di t c a nb ed o w n l o a d e df r o mh t t p ：p c a l b i o s i n o o r g f a s t c l u s t e r h t m l 3 c o n s t r u c t e dag r a p hm o d e lf o rs e q u e n c e sd a t a b a s ea n dd e v e l o p e dp r o g r a mb l a s t c u l l e r ： a nu n d i r e c t e dg r a p hi su s e dt or e p r e s e n tr e l a t i o n sb e t w e e n p r o t e i ns e q u e n c e si nw h i c ha v e r t e xr e p r e s e n ta p r o t e i ns e q u e n c ea n d 如e d g cr e p r e s e n t st h a tt w op r o t e i ns e q u e n c e s h a v eas i m i l a r i t ya b o v et h eg i v e i lt h r e s h o l d s u c ha g r a p hm o d e lh e l p s 啪u n d e r s t a n d r e d u n d a n c yp r o b l e mm o r ec l e a r l y o u rp r o g r a mb l a s t c u l l e ru s e sag r a p ht h e o r y a l g o r i t h mt og e n e r a t eam a x i m a ln o n - r e d u n d a n ts e q u e n c es e tf r o map r o t e i nm x l u e n c c c d a t a b a s e b l a s t c u l l e rp r o v i d e sa ne f f e c t i v ea n de x t e n d a b l ef r a m e w o r kf o rt h ei s s u eo f r e m o v i n gr e d u n d a n c ya n dc a nb eu s e dt op r o c e s sap r o t e i ns e q u e n c ed a t a b a s eo fl a r g e s c a l e t h ed o w n l o a d e du r lf u rb l a s t c u l l e ri sh t t p ：p c a l b i o s i n o u r # b l a s t c u l l e r h t m i t h et e s t sh a v ep r o v e dt h a to u ri m p r o v e da l g o r i t h mo f h o b o h ma n ds a n d e ri sp r a c t i c a l a n de f f e c t i v e ，w h i c hc a na v o i d r e m o v i n gn o n r e d u n d a n ts e q u e n c e se f f e c t i v e l ya n dt h u s p r o d u c em o r en o n r e d u n d a n ts e q u e n c e s a n db l a s t c u l l e r , w h i c hw a sd e v e l o p e db a s e do n a g r a p hm o d e l ，i sv e r yg e n e r a la n de x t e n d a b l e w ec a nm a k e $ o m ei m p r o v e m e n t st ob l a s t c u l l e r f o rf u r t h e rr a s e a r c h k e yw o r d s b i o i n f o r m a t i c s ；g r a p ht h e o r y , r e p r e s e n t a t i v es e q u e n c e s ；r e m o v er e d u n d a n c y ； b l a s t h 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了 明确说明并表示谢意 作者签名：日期：型! ：! ! ：! 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定，学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质 版有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆被查阅有权将学位论文的内容编入有关数据库进行检索有权将学位 论文的标题和摘要汇编出版保密的学位论文在解密后适用本规定 学位论文作者签名：司鹃飞导师签名：、秀口卢j 历 日期：婴：! ! ：! 三 日期： 弘。了ii 1 t h 华东师范大学2 0 0 8 届硕十学位论文 蛋白质数据库去冗余程序的研究与开发 1 1引言 第1 章绪论 近年来，生物序列数据在爆炸式地增长，分析和处理这些数据是一个巨大的挑战。 许多生物序列数据库中都存在着冗余序列，这给许多研究问题带来了麻烦，比如分析和 处理基因序列或蛋白质序列时经常碰到的一个棘手问题就是数据库的冗余。 目前关于冗余问题还没有统一的定量的定义，事实上针对不同的生物学问题，也无 法找到一种这样的定量定义【i 】。一般而言，如果某些序列之间具有很高的相似度，那么 可以认定为它们是相同的序列或者是互为冗余的序列。冗余问题可能是由多种不同的原 因造成的，比如不同的研究机构可能向某个数据库中心提交了相同的序列数据，如果没 有被检查出来，则就导致数据库中存储了多个相同的序列，也就造成了冗余；另外，基 因或蛋白质序列数据库中的很多序列是属于同一个基因家族或蛋白质家族【2 ，3 】的，或者 是在不同的生物体上发现的同源基因或同源蛋白质，如果这些序列之间具有很高的相似 度，那么也认为这些序列之间互为冗余。 冗余序列通常不能提供更多的信息，而且不利于数据的统计分析。很多生物学的研 究问题需要基于非冗余的序列数据，如对蛋白质的序列和结构之间关系的统计分析需要 基于非冗余的蛋白质序列。在数据的统计分析方面，冗余数据可能会导致一些错误，比 如假定一个d n a 或蛋白质序列数据库中包含了大量非常相似的序列，那么这些序列会 分配到同一个“家族”中，造成这些“家族”的某些特性被夸大；而且在进行序列问相 关性分析时，以含有冗余序列的数据库为数据样本是不合适的；此外，如果基于含有冗 余序列的数据样本来进行蛋白质结构或功能的预测，会得到一种不恰当或不够准确的预 测结果。同时，大量的冗余序列通常需要占用更多的计算机资源来进行分析和处理，影 响了序列数据库的搜索速度和相关的分析处理工作。 因此，去除d n a 或蛋白质序列数据库中的冗余序列得到一个非冗余的序列集合是 非常具有现实意义的，本文所做的蛋白质数据库去冗余程序的研究与开发是具有很强的 实用价值的。 1 2相关研究工作 去冗余问题本质上是从一个序列数据库中搜索代表序列【4 5 ，6 ，7 ，8 9 ，1 0 】的问题。如对 华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 蛋白质序列数据库而言，从进化意义上代表序列指从某个蛋白质家族中找出一个序列来 代表整个家族；而从蛋白质的结构和功能意义上则是从一个结构和功能相近的蛋白质集 合中找出一个序列来代表该蛋白质集合。代表序列的确定规则可能会有所不同，这与要 解决的科学问题有关，其基本目标在于达到最大覆盖面并且最小化冗余度1 4 i 。 基于搜索代表序列的思想，目前已经有不少研究者开发出了实用的去冗余软件。去 冗余软件一般包括确定序列之自j 的相似度和选取非冗余序列两部分内容。 人们通常认为相似的生物序列具有相似的生物功能和结构，也具有相似的进化历 史。一般可以通过三种方式来确定序列之间的相似度，即序列片段过滤、序列比对以及 二者结合的方式。序列片段过滤可以通过计算序列片段的数目来断定序列之徊1 的相似度 在某个阈值之内，速度较快；序列比对是一种常用的序列之问相似性分析和比较的方法， 可以分为全局比对和局部比对两种方法，序列比对方法可以获得较为精确的相似度，但 通常占用较多的时间；出于对精确度和速度的折中，可以采用上述两种方法结合的方式 来确定序列之间的相似度，即首先设置一些过滤策略来减少序列之间比对的次数，再在 必要时采用序列比对来确定序列之间的相似度，著名的去冗余程序c d h i t 1 1 ，1 2 1 就是采 用了这种方式来实现。 h o b o h m 和s 锄d e r 【4 ，s l 最早对非冗余序列的选取算法进行了研究，其基本思路是先 将序列数据库划分为若干个不同的簇，然后从每个簇中找出一个序列来代表该簇，这样 所有的代表序列集合就是去除冗余序列后的非冗余序列集合。c d h i t 和p i s c e s 3 t 1 4 1 等软件都采用了这种方式。 目前存在的几个用来去除生物序列数据库中冗余序列的软件，如n i u d b 9 0 l l ”、 c d h i t 、p i c s e s 等，它们各具特色，通常都包括上述的两个部分即确定序列之间的相 似度部分和选取非冗余序列部分。以下是对这些软件的一个简要描述： n r d b 9 0 是一个非冗余序列数据库。序列之间的相似度采用序列过滤和序列比对相 结合的方式来确定。它首先采用了两个“过滤器”来减少序列比对( 【1 5 1 文中称为第三 个“过滤器”) 的次数，第一个“过滤器”排除缺少共同十肽( d e e a p e p t i d e ) 的序列， 第二个“过滤器”排除所有少于5 0 五肽( p e n t a p e p t i d e ) 的序列对 ”】。序列比对采用 了s m i t h 和w a t e r m a n 的算法【1 6 1 来进行。n r d b 9 0 适合处理相似度阈值在9 0 左右的情 况。 由美国b u r n h a mi n s t i t u t e 开发的c d h i t 软件可以用来解决大规模蛋白质序列数据 2 华东师范大学2 0 0 8 届硕十学位论文蛋白质数据库去冗余程序的研究与开发 库去冗余问题，该软件的处理速度比较快，能够在较短的时白j 内处理大规模的序列数据 库；但是c d h i t 并不是基于完全的序列比对，而主要是基于“短词组过滤”( s h o r t w o r d f i l t e r i n g ) 的方式来确定两个序列之间的相似度低于一个给定的阈值，这样c d h i t 在确 定序列相似度阶段节省了大量的运算时间。然而，这显然在精确性方面有不少缺陷，而 且“短词组过滤”的方式使得c d h i t 只适合处理相似度阈值大于4 0 的情况。 p i s c e s 是一个用来去除p r o t e i nd a t ab a n k 中冗余蛋白质序列的程序，它借助于 p s i b l a s t 17 】比对来确定序列之间的相似度，同时选取非冗余序列时它也引入了结构规则 来进行过滤。p i s c e s 处理大规模数据时需要花费比较长的时间。 n l u ) b 9 0 、c d - h i t 和p i s c e 都采用了h o b o h m 和s a n d e r 的算法来生成蛋白质数据 库中的代表序列，通过生成代表序列的方式来达到去除冗余序列的目的。这种算法提供 了一种很好的方式来生成一个非冗余的序列集合，然而它也去除掉了一些非冗余的序 列，导致所生成的非冗余序列集合不是足够大的。 1 3本文所做的工作 本文简要概述了生物信息学的有关背景知识，对蛋白质序列数据库去冗余问题进行 了探索，对现存的一些去冗余程序的进行了分析和研究，同时设计和改进了被广泛采用 的h o b o h m 和s a n d e r 的算法，为去冗余问题建立了基于图论的数学模型。 搜索代表序列的思路是一种站在生物学角度上对去冗余问题的直观建模。从数学意 义上来说，序列集合正好可以用一个无向图模型来描述。这样去冗余问题就完全转化成 了一个数学问题，各个序列以及序列之间的关系用数学意义上的无向图来表示，而非冗 余序列集合则直观上可以对应于图的独立集。图论的模型为去冗余问题奠定了坚实的理 论基础，这样我们可以采用图论研究的有关成果来实现生物信息学上的去冗余问题。 我们开发出了两个蛋白质去冗余程序f a s t c l u s t e r 和b l a s t c u l l e r ，它们对现有的程序 做出了一些改进，可以用来去除蛋白质序列数据库中的冗余序列。f a s t c l u s t e r 和 b l a s t c u l l e r 运行速度较快，生成的非冗余序列集合也较为合理，不仅具有很强的实用价 值，而且为去冗余问题提供了个实用的程序框架，其他研究者可以做进一步的研究， 在去冗余问题上获得新的突破。 在f a s t c l u s t e r 中我们引入了一种基于图论最大独立集【1 8 , 1 9 , 2 0 的分两步生成代表序 列的算法，该算法可以生成更多的代表序列，从而可以更好地避免去除掉非冗余序列。 华尔师范大学2 0 0 8 届硕士学位论文蛋向质数据库去冗余程序的研究与开发 f a s t c l u s t e r 可以用来去除蛋白质序列数据库中的冗余序列，并建立仅包含蛋白质代表序 列的数据库，同时进行一些扩展也可用于对基因序列的处理。f a s t c l u s t e r 的一些参数由 用户指定，如相似度阈值，带有冗余的序列数据库文件，它的处理结果是f a s t a 格式的 序列文件。 另外，我们从图论极大独立集f 嵋1 的概念出发，提出了一种新的去除冗余序列的算 法并开发出了实现该算法的程序b l a s t c u l l e r 。b l a s t c u l l e r 设计的目的是从一个序列集合 中产生一个极大的非冗余序列子集。b l a s t c u l l e r 采用一种递增迭代的方式来搜索图中的 一个极大独立集，运行速度较快；与c d h i t 相比，它提供了一种更灵活方便的运行方 式，可以处理0 到1 之间任何的相似度阈值；它也比p i s c e s 运行速度快，可以用来处 理大规模的序列数据；同时，我们可以方便地对b l a s t c u l l e r 做进一步改进即可处理其它 类型的生物序列如d n a 序列。 综上所述，我们深入研究了去冗余问题的相关内容，建立了相应的数学模型，设计 和实现了具有很高实用价值的程序f a s t c l u s t e r 和b l a s t c u l l e r ，对去冗余问题给出了我们 的解决方案。 1 4 本章小结 本章主要对去冗余闯题进行了简单的描述，探讨了去冗余闯题的研究意义，分析和 研究了现存的一些去冗余程序的优缺点，同时简要说明了我们的研究内容和取得的成 果。 4 华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 2 1生物信息学简介 第2 章背景知识 生物信息学是当今最重要、最前沿的科学发展领域之一，已被广泛应用于基因和蛋 白质序列数据的获取、分析和处理等许多方面，对分子生物学、生物医学和生命科学等 领域的研究和发展产生了深远的影响。 美国人类基因组计划实施五年后的总结报告中对生物信息学的定义是：生物信 息学是- - f - i 交叉科学，它包含了生物信息的获取、处理、存储、分发、分析和解释等在 内的所有方面，综合运用数学、计算机科学和生物学的各种工具，来阐明和理解大量数 据所包含的生物学意义。 在 2 1 世纪1 0 0 个交叉科学难题【2 l l 一书中对生物信息学进行了如下解释以 核酸、蛋白质等生物大分子数据为主要研究对象，以系统生物学为主要研究思路，以计 算生物学为主要研究方法，以数理科学、信息科学和计算机科学为主要研究手段，以计 算机网络为主要研究环境，以计算机软件为主要研究工具，构建各种类型的专用、专门、 专业数据库，研究开发面向生物学家的新一代计算机软件，对浩如烟海的原始数据进行 存储、管理、注释、加工，使之成为具有明确生物意义的生物信息，并通过对生物信息 的查询、搜索、比较、分析，从中获取基因编码、基因调控、核酸和蛋白质结构功能及 其相互关系等理性知识。在大量信息和知识的基础上，探索生命起源、生物进化以及细 胞、器官和个体的发生、发育、病变、衰亡等生命科学中重大问题，搞清它们的基本规 律和时空联系，建立。生物学周期表”。 生物序列数据在爆炸式地增长，这些海量的数据是用特殊的。遗传语言”d n a 的四个碱基字符( a 、c 、g 和t ) 和蛋白质的2 0 个氨基酸字符( a 、r 、n 、d 、c 、q 、 e 、g 、h 、i 、l 、k 、m 、f 、p 、s 、t 、w 、y 和v ) 写成的。2 0 0 1 年2 月，人类基因 组计划测序工作的完成将生物信息学推向了一个高潮，我们从早期的收集生物数据时代 迈入到分析解释生物数据的时代。在这一前提下，为了处理这些仍在不断增加的海量数 据，- - f 交叉学科生物信息学应运而生了。 生物信息学有多个相关的名词，如生物信息学( b i o i n f o m a t i c s ) 、计算生物学 ( c o m p u t a t i o n a lb i o l o g y ) 、计算分子生物学( c o m p u t a t i o n a lm o l e c u l a rb i o l o g y ) 、生物 分子信息学( b i m o l e c u l a ri n f o r m a t i c s ) 等，它是建立在分子生物学的基础上的。分子生 华东师范大学2 0 0 8 届硕士学位论文蛋白质数据库去冗余程序的研究与开发 物学( m o l e c u l a r b i o l o g y ) 是一门从分子水平研究作为生命活动主要物质基础的生物大 分子的结构与功能，从而阐明生命现象本质的科学，主要由三部分内容组成即核酸的分 子生物学、蛋白质的分子生物学和细胞信号转导的分子生物学。核酸的分子生物学研究 核酸的结构及其功能，分子遗传学( m o l e c u l a r g e n e t i c s ) 是其主要组成部分，遗传信 息传递的中心法则( c e n t r a l d o g m a ) 是其理论体系的核心；蛋白质的分子生物学研究执 行各种生命功能的主要大分子蛋白质的结构与功能；细胞信号转导的分子生物学研 究细胞内、细胞间信息传递的分子基础。 概括地说，生物信息学的核心内容是研究如何通过对d n a 序列和蛋白质序列的统 计、计算和分析，更加深入地理解d n a 序列、蛋白质序列、以及同源进化理论等，其 研究课题涉及到分子生物学、分子演化及结构生物学、统计学及计算机科学等许多领域。 生物信息学的主要内容包括序列比对、蛋白质结构比对和预测、基因识别与非编码区分 析研究、分子进化与比较基因组学、序列重叠群装配、遗传密码的起源和基于结构的药 物设计等。 在生物信息学札记( 第2 版) 2 2 1 一书中，浙江大学教授樊龙江将生物信息学的 发展历史分成了3 个主要阶段： 1 萌芽期( 6 0 至7 0 年代) ：以d a y h o 瞒换矩阵f 2 3 1 和n c e d l e m a n w u n s c h 算法1 2 4 1 为代表， 它们的出现，代表了生物信息学的诞生，形成了生物信息学的一个最基本的内容和 思路即序列比对； 2 形成期( 8 0 年代) ：以分子数据库和b l a s t 2 5 1 等相似性搜索程序为代表。1 9 8 2 年三大 分子数据库的国际合作使数据共享成为可能，同时为了有效地管理与日俱增的数据， 人们开发了以b l a s t 、f a s t a 2 6 1 等为代表的多个工具软件，而且研究和提出了大量新 的算法，这极大地改善了人类管理和利用分子数据的能力。在这一阶段，生物信息 学作为一门新兴学科已经形成，并确立了自身学科的特征和地位： 3 高速发展期( 9 0 年代至今) ：以基因组测序与分析为代表。基因组计划特别是人类 基因组计划的实施使得分子数据以亿计增加，基因组水平上的分析使生物信息学的 优势得以充分体现，基因组信息学成为生物信息学中发展最快的学科前沿。 生物信息学作为一门新兴交叉学科，在过去几十年的发展中有不少罩程碑式的事 件。表2 1 列出了生物信息学最近几十年的主要事件： 6 华东师范大学2 0 0 8 届硕士学位论文蛋向质数据库去冗余程序的研究与开发 表2 - 1 ；生物信息学发展史。1 年份事件 p a u l i n g 提出分子进化理论 d a y h o f f 构建蛋白质序列数据库 n e e d l e m a n w u n s c h 算法被提出 s t a d e n 利用计算机软件分析d n a 序列 s m i t h w a t e r m a n 算法被提出 序列模式( m o t i f ) 的概念被提出 g e n b a n k 数据库( r e l e a s e 3 ) 公开；e m b l 仓t | 立 一噬菌体基因组被测序 w i l b u r 和l i p m a n 提出序列数据库的搜索算法( w i l b e r l i p m a n 算法) 快速序列相似性搜索程度f a s t p f a s t n 发布 美国家生物技术信息中心( n c b i ) 创立 欧洲分子生物学网络e m b n e t g u 立；三大核酸数据库( g e n b a n k 、e m b l 和d d b j ) 开 始国际合作 序列相似性快速搜索程序b l a s t 发布 表达序列标签( e s t ) 概念被提出，从此开e o e s t 测序 英国s a n g e r 中心在英国休斯顿建立 欧洲生物信息学研究所在英国h i n x t o n 成立 第一个细菌基因组测序完成 酶母基因组测序完成 p s i b l a s t ( b l a s t 系列程序之一) 发布 p h ii g r e e n 等人研制的自动测序组装系统p h r e d - p h r a p - c o n s e d 系统正式发布 多细胞线虫基因组测序完成 果蝇基因组测序完成 人类基因组测序基本完成 人类基因组初步分析结果公布 2 7 o 7 l 1 2 2 3 5 8 8 昕 卯 g ： g 驰 g ； g ； g 鸲 孑： 舛 ； 盯 叭 坶 坞 均 坶 珀 均 均 挎 坶 均 加 加 华东师范大学2 0 0 8 届硕士学位论文蛋白质数据库去冗余程序的研究与开发 2 2分子生物学基础 2 2 1d n a 在不列颠百科全书中核酸的定义是：“核酸是一类天然的复杂磷化合物，是遗 传物质基础，能控制细胞的蛋白质合成”。核酸是一类物质的总称，它可分为核糖核酸 ( r n a ) 和脱氧核糖核酸( d n a ) 两大类。d n a 是细胞染色体中的遗传基因，其分子 的各个片段就代表各个遗传信息；而r n a 则是d n a 信息指令的携带者和执行者。 d n a 分子的基本组成单位是核苷，每一个核苷由一分子磷酸、一分子脱氧核糖以 及一分子碱基( 碱基共有四种，分别是a 腺嘌呤、g 鸟嘌呤、c 胞嘧啶和t 胸腺嘧啶) 组成。d n a 分子包括两条互相缠绕在一起的链，呈双螺旋结构，依靠嘧啶和嘌呤之间 的氢键连在一起。嘧啶和嘌呤的配对规则是a 和t 配对，c 和g 配对，称为一个碱基 对。碱基间的配对规则是d n a 精确复制的基础。 2 2 2 蛋白质 蛋白质( p r o t e i n ) 是一切生物借以表现生命的最重要基本单元，是一切生命活动的 体现者，是由氨基酸聚合而成的生物大分子，相对分子质量很大。估计人体中约有十万 种不同的蛋白质。按照用途蛋白质可以分为结构蛋白( 构成细胞和生物体的重要物质) 和功能蛋白( 如起催化作用的各种酶、起调节作用的某些激素、起免疫作用的人体内的 抗体等) ；按照外形和在生物体中的位置也可以分为纤维蛋白、膜蛋白和球蛋白等。蛋 白质具有很强的多样性，这是形形色色的生物及其各种复杂生命活动的物质基础。 蛋白质都是由2 0 种基本氨基酸组成的。蛋白质分子可以用氨基酸序列来表示，用 来代表蛋白质的一级结构( p r i m a r y s t r u c t u r e ) 。表2 2 给出了氨基酸的标准符号，包括 了三字母缩写和单字母两套符号，前者便于记忆，后者便于计算机处理，常用的一些软 件如b l a s t 等都支持这些符号。 为了要执行特定的生物功能，蛋白质必须拥有特定的三维空间结构。蛋白质三维空 间结构的形成是一个极其复杂的过程。氨基酸分子之间通过脱水缩合而形成一条或多条 肽链，肽链之间由一定的化学键连接并通过螺旋、卷曲、折叠等方式形成复杂的空间结 构。蛋白质的空间结构信息包含在其一级结构之中，也就是说一般蛋白质的空问结构完 全可以由其组成的氨基酸序列所决定。 华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 表2 - 2 ：氨基酸标准符号表 符号意义 符号意义 a ( a l a ) 丙氨酸 p ( p r o )脯氨酸 b 天冬氨酸或天冬酰胺q ( g i n )谷氨酰胺 c ( c y s ) 半胱氨酸r ( a r g ) 精氨酸 d ( a s p ) 天冬氨酸s ( s e r )丝氨酸 e ( g l u ) 谷氨酸t ( m )苏氨酸 f ( p h e ) 苯丙氨酸u硒代半胱氨酸 g ( g l y ) 甘氨酸 v ( v a l ) 缬氨酸 h ( h i s )组氨酸 w ( t r p ) 色氨酸 i ( d e ) 异亮氨酸 y ( t y r ) 酪氨酸 k ( l y s ) 赖氨酸 z 谷氨酸或谷氨酰胺 l ( l e u ) 亮氨酸x任意 m ( m e t )甲硫氨酸 翻译终止 n ( a s n )天冬酰胺 不定长度的空隙 目前，蛋白质的结构必须通过冗长的实验方法( 主要是用x 光绕射法与核磁共振法) 才能确定。序列、结构以及功能都相近的蛋白质被称为同源蛋白质，也就是说它们在生 命演化上有共同的起源。现有的大量数据显示大多数的蛋白质都有其同源体分布在许多 不同的生命体中。 2 - 2 3 基因和基因组 基因是d n a 分子上具有遗传效应的分子片段，是特定的核苷酸序列的总称。基因 位于染色体上，并在染色体上呈线性排列。基因不仅可以通过复制把遗传信息传递给下 一代，还可以使遗传信息得到表达。 1 9 2 0 年，基因组( g e n o m e ) 这一名词由德国汉堡大学植物学教授h a n sw i n k l e r 首 次使用。一个生物体的基因组是指包含在该生物的d n a ( 部分病毒是r n a ) 中的全部 遗传信息，它包括了基因和非编码序列。因此更确切地讲，一个生物体的基因组是指一 套染色体中的完整的d n a 序列。大部分生物体比病毒复杂，除了染色体，一般还包含 额外的遗传物质，在这种情况下基因组就包含了所有的基因和非编码d n a ；对于人类 来说，基因组通常指的是染色体d n a 。表2 3 列出了基因和基因组研究过程中的一些里 程碑式的事件： 9 华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 表2 - 3 ：基因和基因组研究大事记 年份事件 1 8 6 0 年至1 8 7 0 奥地利学者孟德尔根据豌豆杂交实验提出遗传因子概念，并总结出孟德 年尔遗传定律。 1 9 0 9 年丹麦植物学家和遗传学家约翰逊首次提出“基因”这一名词，用以表达孟 德尔的遗传因子概念。 1 9 4 4 年三位美国科学家分离出细菌的d n a ，并发现d n a 是携带生命遗传物质 的分子。 1 9 5 3 年美国人沃森和英国人克里克通过实验提出了d n a 分子的双螺旋模型。 1 9 6 9 年科学家成功分离出第一个基因。 1 9 9 0 年1 0 月被誉为生命科学“阿波罗登月计划”的国际人类基因组计划启动。 1 9 9 8 年1 2 月一种小线虫完整基因组序列的测定工作宣告完成，这是科学家第一次绘 出多细胞动物的基因组图谱。 1 9 9 9 年9 月中国获准加入人类基因组计划，负责测定人类基因组全部序列的 1 ；1 2 月1 日国际人类基因组计划联合研究小组宣布，完整破译出人 体第2 2 对染色体的遗传密码，这是人类首次成功地完成人体染色体完 整基因序列的测定。 2 0 0 0 年4 月6 日美国赛莱拉公司宣布破译出一名实验者的完整遗传密码，但遭 到不少科学家的质疑；4 月底中国科学家按照国际人类基因组计划的部 署，完成了1 人类基因组的工作框架图；5 月8 日德、日等国科学家宣 布，已基本完成了人体第2 l 对染色体的测序工作；6 月2 6 日科学家公 布人类基因组工作草图，标志着人类在解读自身。生命之书”的路上迈 出了重要一步；1 2 月1 4 日美、英等国科学家宣布绘出拟南芥基因组的 完整图谱，这是人类首次全部破译出一种植物的基因序列。 2 0 0 1 年2 月1 2 日中、美、日、德、法、英等6 国科学家和美国塞莱拉公司联 合公布人类基因组图谱及初步分析结果。 2 0 0 4 年1 0 月自然杂志公布的人类基因组图谱涵盖了9 9 的人类染色体的图谱， 经过美、英、日、德、法、中6 国科学家近3 年的精心“修纂”，原本 遗漏了1 5 万个细节的“人类生命天书”几近完美。新图同时显示，人 类基因实际数目只有2 万至2 5 万，比最仞估计的1 0 万个要少很多。 可以说，人类基因组计划的第一步基因测序工作已经完成。 2 2 4 序列数据库 目前，国内外建立了许多生物信息中心，存在着许多不同的生物序列数据库，如表 2 - 4 所示，列出了世界上主要的d n a 和蛋白质序列数据库的名称及相应网址： l o 华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 表2 4 ：世界主要d n a 和蛋白质序列数据库 数据库( d a t a b a s e ) 网址( a d d r e s s ) 由于历史原因各种数据库如g e n b a n k 、e m b l 和s w i s s p r o t 等都采用了不同的数据 库序列格式，但多数都由文字说明和序列两大部分组成。其中f a s t a 格式是序列分析软 件最常用的格式，该序列格式包括三部分内容： ( 1 ) 在注释行的第- - y i j 用字符“ ” 标识，后面是序列的名字和来源等解释说明性信息； ( 2 ) 标准的单字符标记的序列本 身； ( 3 ) 可选的“”表示序列的结束，它可能出现也可能不出现，但它是许多序列分 析程序正确读取序列所必需的。一个f a s t a 格式的文件片段如下所示： 2 3生物信息学主要内容 生物信息学的研究对象主要是d n a 和蛋白质序列；主要任务是分析研究序列数据中 的各种信息，特别是d n a 序列中的遗传及调控信息，研究蛋白质序列与结构及功能的关 l l 华东师范大学2 0 0 8 届硕士学位论文蛋白质数据库去冗余程序的研究与开发 系；研究内容主要包括序列比对、结构比对、蛋白质结构预测、计算机辅助基因识别、 非编码区分析和d n a 研究、分子进化和比较基因组学、序列装配、基于结构的药物设计 等。下面对几个主要研究内容啪1 进行简要的介绍： 2 3 1 序列比对 序列比对的目的是比较两个或两个以上序列的相似性或不相似性，它是生物信息学 的基础。目前有不少序列比对的算法，可以分为全局序列比对和局部序列比对，也可以 分为序列两两比对和多重序列比对，不同的算法有不同的使用场景。序列两两比对最常 用的算法是动态规划算法，程序b l a s t 和f a s t a 就是基于这一算法的。b l a s t 和f a s t a 在数据库查询和搜索中有重要的应用。多重序列比对一般使用c l u s t a l w 来实现。 2 3 2 结构比对 结构比对要解决的基本问题是比较两个或两个以上蛋白质分子空间结构的相似性 或不相似性。由于蛋白质分子空问结构的复杂性，结构比对算法还不是非常成熟，目前 已经有一些这方面的研究。 2 3 3 蛋白质结构预测 蛋白质结构预测主要包括蛋白质二级和三级结构预测，目前的研究成果还不能满足 实际需要。研究方法有演绎法和归纳法，前者从一些基本原理或假设出发来预测和研究 蛋白质的结构和折叠过程；后者从观察和总结己知结构的蛋白质结构规律出发来预测未 知蛋白质的结构。这是一项非常有实用价值和科研价值的研究内容。 2 3 4 计算机辅助基因识别 这项研究内容研究的基本问题是如何在基因组序列中正确识别基因的范围和在基 因组序列中的精确位置。 2 3 5 非编码区分析和d n a 语言研究 在人类基因组中，编码部分仅占总序列的3 到5 ，其余是非编码区d n a 序列。d n a 序列作为一种遗传语言，不仅体现在编码序列之中，而且隐含在非编码序列之中。分析 华东师范大学2 0 0 8 届硕士学位论文 蛋白质数据库去冗余程序的研究与开发 和研究非编码区的功能有许多工作可以做。 2 3 6 分子进化和比较基因组学 早期的研究工作主要是利用不同物种中同一种基因序列的异同来研究生物的进化， 构建出进化树，既可以用d n a 序列也可以用由其编码的氨基酸序列来做，甚至于可通 过相关蛋白质的结构比对来研究分子进化。近年来由于较多模式生物基因组测序任务的 完成，为从整个基因组的角度来研究分子进化提供了条件。比较两个或多个完整基因组 叭1 这一工作需要新的研究思路和方法，有不少工作值得仔细探讨和研究。 2 3 7 序列装配 一般来说，根据现行的测序技术，每次反应只能测出5 0 0 或更多一些碱基对的序列。 这就有一个把大量的较短的序列拼接成一个较大的、完整序列的问题。显然，为了正确 拼接，短