（运筹学与控制论专业论文）基于unigene的整合系统.pdf

摘要 基因组时代所关注的主要问题之一是基因功能的研究。然而，高质量的c d n a 序列是进行基因功能研究的基础。近年来，大量实验室获得了较多的c d n a 序列 和e s t 序列。但是，由于这些e s t 序列的质量通常较低，例如含有载体序列、含 有非标准碱基，甚至由于实验原因导致不同基因片段形成嵌合体等，导致基于 e s t 序列的c d n a 序列拼接存在较多的问题。甚至已有数据库中的c d n a 序列也存 在质量较差的情况，尤其是开放阅读框架错位等。因此急需一套优化的方案解抉 该问题，针对此问题，我们提出一套利用测序质量较高的基因组序列进行参考分 析的解决方案，并通过对u n i g e n e 数据库中的部分数据进行测试，确认了该方案 的有效性，为构建高质量全长c d n a 序列数据库以及进一步研究真核基因的可变 剪接形式奠定了重要基础。具体而言，基于l i n u x 操作系统，采用改进b l a s t 算 法将e s t 序列和基因组d n a 序列进行比对，用基因组d n a 序列修饰e s t 序列，隧 后利用p h r a p 软件实现e s t 序列的装配，形成高质量c d n a 数据库。由此可为后 序可变剪接的研究提供高质量的数据源。 关键词：生物信息学；全长c d n a ；表达序列标签( e s t ) ；序列装配；可变剪 接 a b s t r a c t o n eo ft h es u b j e c tm a t t e r sp m dc o s ea t t e n t i o nt oo fe r ao ft h eg e n o n lst h er e s e a r c ho ft h eg e n ef u n c t i o n 1 l o w e v e r ，h i g h q u a l i t yc d n as e q u e n ( isaf o u n d a t i o no fc a r r y i n go ng e n ef u n c t i o nr e s e a r c h i nr e c e n ty e a r c al a r g en u m b e ro fl a b o r a t o r i e sh a v eg o tm o r ec d n as e q u e n c ea n de s ts e q u e n t h o w e v e r ，b e c a u s et h eq u a l i t yo fe s ts e q u e n c ei su s u a l l yr e l a t i v e l yl o v f o re x a m p 】ec o n t a i nc a r r i e rs e q u e n c e ，c o n t a i nn o n s t a n d a r db a s e ，e v ( c o m p o s eg e n e ti cf r a g m e n tg o m p h o s i 8b o d yb e c a u s eo fe x p e r i m e n tr e a s o m t h e yl e a dt ot h ef a c t t h a tm o r eq u e s t i o n se x i s ti nt h es e q u e n c e c o n c a t e n a t i o no fc d n ab a s e do ne s ts e q u e n c e e v e ni ta l r e a d yh a v ec d l s e q u e n c ei nd a t a b a s e st h a tt h es i t u a t i o ni n f e r i o ri oq u a l i t ye x i s t st o ( e s p e c i a l l yo p e nt or e a df r a m em i s p l a c e s on e e das e to fs c h e m e so p t i m i z e h a d l yt os 0 1 v et h i sp r o b l e m ，i no r d e rt os o l v et h i sq u e s t i o n ，w ep c f o r w a r donei sb a s e d0 1 3h i g hq u a l i t yg e n o m es e q u e n c e st or e v i s ee s t s e q u e n c e s ，a n dc o n f i r m e dt h ev a l i d i t yo f t h i ss c h e m eb yt e s t i n gu n i g e t d a t a b a s e ind e t a i l s ，w ec o m p a r ee s ts e q u e n c e sw i t h g e n o m es e q u e n c e si r e v i s i o nb l a s to nl i n u xo p e r a t i n gs y s t e m t og e th i g hq u a i t yc d n a d a t a b a s e ，p h r a ps h o u l db eu s e dt oa s s e m b l ye s ts e q u e n c e s i tp r o v i d eh i q u a l i t yr e s o u r e sf o rr e s e a r c ho fa l t e r n a t i v e l ys p l i c e k e yw o r d ：b i o i n f o r m a t i c s ，c o m p l e m e n t a r yd n a ，e x p r e s s e ds e q u e n c et a g ( e s s e q u e n c ea s s e m b l y ，a l t e r n a t i v e l ys p l i c e i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 北京工业大学或其它教育机构的学位或证书而使用过的材料与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意 签名：李砉孝 日期：，芝幺z 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文 ( 保密的论文在解密后应遵守此规定) 签名：李未孚 导师签名：躯萎基日期：旦竺，：兰 弟1 荦绪诧 第1 章绪论 11 概述 随着生物科学技术的不断发展，研究数据迅速积累。获取，储存，处理和 分析生物学及相关信息的方法与工具亟待更新。近年来开展的各种基冈组计划， 列数抛的分析与利用提出了更高的要求，生物信息学应运而生。 ，卜物信息学是在数学、计算机科学和生命科学的基础上形成的一门新型交 叉学科，它是指为理解各种数据的生物学意义，运用数学、计算机科学与生物 学手段进行生物信息的收集、加工储存、传播、分析与解析的科学。最近几年 随着快速序列的测定、綦因重组、多维核磁共振等技术的应用，生物学实验数 圳挚爆炸趋势增长，随之计算机和国际互联网络的发展使得对大规模数据的贮 存、处理和传输成为可能。同时生物信息学作为1 0 新的学科领域，它是将基 吲组d n a 序列信息分析作为源头，在获得了蛋白质编码区的信息之后进行蛋白 质空间结构模拟和预测，然后依据特定蛋白质的功能进行必要的药物设计。它 由相依赖、相互渗透的两个研究领域组成，即构筑现代生物学所必需的信息 基础研究，以及旨在解析基本生物学问题的基于计算机技术的基础生物学研究。 闪此，在基冈组研究时代，基因组信息学、蛋白质的结构模拟药物设计必将有 机的结合在一起，它们是生物信息学的三个重要组成部分。 牛物信息学更多的具备研究领域的特征，而非一套完整的科学撅念和原理， 【) ；= | 而其有独特的开放性和应用途径的多样性等特征。作为建立于应用数学、计 算机科学、生物学、物理学、化学等多学科相结合基础之l 的生物信息学，无 疑具有峰实的理论基础和广泛的应用前景。 1 1 1 生物信息学的国内外现状 一十世纪是z t 命科学的世纪，其里程碑就是人类基因组计划( 1 u m a n g e n o m icp 2 1 0 j e e r ，l q g p ) 的完成。它的完成为揭示人体构造之迷奠定1 秘实的数 据慕础； m 彭用人类基因组计划和生物科学迅猛发展的要求丽迅速兴起的生物 信息学则历史性的成为本世纪生命科学浪潮中的热门学科。 通俗来讲，基因组是由四种刁i 同的脱氧核苷酸( a 、t 、c 和g ) 按照特定的 编码规则串成的脱氧核耕核营酸串( d n a ) ，其中蕴藏着生物体所有的结构信息 北京i 业a 掌理学坝1 。学位论义 和控 , i ；u y a 息，因此基因组可以说就是生物体内的控制中心，其中的功能单程 呵以转录为核糖核苛酸序列( r k a ) ，有的就以r n a 的形式发挥生物功能。有睁 则进一步被翻译成为各种蛋白质而行使生物体构建和生命调控功能。凼此，击 凶组是本完整地讲述人体构造和运转情况的指南，有了它，就可以揭开有多 人体7 二长、发育、寝老、患病和死亡：的秘密，因而危害人类健壤的几千多种蓝 传病以及弓遗传密切相关的癌症、高血压、糖尿病和精神病等，就都可以得至 诊断和治疗。 人类基因组- i , i 戈0 测出人类基因组的全部脱氧核苷酸序列，其中编码有约1 ，j 多个蚩门质基网，从而弄清楚其中所有功能单位的组织结构形式以及调节书 制，相应的绘制成甑观图谱，再深入的工作就是弄清楚基因组所编码的所有i 向质的表达情况，最终达到从整体系统水平上认识人体构造与功能并帮助制i 有效治疗策略和开发有效治疗药物的目的。除此之外，还要对其它几个属于j 闻生物进化剃的模式生物的基冈组进行测序，如酵母、果蝇、蠕虫和小鼠等， 利川这些模式生物可以进行很多在人体内不可能进行的实验研究，是我们了 人类基圳组功能的重要工具。所有这些工作都涉及到大量数掘的处理工作，h 1 1 数据量也在以科学史上阿所未有的高速度增长着。所有这些 青况表明，z 枷 学已不冉是仪仅急于试验观察的科学，仪靠传统的研究手段是无济于事的， 论和计算将越来越来越发挥巨大作用，数学、物理、计算机科学将r 益渗透j 生物学研究中柬，海量的数据必须通过生物信息学的手段进行收集、分析和! 瑚后，才能成为有用的信息和知识，才能再加以传播应用。也就是说，只有f 过尘物信息学手段的分析处理，我们才能获得对基因组的j f 确理解，因此可【 说生物信息学必盛于人类基阏组计划，因为人类基因组计划首次为生物信息： 创造了施胜身手的巨大空间。当然，生物信息学并不局限_ 丁人类基凶组：i 二程， 它已经深入到生命科学的方方面面。 幽外直非常重视生物信息学的发展，各种专业研究机构和公司如雨后； 笋般涌现i i 米，生物科技公司和制药工业内部的生物信息部门的数量也在与 俱增。仍 如i i 对生物信息学的需求是如此迅猛，即使是美国这样的发达嗣家 而i | f i 着供小应求、人才匮乏的局面。近柬，英国鉴于国内列。生物信息学t f 业 jtl 盏迫切的需求，所确主要的研究资助机构( 如生物技术和生物科学研究一 2 弟l 荤绪论 1 n i i f i 葺i i 审i i i i i i i i i i i i i i i i i i i i i i i i 葺i i i i i i i i 鼍嗣皇i i 嗣i i 墨葺i i i 员会、工程学和物理科学研究院委员会等) 达成共识，而且已经实现了对生物 信息学人翻培养的大力资助。事实i ：，欧美等发达国家在生物信息学方面已有 较长时删的积鬃。 h 内对，卜物信息学领域也越来越重视，在一砦著名院士和教授的带领下， 在各自领域都取得了、。定成绩，有的在酱际t 还占有一。席之地，如北京大学在 生物信息学网站建设方面、天津大学在d n a 序列的几何分析方面、中科院理论 物理所等等；北京大学于1 9 9 7 年3 月成立了生物信息学中心，中科院上海生命 科学研究院也予2 0 0 0 年成立了生物信息学中心，分别绦护着国内两个专业水平 相对较高的生物信息学网站，但从全国总体上来看与圈际水平差距很大。 1 2 人类基因组计划( h 6 p ) 1 9 9 0 年启动的“人类基因组计划( h u m a ng e n o m i cp r o j e c t ，h g p ) ”旨 往阐明人类基凶组3 0 亿个碱基对的序列，发现所有人类基凶并搞清其在染色体 上的饪簧，破译人类全都遗传信息，使人类第。次在分子水平上全而地认识自 我。该计划从最初的美国政府资助美国科学家开展d n a 测序，到多国科学家， 政府的主动参与以及私人企业的竞相投入，已经经历了l o 多年的历程，在这短 觚的1 0 多年的时间罩，不但提前完成了整个人类基因组的全部测序，同时还完 成了许多模式生物的全基因组测序。它的完成改变了生物学和医学在2 1 世纪或 更远时间内将要发展的方式。全基因组序列的出现对于生物学研究方法而言无 疑是开拓了一- 个崭新的途径在基因组的规模上阐明d n a 序列的功能，即功 能基凶组学。已经证明，耩因组的许多基因和其它功能因子只有在生物的全长 e d n a 序列完拿知晓时才能够被发现。随着序列数据的积累，这样的发展也正在 加速。然而，了解一个基因或其它因子的结构仪仪是答案的一部分，下步是 阐明攮例组和其环境相互作用而产生的功能。在基因组水平卜- 研究d n a 的功能 包括通过序列模型的比较和分析而直接推断功能，大规模的分析m r n a 和基因的 蛋白质产物，破坏基因的各神途径等。阐明基因组的功能将需要建立新的策略 库，丌发在大规模水平上应有的技术，利用基因转录和蛋自质产物的大规模定 性加强功能分析。因此，对一套表现所有的人类基因的全长e d n a 的签定和测序 将是第一位的，这就需要丌发e d n a 资源，当然也包括其它物种的c d n a 资源。 尤其研究人类基因的表达，需要更多的c d n a 序列和c d n a 痒。 3 北京工业大学理学硕1 学位论文 1 3c d n a 文库与表达序列标签( e s t ) c d n a ( c o m p l e m e n t a r yd n a ，互补d n a ) 是指与r n a 序列互补的d n a ，由 r n a 启动的d n a 多聚酶( r n a d e p e n d e n td n ap o l y m e r a s e ) 或反转录( r e v e r s t r a n s c r i p t a s e ) 合成。这种酶的单链d n a 产物( 反转录物) ，可用d n a 启动自 d n a 多聚酶转换成双链形式，并插入合适的载体成为一个c d n a 克隆。c d n a 克 是成熟m r n a 分子的拷贝，不含任何内含子序列，因而只要与克隆载体上合适自 启动子序列相连接，就很容易在任何一种生物体内表达。 一个c d n a 文库( c d n al i b r a r y ) 中包含多个c d n a 克隆，可用于后续的f 列分析。例如，可以从一个具有2 0 0 0 0 0 0 个克隆的文库中随机选取1 0 0 0 0 个 品并进行测序，结果则贮存在计算机数据库中供进一步的序列分析。 表达序列标签( e x p r e s s e ds e q u e n c et a g ，e s t ) 是从c d n a 文库中产生的一 些很短的序列( 3 0 0 5 0 0 b p ) 。它们代表在特定组织或发育阶段表达的基因，1 时可代表特定的c d n a 。e s t 可能是编码的，也可能不是，而两端有重叠序列 e s t 可以组装成全长的c d n a 序列。因此，e s t 的研究与表达分析可以作为一l 发现新基因的有效方法。事实上，该方法己在人类基因组图谱绘制新基因克9 和基因组序列编码区的确定等方面发挥了极为重要的作用( a t t w o o d 和 p a r r y s m i t h ，1 9 9 9 ：r a s h i d i 和b u e h l e r ，2 0 0 0 ：h a t e ye ta 1 ，1 9 9 8 ) 。图1 2 ； 出了l e s t 与c d n a 以及c d s 和u t r 之间的关系。 e s t c d s u t r 图卜1 c d n ae s tc d s 和u t r 的关系 4 第1 苹绪论 值得一提的是，虽然全长c d n a 序列分析十分重要，但我们并非总能获得全 长序列的信息。事实上，现阶段基因数据库中收录的d n a 序列数据绝大许多都 不是全长序列，而是短片段e s t 序列。 1 4 数据库 1 4 1e s t 数据库 鉴于e s t 在基因研究和商业开发上的重要应用价值，人们已经建立了大量的 e s t 数据库到目前为止，主要的通用公共数据库包括e m b l 数据中的e s t 部分以 及g e n b a n k 中的d b e s t 。通过下面3 个例子，可以初步了解e s t 数据的不同来源。 m e r c k u n i v e r s i t yo fw a s h i n g t o n1 9 9 4 年，m e r c k 公司资助美国华盛顿大学 丌展有关从多种规范化c d n a 文库中测定e s t 序列的研究项目。表卜2 示出了 大部分规范化文库中获得的e s t 的例子。 表卜l m e r c k 华盛顿人学e s t 项目的部分例子 库来源组织号码库来源组织号码 3 0 a r e s 胎盘 n b 2 h pb o a r e s 成人脑 n 2 b 4 h b 5 5 y b o a r e s 视网膜 n 2 b 4 h s t r a t a g e n e角膜基质 9 3 7 2 2 2 s t r a t a g e n e肝 # 9 3 7 2 2 4 s t r a t a g e n e结肠 # 9 3 7 2 0 4 s t r a t a g e n e胰腺 9 3 7 2 0 8 s t r a t a g e n e内皮细胞 9 3 7 2 2 3 s t r a t a g e n e肺癌 9 3 7 2 1 8s o a r e s 黑素细胞 2 n b h m b o a r e s 胚胎b 细胞 n b h t g b cs o a r e s 松果腺 n 3 h p g i n c y t e i n c y t e 制药公司建立了一个数据库l i f e s e q ，重点是通过从标 准c d n a 文库测序获得定量数据。其目标在于提供健康和疾病组织中转录基因相 对拷贝数的信息，以期发现潜在的治疗靶标。 t i g r h g i美国基因组研究所( t h ei n s t i t u t ef o rg e n o m i cr e s e a r c h ，t i g r ) 是一个非盈利的研究机构，成立于1 9 9 2 年。其人类基因索引( h u m a ng e n ei n d e x ， h g i ) 旨在综合全球人类基因研究的成果( 包括d b e s t 及g e n b a n k ) 。具体情况 可见“t i g rg e n ei n d i c e s ”网页。 5 北京t 业入学理学硕士学位论文 1 42 电子克隆 电子克隆又称为虚拟克隆( v i r t u a lc l o n i n g ) 。其原理是根据大量e s t 乒 有相互重叠的性质，通过计算机算法获得e d n a 全长序列，换言之，电子克隆： 采用传统的分子生物学实验方法，而是由一个查询序列开始，依靠e s t 数据 在计算机上对e s t 进行两端延伸，从而获得全长的c d n a 序列。 从部分序列得到全长e d n a 的分子生物学实验方法通常有杂交筛选文库亘 5 末端延伸法，电子克隆则以部分e d n a 为起始，和g e n b a n k 的e s t 数据库d b e ! 进行b i 。a s t 检索，得到与5 端或3 端有相似序列的e s t ，然后以该e s t 为模枥 进一步搜索e s t 数据库，一直往前延伸，直到找到终止密码子，得到全长c d n i 由此可见，该方法依赖于足够的末端重叠并且能够往前延伸的e s t 序列。 1 5 背景及意义 现在，遍布全世界的测序仪每天都在产生着海量的d n a 序列数据，使得； 堋组棚关数据望指数方式增长，大约每几个月就增加一倍。面对海量的、芏： 数形式快速增长的基因组相关数据，必须抓好两个重点，即一一方面必须发展7 新的，j 二物信息处理方法，另方而必须建立适于超大规模数据的信息处理系舒 这是从海肇生物信息数据中获得新的生物体结构、功能知识的关键，也是基l 纰研究取得成果的决定性步骤。因此，沿着”实验d a t a 对实验d a t a ”的思路， 利用超级计算机进行e s i 、和全基因组序列比对( a 1 i g n m e n t ) 是很有必要的， 将会耿得重要的成果。 e s t 序列( e x p r e s s e ds e q u e n c et a g s ) 是基因表达的短c d n a 序列，它一 携带着完整基因的某些片段的信息。现在国际上公共数据库( 如n c b i 的d b e s u n i g e n e ) 中的人类e s t 序列已达四百多万条，已覆盖了人类基因的9 0 i 上，冗余度己达到1 0 倍左右。利用这些已知序列数据，通过大规模计算分析 得到全长e d n a 序列已成了寻找新基因的一种高效且可靠的手段。 目前，大多数e d n a 的数据都已经可以从各种公开的数据库中获得，但是 中有许多还不是完整的e d n a ，而只是e d n a 片段。另外，这些数据仍然存在j 许多缺陷，例如有些数据没有进行正确的分类，来源于不同数据库的数据之 可能存在不一致的地方等等。e d n a 数据的这些缺陷阻碍了它们在研究中的实 6 第1 荦绪论 应用。因此，科学家们一直希望能够将所有收集到的人类e d n a 序列加以整理， 并收录到同一个数据库中，这样，科研人员的工作就可以更加规范和准确了。 相关文献报道：研究者们在相关数据库中收集了一些e d n a 数据，对其进行 基因作图，并将它们逐个标记在人类基因组中不同的区域内。发现，在相同区 域内可能会出现许多不同的e d n a 的重叠。对这一现象的深入探讨也许还将揭丌 人类基因组的其中一个奥秘数目如此少的基因如何才能够制造出人类发展 过程中如此众多的具有各种各样功能的蛋白质，同时，又如何才能产生出如此 复杂的由人类遗传因素所决定的性状差异。目前科学家们对这一现象的解释是， 同一个基因可能会出现不同的剪接方式，因而同一段基因序列可能会转录成不 同的m r n a ，由此我们可以看到许多存在细微差异的各种e d n a 覆盖在同一基因 区域的现象。研究者们指出他们已经发现了许多类似的例子。事实的确如此， 通过分析本实验室有关h e t r i n 的实验结果就很好的证明了这一点，详细结果 在本文的后面一章中提到。在此不予赘述。 通过上面的分析，我们知道建立一套标准化的e d n a 库是势在必行，而且具 有非常重要的生物学意义。 1 6 本文的研究内容 本文主要包括三个部分： 第一部分介绍了生物信息学的发展及其研究方向以及其它概况。重点阐述 了什么是e s t 序列，它于e d n a 文库的关系，以及e s t 序列的相关数据库。最后 【 2 - 明研究e s t 序列构建e d n a 库的背景和意义。 第二部分主要介绍序列分析中用于序列比对的相似性搜索。详细的介绍全 局比对和局部比对的相关理论基础以及其搜索策略，事实上局部比对相全局比 对更能揭示生物学意义。然后给出局部比对的b l a s t 搜索结果。 第三部分主要介绍构建e d n a 库的过程，其间利用基于改进b l a s t 算法柬实 现e s t 序列在基因组水平上的修正。通过序列拼接得到高质量的e d n a 序列，最 后对所形成得序列进行生物学上可变剪接得研究。从而更进一步得揭示蛋白质 得多样性。 7 本章小结： 近年来开展的各种基因组计划，对数据的分析和利用提出了更高的要求， 生物信息学应运而生。随着计算机的飞速发展，生物信息学自身经历几一 发展阶段，闩趋变得完善。 d n a 序列分析是解析基因组信息和发现新基因的基础，其核心内容是全七 c d n a 文库的构建和表达序列标签的检索与分析。介绍了目前国际上现有 e s t d n a 数据库，以及e s t 与e d n a 序列之间的相互关系，从而为构建标 化e d n a 库奠定了坚实的基础。 每天都能产生大量的e s t 序列，但其本身有时不能给出人们所需的完整 息，同时也存在测序质量及其它的一些问题，因此，有必要处理并分析i 些e s t 序列，从中提取练有价值，有意义的生物学知识。 8 第2 章相似性搜索算法 第2 章相似性搜索算法 在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有 力的研究手段，生物学领域中绝大部分的问题在计算机科学领域中主要体现为序 列或字符串的问题。而序列分析的首要问题就是要进行序列比对，从丽找出与未 知数据相类似的已知数据，以便从中推断出未知数据的某些性质。 2 1 数据比对 对于一个新测定的序列，我们无法得知用什么序列同它进行比对。数据库相 似性搜索使我, f f 能够从数据库中存在的数十万个序列中挑选出可能与感兴趣的 序列相关联的序列，这个方法有时会导致意想不到的收获。在数据库搜索中，基 本操作就是将查询序列和数据库中的主题序列作比对。但是如今的序列数据库非 常之大，并且正以指数速度不断增长，在这种条件下，一些传统的最佳方法不可 行时，我们必须求助于那些启发式方法。有一种常用的启发式方法建立在将序列 分解成由连续字母组成的短串( 称为字) 的策略之上。这种基于字的方法，己广 泛应使用于今天的公共搜索程序之中。其基本的思想：一个能够揭示出真实的序 列关系的比对至少包含一个两个序列都拥有的字，把查询序列中的字编成索引， 然后在数据库扫描中查询这些索引，这些命中的字就会很快被鉴定出来。b l a s t 是号为序列相似性搜索设计的，如对一个咨询序列鉴定它的同源物。序列数据可 以用b l a s t 相互比较。这个算法试图达到的目的是找到高度匹配的片段比对，即 能够无缺口的比对且达到定的得分值的成对的序列。同时它也是一种启发式搜 索算法，包括b l a s t p ，b l a s t n ，b l a s t x ，t b l a s t n 和t b l a s t x 程序，五种b l a s t 程序执行如下任务： 1 ) b l a s t p 对一个蛋白质序列数据库比较一个氨基酸咨询序列； 2 ) b l a s t n 对一个核苷酸序列数据库比较一个核苷酸咨询序列； 3 ) b l a s t x 对一个蛋白质序列数据库比较一个核苷酸咨询序列的六个框架 的概念性产物： 4 ) t b l a s t n 对一个核苷酸序列数据库的所有六个框架动力学翻译比较一个 氨基酸咨询序列； 5 ) t b l a s t x 对一个核苷酸序列数据库的六个框架的翻译比较一个核苷酸咨 询序列六个框架的翻译。 9 2 2 相似眭搜索的理论基础 2 2 1 全局搜索算法 定义1 ：两个任意的字符x 和y ，万( x ，y ) 表示x 和y 比较时的分值。 占( x ，x ) = 2 ，6 ( x ，y ) = 占( x ，一) = j ( 一，y ) = 一1 定义2 ：s = s ，晶和t = z ，其全局联配a 可以用序列s 和t 表示，其中： ( 1 ) s l = t 1 ： ( 2 ) 将s 和t 中的空字符除去后所得到的序列分别为s 和t ： 联配a 的分值s c o r e 为：s c o r e = 8 ( s 【f 】，t - 邝 i = 1 主要步骤： 1 计算出两个序列的相似分值，存在于一个矩阵中。 2 根据此矩阵按照动态规划的方法寻找最优的联配序列。 前提条件： v ( o ，o ) = o v ( i ，o ) = v ( i 一1 ，o ) + j ( s f ，一) 实例 v ( o ，j ) = v ( 0 ，j 一1 ) + j ( 丁 】，一) 递规关系： 矿( f l ，j 一1 ) + 8 ( s q ，r 力) v ( i ，j ) = y ( f 一1 ，j ) + 占( s f 】，一) l矿( f ，一1 ) + 占( 一，r ， ) 3 得到相似度矩阵后，通过动态规划回溯的方法可获得序列的最影 配序列 s = “acgc tg ”和t = “ca tg t ” 8 ( x ，x ) = 2 8 ( x ，y ) = 8 ( x ，一) = 占( 一，y ) = 一1 计算相似度矩阵可得： l o j 弋 o12345 cat g t o0 一。1一245 天 1ai l110一12 人气 2c2 1 od12 一人气 3 g 一3b、1l 气 十十 4c一41_ 11、1 人人 5t一522、103 人 十 6 g 一630 j i 一 运”动态规划中回溯得方法就可以得到三种可能的最优联配序列 ls ：acgct g t ：一c at g t 2s t 3s t c g ct g 一 catgt ac gc t g at g - 一t - 。 2 ，2 2 局部比对算法 基本的胤部比对搜索丁具是一种普遍的搜索序列同源性的方法。前面介绍了 伞岗l - l ：x , t j ! t 4 js m it h w a t e r m a n 算法，但是对于实际情况而言，我们也需要序列的 肠部比对，毕竟有的序列在一些局部区域具有很高的相似性，例如，两条d n a 序列n j 能只z f - l p 4 的区域内( 密码区) 存在关系：不同家族的蛋自质往往具有功 能和结构上的干目同的4 燎区域：寻求局部比刈有时可能会发现若干个重要的比 对。这些都说明在生物学上局部比对比全局比对更有实际的意义。 前提条件： v ( i 0 ) = 0 v ( 0 j ) 2 0 递归条件 v ( i j ) = o y ( i - 1 ，j ，- t ) 、+ 5 。( ，s 1 、，飞如 其中的记分函数j ( x ，_ y ) 而 g ( i 一1 ，j ) + j ( s 【f 】，一) 。7 v ( i ，j 一1 ) + 艿( 一，? 、【，】) 找出i + 和，+ ，使得满足： v ( f ，) _ m a xy ( f ，j ) 1 9 s n 1 sj s ” 从这罩可以看到对全局比对稍作修改就可以得到局部的最优比对算法。这种h 的路径不需要达到搜索图的尽头，只要在内部开始和结束。如果某种比对的手 值不会因为增加或减少比对的数量而增加时，这种比对就是最佳的。这个过乖 赖j i 打分系统的矩阵，就是说，某种路径的打分会在不匹配的序列段位嚣减一 当分值降为零时，路径的延展将会终l ：，一个新的路径就会应运而生。这样， 们会得到许多独建，的路径，它们以不匹配的序列段为赛限，丽不是缘在全程e 。州以序列的结尾作为界限。在这些路径。h 拥有最高分的一个就是最佳的局自 对。 实例：s = “a b c x d e x ”t = “x x x c d e ” 记分函数5 ( x ，y ) ： 5 ( x ，x ) = 2 ，5 ( x ，y ) = 5 ( x ，一) = j ( 一，y ) = 一1 计算得到的相似度矩阵： x 0l2j456 xx xcde ooooo0oo la o oo o000 2b0 0 o o00o 1 3co o 0 o y 1o 4x0222 一1k lo 5d0 1 l 11、32 i 6e 00ooo25 7xo222114 1 2 第2 章相似性搜索算法 通过 ：嘶的矩阵 _ 以得到s 和t 的最佳局部比对为： cxde cde 或者 x d e xcde 2 2 3 空位处罚 为了补偿那些插入或缺失，可以在比对中引入一些空位，但不能太多，否则， 会使的分子变得面目全非。每引入一个空位，比对的分值都会有所扣除，对于这 些窄位都有许多罚分的规则，常见的有2 种：1 ) 空位权值恒定模型，2 ) 仿射空 位处罚模型。 空位权值恒定模型：规定在每个空位的空格的分值为零，即： a ( x ，一) = a ( - ，y ) = 0 l 则比对序列的分值为：a ( s 【f ，r f 】) + 睨4 ( # g a p s ) i = l 其1 1 岷为丌放一个空位的罚分。 仿射空位处罚模型：用一个附加的罚分比例去乘空位的长度畋十g + 暇 则比对序列的分值为：a ( s 【f ，t _ + 4 ( # g a p s ) + 形+ ( # s p a c e ) i = l 般最常用的始仿射空位处罚模型，这里有两个参数w 和瞰，但在选择空位参 数时，在很大程度上是唯经验的，所选的分值很少会有理论上的支持。通常，对 于以会选择相对的低分( 大约1 2 ) ，而对于畋会选择一个高的分( 大约1 0 1 5 ) 计算打分矩阵： 初始条件： v ( 0 ，0 ) = 0 v ( i ，o ) 2 e ( i ，o ) 2 + i 哌 v ( o ，j ) 2 f ( o ，j ) 2 以+ j 岷 递归条件： v ( i ，j ) = m a x g ( i ，j ) ，e ( i ，j ) ，f ( i ，j ) ) ： 13 6 ( i ，j ) = v ( i _ 1 ，j 一1 ) + 艿( s i ，t j ) ： e ( i ，j ) = m a x e ( i ，j - 1 ) + w s ，v ( i ，j 1 ) + w g + w s f ( i ，j ) = m a x f ( i1 ，j ) + w s ，v ( i 一1 ，j ) + w g + w s j 2 3 b l a s t 搜索策略 b l a s t 所采用的相似性搜索方法首先搜索咨询序列和一个数据库序列之间 相似性片段，然后评估所发现的每一个匹配的统计学显著性，最后报告满足由 用者确定的显著性闽值的那些匹配。包括咨询序列和一个数据库序列的多重的 得分匹配片断的发现，可以通过许多不同方法进行统计学处理，程序的缺省方 采用“s u m ”统计学。因而由一套高得分匹配片段得到的统计学上的生物显著1 可能比该套高得分匹配片段的任何一个成员都要高，只有当所得的显著性满足 用者所选择的闽值时，匹配才报告给使用者。发现高得分匹配片段的工作由鉴 咨询序列中的长为w 的短片段开始，当对一个相同长度的数据库序列中的一个 段进行排列时，该咨询序列满足某些正数的阂值得分v 。v 是邻近的得分值，： 些最初的邻近的片段被用作开始的搜索的种子，由此发现包含它们的更长的高 分匹配片段。种子沿着每一个序列的两个方向进行延伸，以增加累积的排列得多 在每一个方向上种子序列的延伸在以下条件下停止：l ，累积的排列得分超出 由最大完成值所得到的数量x ；2 由于一个或更多的负数得分的残基 排列，累积得分趋向于0 或更低；3 到达了任一个序列的终点。 2 4b l a s t 搜索结果 1 4 本章小结 本章主要介绍了序列比对中常用的几种算法，即全局比对和局部比对算法。 以及这两种算法的理论基础和它们之间的关系。 在生物学上，局部比对似乎更常用些，详细介绍了b l a s t 相似性搜索的搜索 策略和在实现过程中涉及到的打分矩阵，了解其打分矩阵有助于更好的理解 局部比对的思想。从而揭示生物学界物种之间的同源性。 1 5 北京：i = 业大学理学碗j + 掌位论文 第3 章基于u n ig e n e 的c d n a 库的构建 3 1u n i g e n es y s t e m 的介绍 u n i g e n e 是从属于o e n e b a n k 的一部分，专门收集非冗余性的基因来源的 c l u s t e r s 数据。每一个u n i o e n ec l u s t e r 包含代表单一基因的序列和相关的作 息，例如基因表达的组织类型和图谱定位信息。 除了这些具有特征的序列以外，成千上万的e s t 也被收录在内。因此，车| 应的，这些收集的资源可以作为基因发现的来源。现在，许多实验室研究人点 已经利用u n i g e n e 进行大规模的基因表达图谱分析，并且所有这些序列并没笮 被用束尝试产生c o n t i g s 或c o n s e n s u s 。这旱存在的些原因解释为什么同属 于某一基因的序列不用来产生一个单一的c o n t i g 。 1 所有属于同一基因的剪切变异被放在同一聚类中。 2 束从同一c d n a 克隆的e s t 序列，通常都有5 和3 端的序列，但这生 序列并不都具有重叠部分。 当前，u n i o e n e 已收录了h u m a n 、r a t 、m o u s e 和c o w 、z e b r a f i s h 的序列。 选择这些物种是因为他们有大量的e s t 可用数据，其它物种的序列将在今后院 续被加入。u n i o e n e 的网络化界面下图所示： 1 6 311u n i g e n eb u jdp r o c e d u r e 聚类是一个发现同属于个大类中的小的亚序列的过程，可通过转换离散 相似值为序列之间的布尔数学体系联系。也就是说，如果序列间的相似性超过 某一阏值，则认为他们具有相关性。u n i g e n ec l u s t e r i n g 对于这种相关性分析 提供更多的生物学意义上的考虑，聚类过程大致如下： 1 对载体中的载体、寡核苷酸、重复片段以及线粒体、核糖体等污染序列 进行过滤。去除污染序列之后的序列至少要含有i o o b p 的带有信息的序 列才可作为候选序列。 2 g e n e n k s 从属于同一基因的序列( 包括m r n ao rg e n o m es e q u e n c e s ，完整的c d s ) 彼此问要进行比较，足够相似的序列被放在一起，形成初始 c 1 u s t e r s 。 3 e s tt oo e n e1 i n k sa n de s tt oe s t 通过m e g a b l a s t ，e s t 与属于同一基因的序列进行比较，足够相似的 序列被加入到这些c l u s t e r s 。如果某一序列，表现为可同时放在2 个 不同的c l u s t e r s ，但不能把2 个c l u s t e r s 联成一个d u s t e r ，这样的 序列必须被剔除。另外，如果在c l u s t e r s 有2 个以上的带有37 末端 标记e s t 或在c l u s t e r s 中没有带有p o l y ( a ) 信号的序列，这样的 c l u s t e r s 必须被抛弃。经过这些标准筛选得到的c l u s t e r s ，称为锚定 c l u s t e r s 。因为这些c l u s t e r s 具有3 末端序列，并被假定为已知的。 4 根据克隆信息设定c l u s t e r 的边界。 这样可以确保如果同属于一个c l u s t e r 的5 末端和3 末端e s t s 即 使中间没有重叠的片段将它们联系起来，也能认定它们属于同 c l u s t e r 。如果在一个c l u s t e r 中有两个3 末端e s t s ，那么就可在相 同的克隆中找到两个5 末端e s t ，并将其放到同一个c l u s t e r 中。并 且可以提供c l u s t e r s 之间合并的信息。 由于新的序列数据的加入和每星期的不断更新，因此在u n i g e n e 中的 r e s u l t i n gc l u s t e r 每星期也随之重新整理，不断更新。c l u s t e r s 之间会发生 1 7 融合，因此使用c l u s t e r 的i d 作为标识，是不明智之举，最好利用g b8 c c e s s i o n u m b e r s 比较安全。层前，在u n i g e n e 中包括4 8 ，0 0 0c l u s t e r s ，c l u s t e r sj 部分依据e s t 序列形成，每一个c l u s t e r 代表一个h u m a ng e n e 的转录子，兰 前估计人类基因组约有8 0 ，0 0 0 到i 0 0 ，0 0 0 基因。利用u n i g e n ec l u s t e r s 的一 个重要的目的是识别新的，非冗余的候选b 表达图谱，为产生一个转录子图 一识别基因组所有的编码序列。 3 2 建库过程 3 2 1 基本思路： 建库的过程是基于u n i g e n e 的基础上，对其中的e s t 序列进行校正、拼 以取的较长的c d n a 序列，从而构建一套标准化的c d n a 库。为了实现上述目标 设计如下方案，方案大体流程如下图所示： 三大核酸数据库 ( d d b j