Nghiên cứu Phương Pháp Nén Dữ Liệu Để Tăng Hiệu Quả Lưu Trữ Chuỗi DNA

Tìm hiểu phương pháp nén dữ liệu chuỗi DNA để tối ưu hiệu quả lưu trữ. Nghiên cứu các thuật toán nén tiên tiến, giảm dung lượng, tăng tốc truy xuất dữ liệu gen.

• 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: Trường Đại học Công nghệ - Đạ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
• DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT
• 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.1.1. Mã hóa trực tiếp phần khác biệt (thuật toán 2D)
• 1.1.2. Thuật toán nén DNABIT
• 1.2. Thuật toán nén dựa trên bộ từ điển
• 1.3. Thuật toán nén xác suất thống kê
• 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
• 1.3.2. Thuật toán Expert Markov (XM)
• 1.4. Thuật toán nén tham chiếu
• 1.4.1. Đặc trưng thuật toán tham chiếu
• 1.4.2. 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.1.1. Thuật toán nén
• 2.1.2. Thư viện FRESCO
• 2.1.3. Định dạng tệp
• 2.2. Cải thiện tỉ lệ nén
• 2.3. Cải thiện thời gian
• 2.4. 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. Giới Thiệu Nén Dữ Liệu DNA Tiềm Năng Lưu Trữ Vượt Trội

Trong kỷ nguyên big data sinh học, việc quản lý và lưu trữ hiệu quả dữ liệu chuỗi DNA trở nên vô cùng cấp thiết. Dữ liệu bộ gen khổng lồ từ các nghiên cứu giải mã bộ gen, y học cá nhân hóa và sinh tin học đòi hỏi các giải pháp lưu trữ dung lượng lớn, chi phí thấp và tốc độ truy cập nhanh chóng. Nén dữ liệu DNA nổi lên như một giải pháp đầy hứa hẹn, giúp giảm thiểu chi phí lưu trữ DNA và tăng tốc độ truyền tải dữ liệu. Bài viết này sẽ đi sâu vào các phương pháp nén dữ liệu DNA tiên tiến, đánh giá hiệu quả nén DNA và khám phá các ứng dụng lưu trữ DNA tiềm năng.

1.1. Tổng Quan Về Lưu Trữ DNA và Yêu Cầu Dung Lượng

Lưu trữ DNA không chỉ là vấn đề về dung lượng mà còn liên quan đến độ bền lưu trữ DNA và khả năng phục hồi dữ liệu DNA. Bộ gen người chứa khoảng 3 tỷ cặp base, tương đương hàng gigabyte dữ liệu. Các nghiên cứu giải mã bộ gen hàng loạt tạo ra lượng dữ liệu khổng lồ, cần được lưu trữ lâu dài để phục vụ nghiên cứu và ứng dụng trong tương lai. Theo tài liệu gốc, "Bộ gen của con người gồm khoảng 3 tỉ đặc trưng trên 23 cặp nhiễm sắc thể (NST). Cơ sở dữ liệu hệ gen là vô cùng lớn và phức tạp. Để lưu trữ, truy cập và xử lý dữ liệu này một cách hiệu quả là một nhiệm vụ rất khó khăn."

1.2. Tại Sao Nén Dữ Liệu DNA Quan Trọng Trong Sinh Tin Học

Nén dữ liệu DNA là yếu tố then chốt để xử lý và phân tích hiệu quả big data sinh học. Việc phân tích dữ liệu DNA yêu cầu tài nguyên tính toán lớn, và việc giảm kích thước dữ liệu giúp giảm tải cho hệ thống, tăng tốc độ phân tích và giảm chi phí. Ngoài ra, bảo mật dữ liệu DNA cũng là một vấn đề quan trọng, và các thuật toán nén có thể được tích hợp với các phương pháp mã hóa DNA để tăng cường an ninh. Các nhà nghiên cứu liên tục tìm kiếm các thuật toán nén DNA mới để tối ưu hiệu suất và giảm chi phí lưu trữ.

II. Vấn Đề Lưu Trữ DNA Dung Lượng và Chi Phí Nén Khổng Lồ

