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Ộ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<br /> TƢƠNG 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 /> HÀ NỘI – 2016<br /> 1<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<br /> kiếm chuỗi DNA sử dụng phương pháp tương tự nhanh” là sản phẩm do<br /> 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<br /> 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à<br /> đượ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ó<br /> xuất xứ rõ ràng và được trích 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<br /> quy đị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 /> 2<br /> <br /> MỤC LỤC<br /> LỜI CAM ĐOAN ......................................................................................... 2<br /> DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ............................................ 5<br /> GIỚI THIỆU ................................................................................................. 6<br /> CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM<br /> CHUỖI DNA ................................................................................................ 7<br /> 1.1.<br /> ẩn<br /> <br /> Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov<br /> 7<br /> <br /> 1.2.<br /> <br /> Phƣơng pháp liên kết nhạy cảm đầy đủ ..................................... 8<br /> <br /> 1.3.<br /> <br /> Phƣơng pháp tìm kiếm tƣơng tự nhanh ..................................... 9<br /> <br /> 1.4.<br /> <br /> Phƣơng pháp sử dụng mô hình phù hợp gần đúng ................. 10<br /> <br /> 1.5.<br /> xác<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<br /> 10<br /> <br /> CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI<br /> TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM............................................ 12<br /> 2.1.<br /> <br /> Mô hình N-Gram ........................................................................ 12<br /> <br /> 2.1.1.<br /> <br /> Một số khái niệm .................................................................. 12<br /> <br /> 2.1.2.<br /> <br /> Mô hình ngôn ngữ N-gram ................................................... 12<br /> <br /> 2.1.3.<br /> <br /> Công thức tính “xác suất thô” ............................................... 12<br /> <br /> 2.1.4.<br /> <br /> Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ........... 13<br /> <br /> 2.2. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi<br /> DNA. ...................................................................................................... 13<br /> 2.2.1.<br /> <br /> Phân đoạn DNA .................................................................... 13<br /> <br /> 2.2.2.<br /> <br /> Các “từ DNA” ...................................................................... 13<br /> <br /> 2.2.3.<br /> <br /> Quá trình tìm kiếm chuỗi và hiển thị kết quả ....................... 14<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<br /> tự nhanh áp dụng N-Gram .................................................................... 16<br /> 3<br /> <br /> 2.3.1.<br /> <br /> Định dạng chuỗi cơ sở dữ liệu .............................................. 16<br /> <br /> 2.3.2.<br /> Bảng kết quả các lần thử phương pháp tìm kiếm chuỗi tương<br /> tự nhanh áp dụng N-Gram .................................................................... 17<br /> 2.4. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp<br /> dụng N-Gram .......................................................................................... 17<br /> 2.4.1.<br /> <br /> Cải thiện thời gian tìm kiếm ................................................. 17<br /> <br /> 2.4.2.<br /> <br /> Tiết kiệm bộ nhớ trong quá trình tìm kiếm ........................... 18<br /> <br /> CHƢƠNG 3. THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾM<br /> TƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁP<br /> BLAST VÀ PHƢƠNG PHÁP SMITH-WATERMAN ........................... 19<br /> 3.1.<br /> <br /> Môi trƣờng thực nghiệm ............................................................ 19<br /> <br /> 3.2. Thực nghiệm đánh giá phƣơng pháp tìm kiếm tƣơng tự nhanh<br /> áp dụng N-Gram với phƣơng pháp BLAST và phƣơng pháp SmithWater Man .............................................................................................. 21<br /> KẾT LUẬN ................................................................................................. 22<br /> TÀI LIỆU THAM KHẢO.......................................................................... 23<br /> <br /> 4<br /> <br /> Kí hiệu<br /> DNA<br /> NST<br /> A<br /> T<br /> G<br /> C<br /> SNP<br /> <br /> CPU<br /> RAM<br /> NCBI<br /> <br /> HMM<br /> BLAST<br /> HTS<br /> <br /> DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT<br /> Tiếng Anh<br /> Tiếng Việt<br /> Deoxy Ribonucleic Acid<br /> Phân tử mang cấu trúc<br /> gen di truyền<br /> Chromosome<br /> Nhiễm sắc thể<br /> Adenine<br /> Thymine<br /> Guanine<br /> Cytosine<br /> Single nucleotide<br /> Tính đa hình của phân tử<br /> polymorphisms<br /> nucleotit. Mỗi SNP biểu<br /> diễn một biến đổi trong<br /> một khối chuỗi DNA<br /> Cental Processing Unit<br /> Bộ xử lý trung tâm<br /> Random access memory<br /> Bộ nhớ truy cập ngẫu<br /> nhiên<br /> National Center for<br /> Trung tâm quốc gia<br /> Biotechnology Information<br /> thông tin công nghệ sinh<br /> Differential Direct coding<br /> Mã hóa trực tiếp phần<br /> khác biệt<br /> Hidden Markov Modeling<br /> Mô hình Markov ẩn<br /> Basic Local Alignment Search<br /> Công cụ tìm kiếm cục bộ<br /> Tool<br /> theo mẫu có sẵn<br /> High – Throughput Sequencing<br /> Trình tự chuỗi đa lượng<br /> <br /> 5<br /> <br />