Bài giảng Tin sinh học đại cương - Chương 3: Bắt cặp trình tự (Sequence Alignment)

TIN SINH HỌC ĐẠI CƯƠNG (Introduction to Bioinformatics)

Chương 3: BẮT CẶP TRÌNH TỰ (SEQUENCE ALIGNMENT)

PGS.TS. Trần Văn Lăng Email: langtv@vast.vn

PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM

NỘI DUNG

MỘT SỐ KHÁI NIỆM CHUNG

•  Giới thiệu •  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

Nhắc lại

•  Các tế bào, với các ngăn khác nhau của nó gọi là bào quan, phải đối mặt với một vấn đề là: –  Tế bào sản xuất các phân tử như kích thích tố, dẫn

truyền thần kinh, các cytokine và enzyme

–  Chúng phải được gửi đến nơi khác bên trong tế bào,

•  Sinh vật được tạo thành từ tế bào. •  Bên trong mỗi tế bào - ngoại trừ hồng huyết cầu trưởng thành - có nhân (nucleus) chứa tất cả các chỉ thị di truyền (genetic instruction)

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

•  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ỗi nhiễm sắc thể được cấu thành bởi một trình

tự DNA

•  DNA chứa các gen mã hóa RNA mà nó sẽ sinh

•  Một gene là một đoạn của DNA với trình tự base đặc trưng – cụ thể, gọi là mã di truyền (genetic code), hay chỉ thị di truyền để xác định chức 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

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

của các trình tự

nucliotide đã xãy ra tại vị trì này trên trình tự. •  Trong tin học, việc thêm ký tự gap là khoảng

trống (“-”) giúp cho việc tạo ra 2 chuỗi ký tự gần giống nhau nhất.

•  Việc bắt cặp được thực hiện bằng cách thêm các “gap” vào các vị trí có thể sao cho các cột giống 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

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.

•  Còn các gốc bắt cặp không giống nhau chính là

sự đột biến của một trong hai trình tự. –  Tuy nhiên, không thể xác định trình tự nào bị đột biến

so với trình tự nào.

•  Vì vậy có thể xãy ra tại: –  các gene mã hóa protein –  các gene mã hóa phân tử RNA chức năng –  trình tự điều hòa tham gia bật tắc gene khác –  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

•  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

–  đột biến điểm: chỉ xãy ra ở một nucleotide, sẽ rất

•  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 sự hình thành và phát triển loài mới.

quan trọng nếu tại vùng mã hóa protein, hay vùng tín hiệu

•  Đó chính là sự tiến hóa (evaluation), trong đó đột

biến là nguyên liệu quan trọng

–  đột biến đoạn: do mất hay thêm một đoạn trình tự. Kết 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

Ví dụ

•  Tương tự, với 2 trình tự dài hơn

•  Ví dụ bắt cặp 2 trình tự

•  Hoặc 2 trình tự

– GAATTCAGTTA – GGATCGA

•  Kết quả

– tcctctgcctctgccatcat---caaccc – |||| ||| ||||| ||||| |||||| – tcctgtgcatctgcaatcatgggcaaccc

– ACGCTG – CATGT •  Kết quả

– GAATTCAGTTA – | || | | | – 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

Ký tự “gap”

•  Ký tự “gap” là chỗ trống, khe hở, chỗ gián đoạn,

Cho 2 trình tự: u = ATCTGATG v = TGCATAC

chỗ thiếu sót.

Nếu lấy v làm căn cứ, thì u có: •  4 match •  1 mismatch •  3 insertion •  2 deletion

match

•  Trong sinh học gap có ý nghĩa: sự đột biến, hoặc

deletion

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

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ý

tự.

•  Mục đích

–  Bắt cặp trình tự nhằm nghiên cứu sự tiến hóa –  Hoặc để tìm kiếm, so sánh mức độ tương đồng giữa

•  Tuy nhiên, do protein có đặc điểm bảo tồn cấu trúc và chức năng cao (bởi nếu mất chức năng sẽ gây bất lợi)

các 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

Đánh giá sự bắt cặp

•  Thế nào là sự bắt cặp tốt, tiêu chuẩn nào. •  Có thể cho điểm tốt đối với giá trị Match, điểm

•  Vì vậy, trong qua trình tiến hóa có khuynh hướng chỉ thay thế các amino acid có cấu trúc tương tự, í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

