（农业机械化工程专业论文）生物信息平台构建及序列比对算法研究.pdf

摘要 生物信息平台构建及序列比对算法研究 农业机械化工程专业硕士研究生孙荣荣 指导教师余建桥教授 摘要 生物信息学是当今最重要、最前沿的科学发展领域之一，已被广泛用于基因序列数据的 获取、处理、分析和管理等许多方面，对于分子生物学和生物医学研究的深入发展发挥了巨 大作用。序列比对是生物信息学中一种基本的信息处理方法，对于发现核酸和蛋白质序列上 的功能结构和进化的信息具有非常重要的意义。 本文的工作是在本人所从事开发的柑橘生物信息平台的基础上进行的。针对生物信息平 台开发过程中遇到的问题海量的基因数据库序列比对，我们在平台中采用了快速、高效 的序列比对算法。本文的主要工作包括基因序列比对算法研究和生物信息平台的构建。 本文首先采用了一种基于n e t 和s q ls e n ，e r 相关技术构建生物信息平台的方案。在此 基础上选择i n s d s q ex m l 作为中间数据格式，以x m l 为数据存储语言。使用大型关系数 据库s q ls e n ，e r 构建二级生物信息数据库。 其次，对b l a s t 算法进行了改进，提出了基于十六进制编码序列通过循环位移寻找最 优比对序列的思想，本算法通过将二进制表示的d n a 序列转换为十六进制，并根据序列片 断相似度得到最佳搜索窗口值，从而提高搜索速度和准确度。本文在搭建好的生物信息平台 基础上，以柑橘基因数据为例建立出实验环境并实现了相应算法。 最后是生物信息平台的构建，本文所建立的生物信息平台是以生物信息学为基础，通过 编程而实现的生物信息处理系统，包括生物信息二级数据库和生物信息处理模块，其作用是 通过序列检索、序列比对、相似性搜索、同源性搜索等操作从大量的序列信息中获取基因结 构、功能和进化等知识，以便理解数据中蕴含的生物学意义，决定研究方向和策略。 实验表明，本文所构建的生物信息平台整合多个一级数据库数据及服务资源，并且开发 和整合了大量的生物信息工具，为用户提供统一的查询平台；数据格式、查询方式与公开数 据库兼容性好，查询灵活、功能强：运用x m l 存储数据使得数据库内容更新更加方便；改 进算法的应用则使系统对用户操作的响应时间更短，查询的准确率更高；自己独立开发，维 护与开发方便、成本低。 关键词：序列比对b l a s t 算法生物信息数据库 两南大学硕士学位论文 a b s t r a c t t h eb i o i n f o n n a t i c si so n eo fm em o s ti m p o n a n ta n da d v a n c e ds c i e n c ed e v e l 叩m e n tr e a l m s n o w a d a y s i th 笛a l r e a d yb e e nu s e df o ro b t a i n i n g ，h a n d l i n g ，a i l a l y z i n ga n dm a n a g i n go ft h eg e n e s e q u e n c ed a t ae x t e n s i v e l y ，w h i c hh 器ag r e a ti m p a c ti nt l ed e v e l 叩m e n to fm 0 1 e c u l a rb i o l o g y 锄d b i o m e d i c a ls c i e n c e t h es e q u e n c ea l i 印哪e n ti sal 【i n do fb 私i cm e t h o do fh a l l d l i n gi n f 0 兀n a t i o ni n b i o i n f o 肌a t i c s i ti sv e 叮i m p o r t a n tt od i s c o v e 巧t h e c t i o ns m l c t l i r ea n de v o i u t i o ni n f b m 诅t i o no f n u c l e i ca c i da 1 1 dp m t e i n 1 1 1 i st 1 1 e s i sc a 耐e s0 nt 1 1 eb i o i n f o 册a t i o nt e m c eo fc i t m sw h i c hi 锄s t u d y i n g a i m e da tt l l e a c t u a lp r o b l e m si nt h ep r o c e s so fb i o i n f o 册a t i o np r o c e s s i o n 争一al a r g eq u 卸t i t yo fg e n ed a t a b a s e q u e n c ea l i g n m e n t ，w eu s e df 如t ，e f 6 c i e n ts e q u e n c ea l i g 姗e n ta l g o r i 吐l mi 1 1o u rt e r r a c e t h em a i n w o r ko fm i st l l e s i si n c l u d e sr e s e a f c ho fg e n es e q u e n c ea l i 伊衄e n ta l g o t l i ma n dc r e a t i l 他o f b i o i n f o n n a t i o nt e 】r r a c e 1 1 1 i st e x tf i r s tp u to u tak i n do fp l 锄t oc r e a t eb i o i n f 0 册a t i o nt e m c ew 淌t 1 1 e n e t 锄dr e l a t e d t c c l l n i q u eo f 廿l es q ls e n ，e r i i lt 1 1 i sf o u n d a t i o nw es e l e c ti n s d s q ex m l 弱ac e n 舰ld a t af o 彻瞰， u 辩dx m lt os a v ed a t a ，觚d 啪e dl a r g e 咒l a t i o nd a t a b a s q ls e r v e rt os e tu pas e c o n d a 巧 b i o i n f 0 n n a t i c sd a 协a s e 1 1 1 e n ，i m p r o v eb l a s ta 1 9 0 r i t l l i l l p u to u tat l l o u 咖b 舔e do nh e x a d e c i m a lc o d es e q u e n c e 勰d c i r c u l a t i o nm o v et ol o o kf o rt i l em o s ts u p e o rs e q u e n c e t h i sa l g o r i m mm i s e ss e a r c h i n gs p e e d 矾d a c c u m c yd e g r e ea c c o r d i n g t 0c o n v e n i n gt l ed n as e q u e n c ew h i c hi si i i b i l l a d ，s y s t e mt 0 h e x a d e c i m a l ，a i l dg e t st 1 1 eb e s tw i n d o wv a l u ea c c o r d i n gt om es e q u e n c ef h 舯e n tl i k e n e s sd e g r c e b a l s eo nt h eb i o i n f 0 肌a t i o nt e m c ew em a d et l l eo r 锄g eg e n ed a t a 鹤a l le x 觚l p l et 0b u i l du p 锄 e x p e f i m e n t 朋v i r o n m e n t 觚dc 卸哆o u tt h ea l g 谢t 1 1 】m t h e1 a s ti st oc r e a t eb i o i i d 0 力n a t i o nt e n a c e t h eb i o i i l f 细a t i o nt e m c ei nt l l i st e x ti sa b i o i n f 0 肌a t i o n h a n d l i n gs y s t e mb a s e d o nb i o i n f o n n a t i o n ，i n c l u d e s s e c o n d a 巧b i o i n f o h l 舱t i o n d a t a b a s ea n db i o i n f o 姗t i o np r o c e s s i n gm o l d s t h e 血r l c t i o no fi ti st og a i ng e n e ss 觚l c t u r e ， f h n c t i o n ，a i l de v o l u t i o nb ys e q u 锄c ed o c u m e n tm 孤a g 黜她b 鹊i cs e q u e n c ea l i 印m e l l t ，s e q u e l l c e a l i g n m e n tp a r a m e t e rc o n s t i t u t i o n ，s e q u e n c ea l i 是皿m e n tr e s u l to u t p u t t h e nw ec a nc o m p r e h e n d b i o i n f o m a t i o nm e 孤i n gc o n t a i n e di i lt h ed a t a ，t od e c i d er e s e a f c hd i r e c t i o na n ds 仃a t e g y e x p e m e n tp r o v e dt l l a tt h et e l l r a c ei nt 1 1 i s t e x tm e r g e sm m yf i r s td a t a b a s ed a t aa n ds e r v i c e 陀s o u r c e s ，a n dd e v e l o pal o to fb i o i n f o r m a t i o nt o o l s ，p r o 、，i d eu n i f o 珊t e m c ef o ru s e r s ；t h ed a t a f o 皿豫t ，s e l e c t i n gm o d eh a v eg o o dc o m p a t i b i l i t yw i t lp u b l i cd a t a b a s e sa n da r ev e r yf l e x i b l e ；u s i n g x m lt os a v ed a t ai i l a k e s ( 1 a 劬a s em o r en e wa n dc o n v 饥i e i l t ；u s i i l gn e wb l a s t a l g o r i t l l i l lm a l ( e s s y s t e mr e s p o n d i n gt i m ef o ru s e r 叩e m t i o ns h o r t e r 卸d c u m c yd e 伊e eh i g h e r ；b e c a u s ei t i s a b s t r a c t d e v e l o p e db ym y s e l f ，i th a st h ea d v a n t a g e so fc o n v e n i e n c ea j l dd e v e l 叩m e n tl o wc o s t k e y w o r d s ：s e q u c ea l i 伊l i i l e n t ，b l a s ta 1 9 0 r i t h m ，b i o i n f o r m a t i o n ，d a t a b 弱e i i l 独创性声明 学位论文题目：生物焦皇壬金抱建区庄到出挝篡洼珏窥 本人提交的学位论文是在导师指导下进行的研究工作及取得的研 究成果。论文中引用他人已经发表或出版过的研究成果，文中已加了 标注。 学位论文作者：砑、昧椿签字日期：j 口力汐年5 月吕 日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生部可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 。 学位论文作者签名： 劲、昧徕 导师签名： 签字日期：j 一8 年5 月8 日签字日期： 绪论 第1 章绪论 1 1 研究背景 随着生物学和医学的迅速发展，人类已获得大量的生物分子数据，并且其积累速度正以 爆炸方式增加。如何从这些庞大、复杂且具有丰富内涵的数据中揭示对人类有用的信息，是 生物学家所面临的一个严峻挑战。生物信息学就是近年来为迎接这种挑战而发展起来的一种 新型交义学科【i 】o 生物信息学的研究范围很广，其研究对象与生物数据直接相关。因此，各种生物数据库 的建立和管理是一切生物信息学工作的基础和出发点。生物信息数据库主要分为一级数据库 和二级数据库。其中，一级数据库的数据直接来源于原始的实验数据包括核酸和蛋白质两类 生物人分子的序列和结构信息，只经过简单地整理和注释。一级数据库数据量大，更新速度 快，数据通过网络进行发布，主要由国际著名生物信息中心如美国国家生物技术信息中心、 欧洲生物信息学研究所和日本国家遗传学研究所等负责维护。而二级数据库的构建很少来源 于直接的实验数据，往往是结合某一研究领域的实际需要，通过搜索已知数据库( 主要为一 级数据库) 的数据信息，并对其进行加工整理而成。二级数据库专一性强，数据质量高，在 实验室的日常工作和生物信息学的研究发展中具有不可替代的重要作用。 生物信息学的基本任务是对各种生物大分子序列进行分析，从大量的序列信息中获取基 因结构、功能和进化等知识【2 】o 其中，序列比对( s e q u e n c ea l i 印m e n t ) 是一种将未知序列同已 知序列进行相似性比较的重要分析手段。从序列的片段测定，拼接，基因的表达分析，到r n a 和蛋白质的结构功能预测，物种亲缘树的构建都需要进行生物分子序列的相似性比较1 3 】。目 前，国际互联网上提供了众多的序列比对分析软件。然而，不同的分析软件会得到不同的结 果，序列比对所使用的算法参数在很大程度上直接影响分析结果。有时常常会由于采用了不 合适的参数而丢失了弱的但却具有统计学显著性意义的重要信息，导致随后的实验研究走弯 路。因此，生物信息平台中的序列比对算法研究具有非常重要的理论和实践意义。 1 2 研究目的和意义 从生物信息学的定义可以得知，生物信息学的中心任务就是从浩如烟海的序列数据中提 取理性知识。生物学家所面临的任务，不仅要解决高效的数据存储手段，而且要开发有效的 数据分析手段。 目前生物信息数据库的开发和维护单位将来自实验的原始数据稍加整理和注释后，各自 开发一套系统为用户提供数据查询和分析服务，这一定程度利于用户处理数据，但仍不可避 免地需要用户在多个网站间切换，寻找感兴趣的数据及服务，并不得不学习和适应不同的系 四罔人7 坝= c 孚世记义 统使用方法。有许多二级数据库针对特定的研究内容整合多个一级数据库，如专注于蛋白质 结构家族分类或人类基因组图谱等，但这不利于相关内容的查询。因此可以从生物学意义角 度选择更综合的多个一级数据库，整合其数据及服务资源，为用户提供统一的查询平台。 在构建生物信息平台的过程中，遇到一个主要问题是序列比对问题，一股来说，评价生 物序列比对算法有两个标准，一为算法的运算速度，二为获得最佳比对结果的敏感性。目前， 己经有很多序列比对的软件开发出来，但存在一些问题。双序列比对中常见的算法是 s t n j t l l w a t e r n l a n 算法、b l a s t 算法与f a s t a 算法，是序列局部比对算法的基础，后来的许多 其它算法都是基于这些算法开发和改进的。三者比较而言，s l i l i t l l w a t e m 姗敏感性强，但算法 的复杂度最高，需要在具有极高计算能力的超级计算机上实现；后两种则以预测的敏感性的 下降来换取速度上的提高，如b l a s t 运算速度最快，可以在普通计算机上运行，但敏感性最 差同。除此之外，目前还缺乏快速而又十分有效的算法。因此，目前生物信息平台开发中的主 要困难就是如何研究和设计同时具备高敏感性和高速度的算法。 本文在前人研究成果的基础上，探索性的提出生物信息学中序列比对的改进与创新算法， 并以此为基础、以柑橘为例构建生物信息平台，旨在为用户提供一个针对研究各种柑橘基因 特性的专业操作平台，将各种数据库资源整合到一个具有统一数据模式的二级数据库中，通 过编程的方式对用户提供统一界面，方便用户进行序列检索、序列比对、相似性搜索、同源 性搜索等操作。开发出来的柑橘生物信息平台能实现柑橘各种生物大分子的序列分析，能从 大量的序列信息中获取基因结构、功能和进化等知识。帮助使用者理解数据中蕴含的生物学 意思，决定研究方向和策略，在某种程度上减少研究者时间和经费的开支。 生物序列比对算法的研究、改进及应用一方面在前人工作的基础上对生物信息学领域的 进一步研究；另一方面极大提高了系统运行速度及检测结果的准确度。 1 3 研究内容 随着生物学数据的大量积累，对数据库搜索和序列比对算法提出了更高的要求，构建专 业二级数据库、整合的生物信息平台以及开发兼有高敏感性和高效率的算法成为生物信息学 领域中的一个非常重要的研究课题。 本文研究的主要内容包括： ( 1 ) 利用n e t 相关技术，实现一种建立生物信息平台的框架体系。该平台用x m l 提取 分析网络数据库资源并创建本地二级生物信息数据库，用a s p n e t 和a d o n e t 实现对此二 级数据库的查看、查询等操作。 ( 2 ) 针对序列比对目前存在的时间和空间复杂度以及敏感性问题，综合分析b l a s t 算法 以及其改进算法p a n e m h 岫t e r 序歹0 比对算法的特点，运用循环位移和用十六进制存储的思想 对其进行了改进，并在系统中加以实现。 2 绪论 ( 3 ) 生物信息平台主要模块的实现，包括序列基本分析模、序列同源比较模块、基于动 态规划的双序列比对模块、基于改进的b l a s t 算法模块。 ( a ) 序列基本分析模块包括查找序列开放阅读框、画出序列点阵图、成分分析、统计密 码子、画出碱基分布密度图等功能，采用m a t l a b 7 0 与c 群混合编程的方案实现。 ( b ) 序列同源比较模块是对b l a s t 程序进行本地化，以实现基本的数据库相似性搜索。 ( c ) 基于动态规划的双序列比对模块用基于动态规划的序列比对算法开发的程序对两条 序列进行比对，从而判断其是否具有同源性或相似性。 ( d ) 基于改进的b l a s t 算法模块是在改进的b l a s t 算法基础上编程实现，用于对数据 库进行相似性搜索 就整个研究过程设计技术路线如下： 首先搭建开发生物信息平台的相应软件硬件环境，然后构建生物信息二级数据库，并在 此基础上构建生物信息平台。在构建平台过程中针对遇到的问题，研究和改进相应算法，最 后，编程实现。技术路线如图1 1 所示； 图1 1 技术路线图 3 西南大学硕士学位论文 1 4 组织结构 本文主要研究了生物信息学领域的基础知识、生物信息数据库和序列比对算法，构建了 本地二级生物信息数据库，在此基础上采用n e t 技术实现了一个生物信息平台。针对构建平 台过程中遇到的问题提出了一种改进的b l a s t 序列比对算法。通过实验对新算法进行了分 析，从搜索速度和敏感度上验证其有效性。 本文的章节安排如下： 第t 章为引言部分。 第2 章主要介绍了和本文有关的生物信息学背景知识，简单介绍了生物信息学的定义、 及发展现状，介绍了国内外在生物信息数据库和生物序列对比方面的情况。 第3 章提出了一种采用n e t 和s q ls e r v e r 相关技术构建生物信息平台的方案，研究 了如何构建本地生物信息二级数据库，并重点阐述了本地生物信息二级数据库的构建过程和 方法。 第4 章首先对b l a s t 算法及其改进算法p a t t e n l h u n t e r 和p 甜e n l h u n t 盯i i 进行了研究。 指出算法的不足，并在此基础上进行改进，给出了算法思想及性能评价。 第5 章介绍平台主要模块的实现过程，利用m a t l a b 7 o 与c 撑混合编程，在改进算法 的基础上开发了生物信息学平台。 第6 章总结本文的研究工作，并做出进一步的展望。 4 生物信息平台及序列比对算法 第2 章生物信息平台及序列比对算法 本文所建立的生物信息平台是以生物信息学为基础，通过编程而实现的生物信息处理系 统，包括生物信息二级数据库和生物信息处理软件，其作用是通过序列检索、序列比对、相 似性搜索、同源性搜索等操作从大量的序列信息中获取基因结构、功能和进化等知识，以便 理解数据中蕴含的生物学意义，决定研究方向和策略。其中序列比对是整个平台开发过程中 的重点及难点。下面将对生物信息平台开发所涉及的理论知识做简要介绍。 2 1 生物信息学 2 1 1生物信息学概述 生物信息学( b i o i l l f o m 诅t i o n ) 是生物学、计算机科学以及应用数学等学科相互交叉形成 的一门新兴学科，是8 0 年代末期随着人类基因组计划( h u m a ng e n o m ep r o j e c t ，h g p ) 的启 动而兴起的。它以计算机为主要工具，发展各种生物数据库和应用软件，对逐日增加的浩如 烟海的核酸和蛋白质等大分子的序列与结构数据进行收集、整理、存储、发布、提取、加工、 分析和研究，进而达到揭示数据蕴涵的生物学意义f 4 】。 2 1 2 生物信息学研究任务 生物信息学研究的主要任务是( 1 ) 生物数据库的设计、建立和优化；( 2 ) 从数据库中提取有 效信息的算法；( 3 ) 为用户设计查询信息的界面：( 4 ) 开发数据可视化的有效方法；( 5 ) 与多种资 源和信息建立有效连接；( 6 ) 开发数据分析的新方法；( 7 ) 发展预测的算法，对新产品、新功能、 疾病诊断和治疗等进行预测【5 】。 研究任务包括各种生物数据库、网站、软件、工具和远程网络等等。其中数据库是最基 本的。目前，国际上公共数据库有近百种，其中著名的核酸和蛋白质序列数据库有几十种。 除了公用数据库外，还有很多内部数据库。目前，数据库的内容正以指数速率增长，其内容 每年可增长1 倍。这些信息公布在不同的计算机、不同的数据库和不同的界面上。因此，要 使科学家能迅速地从庞杂的数据库迷宫中，搜集到全部有关信息将十分困难。为此，必须应 用计算工具和程序，将各种专业的、分散的信息资源适当地连接起来，并且能进行快速存取， 集成为新型的w e b 资源和生物信息分析工具。例如，一个理想的基因数据库不仅可以储存全 部基因的信息进行分析和比较，还应该能够预测核酸的结构和功能，指导试验的进行，分析 可能发生的情况，并加以处理这将是生物信息学面临的主要挑战。 2 1 3国内外研究现状 随着基因组计划的实施，国内外在生物信息学上的研究正在蓬勃发展。欧洲、美国、日 5 西南大学硕士学位论文 本等发达国家十分重视生物信息学的发展，在生物信息数据库建设和生物信息学专业机构的 设立两方面均走在世界前列【6 l 。美国在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 年提供服 务，其它一些国家，如德国、法国、意大利等，在共享网络资源的同时，也分别建立自己的 具有专业特色的二级数据库，为本国的生物学研究提供服务。与此同时，这些国家也相继在 因特网上建立了各自的生软信息学网络节点，如美国的国家生物技术中心，国家基因组资源 中心、英国的欧洲生物信息研究所、日本的国家遗传学研究所等。其中，欧洲分子生物学网 络组织( e u r o p e a i lm o l e c u l 缸b i o l o g yn e t 、o r k ，e m b n e t ) 是目前国际上最大的分子生物信息研 究、开发和服务机构，实现了通过计算机网络使英、德、法、瑞士等国生物信息资源共享的 功能m 。 生物信息学在我国起步较晚，但是发展很快。早在1 9 9 3 年在国家自然科学基金委的资助 下，中国己经开始参与人类基因组计划，但由于条件所限，我国发展生物信息学面临许多制 约因素，其主要问题是认识不够、人才缺乏和信息网络建设落后等。因此，如何提高生物信 息学认识，培养生物信息学人才，构建生物信息网络己成为当前我国生物信息学研究发展中 亟待解决的问题。 在最近发展的十几年中，我国已有多所科研机构和高校加入了研究生物信息学的行列， 相继成立了一些机构，例如：中科院上海生命科学研究院于2 0 0 0 年3 月成立了生物信息学中 心，北京大学于1 9 9 7 年3 月成立了生物信息学中心。此外，一些著名大学和研究所在各自领 域也取得了一定成绩，例如：中科院生物物理所在e s t 序列拼接及在基因组演化方面、天津 大学在d n a 序列的几何学分析方面、清华大学在蛋白质结构模拟方面等等。 2 2 生物信息数据库 2 2 1 生物信息数据库概述 生物信息数据库种类繁多，总体上可分为一级数据库和二级数据库。一级数据库记录实 验结果数据和一些初步的解释，如d n a 序列，由晶体衍射( c q 佟t a l l o 争a p h y ) 获得的蛋白质结构 等。二级数据库是从生物大分子序列、结构、功能数据中提取的有用信息，使它们更便于特 定专业人员的使用，如真核生物启动子序列库e p d 和蛋白质一般结构或功能模体( m o t i 嗷据库 p r o s i t e f 8 1 。 一个生物信息数据库记录一般由两部分组成：原始序列数据和描述这些数据生物学信息 的注释。注释中包含的信息与相应的序列数据同样重要和有应用价值。根据生命科学不同研 究领域的实际需要，对基因组图谱、核酸和蛋白质序歹0 、蛋白质结构以及文献等数据进行分 析、整理、归纳、注释，构建具有特殊意义和专门用途的二次数据库，是数据库开发的有效 途径唧。图2 1 所示为生物信息数据库分类。 6 生物信息平台及序列比对算法 图2 1 生物信息数据库分类图 2 2 2 生物信息数据库发展趋势 生物信息数据库的发展主要体现在以下方面： ( 1 ) 数据库的增长和更新 爆炸性增长是生物信息数据库的重要特征，截止2 0 0 4 年底，仅登录在美国g e i l b a i 】l ( 数 据库中d n a 序列总量已超过4 4 6 亿碱基对，d n a 序列数达4 0 6 0 4 3 1 9 条。 ( 2 ) 数据库的复杂程度增加 除了在数量上的增长，数据库的复杂程度也在不断增加。它包括了大量注释、参考文献 及软件，并通过指针将相关内容链接到其他数据库，在第3 5 版s w i s s p r o t 中注释项涉及 蛋白质的功能、结构域和活性位点、二级结构、四级结构、翻译后修饰、与其他蛋白质的相 似性、相关疾病、序列冲突等。与之交叉引用的数据库增加到2 6 个。数据库结构层次的加深 客观上要求管理的进步，当今面向对象数据库管理方法正在逐步取代旧的模式。 ( 3 ) 数据库使用的高度计算机化和网络化 计算机化和网络化是生物信息学的又一重要特点。e m b n e t ( e u r o p e 锄m o l e c u l a rb i o l o g y n 咖o r k ) 已经连接了2 2 个国家节点和8 个大型生物计算中心。成为最大的生物信息学区域网 络。许多数据库服务器己从工作站升级到大型服务器。软件的进步使数据库实现了更为高效 灵活的管理和使用【1 0 1 。 2 2 3序列数据库 序列数据库是生物信息数据库中最基本的数据库，包括核酸序列数据库、蛋白质序列数 据库和蛋白质结构数据库( p d b ) 三类，以核营酸碱基顺序或氨基酸残基顺序为基本内容，并 附有注释信息1 1 1 。对碱基序列进行测序和编码是生物学研究最重要的工作，生物基因序列数 7 西南大学硕士学位论文 据就是对于某一生物基冈采用某种编码方式编码产生的数据，这些基因数据以数据库的形式 被存放起来，就构成了各种各样的序列数据库。 2 - 3 序列比对算法 2 3 1 序列比对算法概述 在生物学的研究中，序列比对是序列分析和数据库搜索的基础，也是计算机工具运用于 生物学领域最基本的操作，是生物信息学的基础，非常重要。简单序列比对过程如下【1 2 j ： 序列s = a t c g a g c t g g tt = c a t c a a g c g g t 在移位前两序列匹配如下： atcgagctggt iiil catcaagcggt 两序列之间的竖线表示为相同碱基，其中共有4 个相同碱基，也就是在这个匹配位置上， 有4 个碱基对是匹配的。把序列t 向左移动一位以后，两序列匹配如下： atcgagctggt illliii catcaagcggt 移位后有7 个相同碱基，在移位后碱基的匹配数比原来没有移位的时候增加了3 个匹配碱 基，这说明了找到最佳匹配位置的重要性，尽可能找到最大匹配碱基数的对应位置，这样才 能发现最大相似序列。 有的序列比对方法通过对两个或多个字符串序列匹配插入空位来显示来得到序列之间的 最大相似性排列，在插入空位后碱基的匹配数比原来没有空位的时候增加了，这就说明空位 加入的必要性，在序列比对的过程中，有时需要适当的加入空位来增加匹配【1 3 】。 ( 1 ) 字符表 核酸和蛋白质序列可以看成是由字符表中选出的字符组成，字符表为一些字符组成的集 合。比如d n a 序列元素有腺嘌呤、鸟嘌呤、胞嘧啶、胸腺嘭啶，分别简写为a ，g ，c ，t 。 d n a 序列字符表示为： = a ，t ，c ，g ) 同理蛋白质序列字符表为： = a ，c ，d ，e ，f ，g ，h ，i ，k ，l ，m ，n ，p ，q ，r ，s ，t v ，w ，y ( 2 ) 相似性和同源性 8 生物信息平台及序列比对算法 相似性和同源性虽然在某种程度上具有一致性，但它们是完全不同的两个概念。相似性 是一种很直接的数量关系，是指序列比对过程中用来描述序列之间相同或相似d n a 碱基或氨 基酸残基序列所占比例的高低。同源性是指从一些数据中判断出两个基因在进化上曾具有共 同祖先的结论，它是质的判断。 序列的相似性和序列的同源性有一定的关系，一般来说序列间的相似性越高的话，它们 是同源序列的可能性就更高，所以经常可以通过序列的相似性来推测序列是否同源【14 1 。 2 3 2序列比对算法研究现状 目前，进行序列比对的算法很多，这些算法大多是基于运筹学中动态规划【1 5 1 的思想。只 是在其基础对算法进行了不同程度的改进而己。根据同时进行比对的序列个数，序列比对算 法分为双序列比对算法和多序列比对算法。 由于本文主要对双序列比对算法进行改进，因此简要介绍几种双序列比对算法l 坦】。 ( 1 ) 点阵法 点阵法是双序列比对的基本方法，用来寻找序列之间字符的相似性匹配，通常用图示表 示，非常直观。这种方法能以矩阵对角线的形式显示尽可能多的比对。点阵法可以很容易的 发现插n 去除序列和重复序列，这对于其他方法要困难一些。该方法的主要局限在于绝大多数 点阵计算机程序不能显示出精确的序列【1 6 j 。 进行序列比较的一个简单的方法是“矩阵作图法”或“对角线作图”，这种方法是由g i b b s 首 先提出的。点阵法比较两个序列主要的优点是能够找到两序列之间字符所有的匹配。 在点阵法比较两序列时，将要比对的长度不二定相同的序列s 及t 的字符分别沿x 轴和y 轴 排列，一般将较长的序列沿y 轴排列，由此构建一个矩阵。对s 中的每个字符，从第一个开始 与t 中所有的字符进行比对，若两字符相同也即匹配，则在该矩阵对应的位置打一个标记t x ，。 但是对于两长度比较长的序列来说，用x 打标记会有很大的噪声，所以将标记x 替换成点， 连续的点连在一起构成一条直线，点阵图的名字由此而来。 如有以下两个序列：s = i a c g t a c g r at = a c g t a c g t a 用点阵法得出的点阵图如图2 2 中 所示。 9 西南大学硕士学位论文 acgtacgta ax x x cxx gx x txx axxx cxx gxx txx axxx 图2 2 点阵图 在图中可看出打的标记大部分都在对角线上或者在与对角线平行的线上，由此可以得出 结论说这两条序列相似度很高。 两条完全相同的序列在点阵图中表现为一条连续的对角线，如下图2 3 中( a ) 所示；而 对于相似性很高却又不完全相同的序列，如下图2 3 中( b ) 所示表现为不连续的对角线，其 中间断的部分表示在那些区域字符不匹配也有如图2 3 中( c ) 中所示，点阵图中会有一些平 行于主对角线的对角线，其说明两条序列有一定片断的相似，它与主对角线之间的距离体现 了在序列中插入空位的多少。 图2 3 点阵图对角线 ( 2 ) 动态规划算法 动态规划是一种将问题实例分解为更小的、相似的子问题，并存储了子问题的解而避免 计算重复的子问题，以解决最优化问题的算法策略。动态规划的核心，是要将各个最佳子路 径连接起来，最终构成具有最优结果的路径，从而得到比对结果。 动态规划算法是用来比对两个序列的计算机方法。这种方法对于序列分析很重要，因为 该算法能够给出最佳的比对结果。 动态规划算法比较两序列中的每一个字符对并且产生一个比对，这个比对包括匹配和不 匹配的字符对，还有两序列中的空位。动态规划算法为d n a 比对和蛋白质比对提供了一个可 靠的计算方法。该方法已经被数学证明，可以找出序列之间最佳的比对，从而为研究序列相 1 0 生物信息平台及序列比对算法 似性的生物学家提供许多有用的信息。这些信息对于功能、结构和进化预测非常重要。 设计一个动态规划算法，通常可按以下几个步骤进行1 7 l ： ( a ) 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶 段一定要是有序的或者是可排序的即无后向性，否则问题就无法用动态规划求解。 ( b ) 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。 当然，状态的选择要满足无后效性。 ( c ) 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移 有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如 果确定了决策，状态转移方程也就写出来了。但事实上，往往根据相邻两阶段的各状态之间 的关系来确定决策。 ( d ) 写出规划方程( 包括边界条件) ：动态规划的基本方程是规划方程的通用形式化表达 式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划算法在序列比对中有很大的应用，其中序列比对的两个最佳算法：n e e d l e w u n s c h 算法为动态规划在序列比对的全局比对中的应用；s i l l i m w a t e m l 孤算法为动态规划算 法在序列比对的局部比对中的应用。 ( 1 ) n e e d l e m a i l w u n s c h 算法 n e e d l e m 蠲w u n s c h 算法1 9 1 是n e e d l e m 孤和w u n s c h 于1 9 7 0 年提出的一个全局序列比对算 法，是最早的一个序列比对算法，在其后的三十多年中被得到了广泛的应用，成为生物信息 处理中的一个最基本的算法。其基本思想是利用动态规划计算两条序列之间的一个全局最优 比对。 根据动态规划算法的原理，其基本思想可描述为：使用迭代方法计算出两个序列的相似 分值，存于一个得分矩阵中，然后根据这个得分矩阵，通过动态规划的方法回溯寻找最优的 比对序列。 ( 2 ) s i n i m w a t e 册鲫算法 s i t l i t h w a t e n n a n 算法2 0 川是1 9 8 1 年s r n i 廿l 和w a t e n m n 提出的一种用来寻找并比较具有局部 相似性区域的动态规划算法，在识别局部相似性时，具有很高的灵敏度，一直是局部序列比 对算法的基础，后来有许多算法都是基于这一算法开发和改进的。 其算法过程简单描述为： ( a ) 为每一碱基对或残基对赋值。相同或类似的赋予正值，对于不同的或有空位的赋予 负值： ( b ) 用o 对矩阵边缘单元初始化： ( c ) 矩阵中得分值相加，任何小于0 的得分值均用o 代替： ( d ) 通过动态规划的方法，从矩阵中的最大分值单元开始回溯寻找； ( e ) 继续，一直到分值为o 的单元停止，此回溯路径的单元即为最优比对序列。 西南大学硕士学位论文 例如，两个序列a c g c t g 和c a t 舀，使用s r n i t h w a t e m a n 算法进行局部列比对，相同值为2 ，不 同值和插入空位值为1 ，得到图2 4 的得分矩阵，图中加粗字表示回溯路径。 123 4 5 0 cat g t o 孥 一l x 2 3 4 5 la 1 1 、1 o12 天氕 2c2 lo、o12 天 3g3o i净一l2l 戈 4c_ 4 11 il1 1 ll 5t522 1o 、 3 6g6330 r 、 32 t 。_ 图2 4 算法得到的最终得分矩阵 从回溯路径得出三种可能的局部最优比对的结果，如图2 5 所示。 1 - s ：acgct g 一- t ：一c atg “ 2 s ：acgctg 一 t ：一ca tg “ 3 s ：一acgctg + t ：catg t 一 图2 5 算法得到的三种可能的最优比对序列 s m i t l l w a t e 锄锄算法是生物信息学中最重要，也是最基本的算法之一。但是，随着生物数 据的急剧膨胀，s i l l i m w a t e n n a i l 算法的效率越来越不适合当前对生物信息学研究的需求。中科 院计算机技术研究所生物信息学实验室研究发现了该算法的时间效率和如何对数据进行分割 相关，实现了两种s 枷t 1 1 w a t e n n a n 并行算法，并在a m p 机群系统( 曙光3 0 0 0 ) 上实现了其中的并 行算法。 ( 3 ) f a s t a 算法 f a s t a 算法【2 2 2 3 1 是1 9 8 5 年由p e a r s 0 m 和l i p m a n 提出并在1 9 8 8 年做了进一步改进的双序列 比对启发式算法，采用了改进的w i l b u r 和l i p m a n 算法以集中反映具有显著意义的比对结果。其 基本思想是：一个能揭示出真实序列关系的比对至少包含一个两个序列都拥有的字( 片段) ，把 查询序列中的所有字编成h a s h 表，然后在数据库搜索时查询这个表，以检索出可能的匹配， 这样那些命中的字就能很快地被鉴定出来。 1 2 生物信息平台及序列比对算法 其算法过程可简单描述为： ( a ) 根据点阵图逻辑，从比对的所有结构中计算出最佳的对角线： ( b ) 使用字符方法寻找查询字符和测试序列之间的精确匹配； ( c ) 当所有的对角线发现之后，通过增加空位来连接对角线； ( d ) 在最佳对角线区域中计算出比对结果。 f a s t a 对d n a 序列搜索的结果要比蛋白质序列搜索的结果更敏感，因为它对数据库的每 一次搜索都只奄一个最佳的比对，这样对于蛋白质序列而言，一些有意义的比对可能被错过。 虽然f a s t a 所产生的比对结果不是最优的，但是f a s t a 算法的速度要比动态规划算法的速度 快很多。 ( 4 ) b l a s t 算法 b l a s t 算法f 2 4 2 5 1 是由a n s c h u l 等人在1 9 9 0 年提出，采用了一种短片段匹配算法和一种有效 的统计模型来找出目的序列和数据库之间的最佳局部比对效果。它的基本思想是通过产生数 量更少的但质量更好的增强点来提高速度。 其算法过程可简单描述为： ( a ) 从两个序列中找出一些长度相等且可以形成无空位完全匹配的子序列，即序列片段 对； ( b ) 找出两个序列之间所有匹配程度超过一定阀值的序列片段对； ( c ) 将得到的序列片段对根据给定的相似性阀值延伸，得到一定长度的相似性片段，称 为高分值片段对。 1 3 生物信息平台的分析与设计 第3 章生物信息平台的分析与设计 本章所建立的生物信息平台，为第4 章提出的算法搭建出了一个软件的实验环境。本研 究平台主要包括柑橘生物信息二级数据库、数据库管理平台、算法部分以及一些生物工具的 集成。 3 1 生物信息平台总体设计 生物信息平台需要为面向i n t e r n e t 的生物数据一体化存储、数据库的构建、管理、检索 以及信息的网络发布提供较完整的解决方案，涉及到众多的标准规范和相当多的计算机技术， 这是一个较复杂的软硬件系统设计过程。 3 1 1 系统设计原则 生物信息平台是一项系统工程，