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 loài - Trần Văn Lăng

Nội dung text: 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 loài - Trần Văn Lăng

1. 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
2. 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
3. • 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
4. • 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
5. • 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
6. 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
7. 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
8. 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
9. 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
10. 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
11. • 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