Báo cáo Tìm hiểu bài toán so sánh cặp trình tự

BÁO CÁO CHUYÊN ĐỀ 7 GV: Ngô Công Thắng SV:Vũ Thị Thùy Linh NỘI DUNG Tìm hiểu bài toán so sánh cặp trình tự: 1.Nội dung và ý nghĩa sinh học bài toán so sánh cặp trình tự. 2.Thuật toán ma trận điểm 3.Thuật toán quy hoạch động Smith-Waterman 1.Nội dung và ý nghĩa sinh học bài toán so sánh cặp trình tự. 1.1 Nội dung - Định nghĩa so sánh trình tự: là quá trình nghiên cứu sự giống nhau giữa các chuỗi trình tự(sequence),là cách thức so sánh giữa 2 hay nhiều trình tự dựa trên việc so sánh một chuỗi các thành phần(ký tự) của trình tự để tìm ra những điểm tương đồng, giống nhau giữa các trình tự. - Nội dung của bài toán so sánh cặp trình tự. + Cho 2 chuỗi sinh học S1,S2. Gióng cặp chuỗi này được thực hiện bằng cách chèn thêm vàohai chuỗi S1 và S2 các dấu cách (kí hiệu là-) tại các cị trí bất kỳ với số lượng không hạn chế để tạo ra 2 chuỗi S1’ và S2’ tương ứng, sau đó đặt một chuỗi trên chuỗi kia sao cho môi kí tự của chuỗi này gióng thẳng với một kí tự của chuỗi kia và cặp trình tự gióng không đồng thời là dấu cách. + Chuỗi sinh học ban đầu không có dấu cách và nếu loại bỏ dấu khỏi S1’ và S2’ ta sẽ có S1 và S2 ban đầu. -Phân loại: + Phép so sánh trình tự theo hướng toàn cục: Phép toán so sánh được áp dụng trên toàn bộ chuỗi trình tự. Thường được sử dụng khi các trình tự so sánh có kích thước gần tương đương và các trình tự này có độ tương đồng, giống nhau cao. +Phép so sánh trình tự theo hướng cục bộ: Phép toán so sánh được sử dụng trên một phần của chuỗi trình tự. Thường được sử dụng khi các trình tự có chiều dài lớn, độ tương đồng giống nhau không cao, chỉ có một số ít các gene giống nhau trên 2 trình tự, hoặc khi 2 trình tự có kích thước khác biệt lớn. VD: +So sánh tổng thể cả chuỗi (toan cuc) L G S S K Q T G K G S - R I T D | | | | | | | L N - Y K S A G K G A I R L G D +So sánh cục bộ một đoạn chuỗi(cuc bo) L G S S K Q T [G K G] S - R I T D | | | L N - Y K S A [G K G] A I R L G D 1.2 Ý nghĩa sinh học - Đánh giá mức độ sai khác giữa các trình tự do nhiều nguyên nhân. Có thể ứng dụng để phát hiện các đột biến điểm hoặc mất đoạn Nucleotide. - Xác định được các Intron, exon(khi so sánh một trình tự mRNA với trình tự DNA). Xác định được các vùng bảo thủ trong các trình tự chẳng hạn như vùng Promoter(kỹ thuật footprinting). Nghiên cứu và xây dựng cây phát sinh chủng loại(Phylogenetic). - Là một phần không thể thiếu khi đăng ký trình tự vào ngân hàng EMBL. - Là cơ sở xây dựng cây phát sinh chủng loại. 2.Thuật toán ma trận điểm -Là thuật toán khá đơn giản. Ra đời năm 1970 bởi Gibbs và G.A.McIntyre để so sánh hai trình tự Nucleotide và trình tự axit amin. -Bài toán: Cho hai chuỗi S1 và S2. Từ đó tạo ra hai chuỗi S1’ và S2’ sao cho có độ tương đồng cao nhất +Input: Hai chuỗi S1,S2 Ma trận F +Out put: Hai chuỗi S1’,S2’ - Thuật toán: +Bước 1: Thiết lập bảng ô vuông và chép trình tự một chuỗi theo hàng và một chuỗi theo cột dọc vuông góc với nhau +Bước 2: Đánh dấu vào tất cả các ô vuông tương ứng cùng với một nucleotide, dùng thước kẻ nối tất cả các ô được đánh dấu liền kề nhau theo chiều đường chéo phía góc trên bên trái kẻ xuống để xác định đoạn chuỗi tương đồng -VD:So sánh 2 chuỗi: ATCGAGGCTAATCACACT ATCGACTATAATACACT -Bước 1: -Bước 2: +Từ ma trận điểm có thể thấy dường như có sự tồn tại một khả năng là hai chuỗi trên có cùng nguồn gốc, với sự sao chép nhầm lẫn giữa chúng ở đoạn GGC và một đột biến đứt đoạn tại C theo sơ đồ sau: A T C G A G G C T A A T C A C A C TA T C G A C T A T A A T - A C A C T -Ưu điểm: +Phương pháp này cho phép phát hiện sự có mặt của các dạng mất đoạn hoặc thêm đoạn giữa hai trình tự. +Phương pháp này nó thể hiện một số đặc điểm, chẳng hạn như là sự tương đồng giữa các nhiễm sắc thể, các vùng lặp lại trong trình tự Protein, các trình tự bổ sung trong RNA mà có thể dẫn đến hình thành cấu trúc bậc 2. 3.Thuật toán quy hoạch động Smith-Waterman -Thuật toán Smith-Waterman là một thuật toán quy hoạch động dùng để tìm kiếm cơ sở dữ liệu phát triển bởi TF Smith và MS Waterman vào năm 1981 và dựa trên một mô hình thích hợp trước đó có tên Needleman và Wunsch -Đặc điểm:Thuật toán Smith-Waterman là thuật toán gióng cặp chuỗi cục bộ dựa trên quy hoạch động để tính điểm cho quá trình gióng chuỗi. Ý nghĩa:Giải thuật này giúp nhận ra những miền tương đồng giữa hai chuỗi tìm kiếm cho gióng chuỗi cục bộ tối ưu hơn. Giải thuật xây dựng trên ý tưởng so sánh tìm ra những đoạn hay những miền của hai chuỗi mà có độ tương đồng cao nhất, để từ đó đánh giá mức độ tương đồng giữa hai chuỗi -Quá trình gióng chuỗi được thực hiện bởi việc gióng chuỗi từng cặp trong 2 chuỗi. +Khi đó điểm cho gióng chuỗi từng cặp ký tự phụ thuộc vào: hai ký tự là giống nhau (matches), hai ký tự không giống nhau (mismatches) và điểm cho việc thêm/bớt khoảng trống (gap penalty). Kết quả của gióng cặp cục bộ là tìm ra được những đoạn trong 2 chuỗi có độ tương đồng cao nhất. *Bài toán:Giả sử có hai chuỗi S1 và S2. Để việc sắp trình tự cặp chuỗi S1, S2 có điểm cao nhất (tức cho kết quả tương đồng cao nhất), một ma trận F hai chiều được tạo ra. Mỗi vị trí trong ma trận được kí hiệu là Fij. Điểm cho sắp trình tự được đặc trưng bằng ma trận thay thế S, trong đó: -S(i,j) là điểm tương đồng giữa hai kí tự i và j. -d là một điểm phạt tuyến tính cho các gap (gap penalty). Trong ma trận, trục hoành là các kí tự của chuỗi S1 (có chiều dài n), các kí tự của chuỗi S2 (có chiều dài m) được biểu diễn trên trục tung. THUẬT GIẢI - Input: + 2 chuỗi S1, S2 với chiều dài tương ứng là n, m + Ma trận thay thế S + Gap penalty d - Output: 2 chuỗi S1’,S2’ Bước 1: Khởi tạo + F(0,0)=0 + F(i,0)=0 0≤ i ≤ m + F(0,j)=0 0≤ j ≤ n Bước 2: Điền giá trị vào ma trận + Tính F(i,j) theo công thức: F(i,j)=Max ( 0, F(i-1,j-1) + S(i,j), F(i-1,j)+d, F(i,j-1)+d ) (1) + Mỗi khi tính F(i,j) lưu lại chỉ số của số hạng ở vế phải (1) Bước 3: Tìm ô (i_max,j_max) có điểm cao nhất (0≤ i ≤ m, 0≤ j ≤ n) Bước 4: Traceback - Xuất phát từ ô (i_max,j_max). Dựa vào những chỉ số đã lưu ở bước 2 để tìm traceback cho đến khi gặp ô F(i,j) = 0 thì dừng. - Xét ô (i,j) + Nếu đường đi theo chiều ngang hay từ ô (i,j-1) sang ô (i,j) thì thêm “ – “ vào S2’ và thêm ký tự S1(j) vào S1’. + Nếu đường đi theo chiều thẳng đứng hay từ ô (i-1,j) xuống ô (i,j) thì thêm “ – “ vào S1’ và thêm ký tự S2(i) vào S2’. + Nếu đường đi theo đường chéo hay từ ô (i-1,j-1) đến ô (i,j) thì thêm ký tự S1(j) vào S1’ và S2(i) vào S2’ Đảo ngược S1’, S2’ - Ví dụ Bước1: Khởi tạo Bước 2: Điền giá trị vào ma trận theo công thức F(i,j)=Max ( 0, F(i-1,j-1) + S(i,j), F(i-1,j)+d, F(i,j-1)+d ) Cho Match =2 , Mismatch=-1, D=-1 Bước 3: Tìm ô ( i max,j max) có điểm cao nhất Bước 4: Traceback Kết quả như sau: -Nhận xét: Sử dụng thuật toán qui hoạch động SW giải quyết bài toán so sánh trình tự theo hướng tìm ra lời giải gần tối ưu nhất dựa trên các bước di chuyển tốt của của mỗi trạng thái của lời giải so với các trạng thái xung quanh nó trong mỗi vòng lặp xác định. Chủ yếu được sử dụng cho việc giải quyết bài toán so sánh theo hướng toàn cục. +Ưu điểm: giảm không gian tìm kiếm của lời giải, tốc độ tìm kiếm nhanh… +Nhược điểm: do phương pháp tìm kiếm cục bộ chỉ đảm bảo tính đúng chứ không đảm bảo tính đầy đủ(complete), và do việc lựa chọn các bước đi để thoát khỏi tình trạng tối ưu cục bộ là ngẫu nhiên nên có thể thuật toán sẽ không tìm ra được lời giải tốt trong một số lần chạy(phụ thuộc vào việc ấn định các tham số đầu vào). Tài liệu tham khảo 1. Bài giảng tin sinh học Nguyễn Đức Bách – Phan Trọng Nhật Trường ĐH Nông Nghiệp HN 2. GT Tin sinh hoc GS.TS: Nguyễn Văn Cách NXB Khoa học và kỹ thuật 3.Các trang web: