Bài giảng Tin sinh học đại cương - Chương 3: Bắt cặp trình tự (Sequence alignment) - Trần Văn Lăng

Nội dung text: Bài giảng Tin sinh học đại cương - Chương 3: Bắt cặp trình tự (Sequence alignment) - Trần Văn Lăng

1. • Như vậy, với 2 trình tự: – ACTCGATT – AGCTAATC • Khi đó, ký tự “gap” vừa: • có thể được bắt cặp là: – deletion gap: mất đi – ACTCG ATT – insertion gap: thêm vào – | || – AG—CTAATC PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM • Có thể tìm tại Sử dụng PHẦN MỀM CLUSTALX PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 11
2. Ví dụ >Seq1 • Để bắt cặp 2 trình tự, ACTCCGATT – tạo file dạng FASTA >Seq2 AGCTAATC • Có hai dạng Clustal trên 3 hệ điều hành khác – chọn File/Load Sequences là file mới tạo nhau: Linux, Mac OS X, Windows: – chọn Alignment/Do – ClustalW: thực thi ở chế độ dòng lệnh Complete Sequences – ClustalX: dùng ở chế độ khung của sổ (window) PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Hoặc có thể viết một application Thuật toán NEEDLEMAN - WUNSCH PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 12
3. • Cho 2 trình tự lần lượt có chiều dài là n và m • Thuật toán gồm các bước sau: • Do Saul Needleman và Christian Wunsch đưa ra – Bước 1: Khởi tạo giá trị ban đầu cho ma trận tính toán vào năm 1970 M như sau: • Áp dụng trên toàn bộ trình tự để tìm sự tương Mi0 =id, ∀i=0,n, M0j = jd, ∀j=0,m đồng giữa toàn bộ 2 trình tự (bắt cặp toàn cục – M = max M +σ ,M +d,M +d , ij { i−1,j−1 ij i−1,j i,j−1 } Gobal Alignment) ∀i=1,n;j=1,m #match σ ij = $ , d= gap %mismatch PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Giải thích kết quả • Ví dụ cho 2 trình tự C A T G T C A T G T – CATGT 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 – ACGCTG A -2 -1 0 -2 -4 -6 A -2 -1 • Các giá trị tính toán C -4 0 -2 -1 -3 -5 C -4 G -6 -2 -1 -3 1 -1 G -6 – match = 2 C -8 -4 -3 -2 -1 0 C -8 – mismatch = -1 T -10 -6 -5 -1 -3 1 T -10 – d = -2 G -12 -8 -7 -3 1 -1 G -12 • Ma trận M như bảng PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 52 13
4. C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 A -2 -1 0 -2 C -4 C -4 G -6 G -6 C -8 C -8 T -10 T -10 G -12 G -12 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 A -2 -1 0 -2 -4 -6 C -4 C -4 G -6 G -6 C -8 C -8 T -10 T -10 G -12 G -12 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. C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 C -4 0 -2 G -6 G -6 C -8 C -8 T -10 T -10 G -12 G -12 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 C -4 0 -2 -1 -3 G -6 G -6 C -8 C -8 T -10 T -10 G -12 G -12 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 A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 G -6 -2 C -8 C -8 T -10 T -10 G -12 G -12 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 G -6 -2 -1 -3 C -8 C -8 T -10 T -10 G -12 G -12 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. C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 G -6 -2 -1 -3 1 -1 C -8 C -8 T -10 T -10 G -12 G -12 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 C -8 -4 -3 T -10 T -10 G -12 G -12 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. C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 C -8 -4 -3 -2 -1 T -10 T -10 G -12 G -12 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 T -10 T -10 -6 G -12 G -12 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. C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 T -10 -6 -5 T -10 -6 -5 -1 G -12 G -12 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 T -10 -6 -5 -1 -3 T -10 -6 -5 -1 -3 1 G -12 G -12 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 A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 T -10 -6 -5 -1 -3 1 T -10 -6 -5 -1 -3 1 G -12 -8 G -12 -8 -7 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 T -10 -6 -5 -1 -3 1 T -10 -6 -5 -1 -3 1 G -12 -8 -7 -3 G -12 -8 -7 -3 1 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. C A T G T • Bước 2: Tìm vết dựa trên kết quả tính các giá trị 0 -2 -4 -6 -8 -10 của ma trận trước đó. Xuất phát từ Mnm nếu: A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 − M = M −σ , theo duong chéo, (i,j) → (i-1,j-1) G -6 -2 -1 -3 1 -1 i−1, j−1 ij ij M M d, dich chuyen lên trên, (i,j) (i-1,j) C -8 -4 -3 -2 -1 0 − i−1, j = ij − → M M d, dich chuyen lui, (i,j) (i,j-1) T -10 -6 -5 -1 -3 1 − i, j−1 = ij − → G -12 -8 -7 -3 1 -1 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 C A T G T C A T G T 0 -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 A -2 -1 0 -2 -4 -6 A -2 -1 0 -2 -4 -6 C -4 0 -2 -1 -3 -5 C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 C -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 T -10 -6 -5 -1 -3 1 T -10 -6 -5 -1 -3 1 G -12 -8 -7 -3 1 -1 G -12 -8 -7 -3 1 -1 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
12. C A T G T • Bước 3: Bắt cặp trình tự 0 -2 -4 -6 -8 -10 – Xuất phát từ phần tử Mnm A -2 -1 0 -2 -4 -6 – Nếu phần tử kế nằm trên đường chéo: hai ký tự được C -4 0 -2 -1 -3 -5 -CA-TGT bắt cặp với nhau G -6 -2 -1 -3 1 -1 ACGCTG- – Nếu phần tử kế nằm bên trái: thêm gap cho trình tự C -8 -4 -3 -2 -1 0 thứ hai (ở dưới) T -10 -6 -5 -1 -3 1 – Ngược lại, nếu phần tử kế nằm ở trên: thêm gap cho G -12 -8 -7 -3 1 -1 trình tự thứ nhất • Điểm đánh giá = 3x2 + 1x(-1) + 3(-2) = -1 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 85 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 86 Xem xét ví dụ khác CATG-T- • Điểm: 3x2 + 1(-1) + 3(-2) = -1 -ACGCTG C A T G T • Xét 2 trình tự peptide như sau: 0 -2 -4 -6 -8 -10 – U = AlaCysGlyCysAspGly A -2 -1 0 -2 -4 -6 – V = CysAlaAspGlyAsp C -4 0 -2 -1 -3 -5 G -6 -2 -1 -3 1 -1 • Gồm các amino acid: Alanin (A), Cystein (C), C -8 -4 -3 -2 -1 0 Glycine (G), Aspartic acid (D) T -10 -6 -5 -1 -3 1 G -12 -8 -7 -3 1 -1 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 87 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 22
13. • Tạo ma trận đánh giá theo quy tắc: – M00 = 0 – Mi0 = Mi-1,0 + d • Có thể biểu diễn – M0j = M0,j-1 + d – U = “ACGCDG” – Mij = Max {Mi-1,j-1 + σij, Mi,j-1 + d, Mi-1,j + d} – V = “CADGD” – d = -1 • Trong đó – σij = +2 nếu Ui và Vj giống nhau – σij = -1 nếu Ui và Vj khác nhau PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM C A D G D 0 -1 -2 -3 -4 -5 • Tìm vết bằng cách dùng d = -1 và ma trận σ để so sánh trên 2 trình tự: A -1 -1 1 0 -1 -2 C -2 1 0 0 -1 -2 • Xuất phát từ M65, nếu: G -3 0 0 -1 2 1 – Mij = Mi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) đi theo đường chéo C -4 -1 -1 -1 1 1 – M = M + d thì vết (i,j) → (i,j-1) đi lui D -5 -2 -2 1 0 3 ij i,j-1 → G -6 -3 -3 0 3 2 – Mij = Mi-1,j + d thì vết (i,j) (i-1,j) đi lên PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 23
14. • Trong trường hợp này, có nhiều vết được tạo ra (màu red, blue, green) C A D G D C A D G D 0 -1 -2 -3 -4 -5 0 -1 -2 -3 -4 -5 C A D G D A -1 -1 1 0 -1 -2 A -1 -1 1 0 -1 -2 0 -1 -2 -3 -4 -5 C -2 1 0 0 -1 -2 C -2 1 0 0 -1 -2 A -1 -1 1 0 -1 -2 G -3 0 0 -1 2 1 G -3 0 0 -1 2 1 C -2 1 0 0 -1 -2 C -4 -1 -1 -1 1 1 C -4 -1 -1 -1 1 1 G -3 0 0 -1 2 1 D -5 -2 -2 1 0 3 D -5 -2 -2 1 0 3 C -4 -1 -1 -1 1 1 G -6 -3 -3 0 3 2 G -6 -3 -3 0 3 2 D -5 -2 -2 1 0 3 G -6 -3 -3 0 3 2 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM • Vết Red: 3(2) + 1(-1) + 3(-1) = 2 CADG-D- • Sử dụng kỹ thuật lưu vết theo quy tắc: -ACGCDG – (i,j) →(i-1,j-1): Ui và Vj được ghi vào • Vết Blue: 3(2) + 1(-1) + 3(-1) = 2 – (i,j) →(i-1,j): “-” và Vj được ghi và -CA-DGD – (i,j) →(i,j-1): Ui và “-” được ghi vào ACGCDG- • Vết Green: 3(2) + 1(-1) + 3(-1) = 2 -C-ADGC ACGCDG- PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 24
15. Một ví dụ khác G A A T T C A G T T A 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 G -1 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 • Cho 2 trình tự DNA: G -2 1 1 0 -1 -2 -3 -4 -2 -3 -4 -5 GGATCGA A -3 0 3 3 2 1 0 -1 -2 -3 -4 -2 GAATTCAGTTA T -4 -1 2 2 5 4 3 2 1 0 -1 -2 C -5 -2 1 1 4 4 6 5 4 3 2 1 G -6 -3 0 0 3 3 5 5 7 6 5 4 A -7 -4 -1 2 2 2 4 7 6 6 5 7 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Bài tập • (P1) Tính toán các giá trị của ma trận với trường • Bắt cặp 2 trình tự này là: hợp tương tự, nhưng: GGA-TC-G A – M = 0 | | || | | 00 – M = M + d GAATTCAGTTA i0 i-1,0 – M0j = M0,j-1 + d • Kết quả: 6(2) + 4(-1) + 1(-1) = 7 – d = -2 • Rút ra nhận xét PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 25
16. TG Needleman – Wunsch nguyên thủy AlignmentU ← "" AlignmentV ← "" for i=0 to length(U) i ← length(U) M(i,0) ← d*i j ← length(V) for j=0 to length(V) while (i > 0 and j > 0){ M(0,j) ← d*j Score ← M(i,j) for i=1 to length(U) ScoreDiag ← M(i - 1, j - 1) for j=1 to length(V){ ScoreUp ← M(i, j - 1) Match ← M(i-1,j-1) + σ(i,j) ScoreLeft ← M(i - 1, j) Delete ← M(i-1,j) + d if (Score == ScoreDiag + σ(i,j)){ Insert ← M(i,j-1) + d AlignmentU ← Ui + AlignmentU M(i,j) ← max(Match, Insert, Delete) AlignmentV ← Vj + AlignmentV } i ← i - 1 j ← j - 1 } PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM else if (Score == ScoreLeft + d){ while (i > 0){ AlignmentU ← U + AlignmentU i AlignmentU ← U + AlignmentU AlignmentV ← "-" + AlignmentV i AlignmentV ← "-" + AlignmentV i ← i - 1 i ← i - 1 } } otherwise (Score == ScoreUp + d){ while (j > 0){ AlignmentU ← "-" + AlignmentU AlignmentU ← "-" + AlignmentU AlignmentV ← V + AlignmentV j AlignmentV ← V + AlignmentV j ← j - 1 j j ← j - 1 } } } Coi thêm NeedWun.java PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 26
17. • Do Temple F. Smith và Michael S. Waterman đưa ra vào 1981 • Khác biệt so với thuật toán Needleman – Thuật toán Wunsch là chỉ sử dụng để bắt cặp 2 trình tự SMITH - WATERMAN trong một đoạn của trình tự (bắt cặp cục bộ - Local Alignment) PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM • Các bước tính toán hoàn toàn tương tự, chỉ khác một số bước như sau: – Cách thức tính ma trận: • Do chỉ bắt cặp cục bộ, nên vết được xác định Hi0 =0, ∀i=0,n, H0j =0, ∀j=0,m không phải bắt đầu từ giá trị cuối (Hnm), mà từ giá H = max 0,H +σ ,H +d,H +d , ij { i−1,j−1 ij i−1,j i,j−1 } trị tốt nhất (điểm cao nhất của ma trận) ∀i=1,n;j=1,m #match σ ij = $ , d= gap %mismatch Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 27
18. Ví dụ • Với U = “ACA”, V = “AGCA”, với d = -1 ta có các phần tử của ma trận H như sau: H21 = max{0,H10 +σ 21 ,H11 −1,H20 −1} A C A = max{0,0−1,2−1,0−1} =1 0 0 0 0 H max{0,H ,H 1,H 1} A 0 H11 H12 H13 22 = 11 +σ 22 12 − 21 − 0 H H H G 21 22 23 = max{0,2−1,1−1,2−1} =1 C 0 H31 H32 H33 H max{0,H ,H 1,H 1} A 0 H41 H42 H43 23 = 12 +σ 23 13 − 22 − max{0,1 1,2 1,1 1} 1 H11 = max{0,H00 +σ 11 ,H01 −1,H10 −1} = max{0,0+2,0−1,0−1} =2 = − − − = H12 = max{0,H01 +σ 12 ,H02 −1,H11 −1} = max{0,0−1,0−1,2−1} =1 H13 = max{0,H02 +σ 13 ,H03 −1,H12 −1} = max{0,0+2,0−1,1−1} =2 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM H31 = max{0,H20 +σ 31 ,H21 −1,H30 −1} H41 = max{0,H30 +σ 41 ,H31 −1,H40 −1} = max{0,0−1,1−1,0−1} =0 = max{0,0+2,0−1,0−1} =2 H32 = max{0,H21 +σ 32 ,H22 −1,H31 −1} H42 = max{0,H31 +σ 42 ,H32 −1,H41 −1} = max{0,1+2,1−1,0−1} =3 = max{0,0−1,3−1,2−1} =2 H33 = max{0,H22 +σ 33 ,H23 −1,H32 −1} H43 = max{0,H32 +σ 43 ,H33 −1,H42 −1} = max{0,1−1,1−1,3−1} =2 = max{0,3+2,2−1,2−1} =5 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 28
19. Tạo vết A C A • Xuất phát từ Hnmax,mmax, nếu: 0 0 0 0 – Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo A 0 2 1 2 – Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui G 0 1 1 1 – Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên C 0 0 3 2 A 0 2 2 5 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Tìm kết quả A C A • Nếu → 0 0 0 0 – (i,j) (i-1,j-1): theo đường chéo Ui và Vj được ghi vào A 0 2 1 2 – (i,j) →(i-1,j): đi lên G 0 1 1 1 “-” và Vj được ghi vào C 0 0 3 2 – (i,j) →(i,j-1): đi lui U và “-” được ghi vào A 0 2 2 5 i PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 29
20. Ví dụ • Với trình tự dài hơn, chẳng hạn: • Kết quả bắt cặp U = “ATATGCTAAG” – U’ = “A-CA” V = “ACTACTTAG” – V’ = “AGCA” • Chọn d = -1, Match = 2 và Mismatch = -1 cho sự • Độ đánh giá: 3(2) + 1(-1) + 0(-1) = 5 tương đồng và không tương đồng của 2 phân tử trong 2 trình tự. PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Với kỹ thuật lưu vết như trên A T A T G C T A A G A T A T G C T A A G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A 0 2 1 2 1 0 0 0 2 2 1 A 0 2 1 2 1 0 0 0 2 2 1 C 0 1 1 1 1 0 2 1 1 1 1 C 0 1 1 1 1 0 2 1 1 1 1 T 0 0 3 2 3 2 1 4 3 2 1 T 0 0 3 2 3 2 1 4 3 2 1 A 0 2 2 5 4 3 2 3 6 5 4 A 0 2 2 5 4 3 2 3 6 5 4 C 0 1 1 4 4 3 5 4 5 5 4 C 0 1 1 4 4 3 5 4 5 5 4 T 0 0 3 3 6 5 4 7 6 5 4 T 0 0 3 3 6 5 4 7 6 5 4 T 0 0 2 2 5 5 4 6 6 5 4 T 0 0 2 2 5 5 4 6 6 5 4 A 0 2 1 4 4 4 4 5 8 7 7 A 0 2 1 4 4 4 4 5 8 8 7 G 0 1 1 3 3 6 5 4 7 6 10 G 0 1 1 3 3 6 5 4 7 7 10 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 30
21. Ví dụ • Với 2 trình tự như hình, có thể tính được • Cũng bằng cách ghi kết quả theo vết, 2 trình tự được bắt cặp: – U’ = “ACTA CTAAG” – V’ = “A-TATGCTAAG” • Kết quả: 8(2) + 3(-1) + 0(-1) = 13 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM • Kết quả trên ứng với match = 2, mismatch = -3 và gap = -2 • Khi đó, 8 là giá trị lớn nhất, nên bắt đầu từ vị trị này để xác định vết. • Từ đó, kết quả bắt cặp cục bộ của 2 đoạn trình tự: ATCC ATCC PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 31
22. Thuật toán ClustalW • Dùng cho việc bắt cặp nhiều trình tự (giải bài toán MSA) • Lấy ý tưởng từ thuật toán lũy tiến Thuật toán (Progessive Algorithm) CLUSTAL PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Thuật toán Clustal W • Thuật toán lũy tiến như sau: • Bước 1: – Bước 1: giải bài toán PSA trên 2 trình tự bất kỳ được – Dùng PSA cho tất cả các trình tự chọn. – Xác định mức độ tương đồng mỗi cặp – Bước 2: chọn một trình tự khác rồi sắp hàng với nhóm đã thực hiện. – Xây dựng ma trận khoảng cách tương đồng giữa các trình tự. – Bước 3: lặp lại Bước 2 cho trình tự khác PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 32
23. • Bước 2: – Xây dựng cây cây tương đồng (similarity tree) hay cây hướng dẫn (guide tree) bằng cách dùng thuật toán • Bước 3: Thực hiện quá trình lũy tiến gom nhóm Neighbor – Joining. – Căn cứ vào cây hướng dẫn xác định những nhánh có – Cây hướng dẫn hể hiện mối quan hệ tương đồng giữa cặp trình tự tương đồng lớn nhất các trình tự với nhau – Thực hiện PSA trên từng cặp – Kết hợp những cặp đó lại thu được kết quả đa trình tự. PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM Minh họa • Lần lượt bắt cặp: • Xét 5 trình tự: – S ’ = “ARDFGI” 1 – S1’ = “ARDFG-I” – S ’ = “A-KHGL” – S1 = “ARDFGI” 2 – S4’ = “AR-FGLI” – S2 = “AKHGL” – S ’ = “ARDFGI ” – S ’ = “ARDFGI ” – S3 = “ADFIKF” 1 1 – S3’ = “A-DF-IKF” – S5’ = “AKD ILM” – S4 = “ARFGLI” – S5 = “AKDILM” PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 33