Tin học đại cương - Chương 4: Tiến hóa phân tử và cây phân loài

Nội dung text: Tin học đại cương - Chương 4: Tiến hóa phân tử và cây phân loài

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