论文部分内容阅读
系统发生学是进化生物学的一个重要研究领域,而系统发生分析早在达尔文时期就已经开始了.系统发生是指生物形成或进化的历史,系统发生学研究物种之问的进化关系,其基本思想是比较物种的特征,井认为特征相似的物种在遗传学上接近.系统发生研究的结果往往以系统发生树表示,用它描述物种之间的进化关系.通过对生物学数据的建模提取特征,进而比较这些特征,研究生物形成或进化的历史.
近些年来,重建系统发生树的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集兼容的必要条件.