Mặc dù có nhiều tiềm năng, việc lưu trữ dữ liệu chuỗi DNA đối mặt với những thách thức lớn. Dung lượng lưu trữ DNA cần thiết để chứa bộ gen ngày càng tăng, vượt quá khả năng đáp ứng của các phương pháp lưu trữ truyền thống. Chi phí lưu trữ DNA cũng là một rào cản lớn, đặc biệt đối với các nghiên cứu quy mô lớn và các ứng dụng thương mại. Các phương pháp nén dữ liệu hiện tại chưa đáp ứng được yêu cầu về hiệu quả nén DNA, đặc biệt là khi xử lý các chuỗi DNA phức tạp và đa dạng.

2.1. Hạn Chế Của Phương Pháp Lưu Trữ Dữ Liệu Truyền Thống

Các phương pháp lưu trữ dữ liệu truyền thống như ổ cứng và đám mây gặp khó khăn trong việc đáp ứng nhu cầu lưu trữ big data sinh học. Dung lượng lưu trữ có giới hạn, tốc độ truy cập chậm và chi phí cao là những hạn chế chính. Hơn nữa, các phương pháp này không được thiết kế đặc biệt để xử lý dữ liệu chuỗi DNA, dẫn đến hiệu suất kém và khó khăn trong việc quản lý dữ liệu. Do đó, cần có những giải pháp lưu trữ sinh học chuyên dụng để giải quyết vấn đề này.

2.2. Tại Sao Cần Nâng Cao Hiệu Quả Nén Chuỗi DNA

Việc nâng cao hiệu quả nén DNA là yếu tố then chốt để giảm chi phí lưu trữ DNA và tăng tốc độ truyền tải dữ liệu. Các thuật toán nén dữ liệu DNA hiện tại chưa khai thác hết tiềm năng của cấu trúc và đặc tính của chuỗi DNA, dẫn đến hiệu quả nén chưa cao. Cần có những nghiên cứu và phát triển các thuật toán nén DNA mới, tận dụng các kỹ thuật tiên tiến như mã hóa DNA và giải nén dữ liệu DNA để đạt được hiệu quả nén tối ưu.

III. Thuật Toán Nén Tham Chiếu JDNA Giải Pháp Lưu Trữ Tối Ưu

Trong số các phương pháp nén dữ liệu DNA khác nhau, thuật toán nén tham chiếu JDNA nổi bật như một giải pháp lưu trữ hiệu quả. Thuật toán này tận dụng sự tương đồng giữa các chuỗi DNA khác nhau để giảm thiểu kích thước dữ liệu. JDNA sử dụng một chuỗi tham chiếu làm cơ sở để mã hóa các chuỗi DNA khác, chỉ lưu trữ sự khác biệt so với chuỗi tham chiếu. Điều này giúp đạt được hiệu quả nén DNA rất cao, đặc biệt là khi xử lý các chuỗi DNA có nguồn gốc gần nhau.

3.1. Cơ Chế Hoạt Động Của Thuật Toán Nén Tham Chiếu JDNA

Thuật toán nén tham chiếu JDNA hoạt động bằng cách so sánh chuỗi DNA cần nén với một chuỗi tham chiếu. Các đoạn giống nhau được thay thế bằng tham chiếu đến chuỗi tham chiếu, trong khi các đoạn khác nhau được mã hóa riêng. Việc lựa chọn chuỗi tham chiếu phù hợp là rất quan trọng để đạt được hiệu quả nén DNA cao. Theo tài liệu gốc, "Tương tự như thuật toán nén dựa trên bộ từ điển nhưng do các chuỗi mã hóa tham chiếu tới tập hợp chuỗi tham chiếu bên ngoài nên tốc độ nén cao hơn và giải mã cũng thuận lợi hơn."

3.2. Ưu Điểm Vượt Trội Của JDNA So Với Các Thuật Toán Khác

So với các thuật toán nén dữ liệu truyền thống và các thuật toán nén dữ liệu DNA khác, JDNA có nhiều ưu điểm vượt trội. Hiệu quả nén DNA cao, tốc độ nén và giải nén nhanh chóng, và khả năng xử lý các chuỗi DNA phức tạp là những ưu điểm chính. Ngoài ra, JDNA còn được tối ưu hóa để giảm chi phí lưu trữ DNA và tăng độ bền lưu trữ DNA. Thực nghiệm cho thấy rằng JDNA vượt trội hơn so với Huffman và Lempel-Ziv.

IV. Ứng Dụng Thực Tế Lưu Trữ DNA Trong Y Học và Khoa Học

