学位论文 > 优秀研究生学位论文题录展示

基于距离矩阵的进化树构建方法研究

作　者: 朱雯
导　师: 李仁发
学　校: 湖南大学
专　业: 计算机科学与技术
关键词: 构建进化树距离矩阵传递闭包 K近邻
分类号: TP18
类　型: 硕士论文
年　份: 2010年
下　载: 41次
引　用: 0次
阅　读: 论文下载

内容摘要

系统发育分析是生物信息学中的重要研究领域，它的主要研究手段是从一组同源的DNA或蛋白质序列出发，计算各个序列之间的进化距离，从而得到反映物种进化关系的进化树。进化树通常是一棵二叉树，树的叶节点，代表了某个具体序列；树的拓扑结构表示了各物种之间的亲缘关系远近；树的分支长度刻画了进化距离的大小。构建进化树的方法主要分为两大类：基于距离矩阵法和基于特征法。其中，距离矩阵法以结构简单，具有良好的理论基础等特点获得广泛应用。基于距离矩阵法是构建进化树方法中比较常用的一类方法，但是传统的基于距离矩阵法是建立在序列比对基础上的。所以本文为了解决这个问题，提出了两种新的方法，这两种都是不需序列比对，而且比较直观，计算量小，通俗易懂。两种新方法是：基于改进的模糊聚类传递闭包的距离矩阵法和基于改进的k近邻距离矩阵法。基于改进的模糊聚类传递闭包的距离矩阵法是在原始的非相似距离矩阵上通过改进，得到一个新的相似距离矩阵，这个新的相似距离矩阵是反映物种之间相似度高的矩阵，然后在新的相似距离矩阵基础上利用了模糊聚类中的传递闭包法构建进化树。基于改进的k近邻距离矩阵法是建立在k近邻法和图论的基础上提出来的。这种方法是在原始的距离矩阵基础上找出每一行的k个最相似的分类群，然后用线连接起来，如果出现回路，则删除回路中距离最大的那条边，通过构建的一个最小连通图，利用聚类的思想构建物种之间的进化树。这种算法主要是k的选择问题。如果k过小，那么该图就不是一个最小连通图，而且存在孤立的边；如果k过大，那么该图会变得复杂化，计算量会增加，相应地，时间复杂度和空间复杂度都会增加。评估构建进化树的方法可行性，通常是采用PHYLIP软件中的Neighbor.exe程序来评估的，通过做实验来验证算法的可行性。

全文目录

摘要  4-5
Abstract  5-7
目录  7-9
插图索引  9-10
附表索引  10-11
第1章绪论  11-22
  1.1 研究背景和意义  11-12
  1.2 国内外研究现状  12-20
    1.2.1 距离度量标准  13
    1.2.2 基于距离建树法  13-15
    1.2.3 基于特征建树法  15-17
    1.2.4 传统建树方法比较  17-18
    1.2.5 其他构建进化树方法  18-19
    1.2.6 构建系统进化树的主要过程及相关软件  19-20
  1.3 本文的主要研究工作  20
  1.4 本文的章节安排  20-22
第2章基于图形表示的相似距离矩阵计算  22-29
  2.1 DNA 序列的图形表示  22-24
  2.2 基于图形的序列相似性分析  24-26
  2.3 构建相似距离矩阵  26-28
  2.4 小结  28-29
第3章基于改进的模糊聚类传递闭包建树法  29-36
  3.1 模糊聚类的传递闭包  29
  3.2 新方法的基本思想  29-30
  3.3 新算法步骤  30
  3.4 实验及结果分析  30-35
  3.5 小结  35-36
第4章基于改进的 k 近邻距离矩阵建树法  36-43
  4.1 k 近邻法概述  36-38
  4.2 新方法的基本思想  38
  4.3 新算法的具体步骤  38-39
  4.4 测试实例和结果分析  39-42
  4.5 小结  42-43
结论  43-45
参考文献  45-50
致谢  50-51
附录A 攻读学位期间所发表的学术论文和参加的项目与获得的奖励  51-52

基于距离矩阵的进化树构建方法研究

内容摘要

全文目录

相似论文