（生物化学与分子生物学专业论文）快速多重序列局部对齐算法开发及其应用.pdf

黄明松中山大学硕士学位论文 中文摘要 随着基因组计划的实施，基因组序列信息高速增加，为我们提供了进行大批量的 长序列问多重比对分析的原始材料，然而现有的多重序列比对分析工具软件在面对数 量大，平均长度长的多重序列时显得无能为力，因此发展一种新的快速的能处理大量 长的多重序列的比对分析软件有重要的意义。 根据分子进化分析的基本原理，采用启发式算法，用先通过多序列间两两局部比 对，再以此为基础进行多重对齐的策略，开发了快速多重序列局部比对工具软件。接 着利用开发的快速多重序列局部对齐算法，构建快速进化树构建分析系统。并为上述 的两个分析系统构建界面友好的w w w 服务平台，以方便有需要的研究人员应用它 们。在开发过程中，系统整合许多已有的研究成果和代码，软件资源( 包括b l a s t ，p h y l i p 等) ，节省了人力物力和时间。最后利用构建的进化树构建分析平台，重建了2 3 种杆 状病毒的系统发育树。该系统进化树的结果和以前采用传统方法所获得的结果具有高 度一致性。 从测试结果也能来看，在处理分析数量大，平均长度长的多序列时，本文系统较 传统方法能明显体现出高速度且有相对高的精确度优势。用户可以通过网址 h t t p ：l i f e z s i i e d u c n h u a n g h u a n g _ r e a l i g n 获得本系统的w w w 服务。 关键字：生物信息学，启发式算法，多序列局部对齐，进化树重建 黄明松中山大学硕士学位论文 a b s t r a c t t h ea m o u n to fl o n gs e q u e n c e sa n dg c n o m c ss e q u e n c e si sg r o w i n gr a p i d l y , a n dw i t h i nt h e s e q u e n c e sl u r kc o u n t l e s sc l u e st ol i f ei t s e l f i t h a sc r e a t e do p p o r t u n i t i e sf o r s t u d y i n g n u m e r o u sa s p e c t so fg c n ef u n c t i o na tt h eg e n o m i cl e v e lh o w e v e r , w i t ht h en e e dt oh a n d l e t h e s ei n c r e a s i n gn u m b e r so fl o n gs e q u e n c e s ，i tb e c a m ec l e a rt h a tc u r r e n tm u l t i p l es e q u e n c e s a n a l y z i n gs o f t w a r ew e r en o tf a s ta n ds p e c i a l i z e de n o u g h s od e v e l o p m e n to fan e wf a s t a l g o r i t h mw h i c hc a nh a n d l el a r g en u m b e r so fl o n gs e q u e n c e sa n dg e n o m e sw i l lb ev e r y h e l p f u l i nt h i ss t u d y , b a s e do nt h e o r yo f m o l e c u l a re v o l u t i o n , u s i n gh e u r i s t i cs e a r c h e s , w e d e v e l o p e daf a s ta l g o r i t h mf o rl o c a lm u l t i p l es e q u e n c ea l i g n m e n t a n dap h y l o g e n e t i ct r e e r e c o n s t r u c t i o ns y s t e mw a sa l s od e v e l o p e du s i n gt h i sn e wa l g o r i t h m t h e nw ed e v e l o p e da u s e r - f r i e n d l yp l a t f o r mf o rt h e s et w os y s t e m sa n du s e r sc a ne a s i l ya c c e s si t t h r o u g ht h e w o r l dw k l ew e b i nt h ed e v e l o p m e n tp r o c e s s , w ea l s oi n t e g r a t e ds o l n ct o o l sa n dc o d e st h a t w e r ea v a i l a b l ea n dw e l lt e s t e di n c l u d i n gb l a s ta n dp h y l l pt os a v et i m e ，m o n e ya n d r e s o u r c e s t h ep l a t f o r mw a st e s t e db yu s i n gd a t a s c t so fb a c u l o v i r u sg e n o m e s p h y l o g e n e t i c t r e eo f 2 3b a c u l o v i r u sg e n o m e sw a sg e n e r a t e di n2m i n u t e so ns u b m i s s i o n t h et r e ew a s h i g h l yc o n s i s t e n tw i t ht h a tr e p o r t e db yo t h e rr e s e a r c h e r su s i n gt r a d i t i o n a lm e t h o d s t e s tr e s u l t sa l s os h o w e dt h a tt h en e wm e t h o dm a yb eb o t hf a s t e ra n dm o r ea c c u r a t et h a n t r a d i t i o n a lm e t h o d si na n a l y z i n gl 盯g en u m b e ro f l o n gs e q u e n c e ac g is e r v i c ec a nb e a c c e s s e dt h r o u g hh t t p ：l i f e z s u e d u c n h u a n g h u a n g _ r e a l i g n 。 k e y w o r d s ：b i o i n f o r m a t i c s ，h e u r i s t i ca l g o r i t h m s ，l o c a lm u l t i p l es e q u e n c ea l i g n m e n t ， p h y l o g e n e t i ct r e er e c o n s t r u c t i o n 黄明松中山大学硕士学位论文 b l a s t n c b i e b i p a u p p h y l i p u p g m a n j w w w 缩写词 b a s i cl o c a la l i g n m e n ts e a r c ht o o l 基本的局部序列对齐搜索工具 n a t i o n a lc e n t e rf o rb i o t c c h n o l o g yi n f o r m a t i o n 美国国立生物技术信息中心 e u r o p e a nb i o i n f o r m a t i c si n s t i t u t e 欧洲生物信息学研究所 p h y l o g e n e t i ca n a l y s i su s i n gp a r s i m o n y ( a n do t h e rm e t h o d s ) 采用简约法( 和其他方法) 的系统发育分析 p h y l o g e n yi n f e r e n c ep a c k a g e 系统发育推导软件包 u n w e i g h t e dp a i rg r o u pm e t h o dw i t ha r i t h m a t i cm e a n 算术平均的不加权成对分组法 n e i g h b o rj o i n i n g 邻接法 w o r l dw k l ew e b 万维网 v 黄明松 中山大学硕士学位论文 第1 章前言 1 1 生物信息学与序列比对 1 1 1 生物信息学 人类为了更深入地了解和认识自身，制定了宏伟的人类基因组计划。人类基因组 计划顺利实施，产生了大量的生物分子数据。据权威机构统计，目前生物分子数据量 每1 5 个月翻一翻，生物分子数据发展的速度甚至超过了摩尔定律( 即半导体芯片上 的晶体管数量每1 8 个月翻一醒) 。这些生物分子数据具有丰富的内涵，其背后隐藏着 人类目前尚不知道的生物学知识。充分利用这些数据，通过数据分析、处理，揭示这 些数据的内涵，从而得到对人类有用的信息，是生物学家、数学家和计算机科学家所 面临的一个严峻的挑战。生物信息学就是为迎接这种挑战而发展起来的一门新型学 科，它是由生物学、应用数学、计算机科学相互交叉所形成的学科，是当今生命科学 和自然科学的重大前沿领域之一，也是2 1 世纪自然科学的核心领域之一。 h g p 生物数据的漱增 ( 每1 5 - t - 月翻一番) 1 1 。2 生物信息特征 生物学家 数学蒙 计算机 科学家 图1 - 1 生物信息学的诞生 生物信息学 ( q 融1 0 鹚翕l i s ) 的诞生 生物体是一个复杂的系统，同时也是一个信息系统，该信息系统控制着生物的遗 传、生长和发育。所有的信息都存贮在生物体内的遗传物质中。需要用信息科学方法 研究生命信息特别是遗传信息的组织、复制、传递、表达及其作用，否则难以理解生 命的工作机制，难以揭示生命的奥秘。从信息学的角度来看，生物分子是生物信息的 黄明松中山大学硕士学位论文 载体，生物分子至少携带着三种信息，即遗传信息、与功能相关的结构信息、进化信 息。 与一般信息相比，生物分子信息具有明显的特征。首先，生物分子信息数据量大， 如d n a 序列常以千兆碱基( g i g ab a s e ，g b ) 为单位。其次，生物分子信息复杂，既 有生物分子序列的信息，又有结构和功能的信息，既有生命本质信息，如基因，又有 生命表象信息，如基因表达信息。生物分子信息另一个重要的特征是，生物分子信息 之间存在着密切的联系，例如，基因序列与蛋白质序列之间的关系，生物分子序列与 结构之间的关系，结构与功能之间的关系。 1 1 3 生物信息学目标和任务 揭示生物分子数据的内涵是生物信息学的长远目标。生物分子数据具有深刻的内 涵，数据之间存在着复杂的联系，这些数据中蕴涵着丰富的生物学知识和生物学规律。 生物信息学的发展将揭示生物分子信息的本质，使人类彻底了解、掌握遗传信息的编 码、传递及表达，从而加快人类了解自身的进程。目前其主要任务是研究生物分子 数据的获取、存贮和查询，发展数据分析方法。主要包括三个方面。 1 收集和管理生物分子数据，使得生物学研究人员能够方便地使用这些数据， 并为信息分析和数据挖掘打下基础。生物分子数据来自于生物学实验，应用信息学技 术收集和管理这些数据，将各种数据以一定的表示形式存放在计算机中，建立数据库 系统，并提供数据查询、搜索和数据通讯工具。 2 进行数据处理和分析。通过数据分析，发现数据之间的关系，认识数据的本 质，进而上升为生物学知识。并在此基础上，解释与生物分子信息复制、传递和表达 有关的生物过程，解释在生物过程中出现的信息变化与疾病的关系，帮助发现新的药 物作用目标，设计新的药物分予，为进一步的研究和应用打下基础。目前生物信息学 的主要研究对象是d n a 和蛋白质。在d n a 分析方面，着重分析d n a 序列中的基因信息 及基因表达调控信息，分析基因表达数据，分析基因之间的相互作用关系，比较不同 种属的基因组，研究基因组中非编码区域的生物学功能。在蛋白质分析方面，着重分 2 黄明松 中山大学硕士学位论文 析蛋白质序列与蛋白质结构及功能之间的关系，预测蛋白质的结构和功能，研究蛋白 质的进化关系。 3 开发分析工具和实用软件，解决具体的问题，为具体的生物信息学应用服务， 例如，开发生物分子序列比较工具、基因识别工具、生物分子结构预测工具、基因表 达数据分析工具等。 1 1 4 研究的重要内容：数据库搜索和序列比对 对于许多新得到的生物分子序列，我们并不知道其相应的生物功能。生物学研究 人员希望能够通过搜索序列数据库找到与新序列同源的已知序列，并根据同源性推测 新序列的生物功能。搜索同源序列在一定程度上就是通过序歹4 比较寻找相似序列。在 分子生物学中，d n a 或蛋白质的相似性是多方面的，可能是核酸或氨基酸序列的相似， 可能是结构的相似，也可能是功能的相似。一个普遍的规律是序列决定结构，结构决 定功能。所以，当研究序列的相似性时，我们最终希望根据这个普遍规律推测出与新 序列相应的结构或功能，也就是发现新的生物分子数据的内涵。这种方法在大多数情 况下是成功的。当然，也有例外；同时也存在着这样的情况，即两个序列几乎没有相 似之处，但分子却折叠成相近的空间形状，并具有相似的生物功能。 对于d n a 序列，同源搜索除有助于确定其功能之外，还有助于确定编码区域，确 定基因。对于蛋白质，我们希望能够直接从蛋白质序列准确地预测蛋白质的结构和功 能。通过序列的比较分析，特别是将一个未知结构、功能的蛋白质序列与已知结构、 功能的蛋白质序列进行比较，可以得到一些关于蛋白质结构或功能的有用信息。通过 比较不同种属的同源序列，还可以得到这些种属由他们共同祖先进化而来的信息。可 以比较同类序列，也可以比较不同类型的序列，如比较d n a 序列与蛋白质序列。当 然，在比较之前，需要将不同类型的序列按照一定的规则转换成相同类型的序列，如 将d n a 序列按三联密码的关系转换为蛋白质序列。 序列比较的基本操作就是比对( a l i g n m e n t ) ，即将两个序列的各个字符( 代表核 苷酸或者氨基酸残基) 按照对应等同或者置换关系进行对比排列，其结果是找出两个 黄明松中山大学硕士学位论文 序列共有的排列顺序，这是序列相似程度的一种定性描述，它反映出在什么部位两个 序列相似，在什么部位两个序列存在差别。 序列比对的数学模型大体可以分为两类，一类从全长序列出发，考虑序列的整体 相似性，即整体比对；第二类考虑序列部分区域的相似性，即局部比对。局部相似性 比对的生物学基础是蛋白质功能位点往往是由较短的序列片段组成的，这些部位的序 列具有相当大的保守性，尽管在序列的其它部位可能有插入、删除或突变。此时，局 部相似性比对往往比楚体比对具有更高的灵敏度，其结果更具生物学意义。区分这两 类相似性和这两种不同的比对方法，对于正确选择比对方法是十分重要的。应该指出， 在实际应用中，用整体比对方法企图找出只有局部相似性的两个序列之阅的关系，显 然是徒劳的；而用局部比对得到的结果也不能说明这两个序列的三维结构或折叠方式 一定相同。b l a s t 和f a s t a 等常用的数据库搜索程序均采用局部相似性比对的方法， 具有较快的运行速度，而基于整体相似性比对的数据库搜索程序则需要超级计算机或 专用计算机才能实现。 序列最优比对反映了两个序列的最大相似程度，寻找最优比对的基本算法就是动 态规划算法。一个新序列与数据库中的某个序列的比较可以在很短的时间内就可以完 成，但由于序列数据库的数据量巨大，逐个与数据库中的每条序列进行比较比较需要 很长的时间。因此，对于进行数据库搜索的序列比较算法要求具有较高的速度。目前 在序列搜索方面有多种不同的实用程序，比如b l a s t 和f a s t a ，它们能够根据所给 定的目标序列，从d n a 序列数据库或蛋白质序列数据库中快速地找出相似序列。现 在，这两个程序已被广泛地应用于d n a 或蛋白质序列分析。 与序列两两比对不一样，多重序列比对研究的是多个序列的共性。序列的多重比 对可用来搜索基因组序列的功能区域，也可用于研究一组蛋白质之间的进化关系。在 蛋白质研究方面，除序列数据库搜索之外，还有结构数据库搜索，而通过结构数据库 的搜索，常常能发现蛋白质之间更深层的关系。如对于两个序列不相似的蛋白质，通 过结构数据库搜索比较，有可能发现这两个蛋白质具有相似的空间结构，由此可以推 测这两个蛋白质具有相似的生物功能。 4 黄明松中山大学硕士学位论文 1 1 5 研究中常用的动态规划方法介绍 动态规划( d y n a m i cp r o g r a m m i n g ) 是一种解决多阶段决策问题的最优化方法，或 复杂空间的优化搜索方法。动态规划将比较复杂的问题划分为若干阶段，通过逐段求 解，最终获得全局最优解。这种方法在解决一些复杂的组合问题中显示出优越性，尤 其是在解决离散性问题方面，用动态规划方法去处理，往往比用线性规划或非线性规 划方法更有效。所谓多阶段决策问题是指这样一类活动过程：它可以分为若干个相互 联系的阶段，在每个阶段上都要作出决策，而每个阶段的决策确定以后，将会影响以 后各阶段的活动及其决策；当所有阶段的决策确定以后，就完全确定了该问题的活动 过程。各个阶段所确定的阶段性决策构成一个决策序列，成为总体决策。一般来说， 由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供 选择的策略。若对应一个策略，可以由一个量化的指标来确定这个策略所对应过程的 效果，那么，不同的策略就有各自不同的效果。在所有可供选择的策略中，对应效果 最好的策略称为最优策略。将一个问题划分成若干个相互联系的阶段，选取其中的最 优策略，这类问题就是多阶段决策问题。动态规划的理论和方法在求解多阶段决策问 题中是卓有成效的，顺序递推和逆序回溯这两个过程是动态规划基本方法的核心。 动态规划是生物信息学中一种基本的优化方法，在d n a 序列或者蛋白质序列的比 对、基因识别、r n a 结构预测、隐马尔科夫模型求解、生物分子探针优化设计等方面 有着重要的应用。动态规划解决问题的基本过程是：将一个问题的全局解分解为局部 解，顺序递推求出局部最优解，随着执行过程的推进，“局部”逐渐接近“全局”， 最终获得全局最优解。在计算机中，以“图”作为求解动态规划问题的数据结构，图 中的每个顶点代表一个局部问题。其中有一个顶点( 起点) 代表特别的局部问题，即 问题的开始阶段，另有一个顶点( 终点) 代表全局问题。这样，一个优化问题可以转 化为在图中求出一条从起点到终点的最短路径。通过顺序递推求出最短路经的长度， 然后，通过逆序回溯找出最短路经。 黄明松中山大学硕士学位论文 1 2 生物信息学平台的开发环境和所用到的工具简介 1 2 1l i n u x 操作系统 l i n u x 系统具有最新u n i x 的全部功能， 函数，即时负载，优越的存储管理和t c p i p ， l i n u x 主要优点还有： 包括真正的多任务，虚拟存储，共享库 u u c p 网络工具。 稳定的系统：优秀的系统设计的结构，精简的系统实现内核，不有象其它操作系统 一样内核如此庞大、漏洞无穷。同时l i n u x 开发源代码的开发模式，这保证了系 统的漏洞能被及时发现和改正。 高效：建立在u n i x 上面发展出来的操作系统，具有与u n i x 系统相似的的程序 接口跟操作方式，当然也继承了u n i x 稳定并且高效率的特点。 免费或少许费用。 1 2 2 p e r l 语言 p e f l 强大的正则表达式以及字符串操作使这个工作变得简单而没有其它语言能 相比( s c h w a r t z ，1 9 9 7 ) 。p e t l 非常擅长于切割，扭转，绞，弄平，总结，以及其它的 操作文字文件( w a l le ta 1 ，2 0 0 0 ) 。生物信息的内容大部分是以文字文件存在的，如物 种名称，种属关系，基因或序列的注解，评注，目录查阅，就连d n a 和蛋白质序列本 身也是以文字形式出现的。正是因为这样，在生物信息资料处理的时候最多涉及的也 是字符操作问题。各种不同格式的生物信息资料之间的相互转换是一个很难解决的问 题，而p e r l 由于具有方便和强大的字符操作功能，使得它在这方面具有特殊的用途 ( t i s d a l l , 2 0 0 1 ) 1 2 3 c c + + 语言 c 语言：集低级语言和高级语言优点于一身的语言，由于它的简结、紧凑、方便 和灵活，它很快就成为国际上广泛流行的语言。 c + + 语言：从c 语言发展而来的，面向对象的程序设计语言。兼容c 语言，c 语言 可以被看做c + + 的一个子集。 6 黄明松中山大学硕士学位论文 c c + 语言主要优点： 中级语言：c 语言把高级语言的基本结构和语句与低级语言的实用性结合起来。 可以象汇编语言一样对位、字节和地址进行操作，而这三者是计算机最基本的工 作单元。 性能好：性能有两方面，算法速度和机器代码效率。算法与语言是独立的，在编 程之前必设计算法，编写一个快速程序的第一个步骤是设计良好的算法。机器代 码效率性能上，用汇编语编写程序是最佳的选择，但汇编在编写规模较大软件时 复杂性，直观性，可维护性等方面缺陷明显。综合而言，c 犯+ + 语言则是更好的 选择。 重利用现有的代码：由于c 和c + + 已经存在且被广泛应用许多年了，积累了大量 的可利用的模块和代码。比如大家所熟悉的b l a s t ，p h y l i p ，c l u s t a l 等软件都是 c 语言编写且源代码都是开放的。 功能齐全 1 2 4 b i a s t 最初的序列比对是以1 9 7 0 年n e e d l e m a n 和w u n s c h 提出动态规划算法作为依据 的，该算法是全序列比对算法，在比对中包含两个被比较序列的所有元素。其缺点是 一些局部序列相似性较高，而全序列相似性较小的序列，其同源性不易检出，因前者常 被后者的平均效应所掩盖。在具有模块性质的蛋白质比对中，这种情况更为明显。因此 在n e c d l c m a n w u n s c h 算法基础上改良产生了s m i l h w a t e r m a n 算法。它是一种局部比 对的方法，用于寻找两个被比较序列相似的片段，这样对全局相似性较小的序列，可 检出局部性比对较好的片段 如果用标准的s m i t hw a t e r r n a n ，$ 法来进行局部序列比对，将仍是非常慢的查询过 程b l a s t 算法可以大幅度提高局部比对的速度。 b l a s t 是由a l t s c h u ls f 等在1 9 9 0 年提出的，采用了启发式算法对局部匹配算法， 可以快速的对数据库中的序列进行相似性比较，且能检测只有部分相似性的序列，并 为比对结果提供统计学的评估，是现在应用最广泛的序列相似性搜索工具，特别适用 于大量的数据筛选。 b l a s t 算法主要包括了启发点查找，序列延伸，和统计三个步骤( b c d c uc t 7 黄明松中山大学硕士学位论文 a l 2 0 0 3 ) 。 b l a s t 在进行序列两两比对的时候采用了两个步骤的启发式搜索方法。b l a s t 假 设具有一定相似性的序列对之间存在着一样的小片断( w o r d s ) ，要找到具有一定相 似性的序列可以先找出这些小片断，然后再从这个小片断出发，找出具有一定相似性 的序列( a l t s c h u lc ta l ，1 9 9 0 ) 。这样，就可以省略很多不必要的搜索过程，大大的 节省了相似性序列的搜索过程，这在进行大量的数据筛选的时候是很重要的。 b l a s t 首先在两个序列中寻找具有特定长度的共有小片断，这些小片断可以是一 样的，或者是根据打分矩阵两个片断之间的得分达到某个设定的要求。这些小片断将 作为下一步展开搜索的启发点，这样就不需要从任意位点开始进行搜索，这样将会大 大的节省了第二步搜索所需要耗费的时间。第二步搜索是从启发点开始，分别向序列 的两边延伸，并根据打分矩阵给予相应的分值，直到两个序列的分值不再增加，或者 分值的最高值和分值的最低值的差异超过一定的限度，序列将停止延伸。到此为止， 就获得了一个序列匹配对，并得到了相应的匹配得分( r a ws c o r e ) 。 获得了这个序列匹配对以后，b l a s t 采用了k a r l i n a l t s c h u l 统计公式，对其进 行统计学评估，看它是否具有统计学意义，如果具有统计学意义的，该序列匹配对被 称之为高分序列匹配对( h s p ) 。根据序列的匹配得分计算出出对应的统计学参数， 如e 值，规格化分值( b i ts c o r e ) 等 b l a s t 是一个序列相似性搜索的程序包，其中包含了很多个独立的搜索程序，这 些程序是根据所要分析的对象和数据库的不同来定义的( b e x t e l le ta 1 ，2 0 0 3 ) 。 b l a s t n 是核酸序列对核酸数据库的搜索程序，它会将所输入序列和数据库中存 在的每一个条序列做相似性比对，输出数据库中与输入序列具有一定相似性的序列列 表以及序列的对位排列( s e q u e n c ea l i g n m e n t ) 。 b l a s t p 是蛋白质序列对蛋白数据库的搜索程序。输入的蛋白质序列将会和数据 库中所有的蛋白序列进行一对一的相似性比对。 b l a s t x 是核酸序列对蛋白数据库的搜索程序。它先把输入的核酸序列采用六框 翻译法翻译成六条蛋白质序列，然后再将这六条蛋白质序列对蛋白数据库中的所有序 列进行一对一的相似性比对。 t b l a s t n 是蛋白质序列对核酸数据库的搜索程序。它和b l a s t x 相反，它先将数 据库中的核酸序列六框翻译成蛋白序列，然后再跟输入的蛋白序列进行一一的比对。 8 黄明松中山大学硕士学位论文 t b l a s t x 是核酸序列对核酸数据库的搜索程序。这种搜索算法会先将输入序列和 数据库中的核酸序列分别六框翻译成蛋白质序列，然后再对这些蛋白质序列进行一一 的相似性比对，这样每次都会产生3 6 种比对。 1 2 5 肿i i p p h y l i p 是免费软件，并且可以在很多平台上运行( m a c , d o s ，u n i x v a x v m s ， 及其它) 。p h y l i p 目前已经是最广泛使用的系统发育程序。 p h y l i p 是一个包含了大约3 0 个程序的软件包，这些程序基本上囊括了系统发育 的各个方面。主要包括以下几个方面的功能软件： i ，d n a 和蛋白质序列数据的分析软件。 i i ，序列数据转变成距离数据后，对距离数据分析的软件。 i i i ，对基因频率和连续的元素分析的软件。 i v ，把序列的每个碱基，氨基酸独立看待( 碱基氨基酸只有0 和1 的状态) 时，对 序列进行分析的软件。 v ，按照d o l l o 简约性算法对序列进行分析的软件。 、r i ，绘制和修改进化树的软件。 1 3 多重序列对齐的研究背景 与序列两两比对不一样，序列多重比对( m u l t i p l ea 1 i g n m e n t ) 的目标是发现多 条序列的共性。如果说序列两两比对主要用于建立两条序列的同源关系和推测它们的 结构、功能，那么，同时比对一组序列对于研究分子结构、功能及进化关系更为有用。 例如，某些在生物学上有重要意义的相似性只能通过将多个序列对比排列起来才能识 别。同样，只有在多序列比对之后，才能发现与结构域或功能相关的保守序列片段。 对于一系列同源蛋白质，人们希望研究隐含在蛋白质序列中的系统发育的关系，以便 更好地理解这些蛋白质的进化。在实际研究中，生物学家并不是仅仅分析单个蛋白质， 而是更着重于研究蛋白质之间的关系，研究一个家族中的相关蛋自质，研究相关蛋白 质序列中的保守区域，进而分析蛋白质的结构和功能。序列两两比对往往不能满足这 样的需要，难以发现多个序列的共性，必须同时比对多条同源序列。 9 黄明松中山大学硕士学位论文 通过序列的多重比对，可以得到一个序列家族的序列特征。当给定一个新序列时， 根据序列特征，可以判断这个序列是否属于该家族。进行多序列比对后，可以对比对 结果进行进一步处理，例如构建序列的特征模式，将序列聚类，构建分子进化树等。 多重序列比对的最终日标是通过处理得到一个得分最高( 或代价最小) 的序列对比排 列，从而分析各序列之间的相似性和差异。如同处理序列两两比对一样，依然可以用 动态规划算法。 序列两两比对的动态规划算法经改进后可直接用于序列的多重比对。随着待比对 的序列数目增加，计算量和所要求的计算空间猛增。对于k 条序列的比对，动态规划 算法需要处理k 维空间里的每一个节点，计算量自然与晶格中的节点数成正比，而节 点数等于各序列长度的乘积。另外，计算每个节点依赖于其前趋节点的个数。对于k 维超晶格，前趋节点的个数等于2 l1 。因此，用动态规划方法计算多重比对的时间 复杂度为0 ( 2 “h 。，。ls 。i ) 。这个计算量是巨大的，而动态规划算法对计算空间的要 求也是很大的。假设有k 个长度n 的序列，则利用s p ( s u m - o f - p a i r s ，逐对加和) 模 型寻找最优多重序列比对算法的时间复杂度为0 ( 2 “r 1 ) ，这里k 和n 都是问题的规模。 假设有1 0 0 个长为1 万b p 多序列，既k = 1 0 0 ，n = l o k ，则使用动态规划法做多重 序列对齐的时间复杂度0 ( 2 “1 0 0 0 0 ”) ，数量级将达到le4 3 0 ( 1 0 的4 3 0 次方) 规模。 作为比较参考，主频为l o g 的高速计算机处理能力的数量级才1e1 0 ，全世界人口数 目数量级是1e1 0 ( 百亿) 规模。 所以，动态规划算法是一种最优算法，但该种算法的缺点是所需的时间和空间复杂 度高，因此在实际的序列相似性比较中很少使用动态规划算法除非所需比对序列较 少或需得到较好的比对结果在应用中有一些变通的方法。概括如下：( 1 ) 只求解规 模比较小的问题；( 2 ) 利用动态规划、分支约束等技术减小搜索空间，提高求解问题 的效率；( 3 ) 针对具体问题的特点，根据实际输入情况，设计实用求解算法，这样的 算法虽然在最坏的情况下其时间复杂度是非多项式的，但是算法执行的平均效率和复 杂度与多项式的算法相当；( 4 ) 采用近似算法或者启发式方法，如局部搜索、模拟退 火、遗传算法等。 目前对多序列比对的研究还在不断前进中，而几乎所有的近似算法和许多的启发 式算法，实际上都是在算法的计算速度和获得最佳联配结果的敏感性之间寻找一种权 衡策略。现有的大多数算法都基于渐进的比对的思想，在序列两两比对的基础上逐步 1 0 黄明松中山大学硕士学位论文 优化多序列比对的结果。进行多序列比对后可以对比对结果进行进一步处理，例如构 建序列模式的p r o f i l e ，将序列聚类构建分予进化树等等。 现今最主要的多序列比对程序有如下： c l u s t a l ：目前使用最广泛的多序列比对程序，基于渐进比对的思想，得到一系列 序列的输入，对于每两个序列进行双重比对并且计算结果。基于这些比较，计算得到 一个距离矩阵，反映了每对序列的关系，于是，基于邻近加入方法，这个矩阵被用来 计算出一个系统发生辅助树，对关系密切的序列进行加权；然后从最紧密的两条序列 开始，逐步引入临近的序列并不断重新构建比对，直到所有序列都被加入为止。 c l u s t a l w 的程序可以自由使用，在n c b i 的f t p 服务器上可以找到下载的软件包。 c l u s t a l w 程序用选项单逐步指导用户进行操作，用户可根据需要选择打分矩阵、设置 空位罚分等。e b i 的主页还提供了基于w e b 的c l u s t a l w 服务，用户可以把序列和各种 要求通过表单提交到服务器上，服务器把计算的结果用e m a i l 返回用户。 c l u s t a l w 对输入序列的格式比较灵活，可以是前面介绍过的f a s t a 格式，还可以 是p i r 、s w i s s p r o t 、g d e 、c l u s t a l 、g c g m s f 、r s f 等格式。输出格式也可以选择， 有a l n 、g c g 、p h y l i p 和g d e 等，用户可以根据自己的需要选择合适的输出格式。用 c l u s t a l w 得到的多序列比对结果中，所有序列排列在一起，并以特定的符号代表各个 位点上残基的保守性，“术”号表示保守性极高的残基位点；“”号代表保守性略低 的残基位点。 淞a ：是少数几个试图寻找最优解的算法之一，其主要思想应用c a r r i l l o l i p m a n 法，将最优解确定在比较小的范围内，然后使用d i j k s t r a 算法求解。m s a 对于规模较 小的问题可以得出比较好的比对结果，但m s a 需要较多的内存，对于规模稍大的情形， 如多于l o 条序列的序列簇，m s a 无法计算出比对结果。 m a c a w ：其关键之处就是对寻找的多重序列对准附加一个条件：所有序列至少要具 备最低程度的两两之间的相似性。这样一来使整个对准空间减少o ( n 2k 2 ) ，而剩余 的对准部分再作仔细分析并评价其统计学意义。对准时根据需要分阶段进行，首先将 对准的序列限制在某个范围之内，使执行的时间大大减少。另外在初始阶段提高序 列对准的阈值使类似值最大的那些序列区段先被检出，再使范围限制到未对准的序列 部分，降低对准的阚值，使相似性较小的区段被检出，该过程不断重复，直到得出最终 结果。 i i 黄明松中山大学硕士学位论文 使用这些软件我们将会看到，随输入的多重序列的性质不同。应用不同的方法会 得到不同程度的成功。故采用多种不同的方法进行分析，再将结果综合，是一种行之 有效的方法。一般来说，对于那些长度相仿且相似性程度较高的序列，采用自动比对 方法将会得到相当满意的结果；而当序列长度相差较大而相似性程度较低时，采用自 动方法得出的结果则不很理想。此对，手工序列编辑器就接显得十分有用。通过手工 调整，可使结果交得接近实际。故经验丰富的用户往往会选择若干个工具同时使用， 并且对最终的比对结果作手工修正以翅达到最佳效果。 1 4 进化树重建的研究背景 传统的物种分类主要是根据化石记录，解剖，形态和生理等特征来进行的。而今， 随着生化技术的发展，特别时分子生物学技术的发展，已经积累了很多的分子资料， 如核酸和蛋白质序列、免疫距离、分子杂交数据、限制性酶切多态性数据等。这些分 子资料的积累促进了利用些分子资料推断物种闯的进化关系。 b n a 序列测定技术的快速发展，使得d n a 序列的测定自动化、半自动化而成为 个常规的实验室技术。快速的d n a 测序技术敦促了人类基因组计划的开展，越来越多 生物体的基因组序列被测定，如各类病毒、细菌等低等的微生物，水稻基因组和小鼠 基因组等的测序也已经相继完成。这些测序工作积累了大量的d n a 序列数据，这些数 据都被收录到公共的基因数据库g e n b a n k 中。任何人都可以免费从g e n b a n k 这个公共 的数据库中获取相关的序列等信息，也可以将自己的铡序结果提交至这个公共数据库 ( b u r k se ta 1 ，1 9 8 5 ) 。正是因为d n a 和蛋白质的序列信息的急剧增长，使得基于分子 序列的分子进化分析快速发展。 核酸和蛋白质序列包含了进化过程中的所有信息，分子进化就是要根据这些信 息，推导出不同物种之间的相互关系。分子进化分析都是要从序列比较开始的，因为 只有进行序列比较，才能进一步推算出进化速率，进化距离等进化和系统分析的参数。 为此，就需要事先确定所比较的序列具有共同的祖先来源，即是同源序列。同源序列 的确定是进行分子进化分析的第一个步骤，基因作为具有特定功能的序列片断，考察 其同源性具有特殊的意义，也是最先受到分子进化分析家们青睐的。如今，聚合酶基 因，细胞色素酶基因，核糖体r n a 基因等多种基因已经成为分子进化分析的典型分子 标记，也有采用其他一些保守位点信息来推导分子进化树。 1 2 黄明松中山大学硕士学位论文 根据序列可构建分子进化树，进化树给出分支层次或拓扑图形，它是产生新的基 因复制或享有共同祖先的生物体的歧异点的一种反映，树枝的长度反映之间的进化距 离。根据进化树不仅可以研究从单细胞有机体到多细胞有机体的生物进化过程，而且 可以粗略估计现存的各类种属生物的分歧时间。通过分子进化树分析，为从分子水平 研究物种进化提供了新的手段，可以比较精确的确定某物种的进化地位。对于物种分 类问题，序列的分子进化树亦可作为一个重要的依据。 构建序列进化树的主要步骤是比对，建立替代模型，建立进化树以及进化树评估。 流程图如图1 - 2 所示。 多序列比对 对象 多序别比对结果 进化树 分拼结果 图1 2 序列进化分析流程 1 建立数据模型( 比对) 建立一个比对模型的基本步骤包括：选择合适的比对程序；然后从比对结果中提 取系统发育的数据集，至于如何提取有效数据，取决于所选择的建树程序如何处理容 易引起歧义的比对区域和插入删除序列( 即所谓的i n d c l 状态或者空位状态) 。 黄明松中山大学硕士学位论文 一个典型的比对过程包括：首先应用c l u s t a l w 程序，然后进行手工比对，最 后提交给一个建树程序。这个过程有如下特征选项：( 1 ) 部分依赖于计算机( 也就是 说，需要手工调整) ；( 2 ) 需要一个先验的系统发育标准( 即需要一个前导树) ；( 3 ) 使用先验评估方法和动态评估方法( 推荐) 对比对参数进行评估；( 4 ) 对基本结构( 序 列) 进行比对( 对于亲水氨基酸，推荐引入部分二级结构特征) ；( 5 ) 应用非统计数 学优化。这些特征选项的取舍依赖于系统发育分析方法。 2 决定替代模型 替代模型既影响比对，也影响建树：因此需要采用递归方法。对于核酸数据而言， 可以通过替代模型中的两个要素进行计算机评估，但是对于氨基酸和密码子数据而 言，没有什么评估方案。其中一个要素是碱基之间相互替代的模型；另外一个要素是 序列中不同位点的所有替代的相对速率。还没有一种简单的计算机程序可以对较复杂 的变量( 比如，位点特异性或者系统特异性替代模型) 进行评估，同样，现有的建树 软件也不可能理解这些复杂变量。 3 建树方法 三种主要的建树方法分别是距离、最大简约( m a x i m u mp a r s i m o n y , m p ) 和最大似 然( m a x i m u ml i k e l i h o o d ，m l ) 。最大似然方法考察数据组中序列的多重比对结果，优 化出拥有一定拓扑结构和树枝长度的进化树，这个进化树能够以最大的概率导致考察 的多重比对结果。距离树考察数据组中所有序列的两两比对结果，通过序列两两之间 的差异决定进化树的拓扑结构和树枝长度。最大简约方法考察数据组中序列的多重比 对结果，优化出的进化树能够利用最少的离散步骤去解释多重比对中的碱基差异。 距离方阵方法简单的计算两个序列的差异数量。这个数量被看作进化距离，而其 准确大小依赖于进化模型的选择。然后运行一个聚类算法，从最相似( 也就是说，两 者之间的距离最短) 的序列开始，通过距离值方阵计算出实际的进化树，或者通过将 总的树枝长度最小化而优化出进化树。用最大简约方法搜索进化树的原理是要求用最 小的改变来解释所要研究的分类群之间的观察到的差异。最大似然方法评估所选定的 进化模型能够产生实际观察到的数据的可能性。进化模型可能只是简单地假定所有核 苷酸( 或者氨基酸) 之间相互转变的概率一样。程序会把所有可能的核苷酸轮流置于 进化树的内部节点上，并且计算每一个这样的序列产生实际数据的可能性( 如果两个 姐妹分类群都有核苷酸“a ，那么，如果假定原先的核苷酸是“c ，得到现在的“a ， 1 4 黄明松中山大学硕士学位论文 的可能性比起假定原先就是w 的可能性要小得多) 。所有可能的再现( 不仅仅是比较 可能的再现) 的几率被加总，产生一个特定位点的似然值，然后这个数据集的所有比 对位点的似然值的加和就是整个进化树的似然值。 4 进化树搜索 单一的进化树的数量会随着分类群数量的增长而呈指数增长，从而变为一个天文 数字。由于计算能力的限制，现在一般只允许对很小一部分的可能的进化树进行搜索。 具体的数目主要依赖于分类群的数量、优化标准、参数设定、数据结构、计算机硬件 以及计算机软件。 有两种搜索方法保证可以找到最优化的进化树：穷举法和树枝跳跃法( b b ) 。对 于一个很大的数据集，这两种方法都很不实用。对分类群数量的限制主要取决于数据 结构和计算机速度，但是对于超过2 0 个分类群的数据集，b b 方法很少会得到应用。 穷举法要根据优化标准，对每一个可能的进化树进行评估。b b 方法提供一个逻辑方 法，以确定那些进化树值得评估，而另一些进化树可被简单屏蔽。因此b b 方法通常 要比穷举法快得多。 绝大多数分析方法都使用“启发式”的搜索。启发式现搜索出相近的次优化的进 化树家族( “岛屿”) ，然后从中得到优化解( “山顶”) 。不同的算法用不同程度的精确 性搜索这些岛屿和山顶。最彻底也是最慢的程序( t b r ，t r e eb i s e c t i o n r c c o n n e c t i o n ，