Tài liệu Luận văn cntt nghiên cứu thuật toán tìm kiếm chuỗi dna sử dụng phƣơng pháp tìm kiếm tƣơng tự nhanh luận

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN HOÀNG ANH NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN 1 HÀ NỘI – 2016 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN HOÀNG ANH NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 01 04 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: Tiến sĩ Nguyễn Thị Hậu 2 HÀ NỘI – 2016 LỜI CAM ĐOAN Tôi xin cam đoan nội dung của luận văn “Nghiên cứu thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tương tự nhanh” là sản phẩm do tôi thực hiện dưới sự hướng dẫn của TS. Nguyễn Thị Hậu. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 20 tháng 9 năm 2016 TÁC GIẢ Nguyễn Hoàng Anh 3 LỜI CẢM ƠN Trước tiên tôi xin gửi lời cảm ơn chân thành tới tập thể các các thầy cô giáo trong Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã giúp đỡ tận tình và chu đáo để tôi có môi trường tốt học tập và nghiên cứu. Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Thị Hậu, người trực tiếp đã hướng dẫn, chỉ bảo tôi tận tình trong suốt quá trình nghiên cứu và hoàn thiện luận văn này. Một lần nữa tôi xin được gửi lời cảm ơn đến tất cả các thầy cô giáo, bạn bè và gia đình đã giúp đỡ tôi trong thời gian vừa qua. Tôi xin kính chúc các thầy cô giáo, các anh chị và các bạn mạnh khỏe và hạnh phúc. Hà Nội, ngày 20 tháng 9 năm 2016 TÁC GIẢ Nguyễn Hoàng Anh 4 MỤC LỤC LỜI CAM ĐOAN .....................................................................................................3 LỜI CẢM ƠN ...........................................................................................................4 DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT .......................................................7 GIỚI THIỆU ............................................................................................................8 CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA .........................................................................................................................13 1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn ............ 13 1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ....................................................... 15 1.3. Phƣơng pháp tìm kiếm tƣơng tự nhanh ...................................................... 21 1.4. Phƣơng pháp sử dụng mô hình phù hợp gần đúng .................................... 25 1.5. Phƣơng pháp sử dụng mô hình kết hợp chính xác và gần chính xác........ 31 CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM. ......................................................................35 2.1. Mô hình N-Gram ............................................................................................ 35 2.1.1. Một số khái niệm ...................................................................................................... 35 2.1.2. Mô hình ngôn ngữ N-gram ....................................................................................... 36 2.1.3. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ............................................... 37 2.1.4. Các phương pháp khắc phục cụm N-Gram phân bố không đều ............................... 38 2.2. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA. .... 39 2.2.1. Phân đoạn DNA ........................................................................................................ 39 2.2.2. Các “từ DNA” ........................................................................................................... 40 2.2.3. Quá trình tìm kiếm chuỗi và hiển thị kết quả............................................................ 40 2.3. Bảng kết quả các lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram ............................................................................................................ 48 2.3.1. Định dạng chuỗi cơ sở dữ liệu .................................................................................. 48 5 2.3.2. Bảng kết quả các lần thử phương pháp tìm kiếm chuỗi tương tự nhanh áp dụng NGram ................................................................................................................................... 50 2.4. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram51 2.4.1. Cải thiện thời gian tìm kiếm ..................................................................................... 51 2.4.2. Tiết kiệm bộ nhớ trong quá trình tìm kiếm .............................................................. 52 CHƢƠNG 3. THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁP BLAST VÀ PHƢƠNG PHÁP SMITH-WATERMAN.....................................................53 3.1. Môi trƣờng thực nghiệm................................................................................... 54 3.2. Thực nghiệm đánh giá phƣơng pháp tìm kiếm tƣơng tự nhanh áp dụng N-Gram với phƣơng pháp BLAST và phƣơng pháp Smith-Water Man ........................... 56 3.3. Phân tích và đánh giá kết quả thực nghiệm ................................................... 58 KẾT LUẬN .............................................................................................................60 TÀI LIỆU THAM KHẢO .....................................................................................62 6 DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu DNA Tiếng Anh Deoxy Ribonucleic Acid NST A T G C SNP Chromosome Adenine Thymine Guanine Cytosine Single nucleotide polymorphisms CPU RAM NCBI Cental Processing Unit Random access memory National Center for Biotechnology Information Differential Direct coding HMM BLAST Hidden Markov Modeling Basic Local Alignment Search Tool High – Throughput Sequencing HTS 7 Tiếng Việt Phân tử mang cấu trúc gen di truyền Nhiễm sắc thể Tính đa hình của phân tử nucleotit. Mỗi SNP biểu diễn một biến đổi trong một khối chuỗi DNA Bộ xử lý trung tâm Bộ nhớ truy cập ngẫu nhiên Trung tâm quốc gia thông tin công nghệ sinh Mã hóa trực tiếp phần khác biệt Mô hình Markov ẩn Công cụ tìm kiếm cục bộ theo mẫu có sẵn Trình tự chuỗi đa lượng GIỚI THIỆU Việc phát hiện ra DNA là một bước ngoặt lớn trong khoa học sinh học nói riêng và cuộc sống của con người nói chung. Hiện nay, các nhà khoa học đã tìm ra rất nhiều cấu trúc DNA và giải thích được nhiều câu hỏi về di truyền ở các loài, các căn bệnh, dị tật di truyền, khoa học hình sự,… và ngày càng phát hiện thêm rất nhiều cấu trúc DNA mới, điều đó đã và đang tạo ra một khối lượng khổng lồ dữ liệu các chuỗi gen phục vụ cho y sinh học hiện đại. Kích thước dữ liệu ngày càng tăng đặt ra vấn đề về chi phí cho không gian lưu trữ và tốc độ truy cập, truyền tải. DNA (DeoxyriboNucleic Acid) là tên hóa học chỉ các phân tử mang cấu trúc gen trong tất cả các thực thể sống. DNA gồm một chuỗi được tạo nên từ 4 loại đơn vị nucleotide, mỗi loại gồm: 1 đơn vị đường carbon 5 (2’-deoxyribose), 1 nhóm phốt phát (phosphate) và 1 trong 4 thành phần cơ bản Adenine, Cystosine, Guanine và Thymine gọi là các bazơ. Mỗi phân tử đường được gắn với ¼ thành phần cơ bản. Mỗi thành phần cơ bản là 1 base. Số lượng base ở người là khoảng 3 tỷ, đó là con số vô cùng lớn. Dạng đơn giản nhất của DNA trong 1 tế bào là 1 cấu trúc dây xoắn đôi, trong đó 2 sợi DNA đơn xoắn quanh nhau theo hình xoắn ốc thuận tay phải. Bộ gen của con người gồm khoảng 3 tỉ đặc trưng trên 23 cặp nhiễm sắc thể (NST). Do đó, cơ sở dữ liệu hệ gen là vô cùng lớn và phức tạp. Để lưu trữ, truy cập và xử lý dữ liệu này một cách hiệu quả là một nhiệm vụ rất khó khăn. DNA có chức năng chính là lưu trữ, bảo quản và truyền đạt thông tin di truyền về cấu trúc và toàn bộ các loại protein của cơ thể sinh vật, do đó quy định các tính trạng của cơ thể sinh vật. DNA có chức năng chính là lưu giữ truyền đạt và bảo quản thông tin di truyền giữa các thế hệ. Có rất nhiều ứng dụng từ việc tìm kiếm chuỗi DNA cả trong khoa học và đời sống con người, chẳng hạn như:  Sự di truyền trí thông minh: Các nhà khoa học tiến hành lấy mẫu (có thể lấy là tế bào máu, niêm mạc miệng, tế bào má, tóc có chân, móng tay, móng chân, cuống rốn sau khi rụng...) và nghiên cứu chuỗi gen của những người có chỉ số thông minh cao, sau đó tìm ra những đặc điểm chung. Tiến hành nghiên cứu trên tập lớn các mẫu để xác định các chuỗi gen quyết định trí thông minh. Từ đó có thể ứng dụng vào sinh học, y học cho con người. Qua nghiên cứu cụ thể, các nhà khoa học nhận thấy rằng, 75% trí thông minh của con người do gen quyết định. [1] 8  Kiểm tra quan hệ cùng huyết thống: Phương pháp này hiện nay được ứng dụng phổ biến trong đời sống thường được gọi là xét nghiệm DNA. Xét nghiệm DNA là một lĩnh vực đòi hỏi độ chính xác cao. Mỗi kết quả của một xét nghiệm DNA huyết thống có thay đổi cuộc sống của một hoặc nhiều người, do vậy cần phải đảm bảo việc xét nghiệm được thực hiện chính xác nhất có thể. Tất cả các quá trình tư thu mẫu, tách chiết DNA, phân tích DNA và đọc kết quả đều được làm và kiểm soát theo một quy trình chuẩn, từ đó các kết quả có độ chính xác và ổn định cao nhất. Thông thường, có thể lấy hai mẫu xét nghiệm của hai người (hoặc sinh vật khác) từ tóc, tế bào trên da, mẫu máu… Sau đó xét nghiệm các chuỗi gen xem có độ tương đồng cao hay không. Thông thường nếu các mẫu DNA của mẹ, con và bố nghi vấn khớp với nhau trong từng gene thì độ chính xác có quan hệ huyết thống là 99.9999% có thể kết luận hai mẫu gen có cùng huyết thống [2].  Phát hiện các loại gen gây bệnh: Bác sỹ lấy mẫu máu từ các bệnh nhân bị bệnh, tìm kiếm các bắt cặp trình tự có độ tương đồng cao. Sau đó, so sánh các bắt cặp trình tự cao đó với mẫu gen của người bình thường để xem các điểm khác nhau của các mẫu gen đó. Từ đó đưa ra kết luận về các mẫu gen có thể gây bệnh. Tập hợp các mẫu gen có thể gây bệnh đưa vào cơ sở dữ liệu để làm mẫu gen thử cho các lần nghiên cứu sau.  Khoa học hình sự: Các điều tra viên lấy các mẫu (tóc, máu, da…), dấu vết tại hiện trường. Sau đó, mang đi giám định. Tiếp theo, tiến hành so sánh với cơ sở dữ liệu chuỗi DNA đã lưu. Từ đó có thể biết được những ai đã có mặt tại hiện trường vào thời điểm xảy ra vụ việc. Tiến hành lấy lời khai các nhân chứng. Căn cứ vào đó có thể kết luận được hung thủ, thời gian, quá trình xảy ra vụ án. ADN thường được sử dụng để xác định tội phạm theo một trong hai cách. Trường hợp nghi ngờ: Một mẫu DNA của người đó được so sánh với bằng chứng từ hiện trường vụ án. Kết quả của sự so sánh này có thể giúp xác định liệu các nghi can phạm tội. Trường hợp nghi ngờ chưa được xác định, bằng chứng sinh học từ hiện trường vụ án có thể được phân tích và so sánh với hồ sơ phạm tội trong cơ sở dữ liệu ADN để giúp xác định thủ phạm. bằng chứng hiện trường vụ án cũng có thể được liên kết với những cảnh tội phạm khác thông qua việc sử dụng các cơ sở dữ liệu ADN. Hiện nay, với trình đô khoa học phát triển, các lớp đào tạo điều tra viên được mở, giúp các học viên tiếp cận công nghệ mới một cách nhanh chóng. Có dự án kêu gọi được nhiều nguồn tài chính lên tới 5 triệu đô la Mỹ [3]. 9  Lý thuyết tiến hóa: Các nhà sinh vật tiến hành lẫy mẫu gen từ các sinh vật hóa thạch. So sánh với mẫu gen của các loài có hình thù, độ lớn, màu sắc, các sinh vật nghi ngờ cùng loài… Nếu các mẫu gen của các loài đó giống nhau hoặc có mức độ tương đồng cao có thể kết luận các sinh vật đó cùng loài hoặc tiến hóa từ mức thấp lên mức cao hơn [4].  ……………………………….. Đặc trưng phức tạp của một chuỗi DNA nằm ở chỗ đó là một chuỗi các chỉ số độ dài khác nhau biểu diễn một phạm vi có thể dự đoán được của các thành phần cơ bản cấu tạo nên DNA. Những đặc trưng phức tạp này cho phép tìm kiếm những cấu trúc lặp bên trong một nhiễm sắc thể hoặc qua nhiều nhiễm sắc thể. Và cũng chính những đặc trưng này được sử dụng để tìm ra khoảng cách tiến hóa và cấu trúc nên cây phát sinh loài. Nên khó có thể đưa ra 1 thuật toán tối ưu để tìm kiếm, giải trình tự các đoạn DNA hiệu quả nhất. Nhiều thuật toán tìm kiếm dành riêng cho chuỗi DNA đã được phát triển từ khoảng 30 năm trước. Hiện nay, kỹ thuật tìm kiếm dữ liệu chuỗi DNA được sử dụng rộng rãi trong sinh học. Có hàng trăm thuật toán đã được đề xuất cho tìm kiếm dữ liệu DNA nhưng nhìn chung các thuật toán tìm kiếm thường được sử dụng là:  Phương pháp áp dụng Mô hình Markov ẩn[5] là phương pháp sử dụng mô hình thống kê, tính toán xác suất. Thuật toán dùng phương pháp mô hình hóa quá trình tìm kiếm chuỗi trong đó có sử dụng các tham số quan sát được và các tham số không biết trước – mô hình Markov. Sau đó sẽ xác định các tham số không biết trước từ các tham số quan sát được. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Phương pháp này đã được sử dụng rộng rãi trong tin sinh học tuy nhiên chi phí thời gian lớn và các hàm tính toán phức tạp.  Phương pháp liên kết nhạy cảm đầy đủ: Vd: thuật toán Smith&Waterman[6] Phương pháp này được sử dụng để tìm sự giống nhau hoặc có độ tương đồng cao của hai chuỗi. Bằng cách lập ma trận, tính độ đo để tìm ra sự giống hoặc có độ tương đồng cao của tất cả độ dài các phân đoạn của hai xâu, hai chuỗi protein hoặc nucleotide. Với chuỗi đã được tìm kiếm và có độ tương đồng cao trước đó, phương pháp có thể mở rộng phạm vi tìm kiếm về hai phía (trước hoặc sau). Phương pháp này có ưu điểm là độ chính xác cao. Tuy nhiên chi phí thời gian lớn. Phương pháp 10 đặc trưng của dạng này là phương pháp Smith & Waterman do hai nhà khoa học T.F.Smith & M.S.Waterman công bố năm 1981. [6]  Phương pháp tìm kiếm tương tự nhanh: Vd: BLAST [7] gần giống với phương pháp liên kết nhạy cảm đầy đủ, thậm chí vẫn có thể sử dụng khi có những giải pháp tốt hơn do chỉ việc phải so sánh chuỗi cần truy vấn với thư viện hoặc CSDL chuỗi có sẵn. Sau đó, đối sánh chuỗi ở thư viện hoặc cơ sở dữ liệu với chuỗi truy vấn theo một ngưỡng nhất định. Mặc dù có thời gian xử lý nhanh hơn nhưng phương pháp này có độ chính xác không bằng phương pháp liên kết nhạy cảm đầy đủ.  Phương pháp sử dụng mô hình phù hợp gần đúng: Vd: Bowtie[8] (là kỹ thuật tìm kiếm chuỗi phù hợp với một mô hình gần đúng (chứ không phải là chính xác). Vấn đề phù hợp được hiểu thành hai ý: tìm kiếm chuỗi phù hợp gần đúng với các phân đoạn một chuỗi cho trước và tìm kiếm chuỗi từ điển gần đúng với mẫu cần truy vấn. Mô hình này sử dụng cách tiếp cận brute-force để tính “độ chỉnh sửa” chuỗi mẫu sao cho gần đúng với tất cả các chuỗi con của chuỗi cần truy vấn, sau đó chọn các chuỗi với “độ chỉnh sửa” tối thiểu. Tuy nhiên, thuật toán này sẽ có thời gian chạy O(n3m). Ở đây m là độ dài chuỗi mẫu, n là độ dài chuỗi cần truy vấn.)  Phương pháp sử dụng mô hình kết hợp chính xác và gần chính xác: Vd: mpscan[9]. Phương pháp sử dụng mô hình đánh dấu tập mẫu, tức là chia chuỗi cần truy vấn thành các chuỗi mẫu con nhỏ với chiều dài cố định. Sau đó, so sánh các chuỗi con đã được chia đó với chuỗi trong cơ sở dữ liệu để tìm kiếm sự tương đồng, có thể thực hiện xử lý đồng thời nhiều mẫu. Phương pháp này thường được dùng và rất có hiệu quả trong việc tìm kiếm một tập lớn các chuỗi DNA ngắn trong một CSDL các chuỗi DNA. Phương pháp điển hình của dạng này là Mpscan. Chương trình của Mpscancó thể đọc được bản đồ ngay trên giao diện. Có khả năng tìm kiếm ngược, bổ sung mẫu. Tuy nhiên, thời gian thực hiện ở mức độ trung bình). Là công cụ đánh dấu tập mẫu đạt hiệu quả chính xác cao cho việc giải trình tự DNA. Trong khuôn khổ luận văn, người viết chỉ trình bày một số thuật toán tiêu biểu cho từng phương pháp đã nêu và hầu hết các phương pháp đều nhằm các mục đích chính đó là tìm kiếm, giải trình tự chuỗi DNA nhanh và chính xác nhất có thể để tiết kiệm không gian lưu trữ, bộ nhớ, đưa ra kết quả cũng như truy cập thông tin 11 nhanh chóng. Trong khuôn khổ bài viết này, người viết chỉ nêu một số phương pháp tìm kiếm cơ bản và đưa ra phương pháp tìm kiếm mới với mong muốn cải thiện tốc độ tìm kiếm một chuỗi DNA trong một cơ sở dữ liệu chuỗi có sẵn. Bố cục luận văn được chia thành 3 chương. Chương 1 trình bày về tổng quan các phương pháp sử dụng để tìm kiếm chuỗi DNA. Thuật toán tìm kiếm cụ thể mà người viết tập trung nghiên cứu là thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram được trình bày ở chương 2. Chương 3 của luận văn mô tả môi trường thực nghiệm so sánh thuật toán tương tự nhanh áp dụng N-gram với phương pháp tìm kiếm khác và một số phân tích đánh giá của người viết về kết quả đạt được. Cuối cùng là kết luận về hiệu quả cũng như hạn chế còn tồn tại và hướng phát triển trong tương lai cho việc nghiên cứu và cải tiến phương pháp tìm kiếm chuỗi DNA. 12 CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA Ở phầ n trước, người viết đã giới thiệu sơ lược về cấu trúc DNA, các ứng dụng của DNA trong đời sống. Khái quát, một số phương pháp thường được sử dụng để tìm kiếm chuỗi DNA. Chương này, người viết sẽ trình bày cụ thể hơn về các thuật toán tìm kiếm chuỗi: Đặc trưng chung của các dạng tìm kiếm, các phương pháp nổi bật của từng dạng, ưu điểm, nhược điểm của các dạng tìm kiếm chuỗi. 1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn Mô hình Markov ẩn được bắt đầu xây dựng và công bố từ những năm 1960, đây là mô hình toán học về thống kê, tính toán xác suất. Nhiều năm sau đó (1980) mô hình được bắt đầu được nghiên cứu để ứng dụng trong lĩnh vực nhận dạng. Thuật toán tìm kiếm chuỗi sử dụng mô hình Markov ẩn dùng phương pháp mô hình hóa quá trình tìm kiếm chuỗi trong đó có sử dụng các tham số quan sát được và các tham số không biết trước – mô hình Markov. Sau đó sẽ xác định các tham số không biết trước từ các tham số quan sát được. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Với mô hình Markov ẩn cấu trúc mô hình có thể thay đổi dễ dàng cho phù hợp với từng ứng dụng cụ thể. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn Thuật toán: Cho 2 chuỗi: Chuỗi quan sát: x = x1x2 ... xL. Chuỗi so sánh: y = y1y2 ... yL, (ở mỗi vị trí xn thì có tương ứng yn ). Xn là số vị trí của giá trị có thể từ tập quan sát O = {O1O2,...,ON} Yn nhận giá trị từ tập trạng thái S = {1,2,...,M}. N và M biểu thị vị trí quan sát và số lượng các trạng thái trong mô hình. Cho chuỗi trạng thái ẩn xuất hiện đồng thời trong chuỗi Markov. Điều này có nghĩa là trạng thái đầu vào j sau sẽ phụ thuộc vào trạng thái i trước đó. Trạng thái này có thể sẽ không đổi. P{yn+1=j|yn=i, yn −1=in−1,...,y1=i1}=P{yn+1=j| yn =i}=t(i,j) với mọi i, j ∈ S và n≥1 [5] 13 Các trạng thái chuyển từ trạng thái i sang trạng thái j gọi là trạng thái chuyển tiếp. Gọi hàm chuyển tiếp là t(i,j). Trạng thái bắt đầu Y1 có thể ở bất kỳ i ∈ S. Ở vị trí quan sát xn=x có thể chỉ phụ thuộc vào trạng thái yn. Do vậy: P{xn=x|yn=i,yn−1,xn−1,...}=P{xn=x|yn=i}=e(x|i) [5] Với mọi x ∈ O, mọi i ∈ S, và mọi n ≥ 1; e(x|i) là hàm giá trị x tạo ra tại trạng thái i. Ba độ đo: t(i, j), π(i), and e(x | i) là 3 tham số mô tả cho mô hình HMM. Gọi tập 3 tham số này là Θ. Dựa vào 3 tham số trên, ta có thể tính được chuỗi quan sát x = x1 x2 ... xL sẽ sinh ra chuỗi y = y1 y2 ... yL. P{x,y |Θ}=P{x|y,Θ}P{y|Θ}, [5] Với P{x|y,Θ}=e(x1|y1)e(x2|y2)e(x3|y3)...e(xL|yL) P{y|Θ}=π(y1)t(y1,y2)t(y2,y3)...t(yL−1,yL). Như vậy dựa vào mô hinh khi biết chuỗi trạng tháivà đầu vào ta có thể biết được chuỗi quan sát. Ví dụ minh họa cho mô hình Markov ẩn: Hình 1.1: Mô hình Markov ẩn [5] a. Sắp xếp các chuỗi ban đầu. 14 b. Mô hình Markov ẩn (bỏ khoảng trống giữa các trạng thái). c. Mô hình hóa sự liên kết theo Mô hình Markov ẩn Mô hình Markov ẩn hiệu quả cho mô hình hóa thông tin về các chuỗi liên kết, phù hợp cho các cấu trúc chuỗi mẫu vì mô hình này có cấu trúc trái sang phải tuyến tính mà không chứa bất kỳ chu kỳ nào. Mô hình sử dụng ba loại trạng thái: ẩn(delete), quan sát được(insert) và kết quả(match). Ví dụ: Việc so sánh hai chuỗi sinh học theo Mô hình Markov ẩn sẽ sắp xếp các chuỗi dựa trên sự giống nhau, tính toán số điểm liên kết của chúng, và đánh giá các liên kết thống kê được. Tuy nhiên, để tìm ra sự liên kết tốt giữa các trình tự, chúng ta phải đưa ra được một bảng xếp hạng dựa trên sự giống nhau của các chuỗi . Căn cứ vào bảng này, chúng ta có thể chọn các liên kết nhằm tối đa hóa điểm số liên kết. Hình 1.2. Ví dụ về mô hình cặp HMM [5] Mô hình cặp -HMM tạo ra cặp liên kết chuỗi. Hai chuỗi DNA x và z được đồng thời tạo ra bởi các cặp-HMM, các dãy trạng thái cơ bản là y. Các trạng thái y xác định chỉ 1 liên kết duy nhất giữa x và z. Ưu điểm: Phương pháp này đã được sử dụng rộng rãi trong tin sinh học vì độ chính xác cao. Cách mô hình hóa dễ sử dụng. Nhược điểm: Chi phí thời gian lớn và các hàm tính toán phức tạp. 1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ Phương pháp này được sử dụng để tìm sự giống nhau hoặc có độ tương đồng cao của hai chuỗi. Bằng cách lập ma trận, tính độ đo để tìm ra sự giống hoặc có độ 15 tương đồng cao của tất cả độ dài các phân đoạn của hai xâu, hai chuỗi protein hoặc nucleotide. Với chuỗi đã được tìm kiếm và có độ tương đồng cao trước đó, phương pháp có thể mở rộng phạm vi tìm kiếm về hai phía (trước hoặc sau). Phương pháp này có ưu điểm là độ chính xác cao. Tuy nhiên chi phí thời gian lớn. Phương pháp đặc trưng của dạng này là phương pháp Smith & Waterman do hai nhà khoa học T.F.Smith & M.S.Waterman công bố năm 1981. [6] Hiện nay, do những cải tiến về máy tính và thuật toán tìm kiếm, phương pháp này có thể tìm kiếm đồng thời nhiều chuỗi cùng lúc khoảng (1000 chuỗi). [18] Thuật toán Smith & Waterman Thuật toán Smith-Waterman là một thuật toán quy hoạch động dùng để tìm kiếm cơ sở dữ liệu phát triển bởi T.F Smith và M.S Waterman vào năm 1981 và dựa trên một mô hình thích hợp trước đó có tên Needleman và Wunsch. Thuật toán sử dụng bảng ma trận để đánh giá sự tương đồng của hai chuỗi. Tìm kiếm lần lượt từ đầu đến cuối trong hai chuỗi xem mức độ tương đồng ở mức nào (tương đồng hoặc không tương đồng). Với các mức độ tương đồng khác nhau sẽ có những chỉ số độ đo khác nhau. Đặc điểm của thuật toán Smith-Waterman là thuật toán so sánh các cặp chuỗi cục bộ dựa trên quy hoạch động để tính điểm cho quá trình so sánh.Giải thuật này giúp nhận ra những miền tương đồng giữa hai chuỗi tìm kiếm cho giống chuỗi cục bộ tối ưu hơn. Giải thuật Smith-Waterman thực hiện so sánh đối xứng ở dạng cục bộ, khác với giải thuật so sánh đối xứng toàn cục (ví dụ: Needleman- Wunsch), giải thuật sắp hàng hay so sánh đối xứng cục bộ chỉ thực hiện việc so sánh đối xứng trên một số phần của các trình tự được so sánh. Độ tương tự s(a,b) được đưa ra bởi các cặp (a,b). Để tìm cặp tương đồng (a,b) ta lập ma trận H. Đặt: HkO = HoL, = 0 for 0 ≤ k ≤ n and 0 ≤ l ≤ m. [6] Hij thể hiện mức độ tương đồng của ai,bj. Hij được tính bằng công thức: Hij=max{Hi-1,j-1 + s(ai,bj).max(Hi-k,j - wk}.max{ Hi,j-l - wl},0} (1) k≥1 l≥1 với l ≤ i ≤ n và l ≤ j ≤ m. [6] Công thức Hij tính bởi các giá trị ở cuối các đoạn tại bất kỳ giá trị ai và bj nào. (1) Nếu ai và bj có liên kết, độ tương tự tính như sau: 16 Hi-1,j-1 + s(ai.bj) (2) Nếu ai tại vị trí cuối của dãy xóa k, độ tương tự tính bằng công thức Hi-k,j - Wk (3) Nếu bj là vị trí cuối của vị trí xóa có độ dài l, độ tương tự xác định bởi Hi-k,j – Wl (4) Giá trị 0 đã bao gồm biểu thị cho mức độ không tương đồng, nó chỉ ra rằng mức độ không tương đồng cho đến giá trị ai và bj Giá trị H càng cao thì mức độ tương đồng của Hij càng lớn. Đầu tiên ta tìm chỉ số cao nhất của ma trận. Sau đó, duyệt ngược trở lại. Ta sẽ tìm được mức độ tương đồng của 2 chuỗi cần chọn. Thuật toán: - Đầu vào : Hai chuỗi S1 và S2 với chiều dài tương ứng là n, m. Ma trận thay thế S.Gap d.  Đầu ra : Hai chuỗi S1’, S2’.  Bước 1 : Khởi tạo : + H(0,0) = 0 + H(i,0) = 0 0 ≤ i ≤ m + H(0,j) = 0 0 ≤ j ≤ n  Bước 2 : Điền giá trị vào ma trận. Tính H(i, j) theo công thức H(i, j) = MAX (0, H(i-1,j-1) + S(i,j), H(i-1,j)+d, H(i,j-1) + d) (1) [6] Mỗi khi tính H(i, j) lưu lại chỉ số của số hạng ở vế phải (1)  Bước 3 : Tìm ô (i_max, j_max) có điểm cao nhất (0  i  m, 0  j  n)  Bước 4 : Quay lại bước 2.  Xuất phát từ ô (i_max, j_max).Dựa vào những chỉ số đã lưu ở bước 2 để tìm giá trị cho đến khi gặp ô H(i,j) = 0 thì dừng.  Nếu đường đi theo chiều ngang hay từ ô (i,j-1) sang ô (i,j) thì thêm “-“ vào S2’ và thêm kí tự S1(j) vào S1’.  Nếu đường đi theo chiều thẳng đứng hay từ ô (i-1, j) xuống ô (i,j) thì thêm “-“ vào S1’ và thêm kí tự S2(i) và S2’.  Nếu đường đi theo đường chéo hay từ ô (i-1, j-1) đến ô (i,j) thì thêm kí tự S1(j) vào S1’ và S2(i) vào S2’  Đảo ngược S1’, S2’ 17 Ví dụ: Bước 1: Khởi tạo: T C A A T C 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 A 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 A 0 0 0 0 0 0 0 T 0 0 0 0 0 0 0 C 0 0 0 0 0 0 0 Bước 2: : Điền giá trị vào ma trận: giống nhau = 2, khác = 0, tương đồng = 1 T C A A T C 0 0 0 0 0 0 0 T 0 2 0 1 1 2 0 A 0 1 1 2 2 0 0 T 0 2 0 1 1 2 0 A 0 1 1 2 2 0 0 T 0 2 0 1 1 2 0 C 0 0 2 0 1 0 2 T 0 2 1 C 0 0 2 Bước 3: Tìm H (i_max, j_max) có điểm cao nhất : T C 0 0 0 T 0 2 0 A 0 1 1 18 T 0 2 1 A 0 1 1 A A T C 0 0 0 0 1 1 2 1 3 2 0 1 1 1 3 1 2 4 1 1 1 1 5 1 0 1 1 6 Bước 4: Duyệt ngược đến khi về H (1,1) thì kết thúc. T C A A T C T C A A T C 0 0 0 0 0 0 0 T 0 2 1 1 1 2 0 A 0 1 1 3 2 1 0 T 0 2 1 1 1 3 0 A 0 1 1 3 4 1 0 T 0 2 1 1 1 5 0 C 0 0 2 0 1 0 6 0 0 0 0 0 0 0 T 0 2 1 1 1 2 1 A 0 1 1 3 2 1 1 T 0 2 1 1 1 3 1 A 0 1 1 3 4 1 1 T 0 2 1 1 1 5 1 C 0 1 2 1 1 1 6 Bước 5: Lặp lại bước 2, duyệt trở về đầu ma trận. Ta có kết quả: TATAT C | | | | | TCAATC 19 Ví dụ về ma trận thực hiện so sánh chuỗi của Smith & Waterman: Hình 1.3. Bảng ma trận độ đo trong ví dụ 2 chuỗi của Smith & Waterman [2] Chuỗi A-A-U-G-C-C-A-U-U-G-A-C-G-G và chuỗi C-A-G-C-C-U-C-G-C-U-U-A-G Ở hình 1.3 chỉ số (3-3) là chỉ số cao nhất của ma trận. Duyệt theo đường chéo, lấy giá trị cao nhất. Nếu có giá trị thấp, xét các vùng lân cận để lấy chỉ số cao. Duyệt ngược trở lại. Lấy giá trị cao nhất. Lặp lại bước này. Cuối cùng ta có độ tương đồng của 2 chuỗi là: -G-C-C-A-U-U-G-G-C-C --- U-C-GƯu điểm: Do phải duyệt và so sánh lần lượt thứ tự từng nucleotide nên phương pháp này có độ chính xác cao. 20