›
›

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

pdf 37 trang ngocly 1970
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_tin_sinh_hoc_dai_cuong_chuong_3_bat_cap_trinh_tu_s.pdf

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. TIN SINH HỌC ĐẠI CƯƠNG (Introduction to Bioinformatics) Chương 3: BẮT CẶP TRÌNH TỰ (SEQUENCE PGS.TS. Trần Văn Lăng Email: langtv@vast.vn ALIGNMENT) PGS.TS. Trần Văn Lă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 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM NỘI DUNG • Giới thiệu MỘT SỐ KHÁI NIỆM CHUNG • Bắt cặp hai trình tự • Bắt cặp nhiều 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 1
  2. Nhắc lạ i • Các tế bào, với các ngăn khác nhau của nó gọi • Sinh vật được tạo thành từ tế bào. là bào quan, phải đối mặt với một vấn đề là: • Bên trong mỗi tế bào - ngoại trừ hồng huyết cầu – Tế bào sản xuất các phân tử như kích thích tố, dẫn trưởng thành - có nhân (nucleus) chứa tất cả các truyền thần kinh, các cytokine và enzyme chỉ thị di truyền (genetic instruction) – Chúng phải được gửi đến nơi khác bên trong tế bào, hoặc xuất ra khỏi tế bào. • Những chỉ thị này là chức năng của tế bào – Việc sản xuất và vận chuyển này phải được thực hiện đúng nơi và đúng lú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 • Chẳng hạn, mỗi tế bào người có 46 nhiễm sắc thể, được tổ chức thành 23 cặp. • Một gene là một đoạn của DNA với trình tự base • Mỗi nhiễm sắc thể được cấu thành bởi một trình đặc trưng – cụ thể, gọi là mã di truyền (genetic tự DNA code), hay chỉ thị di truyền để xác định chức • DNA chứa các gen mã hóa RNA mà nó sẽ sinh năng của tế bào ra các protein, để từ đó điều chỉnh tất cả các quá trình phát triển của một sinh vậ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 2
  3. Khái niệm bắt cặp • Bắt cặp trình tự, hay là sắp xếp thẳng hàng trình tự (Sequence Alignment) • Việc thêm các gap biểu thị sự đột biến mất • Mục đích đạt đến sự giống nhau đến mức tối đa nucliotide đã xãy ra tại vị trì này trên trình tự. của các trình tự • Trong tin học, việc thêm ký tự gap là khoảng • Việc bắt cặp được thực hiện bằng cách thêm các trống (“-”) giúp cho việc tạo ra 2 chuỗi ký tự gần “gap” vào các vị trí có thể sao cho các cột giống giống nhau nhất. nhau hoặc tương tự 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 Tiến hóa và đột biến • Dưới góc độ sinh học, đột biến xãy ra trên cả một • Trong sự tiến hóa, các gốc giống nhau đó chính trình tự DNA của bộ gene. là một phần của trình tự sinh học tổ tiên. • Vì vậy có thể xãy ra tại: • Còn các gốc bắt cặp không giống nhau chính là – các gene mã hóa protein sự đột biến của một trong hai trình tự. – các gene mã hóa phân tử RNA chức năng – Tuy nhiên, không thể xác định trình tự nào bị đột biến – trình tự điều hòa tham gia bật tắc gene khác so với trình tự nào. – vùng trình tự nối các gene 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 3
  4. • Từ đó, đột biến có thể ảnh hưởng hay không ảnh hưởng đến kiểu hình của sinh vật. • Khi phân loại, có 2 loại đột biến • Qua thời gian, những đột biến có lợi hoặc không có hại sẽ được giữ lại trong quần thể, kích thích – đột biến điểm: chỉ xãy ra ở một nucleotide, sẽ rất quan trọng nếu tại vùng mã hóa protein, hay vùng tín sự hình thành và phát triển loài mới. hiệu • Đó chính là sự tiến hóa (evaluation), trong đó đột – đột biến đoạn: do mất hay thêm một đoạn trình tự. Kết biến là nguyên liệu quan trọng quả của việc đột biến đoạn là sự nhân đôi gene hay nhân đôi một vùng nhiễm sắc thể 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í dụ • Ví dụ bắt cặp 2 trình tự • Tương tự, với 2 trình tự dài hơn – GAATTCAGTTA – tcctctgcctctgccatcat caaccc – GGATCGA • Hoặc 2 trình tự – |||| ||| ||||| ||||| |||||| • Kết quả – ACGCTG – tcctgtgcatctgcaatcatgggcaaccc – GAATTCAGTTA – CATGT – | || | | | • Kết quả – GGAT-C-G—-A – ACGCTG- – | | | – -C-ATGT 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 4
  5. Ký tự “gap” Nếu lấy v làm căn cứ, Cho 2 trình tự: thì u có: u = ATCTGATG • 4 match • Ký tự “gap” là chỗ trống, khe hở, chỗ gián đoạn, • 1 mismatch v = TGCATAC chỗ thiếu sót. • 3 insertion • 2 deletion • Trong sinh học gap có ý nghĩa: sự đột biến, hoặc deletion match mất đi do quá trình tiến hóa A T - C - T G A T G - T G C A T - A - C mismatch insertion 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ề bắt cặp trình tự protein • Sự bắt cặp trình tự không chỉ dừng lại ở trình tự DNA mà cả trình tự protein. • Trong đó, việc chỉ có 4 ký tự được thay bởi 20 ký • Mục đích tự. – Bắt cặp trình tự nhằm nghiên cứu sự tiến hóa • Tuy nhiên, do protein có đặc điểm bảo tồn cấu – Hoặc để tìm kiếm, so sánh mức độ tương đồng giữa trúc và chức năng cao (bởi nếu mất chức năng các trình tự sẽ gây bất lợ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 5
  6. Đánh giá sự bắt cặp • Vì vậy, trong qua trình tiến hóa có khuynh hướng • Thế nào là sự bắt cặp tốt, tiêu chuẩn nào. chỉ thay thế các amino acid có cấu trúc tương tự, • Có thể cho điểm tốt đối với giá trị Match, điểm ít làm thay đổi đến cấu trúc và chức năng protein xấu với các trường hợp ngược lại. • Những trình tự protein trong cùng một họ tiến • Tuy nhiên, với trình tự protein việc thay thế một hóa chung thường có sự thay thế giữa các amino amino acid khác vẫn bảo toàn cấu trúc và chức acid có cùng đặc tính hóa lý. năng cũng không thể là điểm xấu 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 Đánh giá • Sự tương tự giữa PAM và BLOSUM: • Chính vì vậy, với việc bắt cặp trình tự protein có – PAM100 ~ BLOSUM90 các ma trận điểm thay thế để xem xét khả năng – PAM160 ~ BLOSUM62 thay thế amino acid mà không ảnh hưởng này. – PAM250 ~ BLOSUM45 • Có 2 loại ma trận điểm thay thế: • PAM được tạo ra từ khoảng cách tiến hóa trong – Ma trận PAM (Percentage Accepted Mutation) các trình tự liên quan. – Ma trận BLOSUM (BLOck SUbstitution Matrix) – Chẳng hạn, PAM100 có khoảng cách tiến hóa 100 lần đột biến trên 100 gốc amino acid 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 6
  7. Hàm đánh giá trình tự DNA • Đánh giá sự bắt cặp trình tự DNA: dùng hàm đánh giá. • BLOSUM được tính toán thông qua tần suất thay • Chẳng hạn, nếu thế của các cặp amino acid trong việc bắt cặp – Match (Giống nhau ở cùng vi trí): giá trị là +2 các trình tự có độ tương đồng cao. – Mismatch (Không giống nhau): giá trị là -1 – Chẳng hạn, BLOSUM45 gồm các nhóm trình tự giống – Gap (Thêm vào hoặc bị loại bỏ): giá trị là -2 nhau 45% • Hàm đánh giá có giá trị càng cao thì sự giống nhau càng nhiều. 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 • Trong đó, – na, ni, ng: tương ứng là số phần tử giống nhau (match), • Định nghĩa: Mức độ tương đồng (điểm đánh giá) không giống nhau (mitmatch) và số gap. của 2 trình tự bắt cặp S1’ và S2’ là đại lượng: – match, mismatch, gap: tương ứng là giá trị tính toán để đánh giá. na x match + ni x mismatch + ng x gap – Thông thường, điểm dương cho match, điểm âm cho sự đột biến (mismatch và gap) 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 7
  8. Ví dụ • Với GAATTCAGTTA – match = 2 | || | | | – mismatch = -1 GGAT-C-G—-A – gap = -2 • Điểm đánh giá: 6 x (+2) + 4 x (-2) + 1 x (-1) = 3 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 ACGCTG- | || AC GCTG -C-ATGT | | | • Điểm: 3 x (+2) + 3 x (-2) + 1 x (-1) = -1 -CATG-T- tcctctgcctctgccatcat caaccc • Điểm đánh giá: 3 x (+2) + 5 x (-2) + 0 x (-1) = -4 |||| ||| ||||| ||||| |||||| tcctgtgcatctgcaatcatgggcaaccc • Điểm: 23 x (+2) + 3 x (-2) + 3 x (-1) = 37 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 8
  9. Phân loại – Bắt cặp cục bộ (Local alignment): chỉ thực hiện trên một vùng trình tự con tương đồng nằm ở các vị trí • Có 2 loại: khác nhau trên hai trình tự. – Bắt cặp toàn cục (Global alignment): được áp dụng – Mục đích tìm ra vùng trình tự tương đồng nhất. trên toàn bộ trình tự để tìm sự tương đồng giữa các – Sử dụng khi so sánh 2 trình tự có chiều dài khác trình tự. nhau, mức độ tương đồng trên toàn bộ là thấp. – Thường được sử dụng khi 2 trình tự có độ tương đồng Thuật toán: Smith - Waterman cao, chiều dài xấp xỉ nhau Thuật toán sử dụng: 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 Bắt cặp hai trình tự Ví dụ PSA • Bài toán (Pairwise Sequence Alignment - PSA): cho 2 trình tự sinh học S1, S2. Hãy tìm 2 trình tự – S1 = “ACGCTG” S1’, S2’ bằng cách thêm các ký tự ‘-’ sao cho: – S2 = “CATGT” – Điểm đánh giá Score(S1’, S2’) là lớn nhất với giá trị match, mismatch và gap cho trước – S1’ = “-ACGCTG” – Chiều dài S1’, S2’ là bằnh nhau (|S1’| = |S2’|) – S2’ = “CATG-T-” – Nếu loại bỏ ký tự gap từ S1’, S2’ sẽ nhận được S1, S2 ban đầu 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 9
  10. Bắt cặp đa trình tự Ví dụ MSA • Bài toán (Multiple Sequence Alignment - MSA): Cho k trình tự sinh học S1, S2, , Sk. Hãy tìm k trình tự S1’, S2’, , Sk’ bằng cách thêm các ký tự ‘-’ sao cho: • Thông thường, bắt cặp đa trình tự được sử dụng khi cần tìm – Mức độ tương đồng của các trình tự này là cao nhất kiếm một trình tự đại diện trong – |S ’| = |S ’|= = |S ’| 1 2 k tập hợp nhiều trình tự sinh học. – Nếu loại bỏ ký tự gap từ S1’, S2’, ,Sk’ sẽ nhận được S1, S2, , S2 tương ứ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 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í dụ • Với đoạn trình tự “ACTCGATT” • Trong quá trình tiến hóa, một đoạn gen có thể: – Mất T,C ở vị trí 3, 4: “ACGATT” – Đột biết vị trí 2 (thay C bằng G), vị trí 3 (thay G bằng – đột biến C), vị trí 6 (thay T bằng C): “AGCATC” – mất đi – Thêm TA vào vị trí 4: “AGCTAATC” – di truyền lại (giữ lại) • Như vậy, từ “ACTCGATT” sẽ tiến hóa “AC GATT”, “AG CATC”, “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 10
  11. • 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
  12. 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
  13. • 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. • 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
  24. • 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
  25. 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
  26. 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
  27. • 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. • 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
  34. – S2’ = “AKHGL-” – S2’ = “A KHGL” – S3’ = “ADF IKF” – S5’ = “AKDILM” – S3’ = “ADFIK F” – S4’ = “ARFGLI ” – S4’ = “ARFGLI” – S5’ = “AKDILM” – S2’ = “AKHGL-” – S3’ = “A-DFIKF” – S4’ = “ARFGLI” – S5’ = “AKD-ILM” 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 • Khoảng cách D(S1’,S2’) giữa 2 trình tự bằng tỷ số giữa m và n. Trong đó – m = số mismatch giữa 2 trình tự (không tính gap) • Ví dụ: – n = số cặp không phải là gap giữa 2 trình tự – S1’ = “ARDFGI ” • Ví dụ: – S3’ = “A-DF-IKF” Có m = 0, n = 4. Suy ra D(S ’,S ’) = 0/4 = 0 – S1’ = “ARDFGI” 1 3 – S2’ = “A-KHGL” Có m = 3, n = 5. Suy ra D(S1’,S2’) = 3/5 = 0,6 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 34
  35. Ma trận khoảng cách S1 S2 S3 S4 S5 S1 - • Ví dụ: S2 0,60 - – S1’ = “ARDFGI ” S3 0 0,33 - – S5’ = “AKD ILM” Có m = 1, n = 4. Suy ra D(S1’,S5’) = 1/4 = 0.25 S4 0 0,40 0,25 - S5 0,25 0,60 0,40 0,66 - 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 S13 S2 S4 S5 • Theo ma trận khoảng cách, có thể S1 và S3 là S13 nhỏ nhất, nên mức độ gần nhau là nhiều nhất. (0,6+0,33)/2 = S2 • Hoặc S1 và S4 0.465 (0+0,25)/2 = S4 0,4 0.125 (0,25+0,4)/2 = S5 0,6 0,66 0.325 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 35
  36. S13,4 S2 S5 S13,4 (0,465+0,4)/2 = S2 • Tiếp tục, khoảng cách giữa S13 và S4 là nhỏ 0,4325 nhất. (0,325+0,66)/2 S5 0,6 = 0,4925 • Nên S13 và S4 là gần nhau 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 ARDFGI S1 ARDFGI A-DF-IKF • Tiếp tục, còn S134 và S2 là nhỏ nhất ARDFG-I A-DF IKF AR-FGLI S3 ADFIKF S134,2 S5 ARDFG-I A-DF IKF AR-FGLI S134,2 A-KHGL S4 ARFGLI (0,4925+0,6)/2 = S5 ARDFG-I 0,54625 A-DF IKF AR-FGLI S2 AKHGL A-KHGL AKD ILM 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 36
  37. • Ở đây kết quả có được bằng cách gióng từng cặp: – S1, S3 – Lấy kết quả S1 có được để bắt cặp với S4 – Tương tự, với S2 – Rồi với S5 PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 37