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ĩ nghiên cứu phương pháp nén dữ liệu nhằm tối ưu hóa hiệu quả lưu trữ chuỗi DNA, góp phần nâng cao nghiên cứu sinh học.

• Tác giả: Cao Thục Tuyết Trinh
• Người hướng dẫn: Tiến Sĩ Nguyễn Thị Hậu
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Nghiên Cứu Phương Pháp Nén Dữ Liệu Tăng Hiệu Quả Lưu Trữ Chuỗi DNA
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ THUẬT TOÁN NÉN DỮ LIỆU
• 1.1. Thuật toán mã hóa bit (Naïve Bit)
• 1.2. Mã hóa trực tiếp phần khác biệt (thuật toán 2D)
• 1.3. Thuật toán nén DNABIT
• 1.4. Thuật toán nén dựa trên bộ từ điển
• 1.5. Thuật toán nén xác suất thống kê
• 1.6. Thuật toán nén HuffBit sử dụng cây nhị phân mở rộng với mã Huffman
• 1.7. Thuật toán Expert Markov (XM)
• 1.8. Thuật toán nén tham chiếu
• 1.9. Đặc trưng thuật toán tham chiếu
• 1.10. Các thuật toán nén tham chiếu
• 2. CHƯƠNG 2: THUẬT TOÁN NÉN THAM CHIẾU JDNA
• 2.1. THUẬT TOÁN JDNA - Nén tham chiếu các chuỗi gen đã sắp xếp
• 2.2. Thuật toán nén
• 2.3. Thư viện FRESCO
• 2.4. Định dạng tệp
• 2.5. Cải thiện tỉ lệ nén
• 2.6. Cải thiện thời gian. Cải thiện vùng nhớ
• 3. CHƯƠNG 3: THỰC NGHIỆM SO SÁNH THUẬT TOÁN JDNA VỚI THUẬT TOÁN MÃ HÓA HUFFMAN VÀ LEMPEL - ZIV
• 3.1. Môi trường thực nghiệm
• 3.2. Thực nghiệm so sánh JDNA với Mã hóa Huffman và Lempel – Ziv
• 3.3. Phân tích và đánh giá kết quả thực nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Nén Dữ Liệu Chuỗi DNA Để Tăng Hiệu Quả Lưu Trữ

Nén dữ liệu chuỗi DNA là một lĩnh vực nghiên cứu quan trọng trong công nghệ sinh học. Với sự phát triển của công nghệ sắp xếp gen, khối lượng dữ liệu DNA ngày càng lớn, đặt ra thách thức về lưu trữ và truy cập. Việc áp dụng các phương pháp nén hiệu quả không chỉ giúp tiết kiệm không gian lưu trữ mà còn tăng tốc độ truy cập dữ liệu. Nghiên cứu này sẽ trình bày tổng quan về các phương pháp nén dữ liệu hiện có và tầm quan trọng của chúng trong việc tối ưu hóa lưu trữ chuỗi DNA.

1.1. Tại Sao Cần Nén Dữ Liệu Chuỗi DNA

Khối lượng dữ liệu DNA khổng lồ từ các nghiên cứu gen yêu cầu các phương pháp nén hiệu quả. Nén dữ liệu giúp giảm chi phí lưu trữ và tăng tốc độ truy cập thông tin. Điều này đặc biệt quan trọng trong y sinh học, nơi mà thời gian và không gian lưu trữ là rất quý giá.

1.2. Các Phương Pháp Nén Dữ Liệu Hiện Có

Có nhiều phương pháp nén dữ liệu chuỗi DNA, bao gồm mã hóa bit, nén dựa trên bộ từ điển, nén thống kê và nén tham chiếu. Mỗi phương pháp có ưu điểm và nhược điểm riêng, phù hợp với các loại dữ liệu khác nhau.

II. Vấn Đề Trong Lưu Trữ Dữ Liệu Chuỗi DNA

Lưu trữ dữ liệu chuỗi DNA gặp nhiều thách thức do kích thước và độ phức tạp của dữ liệu. Các phương pháp nén truyền thống không thể đáp ứng yêu cầu về hiệu suất và tỉ lệ nén. Điều này dẫn đến việc cần phát triển các thuật toán nén chuyên biệt cho chuỗi DNA.

2.1. Thách Thức Về Kích Thước Dữ Liệu

