（计算机软件与理论专业论文）构建进化树的邻接法的改进算法.pdf

华中科技大学硕士学位论文 摘要 构建进化树就是从生物序列的信息推断生物进化历史，“重塑”出系统进化的 ( 谱系) 关系，并把进化关系用树的形式表示出来树的叶子结点表示各个生物 序列，树枝的长度表示生物间的进化距离。 构建进化树问题是一个典型的n p 完全问题，当序列的条数很大时，没有一种 最优算法能在适当的时间内计算得到其精确解，因此，构造能在适当的时间内得到 最优近似解的算法就有很强的实际意义。对经典算法邻接法进行研究后，提出了两 种改进的算法。 对于距离矩阵法而言，遗传模型在进化树构建算法中非常重要。只有当进化模 型选择恰当时，序列进化距离才会计算得精确，构建的进化树才会准确。但是邻接 法采用了7 u k e s - c a u t o r 单参数模型，该模型没有考虑到基因突变中转换和颠换的 不同概率，其模型比较粗糙。因此，在改进算法i 中，采用了k i m u r a 两参数模型， 根据此模型来计算序列的距离，从而改进序列间距离：并采用新的校正距离 r 。= a m 。，+ 芦日i ，这样算法的准确性得到提高。 改进算法i i 考虑到邻接法的另外一个不足，即在邻接法计算过程中，要不断计 算新加入的结点到其它结点的距离，当进化距离不具有累加性时就会带来误差，而 改进算法每次以最初的距离矩阵为已知条件，避免了因此带来的误差；并且每次计 算树总长时，仍然考虑连接好的结点的分枝，计算出的是精确的树总长，使得构建 的进化树更加准确。 两种改进的算法都采用了评价建树算法中最常用的方法( 计算机模拟法) 来测 试其准确性，从测试数据中看到，两个改进算法的准确性都有很大的提高。 关键词：构建进化树，邻接法，距离矩阵法，生物信息学 华中科技大学硕士学位论文 a b s t r a c t r e c o n s t r u c t i n gp h y l o g e n e t i c t r e e sp r o b l e m ( r p t p ) i st or e c o n s t r u c t s y s t e m a t i c m e v o l u t i o n a lr e l a t i o na n ds h o wi ti nf o r mo ft h et r e e ，o nt h eb a s i so f i n f e r r i n gb i o l o g i c a l e v o l u t i o n a lh i s t o r yf r o mt h ei n f o r m a t i o no f h o m o l o g o u sn u c l e o t i d es e q u e n c e s a n o d eo f t h et r e ed e n o t e se a c h s e q u e n c ea n d ab r a n c hs h o wt h ee v o l u t i o n a ld i s t a n c e r p t pi sa t y p i c a ln pc o m p l e t ep r o b l e m i nt h ep r a c t i c a lc o m p u t i n g f o rt h ei n s t a n c e s w i t hl a r g es c a l e ，n oa l g o r i t h mc a ng e tt h ea c c u r a t es o l u t i o n sw i t h i nt h ea c c e p t a b l et i m e t h e r e f o r e ，i ti si m p o r t a n tt o c o n s t r u c tt h ea l g o r i t h mt o g e t t h e o p t i m u mt r e e i nt h e a c c e p t a b l et i m e i nt h i st h e s i s ，t w oa m e l i o r a t i v ea l g o r i t h m sw a sg i v e n ，b ya n a l y z i n g n e i g h b o rj o i n i n g m e t h o dw h i c hi so n eo fd i s t a n c em a t r i xm e t h o d f i r s t ，w ef i n dt h a tt h ea c c u r a c yo ft h ed i s t a n c ee x e r t sat r e m e n d o u si n f l u e n c eo nt h e e f f i c i e n c yo ft h ea l g o r i t h m s ，a n di td e p e n d so nt h ec h o i c eo f e v o l u t i o n a lm o d e l s t h e r e a r et h ej u k e s c a n t o rs i n g l ep a r a m e t e rm o d e la n dk i m u r at w op a r a m e t e r sm o d e l n o t c o n s i d e r i n g t h ed i f f e r e n t p r o b a b i l i t y o fb e t w e e nt r a n s i t i o na n dt r a n s v e r s i o n ，t h e j u k e s c a u t o rs i n g l ep a r a m e t e rm o d e li sm o r ec o a r s e b u ti ti su s e di nn ja l g o r i t h m t h e n w eu s ek i m u r at w op a r a m e t e r sm o d e la n dn e wr a t e c o r r e c t e dd i s t a n c ei nt h e f i r s t a m e l i o r a t i v ea l g o r i t h m ，s ot h ee f f i c i e n c yo ft h ea m e l i o r a t i v ea l g o r i t h mi sm o r et h a nt h a t o f n ja l g o r i t h m t h e nw ec o n s i d e ra n o t h e r s h o r t a g e o fn ja l g o r i t h m d u r i n gt h e c o m p u t a t i o n a l p r o c e s st h ed i s t a n c e s b e t w e e nn e wn o d e sa n do t h e r sh a v et oc a l c u l a t e i nt h i sw a y ，i tw i l l b r i n gt h e e r r o rw h e nt h ed i s t a n c e sa r en o ta c c u m u l a t i v e s ow ep r o p o s et h es e c o n d a m e l i o r a t i v ea l g o r i t h m d u r i n gt h ec o m p u t a t i o n a lp r o c e s so fa m e l i o r a t i v ea l g o r i t h m ，w e u s eo r i g i n a l d “a sk n o w nc o n d i t i o n se a c ht i m e t h e r e f o r ei t d o e sn o tb r i n gt h ee r r o r t h e nc a l c u l a t i n gt h es u mo fb r a n c h e s ，w ea d da l lo n e se a c ht i m e ，i n c l u d i n gt h eb r a n c h e s t h a tc o n n e c tw i t hw o r k e dn o d e s u s i n gc o m p u t e r s i m u l a t i o nw e s t u d yt h ee f f i c i e n c yo f t h r e ea l g o r i t s t h ec o u n t i i 华中科技大学硕士学位论文 o fo b t a i n i n gt h ec o r l e c _ t t o p o l o g y f r o mt h er e s u l to ft h es i m u l a t i o n ，w ef i n dt h a tt h e e f f i c i e n c yo f a m e l i o r a t i v ea l g o r i t h m sa r em u c hb e t t e rt h a nt h a to fn j k e yw o r d s ：r e c o n s t r u c t i n gp h y l o g e n e t i ct r e e sp r o b l e m ，n e i g h b o rj o i n i n gm e t h o d ， d i s t a n c em a t r i xm e t h o d ，b i o i n f o r m a t i c s 1 1 1 独创性声明 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承 担。 学位论文作者签名：滹尹号 日期：加争年f 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密缸 ( 请在以上方框内打“”) 学位论文作者签名：谗歹专 日期：冲朗7 日 指导狮始会趣 日期：西以年r 月( d 日 华中科技大学硕士学位论文 1绪论 本章首先简述构建进化树的研究背景，接着描述了构建进化树的现实意义，最 后介绍国内外构建进化树算法的发展状况。 1 1 研究背景 过去的十年，“基于硅片的生物学”正在蓬勃兴起。随着分子生物学的不断发 展，进化研究也进入了分子进化( m o l e c u l a re v o l u t i o n ) 研究水平，并建立了一套依赖 于核酸和蛋白质序列信息的理论和方法。 构建进化树就是从生物序列的信息推断生物进化历史，“重塑”出系统进化的 ( 谱系) 关系，并把进化关系用进化树的形式表示出来树的叶子结点表示各个 生物序列，树枝的长度表示生物间的进化距离。它是分子系统学的首要任务。 构建进化树的研究是生物信息学中的一个热点，根据进化树不仅可以研究从单 细胞有机体到多细胞有机体的生物进化过程，而且可以粗略估计现存的各类种属生 物的进化时间。通过蛋白质的系统进化树分析，为从分子水平研究物种进化提供了 新的手段，可以比较精确的确定某物种的进化地位。对于物种分类问题，蛋白质的 系统进化树亦可作为一个重要的依据【2 8 】。 构建进化树在生物学中有重要的应用，例如不少科学家就利用进化树对世界上 的鱼的种群进行研究：d u r a n d 等【9 】基于c y t b 序列，构建了中东地区的6 2 种鲤科 鱼类的分子系统进化树。系统树显示【1 0 】【1 ”，鲤亚科鱼类具有高度分化的3 支谱系， 一支与欧洲地中海地区的残留种共享，一支与非洲共享，还有一支与亚洲共享。因此 他们认为中东地区更可能是淡水鱼类区系的一个重要的交换地带，而不是一个物种 形成中心。这对人类了解不同鱼类的生活习性大有好处，所以研究高效准确地构建 进化树算法很有实际的应用价值。 由现代生存物种的大分子获得的进化历史信息是不完全的，因此，所推断出来 的进化树具有一定程度地不确定性和假设性。常常从同一组数据推断出若干不同的 进化树，因而如何通过可靠的算法，从一系列可能的进化树中选择“最合适的”或 “最可信的”树就是一个十分有意义的问题。 华中科技大学硕士学位论文 构建进化树的主要过程是：首先建立遗传模型遗传模型既影响比对，也影 响建树；接着进行序列比对f 1 2 - 2 2 1 ，从比对结果中提取系统进化的数据集至于如 何提取有效数据，取决于所选择的建树算法；最后得到系统进化树。 1 2 国内外概况 构建进化树的任务就是在序列比对的基础上，建立各个物种的进化关系，将生 物合理地分成一定的类群，使得同一类群内的个体成员相似。构建进化树是分类学 的重要课题，构建的过程有助于通过物种间隐含的种系关系揭示进化动力的实质。 用于构建进化树的数据有二种类型：种是距离数据( d i s t a n c ed a t a ) 或相似性数 据( s i m i l a r i t yd a t a ) ，它涉及的是成对基因、个体、群体或物种的信息；是另一种特征 数据( c h a r a c t e rd a t a ) ，它提供了基因、个体、群体或物种的信息。这些数据可以矩阵 的形式表达，它们分别用于两类不同的建树方法一一距离矩阵法和基于特征的方 法。距离矩阵( d i s t a n c em a t r i x ) 是在计算得到的距离数据基础上获得的，距离的计算 总体上是要依据一定的遗传模型，并能够表示出两个分类单位间的变化量。进化树 的构建质量依赖于距离估算的准确性。 进化树的构建主要有两类方法，一类是距离矩阵法( d i s t a n c em a t r i xm e t h o d ) ， 另一类是基于特征的方法。 距离矩阵法首先计算任意两个序列的差异数量，这个数量被看作进化距离 其准确大小依赖于进化模型的选择；然后运行一个聚类算法一一从最相似( 两者之 间的距离最短) 的序列开始。这类方法主要是根据每对物种之间的距离，其计算一 般很直接，所生成的树的质量取决于距离尺度的质量，而序列的距离通常取决于遗 传模型。最主要的方法是：u p g m 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 ga n a r i t h m e t i ca v e r a g e ) 、f i t c h m a r g o l i a s h 法和邻接法( n e i g h b o r - j o i n i n gm e t h o d ) 。 n e i 等( 1 9 8 3 ) 模拟了构建树的不同方法，发现当沿树上所有分枝的突变率相同 时，u p g m a 法一般能够得到较好的结果。另一些模型研究( 如k i m 和b u r g m a n ， 1 9 8 8 ) 已证实当各分枝的突变率不相等时，这一方法的结果不尽人意。当各分枝突 变率相等时，认为分子钟( m o l e c u l a rc l o c k ) 在起作用。 华中科技大学硕士学位论文 由于u p o 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 承认他们的 方法所得到的拓扑结构可能是不正确的，并建议考查其它的拓扑结构。可以采用 f i t c h 和m a r g o l l a s h 称之为“百分标准差”( c e n t e s i m a ls t a n d a r dd e v i a t i o n ) 的一种拟合优度来比较不同的进化树，最佳进化树应具有最小的百分标准差。根据 百分标准差选择进化树，其最佳进化树可能与由f i t c h m a r g o l i a s h 法则所得的不 相同。当存在分子钟时，可以预期这一标准差的应用将给出类似于u p g m a 方法的结 果。如果不存在分子钟，因而在不同的世系( 分枝) 中的变更率是不同的，则 f i t c h m a r g o l i a s h 标准就会比u p g m a 好得多。 邻接法( n e i g h b o r j o i n i n gm e t h o d ) 是由s a i t o u 和n e i 提出。该方法通过确定 距离最近( 或相邻) 的成对分类单位来使系统树的总长达到尽可能小。相邻是指两个 分类单位在某一无根分叉树中仅通过一个结点( n o d e ) 相连。总之，通过循序地将相 邻点合并成新的点，就可以建立一个相应的拓扑树。 基于特征的方法主要包括最大简约。”3 ”( m a x i m u mp a r s i m o n y ) 法和最大似然 ( m a x i m u m1 i k e l i h o o d ) 法。最大简约法较少涉及遗传假设，它通过寻求物种间最小 的变更数来完成的；而最大似然法对于假设的模型有巨大依赖性，计算量较大，但 为统计推断提供了基础。 用最大简约方法搜索进化树的原理是要求用最小的改变来解释所要研究的分类 群之间的观察到的差异。最大似然法评估所选定的进化模型能够产生实际观察到的 数据的可能性。 最大似然法考察数据组中序列的多重比对结果，优化出拥有一定拓扑结构和树 枝长度的进化树，这个进化树能够以最大的概率导致考察的多重比对结果。它考察 数据组中所有序列的两两比对结果，通过序列两两之间的差异决定进化树的拓扑结 构和树枝长度。最大简约方法考察数据组中序列的多重比对结果，优化出的进化树 能够利用最少的离散步骤去解释多重比对中的碱基差异。 此外，还有大量的建立和搜索进化树的其它方法。这些方法包括w a g n e r 距离 方法和亲近方法( 距离转化方法) ；l a k e 的不变式方法( 个基于特征符的方法， 它选择的拓扑结构包含一个意义重大的正数以支持颠换) ；h a d a m a r d 结合方法( 一 个精细的代数方阵方法，对距离数据或者观察到的特征符进行修正) ；裂解方法( 这 华中科技大学硕士学位论文 个方法决定在数据中应该支持哪一个基于距离的可选的拓扑结构) ；四重奏迷惑 ( q u a r t e tp u z z l i n g ) 方法可以为m l 建树方法所应用，这个算法相对而言是个较快 的系统进化树搜索算法。 1 3 本文的主要研究工作 目前，国内外的构建算法的计算准确性都不是十分的理想，而且国内大部分的 研究仅限于进化树的应用，对于构建进化树算法的研究较少，因此，对构建进化树 的两类方法中的一类距离矩阵法，进行探讨和研究后，将在邻接法的基础上， 提出了两种改进的算法。 对于距离矩阵法而言，序列进化距离的精确性对算法的准确性影响很大，而距 离的精确性依赖于进化模型的选择。但是在邻接法中，算法采用了j u k e s c a u t o r 单参数模型，没有考虑到基因中转换和颠换的不同概率，其模型比较狙糙。因此， 在改进算法i 中，采用了k i m u r a 两参数模型，根据此模型来计算序列的距离d ，从 而改进序列间距离；并采用新的校正距离r = o n 如+ 芦，这样算法的准确性得到 提高。 改进算法i i 考虑邻接法的另外一个不足一一在邻接法计算过程中，要不断计算 新加入的结点到其它结点的距离d 。当d 。不具有累加性时就会带来误差，改进算 法每次以最初的d f 为已知条件，不会因为不断地更新如而带来误差，从而使得构 建的进化树更加准确；并且每次计算树的总长时，仍然考虑连接好的结点的分枝 计算出的是精确的树总长的最小二乘法的解。 两种改进的算法都将采用了评价建树算法中最常用的方法计算机模拟法 来测试其准确性。 华中科技大学硕士学位论文 1 4 文章的框架结构 第一章简要概述构建进化树的研究背景和重要作用；然后解释了进化树的一 些已有的构建过程；最后重点讲述国内外研究的概况和本课题主要研究的工作。 第二章介绍邻接法的主要思想和步骤，指出了影响算法准确性的一个重要因 素一计算d n a 序列距离的遗传模型和校正距离，并分析了邻接法的不足。 第三章详细描述了基于邻接的改进算法，算法主要有以下两点改进：1 采用 新的序列间距离利用k i m u r a 两参数模型，根据此模型来计算d n a 序列距离， 2 定义了新的校正距离。计算机模拟结果表明，改进算法的准确性明显的优于邻按 法。 第四章详细介绍了基于邻接的另一个改进算法，阐述了改进算法的准确性更 高的理由：首先，改进的算法距离的定义更为准确，而且更重要的是：每次挑选下 一组结点相邻时，并不像邻接法一样，不再考虑已经结合好的分枝长，而是考虑所 有的分枝长。这样，树枝总长计算就更为精确，得到的拓扑结构也就更加正确了， 所以改进算法的准确性大大地提高。计算机模拟结果显示，改进算法的准确性明显 的优于邻接法。 第五章对全文进行总结并展望了未来工作，最后是致谢和参考文献。 华中科技大学硕士学位论文 2 邻接法 构建进化树是一个典型的n p 完全问题，首先将介绍距离矩阵法构建进化树问题 的数学模型。其次，由于邻接法是一种高效的经典算法，改进算法将在此基础上修 改，故本章将重点介绍邻接法的计算方法，最后将详细分析邻接法，找出影响算法 准确性的因素。 2 1 距离矩阵法构建进化树问题的数学模型 从已知的生物序列中能推断各个物种间的进化历史，按照一定的遗传模型，把 任意两个序列间的进化历史转化成数字，就得到两两之间的进化距离，把所有的距 离用矩阵的形式表示出来，就得到了距离矩阵。 根据距离矩阵我们最后将构建出一棵进化树，这里先介绍一下进化树的概念和 专用术语： 进化树是二叉树，它分有根( r o o t e d ) 树和无根( u i l r o o t e d ) 树。有根树反映了树上 物种或基因的时间顺序，而无根树只反映分类单元之间的距离而不涉及谁是谁的祖 先问题。如图2 1 所示，该图表示了4 个物种( a 、b 、c 和d ) 的2 种有根树和1 种 无根树形式。 下面是进化树中的一些常用的专用术语 1 树系的末端代表现代生存的物种，称为叶子结点( 1 e a v e s ) 或外结( e x t e r n a l n o d e s ) 。 2 树内的分支点叫内结( i n t e r n a ln o d e s ) 。 。 3 两个结点之间的连接部分称为分枝( b r a n c h e s ) 。 4 达到并终止于外结的技叫周枝( p e r i p h e r a lb r a n c h e s ) ，未达到顶结的其 他的枝叫做内枝( i n t e r i o rb r a n c h e s ) 。 5 在一个无根的二叉树中，假如叶子结点的数目为n ，那么内结数目为n 一2 ， 分枝( 节) 的数目为2 n 一3 ( 其中内枝数目为n - 3 ，周枝数目为n ) 。 6 。从n 个物种( 顶结) 可以推断出无根树的数目t ( n ) 为 华中科技大学硕士学位论文 ，( ) = 兀( 2 i 一5 ) i = 3 例如当n = 8 时，内结的数目为n - 2 = 6 ；分枝数为：n - 3 = 1 3 ( 其中周枝为8 ，内枝 为5 ) ，可能的无根进化树为： r ( 8 ) = 兀( 2 i 一5 ) = l x 3 5 7 x 9 x 1 1 = 1 0 3 9 5a abcd abcd c d 图2 1四个物种的两种有根树和一种无根树形式 定义2 1 基于距离矩阵法的构建进化树问题是指若已知r l 条序列，计算出任意 两个序列间的进化距离，即第i 、j 个序列间的距离为d f ，得到距离矩阵，根掘该矩 阵构建出满足如下条件的无根的系统进化树： 1 ，n 个序列作为树的叶子结点。 2 根据构建出的进化树，能得到任意两个叶子结点间的距离，设第i 、j 个叶子 问的距离为吒，要使得( d j 一叱) 2 尽可能的小。 华中科技大学硕士学位论文 距离矩阵法构建进化树实质上就是试图对一组给定的距离数据找到一棵进化 树，使得各叶子结点之间的进化距离与树中对应的路径长度之间的误差的平方和最 小。 随着序列条数的即的增大，可能的进化树数目增长的更挟。若有栉个叶子，则存 n n 在t i ( n ) = 1 7 ( 2 i 5 ) 种无根系统进化树和：r a n ) = 丌( 2 f 一3 ) 种有根系统进化树。当 1 = 3 i = 3 n = 1 0 时可能的进化树的数目是两百万种，当n = 2 0 时进化树的数目是2 2 1 0 2 0 种。 h a n sl b o d l a e n d e r 、m i k er ，f e l l o w s 和t a n d y j 。w a r n o w ( 1 9 9 2 ) 已经证明构建进化树是 一个n p 完全问题【34 1 。 由此，对于构建进化树这样的一个难题，要对每种可能的进化树都进行穷举， 求出完全精确的解，这显然是不可能的，所以研究在适当的时间内得到最优近似解 的算法就具有很强的实际意义。 在邻接法和改进的算法中，我们首先是对序列进行两两比对，得到任意两个序 列之问的距离d ，而不是用多序列比对，这样就把序列比对的复杂度大大降低了， 只有o ( n ，n ：) 、啦分别表示序列的长度。 接着我们按照树总长s 尽可能小的原则，不断选出两个结点连接起来，形成新 的树拓扑，在可能的树拓扑结构中挑选出s 尽可能小的作为最后的进化树。这样我 们就不用搜索所有可能的树拓扑，算法的计算量又降低了许多。 若我们用穷举法，对于九个叶子的所有的进化树进行穷举，其计算量是相当惊 人的。邻接法和我们的改进算法是逐次挑选出两个结点让其连接，直到所有的结点 都处理完，我们总共搜索了( c ：+ 2 c ：。+ 2 c 三：+ 2 曰) 种无根树，最后得到 的进化树是这些树中树总长最小。 因此邻接法和改进算法都具有时间复杂度小的优点，但是邻接法的计算准确性 并不理想，我们在分析原因后，提出了两个改进的算法，其准确性得到提高。 2 2 序列距离定义方法 遗传模型在进化树构建算法中非常重要，因为对于距离矩阵法而言，只有进化 模型的选择恰当，序列进化距离才会计算得精确，序列的距离又是构建进化树的前 华中科技大学硕士学位论文 提，它的准确性对算法的准确性影响很大。在d n a 序列距离计算中最为常用的遗 传模型是j u k e s c a u t o r 单参数模型和k i m u r a 两参数模型【3 5 【3 6 】。下面我们详细介绍 一下两个不同的模型： 在分子进化研究中，我们通常认为所有序列都是同源的，即它们都是由同一个 祖先序列进化而来；这一祖先序列在进化过程中发生了一系列的核苷酸突变，从而 产生了不同的子孙序列。d n a 序列距离d 就是d n a 序列间的分歧度( s e q u e n c e d i v e r g e n c e ) 即序列间相异性的一个指标。根据j u k e s c a u t o r 单参数模型和k i m u r a 两参数模型等遗传模型，可以分别计算得到两序列的距离。 在同源假设的基础上，j u d e s 和c a u t o r 进一步假设每一碱基( a 、c 、g 、t ) 具 有同等机率，可突变为另外三种碱基中的任何一种，其频率常数为u 3 ，u 为碱基 替换频率。k i m u r a ( 1 9 8 0 ) 3 7 1 考虑到转换( t r a n s i t i o n ，我们称为i 型变换，两种嘧啶或 两种嘌呤碱基之间的突变，即a - - g ；t - - c ) 和颠换( t r a n s v e r s i o n ，称为i i 型变换， 一个嘧啶和一个嘌呤碱基之间的突变，即a 一 c ；a - - t ；g - - c ；g 一 n 具有不 同的频率，用a 和b 表示。表2 1 简要说明了以上两神遗传模型。 表2 1j u d e s c a n t o r 单参数模型( 上三角部分) 和 k i m u r a 两参数模型( 下三角部分) l j ltgc a a t0 g a b a cb a b 注1 a 、b 分别为两种碱基间两个不同的置换频率。 在邻接法中，采用了j u k e s - c a u t o r 单参数模型，根据此模型，j u d e s 和c a n t o r ( 1 9 6 9 ) 提出了d n a 序列距离d 计算公式。 扣和南净2 ( 2 _ ) 11 其中u 为碱基替换频率，q 为d n a 序列中具有相同碱基的概率，即 华中科技大学硕士学位论文 口：堕全些翌壁型! 塑望焦里塑旦堡薹塑篁塑 1 m a x ( 两个序列的总长) 在改进的算法中，我们改进了序列距离计算的遗传模型，采用了k i m u r a 两参数 模型，因为该模型更体现了生物的突变规律，计算出的序列距离更为精确。 根据k i m u r a 两参数模型，根据此模型d n a 序列距离d 计算公式【3 7 l 。 1 一 d = 一l n ( 1 2 p 1 2 p n ) l 一2 p n 2 k t ( 2 2 ) 二 其中k = a + 2 b 是单位时间碱基替换的总频率，p 为d n a 序列中的i 型变换 的概率，p 是i i 型变换的概率。即 2 3 算法步骤 式 两个比对序列中i 型变换的碱基总数 a 2 五i 而丽爵丽瓦酮万一 两个比对序列中n 型变换的碱基总数 p n2 i i 丽雨再可丽甄百一 邻接法的一般步骤如下： 1 采用了j u k e s c a u t o r 单参数模型，计算出第i 条和第j 条序列距离d o 计算公 铲昙t n 杀， 其中q 为两个序列中相应位置上相同碱基的概率。显而易见， d = d 2 计算第i 个叶子结点( 即第i 个序列) 的净分歧度r i l = 氐 女* l 其中n 是叶子结点的个数，d 。k 为叶子结点i 和叶子结点k 之间的距离。 3 计算任意两两结点i 和j 之间的速率校正距离( r a t e c o r r e c t e dd i s t a n c e ) m u 0 华中科技大学硕士学位论文 m ，= d g 一万r , + i r j 4 挑选出最小的速率校正距离m p 5 定义一个新的结点t ，t 的左、右孩子分别是第i 个和第j 个结点。结点t 到 i ，j 的距离为： 或2 譬+ 丽r , - r j d n = d ，一d h 结点t 与进化树其他结点k 的距离为d 晴。 九：盟粤墨 6 从叶子结点集合l 中删除结点i 和j ，并在集合中添加t 结点，n 的值减去1 。 7 如果叶子结点集合l 中剩余的叶子结点个数大于2 ，则重复步骤2 继续计算， 直到叶子结点个数为2 ，即进化树完全建成。 2 4 算法分析 对于距离矩阵法而言，遗传模型的选取对构建迸化树非常重要，只有进化模型 的选择恰当，序列进化距离才会计算得精确；序列的距离又是构建进化树的前提， 它的准确性对算法的准确性影响很大。在d n a 序列距离计算中最为常用的遗传模 型是j u i c e s c a u t o r 单参数模型和k i m u r a 两参数模型。邻接法采用了j u k e s c a u t o r 单参数模型，该模型没有考虑到基因中转换和颠换的不同概率，其模型比较粗糙。 因此，在改进算法i 中，采用了k i m u r a 两参数模型，根据此模型来计算序列的距 离d ，从而改进序列间距离；并采用新的校正距离r n = a m “+ 辟0 ，这样算法的准 确性得到提高。 而且在邻接法计算过程中，每计算一步，都要计算新加入的结点到其它结点的 距离d 。，如果d f ，不具有累加性时就会带来误差，所以改进算法i i 每次将以最初的 d 。为已知条件，不用每次都要更新d ，避免了因此带来误差，使得构建的进化树 华中科技大学硕士学位论文 更加准确；并且在每次算树的总长时，我们仍然考虑连接好的结点的分枝，计算出 的是精确的树总长。 2 5 小结 构建进化树问题是一个典型的n p 完全问题，其穷举法的计算量非常大，它来源 于树拓扑结构的多样性。接着介绍了序列的距离定义两种方法，它们是j u k e s c a u t o r 单参数模型和k i m u r a 两参数模型计算得到。 邻接法是一种高效的经典算法，改进算法将在此基础上修改，故本章重点介绍 了邻接法的计算方法，最后详细分析邻接法，找出影响算法准确性的因素。 华中科技大学硕士学位论文 3 基于邻接法的改进算法i 本章首先将详细描述改进算法i 所作的改进，以及改进算法i 的具体步骤；接 着我们通过一个具体的例子，更加清楚地阐述算法的计算过程；最后我们采用了评 价建树算法中最常用的方法一一计算机模拟法，测试改进算法i 和邻按法的准确 性。 3 1 算法描述 对于距离矩阵法，所生成的树的质量取决于距离尺度的质量和每次挑选相邻结 点的标准。本节将介绍一种基于邻接法的改进算法，它通过改进序列间距离和校正 距离的定义，来优化构建进化树的算法。 在距离矩阵法中，序列距离是计算的前提，而序列距离是根据遗传模型得到的， 所以恰当地选择进化模型是十分重要的。在改进算法i 中，采用了k i m u r a 两参数 模型，该模型考虑到基因中转换和颠换的不同概率，比较符合生物的进化规律，并 且根据此模型来计算序列的距离d 。其次，在改进算法中，我们借鉴u p g m a 算法的 思想一每次挑选具有最小d ，的结点，把它们作为相邻的的结点，同时也吸收邻接 法的精髓，采用校正距离，因此产生一个新的标准。 r 。= a m 口+ 彤“( 其中口十卢= 1 ) 。 3 2 算法步骤 改进的邻授法的一般步骤如f ： 1 采用了k i m u r a 两参数模型，根据此模型，d n a 序列距离d 计算公式： 1 一 d = 一去l n ( 1 2 p 【一2 p n ) 1 2 p 兀 二 其中p 。为d n a 序列中的i 型变换的概率，p 。是i i 型变换的概率，而且d 口= d 扩 2 计算第i 个叶子结点( 即第i 个序列) 的净分歧度r ：y d 。 华中科技大学硕士学位论文 其中n 是叶子结点的个数，d ik 为叶子结点i 和叶子结点k 之间的距离。 3 计算任意两两结点i 和j 之间的速率校正距离r 。= 础。十倒： 其中 r + r 刊f 一箍；叶。1 并且挑选出最小的r 。 4 定义一个新的结点t ，t 的左、右孩子分别是第i 个和第j 个结点。结点t 到 i ，j 的距离为： d 户生2 + 旦2 ( n - 2 ) d 。= d 。一d 。 结点t 与进化树其他结点k 的距离为：巩：曼_ 宅皇蔓 5 从叶子结点集合l 中删除结点i 和j ，并在集合中添加t 结点，n 的值减去l 。 6 如果叶予结点集合l 中剩余的叶子结点个数大于2 ，则重复步骤2 继续计算， 直到叶子结点个数为2 ，即进化树完全建成。 现在以表3 1 所示的线粒体序列为例说明以上计算过程。 表3 1 五种生物线粒体d n a 序列 1 人类 g t a a a l t a gt r r a a c c a a aa c a t c a g a t tg t g a a t c t g ac a a c a g a g g c ( h u ) t f a c g a c c c cy f a t t t a c c 2 黑猩猩 g t a a a t a t a gt 丌a a c c a a aa c a r c a g a t t6 t g a a t c t g ac a a c a g a g g c ( c h ) t c a c g a c c c c1 v i ：盯1 可a c c 3 大猩猩 g t a aa ：l 蛆a gt r i m c c a a aa c a t c a g a t tg t g a a t c t g at a a c a g a g g c ( g o ) t c a c a a c c c c r 聃t t t a c c 4 猩猩 g t a aa n r a gt t l a a c c a a aa c a t t a g a t tg t g a a t c t a at a t a g g g c c ( o r ) c c a c a a c c c ct n 虮丁t a c c 5 长臂猿 g t a a a c a r a gt t t a a t c a a aa c a t t a g a t tg t g a a t c r a ac a r a g a g g c ( g i ) t c g a a a c c t c1 t g c t t a c c 华中科技大学硕士学位论文 我们根据k i m u r a 两参数模型，计算出五条d n a 序列之间的距离d ，如表3 , 2 所示。 表3 2 五种d n a 序列k i m u r a 距离 h uc h g o 0 r g l h u0 0 0 00 。0 1 50 0 4 50 1 4 3o1 9 8 c h0 0 0 00 0 3 00 1 2 60 1 7 9 g o 0 0 0 00 0 9 2o 1 7 9 o r0 0 0 00 1 7 9 9 1 0 0 0 0 表3 3 至表3 6 列出了各步计算的结果，其中每一次都挑选出最小的m i j 值。第 一步，猩猩( o r ) s 1 1 长臂猿( g i ) 之间的m 5 值最小，则把它们作为相邻结点，用结点1 连接起来。然后用结点1 取代猩猩( o r ) 和长臂猿( g i ) ，进入第2 步，则新结点( 结点 1 ) 到这二个结点的距离为： d 。，。节点。= 圭d 。十r o t - - ；一r g i = o 0 5 7 d 掣，节点l = = d ，p d 甜，节点l = 0 1 2 2 结点1 到其它各结点的距离见表3 3 第二步的距离矩阵。在该矩阵中，人( h u ) 和 黑猩猩( c h ) 的m u 值最小，则它们又形成一个新结点( 结点2 ) 依次类推，便可最 终完成矩阵的计算和邻接法无根系统树。 下面详细的解释一下表3 3 至表3 6 ： 表3 3 表示序列还没有处理时的最初的格局，表格的上对角表示五个序列间的距 离d ，下对角部分表示任意两个序列的矫正距离m ，j 。 由于结点4 、5 的矫正距离最小，即0 2 1 4 ，则把结点4 、5 结合，形成其父结点 结点1 。把结点4 、5 从未处理的结点集合中删除，在结点集合中加入结点1 ， 并计算出任意两个结点间的距离d 。i 和矫正距离m i j ，第二步的结果见表3 4 所示。 华中科技大学硕士学位论文 表3 3 最初格局下序列的距离d i j ( 上x 寸角线部分) 和m i j ( t r v j - 角线部分) h uc h g o o r 副净分歧度 j = lj = 2j = 3j = 4j = 5l h ui 憎l0 0 0 00 0 1 50 0 4 501 4 3o 1 9 80 4 0 1 c hi _ 20 2 1 00 0 0 00 0 3 0o 1 2 6o 1 7 90 3 5 0 g o i = 3一o 1 7 9o 。1 7 90 0 0 00 0 9 20 ，1 7 90 ，3 4 6 o ri = 4- o 1 3 9o 1 4 1- o 1 7 40 0 0 00 1 7 90 5 4 0 目 i _ so 1 4 3o 1 4 7o 1 4 50 2 1 40 0 0 00 7 3 5 表3 4 第二步时序列的距离州( 上对角线部分) 和m i j ( t 对角线部分) h uc h g o 结点1 j = 1 j - 2j = 3j = 4 h ui _ l0 0 0 00 0 1 50 0 4 50 0 8 1o 1 4 1 c hi 一20 0 9 70 0 0 00 0 3 00 0 6 30 1 0 8 g o i _ 30 0 7 30 0 7 20 0 0 00 ，0 4 6 0 1 2 1 结点1 i _ 40 0 6 8，0 0 7 10 0 9 40 0 0 00 1 9 0 因为如表3 4 所示，结点l 、2 的矫正距离最小，即一o 0 9 7 ，把结点1 和2 结合， 形成其父结点结点2 。把结点l 、2 从未处理的结点集合中删除，在结点集合中 加入结点2 ，并计算出任意两个结点间的距离d i j 和矫正距离m u ，如表3 5 所示。 表3 5 第三步时序列的距离d i j ( a 2 y 时f l ： 线部分) g lm i j ( 下对角线部分) g o 结点1结点2 j = 1j 2 2 j = 3 g o i _ 1 0 0 0 00 0 4 60 0 3 00 0 7 6