（计算机应用技术专业论文）多叉进化树构建方法的研究与实现.pdf

摘要 1 摘要 分子系统发育分析是生物信息学中的重要研究领域，它的主要研究手段是从 一组同源的d n a 或蛋白质序列出发，计算各个序列之间的进化距离，从而得到反 映物种进化关系的进化树。进化树通常是一棵二叉树：树的叶结点，代表了某个 具体序列；树的拓扑结构表现了各物种之间的亲缘关系远近；树的分枝长度刻画 了进化距离的大小。构建进化树的方法主要分为三类，即距离矩阵法、最简约方 法和极大似然法。其中，距离矩阵法以结构简单、具有良好的理论基础等特点获 得了广泛的应用。 但是，研究指出一些基于距离矩阵的建树方法在某些情况下会产生拓扑结构 不惟一的进化树结果，即进化树的具体拓扑结构会根据同源序列输入算法的顺序 不同而发生变化。不加权算术平均组对法( u n w e i g h t e dp a i r - g r o u pm e t h o du s i n g a r i t h m e t i ca v e r a g e s ，以下简称u p g m a ) 是一种比较常见的距离矩阵法，该方 法也存在上述问题。虽然该方法被设计为针对同一组序列数据产生惟一的进化树 结果，但是可以证明在算法迭代过程中，如果距离矩阵中出现最小元素不惟一的 情况，则算法产生的进化树拓扑结构是随着序列输入顺序的不同而变化的。这一 现象为系统发育分析结果的解释带来了困难在多个进化树结果中，显然只能 有一棵进化树反映了真实的物种进化关系，但是在出现多个结果时u p g r a 并不能 判断哪一棵树的拓扑结构是正确的。并且大多数流行的分子系统发育分析软件并 没有处理u p g r a 产生的进化树不惟一的问题。通常仅根据算法实现方式的不同， 给出了其中一种拓扑结构。 针对以上问题，本文详细分析了u p g 姒产生不惟一结果的原因，在此基础上 提出并实现了u p g m a 的一种改进算法，即不加权算术平均组群方法( u n w e i g h t e d m u l t i g r o u pm e t h o du s i n ga r i t h m e t i ca v e r a g e s ，以下简称u m g m a ) 。u i i g m a 是 u p g m a 的一种扩展，而u p g m a 可以看作u m g m a 的一个特例。在迭代计算过程中， u p g m a 总是选取距离矩阵中最小的元素对应的一对序列生成新的分类群单元。而 u m g m a 则通过引入距离容差参数t ，将所有小于t 的元素对应的序列作为生成新 分类群单元的基础。该方法在一次迭代中可以产生多个新的分类群单元，因此其 北京工业大学工学硕士学位论文 进化树结果可能是多叉树。在u p g m a 结果不惟一的情况下，各种可能的二叉树结 果在u m g m a 中被综合构建成棵惟一的多叉树，从而解决了惟一性的问题；而在 u p g m a 结果惟一的情况下，取距离容差参数t 等于零，u - i g m a 得到的结果将与 u p g m a 的结果完全一致。基于实际数据的进化树构建实验表明，u m g m a 不仅能够 产生结果惟一的进化树，而且通过选择不同的容差参数t ，还能产生不同层次的 进化树。这意味着在大规模系统发育分析中，u m g m a 可以通过调整t 的值，不断 突出进化树的整体脉络。 本文的课题研究工作中还实现了种包含完整u m g m a 算法实现以及传统 u p g m a 方法实现的分子发育分析软件一一m u l t i t r e e 。该软件是一个基于 m i c r o s o f t n e tf r a m e w o r k2 0 平台构建的客户端应用，其中使用w e b s e r v i c e 完成多序列比对功能，并提供一套基本的分子进化分析流程，包括：多序列比对 结果编辑、距离矩阵计算以及多种方法构建进化树，并以多种风格显示进化树。 m u l t i - t r e e 软件系统有别于大多数传统的分子发育分析工具软件包，它具有友 好的富客户界面，支持多语言的界面显示。系统采用了基于插件的程序结构，从 指定位置的一组程序集中动态获取系统的界面元素与业务逻辑，具有良好的扩展 性与可维护性。 关键词分子系统发育分析；距离矩阵法；惟一性；多叉树 a b s t r a c t a b s t r a c t m o l e c u l a rp h y l o g e n e t i ca n a l y s i si so l l eo ft h em o s ti m p o r t a n tf i e l d so f b i o i n f o r m a t i c s ，t h em a i nt a s ko fw h i c hi st or c c o u s t r u c tap h y l o g e n e t i ct r e ef r o ma g r o u po fh o m o l o g o u sd n ao rp r o t e i ns e q u e n c e s ，s h o w i n gt h ee v o l u t i o n a r y r e l a t i o n s h i pb e t w e e nt h es p e c i e so ft h o s es e q u e n c e s u s u a l l y , a p h y l o g e n e t i ct r e ei sa b i n a r yt r e e ，i nw h i c ht h el e a fn o d e ss t a n df o rt h es p e c i e so rt h eo r g a n i s m s ，t h et r e e t o p o l o g yi n d i c a t e st h ep h y l o g e n e t i cr e l a t i o n s h i p ，a n dt h el e n g t ho f b r a n c h e sf i g u r eo u t t h ee v o l u t i o n a r yd i s t a n c eb e t w e e nt h es p e c i e sa n dt h e i rc o m m o na n c e s t o lt h e r ea r c t h r e em a i nt y p e so fm e t h o d st or e c o n s t r u c tp h y l o g e n e t i ct r e e s ：d i s t a n c em a t r i x ， p a r s i m o n ya n dl i k e l i h o o d d i s t a n c em a t r i xm e t h o dh a sw i d ea p p l i c a t i o n sb e c a u s eo f i t ss i m p l i c i t ya n ds o l i dt h e o r y h o w e v e r , i th a sb e e nr e p o r t e dt h a ts o m ed i s t a n c em a t r i xm e t h o d s ，e g u n w e i g h t e dp a i r - g r o u pm e t h o du s i n ga r i t h m e t i ca v e r a g e s ( u p g m a ) ，m a yp r o d u c e m u l t i p l ep h y l o g e n e t i ct r e e sr e dt r e e s ) g i v e nas i n g l es e to f h o m o l o g o u ss e q u e n c e s i nc e r t a i nc a s e s ，d e p e n d i n go nt h ei n p u to r d e ro f t h es e q u e n c e s a l t h o u g hu p g m ai s d e s i g n e dt op r o d u c es i n g l en ：s i ts o m e t i m e sg e n e r a t e st i e dt r e e si nc a s e s t h a tt h e r e a r em o r et h a no n e p a i r so f s e q u e n c e s w i t ht h em i n i m a ld i s t a n c e b e c a u s ei ti sn o tc l e a r f o ru p g m at od e t e r m i n ew h i c ho f s u c hp a i r ss h o u l db es e l e c t e d t oi n t e r p r e t d i f f e r e n tr e s u l t sf r o mt h es a m eg r o u po fs e q u e n c e si sd i f f i c u l t , a n dm o s tp o p u l a r s o f i w a r e sf o rp h y l o g e n e t i ca n a l y s i sd on o th a n d l et h i sp r o b l e mb u t j u s tt og i v ea r a n d o mr e s u rd e p e n d i n go nt h es p e c i f i ci m p l e m e n t a t i o n i no r d e rt os o l v et h e t i e dt r e e s p r o b l e m , w ef i r s ta n a l y z et h er e a s o nf o ru p g m a t od e r i v em u l t i p l er e s u l t ss o m e t i m e si nd e t a i l ，a n dt h e np r e s e n ta ni m p r o v e dm e t h o d f o ru p g m a ，n a m e l y , u n w e i g h t e dm u l t i - g r o u pm e t h o du s i n ga r i t h m e t i ca v e r a g e s ( u r m g m a ) u m g m ae x t e n d su p g m ai nd e a l i n gw i t ht h em i n i m a le l e m e n t si n d i s t a n c em a t r i x i nf a c t , i tc h o o s e sa l lt h ee l e m e n t sl e $ st h a nat o l e r a n tp a r a m e t e rtt o c o n s t r u c tn e wo t u s i nad i f f e r e n tw a yf r o mu p g m a i th a sb e e ns h o w nt h a t u m g m a m a yp r o d u c eau n i q u em u l t i f u r c a t i n gt r e ew h i c hi n t e g r a t e sa l lt h ep o s s i b l e t i e du p g m at r e e s i nc a s eu p g m a p r o d u c e sau n i q u et r e e ，t h eu m g m at r e e i sa l w a y st h e 韶l h l ea st h ec o r r e s p o n d i n gu p g m a t r e e e x p e r i m e n t s0 1 1r e a ls e q u e n c e s h a v es h o w nt h a tu m g m ac a nn o to n l yp r o d u c ep h y l o g e n e t i ct r e e sw i t hau n i q u e i u 北京工业大学工学硕士学位论文 t o p o l o g y , b u ta l s op r o d u c et r e e sa td i f f e r e n tl e v e l s t h i sm e a n st h a tu m g m a c a n 孕a d u a l l ym a k ec l e a rt h eo v e r a l l s t r u c t u r eo ft r e e sb ya d j f u s t i n gt h et o l e r a n tp a r a m e t e r x i nt h el a r g e - s c a l ep h y l o g e n e t i ea n a l y s i s i nt h i st h e s i s ，w ea l s op r o p o s ean e wm o l e c u l a rp h y l o g e n e t i ca n a l y s i ss y s t e m m u l t i t r e e ，w h i c hi n t e g r a t e sb o t hu m g m a a n du p g m a t h es y s t e mi sar i c hc l i e n t a p p l i c a t i o nb a s eo nm i c r o s o f t n e tf r a m e w o r k2 0 ，w i t haw e bs e r v i c es u p p o r tt o p e r f o r mm u l t i p l es e q u e n e e sa l i g n m e n t u s i n gi t , o n ec a nd os o m e b a s i cp h y l o g e n e t i c a n a l y s i s ，i n c l u d i n ga l i g n m e n t o fs e q u e n c e s ，c a l c u l a t i o no fd i s t a n c em a t r i x , c o n s t r u c t i o no fp h y l o g e n e t i ct r e e s ，a n ds oo i l c o m p a r e dw i t hm a n yo t h e rs o t h v a r e t o o l sf o rp h y l o g e n e t i ca n a l y s i s ，t h em u l t i - t r e es y s t e mh a sag o o da n df r i e n d l yu s e r i n t e r f a c e ( u dt h a ts u p p o r t sm u l t i l a n g u a g e s ，a n d i tc a nb ee a s i l ye x t e n d e da n d m a i n t a i n e di nt h ep l u g - i ns t r u c t u r et h a tc a nl o a du ia n db u s i n e s sl o g i cc o m p o n e n t sa t r u n t i m e k e y w o r d sm o l e c u l a rp h y l o g e n e t i ca n a l y s i s ；d i s t a n c em a t r i xm e t h o d ；u n i q u e n e s s ； m u l t i f u r c a t i n gt r e e i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书面使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 釜：兰生日期：三塑z ：么争 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 繇缉：纽。导师繇耄z 避隰血丑纱 第1 章绪论 i 第1 章绪论 分子系统发育分析是生物信息学的重要分支，主要用于研究生物体在分子水 平的进化式样、方向、速率以及各种分子机制对基因和基因组的结构与功能的影 响。构建代表种系进化关系的进化树是分子系统发育分析的主要研究手段。本章 首先阐述相关领域的背景知识以及国内外研究现状，然后简述本文的主要工作内 容。最后介绍了本文各章节的主要内容。 1 1 课题背景 系统发育学是生物学中一门相对较早的科学，它研究的是生物进化关系的历 史。系统发育分析方法包括表现型分类法与进化分支法。在系统发生学的研究中， 最常用的表现进化关系的方式就是系统树。系统树由代表生命个体、物种或类属 的结点组成。系统树的分支结构则代表了分类单位之间的进化关系。通过比较不 同物种的基因信息从而得到它们之间的进化关是分子系统发生学的主要目的。 在过去十年中，随着分子生物学的不断发展以及生物信息学的兴起，对于系 统发育分析研究也进入了分子进化的研究水平，产生了一套完整的以同源核酸或 蛋白质序列为研究材料的分子系统发育分析理论与方法叫。 构建进化树是系统发育分析的主要工作目标之一，在分子系统发育分析领域 中，该工作是通过比较一组生物的同源d n a 或蛋白质序列完成的。主要包括以下 四个步骤： 序列比对 确定核苷酸替换模型 创建系统树 评估系统树的可靠性 构建进化树的目的是重塑分类群( 物种) 之间的系统发育关系，并将其用进 化树的形式加以描述和展现：进化树通常是一棵二叉树嘲，树的叶结点，代表了 某个序列的来源物种：树的拓扑结构表现了各物种之间的亲缘关系远近；树的分 枝长度刻画了进化距离的大小。通常进化树可以分为有根树和无根树两类，前者 可以通过向无根树的分类群中添加已知亲缘关系较远的分类群得到，根节点一般 被放置在结果进化树中新产生的分支上。 北京工业大学工学硕士学位论文 系统发育分析与进化树构建工作是生物信息学研究中的一个重要领域，根据 进化树的拓扑可以研究病毒、细菌以至于大型哺乳动物等各种有机体以及生物蛋 白质分子的之间生物进化关系；通过进化树的支长计算还可以从理论上近似估计 分类群的分化时间。构建进化树的意义主要可以分为理论意义与实际应用两个方 面。从理论意义上来看，它有助于了解物种进化历史，为生物学物种分类提供可 靠依据。例如在探讨人类的起源、h i v 病毒的来源于进化关系等问题上，分子系 统发育分析工作都有许多成功的应用“1 ；从实际应用价值来看，该工作在预测蛋 白质、d n a 分子的高级结构以及基因表达过程、预测配体结构、辅助药物设计、 构建多序列比对先导树等方面均有重要作用。 在分子系统发育方法被发展出来以前，对于系统树的重建工作主要是通过研 究化石来进行的。1 。但是化石是如此的零散且不完整，只是大多数研究者转向形 态比较学和比较生理学的方法。通过后两种途径，进化学家已经得到有机体进化 关系的主要框架。然而形态和生理形状的进化与比较是非常复杂并且容易受到主 观判断影响的，以至于无法用以产生一幅进化历史的清晰图像。不同学者在构建 进化树的细节上几乎总是存在争议。而分子系统发育分析的进展大大改变了这种 局面，不论是细菌、植物还是各种动物，其d n a 分子均由腺嘌呤( a ) 、胸腺嘧啶 ( t ) 、胞嘧啶( c ) 、鸟嘌呤( g ) 这四种碱基组成，r n 分子与蛋白质分子也具 有类似性质。因此通过分子系统发生学的方法可以对所有物种进行比较与研究， 这在传统方法中是不可能做到的“1 。 当然从另一方面来说，现代现存物种的d n a 或蛋白质序列中所保存的进化历 史信息依然不够完整，分子系统发生学方法通常也仅仅通过分子序列数据给出最 可能的推断。通过改进建树算法，从一系列备选的结果中得到最可信的进化树将 是一个极具研究价值的方向”。 1 2 国内外研究概况 已有研究指出“1 ，没有任何一种已知建树方法适用于所有的系统发育分析情 况，并且现有算法并不能修正因为序列同源性验证方面的问题外来的影响。因此 构建系统树的每一个步骤的准确性都对整个系统发育分析的结果具有重要影响。 进行分子系统发育分析的一个最为基本的假设即是，待分析的不同物种的d n a 或 蛋白质序列必须是同源的，即需要保证待分析的序列之间确实具有某种分子水平 2 第1 章绪论 上的进化关系存在，否则任何分析结果都将是没有意义的。 构建进化树的主要过程包括：获取同源序列数据；确定进化模型；进行多序 列比对；根据比对结果提取信息；选择建树算法与参数构建进化树0 1 。构建系统 树的常用方法可以分为三类，即距离矩阵法、最简约方法以及极大似然法“1 所 有基于距离矩阵的方法都需要首先进行多序列比对，并选取适合的进化距离模 型，通过两两比较分类群的序列，得到一个反映序列之问差异程度的距离矩阵。 在此基础上，通过建立在不同的优化原则和假设基础上的各种建树算法完成进化 树的构建。而最简约方法和极大似然法是基于符号或者特征的建树方法，这两种 方法并不需要规定距离测度并计算距离矩阵，而是直接通过各分类群序列的碱基 或氨基酸顺序来构建系统树，通常而言其计算量要比距离矩阵法大很多，对于大 种系发育分析而言距离矩阵法是比较常用的方法埘。 1 2 1基于距离的建树方法 构建距离矩阵时，最简单的距离度量是p 距离，即除去两个序列的插入和丢 失的位点之后，单位长度上的碱基或氨基酸差异率。由于p 距离没有考虑到平 行突变和回复突变等因素所以随着时问的推移序列问的差异有被低估的趋势，这 一点在利用d n a 序列构建系统树时尤为明显。因此对于蛋白质序列，通常使 用p c 距离( 泊松校正距离) 或r 距离来获得更准确的序列差异度量；而对于d n a 序列，由于只有四种碱基存在，需要选择适合的核苷酸替代模型将序列中的碱基 替换比率信息加入到距离测度当中才能得到更好的结果。常用的替换模型包括 j u k e s - c a n t o r 模型、k i m u r a 模型、t a m u r a - n e i 模型“1 等等。 在得到距离矩阵之后，即可应用距离法构建系统树。常用的距离法包括：不 加权算术平均组对方法( u n w e i g h t e dp a i r - g r o u pm e t h o du s i n ga r i t h m e t i c a v e r a g e s ，u p g m a ) 、最小进化法( m i n i m a le v o l u t i o nm e t h o d ) 、邻接法 ( n e i g h b o r - j o i n i n gm e t h o d ，n j ) 以及f i t c h - m a r g o l i a s h 方法等旧。 u p g i 雌是一种来源于数值分类学中构建表征图的方法，最早于1 9 5 8 年由 s o k a l 等人提出“1 。应用该方法的基本假设是各分类群的进化速率相同，因此从 祖先节点分离的两个分类群到该祖先节点的分支长度相等。u p g m a 首先将矩阵中 最小距离的两个分类群聚类，并计算新分类群与剩余分类群之间的距离得到新的 距离矩阵，至此完成算法的一轮计算，重复此过程，最终会得到一个以所有原始 北京工业大学工学硕士学位论文 分类群为叶节点的系统树。 n e i 等( 1 9 8 3 ) 模拟了不同的建树方法，发现当沿树上所有分枝的突变率相 同时，u p g m a 一般能够得到较好的结果。1 。而另一些模型研究( 如k i m 和 b u r g m n ，1 9 8 8 ) 认为当各分枝的突变率不相等时，u p g m a 的结果不尽人意。这是 由于u p g m a 假定进化树的所有分枝突变率为常数( 这也就是不加权的含义) 。 f i t c h 和m a r g o l i a s h 所发展的方法去除了这一假定。但是f i t c h 和 m a r g o l i a s h 承认他们的方法所得到的拓扑结构可能是不正确的，并建议考查其 它建树方法所得到的拓扑结构。 最小进化法( m e ) 是另一种基于距离矩阵的建树方法，其基本假设是：在所 有可能的拓扑结构中，真实树对应的进化过程所需的突变或替代次数最少，即系 统树的分支之和具有最小值。该方法通过公式：s2 岛来计算系统树分支的 和，并遍历所有可能的系统树拓扑结构，找到其中具有最小s 值的系统树。其 中q 是对各个分支的估计，其具体数值可以通过支长的最小二乘估计获得。 r z h e t s k y 和n e i 证明了从无偏的进化距离获得的真实树的s 期望具有最小值 。这是一种优良的统计性质，但是由于该方法需要处理所有可能的拓扑结构， 5 结点的无根树具有1 5 种可能拓扑，1 0 结点时就有2 0 2 7 0 2 5 种可能拓扑，因此当分 类群数量增大时该方法并不实用。 为了解决她法的计算量问题，s a i t o u 和n e i 提出了邻接法( n j ) ，该方 法放弃寻找全局最优解，而是以一棵星形树作为初始状态，假定x 为所有分类 群的共同祖先( 如图1 - 1 所示) ，可计算出星形树的分支长度总和：s o ， 2 3 8 4 6 2 8 图1 - 1n j 树的状态变化 f i g 1 - 1s t a t et r a n s f o m a t i o no fn jt r e e 4 4 6 第1 章绪论 假设以将分类群单元1 、2 合并为一对邻居( 图1 右图) ，则可以得到s 。： 由于任取两个分类群都有可能成为一对邻居，故此算法检查所有可能的组合并以 s 值最小的拓扑为起始状态进行下一轮的算法。这样直到所有分类群结合完毕。 由于建树过程中仅关注拓扑结构，所以最后需要使用最小二乘等方法进行分支长 度的估计“。 1 2 2 最简约方法 e c k 和d a y h o f f 最早使用最大简约法分析氨基酸序列重建系统发育树。此 后f i t c h 和h a r t i g a n 发展了该方法“1 。最大简约法的基本假设是：对系统发 生分析来说，最优的系统树应当在整个进化过程中，全部位点的最小核苷酸替代 数之和最小。这个假设与基于距离的最小进化法很相似，但是该方法并没有使用 距离测度来描述序列间的差异，而是对每个位点进行检查，从各种可能的拓扑中 找到替换次数最少的那些结果。假定四条序列i ，j ，k ，1 某一位点上的碱基如 下： i ：a j ：a k ：t 】：g 在该位点上，不同的可能拓扑以及不同的祖先序列推断将产生不同的最小替 代数的记数。m p 法对所有拓扑的在每一位点的情况进行计算，找到各位点替代 数总合最小的拓扑作为最优树。通常m p 方法会产生一些具有不同拓扑的等价结 果，由于祖先序列信息的缺失，每一种拓扑都有可能是真实树，因此需要通过严 格一致树、多数一致树、自展一致树等方法来确保结果的惟一性嘲。 t 图1 _ 2 三种可能拓扑中的最小替换数计算 f i g 1 - 2c o u n t i n gm i n i m a ls u b s t i t u t i o n so ft h r e ed i f f e r e n tt o p o l o g i e s 5 k jk冰 北京工业大学工学硕士学位论文 当分类群较少时，使用m p 方法可以找到全局最优树：但是当分类群增多时， 与m e 等需要搜索所有拓扑的方法一样艘方法会遇到性能问题，因而通常采用 分支限界、启发式搜索等搜索策略来找到局部最优解。 最大简约法较少涉及遗传假设，它通过寻求物种间最小的变更数来完成的； 而最大似然法对于假设的模型有巨大依赖性，计算量较大，但为统计推断提供了 基础。用最大简约方法搜索进化树的原理是要求用最小的改变来解释所要研究的 分类群之间的观察到的差异。 1 2 3 极大似然法 f e l s e n s t e i n ( 1 9 8 1 ) 将最大似然法用于系统树的构建。k i s h i n o 等( 1 9 9 0 ) 将其用于蛋白质序列数据的分析中。最大似然法的基本假设包括：1 不同的性 状进化是独立的：2 物种发生分歧后进化独立，即不存在种问交流等因素的影 响。位点的似然值是通过计算特定的核苷酸替代模型中某个位点每种可能被取代 的概率之和得到的，因为前述的假设，各位点的进化过程并无关联，故此将所有 位点似然值相乘就得到系统树的似然值“”。 以f e l s e n t e i n 替代模型为例计算位点的核苷酸替代概率，假定某位点的核 苷酸为i ，分枝m 上的核苷酸替代数为vm 时，核苷酸i 在整个序列中的相对频 率为g i ，该位点变为核苷酸j 的概率为： 删_ 嚣一留 小- ， m l 法对最优树的搜索有两种策略：一是对所有可能树的似然值对比，找出最 大值：二是对树的似然函数最大化，估算分枝长度、核苷酸频率、替代速率等未 知参数，从而确定树的拓扑结构o “。 极大似然法评估所选定的进化模型能够产生实际观察到的数据的可能性。具 体方法为考察序列的多重比对结果，优化出拥有一定拓扑结构和分枝长度的进化 树，该进化树能够以最大的概率获得当前的多重比对结果。极大似然法需要考察 原始数据中所有序列两两比对的结果，通过序列两两之间的差异决定进化树的拓 扑结构和树枝长度。最大简约方法考察数据组中序列的多重比对结果，优化出的 进化树能够利用最少的离散步骤去解释多重比对中的碱基差异“1 。 6 第1 章绪论 此外还有很多非传统的建树方法，例如，基于q u a r t e t s 的建树方法、基 于h a d a m a r d 结合法的建树方法、基于人工智能的建树方法( s c r r a ) 、基于全 基因组序列分析的建树方法等等。 1 2 4 建树方法的特点与比较 对近缘大种系进行系统发生分析时，本文所述的各种方法所构建的系统树往 往具有相似的拓扑。但在通常应用这些方法所构建的系统树会存在局部的拓扑差 异。u p ( ；m a 法在不同种系间进化速率有较大差异时往往会得出错误的拓扑结构， 而且当序列的差异较小时，由于距离矩阵中最小元素不惟一，产生的系统树拓扑 会随序列输入顺序变化而变化。n j 法的运算速度最快，但该算法在每次迭代中 仅搜索最近邻居配对，对其他可能的配对不加考虑，最终只生成单一的最优树， 可能会遗漏一些拓扑结构更合理的次优树“”。同时也有可能出现不惟一的系统树 结果。通常的解决办法是在查找最优树时，使用n j 法预先生成一棵树，并以此 为基础查找相似的拓扑结构，以期待获得比n j 树更符合最小进化则的系统树。 m e 法从所有可能的进化树中挑选树长最短的作为最优树，是基于距离的建树方 法中相对较好的方法。关于u p g m a 与n j 法的结果不惟一的问题，可以通过类 似于肝法中一致树的多叉树形式来解决“1 ，不同的是，这种多叉树是在建树过 程中根据指定阈值一次结合多个分类群获得的。应当指出，距离法在从序列数据 生成距离矩阵时会丢失一些进化信息，事实上各种d n 替换模型以及距离度量 的改进都在试图将更多的生物学的背景信息加入到距离矩阵中。而简约法是一种 不依赖任何进化模型的统计方法。但简约树的分支完全决定于所有重建祖先序列 中的最小突变数，而突变是否按照事先约定的核苷酸最少替代的途径进行是不得 而知的，单一的突变图谱可能会得出不合理的错误结论。因此，当序列在单位位 点上核苷酸替代数相对较大，即是分类群序列间的亲缘较远时，肝法则极可能 得出具有错误拓扑的系统树。最大似然法是一种能够完全利用序列数据的系统发 生信息的建树方法，考虑了所有可能的突变概率。但是最大似然法构建的系统树 高度依赖于核苷酸替代模型的选取“1 。不同的位点核苷酸替代速率不一致，在核 苷酸替代一般模型中包含了反映进化过程的参数。但并非替代模型越复杂，结果 就越理想。拓扑的正确性和支长的估计精确程度似乎无法同时被满足。此外在分 类群较多时，最大似然法的性能是所有方法中最差的。 7 北京工业大学工学硕士学位论文 除上述各种建树方法以外，近年来还发展出基于全基因组的建树方法、基于 序列高级结构的建树方法、基于相对熵原理的建树方法、利用古d n a 序列重建 系统树的方法、贝叶斯推断法等等方法n 1 。总的来说，随着系统发生学的广泛 应用与分子生物学的研究深入，会产生更多的建树方法来适应不同的研究目的。 如何加强算法的理论基础与处理大规模数据集的能力将成为系统发生学的研究 趋势。 1 3 本文的主要研究工作 通过上一节的讨论，我们知道构建进化树的方法主要分为三类：距离法、最 简约方法和极大似然法。其中，距离矩阵法以结构简单、具有良好的理论基础等 特点获得了广泛的应用。但是，研究指出一些基于距离矩阵的建树方法在某些情 况下会产生拓扑结构不惟一的进化树结果，即进化树的具体拓扑结构会根据同源 序列输入算法的顺序而发生变化。不加权算术平均组对法( u n w e i g h t e d p a i r - g r o u pm e t h o du s i n ga r i t h m e t i ca v e r a g e s ，以下简称u p g 姒) 是一种比 较常见的距离矩阵法，该方法也存在上述问题“”。虽然该方法被设计为针对同一 组序列数据产生惟一的进化树结果，但是可以证明在算法迭代过程中，如果距离 矩阵中出现最小元素不惟一的情况，则算法产生的进化树拓扑结构是随着序列输 入顺序的不同而变化的。这一现象为系统发育分析结果的解释带来了困难在 多个进化树结果中，显然只能有一棵进化树反映了真实的物种进化关系，但是在 出现多个结果时u p g e 4 并不能判断哪一棵树的拓扑结构是正确的。并且大多数流 行的分子系统发育分析软件并没有处理u p g m a 产生的进化树不惟一的问题。通常 仅根据算法实现方式的不同，给出了其中一种拓扑结构。 针对以上问题，本文详细分析了u p g m a 产生不惟一结果的原因，在此基础上 提出并实现了u p g p “a 的一种改进算法，即不加权算术平均组群方法( u n w e i g h t e d m u l t i - g r o u pm e t h o du s i n ga r i t h m e t i ca v e r a g e s ，以下简称u m g m a ) 。u m g m a 是 u p g m a 的一种扩展，而u p g m a 可以看作u m g m a 的一个特例。在迭代计算过程中， u p g h i a 总是选取距离矩阵中最小的元素对应的一对序列生成新的分类群单元。而 u m g m a 则通过引入距离容差参数t ，将所有小于t 的元素对应的序列作为生成新 分类群单元的基础。该方法在一次迭代中可以产生多个新的分类群单元，因此其 进化树结果可能是多叉树。在u p g m a 结果不惟一的情况下，各种可能的二叉树结 8 第1 章绪论 果在u m g 姒中被综合构建成一棵惟一的多叉树，从而解决了惟一性的问题：而在 u p g m a 结果惟一的情况下，取距离容差参数t 等于零，u m g m a 得到的结果将与 u p g r a _ 的结果完全一致。基于实际数据的进化树构建实验表明，嗍凇不仅能够 产生结果惟一的进化树，而且通过选择不同的容差参数t ，还能产生不同层次的 进化树。这意味着在大规模系统发育分析中，u m g b i a 可以通过调整t 的值，不断 突出进化树的整体脉络。 本文的课题研究工作中还实现了一种包含完整u m g k i a 算法实现以及传统 u p g m a 方法实现的分子发育分析软件一一m u l t i - t r e e 。该软件是一个基于 m i c r o s o f t n e tf r a m e w o r k2 0 平台构建的客户端应用，其中使用w e b s e r v i c e 完成多序列比对功能，并提供一套基本的分子进化分析流程，主要特性包括： 使用第三方提供的w e b s e r v i c e 进行多序列比对； 序列比对结果的编辑； 基于p 距离、j u k e s - c a n t e r 距离以及编辑距离的距离矩阵计算； 使用标准的u p g m a 方法构建进化树； 使用l r m g m a 方法构建进化树； 使用t r i a n g l e 、r e c t a n g l e 、r 8 d i u s 等多种风格显示进化树； 显示进化树的分支长度比例尺； 支持英文、简、繁体中文等多种语言的用户界面： 支持系统插件： m u l t i - t r e e 软件系统有别于大多数传统的分子发育分析工具软件包，它具有 友好的富客户界面，支持多语言的界面显示。系统采用了基于插件的程序结构， 从指定位置的一组程序集中动态获取系统的界面元素与业务逻辑，具有良好的扩 展性与可维护性。 1 4 文章结构 第一章简要介绍了分子系统发与分析的背景以及构建进化树的理论意义与 实际作用。然后介绍了一些已有的进化树构建方法，并对其各自特点做了简要分 析。最后指出u p g m a 存在的闯题并重点讲述了本课题所完成的工作内容。 第二章介绍u p g m a 的主要思想和算法实现步骤，指出了算法结果不惟一的 问题及其表现形式，通过实际数据具体分析了造成这种现象的原因。 9 北京工业大学工学硕士学位论文 第三章提出了u p g m a 的一种改进算法u m g 4 a ，详细描述了算法的思想以及具 体步骤。并通过实验数据验证了其结果的惟一性。 第四章详细介绍m u l t i t r e e 分子进化分析软件的设计与实现，其中包括了 u m g m a 的一种实现。 第五章对全文进行总结并展望了未来工作。最后是参考文献、攻读硕士学 位期间发表的学术论文和致谢。 1 0 第2 章不加权算术平均组对法介绍 第2 章不加权算术平均组对法介绍 在第一章中我们提到不加权算术平均组对法( u p g m a ) 是一种基本而重要的 构建进化树的方法。但是在某些情况下该算法可能产生不惟一的结果。其具体表 现是系统发育分析所得到的进化树的具体拓扑结构会根据同源序列输入算法的 顺序不同而发生变化。本章首先讨论了距离建树算法的一般过程。然后详细描述 了u p g m a 方法的基本步骤，并分析了出现结果树拓扑不惟一现象的原因。最后提 到了传统建树算法得到的二叉树结果的一些其它问题。 2 1 距离矩阵法构建进化树的基本过程 u p g m a 法是距离建树方法的一种，首先让我们来讨论一下距离建树算法的一 般流程。 2 1 1 构建进化树 构建进化树的第一步工作是选取来自于不同物种( 个体) 的同源核苷酸序列。 目前，分子数据的大量涌现为系统发生分析提供了丰富的素材，但并非所有的数 据都适合对特定问题的分析，在构建系统树时要求事先作出一个优先决定：哪些 数据是合理的，哪些是不合理的。由于事先并不知道真实的进化关系，若选取分类 群过少，则有可能遗漏一些关键的分类群，分析结果将十分粗糙，甚至是错误的。 因而需要在原有基础上增加一些额外的分类群，这样可以消除“长枝吸引”，提高 分子系统树的可靠性，并抵消非同源相似或误解带来的影响；然而分枝长度估计 偏倚也会随分类群的增加而放大，当选取的进化模型能无偏倚地调节进化力( 如 突变) 时能减弱这种影响。不过，每增加一个分类群，就会导致内部分枝的增加， 对内部分枝不一致估计的可能性也增大，如果对进化问题的研究不需要大量的数 据时，最好选取少些，而并非是分类群越多则越接近“真实树”。在甄选分类群时 还依赖于比较解剖、个体发育以及化石记录的背景知识。对于分子性状而言，序 列长度过短则不能全面地反映一个基因或基因组的进化情况，但序列越长，也越 可能得出错误的拓扑结构。 从已知的生物序列中能推断各个物种间的进化历史，按照一定的遗传模型， 把任意两个序列间的进化历史转化成数字，就得到两两之间的进化距离，把所有 北京工业大学工学硕士学位论文 的距离用矩阵的形式表示出来，就得到了距离矩阵。根据距离矩阵我们最后将构 建出一棵进化树，这里先介绍一下进化树的概念和专用术语。 进化树通常是一棵二叉树，它分有根( r o o t e d ) 树和无根( u n r o o t e d ) 树。有 根树反映了树上物种或基因的时问顺序，而无根树只反映分类单元之间的距离而 不涉及谁是谁的祖先问题。如图2 - 1 所示，该图表示了4 个物种( a 、b ，c 和d ) 的2 种有根树和1 种无根树形式。 下面是进化树中的一些常用的专用术语0 1 ： 1 树系的末端代表现代生存的物种。称为叶子结点( 1 e a v e s ) 或外结点 ( e x t e r n a ln o d e s ) 。 2 树内的分支点叫内结点( i n t e r n a ln o d e s ) 。 3 两个结点之间