Kích thước dữ liệu DNA có thể lên tới hàng terabyte, gây khó khăn trong việc lưu trữ và xử lý. Các phương pháp nén hiện tại cần phải cải thiện để đáp ứng nhu cầu này.

2.2. Độ Phức Tạp Của Chuỗi DNA

Chuỗi DNA có cấu trúc phức tạp với nhiều yếu tố ảnh hưởng đến việc nén. Các thuật toán nén cần phải xem xét các yếu tố này để đạt được hiệu quả cao nhất.

III. Phương Pháp Nén Dữ Liệu Chuỗi DNA Hiệu Quả

Nghiên cứu đã chỉ ra rằng các phương pháp nén tham chiếu có thể đạt được tỉ lệ nén cao hơn so với các phương pháp khác. Các thuật toán như JDNA đã được phát triển để tối ưu hóa quá trình nén và giải nén dữ liệu chuỗi DNA.

3.1. Thuật Toán Nén Tham Chiếu JDNA

JDNA là một thuật toán nén tham chiếu được thiết kế để tối ưu hóa tỉ lệ nén cho chuỗi DNA. Thuật toán này sử dụng các chuỗi tham chiếu bên ngoài để cải thiện hiệu suất nén.

3.2. So Sánh Với Các Thuật Toán Khác

Kết quả thực nghiệm cho thấy JDNA có tỉ lệ nén cao hơn so với các thuật toán như Huffman và Lempel-Ziv. Điều này chứng tỏ tính ưu việt của phương pháp nén tham chiếu trong việc xử lý dữ liệu chuỗi DNA.

IV. Ứng Dụng Thực Tiễn Của Nén Dữ Liệu Chuỗi DNA

Nén dữ liệu chuỗi DNA không chỉ có ý nghĩa trong nghiên cứu mà còn trong các ứng dụng thực tiễn như y sinh học, phân tích gen và bảo quản dữ liệu. Việc áp dụng các phương pháp nén hiệu quả giúp tiết kiệm chi phí và thời gian trong các nghiên cứu gen.

4.1. Ứng Dụng Trong Y Sinh Học

Trong y sinh học, việc nén dữ liệu chuỗi DNA giúp các nhà nghiên cứu dễ dàng truy cập và phân tích dữ liệu gen, từ đó hỗ trợ cho việc phát triển thuốc và điều trị bệnh.

4.2. Bảo Quản Dữ Liệu Gen

Nén dữ liệu giúp bảo quản thông tin gen một cách hiệu quả, giảm thiểu chi phí lưu trữ và đảm bảo an toàn cho dữ liệu quan trọng này.

V. Kết Luận Về Nghiên Cứu Nén Dữ Liệu Chuỗi DNA

Nghiên cứu về nén dữ liệu chuỗi DNA đã chỉ ra rằng việc áp dụng các phương pháp nén hiệu quả là cần thiết để giải quyết các thách thức trong lưu trữ và truy cập dữ liệu. Tương lai của nghiên cứu này hứa hẹn sẽ mang lại nhiều cải tiến và ứng dụng mới.

5.1. Hướng Phát Triển Trong Tương Lai

Các nghiên cứu tiếp theo có thể tập trung vào việc cải thiện các thuật toán nén hiện tại, nhằm đạt được tỉ lệ nén cao hơn và thời gian giải nén nhanh hơn.

5.2. Tầm Quan Trọng Của Nén Dữ Liệu

Nén dữ liệu chuỗi DNA không chỉ giúp tiết kiệm không gian lưu trữ mà còn mở ra cơ hội mới trong nghiên cứu và ứng dụng công nghệ sinh học.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh công nghệ sinh học phát triển mạnh mẽ, việc xử lý và lưu trữ dữ liệu chuỗi DNA ngày càng trở nên cấp thiết. Bộ gen người gồm khoảng 3 tỷ đặc trưng trên 23 cặp nhiễm sắc thể, tạo ra một khối lượng dữ liệu khổng lồ, đòi hỏi các giải pháp lưu trữ hiệu quả. Chi phí lưu trữ và tốc độ truy cập dữ liệu gen là những thách thức lớn đối với các nhà nghiên cứu và các tổ chức y sinh học. Mục tiêu của luận văn là nghiên cứu và phát triển các phương pháp nén dữ liệu nhằm tăng hiệu quả lưu trữ chuỗi DNA, đặc biệt tập trung vào thuật toán nén tham chiếu JDNA, một khung nén tham chiếu dựa trên thư viện FRESCO, nhằm cải thiện tỉ lệ nén và tốc độ xử lý.

