Bài giảng Tin sinh học đại cương - Chương 5: Tiến hóa phần tử và cây phân toài - Trần Văn Lăng

1 
TIN SINH HỌC ĐẠI CƯƠNG 
(Introduction to Bioinformatics) 
PGS.TS. Trần Văn Lăng 
Email: langtv@vast.vn 
Assoc. Prof. Tran Van Lang, PhD, 
VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 
TIẾN HÓA PHÂN TỬ VÀ CÂY PHÂN 
LOÀI 
Chương 4: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 2 
•  Khái niệm cây phân loài 
•  Nguồn gốc cây phân loài 
•  Các phương pháp xây 
dựng cây phân loài 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 3 
Khái niệm 
•  Cây phân loài (Phylogenetic 
tree) hay còn gọi là: 
–  Cây phả hệ 
–  Cây tiến hóa (Revolutionary 
tree) 
–  Cây phát sinh loài 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 4 
2 
•  Cây được dùng để mô hình 
hóa lịch sử tiến hóa thực tế 
của một nhóm các trình tự 
hay các sinh vật. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 5 
•  Đối tượng nghiên cứu truyền 
thống của cây phân loài là 
biểu diễn mối quan hệ tiến 
hóa giữa các loài. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 6 
•  Khi biểu diễn trong 
cây phân loài 
–  n loài hiện tại được 
biểu diễn ở n lá của 
cây 
–  Các nút bên trong (các 
nhánh) đại diện cho 
các loài tổ tiên chung 
nay đã tuyệt chủng 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 7 
•  Các nút bên trong đôi 
khi còn được coi: 
–  Sự đại diện cho một 
nhóm các loài 
–  Một sự kiện riêng biệt 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 8 
3 
•  Cách biểu diễn: có 2 dạng 
–  Cây có gốc (rooted tree) 
–  Cây không gốc (unrooted tree) 
•  Gọi là biểu diễn Phylip hay NEWICK 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 9 
Biểu diễn cây có gốc 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 10 
Các biểu diễn cây không gốc 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 11 
•  Biểu diễn cây (A, (B, C)) và ((B, C), A) giống 
nhau hoàn toàn. 
•  Theo tự nhiên, cây có nút gốc được vẽ từ 
dưới lên. 
•  Tuy nhiên, khi biểu diễn cây có gốc thường 
từ đĩnh xuống hoặc từ trái sang phải. 
•  Cây không gốc được vẽ từ trung tâm đi ra. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 12 
4 
Ví dụ: cá sấu, , chồn 
((Alligator,Bear),((Cow,(Dog,Elephant)),Ferret)) 
((Alligator,Bear),(((Cow,Dog),Elephant),Ferret)) 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 13 
Trường hợp cây không gốc 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 14 
((Alligator,Bear),((Cow,(Dog,Elephant)),Ferret)) 
((Alligator,Bear),(((Cow,Dog),Elephant),Ferret)) 
PHƯƠNG PHÁP KHOẢNG CÁCH 
ĐỂ TẠO CÂY PHÂN LOÀI 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 15 
Phương pháp UPGMA 
•  UPGMA (Unweighted Pair Group Method 
using arithmetic Averages) 
•  Là phương pháp gom cụm không có trọng số 
dùng trung bình số học 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 16 
5 
Phương pháp 
•  Trên cơ sở khoảng cách giữa từng cặp trình 
tự, biểu diễn thành dạng ma trận khoảng 
cách 
•  Ma trận khoảng cách là ma trận đối xứng 
•  Trên cơ sở ma trận khoảng cách, tìm các 
cụm gần nhất một cách lần lượt 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 17 
Khoảng cách trong cây phân loài 
•  Ma trận khoảng cách D = (dij) là ma trận 
trong đó mỗi phần từ dij là khoảng cách giữa 
2 nút lá trong cây phân loài. 
•  Ngoài ra, trong cây phân loài, còn chỉ rõ 
khoảng cách giữa các nút lá và các nút bên 
trong cây. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 18 
•  Khoảng cách dij trong ngữ cảnh tiến hóa thỏa 
mãn các điều kiện sau đây: 
–  Tính đối xứng: dij = dji với mọi i, j 
–  Tính phân biệt: dij ≠ 0 nếu và chỉ nếu i ≠ j 
–  Bất đẳng thức tam giác: dij ≤ dik + dkj với mọi i, j, k 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 19 
•  Khoảng cách thỏa mãn các điều kiện trên 
được gọi là một Metric (thước đo, độ đo). 
•  Ngoài ra, cơ chế tiến hóa có thể áp đặt các 
hạn chế bổ sung trên khoảng cách như: 
–  khoảng cách additive (cộng thêm) 
–  khoảng cách ultrametric (siêu metric) 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 20 
6 
•  Khoảng cách additive 
–  Cây được gọi là additive nếu như khoảng cách 
giữa một cặp nút là (i,j) bất kỳ là tổng khoảng 
cách giữa nút k và các nút lá i, j trên đường đi 
ngắn nhất từ nút i đến nút j trong cây: 
dij = dik + dkj 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 21 
•  Cây ultrametric 
–  Cây có gốc additive được gọi là cây ultrametric, 
nếu khoảng cách giữa 2 nút lá i và j và nút tổ tiên 
k chung của chúng là bằng nhau: 
dik = djk 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 22 
Bổ sung 2015 
•  Có 3 ràng buộc trên ma trận khoảng cách M: 
–  M phải là một metric 
–  M là một additive metric 
–  M có thể là ultrametric (optional) 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 23 
Metric Space 
•  A distance metric M is said to be a metric, if 
and only if it satisfies: 
–  Symmetric: Mij = Mji and Mii = 0 
–  Triangle Inequality: Mij + Mjk ≥ Mik 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 24 
7 
Additive Metric 
•  Let S be a set of species, and let M be the 
distance matrix for S. If there exists a tree T 
where: 
–  Every edge has a positive weight and every leaf 
is labelled by a disinct species in S 
–  For every i, j ∈ S, Mij = the sum of the edge 
weights along the path from i to j 
•  Then, M is an additive metric. T is called an 
additive tree 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 25 
Example: Additive Metric and Additive 
Tree 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 26 
Properties of Additive Metric 
•  M is additive if and only if for any four 
species, we can label them as i, j, l, k such 
that in S, 
Mik +Mjl =Mil +Mjk ≥ Mij + Mkl 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 27 
Ultrametric 
•  Let M be an additive metric. If there exists a 
tree such that 
–  The distance between any two species i and j 
equals the sum of the edge weights along the 
path from i to j. 
–  A root of the tree can be identified such that the 
distance to all leaves from the root is the same, 
that is, the length is a fixed value. 
•  Then M is known as an ultrametric and the 
tree mentioned is called an ultrametric tree. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 28 
8 
Propertied of Ultrametric 
•  M is ultrametric if and only if for any three 
species in S, we can label them i, j, k such 
that Mik = Mjk ≥ Mij 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 29 
•  Về mặt sinh học, độ dài cạnh dij tương ứng 
với thời gian trôi qua từ khi phân tách i và j 
khỏi nút chung. 
•  Điều đó có nghĩa chiều dài cạnh được đo bởi 
một “molecular clock” với tỉ lệ không đổi. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 30 
Minh họa 
•  Cho 5 trình tự A, B, C, D, E 
•  Từ đây, suy ra cần 10 khoảng cách giữa 5 
trình tự này để tạo ma trận khoảng cách 
–  10 = n(n-1)/2, với n = 5 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 31 
Ví dụ 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 32 
•  Giả sử 5 trình tự này 
có ma trận khoảng 
cách như bảng 
•  Lần lượt tính toán 
khoảng cách giữa các 
trình tự gom nhóm và 
không gom nhóm 
A B C D E 
A 
B 2 
C 6 6 
D 4 4 6 
E 7 7 9 5 
9 
•  Trong ma trận này, khoảng 
cách giữa A và B là ngắn 
nhất, nên gom nhóm A và 
B lại. 
•  Như vậy, A và B có chung 
tổ tiên là I 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 33 
•  Tính lại ma trận khoảng cách trong đó có 
khoảng cách giữa nhóm AB với các loài 
(trình tự) C, D, E còn lại 
•  Khoảng cách từ một loài đến nhóm là 
khoảng cách trung bình từ loài này đến các 
loài trong nhóm 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 34 
•  d(AB)C = (dAC+dBC)/2 
•  d(AB)D = (dAD+dBD)/2 
•  d(AB)E = (dAE+dBE)/2 
–  Kết quả như bảng: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 35 
AB C D E 
AB 
C 6 
D 4 6 
E 7 9 5 
•  Sau khi có ma trận 
khoảng cách mới, tiếp 
tục gom cụm với tiêu chí 
khoảng cách nhỏ nhất 
được chọn 
•  4 là khoảng cách nhỏ 
nhất, nên nhóm AB được 
gom cụm với trình tự D 
để có nhóm (AB)D 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 36 
Có chung tổ tiên là II 
10 
•  Tính toán khoảng cách 
trung bình từ nhóm ABD 
đến các trình tự còn lại 
theo quy tắc trên 
•  d(ABD)C = (dAC+dBC+dDC)/3 
•  d(ABD)E = (dAE+dBE+dDE)/3 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 37 
ABD C E 
ABD 
C 6 
E 6,3 9 
•  Theo ma trận khoảng cách mới, giá trị nhỏ 
nhất là 6 nên tạo ra cụm ((AB)D)C với nút 
trung tâm III 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 38 
•  Tương tự, khoảng cách giữa cụm ((AB)D)C 
với trình tự E là: 
•  d(ABDC)E = (dAE+dBE+dDE+dCE)/4 = 7 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 39 
Bài tập 
•  Hãy vẽ cây theo 
phương pháp UPGMA 
với ma trận khoảng 
cách như bảng 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 40 
11 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 41 
•  Minh họa trên web 
Tổng quát về phương pháp gom cụm 
•  Có 4 phương pháp gom cụm 
•  Những phương pháp này 
khác nhau ở cách tính 
khoảng cách 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 42 
Thuật toán 
•  Bao gồm 5 bước 
1.  Tìm cặp cụm (i,j) có khoảng cách dij là bé nhất 
2.  Tạo cụm u gồm cụm i và j 
3.  Tính chiều cao của cụm u (khoảng cách đến lá) 
là lij = dij/2 
4.  Tính khoảng cách dku với k không thuộc cụm u 
5.  Loại cụm u (cụm i,j) từ ma trận khoảnh cách 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 43 
•  Sự khác nhau giữa các phương pháp 
–  Liên kết đơn giản: dku = min(dki,dkj) 
–  Liên kết phức tạp: dku = max(dki,dkj) 
–  UPGMA: dku = (nidki + njdkj)/(ni+nj) 
–  WPGMA: dku = (dki + dkj)/2 
Trong đó ni là số phần tử của cụm i 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 44 
12 
Ví dụ 
•  Cho các trình tự ký hiệu A, 
B, C, D, E và ma trận 
khoảng cách như hình. 
•  Khoảng cách dBC = 2 là 
nhỏ nhất 
•  Liên kết B và C thành cụm 
(BC) với độ cao là dbc/2 = 
2/2 = 1 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 45 
•  Tính các khoảng cách mới theo UPGMA 
–  dA(BC) = (1x8 + 1x8)/(1+1) = 8 
–  dD(BC) = (1x12 + 1x12)(1+1) = 12 
–  dE(BC) = (1x4 + 1x4)/(1+1) = 4 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 46 
•  Loại bỏ B, C để có 
ma trận khoảng cách 
mới 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 47 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 48 
•  Theo ma trận khoảng 
cách: khoảng cách 
giữa cụm (BC) và E là 
bé nhất 
•  Nên tạo cụm (BC) với 
E để có cụm (BC)E với 
chiều cao là 4/2 = 2 
13 
•  Tiếp tục tính khoảng cách từ cụm (BC)E đến 
các trình tự còn lại 
–  dA((BC)E)) = (2xdA(BC) + 1xdAE)/(2+1) 
–  = (2x8 + 1x8)/3 = 8 
–  dD((BC)E)) = (2xdD(BC) + 1xdDE)/(2+1) 
–  = (2x12 + 1x12)/3 = 12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 49 
•  Ma trận khoảng 
cách mới được viết 
lại 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 50 
•  Do khoảng cách giữa A và cụm (BC)E là 
bé nhất, nên tạo cụm mới ((BC)E)A có 
chiều cao bằng 8/2 = 4 
•  Khoảng cách giữa D với cụm ((BC)E)A 
–  dD((BC)E)A = (3xdD((BC)E) + 1xdDA)/(3+1) 
–  = (3x12 + 1x12)/4 = 12 
•  Từ đây suy ra chiều cao của cây là 12/2 = 6 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 51 
•  Lưu ý, do cây 
này là 
ultrametric, nên 
kết quả của 4 
cách tính là như 
nhau 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 52 
14 
•  Với cây ultrametric, khoảng 
cách từ các nút lá đến gốc đều 
như nhau. 
•  Hình ảnh cây ultrametric như 
sau: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 53 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 54 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 55 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 56 
15 
PHƯƠNG PHÁP NEIGHBOR - 
JOINING 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 57 
•  Do Naruya Saitou và 
Masatoshi Nei đưa ra vào 
năm 1987 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 58 
Neighbor - Joining 
•  Phương pháp Neighbor – Joining là phương 
pháp tương tự như phương pháp gom cụm. 
•  Tuy nhiên, khái niệm cụm hàng xóm có 
khác: 
–  Hai trình tự được gọi là hàng xóm (lân cận) trong 
một cây nếu như giữa chúng chỉ có duy nhất một 
nút. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 59 
Phương pháp 
•  Cho ma trận khoảng 
cách chứa khoảng cách 
dij giữa các trình tự 
trong tập hợp n trình tự. 
•  Các trình tự ban đầu 
được biểu diễn như 
hình ngôi sao. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 60 
16 
Các bước 
•  Bước 1: Ở mỗi nút i có 
thể tính tổng khoảng 
cách ri: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 61 
ri = dik
k=1
n
∑
•  Bước 2: Mỗi cặp nút lá 
tính Mij, lấy các giá trị 
nhỏ nhất. 
Mij = dij −
ri + rj
n− 2
•  Bước 3: Liên kết nút i và nút j thành một nút 
mới ký hiệu u. Khi đó chiều dài từ u đến i và j 
là: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 62 
viu =
dij
2 +
ri − rj
2n− 4, và vju = dij − viu
•  Bước 4: Từ đây có thể tính 
khoảng cách từ u đến nút k 
khác là: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 63 
dku =
dik + djk − dij
2
•  Bước 5: Xóa nút i và j từ ma trận khoảng 
cách. Nếu còn lại nhiều hơn 2 cụm, quay trở 
lại bước 1 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 64 
17 
Ví dụ 
•  Cho ma trận khoảng 
cách với n = 4 trình tự 
ký hiệu A, B, C, D 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 65 
•  Khoảng cách dAB là nhỏ 
nhất, nhưng có thể A, B 
không phải là láng 
giềng; mà có thể là A, 
C như hình bên. 
•  Vì vậy, khoảng cách 
nhỏ nhất không cần 
thiết. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 66 
Bước 1 
•  rA = dAB + dAC + dAD = 3 + 4 + 5 = 12 
•  rB = dBA + dBC + dBD = 3 + 5 + 4 = 12 
•  rC = dCA + dCB + dCD = 4 + 5 + 7 = 16 
•  rD = dDA + dDB + dDC = 5 + 4 + 7 = 16 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 67 
Bước 2 
•  MAB = dAB – (rA + rB)/(4-2) = 3 – 24/2 = -9 
•  MAC = dAC – (rA + rC)/(4-2) = 4 – 28/2 = -10 
•  MAD = dAD – (rA + rD)/(4-2) = 5 – 28/2 = -9 
•  MBC = dBC – (rB + rC)/(4-2) = 5 – 28/2 = -9 
•  MBD = dBD – (rB + rD)/(4-2) = 4 – 28/2 = -10 
•  MCD = dCD – (rC + rD)/(4-2) = 7 – 32/2 = -9 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 68 
Giá trị nhỏ nhất là MAC và MBD 
18 
•  Như vậy có 2 cụm là AC và BD 
•  Sử dụng cụm AC, tạo ra nút mới ký hiệu (AC) 
ở giữa 2 nút A, C này. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 69 
Bước 3 
•  Khi đó 
–  dA(AC) = dAC/2 + (rA-rC)/(2x4-4) 
–  = 4/2+(12-16)/4 = 1 
–  dC(AC) = dAC - dA(AC) = 4 – 1 = 3 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 70 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 71 
A 
C 
(AC) 
B D 
1 3 
4 
2 
Bước 4 
•  Khoảng cách các nút còn lại (B và D) đến 
nút (AC) được tính như sau: 
•  dB(AC) = (dAB + dCB – dAC)/2 
•  = (3 + 5 – 4)/2 = 2 
•  dD(AC) = (dAD + dCD – dAC)/2 
•  = (5 + 7 - 4)/2 = 4 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 72 
19 
Bước 5 
•  Loại bỏ trình tự A và C, 
ma trận khoảng cách 
còn lại như bên cạnh 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 73 
•  Tiếp tục quay lại Bước 1 với n = 3 
–  rAC = d(AC)B + d(AC)D = 2 + 4 = 6 
–  rB = dB(AC) + dBD = 2 + 4 = 6 
–  rD = dD(AC) + dDB = 4 + 4 = 8 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 74 
•  Với Bước 2: 
–  M(AC)B = d(AC)B – (rAC + rB)/(4-2)=2-(6+6)/(3-2)= -10 
–  M(AC)D = d(AC)D – (rAC +rD)/(4-2)=4-(6+8)/(3-2)= -10 
–  MBD = dBD – (rB +rD)/(4-2)=4-(6+8)/(3-2)= -10 
•  Cả 3 đều có giá trị -10, nên có thể gom 
thành cụm (AC)B 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 75 
•  Tính toán theo Bước 3: 
–  dAC((AC)B) = d(AC)B/2 + (rAC - rB)/(2x3-4) 
–  = 2/2+(6-6)/2 = 1 
–  dB((AC)B) = d(AC)B – dAC((AC)B) = 2 – 1 = 1 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 76 
20 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 77 
A 
C 
(AC) 
D 
B 
1 3 
1 1 
(AC)B 
•  Tính khoảng cách từ nút còn 
lại (Bước 4) 
–  d((AC)B)D = (d(AC)D + dBD – d(AC)B)/2 
–  = (4 + 4 – 2)/2 = 3 
•  Khi đó có cây như hình 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 78 
Bài tập 
•  Vẽ cây không gốc theo 
Neighbor – Joining với ma 
trận khoảng cách là: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 79 
KHOẢNG CÁCH TIẾN HÓA 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 80 
21 
•  Khoảng cách của 2 trình tự là tỷ số giữa các 
trính tự không bắt cặp (đột biến) và số cặp 
không kể gap. 
•  Thực chất đó là số nucleotide khác nhau 
giữa 2 trình tự 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 81 
•  Cho 4 trình tự A, B, C, D, mỗi trình tự có 20 
nucleotide: 
A.   AGGCCATGAATTAAGAATAA
B.   AGCCCATGGATAAAGAGTAA
C.   AGGACATGAATTAAGAATAA
D.   AAGCCAAGAATTACGAATAA
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 82 
•  Khoảng cách tiến hóa giữa 
–  A và B là 4/20 (có 4 mismatch) 
–  A và C là 1/20 
–  A và D là 3/20 
–  B và C là 5/20 
–  B và D là 7/20 
–  C và D là 4/20 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 83 
•  Ma trận khoảng cách 
có thể viết 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 84 
A B C D 
A 0,2 0,05 0,15 
B 0,25 0,35 
C 0,2 
D A B C D 
A 4 1 3 
B 5 7 
C 4 
D