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

Định nghĩa Định nghĩa: so sánh trình tựphép gióng hang gióng cột là quá trình nghiên cứu sự giống nhau giữa các chuỗi trình tự,là cách thức so sánh giữa 2 hay nhiều trình tự dựa trên việ

Báo cáo tin sinh học

 Sinh viên thực hiện: Nguyễn Thị Thu Quỳnh

 Lớp : tin học C-k52

 Khoa: Công nghệ thông tin

Chuyên đề 7: Tìm hiểu bài toán

1 Nội dung và ý nghĩa của bài toán so sánh cặp chuỗi

 a Định nghĩa

 b Ý nghĩa

a Định nghĩa

Định nghĩa: so sánh trình tự(phép gióng hang gióng cột) là quá trình nghiên cứu sự giống nhau giữa các chuỗi trình tự,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ự Các trình tự

được đề cập đến trong phần nghiên cứu này

là các chuỗi trình tự DNA, RNA hoặc các trình

tự amino axit

Một vài ý nghĩa của việc so

sánh các trình tự

 Đá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 1 trình

2 Thuật toán ma trận điểm (dot matrix)

a Phương pháp ma trận điểm

b Thuật toán ma trận điểm

c Ví dụ

a Phương pháp ma trận điểm

 Phương pháp ma trận 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 trình tự vì chúng làm thay đổi

hướng theo chiều ngan hoặc dọc

 Phương pháp này có 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 trong

protein

b Thuật toán ma trận điểm

 B1: Khởi tạo 1 sơ đồ từ 2 chuỗi ban đầu

(Một trình tự viết theo chiều ngang trang giấy và trình tự còn lại viết từ trên xuống dưới bên tay trái)

 B2: Các axit amin hay nucleotide của mỗi trình tự đối chiếu với nhau.Khi nào chúng giống nhau thì được đánh bởi 1 dấu chấm.

 B3: Kết quả sẽ tạo ra một bảng các điểm chấm Nếu các điểm chấm là liên tục sẽ tạo thành 1 chuỗi các điểm châm.

Ví dụ1

 So sánh 2 cặp trình tự giống nhau Seq1: ATTCCGGTACGT

Seq2: ATTCCGGTACGT

Ví dụ 2

 So sánh 2 cặp trình tự khác nhau Sqe1: ATTCCGGTACGT

Sqe2: ATTCCAAAGGTACGT

4 Thuật toán quy hoạch động Needman-Wunch

 a Giới thiệu chung về thuật toán.

 b Giải thuật tổng quát.

 c Ví dụ minh họa.

a Giới thiệu tổng quát

 Năm 1970 needleman và wunsch đã tạo ra quá trình alignment bằng cách so sánh 2 axit amin đồng thời Họ bắt đầu ở cuối của mỗi trình tự và sau đó di chuyển dần lên trên mỗi lần 1 cặp axit amin, đồng thời cho phép rất nhiều dạng tổ hợp khác nhau của các cặp

ghép, cặp k0 ghép, hoặc các axit amin thêm trong 1 trình tự

 Trong thuật ngữ của khoa học máy tính, quá trình này được gọi là chương trình động học

b Thuật toán quy hoạch động Needman-Wunch

 Phát biểu bài Toán:

Giả sử có hai trình tự A và B Để việc sắp gióng cột cặp trình tự AB 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 gióng cột được đặc trưng bằng ma

trận tương đồng, 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 trình tự A (có chiều dài x), các

kí tự của trình tự B (có chiều dài y) được biểu diễn

trên trục tung.

 GAP???

Trong quá trình sắp gióng cột, các

khoảng trống gap(được kí hiệu bằng dấu _) được chèn vào giữa các vị trí

nucleotide hay amino axit để các trình

tự có sự tương tự nhau nhiều nhất

trong mỗi cột.