Phạm vi nghiên cứu tập trung vào các thuật toán nén chuỗi DNA, bao gồm mã hóa bit, nén dựa trên bộ từ điển, nén xác suất thống kê và nén tham chiếu, với thời gian nghiên cứu chủ yếu trong giai đoạn trước năm 2016 tại Đại học Công nghệ, Đại học Quốc gia Hà Nội. Ý nghĩa của nghiên cứu được thể hiện qua việc giảm thiểu không gian lưu trữ dữ liệu gen, tăng tốc độ truy cập và xử lý, góp phần thúc đẩy các nghiên cứu di truyền học và y sinh học hiện đại. Theo báo cáo của ngành, thuật toán nén tham chiếu có thể đạt tỉ lệ nén lên đến 1000:1 trong điều kiện lý tưởng, vượt trội so với các phương pháp truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên bốn nhóm thuật toán nén chính cho chuỗi DNA:

1. Thuật toán mã hóa bit (Naïve Bit): Mỗi bazơ DNA (A, C, G, T) được mã hóa bằng 2 bit, cho phép biểu diễn hiệu quả chuỗi DNA đơn giản. Thuật toán 2D là một ví dụ điển hình, sử dụng mã hóa bộ ba bazơ trong một byte, hỗ trợ nén không mất dữ liệu và xử lý các ký tự phụ như N.

2. Thuật toán nén dựa trên bộ từ điển: Thay thế các chuỗi con lặp bằng tham chiếu tới một bộ từ điển được xây dựng trong quá trình nén hoặc trước đó. Thuật toán Lempel-Ziv (LZ77, LZ78) là đại diện tiêu biểu, tận dụng các chuỗi lặp để giảm kích thước dữ liệu.

3. Thuật toán nén xác suất thống kê: Dựa trên mô hình xác suất của dữ liệu đầu vào, như mã hóa Huffman và mô hình Markov ẩn, nhằm dự đoán ký tự tiếp theo và mã hóa với độ dài biến đổi theo tần suất xuất hiện. Thuật toán Expert Markov (XM) kết hợp nhiều chuyên gia dự đoán để tối ưu hóa tỉ lệ nén.

4. Thuật toán nén tham chiếu: Sử dụng một chuỗi tham chiếu bên ngoài để mã hóa các chuỗi con dài của dữ liệu đầu vào, tận dụng sự tương đồng cao giữa các chuỗi gen trong cùng loài. Thuật toán JDNA là một khung nén tham chiếu hiệu quả, kế thừa và cải tiến từ thư viện FRESCO, tập trung vào việc tối ưu hóa cấu trúc chỉ số và phương pháp đánh chỉ số theo yêu cầu.

Các khái niệm chuyên ngành quan trọng bao gồm SNPs (Single Nucleotide Polymorphisms), indels (chèn, xóa nucleotit), k-mer (chuỗi con có độ dài k), mã hóa entropy, và các thuật toán mã hóa số học.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu bao gồm các chuỗi gen từ ba loài: 1092 gen người, 180 gen cỏ Arabidopsis thaliana và 38 gen khuẩn men, được xử lý và nén bằng các thuật toán khác nhau để so sánh hiệu quả.

Phương pháp phân tích bao gồm:

• Thực nghiệm so sánh tỉ lệ nén, thời gian nén và dung lượng bộ nhớ sử dụng giữa thuật toán JDNA và các thuật toán tiêu biểu khác như FRESCO, GDC, RLZ, Huffman, và Lempel-Ziv.
• Đánh giá hiệu quả của các cải tiến trong JDNA như đánh chỉ số theo yêu cầu và sử dụng tính tương đương trong cấu trúc chỉ số.
• Sử dụng các chỉ số định lượng như tỉ lệ nén (kích thước dữ liệu gốc trên kích thước dữ liệu nén), thời gian thực hiện trung bình qua nhiều lần thử nghiệm, và bộ nhớ tối đa sử dụng trong quá trình nén.

