Chuyên Đề Nghiên Cứu 7 - Tin Sinh Học. Giảng Viên: Ngô Công Thắng. Sinh viên thực hiện: Nguyễn Hồng Kiên. Lớp: Tin học A-K52. Khoa: Công Nghệ Thông Tin. Mã Sinh Viên: 521996. Chuyên Đề Nghiên Cứu 7 - Tin Sinh Học. Nội Dung: Nhóm 2: Nhóm 2: Tìm hiểu bài toán so sánh cặp trình tự: a. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự. b. Thuật toán ma trận điểm. d. Thuật toán quy hoạch động Needleman-Wunsch. 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 của 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 Needleman-Wunsch. 1. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự. - Đị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ự. 1. Nội dung và ý nghĩa sinh học 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ào hai chuỗi S1 và S2 các dấu cách (kí hiệu là ”-”) tại các vị 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. - Yêu cầu đặt ra là thực hiện bài toán sao cho tìm ra cặp chuỗi S1’, S2’ có sự tương đồng cao nhất. 1. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự Dựa trên phương pháp so sánh người ta chia ra làm 2 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. 1. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự Tùy thuộc vào số lượng trình tự, bài toán so sánh trình tự được chia làm 2 mức độ: - So sánh 2 trình tự - So sánh nhiều trình tự. 1. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự. - Ví dụ về so sánh trình tự theo hướng toàn cục: Toàn bộ 2 chuỗi trình tự L G P S S K Q T G K G S − S R I W D N và L N − I T K S A G K G A I M R L G D A được so sánh L G P S S K Q T G K G S − S R I W D N L N − I T K S A G K G A I M R L G D A 1. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự - Ví dụ về so sánh trình tự theo hướng cục bộ: Chỉ một phần của 2 chuỗi được so sánh: TGKG và AGKG − − − − − − − T G K G − − − − − − − − − − − − − − − A G K G − − − − − − − − 1. Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự [...]... và ý nghĩa sinh học của bài toán so sánh cặp trình tự - Ví dụ so sánh 2 trình tự: AC – –GCTG – CA TG –T– - Ví dụ so sánh nhiều trình tự AGT−GTG AGTAGTG −GTCGTG − −TAGTG 1 Nội dung và ý nghĩa sinh học của bài toán so sánh cặp trình tự • Ý nghĩa: - Trên quan điểm sinh học, phép so sánh trình tự thể hiện quá trình biến đổi chọn lọc tự nhiên của các chuỗi trình tự, từ đó cho phép các nhà sinh học đưa ra... tương ứng với 3 con đường truy hồi: 3 Thuật toán quy hoạch động Needleman-Wusch Ta có: 0+2-1+2+0+2+0= 5 0+2+0-1+2+2-0= 5 0+2-1+0+2+2+0=5 The End! • Trên đây là những tìm hiểu của em về chuyên đề nghiên cứu tin sinh học thứ 7 của thầy giáo • Bài Viết của em còn nhiều thiếu sót Em rất mong được sự góp ý, bổ sung của thầy giáo và các bạn để bài làm của em được hoàn thiện hơn Thank you for your attention... xạ được định nghĩa như sau: σ : (∑’)²→R Trong đó : ∑’=∑ − { ‘-’ } và ∑ là tập các amino acid hoặc nucleotide 2 Thuật toán ma trận điểm • Có nhiều loại ma trận điểm dựa trên quá trình nghiên cứu, thống kê thực tế sinh học • Hiện tại có 4 loại ma trận điểm: identity matrix, enetic code matrix, chemical similarity matrix và substitution matrix 2 Thuật toán ma trận điểm Identity matrix: • Đây là cơ chế... sinh học đưa ra kết luận về nguồn gốc của các đoạn gene, DNA, RNA, hay protein - Mặt khác, cho phép ta xây dựng 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 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 của 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 Needleman-Wunsch 2 Thuật toán... và hiện nay cũng được sử dụng phổ biến nhất • Ví dụ ma trận BLOSUM62 lưu trữ hàm đánh giá độ tương đồng của tập 23 amino acid 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 của 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 Needleman-Wunsch 3 Thuật toán quy hoạch động Needleman-Wusch • Giải thuật Needleman-Wusch là giải thuật gióng... tự với các giá trị khác, ta có ma trận sau: 3 Thuật toán quy hoạch động Needleman-Wusch - B3: Sử dụng kỹ thuật lưu vết để tìm ra kết quả: Dựa vào các con đường được sinh ra do kỹ thuật lưu vết từ S(m,n) đến S(0,0), các phép so sánh sẽ được sinh ra dựa trên nguyên tắc: + Nếu con đường đi theo hướng đường chéo từ S(i,j) đến S(i-1,j-1) thì 2 ký tự đại diện cho S1[i] và S2[j] sẽ được ghi vào kết quả + Nếu... di truyền Ngày nay ma trận này hiếm khi được sử dụng trong việc so sánh các chuỗi amino acid • Chemical similarity matrix (Ma trận tương đồng hóa học) : - Trong ma trận này, các amino acid có cấu trúc tương đồng về cấu trúc vật lý cũng như thuộc tính hóa học như kích thước, hình dạng, khả năng phân cực,… thì phần tử tương ứng trong ma trận sẽ nhận giá trị lớn hơn so với các cặp còn lại 2 Thuật toán... chất tự nhiên của các chuỗi trình tự, có thể tính giá trị của gap theo các hàm tuyến tính hoặc đa thức 3 Thuật toán quy hoạch động Needleman-Wusch • Trong thực tế, để đơn giản hầu hết các phương pháp đề xuất tính giá trị của gap dựa trên một hàm tuyến tính theo chiều dài của gap • (Một gap bao gồm các phần tử của 1 chuỗi mà mỗi phần tử này tương ứng với các phần tử có ký hiệu là “-“ của chuỗi còn lại.) . Chuyên Đề Nghiên Cứu 7 - Tin Sinh Học. Giảng Viên: Ngô Công Thắng. Sinh viên thực hiện: Nguyễn Hồng Kiên. Lớp: Tin học A-K52. Khoa: Công Nghệ Thông Tin. . Mã Sinh Viên: 521996. Chuyên Đề Nghiên Cứu 7 - Tin Sinh Học. Nội Dung: Nhóm 2: Nhóm 2: Tìm hiểu bài toán so sánh cặp trình tự: a. Nội dung và ý nghĩa sinh