Luận án Thạc sĩ Hệ thống thông tin: 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

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƢỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> NGUYỄN HOÀNG ANH<br /> <br /> NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI<br /> DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG<br /> TỰ NHANH<br /> <br /> LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN<br /> <br /> 1<br /> <br /> HÀ NỘI – 2016<br /> <br /> ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƢỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> NGUYỄN HOÀNG ANH<br /> <br /> NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI<br /> DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG<br /> TỰ NHANH<br /> <br /> Ngành: Hệ thống thông tin<br /> Chuyên ngành: Hệ thống thông tin<br /> Mã số: 60 48 01 04<br /> <br /> LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN<br /> <br /> NGƢỜI HƢỚNG DẪN KHOA HỌC: Tiến sĩ Nguyễn Thị Hậu<br /> <br /> 2<br /> <br /> HÀ NỘI – 2016<br /> <br /> LỜI CAM ĐOAN<br /> 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<br /> 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<br /> 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,<br /> 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<br /> 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<br /> dẫn hợp pháp.<br /> 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<br /> định cho lời cam đoan của mình.<br /> Hà Nội, ngày 20 tháng 9 năm 2016<br /> TÁC GIẢ<br /> <br /> Nguyễn Hoàng Anh<br /> <br /> 3<br /> <br /> LỜI CẢM ƠN<br /> 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<br /> trong Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia<br /> 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<br /> cứu.<br /> Đặ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<br /> 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<br /> thiện luận văn này.<br /> 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à<br /> 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,<br /> các anh chị và các bạn mạnh khỏe và hạnh phúc.<br /> Hà Nội, ngày 20 tháng 9 năm 2016<br /> TÁC GIẢ<br /> <br /> Nguyễn Hoàng Anh<br /> <br /> 4<br /> <br /> MỤC LỤC<br /> LỜI CAM ĐOAN .....................................................................................................3<br /> LỜI CẢM ƠN ...........................................................................................................4<br /> DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT .......................................................7<br /> GIỚI THIỆU ............................................................................................................8<br /> CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI<br /> DNA .........................................................................................................................13<br /> 1.1.<br /> <br /> Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn ............ 13<br /> <br /> 1.2.<br /> <br /> Phƣơng pháp liên kết nhạy cảm đầy đủ....................................................... 15<br /> <br /> 1.3.<br /> <br /> Phƣơng pháp tìm kiếm tƣơng tự nhanh ...................................................... 21<br /> <br /> 1.4.<br /> <br /> Phƣơng pháp sử dụng mô hình phù hợp gần đúng .................................... 25<br /> <br /> 1.5.<br /> <br /> 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<br /> <br /> CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI TƢƠNG<br /> TỰ NHANH ÁP DỤNG N-GRAM. ......................................................................35<br /> 2.1.<br /> <br /> Mô hình N-Gram ............................................................................................ 35<br /> <br /> 2.1.1. Một số khái niệm ...................................................................................................... 35<br /> 2.1.2. Mô hình ngôn ngữ N-gram ....................................................................................... 36<br /> 2.1.3. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ............................................... 37<br /> 2.1.4. Các phương pháp khắc phục cụm N-Gram phân bố không đều ............................... 38<br /> <br /> 2.2.<br /> <br /> Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA. .... 39<br /> <br /> 2.2.1. Phân đoạn DNA ........................................................................................................ 39<br /> 2.2.2. Các “từ DNA” ........................................................................................................... 40<br /> 2.2.3. Quá trình tìm kiếm chuỗi và hiển thị kết quả............................................................ 40<br /> <br /> 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<br /> dụng N-Gram ............................................................................................................ 48<br /> 2.3.1. Định dạng chuỗi cơ sở dữ liệu .................................................................................. 48<br /> 5<br /> <br />