Timeline nghiên cứu kéo dài trong năm 2016, với các giai đoạn thu thập dữ liệu, phát triển thuật toán, thực nghiệm và phân tích kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Tỉ lệ nén vượt trội của thuật toán nén tham chiếu JDNA: Thuật toán JDNA đạt tỉ lệ nén lên đến 1000:1 trong điều kiện lý tưởng, cao hơn đáng kể so với các thuật toán mã hóa bit (khoảng 4:1), nén dựa trên bộ từ điển (4:1 đến 6:1), và nén xác suất thống kê (4:1 đến 8:1). So với FRESCO, JDNA cải thiện tỉ lệ nén trung bình khoảng 10-15%.

2. Tối ưu hóa thời gian nén và dung lượng bộ nhớ: Qua thực nghiệm, JDNA giảm thời gian nén khoảng 20% so với FRESCO nhờ phương pháp đánh chỉ số theo yêu cầu, đồng thời giảm bộ nhớ sử dụng tối đa xuống còn khoảng 2GB, phù hợp với các hệ thống phổ biến.

3. Ảnh hưởng của chuỗi tham chiếu đến hiệu quả nén: Việc lựa chọn chuỗi tham chiếu phù hợp có ảnh hưởng lớn đến tỉ lệ nén. Chuỗi tham chiếu có độ tương đồng cao với dữ liệu đầu vào giúp tăng độ dài chuỗi khớp, giảm kích thước dữ liệu nén. Ví dụ, nén hệ gen người dựa trên chuỗi tham chiếu người đạt tỉ lệ nén cao hơn đáng kể so với khi sử dụng chuỗi tham chiếu của loài khác.

4. Khả năng xử lý các biến thể gen phức tạp: JDNA hỗ trợ hiệu quả các biến thể như SNPs, thay thế, chèn và xóa, với phân loại biến thể nhỏ và lớn dựa trên ngưỡng kích thước θ = 300. Thuật toán xử lý tốt các biến thể nhỏ, chiếm phần lớn trong dữ liệu gen cùng loài.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả vượt trội JDNA là do sự kết hợp giữa cấu trúc chỉ số băm k-mer hiệu quả và phương pháp đánh chỉ số theo yêu cầu, giúp giảm đáng kể thời gian và bộ nhớ cần thiết cho việc tìm kiếm chuỗi khớp. So với các thuật toán truyền thống như Lempel-Ziv hay Huffman, JDNA tận dụng đặc điểm tương đồng cao trong dữ liệu gen cùng loài để đạt tỉ lệ nén cao hơn nhiều.

Kết quả cũng cho thấy tầm quan trọng của việc lựa chọn chuỗi tham chiếu tối ưu, một bài toán phức tạp do kích thước lớn của dữ liệu gen. Việc viết lại tham chiếu dựa trên các chuỗi nén cũng góp phần cải thiện tỉ lệ nén tổng thể.

Dữ liệu có thể được trình bày qua biểu đồ so sánh tỉ lệ nén giữa các thuật toán trên các bộ dữ liệu khác nhau, bảng thống kê thời gian nén trung bình và bộ nhớ sử dụng, giúp minh họa rõ ràng ưu thế của JDNA.

Đề xuất và khuyến nghị

1. Phát triển thêm các phương pháp lựa chọn chuỗi tham chiếu tối ưu: Áp dụng các thuật toán học máy hoặc heuristic để tự động chọn chuỗi tham chiếu phù hợp, nhằm nâng cao tỉ lệ nén và giảm thời gian tính toán. Chủ thể thực hiện: nhóm nghiên cứu công nghệ sinh học, timeline: 12-18 tháng.

2. Tối ưu hóa thuật toán đánh chỉ số theo yêu cầu: Nâng cao hiệu quả đánh chỉ số bằng cách áp dụng các cấu trúc dữ liệu mới như mảng hậu tố hoặc cây FM, giảm thiểu bộ nhớ và tăng tốc độ tìm kiếm. Chủ thể thực hiện: nhóm phát triển phần mềm, timeline: 6-12 tháng.

3. Mở rộng hỗ trợ các biến thể gen phức tạp hơn: Nghiên cứu và tích hợp các kỹ thuật xử lý biến thể lớn, đa dạng hơn như biến thể cấu trúc, nhằm tăng tính ứng dụng trong các dự án gen đa dạng. Chủ thể thực hiện: nhà nghiên cứu di truyền học, timeline: 12 tháng.

