1、 生物信息学基础大作业报告报告主题 系统发育树的构建方法和研究进展 班级 计科 0901 姓名 王海颖 总学号 0304090111 - 2 -目 录目 录 .2一 引言 .3二 系统发育树的构建方法 .32.1 概括介绍 .32.2 具体介绍 .42.2.1 基于距离的方法42.2.2 最大简约法 .42.2.3 最大似然法 .52.2.4 贝叶斯树估计方法 .7三 系统发育树的改进算法 .73.1 遗传算法和模拟退火算法 .73.2 古 DNA 序列构建生物系统发育树 .73.2 基于 28S rDNA 序列构建侧耳属系统发育树 .73.3 基于全蛋白质组的微生物构建系统发育树 .83.4
2、 一种基于线粒体完全基因组的熵密度分布的脊椎动物系统发育树构建方法 .8四 评价方法的改进 .84.1 遗传算法和模拟退火算法的改进 .84.2 用 EM 算法进行参数估计 .84.2 乙型肝炎病毒 C 基因区序列的系统发育树分析 .94.3 矿区的氧化亚铁硫杆菌新菌系的鉴定. .104.4 55 株芽孢杆菌 16S rRNA 基因序列测定与系统发育学分析 .10 4.5 酸马奶中乳杆菌 Lb.casei.Zhang 和 ZLl21 的 16S rDNA 基因序列及聚类分析 11 五 结束语 .11参考文献 .11- 3 -1引言：二十一世纪，生命科学和信息科学都处于科学技术的主导地位，二者的
3、融合使得一个新的领域生物信息学产生了。生物信息学是在生命科学的研究中，以计算机科学知识为辅导工具对生物信息进行存储、检索和分析的科学。它是当今生命科学和自然科学的重大前沿领域之一。系统发生学是生物信息学中的一个重要研究领域，研究物种之间的进化关系，其基本思想是比较物种的特征，并认为特征相似的物种在遗传学上接近。系统分析早在达尔文时代就已经开始了，从那时起，重建地球上所有生物的进化历史就已经成为许多生物学家的梦想。生物进化是生物科学的灵魂，是生物科学体系的轴心。有关进化的思想、实事、原理和规律又始终贯穿于生物分支学科中。 系统发生是指生物形成或进化的历史。系统发生研究的结果往往以系统发育树表示，
4、用它描述物种进化关系。通过对生物学数据的建模提取特征，进而比较这些特征，研究生物形成或进化的历史。在分子水平上进行系统发生分析具有许多优势，所得到的结果更加科学、可靠。系统发育树也称系统进化树，它是用类似树状分支的图来表示各种（类）生物之间的亲缘关系，通过对生物序列的研究来推测物种的进化历史。构建系统发育树就是从生物物种的序列信息推断生物进化历史， “重塑”出系统进化的（谱系）关系，并把进化关系用系统发育树的形式表示出来树的叶子结点表示各个生物序列，树枝的长度表示生物间进化距离。主要通过DNA 序列，蛋白质序列，蛋白质结构等来构建系统发育树，或者通过蛋白质结构比较包括刚体结构叠合和多结构特征比
5、较等方法建立结构进化树。研究系统发育树的目的可以重建祖先序列；估计来自于同一个祖先的不同生物间分歧时间；识别和疾病关联的突变等。构建系统发育树的研究是生物信息学中的一个热点。基于分子的进化研究已经应用到许多方面，如基因进化，物群划分，交配系统，父亲身份测试，环境监视以及已经转移物种的疾病源的研究等。系统发育树的构建是现代生命科学研究中的重要技术,是分析未知菌种与其他茵种的亲缘关系,为进一步了解生物的进化关系的重要依据. 2构建方法介绍2.1 概括介绍系统发育树的构建问题是一个 NP 完全问题，因此研究构造发生树的近似最优算法有着重要意义。发育树的构建主要有两类方法，即基于算法的方法和基于最优原
6、则的方法。基于算法的距离法是一种纯数学法，通过序列两两之间的差异决定发育树的拓扑结构和枝长，它将发育树的构建和最后发育树的确定融合在一起，构建发育- 4 -树的过程，也就是寻找最佳发育树的过程。与距离法不同，基于最优原则的方法是首先确定一个标准，然后按这个标准去比较不同的发生树，最后选择最优的树，结果符合选择标准的最优树可能是一个，也可能是多个。最大简约考察输入数据中序列的多重比对结果，优化出的发生树能够利用最少的离散步骤去解释多重比对的碱基差异。最大似然法考察输入数据中序列的多重比对结果，优化出拥有一定拓扑结构和枝长的发生树，这个发生树能以最大的概率反应考察的多重比对结果 。系统发育树构建的
7、方法通常有四种类型：基于距离的方法，最大简约方法，最大似然法和贝叶斯估计方法。2.2 具体介绍2.2.1 基于距离的方法基于距离的建树方法考察数据中所有序列的两两比对结果，通过序列两两之间的差异决定发生树的拓扑结构和树枝长度。距离矩阵用来记录两个序列的差异数量值，其准确性大小依赖于进化模型的选择。从己知生物序列中能推断各个物种之间的进化历史，按照一定的遗传模型，把任意两个序列间的进化历史转化成数字，就得到两两之间的进化距离，把所有的距离用矩阵的形式表示出来，就得到了距离矩阵，根据该矩阵构建出系统进化树。 使用距离法构建系统发生树，所生成的树的质量取决于距离尺度的质量和每次挑选相邻结点的标准。距
8、离的度量首先需要选取一个进化模型，根据此模型，推导出距离的公式，进而将序列之问的关系换算成距离。而挑选相邻节点的标准，也就是距离法构建进化树的聚类算法，主要的方法有UPGMA、Fitch Margoliash 和邻接(neighbor-joinmg)方法。2.2.2 最大简约法利用最大简约方法构建系统发生树，实际上是一个对给定分类单元所有可能的树进行比较的过程，针对某一个可能的树，首先对每个位点祖先序列的核苷酸组成做出推断，然后统计每个位点用来阐明差异的核苷酸最小替换数目。在整个树中，所有简约信息位点最小核苷酸替换数的总和称为树的长度或树的代价。通过比较所有可能树，选择其中长度最小、代价最小的
9、树作为最终的系统发生树，即最大简约树。简约法的目标就是，构造一棵反映分类物种之间最小变化的系统发生树。简约法的理论基础是 Ockham 哲学原则，即解释一个过程，最好的理论是所需假设数目最少的个。所以，突变最少的进化关系就越有可能是物种之间真实的进化关系。简约法利用的只是对简约分析提供信息的特征，即信息位点，非信息位点对构建最大简约树是无用的。所谓信息位点，是符合以下要求的位点：至少包含两- 5 -种不同的核苷酸，并且出现的核苷酸需要至少出现两次。不变位点(所有物种拥有相同核苷酸的位点)和单一位点(每一个位点上只有一个物种具有一种不同的核苷酸的位点)在简约分析的时候是无用的叫。而这些无用位点对
10、于基于距离的方法中两两相似度的得分都有贡献，仅这一点区别就可能使这两类方法产生的结果有很大的不同“J。最大简约法的处理过程：(1)针对待比较的物种，选择核酸或蛋白质序列；(2)比较各个序列，产生序列的多重比对，确定各个序列字符的相对位置；(3)根据每个序列比对的位置(即多重序列比对的每一列)，确定相应的系统发生树，该树用最少的动作产生序列的差异，最终生成完整的树。从编程的角度计算祖先核苷酸位置的算法如下：如果一个内部节点的两个直接后代节点上的核苷酸的交集非空，那么这个节点的最可能的候选核苷酸集就是这个交集；否则为它的两个后代节点上核苷酸的并集。当一个并集成为一个节点的核苷酸集时，通向该节点的分
11、支的某个位置上必定发生一个核苷酸替换。因此，并集中核苷酸的数目也是生成外部节点上的核苷酸的最小替代数，外部节点从它们的共同祖先出发，通过这些替换，形成当前的核苷酸状态。如果需要计算一裸树在非信息位点的最小替代数，只需要把外部节点上不同核苷酸的数目减去 1 就可以了。简约法在分析过程中可以相当准确地推断出祖先序列，就单个核苷酸而言，这可能是微不足道的，但对于整个基因或者基因组来说，它对了解进化过程的作用是不可替代的。简约分析推断出了祖先，不仅可以填补分子进化研究中的空白，还可以从现存后代的序列中客观地推测出中间的状态，是对进化理论的重大贡献。2.2.3 最大似然法最大似然法最初是由 Cavall
12、iSforza 和 Edwards(1967)提出，用于构建基于基因频率的发生树”。Felsenstein(1988，1993)将该方法引入到基于核苷酸序列的发生树的构建，后来又扩展到氨基酸序列数据。最大似然法明确的使用概率模型，其目标是寻找能够以较高概率产生观察数据的系统发生树,是一种比较成熟的参数估计的统计学方法。最大似然法是由样本观测值估计总体参数的一种常用方法。最大似然法是选择最高概率的树。这个方法采用一个参数模型 ， 是一个 维向量，T 是树的拓扑结构。在这个模型下对于数据集中每个序列所有可能树的似然是独立计算的。对一个给定树和给定替代参数计算 列的似然，f（ | ）。- 6 -似然
13、是所有可能树 T 的拓扑和从向量 获得的分支长度的最大化。这需要计算所有可能树的似然，计算量是很大的，最大似然方法是以下面假定为前提的。在序列中每个符号进化独立于序列的其它符号；不同血统进化是独立的；每个符号以期望突变率代替。最大似然法的缺点：最大似然法的假定在实际中是很少存在的，每个树的似然计算是很耗时间的。最大简约法和最大似然法相似之处是两个算法都是基于标准的，都需要首先确定一个标准，然后按这个标准去比较不同的发生树，最后选择最优的树。两者只是选择的树的标准不一样而己，最大简约法考察输入数据中序列的多重比对结果，优化出的发生树能够利用最少的离散步骤去解释多重比对的碱基差异。最大似然法考察输
14、入数据中序列的多重比对结果，优化出拥有一定拓扑结构和枝长的发生树，这个发生树能够以最大的概率导致考察的多重比对结果。因此它们的搜索策略是相似的。如果物种数目很小，可以采用穷举法来寻找最大似然树。但由于单一的发生树的数量会随着分类物种数量的增长而呈指数增长，因此这种方法只适用于物种数目很小的情况(一般要求小于10)。2.2.4 贝叶斯方法最大似然法与贝叶斯方法的区别在于：前者对参数进行关节点评估，根据参数变动取似然性的峰值所对应的分支树；后者则对参数概率分布进行边界评估，根据参数变动取曲线分布覆盖面积最大的函数所对应的分支树。贝叶斯方法具有可以高效处理大量分子数据和分类阶元等计算上的优点和所得结
15、果易于解释的特点。除了推断系统发育，贝叶斯分析还用于评价系统发育中的不稳定性、探测可能存在的自然选择、考察协同进化、检验分子钟假设(MCMC的分析并不苛求分子的匀速进化假设)、选择DNA替换模型以及探测横向基因转移和基因组进化等相关研究。贝叶斯方法比最大似然法能表示更多的可信进化模型，替代率的变异可以再各个点建模，贝叶斯方法有一个非常宽的先验分布，后验概率分布用 Gibbs 样本和 MCMC(Monte Carlo Markow Chains)方法计算。如果 有不同的突变率，那么有如下形式：很多情况下不知道 ，用经验贝叶斯分析和启发贝叶斯分析两个方法产生后验概率，当未知参数出现时，经验贝叶斯分
16、析用估计来表示未知参数，启发贝叶斯分析将二级先验（second-level priors)作为前期未知参数的密度。积分所- 7 -有的二级先验作为先验，Yang and Rannala(1997)提出用 作为二级先验，平均值为1差异为 似然函数表示为如下公式：对于给定 的树的后验分布公式如下：其中，v 表示所有可能的分支长度，r 表示进化率。当物种数目较多时用 Monte Caelo 积分更有效。当用 metropolis 算法和 Gibbs 样本的 MCMC 方法可忽略分母，基于贝叶斯估计方法的软件包主要有 MrBays,不过速度较慢。一般的进化树分析中较少应用。该软件用MCMC 仿真进行系
17、统发育树的贝叶斯推理。用 MCMC 的贝叶斯方法的主要问题是收敛性没有证明。 3系统发育树的算法改进3.1 遗传算法和模拟退火算法针对最大简约法，引入了遗传退火算法的思想，提出一种新的建树算法，即遗传退火简约法，以简约树的长度作为适应度函数，随机生成多个初始树，通过多次执行选择退火、排序、交叉退火和变异退火操作，逐步收敛到所要搜寻的解，即最大简约树。遗传算法和模拟退火算法的直接互补性体现在：遗传算法把握总体能力的能力较强，但局部搜索能力较差；模拟退火算法具有较强的局部搜索能力。因此两算法互相结合，取长补短。改进的算法要比原有算法性能上均有提高，得到的拓扑结构更加准确，因为在改进的算法中采用了遗
18、传算法和退火算法结合，克服了单纯遗传算法的早熟性，保证了物种的多样性，达到了预期目标。 3.2 古 DNA 序列构建生物系统发育树自 20 年前中国科学家开始古 DNA (脱氧核糖核酸) 的研究工作以来,随着现代生物技术手段的不断发展,人们对古 DNA 的研究不断深入。古 DNA 能够提供有关现代生物和过去生物之间谱系关系的独特的、定量的信息,通过古 DNA 数据并结合现代基因库中的资料,构建某一门类生物的系统发育树, 从而进一步探讨演化生物学、人类演化和迁移、早期农业发展、考古学及地质演化等重要问题。- 8 -古 DNA 序列的研究可测定现代生物和绝灭生物的核苷替换(nucleo tide
19、subs titution)变化的微小差别, 还可用来单独地检测过去根据生物形态学和免疫学资料所建立的谱系假说。3.3 基于全蛋白质组的微生物构建系统发育树新近出现的信息离散性度量方法(简称 FDOD 方法)已在多个领域获得成功的应用，是一种非比对距离方法。随着越来越多的微生物全基因组测序任务的完成，人们开始在整个基因组水平上探讨物种的系统发育关系。因此，将 FDOD 方法应用于微生物系统发育分析是一项很有意义的工作。因为氨基酸序列比 DNA序列更为保守，能为物种的进化分析提供更为有用的信息。对收集到的 163 个原核生物和 5 个真核生物，从完全蛋白质组出发去分析推断其系统的发育关系，所得的
20、系统发育树包括 145 个细菌、18 个古细菌和 5 个真核细菌。FDOD 方法最突出的特点之一就是不带有主观因素，因而能比较客观地反映生物序列间的关系，它作为一种新的推断系统发育关系的方法，将会为传统的基于 ssrRNA 的微生物分类结果提供有价值的参考。3.4 一种基于线粒体完全基因组的熵密度分布的脊椎动物系统发育树构建方法线粒体完全基因组是一种构建脊椎动物系统发育树的非常重要的数据资源。应用基于非序列比对的熵密度分布方法结合对数关联距离对 64 种脊椎动物的线粒体完全基因组进行分析处理并构建系统发育树，产生的树将所选择的生物体分为三个大类：哺乳类(Mammalia)、鱼类(Fish)和初
21、龙下纲(包括鸟类(Birds)和爬行类(Reptiles)，其拓扑结构与当前已知的用传统方法产生的树相似。4评价方法的改进4.1 遗传算法和模拟退火算法对改进算法采用了评价建树算法中最常用的计算机模拟法来测试其性能，从实验结果来看，改进算法的准确性都有较大提高。对改进的算法进行了数据实验和模拟实验。从数据实验来看，改进算法和 PHYLIP 中相应的程序相比，在不增加时间消耗的同时，性能上有所提高。从模拟实验来看，改进算法的准确性得到了提高。总的来说，改进算法的性能都有较大的提高。4.2 用 EM 算法进行参数估计运用 EM 算法对存在插入或缺失但序列长度假设不变的观测序列构建系统发育树进行参数
22、估计，为含缺损数据序列构建良好的系统发育树作铺垫。重点在于运用 EM 算法做 Jukes-Cantor 模型、Kimura 模型下含缺损数据的 DNA 序列构建有根数或无根树最佳分支长度等地参数估计。在 Jukes-Cantor 模型下，两序列间每一位点核苷酸替代概率是- 9 -，当 ；, 当 ，其中 是两序列间的进化距离， 表示核苷酸不变的概率， 表示核苷酸变化的概率。在 Kimura 模型下，设 ，则两序列间每一位点核苷酸替代概率可表示为其中 表示核苷酸发生颠换的概率， 表示核苷酸发生转换的概率， 表示核苷酸不变的概率。长度为 的 2 条 DNA 序列 与 进行比对，设比对结果出现缺损现象
23、：观察到的核苷酸相同的数目为 ，核苷酸相异的数目为 ，存在缺损的核苷酸位点数为 (缺损情况用核苷酸不同情况下的公式计算)，且满足关系式，则在 JukesCantor 模型假设下任意两结点序列 与间的核苷酸替代概率为 。长度为 的 2 条 DNA 序列 与 进行比对，设比对结果显示两结点上观察到的核苷酸不变的数目为 ，观察到的核苷酸发生转换的数目为 ，观察到的核苷酸发生颠换的数目为 ；并出现缺损现象：假定出现缺损的核苷酸可能发生转换的数目为 ，缺损核苷酸可能发生颠换的数目为 ，它们满足关系式- 10 -是： ，则在 Kimura 模型假设下序列 与 的核苷酸替代概率为。假设 n(n2)条长度均为
24、 的 DNA 序列 构建系统发育树，树的拓扑结构 是有根树，概率模型是 JukesCantor 模型，第 次序列比对中核苷酸相同的数目为 ，核苷酸相异的数目为 ，存在缺损的核苷酸位点数为 ，则系统发育树中各分枝长度的最优估计为。4.3 矿区的氧化亚铁硫杆菌新菌系的鉴定.目的：以结瘤豆科植物紫花苜蓿根际土壤为研究材料,筛选具有 ACC 脱氨酶活力的氢氧化细菌,探索氢氧化细菌植物促生作用机制.方法：利用持续通 H2 的气体循环培养体系、矿质盐固体培养基,分离、培养氢氧化细菌,观察菌株形态并测定生理生化特征;16S rDNA 序列分析法构建系统发育树;采用薄层层析法筛选 ACC 脱氨酶阳性菌株,茚三
25、酮显色法测定 ACC脱氨酶活力.结果：分离的 37 株细菌中有 8 株菌氧化氢和自养生长能力较强,初步确定为氢氧化细菌,从中筛选出 1 株 ACC 脱氨酶阳性菌株 WMQ-7.菌株 WMQ-7 的形态特征、生理生化特征与恶臭假单胞菌(Pseudomonas putida)的特征基本一致;16s rDNA 序列(GenBank 登录号为 EU807744)在系统发育树中与恶臭假单胞菌同属一个类群,序列同源性 99%.鉴定菌株 WMQ-7 为恶臭假单胞菌,其 ACE 脱氨酶活力为 0.671 U/g结论采用气体循环培养体系分离氢氧化细菌,克服了传统配气法的局限.ACC 脱氨酶阳性菌株的筛选,为深入
26、研究氢氧化细菌作为植物根际促生菌的菌株特性和促生机制提供理论依据.4.4 55 株芽孢杆菌 16S rRNA 基因序列测定与系统发育学分析采用 16S rRNA 基因序列分析法对中国工业微生物菌种保藏管理中心（CCIC）保藏的 55 株枯草芽孢杆菌（Bacillus subtilis）进行复核鉴定。菌株经纯化培养，以改良 CTAB 法提取总 DNA，采用细菌 16S rRNA 通用引物、TD-PCR 方法（touchdown-PCR)进行 16S rRNA 基因序列扩散，PCR 产物纯化后直接进行序列测定，序列经人工校对后用 Clustal X 进行比对分析，最后用MEGA3.1 软件构建系统发育树。系统发育结果表明：55 株枯草芽孢杆菌中油 52株菌种与原鉴定结果一致，有 3 株菌种与原鉴定结果存在差异，其中 2 株鉴定
