I. Đánh chỉ số tài liệu và tài liệu XML trong tin sinh học tính toán
Luận án tập trung vào vấn đề đánh chỉ số tài liệu XML trong lĩnh vực tin sinh học. Dữ liệu tin sinh học hiện nay rất lớn, thường đạt đến Giga, Tera Byte. Các nguồn dữ liệu như SRA, NCBI Genome, ensembl.org chứa nhiều tài liệu XML tin sinh học. Tài liệu XML có cấu trúc bán cấu trúc, linh hoạt nhưng gây khó khăn cho việc truy vấn hiệu quả. Vì vậy, đánh chỉ số là cần thiết để tối ưu hóa truy vấn, giảm thiểu thời gian truy xuất đĩa cứng. Quản lý dữ liệu sinh học hiệu quả đòi hỏi phương pháp đánh chỉ số phù hợp. Các truy vấn Xpath đòi hỏi giải pháp đánh chỉ số đặc thù. Luận án đề cập đến việc xử lý XML và áp dụng kỹ thuật indexing techniques để giải quyết vấn đề này. Sinh học dữ liệu phức tạp cần phân tích dữ liệu sinh học và phân tích trình tự hiệu quả.
1.1. Thách thức của dữ liệu XML tin sinh học
Kích thước khổng lồ của dữ liệu XML tin sinh học là thách thức lớn. Các cơ sở dữ liệu sinh học truyền thống gặp khó khăn trong việc lưu trữ và truy vấn dữ liệu này. Sinh học dữ liệu thường gồm hai phần: dữ liệu sinh học (DNA, protein,...) và dữ liệu mô tả. Cấu trúc tài liệu XML có thể khác nhau do tùy biến của các cá nhân, tổ chức. Việc truy xuất dữ liệu từ đĩa cứng chậm hơn nhiều so với RAM. Do đó, đánh chỉ số cần tối ưu hóa số lần truy xuất đĩa và tận dụng bộ nhớ chính. Các truy vấn, ví dụ truy vấn Xpath, truy vấn tương đồng trình tự DNA, đòi hỏi thuật toán đánh chỉ số hiệu quả. Giải pháp truyền thống gặp nhiều hạn chế với dữ liệu lớn. Đánh chỉ số truyền thống sinh ra dữ liệu chỉ số lớn hơn dữ liệu gốc, gây khó khăn cho lưu trữ và truy vấn. Vì vậy, cần phương pháp đánh chỉ số mới hiệu quả hơn. Khai phá dữ liệu sinh học đòi hỏi giải pháp tối ưu.
1.2. Phương pháp đánh chỉ số hiện có và hạn chế
Các phương pháp đánh chỉ số hiện có thường gặp khó khăn với tài liệu XML lớn. Phương pháp truyền thống thường tạo ra chỉ số kích thước lớn, gây khó khăn về lưu trữ và hiệu năng truy vấn. XML parsing và xử lý XML là bước quan trọng, nhưng chưa tối ưu. Do đó, luận án đề xuất chia tài liệu XML thành hai phần (dữ liệu cấu trúc và dữ liệu sinh học) và áp dụng các phương pháp đánh chỉ số khác nhau. Việc chuyển đổi dữ liệu văn bản sang dạng số nhằm giảm kích thước và cải thiện tốc độ truy vấn. Cơ sở dữ liệu không gian và kỹ thuật spatial indexing được xem xét. Các indexing techniques cần phù hợp với đặc điểm của dữ liệu và truy vấn. Mở rộng khả năng của hệ thống là mục tiêu. Hiệu năng truy vấn là tiêu chí quan trọng. Thuật toán tìm kiếm gần nhất cũng được nghiên cứu. Khoảng cách không gian được sử dụng để định lượng hiệu quả.
II. R tree và thuật toán đánh chỉ số đề xuất
Luận án đề xuất sử dụng cấu trúc R-tree như một giải pháp đánh chỉ số cho tài liệu XML tin sinh học. R-tree là một cấu trúc dữ liệu cơ sở dữ liệu không gian, phù hợp với việc tìm kiếm không gian. Thuật toán R-tree được cải tiến để tối ưu hóa cho truy vấn Xpath. Luận án trình bày thuật toán đánh chỉ số mới, BioX-tree và BioX+-tree, dựa trên thuật toán R-tree. Cấu trúc R-tree được điều chỉnh để phù hợp với đặc điểm của tài liệu XML. Thuật toán chèn và thuật toán truy vấn được thiết kế lại. Mô hình dữ liệu được chuyển đổi thành dạng số trước khi áp dụng R-tree. Đánh giá hiệu năng được thực hiện thông qua các thí nghiệm. So sánh thuật toán với thuật toán R-tree gốc được thực hiện. Mở rộng khả năng của BioX-tree dẫn đến BioX+-tree. Thuật toán tìm kiếm gần nhất được cải thiện. Khoảng cách không gian được tính toán chính xác hơn.
2.1. BioX tree Thuật toán đánh chỉ số cải tiến
BioX-tree là một thuật toán đánh chỉ số cải tiến dựa trên R-tree. Phương pháp đánh chỉ số này tối ưu hóa cho truy vấn Xpath trên tài liệu XML tin sinh học. Quá trình chuyển đổi tài liệu XML thành dữ liệu không gian được mô tả chi tiết. Cấu trúc chỉ số trên cây BioX-tree được thiết kế để giảm thời gian truy vấn. Thuật toán chèn mới đảm bảo hiệu quả. Thuật toán truy vấn được tối ưu hóa cho các truy vấn Xpath, bao gồm truy vấn tổ tiên, hậu duệ, anh em. Xử lý truy vấn được thực hiện hiệu quả. Đánh giá độ phức tạp của thuật toán được phân tích. Kết quả thực nghiệm cho thấy hiệu quả của BioX-tree so với R-tree gốc, đặc biệt với các truy vấn anh em. Hiệu năng truy vấn được cải thiện đáng kể. Mô hình dữ liệu được tối ưu. Khả năng mở rộng của BioX-tree được đánh giá.
2.2. BioX tree Mở rộng thuật toán và đánh giá hiệu năng
BioX+-tree là phiên bản mở rộng của BioX-tree, khắc phục một số hạn chế của phiên bản trước. Phân tích không gian dữ liệu được thực hiện kỹ hơn. Các thuật toán được cải tiến để xử lý hiệu quả hơn các loại truy vấn khác nhau. Kết quả thực nghiệm so sánh BioX+-tree và BioX-tree được trình bày. Mô hình và môi trường thử nghiệm được mô tả chi tiết. So sánh kết quả cho thấy sự cải thiện đáng kể về hiệu năng. Hiệu quả giảm kích thước dữ liệu được đánh giá. Các thông số đánh giá hiệu năng được sử dụng là các performance evaluation metrics. Benchmarking được thực hiện để so sánh với các phương pháp khác. Khả năng mở rộng của hệ thống được xem xét, đặc biệt là scalability với dữ liệu lớn và dữ liệu đa chiều.
III. Kết luận và ứng dụng
Luận án đã đề xuất hai thuật toán đánh chỉ số mới, BioX-tree và BioX+-tree, dựa trên R-tree, để xử lý hiệu quả tài liệu XML tin sinh học. Các thuật toán này đã được chứng minh hiệu quả qua các thí nghiệm. BioX-tree và BioX+-tree cải thiện hiệu năng truy vấn, giảm thời gian truy xuất đĩa cứng. Tuy nhiên, việc cải tiến cấu trúc R-tree cũng gây ra một số hạn chế. Phân tích dữ liệu sinh học trở nên dễ dàng hơn. Quản lý dữ liệu sinh học hiệu quả. Ứng dụng thực tế của luận án là cải thiện tốc độ truy vấn trong các cơ sở dữ liệu sinh học. Hệ thống quản trị cơ sở dữ liệu (DBMS) có thể tích hợp các thuật toán này. Phát triển phần mềm sinh học sẽ được hỗ trợ. Dữ liệu lớn trong lĩnh vực sinh học tính toán được xử lý tốt hơn. Học máy sinh học được hỗ trợ hiệu quả hơn.