4. Xây dựng công cụ truy cập ngẫu nhiên trên dữ liệu nén: Phát triển các phương pháp truy vấn nhanh trên dữ liệu nén để hỗ trợ phân tích gen trực tiếp mà không cần giải nén toàn bộ. Chủ thể thực hiện: nhóm phát triển phần mềm, timeline: 9-12 tháng.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu công nghệ sinh học và di truyền học: Có thể áp dụng các thuật toán nén để quản lý và phân tích dữ liệu gen lớn, giảm chi phí lưu trữ và tăng tốc độ xử lý.

2. Chuyên gia phát triển phần mềm xử lý dữ liệu sinh học: Tham khảo các kỹ thuật nén tham chiếu và cải tiến thuật toán để phát triển các công cụ lưu trữ và truy xuất dữ liệu hiệu quả.

3. Các tổ chức y tế và phòng thí nghiệm gen: Áp dụng giải pháp nén để tối ưu hóa hệ thống lưu trữ dữ liệu gen bệnh nhân, hỗ trợ nghiên cứu và chẩn đoán.

4. Sinh viên và học viên ngành hệ thống thông tin và công nghệ sinh học: Nắm bắt kiến thức về thuật toán nén dữ liệu DNA, từ đó phát triển các đề tài nghiên cứu hoặc ứng dụng thực tế.

Câu hỏi thường gặp

1. Tại sao cần nén dữ liệu chuỗi DNA?
   Dữ liệu chuỗi DNA có kích thước rất lớn, ví dụ bộ gen người khoảng 3GB, gây tốn kém chi phí lưu trữ và làm chậm quá trình truy cập. Nén dữ liệu giúp giảm không gian lưu trữ và tăng tốc độ truyền tải, hỗ trợ nghiên cứu hiệu quả hơn.

2. Thuật toán nén tham chiếu khác gì so với các thuật toán khác?
   Thuật toán nén tham chiếu sử dụng một chuỗi gen tham chiếu bên ngoài để mã hóa các phần giống nhau trong dữ liệu đầu vào, tận dụng sự tương đồng cao giữa các chuỗi gen cùng loài, từ đó đạt tỉ lệ nén rất cao, vượt trội so với các phương pháp mã hóa bit hay dựa trên bộ từ điển.

3. Làm thế nào để chọn chuỗi tham chiếu phù hợp?
   Chuỗi tham chiếu phù hợp là chuỗi có độ tương đồng cao với dữ liệu đầu vào, giúp tăng độ dài chuỗi khớp và giảm kích thước dữ liệu nén. Việc lựa chọn có thể dựa trên nén thử nghiệm hoặc các phương pháp heuristic để tối ưu hóa hiệu quả.

4. Thuật toán JDNA có thể áp dụng cho các loài khác ngoài người không?
   JDNA có thể áp dụng cho nhiều loài, tuy nhiên hiệu quả nén sẽ giảm khi độ tương đồng giữa chuỗi tham chiếu và dữ liệu đầu vào thấp, ví dụ khi nén hệ gen khác loài. Do đó, việc lựa chọn chuỗi tham chiếu phù hợp là rất quan trọng.

5. Có thể truy cập dữ liệu gen nén mà không cần giải nén toàn bộ không?
   Hiện tại, JDNA chưa hỗ trợ truy cập ngẫu nhiên trực tiếp trên dữ liệu nén, tuy nhiên đây là hướng phát triển tiềm năng để tăng tính ứng dụng, giúp truy vấn nhanh mà không cần giải nén toàn bộ dữ liệu.

Kết luận

• Luận văn đã nghiên cứu và đánh giá các phương pháp nén dữ liệu chuỗi DNA, tập trung vào thuật toán nén tham chiếu JDNA, đạt tỉ lệ nén lên đến 1000:1 trong điều kiện lý tưởng.
• JDNA cải tiến đáng kể về tỉ lệ nén, thời gian nén và bộ nhớ sử dụng so với các thuật toán truyền thống và thư viện FRESCO.
• Việc lựa chọn chuỗi tham chiếu tối ưu và phương pháp đánh chỉ số theo yêu cầu là yếu tố then chốt nâng cao hiệu quả nén.
• Các kết quả thực nghiệm trên dữ liệu gen người, cỏ Arabidopsis và khuẩn men chứng minh tính khả thi và ưu việt của JDNA.
• Hướng phát triển tiếp theo bao gồm tối ưu lựa chọn tham chiếu, mở rộng hỗ trợ biến thể gen phức tạp và phát triển truy cập ngẫu nhiên trên dữ liệu nén.

