（计算机软件与理论专业论文）生物序列数据库中序列相似性查询技术的研究.pdf

东北大学硕士学位论文 摘要 生物序列数据库中序列相似性查询技术的研究 摘要 随着基因测序技术和人类基因组计划的发展，人们积累了越来越多的生物序 列信息。如何分析这些生物序列，从中找到人类和其它生物的遗传规律，并提取 有价值的知识，是目前人们面临的最大挑战。生物信息学的出现为解决这一难题 提供了有效的方法。 从生物角度讲，基因序列结构的相似性往往导致其功能上的相似性。【刭此， 我们可以通过搜索相似序列的方法预测新基因序列的功能。这就是我们研究序列 相似性查询技术的意义所在。 现有的序列相似性查询技术分为基于索引的方法和非索引方法两类。非索引 方法往往需要搜索整个数据库，因此其性能很不理想：而基于索引的方法不需要 搜索整个数据库，性能较好。然而，现有的基于索引的方法还存在很多问题。首 先，这些方法在建立索引过程中使用的变换方法丢失了大量信息，从而导致其距 离函数的过滤能力较弱，整个系统的性能不高；其次，它们不能处理任意长度的 查询：再次，其后处理阶段有大量的冗余计算，影响了系统的性能。 针对这些问题，本文提出了一种基于n 分频率变换( n - - p f t ) 的序列相似 性查询方法n p f t 方法。首先，我们提出了一种n 分频率变换技术，将字符 串变换为高维空间中的向量。这种变换比现有的频率变换和小波变换保留了更多 的字符串位置信息，从而使基于这种变换的距离函数有更好的过滤能力。我们还 分析了长度对距离的影响，进而解决了处理任意长度查询序列的问题。同时，我 们提出了一种新的后处理技术，在保证正确性的同时避免了大量的冗余计算，使 系统的性能得到了很大的提高。 我们不仅对我们的方法给出了严格的理论证明，而且进行了大量的实验。实 验结果表明，我们的方法在各种查询半径下都优于现有的方法，而且性能有几倍 至十几倍的提高。 关键词：序列相似性查询范围查询编辑距离生物信息学 东北大学硕士学位论丈 s t u d y o ns e q u e n c e s i m i l a r i t yq u e r yp r o c e s s i n gt e c h n i q u e s i n b i o s e q u e n c e d a t a b a s e s a b s t r a c t w i mt h e d e v e l o p m e n t o f g e n es e q u e n c i n gt e c h n i q u e sa n dh u m a n g e n o m e p r o j e c t m o r ea n dm o r eb i o s e q u e n c e sw e r ea c c u m u l a t e di nt h eb i o s e q u e n c ed a t a b a s e sa l lo v e r t h ew o r l d h o w e v e r , h o wt o a n a l y z et h e s eb i o s e q u e n c e sa n dh o w t o c a p t u r es o m e i n t e r e s t i n go ru s e f u li n f o r m a t i o nf r o mt h e m ，a r et h eb i g g e s tc h a l l e n g ew ea r ef a c i n g n o w t h e e m e r g e n c eo ft h e b i o i n f o r m a t i c s p r o v i d e s e f f i c i e n ts o l u t i o n s1 0t h e s e c o m p l e xp r o b l e m s f r o mt h ev i e wo f b i o l o g y , t h es i m i l a r i t yo fg e n es e q u e n c e sa l w a y sc o r r e s p o n d s t o t h es i m i l a r i t yo ft h e i rf u n c t i o n s t h e r e f o r e ，w ec a l lp r e d i c tt h ef u n c t i o no fn e wg e n e s e q u e n c eb ys e a r c h i n gi t ss i m i l a rs e q u e n c e s ，w h o s ef u n c t i o n sa r ea l r e a d yk n o w n t h i s i st h er e a s o nw h yw e p r o c e s st h es e q u e n c es i m i l a r i t yq u e r i e s ， e x i s t i n gm e t h o d sm a y f a l li n t ot w og r o u p s ：t h en o n i n d e xm e t h o d sa n dt h ei n d e x b a s e dm e t h o d s ，t h en o n i n d e xm e t h o d sh a v et os c a nt h ew h o l ed a t a b a s ef o re a c hq u e r y ， s ot h ep e r f o r m a n c e so ft h e s em e t h o d sa r en o tv e r yg o o d ；w h i l et h ei n d e xb a s e d m e t h o d sd on o th a v et os c o x lt h ew h o l ed a t a b a s e ，s ot h e yp e r f o r mb e t t e r h o w e v e r , t h e i n d e xb a s e dm e t h o d ss t i l lh a v em a n y p r o b l e m s f i r s t ，t h et r a n s f o r m a t i o n st h e yu s e d l o s el a r g ea m o u n to fi n f o r m a t i o n ，t h e r e f o r el e a dt ot h el o wp r u n i n ga b i l i t yo ft h e c o r r e s p o n d i n g d i s t a n c ef u n c t i o n sa n du n s a t i s f a c t o r y p e r f o r m a n c e s e c o n d ，t h e s e m e t h o d sc a n n o tp r o c e s st h eq u e r i e sw i t ha n yl e n g t h ，t h i r d ，t h e r ea r em a n y r e d u n d a n t c o m p u t a t i o n si nt h ep o s tp r o c e s s i n gp h a s e i no r d e rt os o l v et h e s ep r o b l e m sa n di m p r o v et h eq u e r yp e r f o r m a n c e ，w ep r o p o s e t h en p f tm p a r t i t i o n i n gf r e q u e n c yt r a n s f o r m a t i o n ) m e t h o d ，w h i c ht r a n s f o r m s a s t r i n gi n t oah i g hd i m e n s i o n a lv e c t o r t h en p f t r e s e r v e sm o r ei n f o r m a t i o nt h a nt h e f r e q u e n c yt r a n s f o r m a t i o na n dw a v e l e tt r a n s f o r m a t i o nu s e di np r e v i o u sm e t h o d s ，s oi t i m p r o v e s t h ep r u n i n ga b i l i t yo ft h ed i s t a n c ef u n c t i o n w ea l s oa n a l y z et h ee f f e c to f t h e l e n g t h so n t h ed i s t a n c e s ，a n dc o n s e q u e n t l ys o l v et h ep r o b l e m o f p r o c e s s i n gt h eq u e r i e s i i o 东北大学硕士学位论文 a b s t r a c t 一。_ - - _ _ _ _ - ，一 w i t h a n yl e n g t h m o r e o v e r , w ep r o p o s ean e wp o s tp r o c e s s i n g t e c h n i q u e ，w h i c h i m p r o v e s t h eq u e r y p e r f o r m a n c eg r e a t l y i nt h i st h e s i s ，w en o to n l yp r o v et h e o r e t i c a l l yt h ea d v a n t a g eo f o u rm e t h o d ，b u t a l s od o m a n ye x p e r i m e n t s t h er e s u l t ss h o wt h a tt h en ，p f tb a s e dm e t h o do u t p e r f o r m s t h ee x i s t i n gm e t h o d su n d e r a n y e r r o rr a t e a n dt h ep e r f o r m a n c eo fo u rm e t h o di sa b o u t 2 - 1 5t i m e sf a s t e rt h a nt h ee x i s t i n gm e t h o d s k e y w o r d s ：s e q u e n c es i m i l a r i t yq u e r y , r a n g eq u e r y , e d i td i s t a n c e ，b i o i n f o r m a t i c s 。i v 。 壹聪 本入声臻嚣曼交酪学位论文是在导耍蠹麓指导下完藏酶。论文 中取得的研究成果除加以标注和致谢的地方外，不包含其他人已 羟发表或撰写遭的礴究成采，也不包括本入为获褥其链学位雨镬 甭过豹材料。与我一磷互俸熟同志对本磷究所做的任何贡献均已 在论文串 馨了鲷确靛说甏荠表示谢意。 本入繇葛也 跫 期；汤争毒，毒争霉 f 东北大学硕士学位论文 第一章引言 第一章引言 人类基因组计划是人类二些纪最伟大的计划之一，因为它不仅测序了人类 染色体的全部基因序列而且推动了人类对基因的研究，为人类能够更完全，更清 晰地认识自我奠定了坚实的基础。而生物信息学的出现则为人类破译遗传密码、 揭示遗传规律提供了有效的方法。其中，序列相似性查询技术作为生物信息学的 主要研究课题在预测基因功能方面有着广泛应用。 1 1 生物序列 从分子生物学的角度来看，人体是由大约5 0 0 亿个各种细胞组成的【1 j 。每个 细胞的中心是细胞核。细胞的分裂和复制等许多重要功能都是由细胞核完成的。 具体地说，每个人类细胞的细胞核中都有2 3 对染色体。染色体是细胞遗传物质的 载体，是由d n a 和蛋白质组成的。 染色体上的遗传物质是脱氧核糖核酸，即d n a 。d n a 是由两条碱基互补的 脱氧核苷酸链反向平彳亍旋转形成的双螺旋结构，如图1 1 所示。每个脱氧核：莳酸 由一个碱基、一个脱氧核糖及一个磷酸分子组成。碱基的种类有四种：腺嘌呤( a ) 、 鸟嘌呤( g ) 、胸腺嘧啶( t ) 、胞嘧啶( c ) 。碱基的不同决定了脱氧核苷酸种类的 不同。因此，这四种碱基形成了四种不同的核苷酸，即腺嘌呤脱氧核苷酸、鸟嘌 呤脱氧核苷酸、胞嘧啶脱氧核苷酸和胸腺嘧啶脱氧核苷酸【2 】。人类的遗传信息正 是以核苷酸序列的形式贮存在d n a 分子中。 图1 1d n a 分子的双螺旋结构 f i g u r e1 1 t h es t r u c t u r eo fd n a 1 东北大学硕士学位论文 第一章引言 所谓基因就是d n a 分子上具有遗传效应的特定核苷酸序列的总称，是具有 遗传效应的d n a 分子片段f 3 】。1 9 世纪6 0 年代，奥地利学者盂德尔根据豌豆杂交 实验提出遗传因子概念，并总结出孟德尔遗传定律。1 9 0 5 年丹麦植物学家和遗传 学家约翰逊首次提出“基因”这名词，用以表达孟德尔提出的遗传因子概念。 每个基因具有自身的遗传密码。基因虽然只有小小的一段，却有着重要的功能。 它不仅可以通过复制把遗传信息传递给下一代，还可以使遗传信息得到表达。人 与人之间的差别都是由基因上的差异所导致的。 基因的主要任务就是编码各种蛋白质。蛋白质由2 0 种不同的氨基酸通过肽 键连接而成。各种氨基酸在线形链中的顺序，决定了这种分子的三维结构，也决 定了它的功能，如图1 2 所示。现在的问题是，由4 种碱基组成的d n a 链如何 编码由2 0 种氨基酸组成的蛋白质? 幽1 2 管臼质的三维结构 f i g u r e1 。2t h es t r u c t u r eo fp r o t e ir i $ 天文学家g g a m o w 在破解这一秘密的过程中做出了贡献。他于1 9 5 4 年首 次提出了三联体密码的假说：三个相连的碱基编码一个氨基酸。由四种碱基组合 成的三联体共有6 4 种，而氨基酸只有2 0 秘。所以，某些氨基酸可以对应几种不 同的编码。直到2 0 世纪6 0 年代，人们才发现，破解这种密码的工具是一种叫做 转移r n a ( t r n a ) 的分子。它的一端携带一种氨基酸，另一端则带有编码这种 氨基酸的三联体密码。在合成蛋白质之前，先要根据d n a 上的碱基序列按互补 规律合成信使r n a ( m r n a ) ，然后，核糖体以m r n a 为模板合成蛋白质。携带 不同氨基酸的t r n a 不断地把各种氨基酸带向核糖体。如果某种t r n a 上的三联 体与m r n a 上待读出的三联体可以互补，则这种t r n a 就可以与核糖体结合， 2 东北大学硕士学位论文 第一章引言 它所携带的氨基酸就被连接到正在合成的肽链上。文献【2 】对此有详细描述。 现在我们就搞清了遗传信息的传递方向，即由d n a 到d n a 的“复制”过程 和由d n a 到r n a 再到蛋白质的“转录”和“翻译”过程。前者使遗传信息由 父代传递给子代，后者使遗传信息转化为生物功能。简单地讲，基因序列的结构 决定蛋白质的结构，蛋白质结构决定代谢作用，代谢作用最终决定生物的各种性 状。因此，搞清人类和其它生物的基因序列是揭示其遗传规律的基础。 1 2 人类基因组计划 基因组就是细胞内遗传信息的携带者_ d n a 的总体。基因组中不同的区域 具有不同的功能，基因组结构是指不同功能区域在整个d n a 分子中的分布情况。 人类基因组包含着人类的全部遗传信息，所以搞清楚核苷酸排列顺序无疑将成为 人类破解遗传之谜的第一步。 人类只有一个基因组，大约包含5 一1 0 万个基因，由大约3 0 亿个碱基对组成， 分布在细胞核的2 3 对染色体中。为破译这本蕴藏着生命奥秘、决定人类生老病死 的“天书”，1 9 8 6 年，著名生物学家、诺贝尔奖获得者雷纳托杜尔贝科( r e n a t o d u l b e c c o ) 在科学杂志上率先提出“人类基因组计划”( h u m a n g e n o m e p r o j e c t ， 简称h g p ) ，旨在阐明人类基因组3 0 亿个碱基对的序列，发现所有人类基因并搞 清其在染色体上的位置，破译人类全部遗传信息，使人类第一次在分子水平上全 面地认识自我 4 1 。1 9 9 0 年1 0 月，美国政府决定出资3 0 亿美元正式启动“人类基 因组计划”，预期到2 0 0 5 年得到人体的全部基因序列。随后研究其相互作用和基 因功能，从而揭开人类全部遗传规律。 “人类基因组计划”启动以后，英国、法国、德国、中国和日本迅速跟进， 纷纷加入到此项意义重大的研究中。在各国科学家的努力下，整个工程进展顺利。 1 9 9 9 年1 1 月2 3 同，人类基因组计划d n a 测序工作完成第1 0 亿个碱基对的测定。 同年1 2 月1 臼，一个由英、美、日等国科学家组成的研究小组宣布，已经破译了 人类第2 2 号染色体中所有与蛋白质合成有关的基因序列，这是人类首次了解了一 条完整的人类染色体的结构，它可能使人们找到多种治疗疾病的新方法。研究最 示，第2 2 号染色体与多种致命疾病有关，因此完成对第2 2 号染色体的测定将对 这些疾病的早期诊断和治疗起到帮助作用。因此，这成果是人类基因组计划的 3 。 东北大学硕士学位论文第一章引言 一个里程碑。 我国于1 9 9 9 年7 月在国际人类基因组注册，得到完成人类3 号染色体短臂上 一个约含有3 0 0 0 万碱基的区域的测序任务。我国因此成为参与这一研究计划的唯 一发展中国家。我国负责的测序区域约占人类整个基因组的1 ，简称“l 项目” s l 。我国能够参与这一伟大计划，说明我国在这一领域掌握了一定的技术，而且 对基因的研究有了一定的成绩。2 0 0 0 年4 月，中国科学家按照国际人类基因组计 划的部署，完成了1 人类基因组的工作框架图。 2 0 0 3 年4 月1 4 日，美国联邦国家人类基因组研究项目负责人弗朗西斯柯 林斯博士在华盛顿隆重宣布，人类基因组序列图绘制成功，人类基因组计划的所 有目标全部实现。由美、英、日、法、德和中国科学家经过1 3 年努力共同绘制完 成了人类基因组序列图，在入类揭示生命奥秘、认识自我的漫漫长路上又迈出了 重要的一步。 “人类基因组计划”被誉为生命科学的“阿波罗登月计划”，是人类有史以来 最为伟大的世纪工程。这一计划的实现将对整个人类产生巨大影响。计划成功后， 科学家将对人类的基因序列进行分析，以确定基因的位置、结构和功能，这将为 人类征服多种疑难病症、争取更健康的生活铺平道路。 人类基因组计划虽然提前两年完满地结束了，这不仅是在学术界，也在社会 上也带来了对基因的研究热情。有人认为，测序的完成就意味着遗传密码的“破 译”，人类的一切疾病就都可以治愈，人类的寿命也可以延长到2 0 0 岁以上。实际 上，我们距离这些目标还非常遥远，我们只是为实现这些目标提供了可能。因为， 基因测序并不是我们的目的。我们在全球范围内投入几十亿资金，历时1 3 年，耗 费了巨大的人力、物力、财力，我们想得到的就仅仅是含有人类的全部基因序列 的一本“无字天书”吗? 当然不是! 人类基因组的测序工作只是把记录着生命之谜的天书逐字地读了 一遍，也像是把这本天书打开，摆在了世人的面前，却没有人能够看懂它，更没 有人能够利用它。为了理解它，给它做出全面的注释，科学家们需要找到里面包 含的所有基因和调控这些基因的序列。有人建议，通过国际互联网使全世界的科 学家们都来注释这都用d n a 的碱基写成的记录着全部生命奥秘的天书。此外， 更多的问题是关于这些基因的表达是如何受哪些因素调控的? 他们的表达产物一 - 4 东北大学硕士学位论文 第一章引言 一蛋白质是如何形成一定的结构并互相识别或装配进而发挥特定的生物功能的。 人类基因组测序的完成不是科学研究的终点，雨是新科学的起点。测序完成 之后，科学家们纷纷转向对基因功能的研究，生物学将进入一个崭新的时代 后基因组时代。2 0 0 3 年完成的人类基因组计划只是一个以测序为主的“结构基因 组学”的研究，而所谓的“后基因组计划”则是对基因功能的研究，即“功能基 因组学”。“后基因组计划”的研究内容，就是对基因组的功能进行探索，寻找功 能基因及其编码的蛋白质，测定蛋白质的结构，破译第二套遗传密码，实现多学 科交叉，应用其它学科的知识来解决生物学问题等等。 与此同时，世界各国都在争相开展对其它生物的基因组进行测序的工作。除 德国、美国之外，中国将重点进行家猪的测序，能源部基因组研究所计划在三月 开展对海鞘的测序，在此之前他们已完成了日本气泡鱼基因草图。其他一些机构 则正在测定淡水气泡鱼的基因。德国马普学会下属的分子遗传研究所与日本基因 组研究中心合作，测定了黑猩猩的基因组片段。 要彻底地破译人类基因组中所包含的全部信息仍然需要进行数十年的研究和 分析。到时候，人类的许多疾病都可以在分子水平上寻找致病原因以及治疗方法。 这将给医药行业带来很大的挑战，新药的开发原则将针对疾病的潜在致病原因。 医生在开药方之前进行的遗传测试可以使药物更有效地治疗病人的疾病，而不会 产生副作用。 无论如何，“人类基因组计划”的顺利完成把我们带入了基因的世纪，我 f l e e 在向着理解生命之谜的目标前进。 1 3 生物信息学 随着基因测序技术的快速发展、人类基因组计划的顺利完成以及各种生物基 因组计划的开展，越来越多的基因和蛋白质序列展现在人类面前。面对如此海量 的信息，人类应该如何处理它们，如何从中找到生命的内在的规律，解读人类甚 至其它物种的生命奥秘以及如何将这些规律、知识真正应用到实践中，真正造福 于人类，这些都是人类必须解决的问题。否则人类基因组计划将毫无意义。为了 加快对这些数据的处理和知识发现的过程，人们越来越多的依靠计算机和计算机 领域的算法来解决某些问题，并指导生物领域实验室的生物实验。生物信息学就 东北大学硕士学位论文 第一章引言 是在这样的情况下应运而生的。 1 3 1 生物信息学与人类基因组计划 近十年柬，在人类基因组计划的带动下，在相关学科和技术( 例如基因测序 技术) 蓬勃发展的前提下，基因研究成为全世界生命科学研究中的研究热点。因 此，生物序列信息包括基因序列和蛋白质序列等出现了爆炸性增长。从 1 9 9 5 年至2 0 0 1 年，酵母等数十种生物的基因组被测序出来。2 0 0 1 年的春天，科 学家又公布了人类基因组的绝大部分序列，即：人类基因组的工作草图。根据国 际数据库的统计，1 9 9 9 年1 2 月d n a 碱基对数目为3 0 亿，2 0 0 0 年4 月d n a 碱 基对数目是6 0 亿，2 0 0 1 年这一数目已达1 4 0 亿，平均大约每1 4 至1 5 个月翻一 番【6 1 。 图1 3 所示为1 9 8 2 年至2 0 0 2 年期间，美国n c b i ( n a t i o n a lc e n t e rf o r b i o t e e h n o l o g yi n f o r m a t i o n ) 的数据库g e n b a n k 中碱基对的数量的增长情况。 由图中可以看出，数据库中的生物序列数据正以几何极数递增；而且，近年来， 这种递增的趋势越来越明显。 图1 3g e n b a n k 中碱基对数量的增长情况 f i g u r e1 3t h eg r o w t ho fb a s ep a f si ng e n b a n ki nr e c e n ty e a r s 与此同时，g e n b a n k 中生物序列数量的增长也显示出同样的趋势。图1 4 给 出了g e n b a n k 中生物序列数量的增长趋势。 6 东北大学硕士学位论文第一章引言 图1 4g e n b a n k 中生物序列数量的增长情况 f i g u r e1 4t h eg r o w t ho fb i o s e q u e n c e sir lg e n b a n ki nr e c e n ty e a r s 2 0 0 3 年4 月，人类基因组计划提前两年完成，各种其它物种的基因组测序工 作纷纷开始。导致全球范围内的生物序列的数量再度剧增。同时，也预示着结构 基因学的研究日趋完善，而功能基因学尚待发展。这意味着基因组的研究将全面 进入信息提取和数据分析的崭新阶段，研究重点逐渐由数据的积累转向数据的处 理。 如前所述，生物的遗传物质是一类称为脱氧核糖核酸( d n a ) 的生物大分子， 它是由4 种核苷酸连接起来组成的，通常用字符a 、c 、g 、t 代表。通俗地说， 生物的遗传密码就是这4 个字符连接起来的长链。这种链的长度往往非常巨大， 例如：人的遗传密码就含有3 2 亿个字符，将这些字符堆集起来就构成了一部1 0 0 多万页、每页有3 0 0 0 个字符的“天书”。如何读懂它是个极大的难题。 首先，如何存储如此庞大、如此海量的数据就是一大挑战。据统计，迄今为 止发现的最长的基因序列的长度为6 g b p s ( b a s ep a i r s ，即碱基对) ，相当于含有 6 0 亿个字符的超长字符串。如果仅仅是将这么大的基因序列存储起来，问题就简 单多了。只要我们有足够大的存储介质就可以了。但是存储这种生物序列的目的 是为了对它进行模式匹配、知识发现等分析，从中提取知识。因此，其存储方式 直接关系到其模式匹配等算法的性能。所以，我们不仅要存储，而且要进行索引， 以便于对其进行分析。那么哪种索引结构更适合呢? 这要根据待解决的问题的性 质来决定。 其次，更为本质的原因是：基因组数据的复杂性。这本“天书”包含了人体 1 东北大学硕士学位论文 第一章引言 的结构和功能以及生命活动过程的大量信息，却仅仅由4 个字符组成。其中既无 词法，又无句法，还没有标点符号，看起来每一页都是相似的。基因组研究最终 是要把生物学问题转化成对数字符号的处理问题。 人类要解决这一难题，必须借助计算机的帮助。这是因为： 第，我们从生物实验室中得到的生物序列数据规模巨大，如果直接进行生 物实验来研究这些生物序列，成本势必非常巨大，工作量也是无法承受的。而且， 直接进行实验是没有理论根据的，或者理论根据较弱，属于实验摸索的性质。如 果我们能够建立其数学模型，并利用计算机的分析方法对这些序列进行分析，提 出可能的规律或知识，来指导生物实验室中的实验，不是更好吗? 这时的生物实 验是检验性质的，是有针对性的实验。其实验成本低，而且发现知识的可能性却 较高。 第二，要解决这样的问题就需要对海量生物信息进行处理，就必须发展新的 分析理论、方法、技术、工具，就必须依赖计算机的信息处理能力。因为，传统 的模式匹配等算法已经不再适用于生物信息领域。这是因为，这些算法都是基于 主存的算法。如果其对象是生物信息领域中的超长字符串，这些算法可能都要受 到主存大小的限制。而且算法所消耗的时间往往也比较多。这就要求我们针对生 物信息领域的数据特点，开发新的理论和算法。 如今，生物信息技术已被广泛应用于人类基因组计划中的许多方面，如基因 序列数据的获取、处理、分析和管理等，对于分子生物学和生物医学研究的深入 发展发挥了巨大作用。它包括：数据处理、数据分析、数据库的管理等方面。 总之，人类基因组计划使人类迈入了一个崭新的时代。人类基因组计划是人 类探索生命奥秘的第一步，因为它测序了蕴含人类全部遗传信息的全部基因序列。 它为揭示人类自身的进化和遗传规律，掌握基因调控方法，造福于人类提供了最 基本的研究对象和研究素材。而生物信息学正是人类基因组计划的后继学科。是 在人类面临海量生物序列数据，。而茫然不知所措时，应运而生的新兴学科。它的 研究对象就是人类基因组计划产生的生物序列；其主要研究目的是：通过研究新 的理论、算法，从计算机的角度找到蕴含于这些序列中的真正有意义的知识和规 律，指导生物学家作真正的生物实验来验证这些知识和规律。这样做不仅大大加 快了生物序列的分析进程，而且避免了大量的盲目、无根据的生物实验，节约了 8 。 东北大学硕士学位论文第一章引言 成本。 1 3 2 生物信息学的概念 那么究竟什么是生物信息学呢? 生物信息学( b i o i n f o r m a t i c s ) 的概念足1 9 5 6 年，在美国田纳西州盖特林堡召开的首次“生物学中的信息理论研讨会”上首次 提出的。但是，就生物信息学的发展而占，它还是一门相当年轻的学科。直到2 0 世纪8 0 至9 0 年代，伴随着计算机科学技术的进步，生物信息学才获得突破性进 展。 生物信息学是在生命科学的研究中，以计算机为工具对生物信息进行存储、 检索和分析的科学，是当今生命科学和信息科学的重大前沿领域之一【7 ，8 1 。作为一 门新兴的交叉学科，很多人认为生物信息学的研究范畴既涉及生物又涉及计算机、 人工智能等学科，因此它一定是一个内容十分广泛而且研究范围不清晰的学术领 域。事实恰恰相反，它的内涵十分具体，范围非常明确，其研究内容就是随着基 因组研究而发展的，因为生物信息学就是伴随基因组研究而产生的。 广义地说，生物信息学从事与基因组研究相关的生物信息的获取、加工、储 存、分配、分析和解释。这一定义包括了两层含义，一是对海量数据的收集、整 理与服务，也就是管理、组织这些数据；另一个是从中发现新的规律，也就是用 好这些数据，将数据转化为知识1 3 。 具体地说，生物信息学以分析生物序列为手段，找到基因组序列中代表蛋白 质和r n a 基因的编码区；同时，阐明基因组中大量存在的非编码区的信息实质， 破译隐藏在d n a 序列中的遗传规律；在此基础上，分析基因表达与调控的数据， 从而认识代谢、发育、分化、进化的规律，并最终将其应用到生物制药等领域， 真正造福人类。 生物信息学的含义随着研究的深入和现实需求的改变不断变化。直到1 9 9 5 年，在美国人类基因组计划第一个五年总结报告中，给出了一个较为完整的生物 信息学定义，那就是：“生物信息学是一门交叉科学，它包含了生物信息的获取、 加工、存储、分配、分析、解释等在内的所有方面，它综合运用数学、计算机科 学和生物学的各种工具，来阐明和理解大量数据所包含的生物学意义”。 生物信息学不仅是一门新学科，更是一种重要的研究开发工具。只有通过生 0 东北大学硕士学位论文 第一章引言 物信息学的计算处理，人们才能从众多分散的生物学观测数据中获得对生命运行 机制的系统理解。生物信息学几乎是今后所有生物( 医药) 研究开发所必需的工 具。只有根据生物信息学对大量数据资料进行分析后，人们才能选择该领域正确 的研发方向。生物信息学不仅具有重大的科学意义，而且具有巨大的经济效益。 它的许多研究成果可以较快地产业化，成为价值很高的产品。 生物信息学是一个交叉学科，因为：首先，它需要一定的计算能力，包括相 应的硬件设备和软件工具，需要各种数据库或者能与国际、国内的数据库系统进 行有效的交流，需要有高速、稳定的互联网系统；其次，生物信息学需要强有力 的颓算法和新工具；最后，它要与实验科学建立广泛、紧密的联系。因为实验技 术既是产生生物信息数据的主要方法，又是验证生物信息学研究结果的关键手段。 因此，从事生物信息学研究的人员也必须具备多学科交叉的知识。 生物信息学正在作为生物和计算机科学的前沿战略性学科而崛起，涉及到医 学，生物技术和社会学的许多方面。 1 33 生物信息学的研究内容 生物信息学的研究内容也许会随着结构基因学和功能基因学的发展而变化， 但是当前生物信息学的主要研究内容有如下几个方面： i 获取人和各种生物的完整基因组。入的遗传密码有3 2 亿个碱基，雨现在 的d n a 测序仪每个反应只能读取几百到上千个碱基。因此，要得到人的全部遗 传密码首先要把人的基因组打碎，测完一个个小段的序列后再把它们重新拼接起 来。生物信息学要利用计算机的算法实现序列拼接和填补序列间隙的首要难题。 2 发现新基因和新的单核苷酸多态性。发现新基因是当前国际上基因组研究 的热点，使用生物信息学的方法是发现新基因的重要手段。它包括：基因的电脑 克隆、从基因组d n a 序列中预测新基因以及发现单核苷酸多态。 3 基因组中非编码区的研究。非编码序列必定具有重要的生物功能。普遍的 认识是，它们与基因的表达调控有关。因此寻找这些区域的编码特征、信息调节 与表达规律是未来相当长时间内的热点课题，是取得重要成果的源泉a 4 在基因组水平研究生物进化。近几年来，随着基因组序列数据的大量增加， 对序列差异和进化关系的争论也越来越激烈。首先发现同一种群基于不同分子序 1 0 东北大学硕士学位论文第一章引言 列所重构出的进化树可能不同。同时，对“垂直进化”和“水平演化”之间关系 的讨论i f 逐渐引起人们的重视。 5 对完整基因组的比较。在后基因维时代，完整基因组数据越米越多，有了 这些资料人们就能对若干重大生物学问题进行分析研究，如：生命是从哪里起源 的? 生命是如何进化的? 遗传密码是如何起源的? 等等。这些重大的问题只有在 基因组水平上才能回答。这一工作开创了比较基因组学。我国很重视完整基凶组 的测序和分析工作，现已完成了具有4 3 亿碱基对的水稻基因组的“工作草图”。 这些数据将为我国在这一领域的研究提供最直接的素材。 6 从功能基因组到系统生物学的研究。同一组织在不同的个体生长发育阶段， 表达基因的种类、数量也是不同的，有些基因是在幼年时期表达的，有些是中年 阶段表达的，有些要到老年时期才表达。我们不仅需要了解基因的序列，还要了 解基因的功能，也就是要了解在不同的时间、不同的组织中基因的表达谱。这就 是通常所说的功能基因组研究。为了得到基因的表达谱，有两个新技术：基因芯 片和蛋白质组技术。下一步，功能基因组研究将进入系统生物学的领域。 7 蛋白质结构模拟与药物设计。蛋白的空间结构模拟和药物设计已有- - z 十 年的历史。预测这些蛋白的空间结构，进而实现针对性的药物设计，已经成了追 在眉睫的任务。 8 生物信息学的应用与发展研究：生物信息学的研究结果不仅具有重要的理 论价值，也可直接应用到工农业生产和医疗实践当中去。它包括：疾病相关的基 因信息及相关算法和软件开发、与动、植物良种繁育相关的基因组数据库和研究 与发展药物设计软件和基于生物信息的分子生物学技术。 1 3 。4 生物信息学的研究现状 西方发达国家一直非常重视生物信息学的发展，尤其近年来各种生物研究机 构、生物科技公司和生物制药公司如雨后春笋般涌现出来。目前，绝大部分核酸 和蛋白质数据库由美国、欧洲和日本的3 个数据库系统产生。它们共同组成国际 核酸序列数据库，每天交换数据，同步更新。 美国些最著名的大学，如哈佛大学、普林斯顿大学、斯坦福大学、加州大 学伯克利分校等，都投巨资成立生物学、物理学、数学等学科交叉的研究中心。 1 】 东北大学硕士学位论文第一章引言 1 9 9 9 年6 月，美国n i h 的一个顾问小组建议在生物计算领域设立总额为数亿美 元的重火科研基金，并成立5 到2 0 个计算中心以处理海量的基因组相关信息。 我国对生物信息学领域也越来越重视。很多著名大学和研究所在很多方面取 得了一定的成绩。例如，北京大学的生物信息学网站的建设，中科院生物物理所 在e s t 序列拼接及在基因组演化方面的研究，天津大学在d n a 序列的几何学分 析方面的进展等等。北京大学和中科院生命科学研究院分别在北京和上海成立了 生物信息学中心，分别维护着国内两个专业水平相对较高的生物信息学网站。 虽然与国际上的研究相比，我国目前还有很大差距，但是国内生物、医药科 学研究与开发，对生物信息学研究和服务的需求市场非常广阔。不幸的是，真正 开展生物信息学具体研究和服务的机构或公司却很少，仅有的几家科研机构主要 开展生物信息学理论研究，生物信息学服务公司提供的服务仅局限于简单的计算 机辅助分子生物学实验设计，而且服务体系也不完善。 生物信息学的核心是生物学，而计算机技术只是它的研究工具。生物信息学 的目的就是通过分析大量的生物序列预测生物学的重大突破。这种预测是十分困 难的。然而，科学的发展表明，重大科学规律的发现往往来自于海量的科学数据。 因此，而当今生物信息学海量生物序列数据的积累，也必将导致重大生物学规律 的发现。 总之，生物信息学的发展，不仅将导致生物、物理、数学、计算机等多种学 科知识的融合，而且将培养一批具有交叉学科知识的科学工作者，同时会创造巨 大的经济效益。生物信息学在国内外的发展基本上都处于起步阶段，各国的研究 环境也大体相同。我国基因信息资源丰富，因此，这是我国生物信息学研究赶超 国际先进水平的好时机。我们相信，生物信息学必将蓬勃发展。 1 - 4 问题的提出与研究意义 在人类基因组计划的带动下，基因测序技术有了很大突破，结构基因学的研 究也日趋完善。利用现有的测序技术和设备，人类每天可以测序几千万甚至数十 亿个碱基对的基因序列。尤其是各种生物基因组计划的开展，使人类进入了一个 生物信息大爆炸的时代。数百亿字节的信息摆在人们面前，急需人类进行处理， 从中挖掘与人类生长、发育、遗传等活动相关的知识。 1 2 东北大学硕士学位论文第一章引言 1 4 1 生物序列数据库 为了更好地保存和处理如此海量的生物序列数据，我们毫无疑问的将这些数 据存储到大型计算机的数据库中。目前，国际上的公共数据库有近百种，其中最 著名的核酸和蛋白质序列数据库有几十种，我们将在后面介绍其中几种。除了世 界公用数据库外，还有许多研究机构的内部数据库。据统计，这些数据库巾的数 据量正在以指数速率增长，平均每年翻一番。 更重要的是有了这些数据库，人类将更方便地共享这些生物序列，更方便对 这些数据进行分析处理。因为，到2 0 世纪9 0 年代，i n t e r n e t 技术已经相当成熟， 人们可以方便的通过网络共享资源。因此，这些大型的数据库每天都进行更新， 并通过网络进行数据同步。这样全世界的生物信息学研究人员获取实验数据就变 得很方便了。另外，这些大型数据库服务器大多提供序列分析和基因检索等序列 分析服务。研究人员可以通过这些数据库提供的先进的技术和工具对生物序列进 行分析。 根据数据库中数据内容的不同，现有的生物序列数据库有如下几类： 基因序列数据库，包括最著名的g e n b a n k 9 1 、e m b l 10 1 、d d b j t l l l 等。这些数 据库每天更新，相互交换数据。目前，它们可以提供5 万多个物种的数百亿碱基 对的基因序列。此外，它们还提供序列分析服务，支持在线和离线的序列分析。 蛋白质数据库，其中最著名的是国际蛋白质数据库p s d 1 2 l 和瑞士的数据库 s w i s s p r o t t n l 。它们仅仅提供蛋白质序列数据和一些蛋白质序列搜索服务，如 基于文本的交互式检索，标准序列相似性搜索，结合序列相似性、注释信息和蛋 白质家族信息的高级搜索等。 功能数据库，如k e g g l l 4 1 ，它是系统分析基因功能，联系基因组信息和功能 信息的知识库。它存储了基因组序列和更高级的功能信息，包括图解的细胞生化 过程以及关于化学物质、酶分子、酶反应等信息。k e g g 还提供了j a v a 的图形工 具来访问基因组图谱，比较基因组图谱和表达图谱，以及其他序列、图形比较等。 其它生物数据库，包括r n a 数据库、线粒体数据库、基因表达数据库、密 码子数据库、蛋白质三维结构数据库和霉代谢数据库等等。 这些数据库提供了在全球进行生物序列数据共享和研究的平台，为生物信息 1 3 东北大学硕士学位论文第一章引言 学的快速发展奠定了基础。有了这样一个平台，我们下一步的工作就是开发基于 这种数据库平台的高效序列分析工具软件，如序列拼接软件、基因发现软件、基 因结构分析软件和基因功能预测软件等都是生物学家不可或缺的计算和分析工 具。有了这些强有力的工具，全世界的科学家就可以方便的进行序列分析，研究 基因结构与基因功能之间的关系，并指导生物实验室中的实验。 1 4 2 序列相似性查询 基因功能预测是指通过某些方法或途径对所发现的基因的功能进行预测，为 进一步的生物学实验验证提供启发和指导。目前，序列查询技术是基因功能预测 的主要方法，也是本文要解决的主要问题。 对于许多新得到的序列，我们并不知道其相应的生物功能。生物学研究人员希 望能够通过搜索生物序列数据库，找到与新序列同源的已知序列，并根据同源性 推测新序列的生物功能。搜索同源序列在一定程度上就是通过相似比较寻找相似 序列实现的。在分子生物学中，d n a 或蛋白质的相似性是多方面的，可能是核酸 或氨基酸序列的相似，可能是结构的相似，也可能是功能的相似。我们解决的问 题是基因序列的相似性，即核苷酸排列的相似性。因为生物学中有这样一个规律， 即序列决定结构，结构决定功能。所以当研究序列的相似性时，我们最终希望根 据这个普遍规律推测新基因序列的功能，也就是发现新的生物分子数据的内涵。 更具体地讲，我们通过将功能待定的新基因的序列与数据库中已有的d n a 或蛋白质序列进行相似性比较，得到与新基因具有较高同源性的一系列基因序列 或基因序列的片段，然后将这些基因或片段的已知的功能作为分析和预测新基因 功能的重要线索，推测这个序列的性质、结构、功能、同源性、变异性等特性， 从而推断其作用机制以及与疾病的关系等等。实际上，我们在实验室e e i g i n _ 实验 得到条新的核酸序列后，通常所做的第一项工作就是将其与所有已知序列对比， 看看能否发现什么有意义的相似性。 另一方面，据统