Ứng dụng lưu trữ DNA ngày càng trở nên phổ biến trong nhiều lĩnh vực, từ y học đến khoa học pháp y. Trong y học, lưu trữ DNA được sử dụng để lưu trữ thông tin bộ gen của bệnh nhân, phục vụ cho chẩn đoán bệnh, điều trị cá nhân hóa và nghiên cứu di truyền. Trong khoa học pháp y, lưu trữ DNA được sử dụng để xác định danh tính tội phạm và nạn nhân. Ngoài ra, lưu trữ DNA còn được sử dụng để bảo tồn đa dạng sinh học và lưu trữ dữ liệu lịch sử.

4.1. Lưu Trữ DNA Tiềm Năng Trong Chẩn Đoán và Điều Trị Bệnh

Lưu trữ DNA có tiềm năng cách mạng hóa ngành y học bằng cách cung cấp thông tin di truyền toàn diện cho việc chẩn đoán và điều trị bệnh. Thông tin bộ gen có thể được sử dụng để xác định nguy cơ mắc bệnh, lựa chọn phương pháp điều trị phù hợp và theo dõi hiệu quả điều trị. Theo tài liệu gốc, "Nhiều thuật toán nén dành riêng cho chuỗi DNA đã được phát triển từ khoảng 10 năm trước. Sự thật là nén chuỗi DNA là một việc khó đối với các thuật toán nén cơ bản, nhưng từ quan điểm của lý thuyết nén thì nó là một đề tài 7 thú vị cho việc tìm hiểu thuộc tính của nhiều thuật toán nén."

4.2. Bảo Tồn Đa Dạng Sinh Học Vai Trò Của Lưu Trữ DNA

Lưu trữ DNA đóng vai trò quan trọng trong việc bảo tồn đa dạng sinh học. Bằng cách lưu trữ DNA của các loài động thực vật quý hiếm, chúng ta có thể bảo vệ nguồn gen của chúng và phục hồi chúng trong tương lai. Điều này đặc biệt quan trọng trong bối cảnh biến đổi khí hậu và suy giảm đa dạng sinh học đang diễn ra trên toàn cầu. Ngoài ra, lưu trữ DNA còn có thể được sử dụng để nghiên cứu lịch sử tiến hóa của các loài.

V. Tương Lai Của Nén Dữ Liệu DNA Hướng Nghiên Cứu và Phát Triển

Nghiên cứu về nén dữ liệu DNA vẫn còn nhiều tiềm năng phát triển. Các hướng nghiên cứu chính bao gồm phát triển các thuật toán nén DNA mới với hiệu quả nén DNA cao hơn, giảm chi phí lưu trữ DNA và tăng độ bền lưu trữ DNA. Ngoài ra, cần có những nghiên cứu về bảo mật dữ liệu DNA và phục hồi dữ liệu DNA để đảm bảo an toàn và tin cậy cho các hệ thống lưu trữ DNA.

5.1. Nghiên Cứu Phát Triển Thuật Toán Nén DNA Thế Hệ Mới

Nghiên cứu và phát triển các thuật toán nén dữ liệu DNA thế hệ mới là yếu tố then chốt để khai thác hết tiềm năng của lưu trữ DNA. Các thuật toán này cần tận dụng các kỹ thuật tiên tiến như trí tuệ nhân tạo, học máy và công nghệ DNA để đạt được hiệu quả nén DNA tối ưu. Các thuật toán nén có thể được kết hợp với các phương pháp mã hóa DNA để tăng cường an ninh và bảo mật dữ liệu.

5.2. Đảm Bảo An Toàn và Bảo Mật Dữ Liệu Chuỗi DNA

Bảo mật dữ liệu DNA là một vấn đề quan trọng cần được quan tâm. Các hệ thống lưu trữ DNA cần được bảo vệ khỏi các cuộc tấn công mạng và các hành vi truy cập trái phép. Các biện pháp bảo mật bao gồm mã hóa DNA, kiểm soát truy cập và giám sát hoạt động của hệ thống. Ngoài ra, cần có các biện pháp phục hồi dữ liệu DNA để đảm bảo dữ liệu không bị mất mát trong trường hợp xảy ra sự cố.

VI. Kết Luận Nén DNA Bước Tiến Trong Lưu Trữ Dữ Liệu Sinh Học