Để tiếp tục nghiên cứu và ứng dụng, các nhà khoa học và kỹ sư được khuyến khích áp dụng và phát triển các thuật toán nén tham chiếu, đồng thời hợp tác đa ngành để nâng cao hiệu quả lưu trữ và xử lý dữ liệu gen trong tương lai.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 – TỔNG QUAN VỀ THUẬT TOÁN NÉN DỮ LIỆU 1. Thuật toán mã hóa bit (Naïve Bit) Thuật toán mã hóa bit sử dụng các bit trạng thái để biểu diễn dữ liệu nén. 4 bazơ đặc trưng của DNA được mã hóa bởi 2 bit (4 trạng thái). Kỹ thuật nén thẳng dữ liệu chuỗi DNA là mã hóa 4 bazơ trong một byte theo mã hóa bit.1 [2] cho thấy một ví dụ về nén mã hóa bit Hình 1.

Ví dụ mã hóa bit Mỗi kí tự ở đầu vào được thay thế bởi 2 bit sử dụng phép thay thế {A = 00, C = 01, G = 10, T = 11}. Những cấu trúc hiện tại cung cấp các phép toán bit tốt hơn, về cơ bản cho phép một mã hóa của dữ liệu chuỗi DNA với 2 bit. Mã hóa này ảnh hưởng tới khả năng đọc dữ liệu đáng kể vì cần một bảng tìm kiếm để dịch dữ liệu nén. Do biểu diễn 4 bazơ vừa đủ chính xác trong 8 bit nên nếu xảy ra thêm giá trị biên thì sẽ phá hỏng cấu trúc này.

Mã hóa sẽ trở nên phức tạp nếu thêm một hoặc nhiều phần bù ví dụ như N vào chuỗi. Một phương pháp dùng để mã hóa 5 kí tự A, C, G, T, N là đặt 3 bazơ liên tiếp vào 1 byte. 7 bit có thể mã hóa 128 trạng thái và vì 53 < 128. Tuy nhiên, việc tăng kích thước các kí tự (nhiều kí tự được thêm vào chuỗi) sẽ khiến cho việc biểu diễn kí tự trở nên khó khăn hơn.

Tỉ lệ nén của thuật toán mã hóa bit là 4:1 nếu kích thước của chuỗi kí tự đầu vào là 4 hoặc ít hơn 4:1 nếu nhiều hơn 4 kí tự [2]. Có nhiều thuật toán được xây dựng dựa trên phương thức mã hóa bit như thuật toán mã hóa trực tiếp phần khác biệt (thuật toán 2D), thuật toán này có thể xử lý các chuỗi đầu vào ở bất kỳ định dạng nào. Với 5 kí tự thông thường của 11 DNA (A, C, G, T, N), một mã hóa 7bit cho 3 kí tự liên tiếp được sử dụng. Theo cách này thì có tới 128 kí tự bổ sung sẽ được mã hóa.

Tiếp theo là Genbit compress (GBC), một công cụ nén chuỗi viết bằng ngôn ngữ java, sử dụng mã hóa độ dài (run-length encoding) thực hiện trên 2 bit (naïve 2bit) [3]. [4] cũng đưa ra một phương thức nén các nhiễm sắc thể tương đồng, mã hóa 3 bazơ sử dụng 1 byte. Tuy nhiên, trong thuật toán này kết hợp những xử lý phức tạp cho phần lặp N, sau đó nén mã hóa đạt được bằng LZ77. Một phương thức khác thuộc lớp thuật toán này được xây dựng trên cơ sở dữ liệu Oracle [5].

