0.1681 0.1114
d B ,(CD ) d E ,(CD )
C D
0.2719
36 /80
• 删去C类和D类，加入新类（CD）类，重新计算（N=4）。
A A B （CD） … … … B … （CD） … … E … … … … … …
ri
ri
N 2
… … …
E
…
…
…
…
5点到（1,2）点的距离计算？），聚类。
1
2
6
7
1
3 4 5
2
4
5
21 /80
续
第四步：继续聚类过程，3点和（4,5点）聚到一起。
d38 d 48 d58
d 34 d 35 d 3 4 , 5 算术平均 2
8 7 6
3
1
2
4 5
1
2
4
5
3
22 /80
续
第五步：最后全部聚成一类。
二．基于特征法
12 /80
Distances in Trees
• 进化树的边权值（边的长度）的含义:
• 进化路径上一个物种进化为另外一个物种的变异次数； • 一个物种进化为另外一个物种的进化时间估计。
• 在一棵树T中，采用符号：
dij T - the length of a path between leaves（OUT） i and j
2 /80
核酸替换模型
J-C模型
Kimura模型
一般意义上，哪个模型更合适？
3 /80
• 利用部分基因（dna序列）构建物种树，你认为dna序列的选择 与构建进化树算法的选择哪个影响更大？为什么？ • 为什么需要对p-distance进行校正？校正值相对于p-distance是 偏大还是偏小？为什么？近缘序列与远缘序列哪一组更需要校 正？ • 假设某蛋白的进化速率是 1.2 109 /site/year，那么该蛋白每 100 million years的PAM是多少？
…
37 /80
最终结果
A B
0.0646 0.0492 0.1114
C
u3
0.1412
u2
u1
0.1681
E
0.0500 0.0730
D
38 /80
自展法（ Bootstrap ）——进化树评估
• 自展法由Felsenstein（1985）引入，是Efrom（1979）和 Efrom与Tibshirani（1993）所发展的统计学中自展技术的 直接应用。
1
4
2
3
26 /80
4条序列的例子
A B (CD)
A
A B C D 0.6 0.4 0.5
B
C
D
A B (CD) 0.6 0.45 0.5
0.6 0.4 0.2
0.1
C D
d B , A,CD
0. 6 0. 6 0. 4 1. 6 3 3
2 1 1.6 d B , A,CD d B ,CD d B , A 3 3 3
• • • • 把i和j归并为一类（ij），计算新节点的分支长度； 计算新类与其他类的距离； 删除类i和j，添加新类（ij），更新距离矩阵。 如果只有2个分类，连接这两个分类，结束循环。
33 /80
Example
• 5个分类群5s rRNA的例子。
A
B C
0
0.1715
0
0.2147
0.2991 0
-0.4221 -0.4441
0.4289
1.3574
1.2616
0.4525
0.4205
也就是第一步C和D被选择合并。
35 /80
• 计算新类（CD）的两个分支长度，即C到（CD）之间距离和D到 （CD）之间距离，以及（CD）到其他节点（类）之间距离。
dC ,(CD ) dCD r r 0.1114 C D 0.2795 0.3959 0.4525 2 2 2 2N 2
9
1 2
8 7
3 4 5
6 1 2 4 5 3
23 /80
距离计算方法
给定两个相连的类 Ci, Cj ，那么
1 dij = ––––––––– {p Ci, q Cj}dpq |Ci| |Cj|
注意，如果 Ck = Ci Cj, 则Ck到类 Cl 的距离是：
dil |Ci| + djl |Cj| dkl = –––––––––––––– |Ci| + |Cj|
17 /80
Fitting Distance Matrix（拟合距离矩阵）
Lengths of path in an (unknown) tree T
• Fitting means Dij = dij(T)
Edit distance between species (known)
18 /80
UPGMA构建进化树的过程
15 /80
Distance Matrix
对称
16 /80
Edit Distance vs. Tree Distance
• 给定n个物种（序列），我们能得到 n x n distance matrix Dij • Dij – edit distance（编辑距离）between i and j • Note the difference with dij(T) – tree distance between i and j
0.225 0.267
A
B
27 /80
距离
11条核酸序列的距离矩阵
28 /80
建树
29 /80
邻接法（ Neighbor Joining Algorithm ）
• In 1987 Naruya Saitou and Masatoshi Nei developed a neighbor joining algorithm for phylogenetic tree reconstruction。 • 该方法基本思路也是和Hierarchical Clustering类似，初始n个分类， 然后按照某种方法归并到一类。 • 在重建系统发生树时，该方法取消了非加权分组平均法（UPGMA） 所做的假定，不需要关于分子钟的假设，在进化分支上，发生趋异的 次数可以不同。 • 这种方法的基本思想是：在进行类的合并时，不仅要求待合并的类是 相近的，同时，还要求待合并的类远离其它的类。
A
B
30 /80
邻接法（ Neighbor Joining Algorithm ）
初始所有OUT聚在一个点成星形结构，然后按照相应 原则分割。如先是1和2组成一个进化分支，加入一个 内部节点X，其他仍然聚在Y点，把X和Y相连，反复迭 代直到得到二叉树。
31 /80
邻近归并法（ Neighbor Joining Algorithm ）
d D,(CD) dCD dC ,(CD) 0.2795 0.1114 0.1681
• 计算新类（CD）与其他类之间的距离。
d A,(CD ) d A,C d A, D d C , D 2 d B ,C d B , D d C , D 2 d E ,C d E , D d C , D 2 0.1222 0.1798
• 什么是进化树的操作分类单元operational taxonomic unit
(OUT)？ • 为什么说DNA序列的进化演变比蛋白质序列的演变更复杂？
4 /80
观察替换数与 实际替换数
5 /80
有根树指定了进化路径。对or错？
6 /80
哪个进化分支更古老。
7 /80
主要内容
一．进化和系统发生概述
• 对所有的i和j，设j>i，然后找出 最小值所对应的i和j。 M ij 最后，根据每一个步骤的结果绘制系统树。 • 原始文献《A note on the neighbor-joining algorithm of Saitou and Nei》。
32 /80
邻接法算法
• （1）初始化（与UPGMA算法一样） • （2）循环 • 计算ri和M ij ，选择最小的 M ij ；
0.3091
0
D
E
0
0.4289
0
34 /80
ri d ik，i 1,...,n
k 1
n
计算ri和M ij
A A B C -0.4766 -0.4905 B 0.1715
M ij d ij
r r
i j
N 2，i, j 1,...,n，j i
第一步：根据多序列比对（多序列比对过程？）结果计 算所有序列成对距离，以二维图示。
1
2
3 4 5
19 /80
续
第二步：找到距离最近的两条序列，聚类在一起
（树图），成为一条序列（点）。6点到1点和2点 距离平均分配。 d12 d16 d 26
1
2
6
3 4 5
1
2
20 /80
续
第三步：迭代，找到距离最近的两条序列（3、4和
24 /80
UPGMA方法的弱点
• UPGMA 算法产生的树有一个特点：从根节点到任何一片 叶子的距离都相等。 • UPGMA假定每条序列（物种）进化速率是恒定的，这是 这种方法的致命缺陷。
25 /80
UPGMA’s Weakness: Example
Correct tree UPGMA
3 2
4 1
1. 2. 历史背景 分子钟假设
二．进化树的基本概念 三．相关研究 四．分子系统发生分析