dx=09 假设分类单元a和分类单元b的分歧起始时间是相同的,根据分子时钟假说,出和a的 值应该是相等的,进一步假设节点u到其它节点的距离相同,则通过求解方程,得到如图 62所示的一棵树 b 图6.2根据方程求解结果构造系统发生 图72是一个简单的例子,但是,在实际应用中,所要处理的分类单元可能很多,因而 需要求解的线性方程也很多,难以求解,或者方程组的求解过程存在着不确定性。因此,需 要采用数学逼近的方法。 统计学上逼近的方法之一是最小二乘法。我们的目标是构造一棵树T,以该树的叶节点 代表分类单元,用该树预测分类单元之间的距离。通过优化,使下式最小化 2()=∑∑W(D-4 这里,D1为分类单元i和j的实际观察距离(或序列之间的计算距离),d是分类单元i和j 在系统发生树T中的距离,W是与分类单元i和j相关的权值。SSQ(T是树T所有预测 值与实际观察值偏差的累加和。权值W一般为1,或 W (6-7)
dbc = 0.9 假设分类单元 a 和分类单元 b 的分歧起始时间是相同的，根据分子时钟假说， 和 的 值应该是相等的，进一步假设节点 u 到其它节点的距离相同，则通过求解方程，得到如图 6.2 所示的一棵树。 图 7.2 是一个简单的例子，但是，在实际应用中，所要处理的分类单元可能很多，因而， 需要求解的线性方程也很多，难以求解，或者方程组的求解过程存在着不确定性。因此，需 要采用数学逼近的方法。 统计学上逼近的方法之一是最小二乘法。我们的目标是构造一棵树 T，以该树的叶节点 代表分类单元，用该树预测分类单元之间的距离。通过优化，使下式最小化： 这里，Dij为分类单元 i 和 j 的实际观察距离（或序列之间的计算距离），dij是分类单元 i 和 j 在系统发生树 T 中的距离，Wij是与分类单元 i 和 j 相关的权值。SSQ（T）是树 T 所有预测 值与实际观察值偏差的累加和。权值 Wij一般为 1，或
寻找一棵最小方差树是一个NP-完全问题,需要采用近似的算法。下面讨论几种计算时 间复杂度为多项式的启发式方法,即连锁聚类方法( linkage clustering)、非加权组平均法 ( UPGMA)和邻近归并法( Neighbor Joining 822连锁聚类方法及非加权分组平均法 连锁聚类属于一般的聚类分析方法,当用来构建系统发生树时,其假定的前提条件是 在进化过程中,核苷酸或氨基酸的替换速率是均等且恒定的,在每一次分歧发生后,从共同 祖节点到两个分类单元间的分支长度一样。在构建系统发生树时,首先用n个叶节点表示n 个分类单元(序列),每个分类单元自成一类,然后通过反复的聚类使所有的分类单元都 聚为一类,并将进化过程中的祖先赋予树的内部节点,最终得到一个完整的系统发生树。假 设若干条序列是从一个共同的祖先进化而来,则系统发生树将是一个有根树,并且从根节点 出发到所有叶节点路径的长度相同。 对于给定的序列,通过序列之间的两两比对,计算序列之间的进化距离,然后根据距离 矩阵构造系统发生树。算法的基本思路是首先从距离矩阵中选择距离最小的一对分类单元 (序列),令它们分别为x和y,然后将这两个分类单元合二为一,形成一个新的对象(代 表这两个分类单元的祖先,记为z),并重新计算这个新的对象与其它分类单元(或对象 u表示)之间的距离d(z,u)。不同的实现方案采用不同的计算公式 单连锁聚类 d (z, umin(d(x u),d(y, u)) 最大连锁聚类:d(z,u=max(dx,u)d(y,u)) (6-9) 平均连锁聚类:d(z,u)=(dx,u)+dy,u)/2 (6-10) 上述公式中z代表x和y的合并,u代表任意其它对象。每次合并所形成的新对象实际上是 个聚类,以一个内部节点表示,该节点到x、y所在节点的距离相同,其值等于d(x,y) 的一半,而到其它节点的距离按照上述公式计算。每次合并后,修改距离矩阵。重复上述过 程,直到所有的分类单元都被合并到一类为止
寻找一棵最小方差树是一个 NP-完全问题，需要采用近似的算法。下面讨论几种计算时 间复杂度为多项式的启发式方法，即连锁聚类方法（linkage clustering）、非加权组平均法 （UPGMA）和邻近归并法（Neighbor Joining）。 8.2.2 连锁聚类方法及非加权分组平均法 连锁聚类属于一般的聚类分析方法，当用来构建系统发生树时，其假定的前提条件是： 在进化过程中，核苷酸或氨基酸的替换速率是均等且恒定的，在每一次分歧发生后，从共同 祖节点到两个分类单元间的分支长度一样。在构建系统发生树时，首先用 n 个叶节点表示 n 个分类单元（序列）， 每个分类单元自成一类，然后通过反复的聚类使所有的分类单元都 聚为一类，并将进化过程中的祖先赋予树的内部节点，最终得到一个完整的系统发生树。假 设若干条序列是从一个共同的祖先进化而来，则系统发生树将是一个有根树，并且从根节点 出发到所有叶节点路径的长度相同。 对于给定的序列，通过序列之间的两两比对，计算序列之间的进化距离，然后根据距离 矩阵构造系统发生树。算法的基本思路是首先从距离矩阵中选择距离最小的一对分类单元 （序列），令它们分别为 x 和 y，然后将这两个分类单元合二为一，形成一个新的对象（代 表这两个分类单元的祖先，记为 z），并重新计算这个新的对象与其它分类单元(或对象，以 u 表示)之间的距离 d(z,u)。不同的实现方案采用不同的计算公式： 单连锁聚类: d(z,u)=min(d(x,u),d(y,u)) （6-8） 最大连锁聚类： d(z,u)=max(d(x,u),d(y,u)) （6-9） 平均连锁聚类： d(z,u)=(d(x,u)+d(y,u))/2 （6-10） 上述公式中 z 代表 x 和 y 的合并，u 代表任意其它对象。每次合并所形成的新对象实际上是 一个聚类，以一个内部节点表示，该节点到 x、y 所在节点的距离相同，其值等于 d（x，y） 的一半，而到其它节点的距离按照上述公式计算。每次合并后，修改距离矩阵。重复上述过 程，直到所有的分类单元都被合并到一类为止