Nén dữ liệu DNA là một giải pháp đầy hứa hẹn để giải quyết các thách thức trong việc lưu trữ big data sinh học. Các thuật toán nén DNA, đặc biệt là thuật toán nén tham chiếu JDNA, có khả năng giảm thiểu chi phí lưu trữ DNA và tăng tốc độ truyền tải dữ liệu. Với những tiềm năng to lớn, lưu trữ DNA hứa hẹn sẽ đóng vai trò quan trọng trong sự phát triển của y học, khoa học và nhiều lĩnh vực khác.

6.1. Tổng Kết Về Hiệu Quả Của Phương Pháp Nén Chuỗi DNA

Việc sử dụng các phương pháp nén dữ liệu, đặc biệt là nén dữ liệu DNA, mang lại hiệu quả rõ rệt trong việc quản lý và lưu trữ dữ liệu sinh học. Hiệu quả nén DNA cao giúp giảm chi phí và tăng tốc độ truy cập dữ liệu. Tuy nhiên, cần có những nghiên cứu và phát triển tiếp theo để tối ưu hóa các thuật toán nén và đảm bảo an toàn và bảo mật dữ liệu.

6.2. Hướng Đi Mới Trong Nghiên Cứu và Ứng Dụng Lưu Trữ DNA

Tương lai của lưu trữ DNA hứa hẹn nhiều điều thú vị. Các hướng nghiên cứu và phát triển mới bao gồm sử dụng trí tuệ nhân tạo để tối ưu hóa các thuật toán nén DNA, phát triển các phương pháp mã hóa DNA tiên tiến và khám phá các ứng dụng mới của lưu trữ DNA trong các lĩnh vực khác nhau. Với những tiến bộ này, lưu trữ DNA sẽ tiếp tục đóng vai trò quan trọng trong sự phát triển của khoa học và công nghệ.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của các công nghệ giải trình tự chuỗi đa lượng thế hệ mới đã tạo ra khối lượng dữ liệu di truyền khổng lồ cho nền y sinh học hiện đại. Một bộ gen người tiêu chuẩn chứa khoảng 3 tỉ cặp bazơ phân bố trên 23 cặp nhiễm sắc thể, đòi hỏi xấp xỉ 3 GB không gian lưu trữ thô ở định dạng 1 byte cho mỗi ký tự nucleotit. Mặc dù chi phí giải trình tự đã giảm từ hàng triệu USD xuống còn khoảng 2.000 USD cho mỗi hệ gen, sự gia tăng nhanh chóng của các ngân hàng dữ liệu di truyền quy mô hàng nghìn cá thể đang tạo ra áp lực nặng nề lên hạ tầng máy chủ, băng thông mạng và chi phí lưu trữ đám mây. Các công cụ nén văn bản tiêu chuẩn như Gzip, PKZip hay ARJ khi áp dụng lên chuỗi DNA thường không mang lại hiệu quả tối ưu do cấu trúc sinh học không phân bố ngẫu nhiên nhưng lại mang các quy luật lặp đặc thù.

Xuất phát từ thực tế hai hệ gen người ngẫu nhiên có độ tương đồng di truyền lên tới 99,9%, phương pháp nén dữ liệu dựa trên chuỗi tham chiếu mở ra tiềm năng đột phá. Luận văn Thạc sĩ chuyên ngành Hệ thống thông tin của tác giả Cao Thục Tuyết Trinh, dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Thị Hậu tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội (2016), tập trung giải quyết bài toán tối ưu hóa thuật toán nén tham chiếu thông qua việc nghiên cứu, phát triển công cụ JDNA kế thừa và cải tiến từ khung nén mã nguồn mở FRESCO. Phạm vi thực nghiệm của đề tài được triển khai trên tập dữ liệu đa dạng gồm 1092 hệ gen người, 180 hệ gen thực vật Arabidopsis thaliana và 38 hệ gen nấm men. Ý nghĩa khoa học và thực tiễn của công trình thể hiện ở việc nâng tỷ lệ nén từ mức 4:1 của các phương pháp truyền thống lên mức 500:1 đến 1000:1 trong điều kiện tối ưu, đồng thời giải quyết triệt để nút thắt cổ chai về thời gian đánh chỉ số và dung lượng bộ nhớ RAM trong xử lý dữ liệu sinh học phân tử.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng của lý thuyết thông tin Shannon và các mô hình thuật toán xử lý chuỗi sinh học hiện đại:

