Bài giảng Tin sinh học đại cương - Chương 4: Phân tích trình tự DNA - Trần Văn Lăng

Nội dung text: Bài giảng Tin sinh học đại cương - Chương 4: Phân tích trình tự DNA - Trần Văn Lăng

1. • Hai người bắt tay vào tìm kiếm kho báu bị mất cùng với • Tuy nhiên, sau khi làm một người hầu tên là Jupiter. theo vài manh mối, họ • Người bạn nghi ngờ tính tìm thấy một kho báu bị đúng đắn trong câu chuyện chôn vùi bởi cướp biển của Legrand. khét tiếng tên là Captain Kidd • Kho báo ước tính trị giá khoảng 14.000.000 USD. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 41 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 42 The Gold Bug Problem • Trong số các manh mối đó, có thông điệp bí mật như sau: • Thông điệp bí mật 53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8! 83(88)5*!; 46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6 !8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48; (88;4(+?3 4;48)4+;161;:188;+?; • Hãy giải mã thông điệp được mã hóa này Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 43 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 44 11
2. Cách giải quyết • Các gợi ý như sau: – Thông điệp được mã hóa • Đếm tần số xuất hiện bằng tiếng Anh của mỗi ký hiệu trong – Mỗi ký hiệu tương ứng với thông điệp được mã hóa một chữ cái trong bảng chữ • Tìm tần số của mỗi ký tự cái tiếng Anh trong bảng chữ cái của – Không có dấu chấm câu văn bản tiếng Anh được mã hóa Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 45 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 46 • Tần số theo thông điệp của Gold Bug • So sánh các tần số của Symbol 8 ; 4 ) + * 5 6 ( ! 1 0 2 9 3 : ? ` - ] . các bước trước đó, cố Frequency 34 25 19 16 15 14 12 11 9 8 7 6 5 5 4 4 3 2 1 1 1 gắng tìm một mối tương quan và ánh xạ các ký • Tần số theo bảng chữ cái tiếng Anh hiệu với một ký tự trong e t a o i n s r h l d c u m f p g w y b v k x j q z bảng chữ cái Tần số cao tần số thấp Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 47 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 48 12
3. • Bằng cách ánh xạ đơn giản các ký hiệu có arhteenmrnwteonihtaesotsnlupnihtamsrn tần số cao nhất đến các ký tự có tần số cao uhsnbaoeyentacrmuesotorl nhất tương ứng trong bảng chữ cái. eoaiitdhimtaecedtepeidtaelestaoaeslsu • Giải mã 4 mãnh trong thông điệp bí mật eecrnedhimtaetheetahiwfa taeoaitdrdtpdeetiwt sfiilfcsoorntaeuroaikoaiotecrntaeleyr cooestvenpinelefheeosnlt • Kết quả không có ý nghĩa gì cả Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 49 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 50 Cách tiếp cận tốt hơn • Suy ra tương tự cho các ký hiệu chưa biết • Đánh giá tần số của l-tuples như tổ hợo trong văn bản mã hóa của 2 ký hiệu, 3 ký hiệu, v.v Chẳng hạn, dựa trên tần số của – “The” là 3-tupe có tần số cao nhất trong tiếng các l-tuple. Anh; “;48” là 3-tuple có tần số cao nhất trong thông điệp mã hóa Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 51 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 52 13
4. • Ánh xạ “the” đến “;48” và thay thế tất cả • Suy đoán 53++!305))6*the26)h+.)h+)te06*the! các ký hiệu xuất hiện: e`60))e5t]e*:+*e!e3(ee)5*!t 53++!305))6*the26)h+.)h+)te06*the! h6(tee*96*?te)*+(the5)t5*!2:*+ e`60))e5t]e*:+*e!e3(ee)5*!t (th956*2(5*h)e`e*th0692e5)t)6!e h6(tee*96*?te)*+(the5)t5*!2:*+ )h++t1(+9the0e1te:e+1the!e5th)he5! (th956*2(5*h)e`e*th0692e5)t)6!e 52ee06*e1(+9thet(eeth(+?3ht )h++t1(+9the0e1te:e+1the!e5th)he5! he)h+t161t:1eet+?t 52ee06*e1(+9thet(eeth(+?3ht • “thet(ee” most likely means “the tree” he)h+t161t:1eet+?t – Suy ra Infer “(“ = “r” Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 53 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 54 • Sau khi tìm ra tất cả các ánh xạ, thông điệp có thể giải mã như sau: • Khi đó, “th(+?3h” trở thành “thr+?3h” – Sau đó có thể đề xuất “+”, “?” được mã hóa ra sao. AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATWEN YONEDEGREESANDTHIRTEENMINUTESNORTHEASTANDBYNOR THMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHELEF TEYEOFTHEDEATHSHEADABEELINEFROMTHETREETHROUGHT HESHOTFIFTYFEETOUT Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 55 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 56 14
5. Giải bài toán Gold Bug • Sử dụng dấu chấm câu, thông điệp có thể là: A GOOD GLASS IN THE BISHOP’S HOSTEL IN THE • Những điều kiện tiên quyết để giải bài toán: DEVIL’S SEA, – Cần phải biết tần số tương đối của các chữ cái, TWENY ONE DEGREES AND THIRTEEN MINUTES và sự kết hợp của hai và ba chữ cái trong tiếng NORTHEAST AND BY NORTH, Anh MAIN BRANCH SEVENTH LIMB, EAST SIDE, SHOOT – Kiến thức về tất cả các từ trong từ điển tiếng Anh FROM THE LEFT EYE OF là mong muốn cao để có những kết luận chính ’ THE DEATH S HEAD A BEE LINE FROM THE TREE xác THROUGH THE SHOT, FIFTY FEET OUT. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 57 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 58 Sự tương tự giữa 2 bài toán • Để giải mã, cần phân tích tần số của các • Những nucleotide trong một mẫu thông điệp DNA/Gold Bug motif mã hóa là ngôn ngữ của • Kiến thức của các motif điều chỉnh được thiết di truyền, tương tự như ký hiệu lập làm cơ sở cho việc tìm motif; cũng như mã hóa trong “The Gold Bug” kiến thức về các từ trong từ điển Tiếng Anh của một thông điệp (message) làm cơ sở cho việc giải bài táon Gold Bug bằng tiếng Anh Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 59 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 60 15
6. • Motif Finding: • Bài toán Motif Finding: – Kiến thức về các motif được thiết lập làm giảm – Phân tích tần suất xuất hiện các mẫu (pattern) trong những trình độ phức tạp của bài toán tự nucleotide • Bài toán Gold Bug Problem • Gold Bug Problem: – Phân tích tần suất xuất hiện các – Kiến thức về các từ trong từ điển Tiếng Anh là mẫu trong văn bản được viết hết sức mong đợi bằng Tiếng Anh Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 61 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 62 Minh họa bài toán Motif Finding • Bài toán Motif Finding khó hơn bài toán Gold • Cho một mẫu ngẫu nhiên các trình tự DNA cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat Bug: agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc – Không có từ điển đầy đủ về motif aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt – Ngôn ngữ di truyền học không có văn phạm agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca chuẩn ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc – Chỉ một phần nhỏ trình tự nucleotide mã hóa cho • Tìm mẫu được ghép vào mỗi trình tự riêng, motif, trong khi đó kích thước dữ liệu lại rất lớn gọi là motif Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 63 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 64 16
7. • Các mẫu cho thấy không có đột biến • Thông tin thêm: cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat – Mỗi trình tự che dấu có agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc chiều dài 8 aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt – Các mẫu không hoàn toàn agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca giống nhau bởi điểm đột ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc biến là ngẫu nhiên xẩy ra trong các trình tự acgtacgt Chuỗi liên ứng (Consensus String) Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 65 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 66 • Mẫu với 2 đột biến: aGgtacTt cctgatagacgctatctggctatccaGgtacTtaggtcctctgtgcgaatctatgcgtttccaaccat CcAtacgt agtactggtgtacatttgatCcAtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc acgtTAgt aaacgtTAgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt acgtCcAt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtCcAtataca ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaCcgtacgGc CcgtacgG Mẫu với 2 đột biến • Liệu có thể tìm được motif với 2 đột biến acgtacgt Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 67 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 68 17
8. Phân loại bài toán tìm motif – Dạng đột biến: Cho trước t trình • Có 2 dạng bài toán tìm motif: tự, hãy xác định các đoạn trình – Không đột biến: Cho trước t trình tự, hãy xác định tự có chiều dài l sao cho các các đoạn trình tự có chiều dài l (l-mer) trên mỗi đoạn này gần giống nhau trên trình tự sao cho đoạn này bắt cặp giống nhau. các trình tự cho phép đột biến (sai lệch) d vị trí Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 69 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 70 Định nghĩa Motif Profiles và Consensus • Để định nghĩa một motif, cần biết vị trí bắt a G g t a c T t C c A t a c g t • Sắp hàng các mẫu theo đầu của motif trong trình tự. Alignment a c g t T A g t vị trí bắt đầu của nó a c g t C c A t • Vị trí này có thể biểu diễn bởi s = (s1,s2,s3, C c g t a c g G s = (s1, s2, , st) ,st) A 3 0 1 0 3 1 1 0 Profile C 2 4 0 0 1 4 0 0 • Xây dựng ma trận profile G 0 1 4 0 0 0 3 1 với tần suất xuất hiện của T 0 0 0 5 1 0 1 4 mỗi nucleotide theo cột Consensus A C G T A C G T • Consensus nucleotide là nucleotide có điểm cao nhất trong cột Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 71 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 72 18
9. Consensus Khoảng cách giữa các trình tự • Consensus (trình tự liên ứng) ở đây được hiểu như là một motif tổ tiên mà từ đó các motif đột biến xuất hiện Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 73 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 74 Đánh giá motif Ví dụ về các tham số • Trước hết, ta có các tham số – t - số mẫu trình tự DNA l = 8 DNA cctgatagacgctatctggctatccaGgtacTtaggtcctctgtgcgaatctatgcgtttccaaccat – n - chiều dài mỗi trình tự DNA agtactggtgtacatttgatCcAtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc – DNA –mẫu DNA (mảng t x n) aaacgtTAgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt – l - chiều dài của motif (l-mer) agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtCcAtataca – si - vị trí bắt đầu của motif trong trình tự i ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaCcgtacgGc – s=(s1, s2, st) - mảng chứa các vị trí bắt đầu của motif n = 69 s s1 = 26 s2 = 21 s3= 3 s4 = 56 s5 = 60 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 75 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 76 19
10. Tính điểm để đánh giá l a G g t a c T t C c A t a c g t • Cho s = (s1, st) và DNA : a c g t T A g t t a c g t C c A t l C c g t a c g G • Nếu các vị trí bằt đầu s=(s1, s2, st) cho score(s, DNA) = c o u n t( k , i) ___ trước, việc tìm consensus dễ dàng ngay cả ∑ max i=1 k∈{A,T,C,G } A 3 0 1 0 3 1 1 0 khi có đột biến trong các trình tự. C 2 4 0 0 1 4 0 0 – Với count(k,i) là số G 0 1 4 0 0 0 3 1 – Bởi khi đó ta có thể xây dựng ma trận profile, từ T 0 0 0 5 1 0 1 4 nucleotide thứ k ở vị trí th ứ ___ đó tìm motif (consensus) i của l-motif Consensus a c g t a c g t Score 3+4+4+5+3+4+3+4=30 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 77 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 78 Bài toán • Mục tiêu: Cho mẫu DNA, tìm tập l-mers từ các trình tự sao cho điểm consensus là cực • Nhưng, khi s không cho trước, làm thế nào đại để tìm ma trận profile tốt nhất. • Nhập: A t x n mảng các mẫu DNA, và chiều – Bài toán đặt ra: lài l của pattern muốn tìm • Xuất: Mảng t vị trí s = (s1, s2, st) mà Score(s,DNA) đạt cực đại Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 79 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 80 20
11. Thuật toán Brute Force BruteForceMotifSearch(DNA, t, n, l) • Tính score của một tổ hợp với vị trí bắt đầu s bestScoe ß 0 for s=(s ,s , . . ., s ) from (1,1 . . . 1) to • Điểm tốt nhất được xác định bởi profile tốt 1 2 t (n-l+1, . . ., n-l+1) nhất. if (Score(s,DNA) > bestScore) • Tìm Score(s,DNA) lớn nhất bằng cách thay bestScore ß score(s, DNA) đổi vị trí bắt đầu si, với i từ 1 đến n-l+1 bestMotif ß (s1,s2 , . . . , st) return bestMotif Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 81 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 82 Nhận xét Bài toán Median String • Thay đổi (n - l + 1) vị trí trong t trình tự, cần (n - l + 1)t tập hợp các vị trí bắt đầu • Đối với mỗi tập hợp vị trí bắt đầu, score được tính dựa trên l phép toán, vì vậy độ t t • Với lý do trên, nên vấn đề đặt ra là tìm một phức tạp tính toán là l x (n – l + 1) = O(ln ) thuật toán nhanh hơn để giải quyết. • Với t = 8, n = 1000, l = 10 phải thực hiện xấp xỉ 1032 tính toán. • Bài toán Motif Finding được đưa về bài toán Median String (chuỗi trung bình) Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 83 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 84 21
12. Khoảng cách Hamming • Khoảng cách Hamming: • Bài toán Median String: – dH(v,w) là số cặp nucleotide mismatch (do not – Cho mẫu t trình tự DNA tìm pattern xuất hiện match) khi sắp hàng v và w. Chẳng hạn trong tất cả t trình tự với số đột biến ít nhất – Pattern này chính là motif dH(AAAAAA,ACAAAC) = 2 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 85 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 86 Ví dụ Ví dụ • Cho v = “acgtacgt” và mẫu DNA • Cho v = “acgtacgt” và mẫu DNA dH(v, x) = 0 dH(v, x) = 1 acgtacgt acgtacgt cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat cctgatagacgctatctggctatccacgtacAtaggtcctctgtgcgaatctatgcgtttccaaccat dH( v, x) = 0 acgtacgt dH( v, x) = 0 acgtacgt agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc acgtacgt dH(v, x) = 0 acgtacgt dH(v, x) = 0 aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt aaaAgtCcgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt acgtacgt acgtacgt agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca acgtacgt acgtacgt ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtaGgtc dH(v, x) = 0 dH(v, x) = 1 dH(v, x) = 0 dH(v, x) = 2 TotalDistance(v,DNA) = 0 TotalDistance(v,DNA) = 1 + 0 + 2 + 0 + 1 = 4 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 87 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 88 22
13. Thuật toán • Với trình tự DNA thứ i, tính tất cả dH(v, x), ở đó x là l-mer với vị trí bắt đầu s • Mục tiêu: cho mẫu các trình tự DNA, tìm i chuỗi trung bình (1 < si < n – l + 1) • Tìm cực tiểu dH(v, x) của tất cả các l-mers trong • Nhập: Ma trận DNA t x n, chiều dài l của trình tự i mẫu cần tìm. • TotalDistance(v,DNA) tổng của các khoảng cách • Xuất: chuỗi v gồm l nucleotides mà Hamming tối thiểu cho trình tự DNA thứ i TotalDistance(v,DNA) đạt cực tiểu đối với tất • TotalDistance(v,DNA) = min d (v, s), ở đó s là s H cả các chuỗi có cùng chiều dài. tập hợp các vị trí bắt đầu s1, s2, st Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 89 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 90 MedianStringSearch (DNA, t, n, l) bestWord ß AAA A bestDistance ß ∞ for each l-mer s from AAA A to TTT T • Motif Finding Problem == Median String if TotalDistance(s,DNA) < bestDistance Problem bestDistanceßTotalDistance(s,DNA) – Motif Finding là bài toán cực đại, trong khi bestWord ß s Median String là bài toán cực tiểu return bestWord Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 91 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 92 23
14. Sự giống nhau a G g t a c T t C c A t a c g t Alignment a c g t T A g t Ta có: a c g t C c A t với các C c g t a c g G Scorei + TotalDistancei = t ___ cột A 3 0 1 0 3 1 1 0 Profile C 2 4 0 0 1 4 0 0 G 0 1 4 0 0 0 3 1 Suy ra: T 0 0 0 5 1 0 1 4 l x (Score + TotalDistance )= l x t ___ j j • Tuy nhiên, đây là 2 bài toán tương đương Consensus a c g t a c g t Hay Score = l x t – TotalDistance – TotalDistance đạt cực tiểu tương đương Score Score 3+4+4+5+3+4+3+4 đạt cực đại TotalDistance 2+2+2+2+2 = 10 = Mà l x t là hằng, nên vế phải đạt cực 2+1+1+0+2+1+2+1 tiểu tương đương vế trái đạt cực đại Sum 5 5 5 5 5 5 5 5 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 93 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 94 Các bước tìm motif • Tại sao lại quan tâm đến chuyện thay bài toán Motif Finding bằng Median String – Motif Finding Problem cần tính toán với tất cả các • Cho một trình tự v có chiều dài l (gọi là l-mer) tổ hợp của s. Đó là (n - l + 1)t tổ hợp. • Và cho t trình tự có chiều dài n – Median String Problem cần tính toán 4l tổ hợp • Tính các khoảng cách Hamming dH(v,x), của v. Con số này tương đối nhỏ hơn. trong đó x là l-mer có vị trí bắt đầu lần lượt từ 1 đến n-l+1 trong trình tự thứ i Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 95 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 96 24
15. • Từ đây suy ra dH(v,xi) là khoảng cách cực tiển trong các khoảng cách này của trình tự i. • Tính TotalDistance là tổng các dH(v,xi) với i từ 1 đến t. • Nhận xét: • Khi đó các xi là các motif tìm được trên cơ sở – Trong trường hợp v chưa biết trước, số lượng trình tự v cho trước. motif xi cần tìm là quá ít so với tập hợp tìm kiếm. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 97 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 98 Ký hiệu protein motif • x: được dùng để chỉ vị trí mà bất cứ amino acide nào cũng được chấp nhận • []: tại vị trí này có thể là một trong các amino acide được liệt kê • {}: tại vị trí này có thế bất kỳ amino acide nào KÝ HIỆU PROTEIN MOTIF ngoại trừ phân tử được liệt kê Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 99 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 100 25
16. • Ví dụ: • : cho biết motif nằm ở cuối trình tự protein – Là motif gồm: Alanine hoặc Cysteine - amino acide – Valine - amino acide -amino acide -Ngoại • Ví dụ: < Ax[ST](2)x(0,1)V trừ Glutamate và Valine – Motif nằm ở đầu trình tự gồm: Alanine – amino • x(2): có 2 amino acide bất kỳ acide - Serine hoặc Threonine - Serine hoặc Threonine – có amino acide hoặc không – Valine • x(0,3): có từ 0 đến 3 amino acide bất kỳ Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 101 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 102 • Ví dụ: – Với l = 10, n = 1000, t = 8 – Số mẫu l-mer cần tìm trong mổi trình tự là 1000-10+1 = 991 – Trong t trình tự có 8 x 991 = 7928 mẫu – Như vậy: chỉ tìm 8 mẫu (8 motif) trong 7928 mẫu Motif Trình tự sinh học dài Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 103 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 104 26