Và [6] kết hợp một thuật toán bổ sung cho việc tìm kiếm nhiều đoạn trong dữ liệu nén. Sau cùng là một thuật toán tập trung vào việc phân tích cách thức lưu trữ các phần lặp với những mã hóa có kích thước biến đổi, thuật toán DNABit [7]. Do tính đặc trưng của thuật toán mã hóa bit được thể hiện khá rõ nét trong 2 thuật toán mã hóa trực tiếp phần khác biệt (2D) và DNABit nên sau đây người viết luận văn sẽ trình bày chi tiết hai thuật toán này. Mã hóa trực tiếp phần khác biệt (thuật toán 2D) Với sự phát triển ngày càng mạnh về các tập dữ liệu gen khổng lồ, nhiều phương pháp nén đã và đang được phát triển để đáp ứng khối lượng lớn gen gồm nhiều chuỗi và phần bù lớn hơn (như đầu chuỗi).

Các giao thức nén phát triển riêng cho dữ liệu chuỗi thì thường có tỉ lệ nén tốt nhưng hiệu suất thấp trên tập dữ liệu lớn mà gồm nhiều dữ liệu phụ trợ (phần bù). Để so sánh thì những ứng dụng nén thông thường có thể dễ dàng nén các tệp dữ liệu lớn không đồng nhất nhưng lại bị hạn chế đối với dải dữ liệu kí tự trong dữ liệu chuỗi. Bởi vậy, thuật toán 2D được thiết kế để cung cấp một giao thức nén chuỗi nucleotit thông thường. Giao thức này có thể phân biệt dữ liệu chuỗi và dữ liệu phần bù, từ đó đưa ra sự điều chỉnh phù hợp giữa nén dữ liệu chung chung và cụ thể.

Thuật toán 2D có những mục tiêu như sau [43]:  Thời gian thực hiện tuyến tính cho việc hỗ trợ các tập dữ liệu lớn: cả hai quá trình nén và giải nén đều phải hỗ trợ thực hiện đối với độ phức tạp thời gian thực hiện O(n).  Hỗ trợ bao gồm cả những kí tự phụ mà không phải thành phần của tập bazơ nucleotit mong đợi: các kí tự bổ sung có thể được sử dụng để biểu diễn thông tin tự do, dữ liệu chú thích hoặc các chuỗi con đặc biệt như miền chức năng hoặc các chuỗi lặp đặc biệt.  Mã hóa trực tiếp pha đơn: Pha nén yêu cầu chỉ một chiều đơn mà không có pha loại bỏ những thông tin dư thừa và không lưu trữ dữ liệu vào các tệp 12 cấu trúc phụ hoặc trung gian tạm thời. Tương tự, việc không lưu trữ dữ liệu phụ phải cho phép khôi phục một chiều đơn đối với pha giải nén.

 Nén không mất dữ liệu: Chuỗi gốc phải được khôi phục hoàn toàn sau quá trình giải nén. Việc này có thể được thực hiện chỉ dựa trên chuỗi thẳng mà không quan tâm tới định dạng hay bị ngắt dòng, hoặc dựa trên bố cục từng dòng của dữ liệu chuỗi gốc.  Không phân biệt loại chuỗi: Nén và giải nén không ưu tiên hay phân biệt chuỗi là DNA hay mRNA.  Giải nén chuỗi polipeptit (mỗi peptit gồm 10 tới 100 amino axit): Có thể lựa chọn khôi phục chuỗi nén nucleotit trực tiếp tới một chuỗi polipeptit dựa trên khung đọc xác định.

 Sử dụng được cùng với phương pháp nén khác: Một chuỗi mã hóa 2D có thể nén được bằng những ứng dụng nén khác để đưa ra khả năng nén chuỗi gốc trong tương lai. (a) Mô hình Để cho thời gian thực hiện tuyến tính, 2D sử dụng một mô hình tĩnh cho việc mã hóa dữ liệu chuỗi cùng với bất kỳ thông tin nào mà có thể được bao gồm trong đầu vào. 2D cho rằng DNA gồm {A, C, G, T} và mRNA gồm {A, C, G, U}. Đồng nhất hai tập trên, tập kí tự cho mô hình 2D gồm {A, C, G, T, U}.

Việc này giúp khai báo rõ ràng loại chuỗi. Trong trường hợp kí tự không phải nucleotit, 2D hỗ trợ tập giá trị ASCII truyền thống gồm 0 tới 127. Để hoàn thành nén, 2D cần biểu diễn nhiều bazơ sử dụng một byte đơn như khung 2-bit-mỗi-bazơ. 2D sử dụng mã hóa trực tiếp trên một bộ ba (3 bazơ nucleotit liên tiếp) vì những lý do sau.