• Lý thuyết mã hóa Entropy và nén thống kê: Khai thác phân bố tần suất xuất hiện của 4 loại bazơ Adenine (A), Cytosine (C), Guanine (G), Thymine (T) để gán mã nhị phân có độ dài biến đổi thông qua cây Huffman mở rộng, kết hợp cùng mã hóa sai phân Delta và mã hóa số học nhằm cực tiểu hóa số bit biểu diễn cho mỗi đơn vị nucleotit.
• Mô hình nén tham chiếu và kỹ thuật cửa sổ trượt Lempel-Ziv: Khác với mô hình LZ77 hoặc LZ78 xây dựng từ điển động nội bộ trong quá trình nén, lý thuyết nén tham chiếu cố định một hệ gen chuẩn bên ngoài để mô hình hóa toàn bộ chuỗi đích thành một tập hợp ánh xạ gồm vị trí, độ dài chuỗi khớp và các sai khác di truyền.
• Mô hình thống kê chuỗi Markov (eXpert Markov - XM): Sử dụng các chuyên gia xác suất bậc cao để dự đoán các cấu trúc lặp xuôi, lặp nghịch đảo và các vùng bảo tồn tiến hóa.

Bên cạnh đó, nghiên cứu vận dụng 4 khái niệm cốt lõi trong biến dị di truyền học: Đa hình đơn nucleotit (SNP - biến đổi tại một vị trí bazơ duy nhất), phép thay thế (Substitution), phép chèn (Insertion) và phép xóa (Deletion). Để quản lý mức độ phức tạp, thuật toán xác định ngưỡng kích thước biến dị $\theta = 300$ nhằm phân loại thành biến dị nhỏ (SD) khi độ dài dưới 300 bazơ và biến dị lớn (BD) khi độ dài vượt quá 300 bazơ. Đồng thời, cấu trúc bảng băm K-mer (K-mer table) được thiết kế đặc thù để tạo chỉ số tra cứu chuỗi con nhanh chóng.

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

Nghiên cứu sử dụng phương pháp mô hình hóa thuật toán kết hợp thực nghiệm so sánh định lượng trên môi trường điện toán:

• Nguồn dữ liệu và cỡ mẫu: Bộ dữ liệu kiểm thử bao gồm 1092 mẫu hệ gen người từ dự án 1000 Genomes Project, 180 mẫu hệ gen loài cỏ Arabidopsis thaliana và 38 mẫu vi khuẩn nấm men. Việc lựa chọn các tập dữ liệu từ đơn bào đến sinh vật bậc cao nhằm đánh giá tính tổng quát của thuật toán trên các mức độ tương đồng di truyền khác nhau. Dữ liệu được nạp vào bộ nhớ theo các khối phân đoạn chuẩn 250 MB để kiểm soát tài nguyên.
• Phương pháp chọn mẫu: Lấy mẫu phân tầng đại diện cho từng nhóm loài sinh học, đảm bảo bao phủ cả các hệ gen có độ thuần nhất cao lẫn các chủng có độ biến dị lớn.
• Phương pháp phân tích và đo lường: Tác giả xây dựng công cụ JDNA bằng ngôn ngữ Java, kế thừa thư viện C++ FRESCO. Mọi kịch bản đo đạc đều được lặp lại 10 lần độc lập để lấy giá trị trung bình chính xác trên 3 chỉ số then chốt: tỷ lệ nén (tính theo tỷ số kích thước gốc trên kích thước nén và số bit/bazơ), thời gian nén/giải nén (giây), và lượng bộ nhớ RAM cực đại tiêu thụ (Megabyte/Gigabyte). Lý do lựa chọn giải pháp đánh chỉ số theo yêu cầu (On-demand Indexing) là nhằm khắc phục triệt để tình trạng tiêu tốn hơn 95% thời gian cho việc lập chỉ số toàn cục của các giải thuật truyền thống. Toàn bộ quá trình nghiên cứu và thực nghiệm được tiến hành hoàn chỉnh vào năm 2016.

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

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

Quá trình phân tích thực nghiệm giữa JDNA và các nhóm thuật toán kinh điển mang lại 4 phát hiện quan trọng:

