多叉进化树构建方法的研究与实现

摘要

本文论述了多叉进化树构建方法的研究与实现，详细分析了UPGMA产生不惟一结果的原因，在此基础上提出并实现了UPGMA的一种改进算法，即不加权算术平均组群方法(Unweighted Multi-Group Method using Arithmetic averages，以下简称UMGMA)。UMGMA是UPGMA的一种扩展，而UPGMA可以看作UMGMA的一个特例。在迭代计算过程中，UPGMA总是选取距离矩阵中最小的元素对应的一对序列生成新的分类群单元。而UMGMA则通过引入距离容差参数t，将所有小于t的元素对应的序列作为生成新分类群单元的基础。该方法在一次迭代中可以产生多个新的分类群单元，因此其进化树结果可能是多叉树。在UPGMA结果不惟一的情况下，各种可能的二叉树结果在UMGMA中被综合构建成一棵惟一的多叉树，从而解决了惟一性的问题；而在UPGMA结果惟一的情况下，取距离容差参数t等于零，UMGMA得到的结果将与UPGMA的结果完全一致。基于实际数据的进化树构建实验表明，UMGMA不仅能够产生结果惟一的进化树，而且通过选择不同的容差参数t，还能产生不同层次的进化树。这意味着在大规模系统发育分析中，UMGMA可以通过调整t的值，不断突出进化树的整体脉络。实现了一种包含完整UMGMA算法实现以及传统UPGMA方法实现的分子发育分析软件--Mult-Tree。该软件是一个基于Microsoft.net framework 2.0平台构建的客户端应用，其中使用WebService完成多序列比对功能，并提供一套基本的分子进化分析流程，包括：多序列比对结果编辑、距离矩阵计算以及多种方法构建进化树，并以多种风格显示进化树。Multi-Tree软件系统有别于大多数传统的分子发育分析工具软件包，它具有友好的富客户界面，支持多语言的界面显示。系统采用了基于插件的程序结构，从指定位置的一组程序集中动态获取系统的界面元素与业务逻辑，具有良好的扩展性与可维护性。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题背景

1.2国内外研究概况

1.2.1基于距离的建树方法

1.2.2最简约方法

1.2.3极大似然法

1.2.4建树方法的特点与比较

1.3本文的主要研究工作

1.4文章结构

第2章不加权算术平均组对法介绍

2.1距离矩阵法构建进化树的基本过程

2.1.1构建进化树

2.1.2核苷酸替代模型

2.2 UPGMA算法

2.3 UPGMA结果不惟一问题的分析

2.4传统建树方法的其他问题

2.5本章小结

第3章不加权算术平均组群方法

3.1 UMGMA的基本思想

3.2 UMGMA算法描述

3.3实验数据与结果分析

3.3.1 12个物种mtDNA序列数据的实验

3.3.2 11种果蝇的adh序列数据实验

3.4算法分析

3.5本章小结

第4章Multi-Tree分子进化分析系统的设计与实现

4.1系统设计原则

4.2系统需求

4.2.1业务目标

4.2.2用户特点

4.3系统架构与设计实现

4.3.1系统架构描述

4.3.2系统详细设计与实现

4.4系统主要源文件说明

4.5系统输入输出

4.5.1进化树结果

4.5.2项目文件

4.5.3序列文件

4.5.4多序列比对结果

4.5.5距离矩阵文件

4.5.6进化树的字符串表示

4.5.7系统树的绘制风格

4.6系统运行环境

4.7本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