Luận văn Thạc sĩ Công nghệ thông tin: Nghiên cứu phương pháp nén dữ liệu để tăng hiệu quả lưu trữ chuỗi DNA

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 thức nén dữ liệu sử dụng cho nén chuỗi DNA. Thuật toán nén tham chiếu cụ thể mà người viết luận văn tập trung nghiên cứu, thuật toán nén tham chiếu JDNA, đượ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 nén tham chiếu JDNA với hai thuật toán thuộc phương thức nén 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.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Công nghệ thông tin: Nghiên cứu phương pháp nén dữ liệu để tăng hiệu quả lưu trữ chuỗi DNAĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆCAO THỤC TUYẾT TRINHNGHIÊN CỨU PHƯƠNG PHÁP NÉN DỮ LIỆU ĐỂTĂNG HIỆU QUẢ LƯU TRỮ CHUỖI DNALUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TINHÀ NỘI – 2016ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆCAO THỤC TUYẾT TRINHNGHIÊN CỨU PHƯƠNG PHÁP NÉN DỮ LIỆU ĐỂTĂNG HIỆU QUẢ LƯU TRỮ CHUỖI DNANgà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 phương pháp néndữ liệu để tăng hiệu quả lưu trữ chuỗi DNA” là sản phẩm do tôi thực hiện dướisự 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ổnghợp từ nhiềunguồ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íchdẫ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 5 năm 2016TÁC GIẢCao Thục Tuyết Trinh2LỜI CẢM ƠNTrướ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áotrong Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc giaHà 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êncứ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ườitrự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 5 năm 2016TÁC GIẢCao Thục Tuyết Trinh3MỤC LỤCLỜI CAM ĐOAN .............................................................................................. 1LỜI CẢM ƠN .................................................................................................... 2MỤC LỤC ......................................................................................................... 3DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT .................................................... 5GIỚI THIỆU ...................................................................................................... 6CHƯƠNG 1 – TỔNG QUAN VỀ THUẬT TOÁN NÉN DỮ LIỆU................. 101.1. Thuật toán mã hóa bit (Naïve Bit) ........................................................ 101.1.1.Mã hóa trực tiếp phần khác biệt (thuật toán 2D) ......................... 111.1.2.Thuật toán nén DNABIT ............................................................ 161.2. Thuật toán nén dựa trên bộ từ điển ....................................................... 201.2.1.LZ77 ........................................................................................... 211.2.2.LZ78 ........................................................................................... 221.3. Thuật toán nén xác suất thống kê ......................................................... 241.3.1. Thuật toán nén HuffBit sử dụng cây nhị phân mở rộng với mãHuffman ................................................................................................... 261.3.2.Thuật toán Expert Markov (XM) ................................................ 291.4. Thuật toán nén tham chiếu ................................................................... 331.4.1.Đặc trưng thuật toán tham chiếu ................................................. 331.4.2.Các thuật toán nén tham chiếu .................................................... 38CHƯƠNG 2 – THUẬT TOÁN NÉN THAM CHIẾU JDNA ........................... 402.1. THUẬT TOÁN JDNA - Nén tham chiếu các chuỗi gen đã sắp xếp ..... 412.1.1.Thuật toán nén ............................................................................ 422.1.2.Thư viện FRESCO ...................................................................... 422.1.3.Bảng K-mer ................................................................................ 462.1.4.Định dạng tệp ............................................................................. 462.2. Đánh giá............................................................................................... 472.2.1.Cải thiện tỉ lệ nén ........................................................................ 472.2.2.Cải thiện thời gian....................................................................... 572.2.3.Cải thiện vùng nhớ...................................................................... 59 ...