hóa chung thường có sự thay thế giữa các amino acid có cùng đặc tính hóa lý.

•  Tuy nhiên, với trình tự protein việc thay thế một amino acid khác vẫn bảo toàn cấu trúc và chức 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

Đá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ó các ma trận điểm thay thế để xem xét khả năng thay thế amino acid mà không ảnh hưởng này.

–  PAM100 ~ BLOSUM90 –  PAM160 ~ BLOSUM62 –  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) –  Ma trận BLOSUM (BLOck SUbstitution Matrix)

các trình tự liên quan. –  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

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á.

•  Chẳng hạn, nếu

•  BLOSUM được tính toán thông qua tần suất thay thế của các cặp amino acid trong việc bắt cặp các trình tự có độ tương đồng cao. –  Chẳng hạn, BLOSUM45 gồm các nhóm trình tự giống

–  Match (Giống nhau ở cùng vi trí): giá trị là +2 –  Mismatch (Không giống nhau): giá trị là -1 –  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

•  Trong đó,

–  na, ni, ng: tương ứng là số phần tử giống nhau (match),

không giống nhau (mitmatch) và số gap.

•  Định nghĩa: Mức độ tương đồng (điểm đánh giá) 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

Ví dụ

•  Với

GAATTCAGTTA | || | | | GGAT-C-G—-A

–  match = 2 –  mismatch = -1 –  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

ACGCTG- | || -C-ATGT

AC--GCTG | | | -CATG-T-

•  Điểm đánh giá: 3 x (+2) + 5 x (-2) + 0 x (-1) = -4

•  Điểm: 3 x (+2) + 3 x (-2) + 1 x (-1) = -1 tcctctgcctctgccatcat---caaccc |||| ||| ||||| ||||| |||||| 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

Phân loại

•  Có 2 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í khác nhau trên hai trình tự.

–  Bắt cặp toàn cục (Global alignment): được áp dụng trên toàn bộ trình tự để tìm sự tương đồng giữa các trình tự.

–  Thường được sử dụng khi 2 trình tự có độ tương đồng

–  Mục đích tìm ra vùng trình tự tương đồng nhất. –  Sử dụng khi so sánh 2 trình tự có chiều dài khác nhau, mức độ tương đồng trên toàn bộ là thấp. 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

Bắt cặp hai trình tự

Ví dụ PSA

– S1 = “ACGCTG” – S2 = “CATGT”

•  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’, S2’ bằng cách thêm các ký tự ‘-’ sao cho: –  Đ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” – S2’ = “CATG-T-”

–  Chiều dài S1’, S2’ là bằnh nhau (|S1’| = |S2’|) –  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

Bắt cặp đa trình tự

Ví dụ MSA

•  Thông thường, bắt cặp đa trình tự được sử dụng khi cần tìm kiếm một trình tự đại diện trong tập hợp nhiều trình tự sinh học.

•  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: –  Mức độ tương đồng của các trình tự này là cao nhất –  |S1’| = |S2’|= … = |Sk’| –  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

Ví dụ

•  Trong quá trình tiến hóa, một đoạn gen có thể:

•  Với đoạn trình tự “ACTCGATT” –  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

C), vị trí 6 (thay T bằng C): “AGCATC”

–  Thêm TA vào vị trí 4: “AGCTAATC”

–  đột biến –  mất đi –  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

•  Như vậy, với 2 trình tự:

– ACTCGATT – AGCTAATC

•  có thể được bắt cặp là:

•  Khi đó, ký tự “gap” vừa: –  deletion gap: mất đi –  insertion gap: thêm vào

– ACTCG--ATT – | || – 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

•  Có thể tìm tại http://www.clustal.org/clustal2/

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

Ví dụ

>Seq1 ACTCCGATT >Seq2 AGCTAATC

•  Để bắt cặp 2 trình tự, –  tạo file dạng FASTA –  chọn File/Load Sequences

•  Có hai dạng Clustal trên 3 hệ điều hành khác

là file mới tạo

–  chọn Alignment/Do

Complete Sequences

nhau: Linux, Mac OS X, Windows: –  ClustalW: thực thi ở chế độ dòng lệnh –  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

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

•  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

{

đồng giữa toàn bộ 2 trình tự (bắt cặp toàn cục – Gobal Alignment)

Mi0 = id, ∀i = 0,n, M0 j = jd, ∀j = 0,m Mij = max Mi−1,j−1 +σij ,Mi−1,j + d,Mi,j−1 + d} ∀i = 1,n; j = 1,m match

