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