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ỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> CAO THỤC TUYẾT TRINH<br /> <br /> NGHIÊN CỨU PHƯƠNG PHÁP NÉN DỮ LIỆU ĐỂ<br /> TĂNG HIỆU QUẢ LƯU TRỮ CHUỖI DNA<br /> <br /> LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN<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 /> CAO THỤC TUYẾT TRINH<br /> <br /> NGHIÊN CỨU PHƯƠNG PHÁP NÉN DỮ LIỆU ĐỂ<br /> TĂNG HIỆU QUẢ LƯU TRỮ CHUỖI DNA<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 /> <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 phương pháp nén<br /> dữ 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ưới<br /> 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ổnghợ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 5 năm 2016<br /> TÁC GIẢ<br /> <br /> Cao Thục Tuyết Trinh<br /> <br /> 2<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à<br /> hoàn 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è<br /> 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ô<br /> giáo, 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 5 năm 2016<br /> TÁC GIẢ<br /> <br /> Cao Thục Tuyết Trinh<br /> <br /> 3<br /> <br /> MỤC LỤC<br /> LỜI CAM ĐOAN .............................................................................................. 1<br /> LỜI CẢM ƠN .................................................................................................... 2<br /> MỤC LỤC ......................................................................................................... 3<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Ề THUẬT TOÁN NÉN DỮ LIỆU................. 10<br /> 1.1. Thuật toán mã hóa bit (Naïve Bit) ........................................................ 10<br /> 1.1.1.<br /> <br /> Mã hóa trực tiếp phần khác biệt (thuật toán 2D) ......................... 11<br /> <br /> 1.1.2.<br /> <br /> Thuật toán nén DNABIT ............................................................ 16<br /> <br /> 1.2. Thuật toán nén dựa trên bộ từ điển ....................................................... 20<br /> 1.2.1.<br /> <br /> LZ77 ........................................................................................... 21<br /> <br /> 1.2.2.<br /> <br /> LZ78 ........................................................................................... 22<br /> <br /> 1.3. Thuật toán nén xác suất thống kê ......................................................... 24<br /> 1.3.1. Thuật toán nén HuffBit sử dụng cây nhị phân mở rộng với mã<br /> Huffman ................................................................................................... 26<br /> 1.3.2.<br /> <br /> Thuật toán Expert Markov (XM) ................................................ 29<br /> <br /> 1.4. Thuật toán nén tham chiếu ................................................................... 33<br /> 1.4.1.<br /> <br /> Đặc trưng thuật toán tham chiếu ................................................. 33<br /> <br /> 1.4.2.<br /> <br /> Các thuật toán nén tham chiếu .................................................... 38<br /> <br /> CHƯƠNG 2 – THUẬT TOÁN NÉN THAM CHIẾU JDNA ........................... 40<br /> 2.1. THUẬT TOÁN JDNA - Nén tham chiếu các chuỗi gen đã sắp xếp ..... 41<br /> 2.1.1.<br /> <br /> Thuật toán nén ............................................................................ 42<br /> <br /> 2.1.2.<br /> <br /> Thư viện FRESCO ...................................................................... 42<br /> <br /> 2.1.3.<br /> <br /> Bảng K-mer ................................................................................ 46<br /> <br /> 2.1.4.<br /> <br /> Định dạng tệp ............................................................................. 46<br /> <br /> 2.2. Đánh giá............................................................................................... 47<br /> 2.2.1.<br /> <br /> Cải thiện tỉ lệ nén ........................................................................ 47<br /> <br /> 2.2.2.<br /> <br /> Cải thiện thời gian....................................................................... 57<br /> <br /> 2.2.3.<br /> <br /> Cải thiện vùng nhớ...................................................................... 59<br /> <br />