, d = gap

σij =

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

Giải thích kết quả

•  Ví dụ cho 2 trình tự

– CATGT – ACGCTG

•  Các giá trị tính toán

–  match = 2 –  mismatch = -1 –  d = -2

•  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

T T G C A A T G T C -4 -8 -10 -6 -2 0 0 -4 -6 -8 -10 -2 -1 -2 A -2 A 0 -2 -4 -6 -1 -4 C -2 -1 -3 -5 0 -4 C -6 G -2 -1 -3 1 -1 -6 G -8 C -4 -3 -2 -1 0 -8 C -10 T -5 -1 -3 1 -6 -10 T -12 G -7 -3 1 -1 -8 -12 G

T

G

C

A

C

A

T

G

T

-6

-8

-10

-2

-4

-2

-4

-6

-8

-10

-1

0

-2

A

-1

-2

A

0 -2

-4

C

-4

C

-6

G

-6

G

-8

C

-8

C

-10

T

-10

T

-12

G

-12

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

A T G T C C A T G T -4 -6 -8 -10 -2 0 -2 0 -4 -6 -8 -10 0 -2 -4 -1 -2 A -1 -2 A 0 -2 -4 -6 -4 C -4 C -6 G -6 G -8 C -8 C -10 T -10 T -12 G -12 G

A

T

G

T

C

A

T

G

T

-4

-6

-8

-10

-2

-4

-6

-8

-10

0 -2 -4 -6

-1

-2

A

-1

0 -2 -4 -6

-2

A

0

-4

C

0 -2

-4

C

-6

G

-6

G

-8

C

-8

C

-10

T

-10

T

-12

G

-12

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

C A T G T C A T G T -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 0 -1 0 -2 -4 -6 -2 A -1 0 -2 -4 -6 -2 A 0 -2 -1 -4 C 0 -2 -1 -3 -4 C -6 G -6 G -8 C -8 C -10 T -10 T -12 G -12 G

C

A

T

G

T

A

T

G

T

C

-2

-4

-6

-8

-10

-4

-6

-8

-10

-2

-1

0 -2 -4 -6

-2

A

0 -2 -4 -6

-1

-2

A

0 -2

-1

-3

-5

-4

C

-2

-1

-3

-5

0

-4

C

-6

G

-2

-6

G

-8

C

-8

C

-10

T

-10

T

-12

G

-12

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

A T G T C A T G T C -4 -6 -8 -10 -2 0 -4 -6 -8 -10 -2 0 0 -2 -4 -6 -1 -2 A 0 -2 -4 -6 -1 -2 A -2 -1 -3 -5 0 -4 C -2 -1 -3 -5 0 -4 C -2 -1 -6 G -2 -1 -3 -6 G -8 C -8 C -10 T -10 T -12 G -12 G

A

T

G

T

C

A

T

G

T

C

-4

-6

-8

-10

-2

-4

-6

-8

-10

-2

0 -2 -4 -6

-1

-2

A

0 -2 -4 -6

-1

-2

A

-2

-1

-3

-5

0

-4

C

-2

-1

-3

-5

0

-4

C

-2 -1 -3

1

-6

G

-2 -1 -3

1 -1

-6

G

-8

C

-8

C

-10

T

-10

T

-12

G

-12

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

C A T G T C A T G T -2 -4 -6 -8 -10 0 -2 -4 -6 -8 -10 0 -1 0 -2 -4 -6 -2 A -1 0 -2 -4 -6 -2 A 0 -2 -1 -3 -5 -4 C 0 -2 -1 -3 -5 -4 C -2 -1 -3 1 -1 -6 G -2 -1 -3 1 -1 -6 G -4 -8 C -4 -3 -8 C -10 T -10 T -12 G -12 G

C

A

T

G

T

C

A

T

G

T

-2

-4

-6

-8

-10

-2

-4

-6

-8

-10

-1

0 -2 -4 -6

-2

A

-1

0 -2 -4 -6

-2

A

0 -2

-1

-3

-5

-4

C

0 -2

-1

-3

-5

-4

C

-2 -1 -3

1 -1

-6

G

-2 -1 -3

1 -1

-6

G

-4 -3 -2

-8

C

-4 -3 -2

-1

-8

C

-10

T

-10

T