Đầu tiên, việc này cho phép 3 bazơ nucleotit hợp lại trong một byte đơn mà không phải là nhiều byte. Thứ hai, bằng việc nén bộ ba (thay vì bộ hai) thì các kí tự không mong muốn có thể được mã hóa trực tiếp. Do đó giúp bỏ được pha loại các kí tự thừa và lưu trữ dữ liệu thừa trong cấu trúc thứ cấp. Điều này có lợi cho cả thời gian nén và giải nén.

Sau cùng, biểu diễn theo bộ ba giúp 2D giải nén các chuỗi polipeptit bằng cách biên dịch bộ ba như các codon (chuỗi liên kết 3 nucleotit của DNA hoặc RNA). (b) Mã hóa Ở mức thấp nhất, 2D sử dụng một byte được gán có dải giá trị từ -128 tới 127. Về mặt khái niệm, 7 bit của mỗi byte được sử dụng cho mã hóa và bít quan trọng nhất được sử dụng như một cờ nén. Khung nén này được mô tả ở Hình 1.

Ít nhất 7 bit được sử dụng để mã hóa dữ liệu. Bit quan trọng nhất được sử dụng như cờ để cho biết ngữ cảnh của byte là dữ liệu nén hay giải nén. Các kí tự được chuyển thành các bộ ba liên tiếp nếu mỗi thành phần là một bazơ nucleotit hợp lệ. Một bộ ba hợp lệ được gán một giá trị đơn trong dải từ 1 tới 125 và cờ nén là một tập hợp ngang hàng với giá trị gán trong khoảng -1 và - 125.

2D sẽ phân biệt dữ liệu chuỗi và các kí tự khác, nếu một giá trị không mong muốn xảy ra thì nó có thể được biên dịch như một giá trị ASCII trong dải từ 0 tới 127, sau đó giá trị này sẽ được lưu nguyên bản và không được gán cờ nén. Trong trường hợp xảy ra giá trị không mong muốn thì các thành phần khác của bộ ba hiện tại vẫn được mã hóa và giải nén độc lập dù có bazơ nucleotit hay không, việc này để duy trì khung đọc hiện tại cho việc hỗ trợ biên dịch một polipeptit chính xác. Mặc định là sự thực hiện có thể giả sử một khung đọc mong muốn bắt đầu cùng với phần bắt đầu của chuỗi. Tuy nhiên, nhiều khung đọc cũng được hỗ trợ dễ dàng bằng việc mã hóa một hoặc hai kí tự đầu tiên khi dữ liệu chưa được nén và sau đó mới bắt đầu thực hiện 2D.

Sau cùng, trong trường hợp kí tự không-biết, 2D biểu diễn nó bằng việc lưu ở dạng chưa nén với giá trị byte được gán nhỏ nhất -128. (c) Thuật toán Đoạn mã giả sau đây mô tả lõi của thuật toán nén 2D, nhận một chuỗi đầu vào và trả về mã hóa 2D dưới dạng mảng byte. begin byte list = new List char triplet = new Array int baseCount = 0 int nonCompressCount = 0 foreach character c in input string if nonCompressCount = 0 then if c is a nucleotide base then triplet at position baseCount = c baseCount = baseCount + 1 14 if baseCount = 3 then convert triplet to byte b and add b to list reset triplet baseCount = 0 else foreach character t in triplet convert t to byte b and add b to list endfor convert c to byte b and add b to list reset triplet nonCompressCount = 2 - baseCount baseCount = 0 else convert c to byte b and add b to list nonCompressCount = nonCompressCount - 1 endfor return list as byte Array end Dữ liệu giải mã được khôi phục theo dòng với độ dài chia hết cho 3. Ví dụ, nếu chuỗi trong tệp nguồn được chia thành dòng, mỗi dòng 70 kí tự thì chuỗi trong tệp khôi phục sẽ có độ dài dòng là 69, 69, 72, 69, 69, 72….

Việc này thực hiện để tăng tính nén toàn bộ mà vẫn duy trì được khả năng đọc. Tuy nhiên, nếu yêu cầu thì có thể thực hiện được phiên bản đọc từng dòng chính xác nhưng sẽ bị giảm tính nén toàn bộ.