（运筹学与控制论专业论文）基于动态规划进行双序列全局比对研究.pdf

摘要 序列比对分析是生物信息学研究中的一个基本内容。大多数序列比对软件以 动态规划算法作为其空位插入的核心算法。然而，一个普遍的问题是目前常用的 大部分序列比对算法虽能达到最优或近似最优的结果，但却均由于计算复杂度所 导致的计算速度缓慢这一瓶颈而在应用上受到限制。虽然近年来由于算法自身的 不断改进以及计算机科学的发展，其实现程序依靠计算机硬件和软件开发技术的 提高得到了效率和精度上的改善，从而使现在应用广泛的序列比对或数据库搜索 程序如b i a s t 、f a s t a 、c l u s t a l w 等才获得了相对满意的计算效率，但是从理论基 础和思想原理上改善序列比对算法以期降低计算复杂度，才是提高计算效率和精 度的根本途径。目前随着各种基因组测序计划陆续完成，大量序列数据急剧增长， 以序列比对为核心的数据分析任务对于高效率的序列比对算法的需求目益迫切。 基于段与段比对的概念，我们设计了一个用于核酸序列全局比对的新算法 s a m i d p ( s e q u e n c ea l i g 啪e m b a s e do n m u l t i p l es t a g e i n t e l l i g e n td y n a n l i c p r o g r 啪m i n ga l g o r i m m ) ，将多阶段动态规划决策算法用于两两序列比对并用 v i s u a l b a s i c 编程实现，结果发现该新算法在将计算复杂度减小到d r m 的同时， 也能够获得较为理想的计算精度，预期将在序列全局比对中起重要作用。 关键词核酸序列，序列全局比对，空位插入，计算复杂度，多阶段动态规划 算法 j ! 要三些奎兰堡兰堡主丝兰 a b s tr a c t s e q u e n c ea l i g n m e n t i saf h n d a m e n t a lt a s kf o rb i o i n f o r i n a t i c ar e s e a r c h m o s to f s e q u e n c ea l i g 皿e n ts o f t w a r eu t i l i z ed y n 锄i cp r o g r a m m i n g ( d p ) o r t 1 1 eh i d d e nm a r k o v m o d e l ( h m m ) a s m ec o r ea l g o r i t h mf o rg a po p e na 1 1 de x t e n s i o n h o w e v e r ，ag e n e r a l p m b l e mi s t h a t a l 也o u g h am a j o r i t yo ft h e c u r r e n t l y a v a i l a b l ea l i g m e n t sp m v i d e o p t i m a l o rn e a ro p t i m a l r e s u l t s ，t h e y a r e g r e a t l y l i m i t e db yt l l eb o t t l e n e c ko f1 0 w c o m p u t a t i o ns p e e di n d u c e db yt 1 1 eh i g hc o m p u t a t i o nc o m p l e x i t y i nr e c e n ty e a r s ，i ti s d u et om em o d m c a t i o na 1 1 d i m p r o v e m e n t o ft h e a l g o r i m m s a n d e s p e c i a l l y m e d e v e l o p m e n to fc o m p u t e rs c i e n c e 鲫dt e c h n o l o g yb o t l li nh a r d w a r ea n ds o f t w a r et h a t l e a dt ot h ea d v e n to fs u c hp r a c t i c a la i l a l 州ct 0 0 1 sa sb l a s t ，f a s t a ，c l u s t a l w ，w h i c h c a nr c l a t i v e i yc a t c rf o rt h en c e do fr e s e a r c hi nb o t he m c i e n c ya i l d a c c u f a c y t h e f l l n d 锄e m a lw a yt o i m p r o v ec o m p u t a t i o ne m c i e n c y a n da c c u r a c yi st ob e n e rt h e a l i g 衄e n ta l g o r i t l l m si np r i n c i p l es oa st om i n i s hm ec o m p u t a t i o nc o m p l e x i t y a sm o r e a 1 1 dm o r eg e n o m es e q u e n c i n gp r o j e c t sa r ea c c o m p l i s h e do n ea f t e ra i l o t h e r t h e 锄o u i l t o f s e q u e n c ed a t ah a sb e e ne x p o n e n t i a l l yi n c r e a s e d ，m ed e m a n d f o re f f i c i e n ta l i g m e n t a l g o r i m mi ns e q u e n c ea n a l y s i si si n c r e a s i n g l yi l r g e n t b a s e do nt h ec o n c 印to f s e q u e n c es e g m e n t a t i o n ，w e 印p l i e dm em l l l t i p l e s t a g ed ”锄i c p r o g r a n l m i n ga l g o r i t l l m i n p a i r 州s ea l i g n r n e n t t od e v i s ean e wa l g o r i t h r nn 锄e d s a m i d pa n dd e v e l o p e dt h ec o r r e s p o n d i n gp r o g r 啪si nv i s u a l b a s i c ，w ef i n dt h a t s a m i d pn o to i d yr e d u c e st h ec o m p u t a t i o nc o r n p k x 时t 0d ，b u ta l s oo b t a i n se v e n s a t i s f 犯t o r ya c c u r a c y ，a i l di t i s e x p e c t e dm a tt h en e wa l g o r i t h r nw i l lb ei m p o n a n ti n 9 1 0 b a ls e q u e n c ea l i g i 】m e n t k e y w o r d sn u c l e o t i d e s e q u e n c e ，g l o b a ls e q u e n c ea i i g m e n t ，g a p i n s e n i o n ， c o m p u t a t i o nc o m p l e x i 吼m u l t i p l e - s t a g ei n t e l l i g e md y n a m i cp r o g r 锄m i n g u 一 第1 章从人类基因组计划到序列分析 1 1 人类基因组计划( h g p ) 人类基因组计划( h u m a l lg e n o m ep r o j e c t ，h g p ) 是由美国科学家于1 9 8 5 年首先提出的一项希望解开人类生老病死的奥秘，并彻底破解控制各种疾病基因 密码的国际科学研究工程，是人类生命科学史上最伟大的工程。1 9 8 8 年，美国 全国卫生协会和能源部开始组织和实施这项计划，1 9 9 0 年1 0 月正式启动，耗资 3 0 亿美元。人类基因组大约有3 万4 万个基因，3 0 亿个碱基对。 人类基因组计划最初的目标是：通过国际合作，用1 5 年时间构建详细的人 类基因组遗传图和物理图，并期望通过分析每个人类基因的功能和基因在染色体 上的位置，使医学专家们了解所有疾病的分子结构，从而在根本上获得治疗的方 法，进而破译人类全部遗传信息，使人类第一次在分子水平上全面地认识自我， 最终解开人类生命的奥秘。 1 2 生物信息学 过去十年，d n a 测序技术的飞速发展使分子生物学经历了信息革命时代。 这一革命得益于计算机技术在过去十多年来突飞猛进的高速发展。只有使用计算 机技术，才有可能应付日益快速增长的生物信息数据。8 0 年代中期以来，计算 机在生物学中的广泛应用孕育了生物信息学这一新兴学科。 1 2 1 什么是生物信息学 生物信息学这一术语在不同的场合下被赋予不同的含义。广义上说，生物信 息学可指利用信息技术管理和分析生物学数据。这就意味着生物信息学所涉及的 范围相当广泛，从人工智能、机器人一直到基因组( g e n o m e ) 数据分析。就基 因组数据分析这一角度来看，生物信息学主要是指核酸和蛋白质序列数据的计算 机处理和分析，即用数理和信息科学的观点、理论和方法去研究生命现象，组织 和分析呈指数增长的生物学数据的一门学科。生物信息学是一门交叉科学，它包 含了生物信息的获取、处理、存储、分发、分析和解释等在内的所有方面，综合 运用数学、计算机科学和生物学的各种工具来阐明和理解大量数据所包含的生物 学意义。基因组计划产生的海量数据是生物信息学的源头和基础。随着基因组计 划的实施，核酸和蛋白质一级结构序列数据迅速增长( 表1 1 ) ，这种指数增长的 数据量必须使用数理方法和计算机技术来处理分析。 表卜1g 曲b a n k 棱酸序列数据库增长情况 1 h b i e1 1i n c 憎矗s eo fn u c l e i ca c 沁d a t ai ng e n b a n k 年份碱基数序列年份碱基数序列 1 9 8 26 8 0 3 3 86 0 61 9 9 21 0 1 0 0 8 4 8 67 8 6 0 8 19 8 32 2 7 4 0 2 92 4 2 71 9 9 31 5 7 1 5 2 4 4 21 4 3 4 9 2 1 9 8 43 3 6 8 7 6 54 1 7 51 9 9 42 1 7 1 0 2 4 6 22 1 5 2 7 3 19 8 55 2 0 4 4 2 05 7 0 01 9 9 53 8 4 9 3 9 4 8 55 5 5 6 9 4 1 9 8 69 6 1 5 3 7 l9 9 7 81 9 9 66 5 1 9 7 2 9 8 41 0 2 1 2 1 1 1 9 8 71 5 5 1 4 7 7 61 4 5 8 41 9 9 71 1 6 0 3 0 0 6 8 71 7 6 5 8 4 7 1 9 8 82 3 8 0 0 0 0 02 0 5 7 91 9 9 82 0 0 8 7 6 1 7 8 42 8 3 7 8 9 7 1 9 8 93 4 7 6 2 5 8 52 8 7 9 l1 9 9 93 8 4 1 1 6 3 0 1 14 8 6 4 5 7 0 1 9 9 04 9 1 7 9 2 8 53 9 5 3 32 0 0 0 1 11 0 1 0 6 6 2 8 81 0 1 0 6 0 2 3 1 9 9 l7 1 9 4 7 4 2 65 5 6 2 72 0 0 l1 4 3 9 6 8 8 3 0 6 41 3 6 0 2 2 6 2 + 引自2 0 0 1 年1 2 月发布的g e i l b a n k 第1 2 7 版说明 1 2 2 生物信息学的重要性 过去2 0 多年来，计算机在分子生物学研究中得到了广泛的应用，其中占主 导地位的分支学科当属结构生物学。基因组计划的实施，使这一局面发生了根本 性的改变，序列数据的激增，使结构数据在数量上无法与其匹配。序列分析已经 成了这一领域的首要任务。生物信息学的中心任务，使从浩如烟海的序列数据中 提取理性知识。生物信息学家所面临的任务，不仅是解决高效的数据储存手段， 而且需要开发有效的数据分析工具。因为只有利用新的、有效的数据分析工具， 才能将序列信息转换成生物学知识，并弄清它们所蕴含的结构和功能信息，进而 彻底了解它们所代表的生物学意义。 显而易见，序列测定本身不是最终目的，弄清序列数据所包含底生物学意义 才是我们的目标。揭示序列数据所代表的生物学意义，是一门深奥的科学。难度 之大，不亚于破译一部“天书”。如同我们所熟悉的自然语言一样，这部“天书” 是由一个个句子、一个个单词甚至一个个字母组成的。若把蛋白质比作句子，把 序列模体( m o t i 有人译为“基序”) 比作单词，那么，组成蛋白质的基本元素 氨基酸就是字母。显然，孤立地分析单个字母，并不能获得多少信息。而由单个 字母排列组合所构成的单词，则具有显著意义。有时，改变一个单词中的某个字 母，则可改变其含义，乃至整个句子面目全非。生物学中类似的例子就是镰刀状 贫血症，其发病的分子机理在于患者和正常人的区别只是血红蛋白a 链上的一 个氨基酸残基的突变，即谷氨酸g l u 突变成缬氨酸v a l ，而编码谷氨酸的三联体 密码g a a 和编码缬氨酸的三联体密码g u a 只差一个碱基。因此，准确地破译 这部“天书”，是生物信息学所面临的艰巨任务。 我们的目标，则是要掌握这部“天书”中组成各种句子的全部单词，也就是 说，弄清组成各种蛋白质的序列特征所代表的意义，并在将来的某一天，设计自 然界不存在的全新蛋白质，最终实现重写编码人类自身的新的“天书”。今天， 现有的算法和应用程序已经可以用来识别这部“天书”中的部分单词，即序列模 体所表征的结构功能特征和信息。但是，我们尚未搞清把单词组合成句子的句法 规律，还不知道如何将序列模体片段恰当地组合起来，构建成具有生物学意义地 蛋白质。 揭示序列数据所隐含的生物学意义的基本方法可分为两类：( 1 ) 第一类方法 的原理基于模式识别技术，其基本出发点是找出不同序列间的相似性，并推断它 们与结构和功能的内在联系；( 2 ) 第二类方法称之为“从头计算”，即直接从蛋 白质序列预测其三维空间结构，并最终推测其功能【l 】。在可以预见的将来，用传 统的实验方法能够测定的蛋白质结构的数量极为有限。因此，研究开发有效地模 式识别和结构预测方法，已成为生物信息学工作者所面临的主要任务。 1 3 基因组序列信息分析 d n a 序列自身编码特征的分析是基因组信息学研究的基础，特别是随着大规 模测序的日益增加，它的每一个环节都与信息分析紧密相关。从测序仪的光密度 采样与分析、碱基读出、载体标识与去除、拼接、填补序列间隙、到重复序列标 识、读码框预测和基因标注的每一步都是紧密依赖基因组信息学的软件和数据 库。特别是拼接和填补序列间隙更需要把实验设计和信息分析时刻联系在一起。 基因组不仅是基因的简单排列，更重要的是它有其特有的组织结构和信息结 构，这种结构是在长期的演化过程中产生的，也是基因发挥其功能所必须的。利 用国际e s t 数据库( d b e s t ) 和各实验室测定的相应数据，经过大规模并行计算识 别并预测新基因，新s n p s 以及各种功能位点，如剪接与可变剪接位点等。 到1 9 9 8 年底在人类基因中约有3 万多个已被发现。由于新基因带来的显著 经济效益和社会效益，它们成为了各国科学家当前争夺的热点。e s t 序列 ( e x p r e s s e ds e q u e n c et a g s ) 到1 9 9 9 年1 2 月已搜集了约2 0 0 万条，它大约覆盖 了人类基因的9 0 ，因此如何利用这些信息发现新基因成了近几年的重要研究 课题。同时1 9 9 8 年国际上又开展了以e s t 为主发现新s n p s 的研究。因此利用 e s t 数据库发现新基因、新s n p s 以及各种功能位点是近几年的重要研究方向。 虽然对约占人类基因组9 5 的非编码区的作用人们还不清楚，但从生物进 化的观点看来，这部分序列必定具有重要的生物功能。普遍的认识是，它们与基 因在四维时空的表达调控有关。寻找这些区域的编码特征，信息调节与表达规律 是未来相当长时间内的热点，是取得重要成果的源泉。 在不同物种、不同进化水平的生物的相关基因之间进行比较分析，是基因研 究的重要手段。目前，模式生物全基因组序列数据越来越多，因此，基因的比较 研究，也必须从基因的比较，上升到对不同进化水平的生物在全基因组水平上的 比较研究。这样的研究将更有效地揭示基因在生命系统中的地位和作用，解释整 个生命系统的组成和作用方式【z 】。 1 4d 从序列分析 d n a 是遗传的物质基础，基因是具有特定生理功能的d n a 序列，通过基因 的表达能够使上一代的性状准确的在下一代表现出来。序列分析的基本思想是基 于分子生物学中的一条实验知识和规则，也就是当两个分子享有相似的序列时， 由于进化关系以及物理化学限制，它们将很有可能具有相似的三维结构和生物学 功能。因此，序列分析的首要任务是找出可以扩展到结构和功能性质的序列特征。 d n a 序列碱基的6 4 个遗传密码子，对应于蛋白质序列2 0 个不同氨基酸( 表1 2 ) ， 而氨基酸是组成蛋白质的基本单元。因此，蛋白质序列比对的灵敏度较高，更容 易发现亲缘关系较远的序列。然而，从信息学的角度看，由6 4 个密码子编码2 0 个氨基酸残基，这一数量上的减少意味着一些信息的丢失，这些信息又往往与进 化过程有更直接的联系，因为蛋白质只是d n a 遗传变化在功能上的反映。以前， 多肽链测序主要依靠低通量的蛋白质化学方法，今天，这种方法依然相当重要， 特别是在验证经过基因工程改造的一段蛋白质序列时，常常采用直接测定蛋白质 序列的方法。然而，这种方法一次实验只能产生少量数据，并不适用于大规模测 序。近年来，由于高通量的自动荧光d n a 测序技术的应用川，使得d n a 序列数 据快速积累，而由d n a 序列通过计算机程序翻译得到的蛋白质序列数据也相应 增长。 d n a 序列分析的应用包括许多方面。例如，系统发育研究，基因工程中限 制性内切酶图谱分析，基因识别中内含子和外显子预测，由开放读码框( o p e n r e a d i n gf r a m e ，0 r f ) 推测蛋白质一级结构，等等。 表1 2 标准遗传密码表l t a b k1 2s t a n d a r d g e n e t i c c o d e tcg tt t tp h et c ts e rt a t t r y t g t c y s t t t ct c ct a ct g cc t t al e u t c a t 从t g a a g t t g t c g t a g 乳o p甜o p t g gt r d cc t tl e uc c tp r oc th isc g t a r g t c t cc c cc a cc g cc c t ac c a c 从g i n c g aa c t gc c g c g c g gg t ti i ea c tt h ra a t s na g ts e rt t c c ca a ca g cc t a c a a 从l y sa g a r g a t g a c g a a ga g g g m e t gg t tv a ig c t l ag a t s dg g t g i y t g t cg c cg a cg g cc g t ag c a g 从g i u g g aa g t gg c g g a g g g gg 1 4 1d n a 序列数据库 1 4 1 1g e n b a n k g e l l b a n k 是美国i 虱家生物技术信息中心n c b i 建立的d n a 序列数据库，其 数据来源主要来自政府部门资助的测序中心和其他学术单位【引。为保证数据尽可 能完整，g e l l b a n k 与e m b l 、d d b j 建立了相互交换数据的合作关系。 鉴于数据库规模不断扩大，而数据来源种类繁多，g e n b a n k 按照数据来源分 成若干个子库( 表1 3 ) ，以便于管理和使用。将大型数据库分成若干子库，有许 多好处。首先，可以把数据库查询限定在某一特定部分，一边加快查询速度。其 次，基因组计划快速测序得到的大量序列尚未加以注释，将它们单独分类，有利 于数据库查询和搜索时“有的放矢”。g e n b 柚k 将这些数据按高通量基因组序列 ( h i 曲t h r o u g h p u t g e n o m i c s e q u e n c e ，h t g ) 、表达序列标签( e x p r e s s e ds e q u e n c e 1 她s ，e s t ) 、序列标签位点( s e q u e n c et a g g e ds i t e s ，s t s ) 和基因组普查序列 ( g e n o m es u r v e ys e q u e n c e s ，g s s ) 单独分类。尽管这些数据尚未加以注释，它 们依然是g e n b a i l l 【中的重要组成部分。 表l - 3g e n b a n k 的1 7 个子数据库名称和含义 1 h b i el _ 3n a m ea n dm e 8 i n g so ft h e1 7s u b - d a t a b a s e si g e n b a n k 代码英文含义中文含义 p r i r o d m a m v r t n 、v p l n b c t r n a p r h n a t e r o d e n t 0 t h e rm a m m a l i a n 0 t l l e rv e n e b r a t e i n v e n e b r a t e p l a r i t ，劬g a l ，a l g a l b a c t e r i a l s t r u c t u r air n a 灵长类动物 啮齿类动物 其他哺乳动物 其他脊椎动物 无脊椎动物 植物、真菌、藻类 细菌 结构i 斟a v r lr a l病毒 p h g b a c t e r i o p h a g e细菌噬菌体 s y ns y r 油e t i c合成产物 u n au n a n n o t a t e d未注明来源 e s t e x p r e s s e ds e q u e n c et a g s 表达序列标签 p a tp a t e m专利序列 s t s s e q u e n c et a g g e ds i f e s序列标签位点 g s sg e n o m es u r v e ys e q u e n c e s基因组普查序列 h t gh i g ht h r o u g h p u tg e n o m i cs e q u e n c e s高通量基因组序列 第1 章从人类基因组计划到d 1 q a 序列分析 可通过e m r e z 数据库查询系统对g e l l b a n k 进行查询引。这个系统将核酸、 蛋白质结构数据库整合在一起。此外，通过该系统的生物医学文献摘要数据库 m e d l i n e ，可获取相关文献信息。通过计算机网络，进入n c b i 主页，可以用 b l a s t 程序对g e n b a i l l ( 数据库进行未知序列的同源性搜索。完整的g e r t b a n k 数 据库包括序列文件、索引文件以及其他有关文件。索引文件根据数据库中作者、 参考文献等建立，用于数据库查询。g e n p e p t 是由g e n b a n k 中的核酸序列翻译而 得到的蛋白质序列数据库，其数据亦采用g e i l b a l l l ( 格式。g e n b a n k 中最常用的 是序列文件。序列文件的基本单位是序列条目，包括核苷酸碱基排列顺序和注释 两部分。目前，许多生物信息资源中心通过计算机网络提供该数据库文件。 1 4 1 2e m b l 核酸序列数据库e m b l 由欧洲生物信息学研究所e b i 维护。e m b l 的数据 来源主要有两部分，一部分由科研人员或基因组测序机构通过计算机网络直接提 交，另一部分则来自科技文献或专利【5 】口e m b l 与d d b j 、g e i l b a n k 建有合作关 系，分别在全世界范围内收集核酸序列信息，每天都将新测定或更新过的数据相 互交换。 近来，d n a 数据库的规模正在以指数方式增长，平均不到9 个月就增加一 倍。可以利用序列查询系统s r s 从e m b l 数据库中检索和获取序列数据及其相 关信息【6 】os r s 序列查询系统通过超文本链接将d n a 序列数据库和蛋白质序列、 功能位点、结构、基因图谱以及文献摘要m e d l i n e 等各种数据库联系在一起。 利用e b i 网站提供的b l a s t 或f a s 认程序，可以对e m b l 数据库进行未知序列 同源性搜索。 1 4 1 3d d b j d d b j 是d n a d a t ab a l l ko f j 印a 1 1 的简称，始建于1 9 8 6 年，由日本国立遗传 学研究院( n a t i o n “i n s 曲l t eo f g e n e t i c s ) 负责数据库的建设、维护和发布7 1 ，并 与e m b l 和g e n b a n k 合作，从世界各地通过计算机网络把序列直接提交该数据 库。d d b j 网页上也提供了包括f a s 俄和b l a s t 在内的数据库查询和搜索工具。 1 4 1 4d b e s t d b e s t 数据库专门收集e s t 数据，亦采用g e i l b a i l l 【格式，包括标识符、编 号、序列数据以及d b e s t 的注释摘要【jo j ，也按d n a 种类分成了若干子库。 1 4 1 5g s d b 基因组序列数据库( g e n o m es e q u e n c ed a t ab a s e ，g s d b ) 由美国新墨西哥州 s a n t af e 的国家基因组资源中心创建j 。g s d b 收集、管理并且发布完整的d n a 序列及其相关信息，以满足基因组测序中心需要。该数据库采用服务器一客户机 关系数据库模式，大规模测序机构可以通过计算机网络向服务器提交数据，并在 发送之前对数据进行检查，以确保数据的质量。 g s d b 数据库中条目的格式与g e n b a n k 基本一致，主要区别是g s d b 数据 库中增加了g s d b i d 识别符。g s d b 数据库可以通过万维网查询，也可以使用 服务器一客户机关系数据库方式查询。无论用哪种方法，熟悉数据库结构化查询 语言s q l ( s t n l c n u 甜q u e r ) ，l a l l g u a g e ) ，对更好地使用g s d b 数据库会有所帮助。 1 4 2 序列分析中的难点 d n a 、r n a 和蛋白质是分别由重复的核苷酸或氨基酸单元组成的线性高分 子，具有高度有序并能完成特定生物学功能的三维结构。通过实验获取核苷酸或 氨基酸是如何排列组成生物大分子序列的信息是相对容易的。因此，通过计算机 进行序列分析的目的是揭示出核苷酸或氨基酸序列数据编码的更高级的结构或 功能信息。序列分析的论题相当广泛，要求理解正在不断地改进和扩展地基本算 法及其实际应用。 生物学中的计算与物理学或化学中的计算不同。它通常处理从观测数据中得 到的实验知识，并不求解第一定律方程式，而事实上生物学中也没有这样的方程 式。实际上，序列分析的基本思想是基于分子生物学中的一条实验知识和规则， 也就是当两个分子具有相似序列时，由于进化关系以及物理化学限制，它们将很 有可能具有相似的三维结构和生物学功能。因此，序列分析的首要任务是找出可 以扩展到结构和功能性质的序列特征。根据数据组织的方式以及相应在序列分析 中使用的计算方法的不同，可以对序列分析进行一个粗略的分类( 表1 4 ) 。在序 列的相似性搜索中，一个基本的操作是将储存在一级数据库中的已知样本进行比 较，发现其中任何可能用于进一步推理的相似性。一级数据库可以是一个序列数 据库或者是一个三维结构数据库，同时相似性搜索还包括对给定的打分函数进行 寻优。基于知识的预测则是以某种方式将已知样本抽象成代表序列结构或序列 功能相关性的经验规则。这些规则以计算结果的形式储存，同时，这些规则将应 用在实际分析中或被用来解释更为基本的原理。这里一个基本的问题是如何获取 足够的经验规则，这与计算机科学中的机器学习有关。寻优以及机器学习方法在 传统的人工智能应用中已经得到了使用，在处理生命科学中的问题时，这两种方 法同样十分有效。 表1 4 序列分析中的搜索和学习问题o ”1 t a b l el - 4s e a r c h i n ga n d i 明n i n gp r o b l e m s i ns e q u e n c ea n a l y s i s 生命科学中的问题计算科学中的问题 相似性搜索两两序列比对寻优算法 相似序列的数据库搜索一动态规划( d p ) 多序列比对一模拟退火( s a ) 系统发生树重建一遗传算法( g a ) 蛋白质三维结构比对 一h o p f i e l d 神经网络 结构功能预从头预测r n a 二级结构预测 测r n a 三维结构预测 蛋白质三维结构预测 基于知识的m o t i f 提取模式识别和学习方法 预测功能部位预测一判别分析 细胞定位预测一级联神经网络 编码区预测一隐马氏模型( h m m ) 跨膜片段预测一形式语法 蛋白质二级结构预测 蛋白质三维结构预测 分子分类超家族分类聚类算法 基因的0 “h o l o g ，p a r a l o g 一层次聚类分析 分组一k o h o n e n 神经网络 三维折叠子分类 寻找序列相似性的过程称为序列比对。序列比对是序列分析的基本手段。对 两条序列进行比较的时候，必须找到一个最佳的对齐方式，这样才能最好地反映 两条序列的相似关系。因此，获取最佳的序列比对等同于将给定的打分函数进行 优化，这个打分函数需要计算氨基酸或核酸的相似度以及插入和缺失对应的罚 分。获取最优的比对有不同的方法。全局比对比较整条序列，而局部比对则可以 发现局部相似区，在同源搜索中也得到使用。 序列相似性搜索或所谓的同源搜索将目标序列和数据库中的序列一一进行 比较，如果在数据库中发现了相似序列，并且已知这条序列负责完成某项特殊的 功能，那么目标序列可能也有相似的功能。同源搜索就好像是在用d n a 语言写 的已知句子中查找新句子的相似句，如果发现了匹配的句子，则可以用已知句子 的意思解释新句子。字典的使用和语法知识的掌握更具价值，这在m o t i f 搜索中 已经部分实现。这一方法从一级数据库中获取序列给你关系的经验知识，并将这 些知识以字典的形式组织起来。使用m o t i f 字典来检查提交的序列，如果存在任 何的m o t i f ，则每个m o t i f 代表提交序列的一个可能的功能位点。不幸的是，迄今 还没办法产生一个详尽的包含所有m o t i f 或其他有关各种功能性质的经验知识列 表。因此，在实际应用中，同源搜索仍然是最受欢迎的方法。 第2 章d 双序列比对 d n a 双序列比对是指通过一定的算法对两个d n a 序列进行比较，找出两者 之间的最大相似性匹配。双序列比对是序列分析的常用方法之一，是多序列比对 和数据库搜索的基础。为了识别一个新测定的序列和一个已知基因家族之间的进 化关系，确定它们是否具有同源性，通常需要通过序列比对，找出它们之间核苷 酸或氨基酸残基的最大匹配，从而定量给出其相似性程度。如果两者相似性程度 很低，则很难确定它们是否具有同源性，除非使用系统发育分析等其他方法，或 有实验结果加以证实。通过对基因或蛋白质家族关系的分析，可以从浩瀚的基因 组信息中找出一些线索，从而对该基因或蛋白质家族的完整性进行预测。 2 1 序列比对 序列比对实际上是根据特定数学模型找出两个序列之间的最大匹配残基数。 而序列比对数学模型一般用来描述两个序列中每一个字符串之间匹配的情况。通 过改变某些参数可以得到不同比对结果，不同模型所反映的生物学性质不同。例 如，可以根据分子结构、功能和进化等方面的相关性进行构建。比对结果没有正 确和错误之分，其区别是由于模型所反映的生物学性质不同。 总体来说，比对模型可以分为两类：一类是考察两个序列之间的整体相似性， 称为全局比对：另一类则着眼于序列中的某些特殊片段，比较这些片段之间的相 似性，即局部比对。在实际应用中，用全局比对企图找出只有局部相似性的两个 序列之间的关系显然是徒劳的；而用局部比对得到的局部相似性结果则同样不能 说明这两个序列的三维结构或折叠方式是否相同。 目前常用的b l a s t 和f a s t a 等数据库搜索程序均采用局部相似性比对方法， 具有较快的运行速度，采用某些优化算法可进一步提高速度。局部相似性搜索主 要用于找出序列中的功能位点，如酶的催化位点等。它们通常只有一个或几个残 基，具有较高的保守性，并且不受序列其他部分的插入、缺失和突变的影响。从 这个意义上说，局部相似性搜索比整体相似性比对更加灵敏，也更具有生物学意 义。 2 1 1全局比对 在全局比对中，需要优化的打分函数是比对后每个位置权重的和。权重由4 种核苷酸之间或2 0 种氨基酸之间的替换矩阵以及空位罚分给出。理想情况下，权 重必须反映突变和插入删除的生物学过程。然而，对于核苷酸序列来说，权重的 分配有主观性，通常是一个匹配和错配对应一个固定的值，而不考虑碱基对的类 型。氨基酸序列的比对相当客观，因为它能反映微妙的序列相似性，进行氨基酸 比对，替换矩阵可以根据观察到的经过不同进化多样性校正后的氨基酸突变频率 来建立。例如p a m 2 5 0 就是从一套紧密相关的序列中计算出来的，经过校正使得 它适用于进化上分离的序列。在当前可以获取的程序中，p a m 和b l o s u m 系 列的矩阵运用得最为广泛。 d l - 1 j 臻l j 硝 ( i )n ) 图2 1 动态规划算法中计算量优得分的方法 ( a ) 空隙罚分是常数的情况：( b ) 空隙罚分是空隙长度的线性函数的情况 用，表示用字母s 相互替换得权重，它是对称的替换矩阵中的一个元素，用 d 代表单个字母空隙的权重。根据动态规划算法，打分函数在每个结点的最优值来 源于图2 1 中的3 种可能的路径：对角，水平和垂直路径。用打分矩阵d 表示成 如下的公式： d = m a x ( d i 1 产l + w 5 r 妒，f 删，d p l ，+ dd 产l + 力( 2 1 ) 这里s 表示水平序列的第f 个字母，倒表示垂直序列的第，个字母。打分矩阵的 初值为： d o o = o d f 。o = 埘( f o r f - 1t oh ) d o ，j 可d ( f o r 卢1t o 埘) 其中n 和m 分别是水平序列和垂直序列的长度。从对应于路径矩阵左上角的元素 d l ，l 开始，对所有元素重复使用公式( 2 1 ) ，最后得到见。就是打分函数的最优值。 如果每一步中，从3 种可能性中选出的最佳路径在路径矩阵中都有打分，那么经 过从路径矩阵的右下角开始的回推可以得到路径的得分连接，从而反推得到完整 的最佳比对。获得最佳得分和最佳比对的过程需要的操作数正比于矩阵的大小 x 埘；因此，这是一个d 口n 的算法。 如果考虑了核苷酸或氨基酸的插入和删除可能的分子机制，公式2 1 的罚分就 不一定符合实际情况了，因为其罚分和空隙长度是成正比的，而实际上，连续的 空隙可能来源于单一的事件。引入长度依赖的罚分，公式2 1 统一成： d ，严a 】【 ( d f 1 ，i + j 。r p f ，m a ) ( p ，t m lm a ) p f j 鳓) ( 2 2 ) 其中政是长度为k 的空隙的罚分。这是个d f 7 叻的算法，因为在内层循环中多了 个求最大值的操作。但是，如果将长度依赖简化成只含有一个起始( 空隙起点) 部分和一个延长( 空隙延伸) 部分，表示为：叶城，其中a 和b 是常数，这样 来算法的复杂度还是d f ? 叻。 2 i 2 局部比对 局部比对用于寻找相似程度较低，或亲缘关系较远的两个序列，它们在整体 上可能不具有相似性，但在一些较小的区域上却可能存在局部相似性。用于局部 比对的算法也是基于矩阵的方法，而且同样是运用回溯法建立允许空位插入的比 对。局部比对的一个重要特征是打分矩阵中每个单元均可以是比对结果序列片段 的终点，该片段的相似性程度由该单元中的分数值表示。 2 2目前常用的序列比对算法 2 2 1点阵图 点阵图( d o tp l o t ) 是双序列比对的基本方法，通常用图示方法表示，非常直 观【。假定有两个序列a 和b ，其长度不一定相同，但相差不大。把序列a 的残 基沿x 轴排列，序列b 的残基沿y 轴排列，并构建一个矩阵。该矩阵的所有元素 的初始值均为o 。对每个矩阵元素x 赋予一个相似性值，表示该矩阵元素对应的 两个残基的相似程度。如果只考虑同一性而不考虑相似性，则可以简单地将序列a 和序列b 相同残基所对应地矩阵元素的值置为1 ，不同残基所对应地矩阵元素的值 置为o 。 点阵图的最基本特征是有一些由噪音组成的随机点和具有喜好特征的主对角 线( 表2 一1 ) 。其中主对角线由连续的点组成，它代表两条序列中具有相似性的区域。 点阵图为从噪声背景中提取信号提高了一个图形表示法，可用于对于数据库搜索 结果的解释。 表2 1 序列比对的点阵图方式 1 h b l e2 一ld o t p i o tf o r 阳i 刑i s ea i i g n m e t 2 2 2 全局比对算法一n e e d ie m a n w u n s c h 算法 从本质上讲，n e e d l e m a n - w u n s c h 算法与点阵图方法类似，从整体上分析两个 序列的关系，即考虑序列总长的全局比对，用类似于使全局相似最大化的方式， 对序列进行比对。两个不等长度序列的比对分析必须考虑在一个序列中滤掉一些 碱基或在另一个序列中作空位处理。n e e d l e m a f i 和、 ，m l s c h 的法则为这些步骤提供 了实例【15 1 。这一算法是为氨基酸序列发展的，但也可以用于核酸序列。算法最初 寻求的是使两条序列间的距离最小。尽管这类距离的元素是以一种特定的方式定 义的，但该算法的良好特性在于它确定了最短距离。这是一个动态规划的方法( 1 6 】。 将两条待比对序列沿双向表的轴放置。从任一碱基对，即表中的任一单元开 始，比对可沿三种可能的方式延伸：如果碱基不匹配，则每一序列加上一个碱基， 并给其增加一个规定的距离权重：或在一个序列中增加一个碱基而在另一序列中 增加一个空位或反之亦然。引入一个空位时也将增加一个规定的距离权重。因此 表中的一个单元可以从( 至多) 三个相邻的单元达到。把到达左上角单元距离最 小的方向看作相似序列延伸的方向。等距离时意味着存在两种可能的方向。将这 些方向记录下来，并在研究了所有的单元之后，沿着记录的方向就有一条路径可 从右下角( 两个序列的末端) 追踪到左上角( 两个序列的起点) ，由此产生的路径 将给出具有最短距离的序列比对。 袭2 - 2n e e m e m a n w u n s c h 算法的初始矩阵 t a b l e2 2o r i g i n a lm a t r i io f n e e d i e m a n w u n s c h a i g o r i t h m dlgavflcdryfo a1o001001000o000 d01000000001o0o0 l0o1000001000000 g0o01o000000o0o0 r0o00o0oo00010o0 to0o0o0oo0o000o0 0o00o0o0ooo00001 n0ooo0o0oo0o00 o0 c000000000100 0o0 d01oo0o0o o010000 r000oo0o0 0001o0o yooo0ooo0 oo0o100 yo0o0o0oo 0o001o0 0o0o00o00 o000001 以下面两条短序列为例来描述该算法。首先构建一个二维矩阵：将两序列中 匹配残基所对应单元的值置为1 ，不匹配的值置为o 。用来表示两个序列的匹配情 况( 表2 2 ) 。然后对矩阵的每个单元进行连续求和，从矩阵中最后一个单元开始， 从最后一行、最后一列开始，先按列、后按行，逐步进行。 下一步统计倒数第2 列，从该列的最后一行开始。该矩阵单元对应的残基不 同，该单元的分值为0 。从该列往上，下一个单元对应的残基也是一对非匹配残基， 其本身的分值为0 ，但根据连续求和的原则，达到该单元的唯一路径为下一行、下 一列的单元为匹配残基，其分值为1 ，因此这一单元的总体分值为l 。接下来统计 倒数第3 列，该列最后一行为不同残基对，分值为0 。往上移动一个单元，到达倒 数第2 行，此时为一