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

BÁO CÁO CHUYÊN ĐỀ 9 Đề tài: Tìm hiểu về thuật toán Clustalw 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 đa trình tự : I. Nội dung và ý nghĩa của bài toán so sánh đa trình tự. 1. Nội dung bài toán so sánh đa trình tự 2. Ý nghĩa của bài toán so sánh đa trình tự. II.Trình bày thuật toán so sánh đa trình tự CLUSTAL I. Cho biết nội dung và ý nghĩa của bài toán so sánh đa trình tự 1. Nội dung bài toán so sánh đa trình tự -Định nghĩa: + Gióng đa chuỗi (Multiple Sequence Alignment _MSA) là phương pháp so sánh nhiều chuỗi được thực hiện bằng cách chèm thêm các dấu cách vào các chuỗi để thu được các chuỗi có cùng chiều dài sao cho khi gióng theo từng cột thì mỗi ký tự trong một chuỗi gióng thẳng với một ký tự hoặc dấu cách trong các chuỗi khác và không có cột nào có toàn dấu cách. Một phương án gióng đa chuỗi được gọi là tối ưu nếu có số ký tự giống nhau hoặc tương tự nhau trên từng cột ký tự là lớn nhất -Nội dung bài toán gióng đa chuỗi + Cho k chuỗi sinh học S1, S2,…,Sk. Bài toán gióng đa chuỗi ( Multiple Sequence Alignment_MSA )của k chuỗi này được thực hiện bằng cách thêm các ký tự “-” vào các chuỗi S1, S2,…,Sk sẽ tạo ra k chuỗi mới S’1, S’2,…, S’k tương ứng với: |S’1|=|S’2|=…=|S’k|=n Sau đó gióng theo từng cột thì mỗi ký tự trong một chuỗi gióng thẳng với một ký tự hoặc dấu cách trong các chuỗi khác và không có cột nào có toàn dấu cách + Nếu bỏ đi các ký tự “-” khỏi S’i ta sẽ được lại chuỗi ban đầu Si (1≤i≤k) k được gọi là số chuỗi (sequence) của MSA n: là chiều dài của MSA. MSA có n cột, mỗi cột chứa các ký tự đại diện cho các chuỗi của MSA, các ký tự này có thể là các amino acid(nucleotide) hoặc DNA 2. Ý nghĩa của bài toán so sánh đa trình tự + Bài toán gióng đa chuỗi có ý nghĩa rất to lớn trong tin sinh học. Giả sử có một tập hợp gồm nhiều chuỗi đại diện cho những loài sinh vật, nhìn vào tập hợp loài nào đó có thể đặt câu hỏi liệu tổ tiên của chúng có quan hệ với nhau không? Giữa chúng có mối quan hệ gì?Để trả lời những câu hỏi đó ta phải xét đến quá trình tiến hóa của những loài vật + Mặt khác kết quả gióng đa chuỗi cho phép ta xây dựng được cây phát sinh chủng loài, xây dựng cây tiến hóa, từ đó đánh giá được mối quan hệ giữa các loài II Trình bày thuật toán so sánh đa trình tự CLUSTALW 1.Khái quát + Giải thuật ClustalW là phương pháp cải tiến cho gióng đa chuỗi. Phương pháp này đang được sử dụng rộng rãi cho gióng đa chuỗi và xây dựng cây phát sinh loài bởi vì phương pháp này giải quyết về độ phức tạp tính toán mà những phương pháp khác chưa giải quyết được, đồng thời giải quyết được bài toán gióng đa chuỗi – xây dựng cây phát sinh chủng loài và đánh giá được mức độ tương đồng giữa các chuỗi + Phương pháp này xây dựng gióng đa chuỗi bắt đầu với việc xác định một gióng cặp có mối quan hệ tương đồng lớn nhất Input: k chuỗi sinh học S1,S2,…Sk cần so sánh Output: kết quả phương án gióng đa chuỗi tối ưu (k chuỗi S1’,S2’…Sk’ có độ dài bằng nhau) b. Các bước của giải thuật ClustalW Gồm 3 bước: + Bước 1: Thực hiện gióng cặp chuỗi giữa tất cả những chuỗi và xác định mức độ tương đồng giữa mỗi cặp. Từ đó xây dựng ma trận khoảng cách(distance) tương đồng giữa các chuỗi. + Bước 2: Từ ma trận khoảng cách xây dựng cây chỉ dẫn (guide tree) thể hiện mối quan hệ tương đồng giữa các chuỗi. Sử dụng phương thức Neighbor-Joining(quan hệ hàng xóm). + Bước 3: Xây dựng gióng đa chuỗi (MSA). Từ kết quả trong bước 2 thu được cây chỉ dẫn(guide tree), căn cứ vào cây chỉ dẫn xác định những nhánh có cặp chuỗi tương đồng lớn nhất thực hiện gióng cặp, rồi kết hợp những gióng cặp đó lại ta thu được kết quả gióng đa chuỗi. Xét ví dụ: Gióng 4 chuỗi S1, S2, S3, S4 sử dụng giải thuật ClustalW + Input: gồm 4 chuỗi S1,S2,S3,S4 + Output: Phương án gióng đa chuỗi tối ưu cho 4 chuỗi Bước 1: Sử dụng phương pháp gióng đôi (PSA) để gióng cặp giữa tất cả những chuỗi ta thu được những gióng cặp sau : PSA (S1,S2) PSA(S1,S3) PSA (S1,S4) PSA(S2,S3) PSA(S2,S4) PSA(S3,S4) Từ đó, tính khoảng cách giữa những cặp như sau: “Với mỗi gióng đôi tìm kiếm những vị trí không chứa dấu cách (non-gapped) và đếm số cặp ký tự khớp giữa 2 chuỗi (m), sau đó chia cho chiều dài của 2 chuỗi (n)_ là chiều dài chuỗi được tính không có dấu cách. VD : N K L – O N - M L N O N Ta tính được: m=3, n=4 => distance= m/n= 3/4= 0.75 Giá trị này còn thể hiện phần trăm tương đồng giữa 2 chuỗi (75%). Giả sử sau đó ta thu được ma trận khoảng cách giữa 4 chuỗi trên như sau: Bước 2: Xây dựng cây chỉ dẫn: Từ ma trận khoảng cách ở bước 1 chúng ta nhận thấy S1 và S3 có độ tương đồng nhất nên ta xây dựng cây gồm 2 chuỗi S1 và S3 Tiếp theo chúng ta sẽ xác định mức độ tương đồng giữa nhánh gồm S1 và S3 với những chuỗi còn lại. Bằng cách xây dựng ma trận khoảng cách mới (bớt S1, S3 và thêm S1,3 Cách tính khoảng cách giữa S1,3 và S4 là: Distance (S1,3,4) = [distance(S1,S4) + distance(S3,S4)]/2 = (0.59 + 0.62)/2 = 0.6 Từ ma trận trên ta thấy S4 tương đồng với S1,3 hơn là S2. Tương tự với những giá trị khác, lần lượt từ đó chúng ta xây dựng được cây chỉ dẫn: Bước 3: Xây dựng gióng đa chuỗi Từ guide tree(cây chỉ dẫn) trong bước 2, chúng ta nhận thấy S1, S3 có quan hệ gần gũi nhất. Thực hiện gióng cặp giữa S1 và S3 được kết quả gióng gồm 2 chuỗi S1, S3. Tiếp theo thực hiện gióng 3 chuỗi S1, S3, S4. Cuối cùng kết hợp gióng với S2. Tài liệu tham khảo 1.Bài giảng Tin Sinh Học GV. Ngô Công Thắng 2.Tạp chí phát triển KH&CN tập 10 số 04_2007 3.Luận văn Thạc sỹ Phạm Mạnh Hùng Trường Đại Học Bách Khoa Tp HCM 4.