-12

G

-12

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

A T G T C A T G T C -4 -6 -8 -10 -2 0 -4 -6 -8 -10 -2 0 0 -2 -4 -6 -1 -2 A 0 -2 -4 -6 -1 -2 A 0 -2 -1 -3 -5 -4 C 0 -4 -2 -1 -3 -5 C -2 -1 -3 1 -1 -6 G -6 -2 -1 -3 1 -1 G -4 -3 -2 -1 0 -8 C -8 -4 -3 -2 -1 0 C -10 T -10 -6 T -12 G -12 G

A

T

G

T

C

A

T

G

T

C

-4

-6

-8

-10

-2

-4

-6

-8

-10

-2

0 -2 -4 -6

-1

-2

A

0 -2 -4 -6

-1

-2

A

0

-4

-2

-1

-3

-5

C

0

-4

-2

-1

-3

-5

C

-6

-2 -1 -3

1 -1

G

-6

-2 -1 -3

1 -1

G

-8

-4 -3 -2

-1

0 C

-8

-4 -3 -2

-1

0 C

-10

-6

-5

T

-10

-6

-5

-1

T

-12

G

-12

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

A T G T C A T G T C -4 -6 -8 -10 -2 0 -4 -6 -8 -10 -2 0 0 -2 -4 -6 -1 -2 A 0 -2 -4 -6 -1 -2 A 0 -4 -2 -1 -3 -5 C 0 -4 -2 -1 -3 -5 C -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 G -8 -4 -3 -2 0 -1 C -8 -4 -3 -2 0 -1 C -3 -10 -6 -5 -1 T 1 -3 -10 -6 -5 -1 T -12 G -12 G

A

T

G

T

C

A

T

G

T

C

-4

-6

-8

-10

-2

-4

-6

-8

-10

-2

0 -2 -4 -6

-1

-2

A

0 -2 -4 -6

-1

-2

A

0

-4

-2

-1

-3

-5

C

0

-4

-2

-1

-3

-5

C

-6

-2 -1 -3

1 -1

G

-6

-2 -1 -3

1 -1

G

-8

-4 -3 -2

0 -1

C

-8

-4 -3 -2

0 -1

C

1 -3

-10

-6

-5

-1

T

1 -3

-10

-6

-5

-1

T

-12

-8

G

-12

-8

-7

G

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

A T G T C A T G T C -4 -6 -8 -10 -2 0 -4 -6 -8 -10 -2 0 0 -2 -4 -6 -1 -2 A 0 -2 -4 -6 -1 -2 A 0 -4 -2 -1 -3 -5 C 0 -4 -2 -1 -3 -5 C -6 -2 -1 -3 1 -1 G -6 -2 -1 -3 1 -1 G -8 -4 -3 -2 -1 0 C -8 -4 -3 -2 -1 0 C -3 -10 -6 -5 -1 1 T -3 -1 -10 -6 -5 1 T -12 -8 -7 -3 G -3 1 -12 -8 -7 G

C

A

T

G

T

-2

-4

-6

-8

-10

•  Bước 2: Tìm vết dựa trên kết quả tính các giá trị của ma trận trước đó. Xuất phát từ Mnm nếu:

A

-1

-2

0 -2 -4 -6

C

0

-4

-2

-1

-3

-5

G

-6

-2 -1 -3

1 -1

C

-8

-4 -3 -2

0 -1

T

1 -3

-10

-6

-5

-1

− M i−1, j−1 = M ij −σij , theo duong chéo, (i,j) → (i-1,j-1) − M i−1, j = M ij − d , dich chuyen lên trên, (i,j) → (i-1,j) − M i , j−1 = M ij − d , dich chuyen lui, (i,j) → (i,j-1)

G

-1

1

-12

-8

-7

-3

Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY

C A T G T C A T G T -2 0 -4 -6 -8 -10 -2 0 -4 -6 -8 -10 A -1 -2 0 -2 -4 -6 -1 -2 0 -2 -4 -6 A C 0 -4 -2 -1 -3 -5 0 -4 -2 -1 -3 -5 C G -6 -2 -1 -3 1 -1 -6 -2 -1 -3 1 -1 G C -8 -4 -3 -2 0 -1 -8 -4 -3 -2 0 -1 C T 1 -3 -10 -6 -5 -1 1 -3 -10 -6 -5 -1 T G -1 1 -12 -8 -7 -3 -1 1 -12 -8 -7 -3 G

