（计算机科学与技术专业论文）基于离散度量的进化树构建方法研究.pdf

、 、 m 吲m 埘眦怕耐山崦呲乱嬲必 d i s c r e t em e a s u r e b y x i n y u a nz h o u b e ( h a r b i ni n s t i t u t eo ft e c h n o l o g y ) 2 0 0 2 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o l l e g eo fi n f o r m a t i o ns c i e n c ea n de n g i n e e r i n g i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rb 0l i a o n o v e m b e r ，2 0 1 0 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 1 作者签名：心卅彰l 日期：列矿年z _ 乒js - 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 组言白姨一 辫荫 日期：2 o l v 年 日期：劫7 年 ，z 月厂日 i 胡j 一1 3 摹丁| 离敞庋鼍的进化树构建方法研究 摘要 系统进化分析是生物信息学中的重要研究领域，它的主要研究手段是从一组 同源的d n a 或蛋白质序列出发，计算各个序列之间的进化距离，进而构建反映 物种进化关系的进化树。构建进化树的方法主要分为三类，即距离法、简约法和 似然法。其中，距离矩阵法以结构简单，具有良好的理论基础等特点获得广泛应 用。本文将对距离法做一些探索性的改进研究。 基于距离矩阵法是构建进化树方法中比较常用的一类方法，但是传统的基于 距离矩阵法是建立在序列比对基础上的，使一些主观因素破坏数据的原始状态， 导致计算结果因人而异。并且序列比对提高了进化树构建的成本，经过序列比对 得到的距离易受序列长度影响，与真实进化距离的差别较大。 所以本文为了解决这个问题，提出了新的相似距离度量算法离散度量，这种 度量法度量序列之间的距离不需要序列比对，没有主观因素干涉，而且比较直观， 计算量小。并在此离散度量的基础上，提出来一种横纵法的改进算法，原横纵法 在构造出连通图后，需要对所有的边的权重进行排序，而改进后的算法不需要进 行排序，构造连通图的同时就可以直接构建进化树。 基于离散度量的距离矩阵法是建立在信息理论法基础上提出来的。这种方法 是在先将分子序列转换成可以让现有的线性代数、统计理论、信息理论等数学工 具处理和分析的对象，进而再定义向量之间的两两相似度或不相似度。在文中采 用信息增益来度量序列之间的相似性。该方法首先运用k 串对d n a 序列进行编码， 提取序列之间的共同之处，然后计算信息增益来表示两两序列之间的相似度，再 构建相似距离矩阵，然后在该相似距离矩阵的基础上构建进化树，并与其他方法 进行了比较。 基于l a b v i e w 平台的进化树构建系统，可以方便的从e x c e l 或t x t 文件中批 量导入相似距离矩阵数据，并以图形化的形式表示出相应的进化树。 为了评估该基于离散度量的构建进化树的方法，本文选取了1 0 种胎生哺乳动 物的线粒体全基因序列作为实验数据，并采用p h y l i p 软件中的n e i g h b o r e x e 程 序来评估的，通过做实验来验证算法的可行性。 关键词：进化树；离散度量；距离矩阵；信息增益；信息理论 v 硕士学f 蕾论文 a b s t r a c t p h y l o g e n e t i ca n a l y s i si so n ei m p o r t a n tf i e l di nb i o i n f o r m a t i c s ；i t sm a i nt a s ki st o r e c o n s t r u c tap h y i o g e n e t i ct r e ef r o mag r o u po fh o m o l o g o u sd n ao r p r o t e i n s 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 yr e l a t i o n s h i pb e t w e e nt h o s es e q u e n c e s t h e r ea r e m a i n l yt h r e et y p e so ft r e e - - b u i l d i n gm e t h o d s ：d i s t a n c e ，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 e o fi t s s i m p l i c i t ya n ds o l i d t h e o r y t h i st h e s i sw i l ld os o m ee x p l o r a t o r yr e s e a r c h e st oi m p r o v et h ed i s t a n c e m e t h o d b a s e do nd i s t a n c em a t r i xm e t h o di sac o m m o n l ym e t h o di n c o n s t r u c t i n g p h y l o g e n e t i ct r e e s ，b u t t h et r a d i t i o n a ld i s t a n c em a t r i xm e t h o di sb u i l tt ob a s eo n s e q u e n c ea l i g n m e n t ，w h i c hm a k e ss o m es u b j e c t i v ef a c t o r sd e s t r o y e dt h eo r i g i n a ls t a t e o fw h o l eg e n o m es e q u e n c e s t h ep r o c e s so fa l i g n m e n tc o n s u m e sl a r g ec o s t ，a n dt h e d i s t a n c e s d i r e c t l yc o m p u t e df r o mp a i r w i s es e q u e n c e sa l i g n m e n ta r es u b j e c t e d t o s e q u e n c el e n g t h sa n dn o tg o o dr e p r e s e n t a t i o n so fr e a le v o l u t i o n a r yp h e n o m e n a t h e r e f o r e ，i no r d e rt o s o l v et h i sp r o b l e m ，w ep r o p o s ean e wm e a s u r ef o r s i m i l a r i t y ，c a l l e dd i s c r e t em e a s u r e ，w h i c hm e a s u r et h es i m i l a r i t yb e t w e e ns e q u e n c e s w i t h o u ta l i g n m e n t ，a n dd o e sn o th a v es u b j e c t i v ef a c t o r st oi n t e r f e r e ，a n dr e l a t i v e l y i n t u i t i v e ，l e s sc a l c u l a t i o n b a s e do nt h ed i s c r e t em e a s u r e ，w ep r o p o s e da ni m p r o v e d v e r t i c a l h o r i z o n t a l a l g o r i t h m a f t e rt h e v e r t i c a l h o r i z o n t a l a l g o r i t h m b u i l tt h e c o n n e c t e dg r a p h ，t h ep r o c e s so fs o r t i n gt h ew e i g h ti sn e e d e d b u tf o ro u ri m p r o v e d v e r t i c a l h o r i z o n t a la l g o r i t h m ，i ti sn o tn e e d e d t h ed i s t a n c em a t r i xm e t h o db a s e do nd i s c r e t em e a s u r ei s p u tf o r w a r do nt h e b a s i so fi n f o r m a t i o nt h e o r y t h i sm e t h o dt r a n s f e r s t h ed n as e q u e n c e si n t oo b j e c t s s u c ha sa b o v ed e f i n e dc o u n tv e c t o r s ，t h ef r e q u e n c yv e c t o r sa n ds oo n ，w h i c ha r e a n a l y z e da n dp r o c e s s e db ym a t h e m a t i c a lt o o l ss u c ha st h ee x i s t i n gl i n e a ra l g e b r a ，t h e s t a t i s t i c a lt h e o r y ，i n f o r m a t i o nt h e o r ya n ds oo n i nt h i sp a p e r ，w eu s ei n f o r m a t i o n d i s c r e t em e a s u r et om e a s u r et h es i m i l a r i t yo rd i s s i m i l a r i t yb e t w e e nv e c t o r s t oe x t r a c t t h es i m i l a r i t yb e t w e e ns e q u e n c e s ，t h ea l g o r i t h mf i r s t l yc o d e st h es e q u e n c e sb y k s t r i n g s ，a n dt h e nc a l c u l a t e st h ei n f o r m a t i o ng a i n a f t e rt h a t ，w eb u i l tt h ed i s t a n c e m a t r i xt oc o n s t r u c tt h ep h y l o g e n e t i ct r e e s ，a n dc o m p a r e dw i t ho t h e rm e t h o d s t h ep h y i o g e n e t i ct r e e sc o n s t r u c t i o ns y s t e mi sb a s e do nl a b v i e w p l a t f o r m ，a n d i tc a nc o n v e n i e n t l yl o a dt h ed a t ao fd i s t a n c em a t r i xf r o me x c e lo rt x tf i l et op r e s e n t t h eg r a p h i cr e s u l t s e q u e n c e sa sad a t a s e t ，a n du s en e i g h b o r e x ep r o g r a mo fp h y l i ps o f t w a r et oa s s e s s i t ，a n dt h e nw ev e r i f yt h em e t h o df e a s i b i l i t yb yt h ee x p e r i m e n t k e yw o r d s ：p h y l o g e n e t i ct r e e s ；d i s c r e t em e a s u r e ；d i s t a n c em a t r i x ；i n f o r m a t i o n g a i n ；i n f o r m a t i o nt h e o r y v i i 硕i ：学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要v a b s t r a c t v i 插图索引v i 附表索引v i i 第l 章绪论1 1 1 研究背景和意义1 1 2 国内外研究现状2 1 2 1 基于序列比对的序列相似分析3 1 2 2 基于图形表示的序列相似分析4 1 2 3 构建系统进化树的数据集及相关软件一8 1 3 本文的主要研究工作9 1 4 本文的章节安排9 第2 章离散度量方法和进化树构建算法l l 2 1 离散度量方法l l 2 2 进化树构建算法1 2 2 2 1 基于距离建树法1 2 2 2 2 基于特征建树法1 5 2 3 建树方法的特点与比较1 7 2 4 小结l8 第3 章一种基于离散度量的进化树构建方法1 9 3 1 分子序列编码及k 串法1 9 3 2 基于信息增益的离散度量1 9 3 3 实验及分析2 l 3 3 1 数据2l 3 3 2 改进的进化树构建算法2 1 3 4 小结2 6 第4 章基于l a b v i e w 的系统实现一2 8 4 1l a b v i e w 平台概述2 8 4 2 系统框架2 9 4 3 构建进化树算法的实现3 0 基丁离散度最的进化树构建方法研究 4 4 测试实例和结果分析一3 2 4 5 小结3 4 结论3 5 参考文献3 7 致谢4 2 附录a 攻读学位期间所发表的学术论文和参加的项目4 3 硕十学化论文 插图索引 图1 1 二维图形的三种坐标一6 图1 2w 曲线核苷酸坐标位置( 左) 和w 曲线核苷酸映射( 右) 7 图2 1 用m p 法计算得出的表2 1 中的系统发生树1 6 图3 1 连通图的比较树2 4 图3 2 基于信息增益的改进横纵法进化树构造2 5 图3 3 基于信息增益的横纵法进化树构造2 6 图3 4sim s 构建的进化树2 6 图4 1 系统数据流程图3 0 图4 2 程序框图3 2 图4 3 导入的相似距离矩阵3 3 图4 4 各物种间的连通图3 3 图4 5 进化树3 4 基于离散度量的进化树构建方法研究 l 暑皇毫! 皇詈詈! ! 詈! 皇皇詈宝詈暑詈= 鼍詈= 詈詈= = ! 詈= = = ! = ! = = 暑皇詈詈皇皇詈= = = ! = ! ! = ! 竺! ! ! ! ! ! 皇2 = = ! ! ! ! ! ! = ! = = ! 竺! = ! = 詈= 詈皇皇= 附表索引 表2 1 分类单元特征矩阵1 6 表3 11 0 种胎生哺乳动物的线粒体全基因序列2 3 表3 2k ：7 ，基于信息增益构建的相似距离矩阵2 3 表3 3 归一化后的相似距离矩阵一2 4 硕十学化论文 第1 章绪论 分子系统发育分析是生物信息学的重要分支，主要用于研究生物体在分子水 平的进化式样、方向、速率以及各种分子机制对基因和基因组的结构与功能的影 响。构建代表物种进化关系的进化树是分子系统发育分析的主要研究手段。本章 首先阐述构建进化树的研究背景和意义以及国内外研究现状；然后简述一下本文 的主要工作内容；最后简述一下本文各章节的主要内容。 1 1 研究背景和意义 系统发生( 或种系发生，系统发育，p h y l o g e n y ) 是指一群有机体发生或进化 的历史，系统发生树( p h y l o g e n e t i ct r e e ，又称e v o l u ti o n a r yt r e e 进化树) 就 是描述这一群有机体发生或进化顺序的拓扑结构，它可以用来研究不同物种间的 进化关系，这一直是生物学的研究热点，自从1 9 8 5 年达尔文的物种起源( o r i g i n o fs p e c ie s ) 发表以来，重构地球上所有生命的进化史并以系统树的形式描述这 部历史一直是每一个生物学家的梦想。由于化石保存的不完备性使得由化石记录 推导出的系统发生树缺乏中间环节，虽然利用现存物种的形态和生理学的研究大 致填补了化石系统发生树树的空缺，但由于形态和生理性状的进化非常复杂，因 此对分类单元何时与最近祖先分歧等细节性问题含糊不清。通过比较学和比较生 理学的方法，进化学家已经得到有机体进化关系的主要框架。然而形态和生理形 状的进化与比较是非常复杂并且容易受到主观判断影响的，以至于无法用以产生 一幅进化历史的清晰图像。不同学者在构建进化树的细节上几乎总是存在争议。 自从上世纪5 0 年代末期，尤其是1 9 8 5 年产生的p c r ( p l o y m e r a s ec h a i n r e a c t i o n ) 技术之后，不同的分子测序技术的速发展使得大量的d n a 分子数据不断 涌现，进化论的研究也进入了分子水平，使得这种局面大大改观。由于所有的生 命蓝图都用d n a ( 在某些病毒中则用r n a ) 来书写，因此人们可而分子系统发育分 析的进展大大改变了这种局面，首先不论是细菌、植物还是各种动物，其d n a 分子 均由腺嘌呤( a ) 、胸腺嘧啶( t ) 、胞嘧啶( c ) 、鸟嘌呤( g ) 这四种碱基组成，r n a 分子 与蛋白质分子也具有类似性质。因此通过分子系统发生学的方法可以对所有物种 进行比较与研究，这在传统方法中是不可能做到的。其次，d n a 的进化演变存 在某种程度的规律性，因而能用数学模型来描述其变化并可比较亲缘关系较远的 生物间的d n a 而形态性状的进化演变，即使在一段较短的进化时间，也是极其复杂 的，因而，基于形态的系统发生树的研究必然会有各种各样的假设，但这些假设往 旗。r 离敞度量的进化树构建方i ：左研究 往难以令人信服。第三，所有生物的基因组都是由长长的核酸序列组成，比形态 性状包含的进化信息要多得多。 构建进化树是系统发育分析研究的主要目的之一，通常分为3 个步骤：( 1 ) 分 子序列或特征数据的分析，( 2 ) 构建进化树，( 3 ) 进化树可靠性的评估。其中， 第( 1 ) 步的作用是通过分析，产生距离或者特征数据，为建立系统进化树提供依 据。 构建进化树的目的就是为了清楚明了的展现物种之间的系统发育历史，一般 来说，进化树是一种二叉树【3 】。所谓树，实际上就是一个无向非循环图。树的节 点代表物种：树的拓扑结构表现了各物种之间的进化关系；数的分支长度描述了 进化距离的时间。进化树有许多形式，一般的形式有：有根树和无根树；有根树 就是有一个唯一的根节点，代表所有其他节点的共同祖先。它能够反映树的进化 层次，从根节点历经进化到任何其他节点只有唯一途径。而无根树是没有层次结 构的，它只说明节点之间的关系，没有关于进化发生方向的信息。 构建进化树是生物信息学研究中的一个重要领域，除了对地球上物种的进化 史的研究，进化树的研究还有更多更加重要的意义。它有助于了解病毒传播的方 式，例如在非典时期，对各种s a r s 病毒的研究，通过构建系统发生树能确定各种 病毒之间的关系，得出病毒到底是由人类传染给动物，还是由动物传染给人类的； 有一些序列比对算法要依赖于进化树，所以它可以帮助科学家更好地比对蛋白质 和d n a 序列；有助于基因功能的研究，基因功能的预测往往是由于从该基因的进 化史中提炼得到的一一知道在一个机体中一个特定基因的功能对于在与该机体 亲缘关系紧密的机体中的相似基因的意义的了解非常重要；进化树可以很好的研 究进化，告诉我们一些进化机制以及不同的进化事件以及其产生的原因；假如用 序列的进化史作为指导树，在数据库中搜索同源序列关系的时候将会变得更加方 便等等。由此可见，进化树在在解决生物学的很多重大问题上都有非常重要意义， 从生物学领域到基因组学再到病毒学领域。因此，系统发生树的研究成了一个研 究热点。 然而从构建进化树算法来看，第一步分子序列或特征数据的分析，它的传统 方法一般是序列比对，因为全基因组序列的碱基数目往往达到几百万甚至足几十 亿b p 的数量级，并且基因重组现象广泛存在于不同物种的全基因组序列中，使用 者就需要设定参数、罚分、插入空位，因而引入了主观因素，破坏数据的原始状 态，导致计算结果因人而异。并且序列比对提高了进化树构建的成本，经过序列 比对得到的距离易受序列长度影响，与真实进化距离的差别较大。 1 2 国内外研究现状 构建进化树的常用方法主要分为两大类：基于距离法和基于特征法【4 8 1 ，从 2 硕仁学f 讧论文 而用于构建系统发生树的分子数据分成两类：( 1 ) 距离( d i s t a n c e s ) 数据，常用 距离矩阵描述，表示两个数据集之间所有两两差异；( 2 ) 特征( c h a r a c t e r s ) 数据， 表示分子所具有的特征。距离法需要首先得到一个反映序列之间差异程度的距离 矩阵，在此基础上，通过建立在不同的优化原则和假设基础上的各种建树算法完 成进化树的构建。而基于特征法，它们是基于符号或者特征的建树方法，并不需 要规定距离度量和计算距离矩阵，而是直接通过各分类群序列的碱基或氨基酸顺 序来构建系统树，通常而言其计算量要比距离矩阵法大很多，对于大宗系发育分 析而言距离法是比较常用的方法。 通常构建相似距离矩阵的是通过进行序列比对而计算两条序列之间的相似 度，但是因为全基因组序列的碱基数目往往达到几百万甚至足几十亿b p 的数量级， 时间和空间复杂度都是非常高的，并且基因重组现象广泛存在于不同物种的全基 因组序列中，使用者就需要设定参数、罚分、插入空位，因而引入了主观因素， 破坏数据的原始状态，导致相似距离矩阵的可靠性有所降低。这样就有一些学者 提出了不需要序列比对的图形表示的相似距离矩阵计算。以下分别介绍两种计算 方法。 1 2 1 基于序列比对的序列相似分析 分子系统发生分析的目的是探讨物种之间的进化关系，其分析的对象往往是 一组同源的序列。这些序列取自于不同生物基因组的共同位点。序列比对是进行 同源分析的一种基本手段，是进行系统发生分析的基础，序列比对算法( s e q u e n c e a l i g n m e n ta l g o r i t h m ) 是生物信息学的一个核心研究内容，是各种序列分析应用的 基础【9 】。因此，围绕如何在空间或时间上优化序列比对算法，学者们陆续提出了 各种各样的算法。正如课题背景中所提到的那样，序列比对算法主要分为两大类： 两序列比对和多序列比对。而两序列比对又可以依据其数学模型不同分为：两序 列全局比对和两序列局部比对。全局比对部分，n e e d l e m a n - - w u n s c h 算法是基本 的两序列全局比对算法，是许多后续方法的基础，但它的时间复杂度和空间复杂 度均为o ( m n ) 。其后，针对n e e d l e m a n - - w u n s c h 算法提出了很多改进的算法。其 中，h i r s c h b e r g 在l9 7 6 就如何降低比对的空间需求，提出一种线性空间复杂度的 两序列全局比对算法。局部比对部分，s m i t h - - w a t e r m a n 算法则是典型的两序列 局部比对算法，其在识别局部相似性时，具有很高的灵敏度。 经典的两序列比对算法有f a s t a 算法和b l a s t 算法，多序列比对如果直接 采用动态规划的思想，利用多维的动态规划矩阵来进行序列比对根本不现实，因 此目前大多数实用的多序列比对程序采用基于渐进思想的启发式算法，以降低运 算复杂度。其中使用最广泛的是f e n g 和d o o l i t t l e 在l9 7 8 年提出的c l u s t a l 算 法。 基于离敞度量的进化树构建方法研究 无论是d n a 序列，还是蛋白质序列，都是由特定字母表中的字符组成的。 计算序列之间距离的一个前提条件是要有一个字符替换模型，替换模型影响序列 多重比对的结果，影响系统发生树的构造结果。在具体的分析过程中，需要选择 一个合理的字符替换模型如各种打分模型或代价、距离模型。 距离( 或者相似度) 是反映序列之间关系的一种度量，是建立系统发生树时 所常用的一类数据。在计算距离之前，首先进行序列比对，然后累加每个比对位 置的得分。可以应用序列比较方法，直接计算序列之间的距离。如果在进行序列 比较时使用的是打分函数或相似性度量函数，则需要将相似度( 或者得分) 转换 成距离。令s ( i j ) 是序列i 和序列j 各个比对位置得分的加权和，一种归一化的距 离计算公式为： 2 l 。面s ( i 丽, j ) - s 丽( i , j ) ( 1 1 ) 其中，s ，( i ，j ) 是序列i 和j 随机化之后的比对得分的加权和，s m a x ( i ，j ) 是两条序 列所有可能的比对的最大值( 当两条序列相同时，取最大值) 。两个序列归一化距 离的值处于0 和l 之间，当两个序列完全一致时，距离为o ；当两个序列差异很 大时，距离接近于l 。如果在上式中令s r ( i , j ) = 0 ，则计算公式变为： d ( i ，j ) = 1 二掣 ( 1 2 ) 3 ，一l l j j 为了适合于处理相似性较小的序列，可以进一步修改距离计算公式： d ( i j ) = 一l n 掣娑 ( 1 3 ) 3 m 戤l l ，j j 序列比对得分的加权和可以根据常用的打分矩阵获得，如果待处理的序列是 蛋白质，则用p a m 矩阵、b l o s u m 矩阵等；如果待处理的序列是d n a 或者r n a ， 则用等价矩阵、核苷酸转换颠换矩阵或者其它具有非对称置换频率的矩阵。 传统的距离法一般通过多序列比对计算距离矩阵，而多序列比对是一个n p 难问题，王方圆等【】试图通过利用一种满足三角不等式的归一化编辑距离来绕过 多序列比对的困难，但仍然需要对序列进行两两比对分析。 1 2 2 基于图形表示的序列相似分析 用四种字母表达的d n a 序列，是d n a 序列的传统形式，它在存储和提供计算 机进行快速分析等方面具有不容争议的优点，因此得到了广泛应用。但它也存在 严重的缺陷。图形表示的研究正是从克服它的缺陷开始的。它的缺陷之一是忽视 了人脑在模式识别方面的强大能力。那么利用图形来表示生物的原始序列可以使 我们更加直观的观察生物序列。他们使用图形表示的基本思想是：先将序列转化 为图形表示，然后根据图形表示构造矩阵，利用与矩阵相关的不变量来分析生物 4 硕 ：学化论文 序列的相似性等问题，下面我们就介绍几种典型的d n a 序列的图形表示方法。 1 9 8 3 年e h a m o r i 和j r u s k i n 提出了d n a 序列图形表示的思想一将d n a 序列表 示为一条平面或者空间中的曲线一g 曲线和h 曲线。g 曲线是一种5 维空间表示， 其中4 个坐标方向分别为四种核苷酸，剩下的一个方向表示d n a 序列核苷酸的位 置，但是这一方法不能实现可视化【l 。改用两个坐标轴的四个方向表示四种核苷 酸似一；g 一姬；c 一目；丁一s 叨，另一个方向表示核苷酸的位置，这时，曲 线变成3 维空间曲线，这就是h 曲线。 二维坐标轴图形表示：( 1 ) 1 9 8 6 年m a g a t e s 提出最早的二维图形表示：+ x 轴方向单位向量为c ，一x 轴方向单位向量为g ，+ y 轴方向单位向量为t ，y 轴方向 单位向量为a 。( 2 ) 1 9 9 4 年a n a n d y 给出的二维图形表示为【1 2 l ：+ x 轴方向单位向量 为g ，x 轴方向单位向量为a ，+ y 轴方向单位向量为c ，y 轴方向单位向量为t 。( 3 ) l9 9 5 年p m l e o n g 和s m o r g e n t h a l e r 提出另一个二维图形表示为：+ x 轴方向单位 向量为a ，x 轴方向单位向量为c ，+ y 轴方向单位向量为t ，y 轴方向单位向量为g 。 这三种表示法均以原点为初始点，每增加一个碱基就按照所给出的方向增加 一个单位向量。三种方法都可能出现图形上的交叠现象( 退化) ，例如在g a t e s 表示方法下g c ，g c g ，g c g c ，g g c g c 的图形将很难区分，n a n d y s 表示方法下 g a ，g a g ，g a g a ，g g a g a 的图形将很难区分。 y y x c 0 g a t t x 基于离散度量的进化树构建方法研究 y t - oa i t 一 g c x 图1 1 二维图形的三种坐标 ( 从左至右然后之下分别为g a t e s ，n a n d y ，l e o n g 和m o r g e n t h a l e r ) 我国著名理论物理专家张春霆院士也提出了一种d n a 几何图形表示一z 曲 线，z 曲线是表示d n a 序列的一个等价三维空间曲线。通过对z 曲线的研究来对基 因组序列进行研究是一种几何学的途径。利用z 曲线研究了真核和原核基因组中 若干重要问题，证明这样的思路是可行的d 3 1 。 考虑长度为n 的单链d n a 序列，该序列的z 曲线包含一系列的点p o p ，p 2 p ， 相应的坐标( ，儿，乙) ，n = 0 ，l ，2 ，n ， i = ( 4 + q ) 一( e + r 。) 几= ( 4 + g ) 一( g + r 。)矗，儿，乙【- n ，n 】，n = 0 ，l ，2 ，n( 1 4 ) i 乙= ( 4 + 乙) 一( q + c 。) 从l 到刀这个子序列中四种碱基各自出现的次数分别用4 ，q ，e ，瓦表示。 z 曲线的三个分量有着明确的生物学意义：( 1 ) 工。表示嘌呤( a + g ) 嘧啶( c + t ) 碱基沿序列的分布。当嘌呤碱基的数目多于嘧啶碱基时，瓦 0 ；否则，瓦 0 ；否则 0 ；当序列中弱氢键碱基少于强氢键碱基时，z 。 0 ；当序列中弱 氢键碱基等于强氢键碱基时，z 。= 0 。 李春给出了的一种三维图形表示【1 4 】，其向量表示为：( 1 ，0 ，o ) 一彳，( 0 ，l ，0 ) 一 c ， ( 0 , 0 ，1 ) 一g ，( 1 ，l ，1 ) 一丁。廖波等对四种碱基赋予不同的向量坐标提 出了一系列三维图形表示【1 5 , 1 6 , 1 7 。 另外廖波教授在后来的研究中，于2 0 0 6 年又提出了一种高维的表示【l 引。所有 的d n a 序列的高维表示都具有类似的特征，即从几何角度出发，找到一个适当的 对应法则把d n a 的四种碱基对应到高维空间中。 由d o u g l a s 提出的w c u r v e 1 9 】也是一种比较优秀的序列图形化表示方法，它可 6 硕一i ：学位论丈 以把d n a 序列中的碱基映射到一个连续的空间中，利用该w 曲线可以进行序列比 对，同时也被成功的运用到单核苷酸多态性的识别问题中，如图1 2 ： 帕f j e 么 麟 f p 水3 。 f - ” | f 晌 担叶c c 图1 2w 曲线核苷酸坐标位置( 左) 和w 曲线核苷酸映射( 右) 当序列用图形表示在坐标系之后，我们就可以运用现有的几何距离公式来计 算序列之间的距离。如：海明距离法；欧式距离法；切比雪夫距离法；绝对值倒 数法；绝对值指数法；指数相似系数法；兰氏距离法；数量积法；夹角余弦法： 相关系数法：最大最小法；算术平均最小法；几何平均最小法。我们以i 和i 分别 代表两个物种，k 代表物种的第k 个特征，c 为一个常数为例，对上述公式介绍一下： 海明距离法：勺= l c i 一i ( 1 5 ) k = l 一 欧式距离法：勺= 1 - c x ( - x j k ) 2 ( 1 6 ) yk = l 切比雪夫距离法：吩2 1 _ c m a x 。i x i k 一l ( 1 7 ) 鲥制黼 古 l = j ， 1 j ； 绝对值指数法：乃= e x p ( 一c l 一i ) 七= l 指数删系数法：= 去扣卜三( 警) 2 】 其中瓯= “ 1 j k 2 i 毛毛t 兰氏距融一一c 喜鼎 7 ( 1 8 ) 、，、，、，、， 9 0 1 2 1 ，-、1li 1 l ，l，l，l 基于离散度帑的进化树构建方法研究 数量积法： 夹角余弦法：= l = j ， 1 j ； x 71 1 厶一“i k “j k k = l ( h 一_ ) ( 一x j ) 相关系数法：= 1 兰一 、( ( 一i ) 2 ) ( ( b i ) 2 ) 其中i = 去善，i = 去善 m i n ( x ，k ，) 最大最小法：= 专l 一 m a x ( x ；k ，啄) 算术平均最小法：= e m i n ( x ，k ，) 三! 去( + ) m i n ( x ；k ，) 几何平均最小法：r i = 生l _ 一 、3 x k x j k ( 1 1 3 ) ( 1 1 4 ) ( 1 1 5 ) ( 1 1 6 ) ( 1 1 7 ) ( 1 1 8 ) ( 1 1 9 ) 各方法都有优缺点，比较常用的方法有两种是欧式距离法和夹角余弦法；欧 氏距离法事计算两个物种的欧式距离，如果两个物种的欧式距离较小就认为这两 个物种比较相似；夹角余弦法，计算物种之间夹角所对应的余弦值，如果两个物 种的余弦值较大就认为这两个物种比较相似。 1 2 3 构建系统进化树的数据集及相关软件 c 。心 ，、 = 吩 硕- 学化论文 p h y l i p ( p h y l o g e n yi n f e r e n c ep a c k a g e ) ，是由f e l s e n s t e i n 所编写的一个系 统发生推断软件包，目前已经广泛应用于系统发育方向的研究。p h y l i p 是一个免 费的软件，并且软件以源程序形式提供，可以在很多平台上进行运行。p h y l i p 包 含了大约3 0 个程序的软件包，有极大似然法，最大简约法，基于距离矩阵法和其 他一些非常有用的程序，这些程序基本上包括了系统发育的所有方面。 目前通常使用p h y l i p 软件中的n e i g h b o r e x e 程序对提出的构建进化树方法构 建的进化树进行可靠性检验和评估。除了p h y l i p 软件以外，还有其他一些系统发 育软件，例如：c l u s t a w ，p a u p ，和m e g a 等【2 们。 1 3 本文的主要研究工作 从上一节我们可以知道构建进化树的方法主要分为两大类：基于距离矩阵法 和基于特征法。其中，基于距离矩阵法以结构简单，良好的理论基础等特点得到 了广泛的应用。但是研究指出一些基于距离矩阵的构建进化树方法在某些情况下 会产生拓扑结构不唯一的进化树结果，而且是建立的序列比对的基础上，因为全 基因组序列的碱基数目往往达到几百万甚至足几十亿b p 的数量级，时间和空间复 杂度都是非常高的，并且基因重组现象广泛存在于不同物种的全基因组序列中， 使用者就需要设定参数、罚分、插入空位，因而引入了主观因素，破坏数据的原 始状态，导致计算结果因人而异。所以本文为了解决这个问题，提出了新的相似 距离度量算法离散度量，这种度量法度量序列之间的距离不需要序列比对，没有 主观因素干涉，而且比较直观，计算量小，实验证明在此基础之上建立的相似距 离矩阵对于构建进化树有着较好的效果。 1 4 本文的章节安排 论文的章节安排如下： 第一章简要介绍了分子系统发生学与系统发育分析的背景，系统进化树的构 成以及构建进化树的理论意义和实际应用意义。然后介绍了在过国内外一些已有 的构建相似距离矩阵方法的研究现状，并对各方法的缺点和优点做出来简要的分 析；还介绍了为了评估系统进化树的所需要的数据集和分析软件；最后讲述了本 课题所完成的工作内容。 第二章详细介绍了离散度量方法和进化树构建方法。 第三章提出一种基于信息增益的离散度量，并对一种构建进化树方法进行了 改进，详细描述该度量方法以及改进算法的思想；并通过实验数据验证方法的可 行性。 第四章用l a b v i e w 实现了基于该改进算法的进化树构建系统。 9 肇丁离散度嚣的进化树构建方法研究 结论最后总结本文并展望未来，并对计算分子生物学的发展趋势进行分析和 预测。 硕l ：学化论文 第2 章离散度量方法和进化树构建算法 在第一章中提到构建相似距离矩阵的一些比较常用方法。但是传统的基于序 列比对获取的相似度量由于引入了主观因素，破坏数据的原始状态，导致相似距 离因人而异。并且序列比对不但提高了进化树构建的成本，而且经过序列比对得 到的距离易受序列长度影响，与真实进化距离的差别较大。这一章会介绍建立在 信息理论法基础上提出来的离散度量，并在此基础上讨论构建进化树的方法