基于层次聚类的进化树构建算法研究

论文摘要

系统发育分析是生物信息学研究的重要领域之一，它主要研究同源的DNA或蛋白质序列，对这些序列进行进化分析，从而得到能够反映蛋白质序列或者DNA序列之间进化关系的系统发育进化树。系统发育进化树的研究已有很长的历史了，它在分子进化与系统发育研究中起到了重要的作用。系统进化树直观的反映了生物进化的关系，有助于了解生物进化历史和进化机制。进化树构建方法从不同的角度可以得到不同的分类，可以把进化树构建算法分为两类：基于算术聚类方法和基于最优搜索方法。由于基于最优搜索方法常常要比基于算术聚类方法慢得多，所以基于算术聚类方法得到了广泛地应用。基于算术聚类方法中层次聚类方法应用于进化树构建方面最为常用，但是传统的基于算术聚类方法中都是建立在序列比对的基础上的。所以本文为了解决这个问题，提出了两种新的基于层次聚类方法，这两种都是不需要进行序列比对，而且算法的计算量小，容易实现。两种新方法是：基于横纵建树法和基于调整权重的自组织映射建树法。基于横纵建树法也是一种基于距离矩阵建树法。它是在距离矩阵基础上进行的，结合横向找点，纵向找边的思想得到一棵二叉树，在此基础上进行聚类。基于调整权重的自组织映射建树法是建立在自组织映射网络基础上提出来的。自组织映射网络既可以应用于分类和聚类，也可以应用于进化分析和进化树的构造。但是当自组织映射网络应用于进化分析和进化树构造的研究中，算法比较复杂，而这种方法降低了算法的复杂度。这种方法与基于距离矩阵建树法比较，它不用进行相似分析构造距离矩阵，而是直接得到一颗最小权重二叉树，然后通过聚类进行进化树构建。评估构建进化树的方法可行性，通常是采用PHYLIP软件中的Neighbor.exe程序来评估的，通过做实验来验证算法的可行性。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 系统发育树的研究背景和意义
• 1.2 国内外研究现状
• 1.3 系统进化树构建的主要过程及相关软件
• 1.4 本文的主要研究工作
• 1.5 本文的章节安排
• 第2章 系统发育树构建算法
• 2.1 层次聚类
• 2.2 不加权算术平均组对方法（UPGMA）
• 2.3 邻接法（NJ）
• 2.4 模糊聚类法
• 2.5 动态增长自组织树算法
• 2.6 多叉自组织树算法
• 2.7 其他进化树构建算法
• 2.8 小结
• 第3章 基于横纵法构建进化树
• 3.1 横纵法的基本思想
• 3.2 横纵法的具体步骤
• 3.3 测试实例和结果分析
• 3.3.1 实验数据
• 3.3.2 基于序列描述符比较的相似分析
• 3.3.2.1 DNA 序列的图形表示
• 3.3.2.2 数值刻画
• 3.3.2.3 构造距离矩阵
• 3.3.3 进化树的构建
• 3.4 小结
• 第4章 基于调整权重的自组织映射构建进化树
• 4.1 自组织映射网络
• 4.1.1 自组织映射概述
• 4.1.2 自组织映射学习过程
• 4.2 新方法的基本思想
• 4.3 新算法的具体步骤
• 4.4 测试实例和结果分析
• 4.4.1 实验数据
• 4.4.2 DNA 序列编码
• 4.4.3 进化树构建
• 4.4.4 两种新方法实验结果比较分析
• 4.5 小结
• 结论
• 参考文献
• 致谢
• 附录 A 攻读学位期间所发表的学术论文和参加的项目