1. Vượt trội về tỷ lệ nén so với các giải thuật truyền thống: Trong khi phương pháp mã hóa bit trực tiếp (Naïve bit) chỉ đạt tỷ lệ nén tối đa 4:1 (tương đương 2 bit/bazơ, tiết kiệm 75% không gian), thuật toán từ điển Lempel-Ziv (LZ77, LZ78) đạt 4:1 đến 6:1, và thuật toán thống kê Huffman đạt 4:1 đến 8:1, thì JDNA đạt tỷ lệ nén từ 500:1 đến 1000:1 khi xử lý hệ gen người cùng loài có độ tương đồng 99,9%. Hiệu quả lưu trữ của JDNA cao gấp hơn 100 lần so với các thuật toán không sử dụng chuỗi tham chiếu.
2. Cải thiện căn bản thời gian thực thi nhờ đánh chỉ số theo yêu cầu: Phân tích quy trình của khung FRESCO nguyên bản chỉ ra rằng giai đoạn đánh chỉ số toàn bộ gen tham chiếu chiếm tới trên 95% tổng thời gian thực hiện, trong khi pha nén thực tế chỉ tiêu tốn 2% và các tác vụ đọc ghi khác chiếm 3%. JDNA đã thay thế cơ chế này bằng quy trình 3 bước: (1) Kiểm tra SNP đơn lẻ; (2) Tìm kiếm cục bộ trong phạm vi cửa sổ $6 \times K$ bazơ chứa hầu hết các biến dị nhỏ; (3) Chỉ đánh chỉ số từng phần khi hai bước trên không tìm thấy đoạn khớp. Giải pháp này giúp cắt giảm hơn 90% thời gian xử lý chỉ số dư thừa.
3. Tối ưu hóa dung lượng RAM tiêu thụ hơn 88%: Việc sử dụng các cấu trúc đối tượng tiêu chuẩn trong Java như HashMap với 50.000 ngăn chứa từng khiến mức chiếm dụng bộ nhớ vượt quá 20 GB cho một nhiễm sắc thể. JDNA đã thay thế bằng cấu trúc MultiValueMap tự thiết kế dựa trên mảng số nguyên nguyên thủy 2 chiều và mảng đếm phụ trợ, giúp khống chế lượng RAM sử dụng ổn định trong ngưỡng 2,0 GB đến 2,5 GB.
4. Cơ chế phân khối 250 MB và xử lý định dạng linh hoạt: JDNA hỗ trợ toàn diện cả định dạng tệp thô RAW (xuất ra tệp nén CRAW) và định dạng chuẩn sinh học FASTA (xuất ra cặp tệp CRAW và CCOM chứa thông tin chú thích dòng). Cơ chế chia nhỏ tệp đầu vào thành các khối độc lập 250 MB cho phép chương trình xử lý trơn tru các nhiễm sắc thể kích thước hàng trăm Megabyte mà không gặp hiện tượng tràn bộ nhớ heap.

Thảo luận kết quả

Hiệu năng đột phá của thuật toán nén tham chiếu JDNA bắt nguồn từ đặc tính bảo tồn cao của quá trình tiến hóa sinh học. Do 99,9% cấu trúc DNA giữa các cá thể người là trùng khớp hoàn toàn, việc lưu trữ toàn bộ các đoạn bazơ lặp lại là không cần thiết; hệ thống chỉ cần ghi nhận tọa độ bắt đầu, độ dài chuỗi khớp và danh sách các biến dị sai khác. Minh chứng điển hình được thể hiện qua thực nghiệm nén hệ gen của nhà khoa học James Watson với hệ gen chuẩn hg18: Dung lượng ban đầu 2991 MB được nén xuống chỉ còn 6,99 MB (tỷ lệ nén đạt ~428:1), trong khi công cụ nén phổ thông Gzip chỉ giảm được xuống 834 MB (đạt tỷ lệ ~3,5:1).

Trong các báo cáo học thuật, dữ liệu thực nghiệm này có thể được mô tả trực quan thông qua biểu đồ thanh phân bổ thời gian (làm nổi bật sự thu hẹp của thanh đánh chỉ số từ 95% xuống mức tối thiểu) và bảng đối chiếu đa tiêu chí so sánh trực tiếp kích thước tệp nén, tỷ lệ nén (bits/base) và dung lượng bộ nhớ giữa các thuật toán JDNA, FRESCO, GDC, RLZ, Huffman và LZ77. Mặc dù vẫn còn độ trễ nhất định khi nén các loài có mức độ sai khác di truyền lớn, JDNA đã khẳng định ưu thế vượt trội khi xử lý dữ liệu quy mô lớn trong cùng một loài sinh vật.

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