C

A

T

G

T

-2

-4

-6

-8

-10

-1

-2

0 -2 -4 -6

A

0

-4

-2

-1

-3

-5

C

•  Bước 3: Bắt cặp trình tự –  Xuất phát từ phần tử Mnm –  Nếu phần tử kế nằm trên đường chéo: hai ký tự được

-6

-2 -1 -3

1 -1

G

bắt cặp với nhau

-CA-TGT ACGCTG-

-8

-4 -3 -2

0 -1

C

–  Nếu phần tử kế nằm bên trái: thêm gap cho trình tự

1 -3

-10

-6

-5

-1

T

thứ hai (ở dưới)

-1

1

-12

-8

-7

-3

G

–  Ngược lại, nếu phần tử kế nằm ở trên: thêm gap cho

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

Xem xét ví dụ khác

•  Điểm: 3x2 + 1(-1) + 3(-2) = -1

CATG-T- -ACGCTG

•  Xét 2 trình tự peptide như sau:

–  U = AlaCysGlyCysAspGly –  V = CysAlaAspGlyAsp

•  Gồm các amino acid: Alanin (A), Cystein (C),

Glycine (G), Aspartic acid (D)

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

C A T G T -2 0 -4 -6 -8 -10 -1 -2 0 -2 -4 -6 A 0 -4 -2 -1 -3 -5 C -6 -2 -1 -3 1 -1 G -8 -4 -3 -2 0 -1 C 1 -3 -10 -6 -5 -1 T -1 1 -12 -8 -7 -3 G

•  Tạo ma trận đánh giá theo quy tắc:

•  Có thể biểu diễn –  U = “ACGCDG” –  V = “CADGD”

–  M00 = 0 –  Mi0 = Mi-1,0 + d –  M0j = M0,j-1 + d –  Mij = Max {Mi-1,j-1 + σij, Mi,j-1 + d, Mi-1,j + d} –  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

C

A

D

G

D

•  Tìm vết bằng cách dùng d = -1 và ma trận σ để

-1

-2

-3

-4

-5

-1

-2

A

-2

-1

-2

so sánh trên 2 trình tự: •  Xuất phát từ M65, nếu:

C

-3

-1

–  Mij = Mi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) đi theo đường

G

chéo

-4

-1

C

-5

-2

D

-6

-3

–  Mij = Mi,j-1 + d thì vết (i,j) → (i,j-1) đi lui –  Mij = Mi-1,j + d thì vết (i,j) → (i-1,j) đi lên

G

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 trường hợp này, có nhiều vết được tạo ra

C

A

D

G

D

C

A

D

G

D

(màu red, blue, green)

-1

-2

-3

-4

-5

-1

-2

-3

-4

-5

C

A

D

G

D

-1

-2

-1

-2

A

-1

-2

-3

-4

-5

-2

-1

-2

-1

-2

C

-1

-2

A

-3

-1

-3

-1

G

-2

-1

-2

C

-4

-1

-4

-1

C

-3

-1

G

-5

-2

-5

-2

D

-4

-1

C

-6

-3

-6

-3

G

-5

-2

D

-6

-3

G

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- -ACGCDG

•  Sử dụng kỹ thuật lưu vết theo quy tắc:

•  Vết Blue: 3(2) + 1(-1) + 3(-1) = 2

-CA-DGD ACGCDG-

–  (i,j) →(i-1,j-1): Ui và Vj được ghi vào –  (i,j) →(i-1,j): “-” và Vj được ghi và –  (i,j) →(i,j-1): Ui và “-” được ghi vào

•  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

Một ví dụ khác

G

A

T

C

A

G

T

A

-1

-2

-3

-4

-5

-6

-7

-8

-9

-10 -11

-1

-2

-3

-4

-5

-6

-7

-8

G

-2

-1

-2

-3

-4

-2

-3

-4

-5

•  Cho 2 trình tự DNA:

G

-3

-1

-2

-3

-4

-2

A

GGATCGA GAATTCAGTTA

-4

-1

-2

T

-5

-2

C

-6

-3

G

-7

-4

-1

A

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à:

GGA-TC-G--A | | || | | GAATTCAGTTA

•  Kết quả: 6(2) + 4(-1) + 1(-1) = 7

hợp tương tự, nhưng: –  M00 = 0 –  Mi0 = Mi-1,0 + d –  M0j = M0,j-1 + d –  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

