Bài giảng Giải thuật nâng cao: Quy hoạch động cho bài toán Sequence Alignment - TS. Ngô Quốc Việt

Chương này gồm có những nội dung chính sau: Giới thiệu tóm tắt về dự án Human Genome; bài toán sequence alignment: Các vấn đề cần giải quyết, scoring system, lập trình động cho vấn đề pairwise alignment; bài toán local sequence alignment. Mời tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Giải thuật nâng cao: Quy hoạch động cho bài toán Sequence Alignment - TS. Ngô Quốc ViệtQUY HOẠCH ĐỘNG CHO BÀI TOÁN SEQUENCE ALIGNMENT TS. NGÔ QUỐC VIỆT 2015 Nội dung• Giới thiệu tóm tắt về dự án Human Genome• Bài toán sequence alignment • Các vấn đề cần giải quyết • Scoring system • Lập trình động cho vấn đề pairwise alignment• Bài toán local sequence alignment Giải thuật nâng cao-DP-Sequence Alignment 2 Human genome project (HGP) – some milestones• 1977. Allan Maxam and Walter Gilbert at Harvard University and Frederick Sanger at the U.K. Medical Research Council (MRC) phát triển các phương pháp sequencing DNA.• 1988. NIH (National Institutes of Health) thành lập Office of Human Genome Research.• 1995. Patrick Brown of Stanford và cộng sự đăng first paper sử dụng printed glass microarray of complementary DNA (cDNA) probes• Các nhà nghiên cứu ở Whitehead và Généthon (Lander, Thomas Hudson at Whitehead) đăng physical map của human genome chứa 15,000 markers.• 1996. NIH tài trợ 6 nhóm giải quyết large-scale sequencing of the human genome.• An international consortium publicly releases the complete genome sequence of the yeast• 1998 NIH công bố dự án tìm SNP (Single Nucleotide Polymorphism)• 2001 The HGP consortium publishes its working draft in Nature (15 February), Celera publishes its draft in Science (16 February).• 2006. Sequence tất cả chromosomes finalized. Giải thuật nâng cao-DP-Sequence Alignment 3 Giới thiệu• Alignment nhằm: xác định hai hoặc nhiều chuỗi có liên quan với nhau hay không (quá trình tiến hóa).• Ví dụ: tìm được gene mới của người. Mong muốn xác định các tính chất. Khi đó, cần xác định phần tương ứng có trong chuột. Có hàng vạn gene của chuột, cần tìm cái nào tương ứng nhất với gene vừa tìm được.• Align proteins chia sẻ chức năng để xác định các chuỗi peptide có ảnh hưởng nhiều đến chức năng đó.• Align các chuỗi DNA nhằm xác định (chức năng hay tiến hóa) các gene liên quan để tìm các segments gắn liền với transcription factors. Giải thuật nâng cao-DP-Sequence Alignment 4Giới thiệu Giải thuật nâng cao-DP-Sequence Alignment 5 Giới thiệu• Alignment là nền tảng để xác định các quan hệ tiến hóa.• Ví dụ: http://www.computational-genomics.net/case_studies/sabertooth_demo_37.png Giải thuật nâng cao-DP-Sequence Alignment 6 Sequence Alignment• Trong thiết kế và/hoặc diễn dịch dữ liệu của các kỹ thuật high-throughput screening (dùng trong dược) dựa trên chuỗi. Khi đó so sánh chuỗi là cần thiết nhằm:- Để xác định microarray probes không có sequence tương tự với các gene khác.- Để match các sequence trong high-throughput sequencing data sang genome.- Để tìm motifs dựa trên ChIP-chip/ChIP-seq data. Giải thuật nâng cao-DP-Sequence Alignment 7 Sequence Alignment AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC -AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--- TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC• Định nghĩa: Cho hai chuỗi ? = ?1?2 … ??, ?= ?1?2 … ??, Alignment là gán các gap vào các vị trí 0, … , ? trong chuỗi x, và 0, … , ? trong y, sao cho align thẳng hàng các chữ trong một chuỗi với chữ hoặc gap của chuỗi kia. Giải thuật nâng cao-DP-Sequence Alignment 8Sequence Alignment: Các vấn đềKhông gian tìm kiếm lớn (số các alignments)Sequence 1: GSAQVKSequence 2: GNPKVKGSAQVK----- GSAQVK---------GNPKVK ----GNPKVKGSAQ--VK -----GSAQVK-G-NPKVK GNPKVK-----Chọn giải pháp nào?? Giải thuật nâng cao-DP-Sequence Alignment 9Tiêu chuẩn đánh giá alignmentAGGCTAGTT, AGCGAAGTTTAGGCTAGTT- 6 matches, 3 mismatches, 1 gapAGCGAAGTTTAGGCTA-GTT- 7 matches, 1 mismatch, 3 gapsAG-CGAAGTTTAGGC-TA-GTT- 7 matches, 0 mismatches, 5 gapsAG-CG-AAGTTT Giải thuật nâng cao-DP-Sequence Alignment 10 Scoring Function• Để so sánh độ tương tự giữa hai chuỗi với các thay đổi như: đột biến, chèn, xóa. Cho chuỗi AGGCCTC • Mutations AGGACTC • Insertions AGGGCCTC • Deletions AGG . CTC• Ký hiệu • Match: +m • Mismatch: -s • Gap: -d• Scoring đơn giản:Score: F=(# matches)  m-(# mismatches) s–(#gaps)  d Giải thuật nâng cao-DP-Sequence Alignment 11 Scoring Function• Độ đo: quasi-statistical model log-likelihood ratio.• Ký hiệu: • x, y là hai chuỗi, i là vị trí align. • Pxiyi: P(xi và yi đúng vị trí align) • Pxi: P(xi xuất hiện) • Pyi: P(yi xuất hiện) • M: một kiểu alignment • R: x, y là các chuỗi độc lập• Độ đo MLE ? ?, ?|? ??? ?? ??? ?? ?? ...