系统发生树重建的resolved triple方法

摘要

系统发生学是进化生物学的一个重要研究领域，而系统发生分析早在达尔文时期就已经开始了．系统发生是指生物形成或进化的历史，系统发生学研究物种之问的进化关系，其基本思想是比较物种的特征，井认为特征相似的物种在遗传学上接近．系统发生研究的结果往往以系统发生树表示，用它描述物种之间的进化关系．通过对生物学数据的建模提取特征，进而比较这些特征，研究生物形成或进化的历史． 近些年来，重建系统发生树的resolved quaret方法越来越手到分子生物界的关注．给定系统发生树T，{n，b，c，d}足其叶子节点子集ab｜cd表示树T中ab-路与cd-路不交，称为resolvrd quartet．对于系统发生树T，其resolced quarted集Q(T)是唯一确定的，这正式resoIred quartet方法的基本依据，但是resolved quartet集的兼容性问题NP-hard的，不存在多项式时间算法． 本文提出了resolred triple．方法，不仅可以在多项式时间内重建系统发生树，还可以检验resolved triple集的兼容性．给定系统发生树T，{a，b，c}是其叶子节点子集，符号ab｜c表示T中存在内部节点ν.ν.使得a，b，c∈des(u)a、b ∈des(ν)，c ∈，des(ν)．称为有resolvedtripl．我们首先通过特定规则建立resoled triple集R相对应的有向图G<,R>，对G<,R>中点不交有向路{pκ}两两进行一系列规的化简，最终得到R的基．在第4部分中，我们利用resoIved quartet集对此方法做出证呱并给出resolved quartet集兼容的必要条件． 本文由四部分组成： 第一章：引言，叙述问题的由来． 第二章：经典结论及基本定义，主要叙述前人的一些经典方法并定义本文所涉及的基本符号． 第三章:resolvel triple集的兼容性及多项式时间算法，这是本文最霞要的一章，也是最核心的一章．在这一章中，通过对有向图G<,R>的分析提出了(n-2)基算法． 第四章：resolved quartet集的兼容性，在这一章中，首先证明了(n-2)基算法，最后提出了resoJved quartet集兼容的必要条件．

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的声明

第一章引言

第二章经典结论及基本定义

§2.1经典结论

§2.2基本定义及标号

第三章Resolved triple集的兼容性及多项式时间算法

§3.1Resolved triple集的闭包

§3.2 Resolved triple集的(n-2)-基算法

第四章Resolved quartet的兼容性

§4.1(n-2)-基算法的理论依据

§4.2 Resolved quartet兼容的必要条件

参考文献

致谢