TG Needleman – Wunsch nguyên thủy

for i=0 to length(U) M(i,0) ← di for j=0 to length(V) M(0,j) ← dj for i=1 to length(U)

for j=1 to length(V){

Match ← M(i-1,j-1) + σ(i,j) Delete ← M(i-1,j) + d Insert ← M(i,j-1) + d M(i,j) ← max(Match, Insert, Delete)

}

PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM

AlignmentU ← "" AlignmentV ← "" i ← length(U) j ← length(V) while (i > 0 and j > 0){ Score ← M(i,j) ScoreDiag ← M(i - 1, j - 1) ScoreUp ← M(i, j - 1) ScoreLeft ← M(i - 1, j) if (Score == ScoreDiag + σ(i,j)){ AlignmentU ← Ui + AlignmentU 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

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

while (i > 0){ AlignmentU ← Ui + AlignmentU AlignmentV ← "-" + AlignmentV i ← i - 1 } while (j > 0){ AlignmentU ← "-" + AlignmentU AlignmentV ← Vj + AlignmentV j ← j - 1 } else if (Score == ScoreLeft + d){ AlignmentU ← Ui + AlignmentU AlignmentV ← "-" + AlignmentV i ← i - 1 } otherwise (Score == ScoreUp + d){ AlignmentU ← "-" + AlignmentU AlignmentV ← Vj + AlignmentV j ← j - 1 } }

•  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 SMITH - WATERMAN

Wunsch là chỉ sử dụng để bắt cặp 2 trình tự 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

•  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

không phải bắt đầu từ giá trị cuối (Hnm), mà từ giá trị tốt nhất (điểm cao nhất của ma trận)

{

Hi0 = 0, ∀i = 0,n, H0 j = 0, ∀j = 0,m Hij = max 0,Hi−1,j−1 +σij ,Hi−1,j + d,Hi,j−1 + d} ∀i = 1,n; j = 1,m match

, d = gap

σij =

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

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:

A

C

A

G

C

A

H11 H12 H13 H21 H22 H23 H31 H32 H33 H41 H42 H43

H21 = max{0,H10 +σ21 ,H11 −1,H20 −1} = max{0,0−1,2−1,0−1} = 1 H22 = max{0,H11 +σ22 ,H12 −1,H21 −1} = max{0,2−1,1−1,2−1} = 1 H23 = max{0,H12 +σ23 ,H13 −1,H22 −1} = 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

H31 = max{0,H20 +σ31 ,H21 −1,H30 −1} = max{0,0−1,1−1,0−1} = 0 H32 = max{0,H21 +σ32 ,H22 −1,H31 −1} = max{0,1+2,1−1,0−1} = 3 H33 = max{0,H22 +σ33 ,H23 −1,H32 −1} = max{0,1−1,1−1,3−1} = 2

H41 = max{0,H30 +σ41 ,H31 −1,H40 −1} = max{0,0+2,0−1,0−1} = 2 H42 = max{0,H31 +σ42 ,H32 −1,H41 −1} = max{0,0−1,3−1,2−1} = 2 H43 = max{0,H32 +σ43 ,H33 −1,H42 −1} = 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

Tạo vết

A

C

A

•  Xuất phát từ Hnmax,mmax, nếu:

A

G

–  Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo –  Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui –  Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên

C

A

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ả

•  Nếu

A

C

A

–  (i,j) →(i-1,j-1): theo đường chéo

A

G

Ui và Vj được ghi vào –  (i,j) →(i-1,j): đi lên “-” và Vj được ghi vào

C

–  (i,j) →(i,j-1): đi lui

Ui và “-” được ghi vào

A

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 trình tự dài hơn, chẳng hạn:

U = “ATATGCTAAG” V = “ACTACTTAG”

•  Kết quả bắt cặp –  U’ = “A-CA” –  V’ = “AGCA”

•  Độ đánh giá: 3(2) + 1(-1) + 0(-1) = 5

•  Chọn d = -1, Match = 2 và Mismatch = -1 cho sự 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

Với kỹ thuật lưu vết như trên

A

T

A

T

G

C

T

A

G

A

T

A

T

G

C

T

A

G

A

C

T

A

C

T

A

6 10

G

7 10

G

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 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

•  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

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

(Progessive Algorithm)

Thuật toán 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

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

chọn.

–  Bước 2: chọn một trình tự khác rồi sắp hàng với nhóm

–  Dùng PSA cho tất cả các trình tự –  Xác định mức độ tương đồng mỗi cặp –  Xây dựng ma trận khoảng cách tương đồng giữa các

đã thực hiện.

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

•  Bước 2:

•  Bước 3: Thực hiện quá trình lũy tiến

–  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 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ặp trình tự tương đồng lớn nhất

–  Cây hướng dẫn hể hiện mối quan hệ tương đồng giữa

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

Minh họa

•  Lần lượt bắt cặp: –  S1’ = “ARDFGI” –  S2’ = “A-KHGL”

–  S1’ = “ARDFG-I” –  S4’ = “AR-FGLI”

–  S1’ = “ARDFGI--” –  S3’ = “A-DF-IKF”

–  S1’ = “ARDFGI--” –  S5’ = “AKD--ILM”

•  Xét 5 trình tự: –  S1 = “ARDFGI” –  S2 = “AKHGL” –  S3 = “ADFIKF” –  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

–  S2’ = “AKHGL-” –  S5’ = “AKDILM”

–  S2’ = “A---KHGL” –  S3’ = “ADFIK--F”

–  S3’ = “ADF--IKF” –  S4’ = “ARFGLI--”

–  S4’ = “ARFGLI” –  S5’ = “AKDILM”

–  S2’ = “AKHGL-” –  S4’ = “ARFGLI”

–  S3’ = “A-DFIKF” –  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

•  Khoảng cách D(S1’,S2’) giữa 2 trình tự bằng tỷ số

•  Ví dụ:

giữa m và n. Trong đó –  m = số mismatch giữa 2 trình tự (không tính gap) –  n = số cặp không phải là gap giữa 2 trình tự

•  Ví dụ:

–  S1’ = “ARDFGI--” –  S3’ = “A-DF-IKF”

Có m = 0, n = 4. Suy ra D(S1’,S3’) = 0/4 = 0

–  S1’ = “ARDFGI” –  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

Ma trận khoảng cách

0,60

•  Ví dụ:

0,33

–  S1’ = “ARDFGI--” –  S5’ = “AKD--ILM”

0,40

0,25

Có m = 1, n = 4. Suy ra D(S1’,S5’) = 1/4 = 0.25

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

S13

•  Theo ma trận khoảng cách, có thể S1 và S3 là nhỏ nhất, nên mức độ gần nhau là nhiều nhất.

•  Hoặc S1 và S4

0,4

(0,6+0,33)/2 = 0.465

0,6

0,66

(0+0,25)/2 = 0.125

PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM

(0,25+0,4)/2 = 0.325

S13,4

•  Tiếp tục, khoảng cách giữa S13 và S4 là nhỏ

(0,465+0,4)/2 = 0,4325

nhất.

0,6

(0,325+0,66)/2 = 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

ARDFGI

ARDFGI-- A-DF-IKF

•  Tiếp tục, còn S134 và S2 là nhỏ nhất

ARDFG-I-- A-DF--IKF AR-FGLI--

ADFIKF

S134,2

ARFGLI

ARDFG-I-- A-DF--IKF AR-FGLI-- A-KHGL---

(0,4925+0,6)/2 = 0,54625

AKHGL

ARDFG-I-- A-DF--IKF AR-FGLI-- A-KHGL--- AKD---ILM

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

•  Ở đâ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

Bài giảng Tin sinh học đại cương - Chương 3: Bắt cặp trình tự (Sequence Alignment)

Bài giảng Tin sinh học đại cương - Chương 3: Bắt cặp trình tự (Sequence Alignment) giới thiệu chung và tập trung làm rõ hiện tượng bắt cặp hai trình tự, bắt cặp nhiều trình tự. Bài giảng hữu ích với các bạn chuyên ngành Sinh học.

TIN SINH HỌC ĐẠI CƯƠNG (Introduction to Bioinformatics)

A

T

-

C

-

T

G

A

T

G

-

T

G

C

A

T

-

A

-

C

{

T

T

G

C

A

C

A

T

G

T

-1

0

A

-1

A

0 -2

C

C

G

G

C

C

T

T

G

G

A

T

G

T

C

C

A

T

G

T

0

-2 -4 -6

-1

A

-1

0

-2 -4 -6

A

0

C

0

-2

C

G

G

C

C

T

T

G