Nếu 2 trình tự được sắp gióng cột có chung 1 tổ tiên, các gap biểu thị cho các đột biến thêm vào hay mất đi của nucleotide trong quá trình tiến hóa.

 Trong sắp gióng cột các trình tự protein,

mức độ tương đồng giữa các amino axit biểu thị cho sự bảo tồn của một vùng đặc biệt

trong sắp trình tự Sắp gióng cột protein cũng cho thấy có sự thay thế các amino axit Sự

thay thế bởi các amino axit có đặc tính sinh hóa tương tự nhau ( sự thay thế có tính bảo tồn) tại một vùng đặc biệt của trình tự giải

thích cho vai trò quan trọng về cấu trúc hoặc chức năng của vùng đó.

 Các bước thực hiện thuật toán:

 Bước 1: Khởi tạo ma trận từ 2 chuỗi sequence.

 Bước 2: lấp đầy ma trận

 Bước 1: Khởi tạo ma trận từ 2 chuỗi

Ta khởi tạo ma trận F như sau:

Fi,j = MAX[ Fi-1, j-1 + Si,j ,Fi,j-1 + d , Fi-1,j + d ]

 Bước 3:Traceback

1 Dựa vào kỹ thuật lưu vết để tìm đường đi ngược lại

a Khởi tạo: Xuất phát từ ô (m,n)

b.Các bước lặp: Từ ô (i,j) ta xét các ô 1,j-1), 1,j), (i,j-1)

- Nếu F(i,j) = F(i,j-1) +d thì ta có đường đi từ ô (i,j-1) đến ô (i,j)

- Nếu F(i,j) = F(i-1,j) +d thì ta có đường đi từ ô (i-1,j) đến ô (i,j)

- Nếu F(i,j) = F(i-1,j-1) + S (i,j) với điều kiện A[j] giống B[i] thì ta có đường đi từ ô (i,j) đến ô (i-1,j-1)

- Nếu F(i,j) = F(i-1,j-1) thì cũng có đường đi từ

ô (i,j) đến (i-1,j-1)

 Mỗi bước có thể chọn nhiều đường đi

2 Tìm ra các alignment( The edit transcript)

+ Nếu đường đi theo hướng đường chéo từ ô (i-1,j-1) đến ô (i,j)

- Nếu A[j] giống B[i] thì A[j] và B[i] được nối với nhau

- Nếu A[j] khác B[i] thì A[j] được gióng với B[i] nhưng không được nối ( được gọi là sự thay thế _ substitution)

+ Nếu đường đi theo hướng từ ô (i,j-1) đến ô (i,j)thì chèn thêm một Gap ở B gióng với A[j]+ Nếu đường đi theo hướng từ ô (i-1,j) đến ô (i,j) thì chèn thêm một Gap ở A gióng với B[i]

c Ví dụ minh họa

 Cho 2 trình tự A và B:

Trình tự A: GAATTCAGTTA (n=11) Trình tự B: GGATCGA (m=7) Hãy so sánh 2 trình tự trên?

Input: 2 trình tự A,B.

Output: các alignment

 Trong đó n là độ dài của trình tự A, m

Bước 1 Khởi tạo

hàng

Bước 2: Lấp đầy ma trận

 Tính Fi,j theo công thức

 Qui ước: F i-1, j-1 sẽ có màu đỏ, F i, j-1 sẽ có màu xanh lá cây và F i-1, j sẽ được màu xanh lam Ta lần lượt điền các giá trị Fi,j cho đến khi lấp đầy ma trận

Các Fi,j còn lại tính tương tự Cuối cùng ta được

Bước 3: Traceback

 Bắt đầu từ giá trị cuối cùng của ma trận

ta xác định đường đi.

 kết quả được một alignment :

 G _ A A T T C A G T T A | | | | | |

G G _ A _ T C _ G _ _ A

Tài liệu tham khảo

 1.Bài giảng tin sinh học-thầy Phan Trọng Nhật

 2 Bài giảng tin sinh học- thầy Ngô Công Thắng

 4.http://tailieu.vn