当前位置:
文档之家› 系统发生分析-东南大学生物电子学国家重点试验室
系统发生分析-东南大学生物电子学国家重点试验室
通过求解方程,得到
如图6.2所示的一棵树。
1、最小二乘法
目标是构造一棵树T,该树的叶节点代表物种,用该树预
测物种之间的距离。通过优化,使下式最小化:
SSQ(T ) Wij ( Dij dij ) 2
i 1 j i
n
这里,Dij为物种i和j的实际观察距离(或序列之间的计算 距离),dij是物种i和j在系统发生树T 中的距离,Wij是与 物种i和j相关的权值。SSQ(T)是树T所有预测值与实际 观察值偏差的累加和。权值Wij一般为1,或
两类数据:
–距离 –离散特征
离散特征数据可分为 二态特征——例如:DNA序列上的某个位置如果是剪切位点 多态特征——例如:某一位置可能的碱基有A、T、G或C
系统发生树的构建方法分为两大类: – 基于距离的构建方法
非加权组平均法 邻近归并法 Fitch-Margol一定的指导性规则压缩搜索空间,提高计算速度。
第二节 基于距离的系统发生树构建方法
基本思路是:
给定一种序列之间距离的测度, 在该距离测度下构建一棵系统发 生树,使得该树能够最好地反映 已知序列之间的距离。
10条核酸序列的距离矩阵
例,如果有三个物种, 其两两距离如下: dab = 0.08 dac = 0.45 dbc = 0.43
Willi Hennig (1913-1976)
系统发生学(分支学)创始人
• 经典系统发生学
主要是物理或表型特征 如生物体的大小、颜色、触角个数
• 现代系统发生学
利用从遗传物质中提取的信息作为物种特征 具体地说就是核酸序列或蛋白质分子 关于现代人起源的研究:
线粒体DNA
——所有现代人都是一个非洲女性的后代
Wij =1/ Dij2
2、连锁聚类方法
•选择距离最小的一对序列 •将这两个序列合二为一,形成一个新的对象 (代表这两个序列的祖先) •重新计算这个新的对象与其它序列的距离。 单连锁聚类: d(x,u)=min(d(y,u),d(z,u))
最大连锁聚类: d(x,u)=max(d(y,u),d(z,u))
平均连锁聚类: d(x,u)=1/2(d(y,u)+d(z,u))
其中x代表y和z的合并,u代表任意其它对象。
3、非加权分组平均法
(Unweighted Pair Group Method with Arithmetic mean, UPGMA)
• 在平均连锁聚类过程中,一个新类到其它类之 间的距离就是简单的原距离平均值。
棵可能的系统发生树,但是只有 一棵树是正确的。
系统发生分析的目标 ——寻找这棵正确的树
3、系统发生分析步骤
(1)序列比对 (2)确定替换模型 (3)构建系统发生树 (4)评价所建立的树
计算序列之间距离 令S(i,j)是序列i和序列j比对位置得分的加权和
d (i, j ) 1
S (i, j ) S r (i, j ) S max (i, j ) S r (i, j )
第六章 系统发生分析
主讲人:孙
啸
制作人:刘志华
东南大学 吴健雄实验室 Axon
Charles Darwin (1809-1882)
第一节
系统发生与系统发生树
基本概念:
系统发生(phylogeny)——是指生物形成或
进化的历史 系统发生学(phylogenetics)——研究物种之间 的进化关系 系统发生树(phylogenetic tree)——表示形 式,描述物种之间进化关系
l 计算新分类到其它类的距离
D(ij ),k ( nj ni ) Di ,k ( ) D j ,k ni n j ni n j
其中ni、nj、(ni+nj)分别为i类、j类、(ij)类的元素个数; l 在距离矩阵中删除与类i和类j相应的行和列,为类(ij)加入新 的行和列;
重复循环,直到仅剩一个类为止。
如果类中分类单元个数不一样,原距离矩阵中各个 距离值对新距离计算的贡献就不一样,或者说是经过 “加权”的,称这样的聚类为加权分组平均。 • 在非加权分组平均法中,在计算新分类到其它分类 之间的平均距离时按照各分类中分类单元的数目进行 加权处理。
UPGMA算法的执行过程如下:
(1) 初始化:使每个物种自成一类,如果有n个物种,则开始时共 有n个类,每个类的大小为1,分别用n个叶节点代表每个类; (2)执行下列循环: l 寻找具有最小距离Dij的两个类i、j;建立一个新的聚类(ij) l 连接i和j形成新节点 (ij),生长两个新的分支,将i 和j 连接到 (ij),分支的长度为Dij/2;
S (i, j ) S max (i, j )
归一化的距离: 其中Sr(i,j)是序列i和j随机 化之后的比对得分的加权 和,Smax(i,j)是可能的最 大值
令Sr(i,j)=0
d (i, j ) 1
S (i, j ) d (i, j ) ln S max (i, j )
为了适合于处理相似性较 小的序列,可以进一步修 改距离计算公式
– 基于离散特征的构建方法
最大简约法 最大似然法 进化简约法 相容性方法
根据建树算法在执行过程中采用的搜索方式,系
统发生树的构建方法也可以分为以下3类。 (1)穷尽搜索方法
即产生所有可能的树,然后根据评价标准选择一棵最优的树。
(2)分支约束方法
即根据一定的约束条件将搜索空间限制在一定范围内,产生可能 的树,然后择优。
物种之间的进化关系 分类单元 (物种或序列)
系统发生树性质:
(1)如果是一棵有根树,则树根代表在进化历 史上是最早的、并且与其它所有分类单元都有 联系的分类单元; (2)如果找不到可以作为树根的单元,则系统 发生树是无根树; (3)从根节点出发到任何一个节点的路径指明 进化时间或者进化距离。
对于给定的分类单元数,有很多
4、邻近归并法
基本思想:
在进行类的合并时,不仅要求待合并的类是相近的, 同时还要求待合并的类远离其它的类。 • 重建时将距离最小的两个叶节点连接起来,合并 这两个叶节点所代表的分类,形成一个新的分类。 在树中增加一个父节点,并在距离矩阵中加入新的 分类,同时删除原来的两个分类。 • 重复上一次循环, 直到只剩一个类为止。