Dựa trên các kết quả nghiên cứu đã đạt được, 4 khuyến nghị hành động cụ thể được đề xuất nhằm ứng dụng và mở rộng công nghệ:

• Tối ưu hóa xử lý song song trên phần cứng đa lõi và GPU: Tái cấu trúc module băm K-mer và thuật toán so khớp chuỗi cục bộ bằng cách ứng dụng OpenMP và kiến trúc tính toán CUDA trên GPU. Mục tiêu nâng thông lượng nén dữ liệu từ mức 35 MB/s lên trên 150 MB/s, thực hiện trong lộ trình 6 tháng bởi đội ngũ kỹ sư phần mềm tin sinh học.
• Triển khai JDNA vào hệ thống lưu trữ đám mây y sinh: Tích hợp bộ giải nén JDNA trực tiếp vào các trung tâm dữ liệu đám mây (AWS S3 Glacier, Google Cloud Life Sciences) nhằm cắt giảm từ 85% đến 95% chi phí lưu trữ định kỳ hàng năm cho các kho dữ liệu quy mô trên 500 Terabyte, hoàn thành trong vòng 12 tháng do các kiến trúc sư hạ tầng đám mây chủ trì.
• Xây dựng bộ thư viện chọn lọc tham chiếu đa hệ gen (Pan-genome Reference Library): Nghiên cứu phát triển thuật toán tự động chọn lọc chuỗi tham chiếu tối ưu theo từng nhóm chủng tộc hoặc quần thể sinh học, nâng tỷ lệ nén thêm 30% đến 40% đối với các mẫu có tính đa hình cao, thực hiện trong 9 tháng bởi các nhà sinh học tính toán.
• Chuẩn hóa giao diện lập trình ứng dụng (API) cho truy xuất ngẫu nhiên: Phát triển bộ SDK hoàn chỉnh hỗ trợ truy vấn ngẫu nhiên trực tiếp trên tệp nén CRAW mà không cần giải nén toàn bộ tệp, duy trì độ trễ truy xuất dưới 20 mili-giây cho mỗi đoạn gen, lộ trình thực hiện 12 tháng do các chuyên gia phát triển phần mềm mã nguồn mở đảm nhiệm.

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

Nội dung luận văn mang lại giá trị thực tiễn và học thuật sâu sắc cho 4 nhóm đối tượng:

• Kỹ sư hệ thống và kiến trúc sư dữ liệu y sinh: Cung cấp giải pháp kỹ thuật tối ưu hóa không gian đĩa cứng, giúp tiết kiệm hàng triệu USD chi phí hạ tầng khi xây dựng các trung tâm dữ liệu lưu trữ hàng trăm nghìn bộ gen người.
• Nghiên cứu sinh và học viên cao học ngành Tin sinh học / Hệ thống thông tin: Tài liệu tham khảo chuẩn mực về phương pháp luận nghiên cứu nén dữ liệu sinh học, kỹ thuật mô hình hóa entropy, cấu trúc dữ liệu mảng nâng cao và quy trình tối ưu hóa giải thuật K-mer băm.
• Chuyên viên kỹ thuật tại các viện nghiên cứu di truyền và trung tâm xét nghiệm DNA: Ứng dụng mô hình phân khối 250 MB và xử lý tệp FASTA/RAW để tối ưu hóa đường truyền dữ liệu giải trình tự HTS giữa các phòng thí nghiệm và máy chủ phân tích.
• Nhà phát triển phần mềm mã nguồn mở: Khai thác nền tảng mã nguồn của FRESCO và JDNA để viết tiếp các plugin tích hợp vào các hệ sinh thái phân tích hệ gen phổ biến như Galaxy, Bioconductor hoặc SAMtools.

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

1. Tại sao các phần mềm nén tệp thông thường như Gzip hay WinRAR hoạt động kém hiệu quả trên chuỗi DNA? Các phần mềm thông thường được thiết kế cho văn bản ký tự ngẫu nhiên hoặc tệp nhị phân đa dạng. Khi nén chuỗi DNA gồm 4 ký tự A, C, G, T, các phần mềm này chỉ đạt tỷ lệ nén dưới 4:1 (khoảng 2 bit/bazơ), thậm chí làm phình to kích thước tệp do phần bù tiêu đề, trong khi nén tham chiếu khai thác được sự trùng khớp di truyền 99,9% để đạt tỷ lệ 1000:1.

