（计算机科学与技术专业论文）基于图形表示的dna相似性分析及进化树构建算法研究.pdf

硕上学位论文 摘要 随着人类基因组计划( h u m a ng e n o m ep r o j e c t ，h g p ) 的完成以及模式生物基因 组计划的蓬勃发展，产生了越来越多的分子序列数据。对这些序列数据进行科学 的分析、处理、研究不仅推动了生物信息学研究方法和技术的发展，而且在人类 疾病及重大疫情的预防、诊断、治疗、新药开发等领域也有着广阔的应用背景。 如何给出有效的基因序列图形表达方式并在此基础上对基因进行相似性分析及进 化关系分析已成为生物信息学中一个热门的课题。 本文着重研究基因序列的图形表达，基于图形表达的基因序列的相似性分析 以及采用聚类技术分析基因序列的进化关系。本文的主要工作有： ( 1 ) 提出一种新的d n a 序列的图形表示一一j z 曲线组。在z 曲线的基础上 结合廖波3 d 图形表达方法给出了一种新的图形曲线j z 曲线组，证明了j z 曲 线组中没有回路，同时j z 曲线组包含部分的生物特性。 ( 2 ) 构造了d n a 序列间相似性度量的特征矩阵一一j j 矩阵。结合j z 曲线组 的j j 矩阵不仅描述了序列碱基的化学性质，而且提取了基因序列的生物意义。 并通过对1 1 种生物的球蛋白基因的第一外显子的编码序列进行相似性分析，实 验结果表明，在j z 曲线组的基础上结合j j 矩阵可以简单有效的分析d n a 序列 的相似性。 ( 3 ) 基于j z 曲线组，提出一种基于谱图理论的模糊聚类的传递算法构造进 化树。对序列的进行聚类，以聚类结果指导构建进化树，确定序列间的进化关系。 同时，聚类算法不仅考虑了类与类之间的分散程度，而且考虑了同一类的紧凑程 度，提高了结果的准确性。通过对1 1 种生物的口球蛋白基因的第一外显子的编码 序列以及h 1 n 1 病毒的n a 基因序列构建进化树，实验结果表明该算法的有效性。 关键词：d n a 序列；图形表达；特征矩阵；进化树构建算法 i i 基于图形表示的d n a 相似性分析及进化树构建算法研究 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fh g p ( h u m a ng e n o m ep r o j e c t ，h g p ) a n dm o d e l o 唱a n i s mg e n o m e - s e q u e n c i n gp r o je c t s ，m o r ea n dm o r em o l e c u l a rs e q u e n c e sd a t ah a v e b e e ng e n e r a t e d t h es c i e n t i f i ca n a l y s i s ，p r o c e s sa n dr e s e a r c ho ft h e s ed a t an o to n l y a c c e l e r a t e st h ed e v e l o p m e n to fb i o i n f o r m a t i c s ，b u ta l s oh a sb r o a d a p p l i c a t i o n b a c k g r o u n di nt h ef i e l d so fh u m a nd i s e a s ep r e v e n t i o n ，d i a g n o s i s ，t r e a t m e n ta n dn e w d r u gd e v e l o p m e n t h o wt o g i v e e f - f e c t i v eg r a p h i c a l r e p r e s e n t a t i o n o ft h e g e n e s e q u e n c e s ，a n a l y s i s o f g e n e t i cs i m i l a r i t y a n d e v o l u t i o n a r yr e l a t i o n s h i p o f b i o i n f o r m a t i c sh a v eb e c o m eah o t t o p i c t h i sd i s s e r t a t i o nm a i n l ys t u d y st h eg r a p h i c a lr e p r e s e n t a t i o no fd n a s e q u e n c e ， t h es i m i l a r i t ya n a l y s i so fb i o l o g i c a ls e q u e n c e sa n dt h ea l g o r i t h mf o rc o n s t r u c t i n gt h e p h y l o g e n e t i ct r e e t h em a i na c h i e v e m e n t sa r es u m m a r i z e da sb e l o w ： f i r s t l y ， t h ej z c u r v e ，an e wg r a p h i c a le x p r e s s i o no ft h eg e n es e q u e n c e ，i s i n t r o d u c e d b yd e f i n i n gt h r e em a t h e m a t i c a lm a p p i n g ， ag e n e s e q u e n c ec a nb e t r a n s f - o r m e di n t ot h r e ec u r v e s i t p r o v e st h a t t h ej z c u r v en o to n l ya v o i d st h e l i m i t a t i o n sa s s o c i a t e dw i t hc r o s s i n ga n do v e r l a p p i n g ，b u ta l s or e t a i n st h eb i o l o g i c a l i n f o r m a t i o no fg e n es e q u e n c e s s e c o n d l y ，w ec o n s t r u c tan e wc h a r a c t e r i s t i cm a t r i x ，n a m e dj jm a t r i x w h e nw e s t u d yt h es e q u e n c ec o m p a r a b i l i t yb a s e do ng r a p h i c a lr e p r e s e n t a t i o no fe i n as e q u e n c e ， t h ej jc h a r a c t e r i s t i cm a t r i xb a s e do nj z c u r v ec a nd e s c r i b et h ec h e m i c a l c h a r a c t e r i s t i ca n dt h eb i o l o g i c a ls i g n i f i c a n c eo fg e n es e q u e n c e s t h ee x a m i n a t i o no f s i m i l a r i t i e s d i s s i m i l a r i t i e sa m o n gt h ec o d i n gs e q u e n c e so ft h ef i r s te x o no fp - g l o b i n g e n eo fd i f f e r e n ts p e c i e s 订l u s t r a t e st h eu t i l i t yo ft h ea p p r o a c h t h i r d l y ，b a s e do nt h ej zc u r v e ，af l u z z yc l u s t e r i n ga l g o r i t h mo nt h eb a s i so f s p e c t r a lg r a p ht h e o r yf b rc o n s t r u c t i n gp h y l o g e n e t i ct r e ei sp r o p o s e d w i t ht h ec l u s t e r a n a l y s i sm e t h o d ， w eb u 订d p h y l o g e n e t i c t r e e sa n dd e t e r m i n et h e e 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 e q u e n c e s m e a n w h i l e ，t h ea l g o r i t h mn o to n l yc o n s i d e r st h e d i v e r g e n c eb e t w e e nc l a s s e s ，b u ta l s oc o n s i d e rt h es i m i l a r i t yb e t w e e nc l a s s e s ，i n c r e a s e t h ea c c u r a c yo ft h er e s u l t s t h ep h y l o g e n e t i cr e l a t i o n s h i p sf o rt h ec o d i n gs e q u e n c e so f t h e6 r s te x o no f - 9 1 0 b i ng e n eo f1 1d i f f e r e n ts p e c i e sa n dt h en a ( h 1 n 1 ) s e q u e n c e s o fa v i a ni n n u e n z av i r u si l l u s t r a t et h a ta l g o r i t h mi sc r e d i b l e i i i 硕上学位论文 k e yw o r d s ：d n as e q u e n c e ；g r a p h i c a lr e p r e s e n t a t i o n ； c h a r a c t e r i s t i cm a t r i x ； a l g o r i t h mf o rc 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 i v 基于图形表示的d n a 相似性分析及进化树构建算法研究 插图索引 图2 1 二维图形的三种坐标一8 图2 2f m 分枝法1 4 图2 3 邻接法星形图1 5 图2 4 距离法生成进化树的流程图t 1 6 图3 11 1 个物种的p 球蛋白基因的第一外显子的j z ( 1 ) 曲线2 5 图3 211 个物种的d 球蛋白基因的第一外显子的j z ( 2 ) 曲线2 5 图3 31 1 个物种的p 球蛋白基因的第一外显子的j z ( 3 ) 曲线一2 6 图4 1 基于模糊相似矩阵对1 1 个物种球蛋白基因聚类得到的进化树3 9 图4 2 基于新的聚类矩阵对1 1 个物种球蛋白基因聚类生成进化树4 0 图4 31 1 个h 1 n l 病毒序列的j z ( 1 ) 曲线。4 2 图4 41 1 个h 1 n l 病毒序列的j z ( 2 ) 曲线一4 2 图4 51 1 个h 1 n 1 病毒序列的j z ( 3 ) 曲线4 3 图4 6 基于新的聚类矩阵对1 1 个h 1 n 1 病毒聚类生成的进化树4 4 图4 78 个h 1 n l 病毒序列的j z ( 1 ) 曲线一4 6 图4 88 个h l n l 病毒序列的j z ( 2 ) 曲线4 6 图4 98 个h 1 n 1 病毒序列的j z ( 3 ) 曲线4 6 图4 1 0 基于新的聚类矩阵对8 个h 1 n 1 病毒聚类生成的进化树4 7 v i i 硕上学位论文 附表索引 表3 11 1 个物种的d 球蛋白基因的第一外显子的d n a 序列2 4 表3 2 基于j z 曲线组的l ，l 矩阵和j j 矩阵正则化最大特征值2 8 表3 3 基于j z 曲线组和l l 矩阵计算1 1 个物种的相似性距离矩阵2 9 表3 4 基于j z 曲线组和j j 矩阵计算1 1 个物种的相似性距离矩阵2 9 表3 5 “个物种与其它1 0 个物种的相似性之和一3 0 表3 6 基于j z 曲线组的l l 矩阵和j j 矩阵正则化最大特征值3 0 表3 7 基于j z 曲线组和l l 矩阵计算1 1 个物种的相似性距离矩阵3 0 表3 8 基于j z 曲线组和j j 矩阵计算1 1 个物种的相似性距离矩阵3 1 表3 91 1 个物种与其它1 0 个物种的相似性之和3 1 表3 1 0g a l l u s ，o p o s s u m 与其他1 0 个物种的相似性之和3 2 表4 1 构造1 1 种生物口球蛋白基因的模糊相似矩阵3 8 表4 2 基于图谱理论构造l1 个物种口球蛋白基因的新聚类矩阵3 8 表4 3 基于模糊相似矩阵对1 1 个物种球蛋白基因的聚类结果3 9 表4 4 基于新聚类矩阵对1 1 个物种球蛋白基因的聚类结果4 0 表4 51 1 个h 1 n 1 病毒n a 基因序列4 l 表4 6 基于图谱理论构造1 1 个h 1 n 1 病毒的新聚类矩阵4 3 表4 7 基于新聚类矩阵对1 1 个h l n l 病毒的聚类结果4 4 表4 88 个h 1 n 1 病毒n a 基因序列4 5 表4 9 基于图谱理论构造8 个h 1 n 1 病毒的新聚类矩阵4 7 表4 1 0 基于新聚类矩阵对8 个h 1 n 1 病毒的聚类结果4 7 v i i i 硕士学位论文 第1 章绪论 各种基因组计划的持续开展和模式生物基因组计划的蓬勃发展，标志着人类 在探索生命奥秘的漫长道路上又迈出了重要的一步，同时产生的包括生物体生老 病死的生物数据以前所未有的速度递增。迅速膨胀的生物数据给科学家们提出了 严峻的挑战：如何有效管理、准确解读、充分使用这些信息? 如何有效的挖掘生 物这本“四字天书”的奥秘? 生物信息学便是在生物数据的急剧膨胀的压力下诞 生了。随着后基因组时代的来临，生物信息的提取和数据分析已成为即生物信息 学一个重要的研究方向。如何给出有效的基因序列图形表达方式并在此基础上对 基因进行相似性分析及进化关系分析已成为生物信息学中一个热门的课题。本章 将阐述序列的相似性分析以及构建进化树的相关概念和重要意义，并引出本文的 主要工作和结果组织。 1 1 项目来源 本学位论文的研究工作主要得到如下项目的资助： ( 1 ) 国家自然科学重点基金项目【6 0 8 7 3 1 8 4 】：新型表达模式下的功能基因分 析算法研究。 ( 2 ) 湖南省自然科学重点基金项目【0 7 j j 5 0 8 6 】：基于聚类的基因功能预测方 法。 1 2 研究背景和意义 随着各种基因组计划的持续开展和模式生物基因组计划的蓬勃发展，生物数 据成指数级增长，对这些生物数据进行科学的分析和研究不仅在人类疾病及重大 疫情的预防、诊断、治疗、新药开发等领域有着广阔的应用背景，而且促进了生 物信息学这一交叉性学科的兴起和发展。生物信息学( b i o i n f o r m a t i c s ) 是生物学、 计算机科学、信息科学以及应用数学等学科相互交叉所形成的一门新兴学科【1 2 】。 它以计算机和网络为工具，以数学和信息科学等方法为手段，以读懂人类基因组， 发现人类遗传语言的根本规律，阐明若干生物学中的重大自然问题为目的，对生 物信息进行存储、检索和分析【3 4 j 。随着后基因组时代的来临，生物信息的提取和 数据分析已成为即生物信息学一个重要的研究方向。 数据挖掘是近年来新兴的一种科学计算技术与数据分析方法，它就是从大量 的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事 先不知道的但又是潜在有用的信息和知识的过程【5 】。生物信息的数据挖掘在商业 基于图形表示的d n a 序列相似性分析及进化树构建算法研究 上很难讲有多大的价值，但对于人类却受益非浅，这不仅有助于我们了解生命本 质和进化过程，同时对新疗法和新药物的发现具有重要意义【6 】。因此如何将众多 的数据挖掘技术应用于生物数据信息分析是当前的研究热点，其中包括生物数据 挖掘体系架构的设计、各种分析算法的研究以及针对生物数据挖掘分析的功能研 究等【7 ，8 1 。 随着基因数据的增长，传统的生物数据字母表示方法已不能满足人们简单、 形象和整体把握长序列的要求【9 】。由于图形具有简单，直观等特点，因此越来越 多的学者采用图形表示法描述生物数据。图形表示法的优点之一是具有很强的直 观性，与字母表达方法相比，图形表示法更能调动人脑的参与性，在基因序列的 相似性分析、功能区的识别以及物种进化关系等领域中，促进了创新性的研究方 法的产生，在认识与分析基因序列的过程中开创了生物信息学研究的新领域【9 1 。 但是图形表示存在回路，丢失生物信息等缺点，因此如何给出有效的图形表示方 法是目前生物学的一个研究热点。 序列的相似性( s i m i l a r i t y ) 指一条d n a 或蛋白质序列与另一条序列的相似程 度。研究序列相似性的目的有两个，一个是通过相似的序列得到相似的结构或相 似的功能；另一个目的是通过序列的相似性判别序列之间的进化关系。在后基因 组时代，人们通过检测新测定序列与已注释的数据库中已知结构和功能的序列之 间的相似性关系可以推测新序列的结构和功能信息，通过比较不同物种的相同保 守结构域的异同可以揭露物种的进化关系，通过比较正常样本序列与致病样本序 列之间的差异可以发现致病基因并开发新药物，因此序列的相似性分析成为基因 功能确认的必要步骤，是研究物种的纵式进化方向以及基因横向转移( l g t ) 的重 要手段，同时在人类疾病以及重大传染病毒的认识、治疗、新药开发等领域有着 广泛的应用背景。由此可见，序列相似性分析是生物信息学领域中一个基础而又 非常重要的研究内容，它分析结果的准确性对研究物种分类、生物进化关系、结 构和功能预测、新药物和新治疗方案的发现等起着关键性作用【1 4 1 、在生物信息 学中有着广泛的应用，因此序列的相似性是一个非常具有研究意义的课题。 系统发生学研究物种之间的进化关系，一个系统发生推断往往以进化树的形 式表现出来，其目的是认识物种代谢、发育、分化、进化的规律。一个可靠的系 统发生的推断对认识自然发展非常重要，它有助于通过分析构建系统发育树的过 程揭示出有关生物进化的顺序、有助于通过物种间隐含的种系关系揭示进化动力 的实质、有助于我们了解生物进化的历史和进化机制【1 0 】。同时研究生物进化树对 解决现代分子生物学中的许多问题也是非常关键的，如多序列比对、蛋白质结构和 功能预测以及药物设计等等。因此重建物种的系统发育树 1 2 】是现代分子进化研 究的一个重要问题。 2 硕上学位论文 1 3 国内外现状、水平与发展趋势 2 1 世纪生物信息学蓬勃发展，它的研究成果不仅对相关的基础学科起巨大的 推动作用，而且还对医药、卫生、食品、农业等领域产生巨大的影响【9 j 。在国外， 生物信息学的发展一直受到高度重视，生物信息数据中心如雨后春笋般纷纷成立， 如日本信息生物学中心( c i b ) 、欧洲生物信息学研究所( e b i ) 、美国的国家生物技 术信息中心( n c b i ) 、国家基因组资源中心( n c g r ) 等。其中连接了2 2 个国家节点 和8 个生物计算中心的e m b n e t ( e u r o p e a nm 0 1 e c u l a rb i o l o g yn e t w o r k ) 已经成为全 球最大的生物信息学网络中心【l 4 8 】。在我国，生物信息学的发展起步稍晚一些。 目前，国内也成立了一些有名的研究单位，如北京大学生物信息中心、天津大学 生物信息中心、中科院遗传所人类基因组中心、中科院计算所生物信息学实验室、 联合基因集团有限公司、上海生命科学研究所、复旦理论生物中心等等。同时， 有些学者在国际上取得了一定成绩，如北京大学的罗静初、顾孝诚两位教授在生 物信息学网站建设方面，天津大学的张春霆院士在d n a 序列的几何学分析方面 【3 9 j ，中科院生物物理所的陈润生研究员在e s t 序列拼接方面以及在基因组演化 方面【2 】，均已接近世界先进水平。近几年，我国加大对生物信息领域的研究投入 力度：国家8 6 3 计划生物和现代农业技术领域专门设有生物信息技术主题，国家 自然科学基金委员会将该主题列为重要发展方向，国家9 7 3 计划也已开始对该主 题立项。 用图形表达方法描述基因序列因其具有独特的直观性受到越来越多的学者关 注1 1 2 】，目前在基因序列图形表达研究中涌现出了很多模型：e h a m o r i 和j r u s k i n 于1 9 8 3 年首先提出了g 曲线【l3 1 ，该方法首次实现了基因序列的图形化表达，但 是由于g 曲线是一种5 维空间表示，所以不具有图形可视化的优点：g a t e s ，n a n d y ， l e o n g 和m o g e n t h a l e r 提出了基于正交坐标系d n a 序列2 维图表示【1 4 1 引，这是最 早的二维基因图形表示，具有可视化优点，但是这些图形可能出现回路，因此不 能很全面的描述生物信息；j e f f r e y 在1 9 9 0 年基于混沌理论提出的c g r 图形表示 方法【l7 1 ，该方法将序列对应于一张揭示其固有分形结构的图，在处理基因组分析 等领域取得了很好的结果；张春霆院士提出z 曲线理论【3 ，9 ，1 7 ，1 引，首创了一个利用 几何学方法分析和研究d n a 序列的崭新领域，但是z 曲线的缺陷是存在回路。 为了避免回路，廖波等提出了一系列图形表示【1 9 2 3 1 ，张惜珍【2 4 1 基于廖波引入参数 的3 d 图形表示法和张春霆院士的z 曲线提出的n 曲线，都很好的解决了退化现 象，避免了图形表达中的重叠与交叉所产生的信息丢失。可以预测，基因序列的 图形表示的研究将会有一个广阔的发展空间。 序列相似性分析是计算机在生物学中应用的热点之一。g i b b s 于19 7 0 年提出 的点阵法【25 j 是最早的序列的相似性分析算法，其基本思想是当相同的字母在两条 基于图形表示的d n a 序列相似性分析及进化树构建算法研究 序列中同时出现时，在交叉处置点。之后m a i z e l 利用带颜色的点阵法来进行氨基 酸和核酸的序列比较。n e e d l e m a n 和w u n s c h 在1 9 7 0 年提出了一种全局优化的序 列比对算法1 2 6 j ，s m i t h 和w a t e r m a n 在1 9 8 1 年提出了一种局部最优的序列比对算 法1 2 ，这两种算法的思路都是动态规划算法允许匹配、错配和缺失。但所需的时 间和空间复杂度很高，不适应于数据库的搜索。随后出现了各种启发式算法，其 中最有名的是l i p m a n 和p e a r s o n 在1 9 8 1 年提出的剧s 尉算法【弱j 和a l t s c h u l 在1 9 8 8 年提出的口鲥s 一2 9 】算法。对这些算法的改进算法已有数十种之多【30 1 。由于上述算 法存在计算复杂度高，计算量繁琐等缺点，2 0 0 0 年r a n d i 等人首次提出来的利用 矩阵的方法1 3 l j 比较生物序列，这使复杂的问题简单化了。他的基本思想是先构造 一个适当的矩阵来表示一个序列，然后考虑这些生物序列的不变量，这样序列之 间的比较就转化为矩阵不变量之间的比较。现有的矩阵包括【3 l j e e 矩阵、m m 矩 阵、l l 矩阵( 也叫d d 矩阵) 、高阶矩阵、压缩矩阵，它们具有各自的特点： e e 矩阵的元素代表着各点之间的直线距离，其缺点是随着序列长度的增加元素 值增加，当序列过长时矩阵元素值差异度很大，不利于后期数据处理；m 似矩阵 是一个对称矩阵，m m 矩阵能够有效的纠正m m 矩阵出现的元素差异度过大的 问题；l l 矩阵是在m m 矩阵的基础上将元素值归一化，所有元素值少于l ；高 阶矩阵是一个o ，l 矩阵，计算量大。现有的矩阵不变量有矩阵最大特征值五，最 大( 小) 行和，次对角线上所有元素和的平均值，矩阵的迹等等。2 0 0 5 年李春给 出的彳上e 一伽如x 不变量【3 2 】，并证明么e 砌比x 不变量，数值上接近矩阵最大特征值 五，但计算量明显小于a 。2 0 0 6 年张玉森考虑行平均值提出的砌v 不变因子【3 3 】，并 证明砌v 不变量的计算量优于李春的彳三e 加如x 。张惜珍提出的z ，聆v 不变量【2 4 】 计算简单并且相对其他不变量更接近于矩阵最大特征值不变量。汪挺松直接利用 图形的曲率【3 4 】作为新的不变量比较生物的相似性，计算复杂度大大降低。郑文新 【35 j 在z 益线上计算图形的中心点，】，动来刻画序列的曲线分布，但是现有的不 变量刻画和比较生物序列方法会伴随某些结构方面的信息丢失，进而实现生物序 列的相似性比较。2 0 0 6 年n a n d y 等人通过比较上述方法发现不同的矩阵方法度量 序列的相似性会得到不同的结果【36 1 ，并分析认为主要原因是因为这些方法只考虑 了序列的组成碱基的位置，没有考虑到模型与序列的相关性以及碱基突变或退化 等生物意义。除此之外，也有人考虑生物的进化距离，密码子的语义性特点，密 码子使用偏好等指标比较生物间的相似性【3 7 】。 进化树构建就是在序列相似性分析的基础上，建立各个物种的进化关系，将 生物合理地分成一定的类群，使得同一类群类内的个体成员相似。迄今为止，人 们已经发展出各种各样的进化树构造方法。总体上可以分为两类【1 0 ，1 1 ，3 8 ，3 9 j ：距离 矩阵法和非距离矩阵法。对于距离矩阵方法，经典的算法有d a v et h o m a s 提出 u p g m a 算法构建进化树【4 0 】；c h r i s 提出的f i t c h m a r g o l i a s h 算法【4 1 】；s a i t o un 提 4 硕上学位论文 出的n j 算法1 4 2 1 。非距离矩阵法中比较常见的有最大简约法( m a x u n u l n p a r s i m o n y ) 4 3 】和最大似然法( m a x l n u ml i k e l i h o d ) 4 4 1 ，非距离矩阵法中通常对所研 究的序列的进化速率和核昔酸的替换模式要求明确，因此计算上非常繁杂，耗费 相对较多的时间。目前对距离矩阵的构树算法改进方法很多。针对u p g m a 生成 二叉树的不唯一问题，徐立业等人【4 5 】提出了不加权算术平均组群方法，通过在迭 代过程中把完全图中所有最小元素对应的分类群按照“属于同一连通分枝 这一 等价关系生成聚类单元，解决了u p g m a 建树的唯一性问题。谭严芳等人【4 6 】借鉴 u p g m a 算法的中每次挑选具有最小距离的节点作为近邻的思想，同时考虑n j 算法中的校正距离，采用k i m u r a 的两参数模型，大大的提高n j 算法效率。针对 n j 得到的拓扑图形不够精确的问题，v i n c e n tr a n w e z 等人1 4 7 j 将最大似然法引入 n j 算法中，提出了t r i p l e m l 法，能够更精确的计算了两序列间的距离值，从而 提高了n j 建树的精确度。s a t o s h i o t a 等人【4 8 j 同样将最大似然法引入n j 算法中， 提出了n j m l 方法，该方法采用了“d i v i d e a n d c o n q u e r 的机制，通过探索拓扑 结构，寻找最佳的拓扑图形。这些方法都是融合经典构树算法而产生新的构树算 法。同时，随着聚类算法的发展，也有人基于图形表示采用聚类算法指导构建进 化树。这种构树方法避免了序列比对，不需要考虑基因突变，颠覆等操作，使得 基于基因族组数据进行相似关系分析称为为可能。郑文新p5 】在z 曲线的基础上提 取几何中心和协方差矩阵，然后通过计算最大特征值和相应的向量之间夹角余弦 值获得距离，利用p h y l i p 软件包中的u p g m a 方法构建进化树。张建辉【4 9 】在序 列3 d 图形的基础上，使用p h y l i p 软件包中的n j 方法指导构建进化树，并对全 基因组数据进行进化关系分析。张惜珍等人【2 4 j 在n 曲线的基础上根据可凝聚的层 次聚类算法对1 2 种禽流感病毒基因构建进化树，结果与经典的f h y l i p 构树方法 一致。2 0 0 6 年廖波等人【2 3 j 在自己给出的2 d ，3 d 图形中运用模糊聚类的传递闭包 法构建进化树。柳菁筠等人【5 l 】将图论融合于模糊聚类中，将模糊相似矩阵转化为 一个带权值的连通图，在连通图中应用经典的k r u s k a l 算法构建最小支撑树，即 系统进化树。李刚成等人【52 j 基于d n a 序列的4 d 表示，提出将序列的相似矩阵视 为模糊聚类的模糊矩阵，然后利用最大树法构造生物进化树的方法，这个方法精 度不高，但是避开了传统模糊聚类计算闭包复杂度高的缺点，具有简单快捷的优 点。苏志忠【5 3 】提出了基于信息相异性的模糊聚类算法构建系统树，这个算法计算 各个分子序列的频率向量作为样本向量，利用模糊聚类对相似的样本向量归类， 从而可得到分子序列的系统树。 1 4 本文的主要工作 本文以生物信息学为背景，重点研究基因序列的图形表达、基于图形表达的 基因序列的相似性分析以及运用聚类技术分析基因序列的进化关系。本文的主要 基于图形表示的d n a 序列相似性分析及进化树构建算法研究 工作有： ( 1 ) 提出一种新的d n a 序列的图形表示一一j z 曲线组。通过定义数学映射 将一条基因序列转化为三条空间曲线，证明了该曲线不仅克服了图形的退化现象， 而且保留了原始d n a 序列的生物特征。 ( 2 ) 构造了d n a 序列间相似性度量的特征矩阵一一j j 矩阵。结合j z 曲线 组的j j 矩阵不仅描述了序列碱基的化学性质，而且提取了基因序列的生物意义。 通过对1 1 种生物的口球蛋白基因的第一外显子的编码序列进行相似性分析，实验 结果表明，在j z 图形表示的基础上结合j j 矩阵可以简单有效的分析d n a 序列 的相似性。 ( 3 ) 提出一种基于图谱理论的模糊聚类构造进化树的算法。对序列的进行聚 类分析，建立进化树，确定序列间的进化关系。通过对l1 种生物的b 球蛋白基因 的第一外显子的编码序列以及h 1 n l 病毒的n a 基因序列构建进化树，实验结果 表明该算法的有效性。 1 5 本文结构组织 本文以生物信息学为背景，对d n a 序列的图形表示方法及进化树构建问题 展开研究，全文主要包括4 章，各章内容安排如下： 第l 章绪论。主要介绍本论文的课题来源，研究背景和研究意义、国内外现 状与发展趋势、本文的研究内容以及组织结构。 第2 章d n a 序列图形表示及进化关系分析概述。首先对d n a 序列的图形表 示的研究现状进行总结，指出不同图形表示方法的优缺点。然后简单介绍了基于 图形表示的相似性分析方法，对特征矩阵，矩阵不变量方法进行了归纳和总结。 最后简要介绍了系统进化树的建树方法、p h y l i p 软件构建序列进化树步骤，以 及聚类分析技术在进化树构建中的运用。 第3 章基于d n a 序列的图形表示的相似性分析。首先提出了一种新的d n a 序列的图形表示方法一一j z 曲线组，然后证明新图形具备的特性，最后利用 m a t l a b 的画图工具画出1 1 个物种的基因序列的图形曲线。然后构造了一种新d n a 序列间相似性度量的特征矩阵一叫j 矩阵，并运用于1 1 种生物的厣球蛋白基因 的第一外显子的编码序列进行相似性分析。最后通过实验证明j j 矩阵可以简单 有效的分析d n a 序列的相似性。 第4 章基于图形的进化树构建方法。首先提出一种基于图谱理论的模糊聚类 构造进化树的算法，然后通过对1 1 种生物的球蛋白基因的第一外显子的编码序 列以及h l n l 病毒的n a 基因序列进行序列聚类，构建进化树并确定序列间的进 化关系，实验结果表明该算法的有效性。 6 硕士学位论文 第2 章基于图形的d n a 序列相似性分析及进化树构 建算法概述 2 1d n a 序列的图形表示 由于生物的原始序列是由彳、丁、g 、c 所表示四种碱基所构成，直接从原始 序列本身寻找生物信息信息是比较困难的，所以利用图形来表示生物的原始序列 可以使我们更加直观的观察生物序列。一个简单，直接，交互式的d n a 序列的图 形表示可以让人们很方便的观察到d n a 序列的整体和局部的特征。图形表示的基 本思想是：通过数学映射将d n a 的4 个碱基设置为几何空间中的向量，然后这些 向量连接组成空间曲线，从而得到d n a 序列的图形表示。下面我们就介绍几种典 型的d n a 序列的图形表示方法。 2 1 1 二维坐标轴的图形表示 二维坐标轴的图形表示的核心问题就是如何在二维平面上的建立x ，】，轴来 表示基因序列的4 个碱基及数量的问题。这种方法的主要思想是通过对4 个二维 向量来表示彳、丁、g 、c 四种碱基建立映射，然后将序列转化为二维空间上的曲 线。 ( 1 ) l9 8 6 年m a g a t e s 提出最早的二维图形表示【1 4 l ：+ x 轴方向单位向量为 c ，轴方向单位向量为g ，+ y 轴方向单位向量为r ，轴方向单位向量为彳。 ( 2 ) 1 9 9 4 年a n a n d y 给出的二维图形表示为【1 5 】：+ x 轴方向单位向量为g ， 喵轴方向单位向量为彳，却轴方向单位向量为c ，吵轴方向单位向量为丁。 ( 3 ) 1 9 9 5 年p m l e o n g 和s m o r g e n t h a l e r 提出另一个二维图形表示为【1 6 】： + x 轴方向单位向量为彳，x 轴方向单位向量为c ，抄轴方向单位向量为丁，哕 轴方向单位向量为g 。 这三种表示法均以坐标原点为序列的初始点，每增加一个碱基就按照映射关 系增加一个单位向量。通过这三种图形表示法，我们可以直观的观察序列，但是 这三种方法都可能出现曲线的交叠现象( 退化) ，造成生物信息的丢失。例如在 g a t e s 表示方法下a t ，a 1 队，a t a t ，a a t a t 的图形将很难区分，n a n d y s 表示方 法下t c ，t c t ，t c t c ，t t c t c 的图形将很难区分。 7 基于图形表示的d n a 序列相似性分析及进化树构建算法研究 - t ii g oc ， i ， c a c 甲 一 一 ti ， t i ca t-一 c c 争一c 孚，二扣g 亿。， c 孚，争斗cc 号，孚，_ r c ：g ( z ) = 一f 一歹一后 ( 2 2 ) 他们定义办( z ) = ；g ( z ) ，并定义岛表示当z 从f 增加到，时j l i ( z ) 走过的3 维曲线 硕士学位论文 轨迹。根据定义，凰。就是一条空间曲线，它由门个基向量首尾连接而成，并沿 z 轴负方向逐渐延伸。 ( 2 ) z 曲线3 ，9 1 7 ，1 8 l ：z 曲线理论是我国张春霆院士提出的d n a 序列的几何 化表示方法，是显示和分析d n a 序列的直观工具。一个给定的d n a 序列与三维 空间中的一条曲线一一对应。z 曲线的提出，开创了一个利用几何学方法分析和 研究d n a 序列的崭新领域。 考虑长度为的单链d n a 序列，该序列的z 曲线包含一系列的点： 只只只r ，相应的坐标( ，咒，乙) 。其中：矗，以，乙卜，】，n = 0 ，1 ，2 ，n 。 l = ( 4 + q ) 一( q + 瓦) 此= ( 以+ q ) 一( q + 乙)( 2 3 ) 【乙= ( 4 + 瓦) 一( q + e ) 4 ，q ，e ，乙分别表示从1 到聍这个子序列中四种碱基各自出现的次数。z 曲线的三个分量有着明确的生物学意义：1 ) 表示嘌呤似+ g ) 嘧啶( c + d 碱基沿 序列的分布，当嘌呤碱基的数目多于嘧啶碱基时，墨 o ；当序列中嘌呤碱基的数 目少于嘧啶碱基时，毛 0 ；当序列中氨基碱基的数目少于酮基碱基的数目时，儿 o ； 当序列中弱氢键碱基少于强氢键碱基时，z 。 0 ；当序列中弱氢键碱基等于强氢键 碱基时，z 。= 0 【1 7 ，18 1 。 ( 3 ) 其它三维图形：r a n d i c 把四种碱基分别赋予这样的向量坐标： ( + 1 ，一l ，一1 ) 专彳，( 一1 ，+ l ，一1 ) og ，( 一l ，一1 ，+ 1 ) 专c ，( + 1 ，+ 1 ，+ 1 ) 寸r ，从而提出了一 种三维图形表示d n a 序列和蛋白质序列【5 8 5 9 1 。李春给出了的一种三维图形表示 【32 1 ，其向量表示为：( 1 ，o ，o ) 专彳，( 0 ，1 ，0 ) 一c ，( o ，o ，1 ) 一g ，( 1 ，1 ，1 ) 一r 。廖波等 对四种碱基赋予不同的向量坐标提出了一系列三维图形表示【1 9 2 3 1 ，张惜珍2 4 1 结合 廖波引入参数的3 d 图形表示法和张春霆院士的z 曲线提出的曲线，都很好的 解决了退化现象。 2 1 3 高维坐标轴的图形表示 ( 1 ) 基于d n a 三联体的6 d 表示：l i a o 等人提出于d n a 三联体的6 d 表示 法【3 引，该方法是建立在相邻的三个碱基基础上来考虑d n a 序列所隐藏的生物信 息。根据中心法则，知道一个密码子是由三个碱基所组成的，那么就有6 4 种( 4 4 4 ) 不同的密码子，但是其中有些不同的密码子经过翻译后得到同一种氨基酸【4 1 。6 4 9 基于图形表示的d n a 序列相似性分析及进化树构建算法研究 种不同的密码子有以下规律：氨基酸种类完全由密码子的第一位和第二位决定。 对任一给定的d n a 序列，我们按照如下规则给出它的表示：先对密码子的第一 位和第二位规定为：( o ，1 ) 一么；( 1 ，0 ) 一g ；( o ，- 1 ) 一f ；( - l ，0 ) 一c ；那么密码子 的第三位给予指派0 ，l ，一1 。详细介绍如下：假设任一d n a 序列g = g 1 9 2 9 3 劭我 们让它按照下面给定的规定投射到6 维空间中去，就可以得到一条非退化的且唯 一的曲线，即g ( g ) = g ( 9 1 9 2 9 3 ) 甙9 2 9 3 9 4 ) g ( g 髫f + l 舒+ 2 ) 按照以上法可求得。 2 2 基于图形的序列相似性分析 利用图形来表示生物的原始序列可以使我们直观的观察生物序列，基于图形 表示的矩阵不变量方法最近被用于d n a 序列的相似性分析36 1 。其大致的计算过 程可分成下列三步：1 ) 从d n a 序列的图形表示中抽象出等价的数学矩阵，例如 d d 矩阵，m m 矩，l l 矩，甚至“高次矩阵；2 ) 从这些数学矩阵中进一步提 取，挖掘出能体现d n a 序列生物特征的数学不变量( 通常是向量形式) 。诸如特 征值、首要特征值及平均带宽等等，以这些量作为d n a 序列的数学描述，进而 构建d n a 序列的特征向量；3 ) 计算这些特征向量之间的距离，以此来衡量d n a 序列之间的相似性。 2 2 1 特征矩阵 d n a 原始序列的图形表示使得我们更直观的观察序列，而用矩阵来表示d n a 序列的信息让我们更方便的提取序列的信息。用于序列比较的特征矩阵方法基本 思想【3 6 ，3 7 1 是先依据序列的图形表示构造一个适当的矩阵，然后提取矩阵不变量， 这样可以通过定量比较矩阵不变量之间的差异来比较序列之间相似性。这个工作 最早由r a n d i c 提出【3 1 】：这里我们以二维图形为例，第f 点和第，点的坐标为( 薯，只) 和( x ，y ，) 。 ( 1 ) e e 矩阵：从几何角度看，矩阵各元素值代表着曲线上两个碱基对应点