Tóm tắt 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

Nội dung đề tài được chia thành 3 phần, nội dung cụ thể như sau: Phần 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 ở phần 2 và cuối cùng phần 3 mô tả môi trường thực nghiệmso 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.
Nội dung trích xuất từ tài liệu:
Tóm tắt 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ỘITRƢỜNG ĐẠI HỌC CÔNG NGHỆNGUYỄN HOÀNG ANHNGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖIDNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾMTƢƠNG TỰ NHANHNgành: Hệ thống thông tinChuyên ngành: Hệ thống thông tinMã số: 60 48 01 04LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TINNGƢỜI HƢỚNG DẪN KHOA HỌC: Tiến sĩ Nguyễn Thị HậuHÀ NỘI – 20161LỜI CAM ĐOANTôi xin cam đoan nội dung của luận văn “Nghiên cứu thuật toán tìmkiếm chuỗi DNA sử dụng phương pháp tương tự nhanh” là sản phẩm dotô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ộidung 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 theoquy định cho lời cam đoan của mình.Hà Nội, ngày 20 tháng 9 năm 2016TÁC GIẢNguyễn Hoàng Anh2MỤC LỤCLỜI CAM ĐOAN ......................................................................................... 2DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ............................................ 5GIỚI THIỆU ................................................................................................. 6CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾMCHUỖI DNA ................................................................................................ 71.1.ẩnPhương pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov71.2.Phương pháp liên kết nhạy cảm đầy đủ ..................................... 81.3.Phương pháp tìm kiếm tương tự nhanh ..................................... 91.4.Phương pháp sử dụng mô hình phù hợp gần đúng ................. 101.5.xácPhương pháp sử dụng mô hình kết hợp chính xác và gần chính10CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖITƢƠNG TỰ NHANH ÁP DỤNG N-GRAM............................................ 122.1.Mô hình N-Gram ........................................................................ 122.1.1.Một số khái niệm .................................................................. 122.1.2.Mô hình ngôn ngữ N-gram ................................................... 122.1.3.Công thức tính “xác suất thô” ............................................... 122.1.4.Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ........... 132.2. Phương pháp tương tự nhanh áp dụng N-gram tìm kiếm chuỗiDNA. ...................................................................................................... 132.2.1.Phân đoạn DNA .................................................................... 132.2.2.Các “từ DNA” ...................................................................... 132.2.3.Quá trình tìm kiếm chuỗi và hiển thị kết quả ....................... 142.3. Bảng kết quả các lần thử phương pháp tìm kiếm chuỗi tươngtự nhanh áp dụng N-Gram .................................................................... 1632.3.1.Định dạng chuỗi cơ sở dữ liệu .............................................. 162.3.2.Bảng kết quả các lần thử phương pháp tìm kiếm chuỗi tươngtự nhanh áp dụng N-Gram .................................................................... 172.4. Đánh giá phương pháp tìm kiếm chuỗi tương tự nhanh ápdụng N-Gram .......................................................................................... 172.4.1.Cải thiện thời gian tìm kiếm ................................................. 172.4.2.Tiết kiệm bộ nhớ trong quá trình tìm kiếm ........................... 18CHƢƠNG 3. THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾMTƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁPBLAST VÀ PHƢƠNG PHÁP SMITH-WATERMAN ........................... 193.1.Môi trường thực nghiệm ............................................................ 193.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 SmithWater Man .............................................................................................. 21KẾT LUẬN ................................................................................................. 22TÀI LIỆU THAM KHẢO.......................................................................... 234Kí hiệuDNANSTATGCSNPCPURAMNCBIHMMBLASTHTSDANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮTTiếng AnhTiếng ViệtDeoxy Ribonucleic AcidPhân tử mang cấu trúcgen di truyềnChromosomeNhiễm sắc thểAdenineThymineGuanineCytosineSingle nucleotideTính đa hình của phân tửpolymorphismsnucleotit. Mỗi SNP biểudiễn một biến đổi trongmột khối chuỗi DNACental Processing UnitBộ xử lý trung tâmRandom access memoryBộ nhớ truy cập ngẫunhiênNational Center forTrung tâm quốc giaBiotechnology Informationthông tin công nghệ sinhDifferential Direct codingMã hóa trực tiếp phầnkhác biệtHidden Markov Modeli ...