2. Kỹ thuật đánh chỉ số theo yêu cầu (On-demand Indexing) trong JDNA mang lại lợi ích gì? Trong các công cụ nén tham chiếu truyền thống như FRESCO, việc đánh chỉ số toàn bộ gen chuẩn chiếm trên 95% tổng thời gian chạy. JDNA kiểm tra nhanh SNP và tìm kiếm trong phạm vi cửa sổ cục bộ $6 \times K$ bazơ trước, chỉ lập chỉ số từng phần khi chuỗi có đột biến lớn, giúp giảm hơn 90% thời gian đánh chỉ số thừa.

3. Làm thế nào JDNA khống chế mức tiêu thụ bộ nhớ RAM không vượt quá 2,5 GB? Thay vì dùng đối tượng Java HashMap phức tạp tiêu tốn hơn 20 GB RAM, JDNA xây dựng cấu trúc MultiValueMap từ mảng số nguyên nguyên thủy hai chiều kết hợp mảng đếm phụ trợ. Cấu trúc này vừa loại bỏ rác bộ nhớ của các đối tượng Java vừa cho phép tái sử dụng bảng băm K-mer bằng cách gán lại mảng đếm về 0.

4. Thuật toán JDNA xử lý các loại biến dị di truyền nào trong chuỗi gen? JDNA hỗ trợ xử lý đầy đủ 4 loại biến dị sinh học: Đột biến điểm đơn nucleotit (SNP), phép thay thế đoạn bazơ, phép chèn thêm đoạn bazơ và phép xóa đoạn bazơ. Thuật toán sử dụng ngưỡng $\theta = 300$ để phân tách và áp dụng chiến lược mã hóa tối ưu riêng cho từng nhóm biến dị nhỏ và biến dị lớn.

5. Định dạng đầu ra CRAW và CCOM của JDNA có hỗ trợ khôi phục dữ liệu gốc chính xác không? JDNA là thuật toán nén hoàn toàn không mất dữ liệu (lossless). Quá trình giải nén sẽ kết hợp tệp CRAW (chứa chuỗi khớp nhị phân) và tệp CCOM (chứa thông tin chú thích dòng) cùng hệ gen tham chiếu ban đầu để tái tạo lại 100% nội dung tệp thô RAW hoặc tệp định dạng FASTA gốc.

Kết luận

• Luận văn đã hệ thống hóa toàn diện các phương pháp nén dữ liệu chuỗi DNA, chỉ rõ sự vượt trội mang tính đột phá của hướng tiếp cận nén dựa trên chuỗi tham chiếu.
• Công cụ JDNA được phát triển thành công dựa trên nền tảng FRESCO, tích hợp cơ chế đánh chỉ số theo yêu cầu giúp loại bỏ 95% thời gian tạo chỉ số dư thừa.
• Giải quyết triệt để bài toán chiếm dụng bộ nhớ trong Java bằng cấu trúc MultiValueMap tối ưu, hạ mức tiêu thụ RAM từ trên 20 GB xuống ổn định ở mức 2,0 GB đến 2,5 GB.
• Xác lập tỷ lệ nén vượt trội từ 500:1 đến 1000:1 trên các tập dữ liệu hệ gen người quy mô lớn, vượt xa mức 4:1 của các thuật toán nén truyền thống.
• Định hình rõ lộ trình phát triển giai đoạn tiếp theo tập trung vào song song hóa GPU và tích hợp API truy xuất ngẫu nhiên phục vụ các kho dữ liệu y sinh đám mây.

Đóng góp cốt lõi của công trình là giải pháp dung hòa hoàn hảo giữa tỷ lệ nén cực đại, tốc độ xử lý nhanh và yêu cầu phần cứng tối thiểu cho bài toán lưu trữ hệ gen. Để tiếp cận toàn bộ mô hình thuật toán, mã nguồn thực nghiệm và bảng thông số đo đạc chi tiết, các nhà nghiên cứu và kỹ sư hệ thống có thể tham khảo toàn văn luận văn thạc sĩ tại thư viện Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội.

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ộ.