（计算机应用技术专业论文）基于信息自动获取构建生物信息平台及序列比对算法研究.pdf

摘要 摘要 二十一世纪是生命科学的世纪，近年来生物信息学得到了前所未有的发展。 生物信息二级数据库是生物信息学中的一个重要研究方向，由于生物信息数据的 复杂性及其分析应用的复杂性，至今没有一种比较通用的构建模型能够满足一般 性生物信息二级数据库系统的开发需要。序列比对是生物信息学中一个非常重要 的操作，是基本的处理信息的方法。将大量累积的核酸和蛋白质序列进行比对， 对发现生物序列的功能、结构和进化信息具有重要的意义。 本文对生物信息学的发展、研究内容、生物数据库做了简单的介绍，对序列 比对的各种算法：点阵法、动态规划全局比对算法、s m i t h w a t e r m a n 算法、f a s t a 算法、启发式b l a s t 算法等做了简单描述，并分析了序列比对研究的目的及其意 义。 本文利用n e t 、x m l 和w e bs e r v i c e s 相关技术，实现了一种建立生物信息学 研究平台的框架体系。该平台可自动从i n t e m e t 获取生物信息数据并建立本地二级 生物信息数据库。重点介绍了用w e b c l i e n t 类的方法提取分析网络数据库资源并创 建本地二级生物信息数据库；用a s p n e t 和a d o n e t 实现了对此二级数据库的 查看、查询等操作；使用x m l 保存从w e b 站点上下载的数据；用w e bs e r v i c e s 技术封装序列对比算法，可从客户端直接调用。此系统在n e t 技术上采用w e b 信 息自动获取并结合w e bs e r v i c e s 技术有助于二级数据库开发人员在海量的信息源 中迅速找到真正需要的生物数据信息，并灵活地加以应用，从而将更多的精力集 中在更纯粹的生物信息处理上来，并可以通过w e b 的方式向i n t e m e t 用户提供方便、 有效的公共生物信息技术服务平台的各类资源。 本文还在b l a s t 部分算法的基础上，基于十六进制编码序列和寻找最优可变 窗口大小的思想，提出了一种相似核苷酸序列搜索算法s l a h a w 。本算法采用十 六进制编码存储序列，通过序列片断相似度得到最佳搜索窗口值，从而提高搜索 速度和准确度并且节约了存诸空间。建立出实验环境和实现了相应算法，通过实 验证明在序列满足相似度的情况下，s l a h a w 是一种快速而有效的相似序列片断 匹配算法。 关键词：生物信息；序列比对；搜索算法；二级数据库 a b s t r a c t 2 1 s t c e n t u r y i st h e c e n t u r y o fl i f es c i e n c e s b i o i n f o r m a t i c sh a s g o t t e n u n p r e c e d e n t e dd e v e l o p m e n ti nr e c e n ty e a r s b i o i n f o r m a t i o ns e c o n d a r yd a t a b a s ei so n e o ft h ei m p o r t a n tr e s e a r c hd i r e c t i o n si nb i o i n f o r m a f i c s d u et ot h ec o m p l e x i t yo fb o t h b i o i n f o r m a t i o nd a t aa n dt h e i ra p p l i c a t i o n s ，t h e r ei sn or e l a t i v e l yc o m m o nf r a m e w o r k m o d e ls of a rt om e e tt h ed e v e l o p m e n tn e e do fg e n e r a lb i o i n f o r m a t i o ns e c o n d a r y d a t a b a s es y s t e m s s e q u e n c ea l i 鲫m e n ti st h em o s ti m p o r t a n tm a n i p u l a t i o na n dt h e f u n d a m e n t a li n f o r m a t i o np r o c e s s i n gm e t h o di nb i o i n f o r m a t i c s a l i g n i n gan u m b e ro f c u m u l a t e dn u c l e i ca c i da n dp r o t e i ns e q u e n c e si ss i g n i f i c a n tf 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 nb i o l o g i c a ls e q u e n c e s i n1 h i st h e s i s ，i ti n t r o d u c e st h e d e v e l o p m e n t , r e s e a r c ha n dd a t a b a s e o f b i o i n f o r m a t i c sf a s t , a n dt h e ns o m eo fa l i g n m e n tm e t h o d sa r ed e s c r i b e d ，s u c ha sd o t m a t r i xs e q u e n c ec o m p a r i s o n , d y n a m i cw o f a m m i n ga l g o r i t h mf o rs e q u e n c eg i o b a l a 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 ，f a s t aa l g o r i t h m ，b l a s ta l g o r i t h ma n ds oo n a n a l y z et h ep u r p o s ea n di t sm e a n i n go ft h er e s e a r c ho fs e q u e n c ea l i g n m e n ta l s o t h i st h e s i sa c h i e v e daf r a m e w o r ks y s t e ma b o u tc r e a t i n gb i o i n f o r m a t i c sr e s e a r c h p l a t f o r mb yt h er e l a t e dt e c h n i q u eo ft h e n e t , x m la n dt h ew 曲s e r v i c e s t h i s p l a t f o r mi sa u t o m a t i ct oo b t a i nb i o i n f o r m a t i o nf r o mi n t e r a c ta n db u i l du pal o c a l s e c o n d a r yd a t a b a s eo fb i o i n f o r m a t i o n n ep o i n ti n t r o d u c e st oe x t r a c t i o na n da n a l y s i s n e t w o r kd a t a b a s er e s o u r c e sw i t ht h ew e b c l i e n tc l a s sm e t h o da n de s t a b l i s h e sal o c a l s e c o n d a r yd a t a b a s eo fb i o i n f o r m a t i o n c a r r yo u ts o m eo p e r a t i o no fv i e wa n ds e a r c he t c o ft h i sl o c a ls e c o n d a r yd a t a b a s ew i t ht h ea s p n e ta n da d o n e t i te n v e l o p s a l g o r i t h mo fs e q u e n c ea l i g n m e n t 妙骶6s e r v i c e st e c h n o l o g yc a ni t 锄b ec a l l e db y c l i e n t t h i ss y s t e ma d o p tw 曲i n f o r m a t i o no b t a i n sa u t o m a t i c a l l yo nt h e n e tt e c h n i q u e u s ex m ld o c u m e n ts t o r ed a t ad o w n l o a d e df r o mw e b s i t e ，a n dc o m b i n et h et e c h n i q u eo f w e bs e r v i c e st oc o n t r i b u t et ot h el o c a ls e c o n d a r yd a t a b a s ed e v e l o p e rt of i n do u tt h e b i o i n f o r m a t i o no fr e a ld e m a n dq m c m yi nt h es e at h eq u a n t i t yo ft h ei n f o r m a t i o ns o u r c e a n dt a k ei n t of l e x i b l ya p p l i e d ，c o m eu pm o r ee n e r g yc o n c e n t r a t i o n si nt h em o r ep u r e b i o i n f o r m a t i o np r o c e s s i n g i tp r o v i d e st h ec o n v e n i e n ta n de f f i c i e n tr e s o u r c eo fp u b l i c b i o i n f o r m a t i c st e c h n o l o g ys e r v i c e sp l a t f o r mt o w a r dt h ei n t e r a c tc u s t o m e ri nt h ew a yo f w e b a n da c c o r d i n gt ot h et h o u g h to fe n c o d i n gs e q u e n c eb yh e x a d e c i m a la n dl o o k i n g f o r t h eo p t i m a lv a r i a b l ew i n d o ws i z e ，t h i st h e s i sp r o p o s e sa l la l g o r i t h mn a m e d s l a h a wa b o u ts i m i l a rn u c l e o t i d es e q u e n c es e a r c hb a s e do nb l a s tm e t h o d t h i s a l g o r i t h ma p p l i e sh e x a d e d m a ic o d et os t o r ed a t aa n dg e t st h eo p t i m a ls e a r c hw i n d o w v a l u et h r o u g ht h es e q u e n c es e g m e n t ss i m i l a r i t yd e g r e e i tr a i s e ds p e e da n dt h ea c c u r a t e d e g r e ea n de c o n o m i z e dt h es t o r es p a c e b u i l du pa ne x p e r i m e n te n v i r o n m e n ta n d c a r r i e do u tt oc o r r e s p o n da l g o r i t h m s u n d e rt h es i t u a t i o no ft h es e q u e n c e ss a t i s f y s i m i l a r i t yd e g r e e ，t h ee x p e r i m e n tp r o v e st h a tt h es l a h a w i saf a s ta n dv a l i da l g o r i t h m o fm a t c h i n gs i m i l a rs e q u e n c es e g m e n t s k e y w o r d ：b i o i n f o r m a t i c s ；s e q u e n c e a l i g n m e n t ；s e a r c h a i g o n t h m ；s e c o n d a r yd a t a b a s e h i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：e t 期：少一年o 月e t 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：衅导师签名： 日期：口i 年月pe l 第一章绪论 1 1 研究背景 第一章绪论 在最近的二十几年中，生命科学尤其是分予生物学的发展日新月异。生物信息 学是生命科学与信息科学以及数学、物理、化学等学科相互交融而形成的新兴学 科，是当今最具发展前途的学科之一。它随着美国提出的三大计划中的人类基因 组计划( h g p ，h u m a ng e n o m ep r o j e c t ) l l l 的实旌兴起并快速的发展。生物信息学 在医药、化学工业和农业等行业中具有很大的应用潜力和良好的市场前景。随着 基因组学的发展，设计和创造了许多重要的生物分子，这些分子可以应用到制药、 农业、食品、化工、化妆品、环境、能源等众多领域，产生惊人的经济效益。 随着人类基因组计划的实施，通过基因测序、蛋白质序列测定和结构分析实验， 分子生物学家提供了大量有关生物分子的原始数据，需要利用现代计算机网络技 术对这些原始数据进行收集、整理、管理，以便于检索使用；而且为了解释和理 解这些数据，还需要对数据进行对比、分析，建立计算模型，进行仿真、预测与 验证，这些都促进了生物信息学的产生和发展。生物信息学最终形成一门独立的 学科被推上了生物科学发展的最前沿。生物信息学的出现极大地推动了分子生物 学的发展。 生物信息学对揭示人类及重要动植物种类的基因的信息，继而开展生物大分 子结构模拟和药物设计十分有益，是当今国际上正在迅速发展的自然科学领域的 重大课题之一，不仅对认识生物体和生物信息的起源、遗传、发育与进化的本质 有重要意义，而且将为人类疾患的诊治开辟全新的途径，还可为动植物的物种改 良提供坚实的理论基础。 生物信息学不仅具有重大的科学意义，而且具有巨大的经济效益。据报道， 生物信息学产业的市场在1 9 9 6 年已经达到1 0 亿美元，而到2 0 0 2 年已增长到2 0 0 0 亿美元以上。这是一笔巨大的财富，任何政府的科技决策人都不能对此视而不见。 美国国会已准备投资1 6 0 亿美元，在美国建立5 - 2 0 个将生物学与计算技术结合起 来的中心。法国议会科技决策评估办公室，最近评估了基因工程、生物信息学和 结构化学等学科的应用前景及法国的对策。美国出现了大批的基于生物信息学的 公司，实施了许多生物信息学研究计划，主要与药物设计、基因工程药物、生物 芯片、代谢工程与化学工程密切相关，生物信息学工业是知识经济的一个典型， 电子科技大学硕士学位论文 其潜力巨大，对蛋白质工程和药物开发意义重大。 它的许多研究成果可以较快地产业化，成为价值很高的产品。生物信息学的 这一特点在现有的许多学科中几乎是独一无二的，应用的领域十分广阔，会带动 一些相关学科和产业的发展，具有重要的现实意义和深远的战略意义。 生物信息学产生和发展的推动因素主要有以下3 个方面： 1 ) 人类基因组计划( h u m a ng e n o m ep r o j e c t ) ； 2 ) 信息技术的大规模应用； 3 ) 生物医药的迅速发展及其经济的需求。l 习 1 2 生物信息学介绍 1 2 1 生物信息学的定义 2 0 世纪8 0 年代末以来，美国提出了开展人类基因组的计划( h g p ，h u m a n g e n o m ep r o j e c t ) 。人类基因组计划旨在通过测定人类基因组d n a 约3 0 亿个碱基 对的序列，搜寻所有人类基因并确定它们在染色体上的位置，明确所有基因的结 构和功能，解读人类的全部遗传信息，使得人类第一次在分子水平上全面认识自 我。人类基因组d n a 序列分布于2 2 条常染色体和2 条性染色体上，目前人们已 掌握其信息存储与表达规律的基因，只占其中的一小部分。对人类基因组的研究， 并不是为了单纯性地积累数据，而是为了揭示大量数据中所蕴藏的内在规律，从 而更好地认识和保护生命体。1 3 j 随着人类基因组计划的实施，越来越多的微生物和其它模式生物( 如秀丽隐 杆性虫) 也己经完成了全基因组测序工作。这些大型国际合作项目所产生的巨量 数据，对数据处理工作提出了前所未有的要求。人们己经迫切认识到，如果不能 及时分析和有效利用这些信息，那么耗费巨资开展各种基因组计划是没有意义的。 生物信息学就是在人类基因组计划推动下产生的运用计算机技术管理生物信息的 - - f 3 新兴学科。美国人类基因组计划实施五年后的总结报告中，对生物信息学作 了定义，总结如下； 生物信息学是一门新兴的交叉学科，它以核酸、蛋白质等生物大分子为主要 研究对象，以数学、物理、化学等自然科学和信息科学、计算机科学等工程科学 为主要手段，以计算机硬件、软件和计算机网络为主要工具，对生物大分予数据 进行存储、管理、注释、加工，以达到阐明和理解大量数据所蕴含的生物学意义 2 第一章绪论 的目的，并通过对序列和结构数据及其相关文献的查询、搜索、比较、分析，从 中获取基因编码、基因调控、代谢途径、核酸和蛋白质结构功能及其相互关系等 理性知识，在大量信息和知识的基础上，探索生命起源、生物进化以及细胞、器 官和个体的发生、发育、病变、衰亡等生命科学中重大问题，发现它们的基本规 律和时空联系。 广义地说，生物信息学从事对生物信息地获取、加工、储存、分配、分析和 释读，并综合运用数学、计算机科学和生物学工具，以达到理解数据中的生物学 含义的目标。这一定义包括了两层含义：一是对海量数据的收集、整理和管理， 也就是管理好这些数据；另一是从中发现新的规律，也即是用好这些数据。【4 】 从信息学的角度来看，生物分子是生物信息的载体，如d n a 核苷酸序列对蛋 白质氨基酸序列进行编码，蛋白质序列决定蛋白质结构，而蛋白质结构又决定了 蛋白质的功能。归根到底，d n a 序列包含了最基本的生物信息，换言之，生命的 信息存储在d n a 四种字符组成的序列中。至于生物大分子蛋白质，则执行着有机 体内各项重要任务，如生化反应的催化、营养的运输、信号的识别与传递。遗传 信息从d n a 序列向蛋白质序列的传递是人类已经基本了解的第一部遗传密码，而 有人将蛋白质序列到蛋白质结构的关系称为第二部遗传密码。第一部遗传密码已 被破译，但对密码究竟处于d n a 序列的哪些区域还了解得不全面。对于第二部密 码，目前则知之甚少。无论是第一部遗传密码，还是第二部遗传密码，都隐藏在 大量的生物分子数据之中，生物分子数据内涵的很大一部分就是遗传信息。以下 简单介绍与生物大分子d n a 和蛋白质相关的部分分子生物学知识。 1 2 2d n a 相关分子生物学知识 d n a 分子包含两条链，它们相互缠绕在一起，其基本组成单位是核苷，每一 个核苷由一分子磷酸、一分子脱氧核糖以及一分子碱基组成( 碱基共有4 种，分 别是a 腺嘌呤，g 鸟嘌呤，c 胞嘧啶，t 胸腺嘧啶) 。在一般的条件下，d n a 呈双 螺旋结构，这种双链结构依靠嘧啶和嘌呤之间的氢键连在一起，a 和t 配对，c 和g 配对，这样配对的一对碱基称为一个碱基对( b p ) ，d n a 结构见图1 1 。基因 组的大小通常使用碱基对的数量来表示；比如，人类基因组包含大概3 0 亿个碱基 对。碱基间配对的特异性是d n a 精确复制的基础。在d n a 复制中，d n a 双螺旋 中的每一条链都作为新链合成的模板，模板链决定了新链的系列，两条新合成的 d n a 就象双生子，每一条都是父本d n a 的精确复制。4 种含氮的碱基在脱氧核糖 3 电子科技大学硕士学位论文 一磷酸框架内按照特定的顺序排列( d n a 序列) ，这种序列中蕴涵了指导生物体生 长发育并形成自己独特性状的遗传密码。遗传信息由核苷酸序列编码，一旦给定 某一条链上的核苷酸序列，那么根据互补规则，另一条序列上的核苷酸序列也会 自动确定。因此，d n a 双螺旋模型对遗传的分子机理产生了深远的影响。d n a 分 子的复制揭示了遗传信息的传递，而互补的双链则确保了信息复制的正确性。在 d n a 复制时，每条链先解开螺旋，碱基之间的氢键断裂，两条链分离。每条链指 导一条新链的合成，游离的核苷酸严格按碱基互补配对的原则加到新链上。即腺 嘌呤a 和胸腺嘧啶t 配对，鸟嘌呤g 和胞嘧啶c 配对。因此每个子细胞都会获得 一条父链及一条子链。这种严格的互补配对原则保证了新链是原链的一个精确拷 贝，尽可能地降低了发生复制差错( 基因突变) 的危险，这种差错可能会极大地 改变生物体自身或后代的性状。p 卅 图卜1d n a 的结构 细胞分子中还有另外一种核酸r n a ( r i b o n u c l e i ca c i d ) 能够携带遗传信息。 r n a 和d n a 的相同之处在于其碱基也具有配对能力，但其使用碱基尿嘧啶u 4 第一章绪论 ( u r a c i l ) 来代替d n a 中的胸腺嘧啶t ( t h y m i n e ) ，即：在r n a 中腺嘌呤a ( a d e n i n e ) 和u ( u r a c i 0 配对，鸟嘌呤g ( g u a n i n e ) 和胞嘧啶c ( c y t o s i n e ) 配对。r n a 和d n a 的 不同之处主要是：r n a 是一单链的分子结构，不像d n a 位于细胞核内，r n a 可 以在细胞核和细胞质中发现。 信使r n a ( m e s s a g er n a ) 是另外一种r n a 分子，它的作用是：携带来自于 d n a 的遗传信息到核糖体，并最终转录到蛋白质中。 1 2 3 生物信息学展望 生物信息学从产生到现在不过十几年的时间，仍然处在萌芽阶段，但这一新 兴学科充满了活力，已经显示出了巨大的潜力。当今生物信息学已经广泛渗透到 生物学及相关的各个领域，生物学的迅速发展还会为生物信息学不断提出新的任 务和挑战。例 当基因组测序计划持续开展，研究重点已逐步从数据的积累转向数据的解释。 用于序列分类、相似性搜索、d n a 序列编码区识别、分子结构与功能预测、进化 过程的构建等方面的计算工具已成为研究工作的重要组成部分。生物信息学已成 为介于生物学和计算机科学学科前沿的重要学科，在许多方面影响着医学、生物 技术和人类社会。 随着人类基因组研究的不断深入，生物信息技术面临着巨大挑战，同时也为 促进生物医学研究的发展提供了机遇。结合重大科学问题的研究，发挥我国在理 论生物学和信息科学领域的研究特色，发展生物信息学的新理论、新方法、新技 术和新软件。生物信息学基础理论研究包括：分子进化遗传学、群体遗传学、统 计生物学、基因组学以及计算机科学和应用数学的相关学科等。 二十一世纪是生命科学的时代，亦是信息科学的时代。生物信息学是这两种科 学的结合，它不仅可以促进生命科学的进步，亦可以推动信息科学的发展。尽管 目前生物信息学还处于初级阶段，需要不断地成熟和完备，但是它对人类的影响 和价值是无法估计的。2 1 世纪亦将是生物信息学的时代。当前最缺乏的是生物信 息学的人才，必须在实践中加速培养既会生物学，又会计算机科学的双料人才， 生物信息学才有希望。 总之，计算机及计算机网络的应用己渗透到人类基因组研究的各个层面，随 着我国计算机产业的发展和中国人类基因组计划的实施，中国生物信息学研究必 将迅速发展，做出具有国际领先水平的工作，定会在国际科学界占有一席之地， 5 电子科技大学硕士学位论文 为中国人类基因组研究的发展创造有利条件。 1 3 本文的研究意义 生物信息学的研究范围很广，其研究对象与生物数据直接相关。因此，各种生 物数据库的建立和管理是一切生物信息学工作的基础和出发点。 一般而言，生物信息一级数据库的数据直接来源于原始的实验数据( 包括核酸 和蛋白质两类生物大分子的序列和结构信息) ，只经过简单地整理和注释。一级数 据库数据量大，更新速度快，数据通过i n t e r n e t 进行发布，主要由国际著名生物信 息中心( 如美国国家生物技术信息中心n c b i 、欧洲生物信息学研究所e b i 和日本 国家遗传学研究所n i g 等) 负责维护，一般还提供免费的数据库检索服务。 而二级数据库的构建很少来源于直接的实验数据，往往是结合某一研究领域的 实际需要，通过搜索已知数据库( 主要为一级数据库) 的数据信息，并对其进行 ，n - r 整理而成。二级数据库专一性强，数据质量高，在实验室的日常工作和生物 信息学的研究发展中具有不可替代的重要作用。所以在生物信息学研究当中，构 建一个二级数据库和研究平台是相当有必要的。本文所构建的生物信息实验平台 正是为生物信息研究人员提供的一个方便快捷的专业核苷酸序列数据库。 序列比对也就是对核酸及蛋白质序列的相似性分析是生物信息学研究又一个 重要的内容。序列比对对于生物序列中的功能、结构及进化信息是非常有用的。 获得最有可能的或者说是称为最佳的比对来发现这些信息是很重要的。序列分析 中得出的非常相近或相似的序列往往可能具有相同的功能，对蛋白质而言可能具 有相同的三维结构。另外，如果来自不同的生物体的序列相似，那么它们可能具 有相同的祖先序列。 对于核酸和蛋白质，可以看成是由不同的字符组成的字符串序列，所以对核 酸和蛋白质的分析转化为对多个字符组成的字符序列进行比对，反应它们之间的 匹配和不匹配情况。 本文所作的关于生物序列的比对算法的研究和提出的相似核苷酸序列搜索算 法：“基于十六进制可变窗口的序列局部比对方法”( s e q u e n c e l o c a l a l i 卸j - n e n t b a s e d 0 1 1h e x a d e c i m a la l t e r a b l ew i n d o w , s l a h a w ) ，是在前人的工作上对生物信息学领 域的进一步研究，帮助生物信息研究人员在海量的生物信息中找到需要的资源， 以便进行深一步的生物研究。对于目前生物技术迅猛发展，国内生物技术企业面 临参与国际竞争的环境下，利用先进的计算机技术对生物数据进行处理，得出结 6 第一章绪论 果，最终实现生物技术和计算机技术的结合，促进生物技术的发展，作了有益的 研究。 1 4 作者的主要工作 作者的主要工作包括： 1 ) 简单的介绍了生物信息学的发展、研究内容、生物数据库，对序列比对的 各种算法：点阵法、动态规划全局比对算法、s m i t h - w a t e r m a n 算法、f a s t a 算法、 启发式b l a s t 算法等做了简单描述，并分析了序列比对研究的目的及其意义。 2 ) 利用n e t 相关技术，实现了一种建立生物信息学研究平台的框架体系。该 平台用w e b c l i e n t 类的方法提取分析网络数据库资源并自动创建本地二级生物信 息数据库，并用a sp n l 玎和a d o n e t 实现了对此二级数据库的查看、查询等操 作。 3 ) 在b l a s t 部分算法的基础上，基于十六进编码序列和寻找最优可变窗口大 小的思想，提出了一种新的相似核苷酸序列搜索算法s l a h a w 。本算法提出一种 相似程度概念，通过序列片断相似程度得到可变的最佳搜索窗口大小，从而提高 搜索速度和准确度。此算法在生物信息学上可以快速而准确地找到相似序列或同 源序列。 4 ) 建立了s i _ a h a w 算法的实验环境，经过多次实验，给出具体的实验方法 和实验结果，验证了在序列满足相似度的情况下，s i _ a h a w 是一种快速而有效的 相似序列片断匹配算法。 5 ) 用w e bs e r v i c e s 技术封装序列对比算法，采用b s 模式可让客户端直接调 用，有助于二级数据库开发人员在海量的信息源中迅速找到真正需要的生物数据 信息，并灵活地加以应用，从而将更多的精力集中在更纯粹的生物信息处理上来， 并可以通过w e b 的方式向i n t e r n e t 用户提供方便而有效的公共生物信息技术服务平 台的各类资源。 1 5 章节安排 本文研究了生物信息学领域的基础知识、生物数据库、序列比对算法等方面， 建立了本地生物信息二级数据库，并基于n e t 技术实现了一个生物信息研究平台， 生物信息研究人员可用此平台来作生物信息研究实验。提出了一种相似核苷酸序 7 电子科技大学硕士学位论文 列搜索算法s l a h a w ，并采用w e bs e r v i c e s 将算法封装，通过b s 模式向i n t e r n e t 用户提供调用接口。通过实验对s l a h a w 算法进行了分析，从搜索速度和敏感度 上证明了s l a h a w 是一种有效的相似序列比对算法。 本章主要介绍了和本文有关的生物信息学背景知识，简单介绍了生物信息学 的定义和d n a 相关的分子生物学知识背景，并对生物信息学的发展进行了展望发 展历史与现状。 余下的章节安排如下： 第二章介绍了国内外在生物信息数据库和生物序列对比方面的发展情况。着 重介绍了d n a 和生物信息数据库的发展历史与现状。并探讨了生物信息学领域的 几个主要研究方向。并研究了生物催漶学中序列比对的各种算法：点阵法、动态规划全 局比对算法、s m i t h - w a t e r m a n 算法、f a s t a 算法、启发式b i a s r 算法等，并分析了序列 比对研究的目的及其意义。 第三章研究了如何构建本地生物信息二级数据库，介绍了构建二级数据库的 必要性和一般方法，并重点阐述了本生物信息研究平台的构建过程和方法，以及 如何用w e bs e r v i c e s 来封装序列比对算法。 第四章首先介绍了s i _ a h a w 算法的数据结构和算法描述，然后对提出的相似 核苷酸序列搜索算法s l a h a w 的作了详细的描述，给出了算法思想、算法示例和 实现界面。 第五章对s l a h a w 算法在本生物信息研究平台上进行了多次实验，给出具体 的实验方法和实验结果，验证了s i _ a h a w 算法是一种快速而有效的相似核苷酸序 列片断匹配算法。 第六章对全文进行了总结，并指出下一步的研究方向。 8 第二章国内外发展情况 第二章国内外发展情况 我们所处的2 1 世纪是生命科学的世纪，因为随着历时1 3 年、耗资数十亿的 人类基因组计划的完成，其为最终揭示人体构造之谜奠定坚实的数据基础，所以 将人类基因组计划作为2 1 世纪的里程碑。而随着基因组计划的实施，不管是在国 内还是在国外，生物信息学都在蓬勃的发展。 欧洲、美国、日本等发达国家都十分重视生物信息学的发展，在生物信息数 据库建设和成立生物信息学专业机构两方面均走在世界前列，每年拨出相当多的 经费支持生物信信息学的发展，己相继在因特网上建立了各自的生物信息学网络 节点，如美国的国家生物技术中心，国家基因组资源中心、英国的欧洲生物信息 研究所、日本的国家遗传学研究所等。欧洲分子生物学网络组织( e u r o p e a n m o l e c u l a r b i o l o g y n e t w o r k ，e m b n e t ) 是目前国际上最大的分子生物信息研究、开发 和服务机构，通过计算机网络使英、德、法、瑞士等国生物信息资源共享。 对欧美国家来说，对生物信息学的研究己经有了较长的时间，主要是从数据 库方面来看，美国在1 9 7 9 年就建立了g e n e b a n k 数据库，e m b l 数据库服务也 在1 9 8 2 年就已经提供，而日本的d d b j 也在1 9 8 4 年开始建立并在1 9 8 7 年提供服 务，其它一些国家，如德国、法国、意大利等，在共享网络资源的同时，也分别 建立自己的具有专业特色的二级数据库，来为本国的生物学研究提供服务。 生物信息学在我国起步较晚，但是发展很快。早在1 9 9 3 年在国家自然科学基 金委的资助下，中国己经开始参与人类基因组计划，但田于条件所限，我国发展 生物信息学面临许多制约因素，其中最主要的是人才缺乏、认识不够和信息网络 建设落后。因此，我国生物信息学研究真正起步是在1 9 9 5 1 9 9 6 年。 在最近发展的十几年中，我国的很多科研所和高校都加入了研究生物信息学的 行列，成立了一些机构：中科院上海生命科学研究院于2 0 0 0 年3 月成立了生物信 息学中心，北京大学于1 9 9 7 年3 月成立了生物信息学中心。并且一些著名大学和 研究所在各自领域取得了一定成绩：中科院生物物理所在e s t 序列拼接及在基因 组演化方面、天津大学在d n a 序列的几何学分析方面、清华大学在蛋白质结构模 拟方面等等。 9 电子科技大学硕士学位论文 2 1 生物信息数据库 2 1 1 生物信息数据库介绍 分子生物学中最重要的两种物质是：d n a 和蛋白质。众所周知，d n a 是一种 由碱基按一定规则排列而成的双链结构生物大分子。这种碱基排列顺序就构成了 生物的遗传信息。蛋白质是由d n a 根据链结构上的某些功能碱基序列复制而成的 具有特殊功能的生物大分子。生物基因包括d n a 链上的碱基及其排列顺序。虽然 碱基的数目只有四种a d e n i n e ( a ) 、c y t o s i n e ( c ) 、g u a n i n e ( g ) 、t h y m i n e ( t ) ，而它们 在d n a 上做各种有序的排列形成了生物的多样性。所以对这种碱基序列进行测序、 编码和研究是生物学研究最重要的工作。生物基因序列数据就是对于某一生物基 因采用某种编码方式编码产生的数据。这些基因数据以数据库的形式被存放起来， 就构成了各种各样的序列数据库。序列数据库是分子生物信息数据库中最基本的 数据库，包括核酸序列数据库、蛋白质序列数据库和蛋白质结构数据库( p d b ) 三类，以核苷酸碱基顺序或氨基酸残基顺序为基本内容，并附有注释信息。序列 数据库早期的数据主要由数据录入人员通过查阅文献杂志搜集，或者由科研人员 用磁盘、电子邮件方式向国际生物信息数据库中心递交。数据中心对搜集到的序 列数据进行整理、维护，并定期通过磁盘、磁带和光盘方式向全世界发布。序列 数据库的序列数据来自核酸和蛋白质序列测定；注释信息包括两部分，一部分由 计算机程序经过序列分析由计算机程序生成，另一部分则依靠生物学家通过查阅 文献资料而获得。随着基因组大规模测序计划的迅速开展，序列数据库特别是核 酸序列数据库的数据量迅速增长，数据来源主要集中于国际上几大著名的测序中 心，如位于英国剑桥南郊基因组园区的s a n g e rc e n 仃e ，华盛顿大学基因组研究中 心等。我国于1 9 9 9 年参加国际人类基因组研究项目，己经于2 0 0 0 年4 月按计划 完成人类基因组1 序列的测定。 随着近年来生物学实验方法和检测手段的不断发展与提高，积累了大量的生 物学数据，对这些数据进行搜集和整理，形成目前数以百计的生物学。数据库分 子生物信息数据库种类繁多，归纳起来，大体可以分为以下两类：一级数据库及 二级数据库。一级数据库记录实验结果数据和一些初步的解释，如d n a 序列，由 晶体衍射( c r y s t a l l o g r a p h y ) 获得的蛋白质结构等。二级数据库是从生物大分子序列、 结构、功能数据中提取有用的信息，使它们更便于特定专业人员的使用，如真核 第二章国内外发展情况 生物启动子序列库e p d 和蛋白质一般结构或功能模体( m o t i f ) 数据库p r o s i t e 。 一个数据库记录一般由两部分组成：原始序列数据和描述这些数据生物学信 息的注释。注释中包含的信息与相应的序列数据同样重要和有应用价值。在基因 组规模上的测序过程便产生了注释问题。对于那些从自动测序仪中出来的序列， 我们往往只知道它们来自何种细胞类型，而其它方面却知之甚少。如果你在确定 一段未知蛋白质序列的功能，发现一个与之匹配的序列，但该序列却没有任何有 关功能的信息时，研究工作便很难继续了。 根据生命科学不同研究领域的实际需要，对基因组图谱、核酸和蛋白质序列、 蛋白质结构以及文献等数据进行分析、整理、归纳、注释，构件具有特殊意义和 专门用途的二次数据库，使数据库开发的有效途径。如图2 1 所示： 1 l 电子科技大学硕士学位论文 2 1 2 核酸序列数据库 图2 - 1 分子生物信息数据库 目前国际上有3 个主要的核酸序列数据库为e m b 乙d d b j ，g e n b a n k 。【6 l 1 ) e m b 卜欧洲分子生物学实验室( e u r o p e a nm o l e c u l a rb i o l o g yl a b o r a t o r y ) ， 位于英国剑桥，由欧洲生物信息学研究所( e b i ) 维护的核酸序列数据构成，查询检 索可以通过因特网上的序列提取系统( s r s ) 服务完成。数据库网址是： h t t p ：w w w e b i a c u k c m h i 。e m b l 数据库正是本文第三章中使用的数据源。 2 ) g e n b a n k - - 美国国家生物技术信息中心( n a t i o n a lc e n t e rf o rb i o t e c h n o l o g y i n f o r m a t i o n ，n c b i ) ，该中心隶属于美国家医学图书馆，位于美国家卫生研究院( n i h ) 内，g e n b a n k 库包含了所有已知的核酸序列和蛋白质序列，以及与它们相关的文 献著作和生物学注释。它是由美国国立生物技术信息中- c , , ( n c b i ) 建立和维护的。 n c b i 的网址是：h t t p ：w w w n c b i n l m n i h g o v 。 3 ) d d b j - - e i 本d n a 数据库( d n ad a t a b a s eo fj a p a n ) ，日本d n a 数据仓库 ( d d b j ) 也是一个全面的核酸序列数据库，与g e n b a n k 和e m b l 核酸库合作交换数 据。使用其主页上提供的s r s 工具进行数据检索和序列分析。d d b j 的网址是： h t t p ：w w w d d b i n i g a c j p 。 这三个数据库系统互相合作，共享序列信息，其序列来源于作者提交或学术刊 物。e m b l 是由欧洲分子生物学实验室( e u r o p e a nm o l e c u l a rb i o l o g yl a b o r a t o r y ) 于 1 9 8 2 年创建的，其名称也由此而来，目前由欧洲生物信息学研究所负责管理。美 国国家健康研究院( n a t i o n a l i n s t i t u t e o f h e a l t h ，简称1 , n i l ) 也于2 0 世纪8 0 年代初委 托洛斯阿拉莫斯( l o s a l a m o s ) 家实验室建立g e n b a n k ，后移交给国家生物技术信 息中心n c b i 隶属于n i h 下设的国家医学图书馆( n a t i o n a ll i b r a r yo fm e d i c i n e ，简 称n u d 。d d b j 是d n a d a t ab a s eo f j a p a n 的简称，创建于1 9 8 6 年，由日本国家 遗传学研究所负责管理。1 9 8 8 年，e m b l , g e n