›
›

Tin học đại cương - Chương 4: Phân tích trình tự DNA

pdf 26 trang vanle 2880
Download
Bạn đang xem 20 trang mẫu của tài liệu "Tin học đại cương - Chương 4: Phân tích trình tự DNA", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdftin_hoc_dai_cuong_chuong_4_phan_tich_trinh_tu_dna.pdf

Nội dung text: Tin học đại cương - Chương 4: Phân tích trình tự DNA

  1. TIN SINH HỌC ĐẠI CƯƠNG (Introduction to Bioinformatics) Chương 4: PHÂN TÍCH TRÌNH TỰ DNA PGS.TS. Trần Văn Lăng Email: langtv@vast.vn Assoc. Prof. Tran Van Lang, PhD, Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 2 VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY • Chuyển đổi trình tự DNA • Dự đoán gene, tìm motif PHƯƠNG PHÁP SIXFRAME Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 3 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 4 1
  2. • DNA động thực vật được cấu thành chủ yếu từ 4 base cơ bản là A, T, G, C • Tuy nhiên, các sinh vật không giống nhau nên sự hình thành amino acid cũng không • Chúng có khả năng tạo nên 64 codon (mỗi giống nhau. codon gồm 3 base), • Có những loài với codon này thì tạo nên • Được gói gọn thành 20 amino acid. amino acid này nhưng đối với loài khác thì lại • Các amino acid này lại góp phần hình thành là một acid amin khác. nên các protein đặc trưng. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 5 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 6 Chẳng hạn Dịch mã sang Protein • Bộ ba (codon) “CTT” ở động vật có xương • Tiến trình chuyển đổi DNA sang protein cũng sống hình thành nên Leucine thì ở nấm men có sự khác biệt. là Threonine. • Bởi không thể biết chính xác trình tự DNA • Do đó, có nhiều bảng dịch mã khác nhau đưa vào có base bắt đầu chính là base đầu cho từng loài, từng trường hợp khác nhau tiên trong một codon hay không Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 7 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 8 2
  3. Six-Frame Translation • Hơn nữa, đầu 3’ của • Dùng phương pháp Six-Frame với 3 dịch DNA không rõ là phía chuyển, ký hiệu +1, +2 và +3. nào. • Ngoài ra, DNA tồn tại dạng chuỗi xoắn kép • Nên có 6 trường hợp cho theo từng cặp A-T, C-G. cả 2 trình tự xoắn với nhau. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 9 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 10 Ví dụ Translation in forward direction • Với chuỗi xoắn kép của DNA • Theo hướng: 3’ GGTCTAT 5’ 3’ GGTCTAT 5’ – frame +1, có 2 codon: GGT CTA: GlyLeu 5’ CCAGATA 3’ – frame +2 có 2 codon: GTC TAT: ValTyr • Khi đó có các trường hợp xãy – frame +3 có 1 codon: TCT: Ser ra như sau: Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 11 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 12 3
  4. Sử dụng phần mềm • Theo hướng 3’ ATAGACC 5’ – frame -1, có 2 codon: ATA GAC: IleAsp – frame -2, có 2 codon: TAG ACC: Am*Thr – frame -3, có 1 codon: AGA: Arg Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 13 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 14 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 15 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 16 4
  5. • Motif là một đoạn trình tự nucleotide hay amino acid phổ biến và có (hoặc cho là có) một chức năng sinh học nào đó • Đối với protein, motif được phân thành 2 loại: – Motif trình tự TÌM MOTIF – Motif cấu trúc Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 17 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 18 • Motif trình tự: sequence motif, motif, pattern, conserved pattern, consensus pattern, • Bản thân nó đại diện cho chức năng, cấu signature, fingerprint, block, feature. trúc hoặc thành viên trong họ. • Là một vùng trình tự bảo tồn hay là một đoạn • Các motif có thể được tìm thấy ở DNA, RNA, trình tự đặc trưng được tìm thấy ở 2 hay và Protein. nhiều trình tự. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 19 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 20 5
  6. • Motif cấu trúc (structural motif) là một nhóm cấu • Ví dụ: xoắn – vòng - xoắn trúc gần kề nhau kết hợp • Còn được gọi là siêu cấu trúc bậc 2 lại tạo thành một cấu trúc (supersecondary structure) 3D chuyên biệt • Lưu ý, với protein, motif trình tự (sequence motif) và mô tif cấu trúc là khác nhau hoàn toàn. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 21 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 22 • Có một mẫu trình tự nucleotide ngẫu nhiên atgaccgggatactgataccgtatttggcctaggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatactgggcataaggtaca • Ứng dụng, chẳng hạn tgagtatccctgggatgacttttgggaacactatagtgctctcccgatttttgaatatgtaggatcattcgccagggtccga – Ghép mẫu motif vào trong trình tự. gctgagaattggatgaccttgtaagtgttttccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatggcccacttagtccacttatag – Sau đó tìm nợi đã cấy ghép gtcaatcatgttcttgtgaatggatttttaactgagggcatagaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtactgatggaaactttcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttggtttcgaaaatgctctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatttcaacgtatgccgaaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttctgggtactgatagca Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 23 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 24 6
  7. • Ghép motif trình tự AAAAAAAAGGGGGGG vào • Vấn đề đặt ra là motif được ghép nằm ở đâu atgaccgggatactgatAAAAAAAAGGGGGGGggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg atgaccgggatactgataaaaaaaagggggggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaataAAAAAAAAGGGGGGGa acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaataaaaaaaaaggggggga tgagtatccctgggatgacttAAAAAAAAGGGGGGGtgctctcccgatttttgaatatgtaggatcattcgccagggtccga tgagtatccctgggatgacttaaaaaaaagggggggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgAAAAAAAAGGGGGGGtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga gctgagaattggatgaaaaaaaagggggggtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatAAAAAAAAGGGGGGGcttatag tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaataaaaaaaagggggggcttatag gtcaatcatgttcttgtgaatggatttAAAAAAAAGGGGGGGgaccgcttggcgcacccaaattcagtgtgggcgagcgcaa gtcaatcatgttcttgtgaatggatttaaaaaaaaggggggggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtAAAAAAAAGGGGGGGcaattatgagagagctaatctatcgcgtgcgtgttcat cggttttggcccttgttagaggcccccgtaaaaaaaagggggggcaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttAAAAAAAAGGGGGGGctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta aacttgagttaaaaaaaagggggggctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatAAAAAAAAGGGGGGGaccgaaagggaag ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcataaaaaaaagggggggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttAAAAAAAAGGGGGGGa ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttaaaaaaaaggggggga Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 25 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 26 • Và rồi, giả sử có 4 đột biến trong motif đã • Motif ở đâu trong trình tự này cấy ghép AAAAAAAAGGGGGGG. atgaccgggatactgatAgAAgAAAGGttGGGggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg atgaccgggatactgatagaagaaaggttgggggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacAAtAAAAcGGcGGGa acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacaataaaacggcggga tgagtatccctgggatgacttAAAAtAAtGGaGtGGtgctctcccgatttttgaatatgtaggatcattcgccagggtccga tgagtatccctgggatgacttaaaataatggagtggtgctctcccgatttttgaatatgtaggatcattcgccagggtccga gctgagaattggatgcAAAAAAAGGGattGtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga gctgagaattggatgcaaaaaaagggattgtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatAtAAtAAAGGaaGGGcttatag tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatataataaaggaagggcttatag gtcaatcatgttcttgtgaatggatttAAcAAtAAGGGctGGgaccgcttggcgcacccaaattcagtgtgggcgagcgcaa gtcaatcatgttcttgtgaatggatttaacaataagggctgggaccgcttggcgcacccaaattcagtgtgggcgagcgcaa cggttttggcccttgttagaggcccccgtAtAAAcAAGGaGGGccaattatgagagagctaatctatcgcgtgcgtgttcat cggttttggcccttgttagaggcccccgtataaacaaggagggccaattatgagagagctaatctatcgcgtgcgtgttcat aacttgagttAAAAAAtAGGGaGccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta aacttgagttaaaaaatagggagccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatActAAAAAGGaGcGGaccgaaagggaag ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatactaaaaaggagcggaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttActAAAAAGGaGcGGa ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttactaaaaaggagcgga Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 27 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 28 7
  8. Biểu tượng motif (motif logo) • Tại sao tìm motif (15,4) này lại khó TGGGGGA • Motif có thể đột biến trên TGAGAGA atgaccgggatactgatAgAAgAAAGGttGGGggcgtacacattagataaacgtatgaagtacgttagactcggcgccgccg những base không quan TGGGGGA acccctattttttgagcagatttagtgacctggaaaaaaaatttgagtacaaaacttttccgaatacAAtAAAAcGGcGGGa trọng. TGAGAGA tgagtatccctgggatgacttAAAAtAAtGGaGtGGtgctctcccgatttttgaatatgtaggatcattcgccagggtccga • Năm motif trong 5 gen TGAGGGA gctgagaattggatgcAAAAAAAGGGattGtccacgcaatcgcgaaccaacgcggacccaaaggcaagaccgataaaggaga khác nhau có đột biến ở tcccttttgcggtaatgtgccgggaggctggttacgtagggaagccctaacggacttaatAtAAtAAAGGaaGGGcttatag vị trí thứ 3 và 5 như hình. gtcaatcatgttcttgtgaatggatttAAcAAtAAGGGctGGgaccgcttggcgcacccaaattcagtgtgggcgagcgcaa • Motif logo minh họa vùng cggttttggcccttgttagaggcccccgtAtAAAcAAGGaGGGccaattatgagagagctaatctatcgcgtgcgtgttcat bảo tồn và vùng thay đổi aacttgagttAAAAAAtAGGGaGccctggggcacatacaagaggagtcttccttatcagttaatgctgtatgacactatgta của một motif ttggcccattggctaaaagcccaacttgacaaatggaagatagaatccttgcatActAAAAAGGaGcGGaccgaaagggaag ctggtgagcaacgacagattcttacgtgcattagctcgcttccggggatctaatagcacgaagcttActAAAAAGGaGcGGa AgAAgAAAGGttGGG | |||.| ||| cAAtAAAAcGGcGGG 29 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 30 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 31 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 32 8
  9. Việc định danh motif Sự phức tạp trong việc định danh motif • Không biết được trình tự motif • Ta biết gen được bật tắt bởi protein điều • Không biết nó nằm ở đâu so với gen bắt đầu chỉnh (regulator protein) • Các motif có thể khác nhau đôi chút từ gen • Các protein điều chỉnh này liên kết với trình này đến gen kế tiếp, vì vậy làm sao có thể tự DNA ngắn gọi là motif phân biệt được nó từ các motif ngẫu nhiên • Vì vậy việc tìm các motif tương tự nhau trong nhiều vùng điều chỉnh gen cho ra một quan hệ điều chỉnh trong số những gen này. Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 33 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 34 • Edgar Allan Poe là một tác giả người Mỹ, được xem như người đã tạo ra thể loại văn học trinh thám. • Bài toán tìm motif (Motif – Bản thảo tìm thấy trong chai (Ms. Finding Problem) tương tự như Found in a Bottle) bài toán được đặt ra bởi Edgar – Những câu chuyện nghịch dị và Allan Poe (1809 – 1849) trong kỳ lạ (Tales of the Grotesque and quyển truyện Gold Bug Arabesque) Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 35 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 36 9
  10. – Tụt xuống xoáy nước Maelstrom – Sự sụp đổ của ngôi nhà dòng họ (A Descent into the Maelstrom) Usher (The Fall of the House of – Bọ rầy vàng óng ánh (The Gold Usher) Bug), – Nàng Legiea (Legiea), – Lá thư bị đánh cắp (The – Mặt nạ tử thần đỏ (The Masque of Purloined Letter), the Red Death) – Án mạng trên phố Morgue (Murders in the Rue Morgue) Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 37 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 38 Truyện Gold Bug • "Gold Bug" là câu chuyện về một người đàn – Điều bí ẩn về Marie Rogers (The Mystery of Marie Rogers) ông tên là William Legrand, người dường như bị điên sau khi bị cắn bởi một con bọ được – Trái tim vạch tội (Tell-tale Heart) làm bằng vàng nguyên chất. – Người đàn ông được phẫu thuật triệt để (The Man that Was Used • Legrand nói người bạn thân nhất của mình, Up) đến thăm tại nhà của ông trên đảo Sullivan ở – Sự thật về trường hợp của South Carolina. Valderma (The Facts of M. Valdermar’s Case) Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 39 Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 40 10
  11. • 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
  12. 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
  13. • 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
  14. • Á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
  15. 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
  16. • 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
  17. • 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. • 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
  26. • 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