Luận án tiến sĩ: Phương pháp đánh chỉ số cho tài liệu XML tin sinh học dựa trên R-tree

Luận án tiến sĩ phân tích phương pháp đánh chỉ số cho tài liệu xml tin sinh học dựa trên r tree, xây dựng cơ sở lý luận, kiểm chứng thực nghiệm, đóng góp tri thức mới cho ngành.

• Tác giả: Đinh Đức Lương
• Người hướng dẫn: TS. Hoàng Đỗ Thanh Tùng
• Trường học: Học viện Khoa học và Công nghệ
• Chuyên ngành: Cơ sở toán học cho tin học
• Đề tài: Phương Pháp Đánh Chỉ Số Tài Liệu XML Tin Sinh Học Dựa Trên R-Tree
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• Danh mục các thuật ngữ
• Bảng các ký hiệu, từ viết tắt
• Danh sách bảng
• Danh sách các thuật toán
• Danh sách hình vẽ
• MỞ ĐẦU
• 1. CHƯƠNG 1: Tin sinh học và các nguồn dữ liệu
• 1.1. Tin sinh học
• 1.2. Các nguồn dữ liệu

Tóm tắt

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.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Phương pháp đánh chỉ số cho tài liệu XML tin sinh học dựa trên R-tree" được thực hiện bởi nghiên cứu sinh Đinh Đức Lương, dưới sự hướng dẫn khoa học của TS. Hoàng Đỗ Thanh Tùng và PGS. Đặng Hữu Đạo. Công trình được bảo vệ năm 2019 tại Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam, thuộc chuyên ngành Cơ sở toán học cho tin học (mã số: 9 46 01 10).

Tính cấp thiết và khoảng trống nghiên cứu

Sự phát triển của các công nghệ giải trình tự sinh học đã tạo ra khối lượng dữ liệu khổng lồ được chia sẻ công khai qua các cơ sở dữ liệu quốc tế như Sequence Read Archive (SRA), National Center for Biotechnology Information (NCBI) Genome hay cổng Ensembl (BioMart). Các tài liệu sinh học này thường được phân phối dưới dạng tài liệu XML – một mô hình dữ liệu bán cấu trúc bao gồm hai thành phần: dữ liệu sinh học (chuỗi DNA, protein, thông tin phân loài) và dữ liệu mô tả cấu trúc bằng các thẻ (tags). Kích thước của các tệp XML tin sinh học đã đạt đến quy mô Gigabyte và Terabyte.

Do kích thước vượt quá dung lượng bộ nhớ chính (RAM), các tài liệu XML này bắt buộc phải lưu trữ và khai thác trên bộ nhớ ngoài (ổ đĩa cứng) hoặc các hệ thống lưu trữ phân tán. Cơ chế truy xuất đĩa cứng hoạt động tuần tự theo các khối (block) hoặc cung từ (sector), có tốc độ chậm hơn truy xuất bộ nhớ RAM hơn 100.000 lần, trở thành nút thắt cổ chai trong việc xử lý và truy vấn dữ liệu.

Các phương pháp đánh chỉ số truyền thống dành cho dữ liệu văn bản XML bộc lộ nhiều hạn chế: kích thước chỉ số sinh ra thường rất lớn, thậm chí vượt qua kích thước tệp gốc, gây áp lực lên không gian lưu trữ và làm giảm hiệu quả nén cũng như tốc độ xử lý câu truy vấn. Việc áp dụng trực tiếp cấu trúc chỉ số không gian đa chiều kinh điển như R-tree lên dữ liệu XML đã chuyển đổi sang tọa độ số gặp phải hiện tượng duyệt dư thừa các nhánh cây trên đĩa cứng đối với các truy vấn cấu trúc XPath đặc thù (như quan hệ anh em - sibling, con cái - child). Từ thực tế đó, luận án xác định khoảng trống nghiên cứu cần giải quyết là xây dựng phương pháp đánh chỉ số cải tiến dựa trên R-tree nhằm giảm thiểu số lần truy xuất đĩa cứng (thao tác I/O) khi thực thi các truy vấn XPath trên dữ liệu XML tin sinh học.

Mục tiêu nghiên cứu

Luận án xác định hai mục tiêu nghiên cứu cụ thể:

1. Nghiên cứu phương pháp đánh chỉ số dựa trên phương pháp R-tree nhằm tăng hiệu quả các truy vấn XPath trên dữ liệu XML, thông qua dữ liệu trung gian được chuyển đổi về dạng tọa độ số của các thẻ (tags), áp dụng cho dữ liệu mục tiêu là tài liệu XML tin sinh học.
2. Sử dụng phương pháp chuyển đổi dữ liệu văn bản có cấu trúc XML về dữ liệu dạng số biểu diễn được trên không gian 2 chiều (có khả năng mở rộng lên nhiều chiều), nhằm giảm kích thước dữ liệu gốc ban đầu và tạo cơ sở áp dụng cấu trúc chỉ số đề xuất.

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Cấu trúc tài liệu XML tin sinh học; các phương pháp chuyển đổi dữ liệu bán cấu trúc sang không gian số; các trục truy vấn trong ngôn ngữ XPath; cấu trúc chỉ số cây R-tree và các thuật toán quản lý không gian đa chiều; mô hình bộ nhớ ngoài và tối ưu hóa chi phí vào/ra (I/O) dữ liệu.
• Phạm vi nghiên cứu: Luận án tập trung giải quyết bài toán đánh chỉ số dữ liệu cấu trúc (dữ liệu các thẻ tag) để phục vụ các truy vấn XPath; đối với dữ liệu sinh học dạng chuỗi ký tự (như chuỗi DNA để tìm kiếm tương đồng xấp xỉ), luận án dừng lại ở mức độ khảo sát lý thuyết và định hướng nghiên cứu tiếp theo. Dữ liệu thực nghiệm bao gồm các tệp XML sinh học thực tế: DNACorn (dữ liệu DNA ngô), DNARice (dữ liệu DNA lúa gạo), Swissprot (dữ liệu protein) và Allhomologies (dữ liệu tương đồng di truyền).

---

Tổng quan tài liệu và vị trí của luận án

Luận án tiến hành khảo sát và phân loại các công trình nghiên cứu liên quan theo hai hướng tiếp cận chính: đánh chỉ số dữ liệu sinh học và đánh chỉ số tài liệu XML.

Các hướng nghiên cứu đánh chỉ số dữ liệu sinh học

Tác giả phân chia các phương pháp đánh chỉ số cơ sở dữ liệu sinh học thành hai nhóm:

1. Nhóm so sánh tương đồng thông qua chuỗi đại diện: Sử dụng các thuật toán so sánh phân đoạn chuỗi để tìm kiếm vị trí tương đồng giữa hai trình tự DNA hoặc protein.
   • Thuật toán Smith - Waterman và thuật toán BLAST: Các phương pháp cơ bản với độ phức tạp tính toán $O(mn)$, trong đó $m$ và $n$ là độ dài các chuỗi con.
   • Các biến thể cải tiến từ BLAST: FLASH, PatternHunter, BLAT, Piers nhằm phát hiện các đoạn tương đồng trên tập dữ liệu lớn khi thực hiện nhiều truy vấn con.
   • Kỹ thuật lọc và tinh lọc (filter and refine): Thuật toán Twee-Hee Ong (phát triển từ FASTA) và thuật toán Paper/Papers (phát triển thành phương pháp Similar multi-step).
   • Các kỹ thuật khác: Suffix array scans, RAMdb (Rapid Access Motif database) và Dynamic programming.
2. Nhóm sử dụng sự biến đổi cấu trúc chỉ số: Can thiệp vào cấu trúc chỉ số thông qua các phép biến đổi toán học (wavelet, phân tích ma trận, thống kê bộ gen, biến đổi tần số) để chuyển đổi sang không gian vectơ.
   • Các công cụ điển hình: ProperSearch, CAFE.
   • Kỹ thuật không gian mêtric và thống kê: Các nghiên cứu của Kahveci & Singh, Williams & Zobel, Ozturk & Ferhatosmanoglu, cùng các biến thể của Jeong, Jiang.
   • Cấu trúc chỉ số bitmap và bao phủ: BIS (Bitmap Indexing Structure) và IDC (Incrementally Decreasing Cover).

Các hướng nghiên cứu đánh chỉ số và nén tài liệu XML

Đối với dữ liệu bán cấu trúc XML, các công trình tiền đề tập trung vào nén, mã hóa đường dẫn và chuyển đổi không gian:

• Phương pháp nén và tóm tắt cấu trúc: XGrind (Tolani & Haritsa) thay thế tên phần tử và thuộc tính bằng ký tự duy nhất; Xpress (Min et al.) sử dụng toán học nghịch đảo mã hóa đường dẫn nhãn; XQzip (Cheng & NG) dùng cây chỉ số cấu trúc SIT (Structure Index Tree); XQueC (Arion et al.) dùng cây tóm tắt cấu trúc (structure summary tree); Arroyuelo et al. sử dụng cây đánh nhãn kết hợp mảng bit (bit array); Qian et al. tách riêng phần cấu trúc và nội dung để nén độc lập.
• Phương pháp đánh số trên lược đồ và phép nối cấu trúc: Hệ thống XISS (Li & Moon) sử dụng cây $B^+$-tree kết hợp cơ chế đánh số cải tiến từ Dietz với cặp giá trị <order; size> cho mỗi node. XISS xử lý các biểu thức đường dẫn bằng cách phân rã thành các biểu thức con và thực hiện các phép nối: EA-Join (nối phần tử - thuộc tính), EE-Join (nối phần tử - phần tử) và KC-Join (sử dụng bao đóng Kleene $+$, $*$ cho các biểu thức lặp).
• Phương pháp chuyển đổi sang không gian đa chiều: Nghiên cứu MDX (Multidimensional Approach to Indexing XML) mô hình hóa cây XML thành các vectơ đường dẫn từ gốc đến lá trong không gian đa chiều, sử dụng 3 cấu trúc chỉ số: Term index ($idT$), Labeled Path index ($LPID$) và Path index ($PID$).
• Phương pháp ánh xạ quan hệ và đồ thị: Kỹ thuật GRIPP (GRaph Indexing based on Pre- and Postorder numbering) tìm đường dẫn tối ưu dựa trên đường đi Hamilton thông qua các giải thuật Heuristic; phương pháp Bộ tăng tốc XPath (XPath Accelerator) biểu diễn các node XML trong không gian 5 chiều: $entry(E) = {pre(E), post(E), par(E), att(E), tag(E)}$ và áp dụng cây R-tree để đánh chỉ số.
• Cải tiến R-tree cho XML: Các công trình phát triển biến thể cây XR-tree và AR*-tree.

Hướng tiếp cận	Công trình / Tác giả tiêu biểu	Đặc điểm kỹ thuật chính
Nén XML dựa trên đường dẫn	XGrind, Xpress, XQzip, XQueC	Thay thế nhãn thẻ, mã hóa toán học nghịch đảo, cây tóm tắt cấu trúc
Đánh số lược đồ & Phép nối	XISS (Li & Moon)	Cặp giá trị <order; size>, chỉ số $B^+$-tree, các phép nối EA-Join, EE-Join, KC-Join
Không gian đa chiều	MDX	Biểu diễn đường dẫn dạng vectơ đa chiều ($idT, LPID, PID$)
Đồ thị & Heuristic	GRIPP	Đánh số thứ tự duyệt cây, xấp xỉ đường đi Hamilton
Không gian 5 chiều & R-tree	XPath Accelerator	Bộ dữ liệu 5 chiều ${pre, post, par, att, tag}$, truy vấn cửa sổ SQL
Chỉ số không gian cải tiến	XR-tree, AR*-tree, BioX-tree (Luận án)	Tối ưu hóa MBR và cấu trúc liên kết node lá trên không gian tọa độ số

Khoảng trống luận án lựa chọn giải quyết

Các phương pháp không gian đa chiều như XPath Accelerator hay R-tree truyền thống khi quản lý các điểm dữ liệu chuyển đổi từ cây XML thường phân chia các hình chữ nhật bao quanh tối thiểu (MBR) thuần túy theo tiêu chí không gian hình học. Khi thực hiện các truy vấn XPath như truy vấn anh em (sibling) hoặc con cái (child), giải thuật tìm kiếm của R-tree buộc phải duyệt ngược lên các node cha và quét qua nhiều node trung gian không chứa kết quả, làm tăng số lượng thao tác đọc đĩa I/O. Luận án lựa chọn giải quyết trực tiếp việc tái cấu trúc các node lá và thiết lập thuật toán chèn, tìm kiếm chuyên biệt để tối ưu hóa việc truy xuất dữ liệu trên đĩa cứng.

---

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

Cơ sở lý thuyết và các khái niệm cốt lõi

Luận án xây dựng trên các nền tảng lý thuyết:

1. Mô hình tài liệu XML và chuẩn XPath: Tài liệu XML được mô hình hóa thành một cấu trúc cây phân cấp gồm các phần tử (element) và thuộc tính (attribute). Chuẩn XPath cung cấp 13 trục quan hệ để định hướng tìm kiếm từ một node bối cảnh: self, parent, child, ancestor, ancestor-or-self, descendant, descendant-or-self, following, following-sibling, preceding, preceding-sibling, attribute, namespace.
2. Cơ chế đánh số thứ tự duyệt cây của Dietz: Mỗi thẻ trong cây XML được gán một cặp tọa độ số dựa trên hai phép duyệt:
   • Duyệt cây theo thứ tự trước (pre-order): Đánh số tuần tự tăng dần từ trên xuống dưới theo thứ tự thăm node.
   • Duyệt cây theo thứ tự sau (post-order): Đánh số tuần tự tăng dần từ trái qua phải sau khi các cây con đã được duyệt hoàn tất.
   • Quan hệ tổ tiên - hậu duệ (Ancestor - Descendant, A-D) giữa hai node $x$ và $y$ được xác định theo công thức: $$x = \text{ancestor}(y) \iff pre(x) < pre(y) \land post(x) > post(y)$$
3. Mô hình bộ nhớ ngoài (I/O Model): Cơ sở dữ liệu kích thước $N$ đối tượng được lưu trên đĩa cứng thành các khối dung lượng $B$. Số khối tối thiểu để lưu trữ là $n = \lceil N/B \rceil$, và số lần đọc/ghi tối thiểu để trả về lời giải kích thước $K$ đối tượng là $k = \lceil K/B \rceil$. Hiệu năng của thuật toán được đo lường bằng chi phí vào/ra với độ phức tạp đạt chuẩn logarit là $O(\log_B n + k)$ thao tác I/O.
4. Cấu trúc dữ liệu cây R-tree: R-tree là cấu trúc cây cân bằng $n$-chiều lưu trữ các đối tượng không gian thông qua hình chữ nhật bao quanh tối thiểu (Minimum Bounding Rectangle – MBR). Mỗi node chứa từ $m$ đến $M$ mục nhập ($m \le M/2$).
   • Node lá chứa các mục dạng: $(MBR, object_ptr)$, trong đó $object_ptr$ trỏ đến bộ dữ liệu thực tế.
   • Node trong chứa các mục dạng: $(MBR, child_ptr)$, trong đó $child_ptr$ trỏ đến node con cấp dưới.
   • Các giải thuật kinh điển trên R-tree gồm: ChooseLeaf (chọn node lá tối thiểu hóa diện tích mở rộng MBR), SplitNode (phân chia node khi vượt quá $M$ mục), AdjustTree (điều chỉnh MBR lan truyền ngược lên gốc), FindLeaf (tìm node lá chứa mục), CondenseTree (loại bỏ node dưới ngưỡng $m$ và chèn lại các mục), các thao tác chèn (Insertion), xóa (Deletion) và cập nhật (Update).

Phương pháp nghiên cứu và nguồn dữ liệu

• Phương pháp nghiên cứu: Luận án sử dụng phương pháp nghiên cứu định lượng kết hợp thiết kế thuật toán và thực nghiệm hệ thống. Tác giả xây dựng giải thuật chuyển đổi XML sang không gian 2 chiều $(pre, post)$, đề xuất cấu trúc cây chỉ số BioX-tree và BioX+-tree, cài đặt chương trình thử nghiệm bằng ngôn ngữ lập trình hướng đối tượng, phân tích độ phức tạp thời gian/không gian và đo lường chi phí I/O thực tế.
• Nguồn dữ liệu thực nghiệm: Dữ liệu thử nghiệm được trích xuất từ các ngân hàng dữ liệu sinh học tiêu chuẩn gồm 4 tệp XML:
  1. DNACorn: Tệp dữ liệu DNA cây ngô/bắp.
  2. DNARice: Tệp dữ liệu DNA lúa gạo.
  3. Swissprot: Cơ sở dữ liệu chuỗi protein chuẩn quốc tế.
  4. Allhomologies: Cơ sở dữ liệu thông tin tương đồng di truyền và cây phân loại sinh học.

---

Nội dung chính theo từng chương

Chương 1. Tin sinh học và các nguồn dữ liệu

Chương 1 trình bày tổng quan về ngành tin sinh học, các trung tâm dữ liệu sinh học lớn trên thế giới và phân tích các phương pháp đánh chỉ số dữ liệu.

Nội dung chương mô tả chi tiết 3 ngân hàng dữ liệu sinh học trực tuyến lớn nhất:

• NCBI (Hoa Kỳ): Quản lý GenBank với khối lượng dữ liệu vượt 100 Terabyte, cung cấp các cơ sở dữ liệu PubMed, dbEST, HomoloGene, MGC, MMDB (cấu trúc phân tử 3D), Taxonomy và Genome Database.
• EMBL/EBI (Châu Âu): Cung cấp các cơ sở dữ liệu Medline, OMIM, Patent Abstracts, ArrayExpress, MIAME (dữ liệu microarray), ASD, ATD, IPD.
• CIB-DDBJ (Nhật Bản): Ngân hàng dữ liệu DNA của Nhật Bản, cung cấp các công cụ trực tuyến như SRS, FASTA, BLAST, ClustalW.

Tác giả phân tích vấn đề lưu trữ và truy xuất dữ liệu lớn, giới thiệu mô hình kết hợp nền tảng dữ liệu lớn (Hadoop / MapReduce) với kho dữ liệu truyền thống (Data Warehouse trên các nền tảng .NET, PHP, Java). Trong mô hình này, Hadoop đảm nhận việc lưu trữ dữ liệu bán cấu trúc/phi cấu trúc thô, sau đó module chiết xuất sẽ lọc các trường thông tin cần thiết (thông tin loài, chuỗi gen, mẫu) đưa vào kho dữ liệu để khai thác nhanh.

Chương 1 đi sâu vào lý thuyết mô hình bộ nhớ ngoài, phân tích chi phí I/O của đĩa cứng và phân loại toàn diện các thuật toán đánh chỉ số dữ liệu sinh học (Smith - Waterman, BLAST, FLASH, PatternHunter, BLAT, Piers, CAFE, ProperSearch, Wavelets, BIS, IDC). Tiếp theo, chương hệ thống hóa các phương pháp đánh chỉ số XML (XGrind, Xpress, XQzip, XQueC, XISS, MDX, GRIPP, XPath Accelerator) và trình bày cấu trúc cây R-tree cùng các thuật toán thành phần (ChooseLeaf, AdjustTree, CondenseTree, FindLeaf, Insert, Delete, Update), chỉ ra các điểm nghẽn của R-tree khi áp dụng cho dữ liệu chuyển đổi từ tài liệu XML.

Chương 2. Phương pháp đánh chỉ số BioX-tree

Chương 2 trình bày phương pháp đánh chỉ số cải tiến mang tên BioX-tree (tên ban đầu trong các công bố của tác giả là XR-tree, sau đó được đổi thành BioX-tree nhằm tránh trùng lặp với một phương pháp khác trong y văn quốc tế).

1. Phương pháp chuyển đổi tài liệu XML

Tài liệu XML được phân tích cú pháp để xây dựng cây phân cấp. Mỗi thẻ (tag name) được gán cặp số nguyên duy nhất $(pre, post)$ tương ứng với giá trị duyệt theo thứ tự trước và sau. Khi chuyển đổi lên mặt phẳng tọa độ 2 chiều Đề-các (trục hoành là $pre$, trục tung là $post$), một node bối cảnh $E$ sẽ chia không gian thành 4 góc phần tư tương ứng với 4 vùng tìm kiếm chính của các trục XPath: vùng hậu duệ (descendant), vùng tổ tiên (ancestor), vùng các node phía trước (preceding) và vùng các node theo sau (following).

2. Cấu trúc chỉ số và các thuật toán trên BioX-tree

Điểm cải tiến then chốt của BioX-tree là bổ sung cấu trúc liên kết trực tiếp giữa các node lá đại diện cho các phần tử có mối quan hệ cùng cấp (anh em - sibling). Cấu trúc này cho phép giải thuật duyệt trực tiếp từ một node lá sang các node lá kế cận mà không cần thực hiện thao tác duyệt ngược lên node cha trên các tầng cây nội tại lưu ở đĩa cứng.

Luận án xây dựng hệ thống các thuật toán:

• Thuật toán chuyển đổi XML (Thuật toán 2.1).
• Thuật toán chèn (Insertion - Thuật toán 2.2): Tích hợp hai thủ tục con FindSiblingNode (Thuật toán 2.3) để tìm vị trí node anh em kế cận và CreateNewLeafNode (Thuật toán 2.4) để tạo và liên kết node lá mới khi xảy ra phân tách.
• Thuật toán truy vấn: Gồm thuật toán truy vấn điểm (Thuật toán 2.5), truy vấn phạm vi (Thuật toán 2.6), truy vấn anh em (Sibling query - Thuật toán 2.7), truy vấn anh em sau (Following-sibling - Thuật toán 2.8), truy vấn anh em trước (Preceding-sibling - Thuật toán 2.9), truy vấn con cái (Child query - Thuật toán 2.10) và truy vấn tổ tiên (Ancestor query - Thuật toán 2.11).
• Đánh giá độ phức tạp: Tác giả chứng minh về mặt toán học rằng việc bổ sung liên kết ngang giữa các node lá giúp giảm số phép toán duyệt từ $O(h \cdot \log_M N)$ xuống $O(k)$ đối với các truy vấn anh em, trong đó $h$ là chiều cao của cây và $k$ là số lượng kết quả trả về.

3. Kết quả thực nghiệm của phương pháp BioX-tree

Chương trình thực nghiệm được xây dựng hoàn chỉnh với biểu đồ lớp (Class Diagram) và biểu đồ tuần tự (Sequence Diagram). Tác giả thực hiện kiểm thử trên 4 tệp dữ liệu XML tin sinh học: DNACorn, DNARice, Swissprot, Allhomologies.

• Hiệu quả giảm kích thước dữ liệu: Việc chuyển đổi văn bản XML sang tệp dữ liệu số chứa các cặp tọa độ $(pre, post)$ giúp giảm dung lượng đáng kể so với tệp XML gốc ban đầu, tạo điều kiện thuận lợi cho việc lưu trữ và lập chỉ số.
• So sánh hiệu năng truy vấn giữa BioX-tree và R-tree: Thực nghiệm đo lường trên 6 loại truy vấn XPath (các Bảng 1.6 – 1.11 và Hình 2.21 – 2.26 trong luận án). Kết quả cho thấy BioX-tree vượt trội so với R-tree ở các truy vấn anh em (sibling), truy vấn con cái (child), truy vấn tổ tiên (ancestor) và hậu duệ (descendant) nhờ giảm thiểu số bước duyệt cây và số lần truy cập khối trên đĩa cứng. Ngược lại, ở hai loại truy vấn node theo sau (following) và node phía trước (preceding), hiệu quả của BioX-tree không ổn định do cấu trúc phân vùng không gian của cây bị biến đổi so với R-tree nguyên bản.

Chương 3. Phương pháp đánh chỉ số mở rộng BioX+-tree

Chương 3 đề xuất cấu trúc chỉ số mở rộng BioX+-tree nhằm tối ưu hóa sâu hơn việc tổ chức các hình chữ nhật bao quanh tối thiểu (MBR) trên không gian dữ liệu chuyển đổi.

1. Phân tích không gian dữ liệu chuyển đổi và mô hình BioX+-tree

Trong cây BioX-tree, mặc dù các node lá đã được liên kết trực tiếp, sự phân bố của các điểm dữ liệu $(pre, post)$ từ cây XML tuân theo quy luật đường chéo nghiêm ngặt ($pre$ tăng dần đồng thời $post$ có xu hướng biến thiên theo độ sâu phân cấp). Việc đóng gói các điểm này vào các MBR hình chữ nhật thông thường của R-tree vẫn để lại các khoảng không gian trống (dead space) và diện tích chồng lấn (overlap) giữa các MBR lân cận, dẫn đến việc giải thuật tìm kiếm phải duyệt qua nhiều MBR không chứa điểm mục tiêu. BioX+-tree cải tiến cách thức phân vùng và gom cụm MBR dựa trên đặc tính phân bố thực tế của cây phân cấp XML.

2. Các thuật toán đề xuất

Tác giả hoàn thiện hai thuật toán trung tâm:

• Thuật toán chèn BioX+-tree (Insertion - Thuật toán 3.1): Tối ưu hóa việc chọn vị trí chèn và tái cấu trúc MBR khi tách node, kiểm soát chặt chẽ diện tích phủ và liên kết thứ tự giữa các node lá.
• Thuật toán truy vấn BioX+-tree (Thuật toán 3.2): Tận dụng cấu trúc MBR thu hẹp kết hợp danh sách liên kết mở rộng để định tuyến truy vấn trực tiếp đến vùng dữ liệu hợp lệ.

3. Kết quả thực nghiệm và so sánh BioX+-tree với BioX-tree

Thực nghiệm so sánh giữa BioX+-tree và BioX-tree được tiến hành trên cùng các bộ dữ liệu XML tin sinh học, tập trung vào 5 nhóm truy vấn (các Bảng 3.1 – 3.5 và Hình 3.5 – 3.9 trong luận án):

1. Truy vấn anh em (Sibling query): BioX+-tree giảm thêm số phép I/O và thời gian thực thi so với BioX-tree.
2. Truy vấn anh em trước (Preceding-sibling query): Tốc độ truy xuất nhanh hơn nhờ tối ưu hóa định vị node lá phía trước.
3. Truy vấn anh em sau (Following-sibling query): Giảm số node trung gian cần nạp vào bộ nhớ.
4. Truy vấn con cái (Child query): Hiệu năng cải thiện rõ rệt so với BioX-tree nhờ giảm diện tích chồng lấn MBR.
5. Truy vấn phạm vi (Range query): Khắc phục một phần sự suy giảm hiệu năng không gian, cho kết quả ổn định hơn BioX-tree.

---

Kết quả và những đóng góp mới

Luận án tự đúc kết các kết quả và đóng góp mới về mặt khoa học lý thuyết và ứng dụng thực tiễn như sau:

Đóng góp về mặt lý luận và phương pháp

1. Phương pháp chuyển đổi dữ liệu không gian cho XML tin sinh học: Luận án áp dụng thành công kỹ thuật ánh xạ cây XML sang không gian tọa độ số 2 chiều $(pre, post)$ trên các bộ dữ liệu sinh học quy mô lớn. Kỹ thuật này chuyển bài toán xử lý chuỗi văn bản phức tạp thành bài toán xử lý hình học trên các điểm tọa độ số.
2. Đề xuất hai cấu trúc chỉ số BioX-tree và BioX+-tree: Phát triển cấu trúc cây chỉ số mới dựa trên việc cải tiến R-tree. Bằng cách thiết lập liên kết ngang trực tiếp giữa các node lá và tối ưu hóa cấu trúc MBR theo đặc thù phân bố của các thẻ XML, luận án đã loại bỏ các nhánh duyệt cây dư thừa, chứng minh bằng lý thuyết sự giảm thiểu số lần truy xuất đĩa cứng (thao tác I/O) khi thực thi các truy vấn XPath.
3. Xây dựng hệ thống thuật toán truy vấn chuyên biệt: Thiết kế đầy đủ các thuật toán chèn và thuật toán xử lý cho các trục quan hệ XPath chính (anh em, anh em trước, anh em sau, con cái, tổ tiên, hậu duệ).

Đóng góp về mặt thực nghiệm và giải pháp ứng dụng

1. Chứng minh hiệu quả nén dữ liệu: Thực nghiệm trên các tập dữ liệu DNACorn, DNARice, Swissprot, Allhomologies đã chỉ ra rằng phương pháp chuyển đổi dữ liệu XML về dạng số đạt tỷ lệ nén dung lượng tốt so với tệp văn bản XML gốc.
2. Khẳng định tính ưu việt qua thực nghiệm: Kết quả thử nghiệm chứng minh BioX-tree và BioX+-tree vượt trội so với R-tree kinh điển về tốc độ và số lượng thao tác I/O đối với các truy vấn anh em, con cái, tổ tiên và hậu duệ.
3. Đề xuất kiến trúc tiền xử lý dữ liệu lớn: Đề xuất mô hình tích hợp Hadoop / MapReduce với kho dữ liệu truyền thống để xử lý sơ bộ các tệp gen thô dung lượng lớn trước khi tiến hành đánh chỉ số chuyên sâu.

---

Hạn chế và hướng nghiên cứu tiếp

Căn cứ theo các nội dung được tác giả công bố trong văn bản, luận án còn một số hạn chế và định hướng nghiên cứu sau:

Hạn chế của nghiên cứu

• Tỷ lệ nén không đồng đều: Mức độ giảm kích thước dữ liệu khi chuyển đổi từ XML sang không gian số phụ thuộc vào cấu trúc thẻ của từng loại dữ liệu, kết quả nén không đồng đều giữa các dạng tài liệu DNA, Protein và cây phân loại sinh học.
• Suy giảm hiệu năng trên một số truy vấn không gian: Việc điều chỉnh cấu trúc cây R-tree để ưu tiên các truy vấn đường dẫn XPath đã làm suy yếu tính tối ưu về mặt hình học không gian nguyên bản của R-tree. Do đó, các truy vấn phạm vi thông thường (range queries không thuộc XPath) cùng hai loại truy vấn XPath trên toàn bộ các node phía trước (preceding) và node theo sau (following) của một thẻ bất kỳ cho kết quả chưa tốt và có độ biến động khó dự đoán.
• Phạm vi xử lý chuỗi sinh học: Luận án mới chỉ giải quyết triệt để bài toán đánh chỉ số cho phần dữ liệu cấu trúc (thẻ XML). Phần dữ liệu sinh học dạng chuỗi ký tự (như so sánh các đoạn DNA tương đồng xấp xỉ) mới dừng lại ở bước khảo sát lý thuyết tổng quan.

Hướng nghiên cứu tiếp theo

• Tiếp tục cải tiến và hoàn thiện cấu trúc BioX+-tree nhằm khắc phục hiện tượng suy giảm hiệu năng đối với các truy vấn phạm vi và truy vấn following/preceding.
• Nghiên cứu mở rộng phương pháp đánh chỉ số kết hợp giữa dữ liệu cấu trúc XML và dữ liệu chuỗi sinh học (chuỗi DNA, chuỗi axit amin) nhằm phục vụ các truy vấn tương đồng xấp xỉ trực tiếp trên các hệ quản trị cơ sở dữ liệu sinh học phân tán.

---

Giá trị tham khảo

Luận án là tài liệu chuyên khảo hữu ích cho các nhóm đối tượng học thuật và thực tiễn:

• Nghiên cứu sinh và học viên cao học ngành Công nghệ thông tin, Toán tin ứng dụng và Khoa học máy tính: Cung cấp tài liệu tham khảo chi tiết về kỹ thuật lập chỉ số không gian đa chiều, mô hình bộ nhớ ngoài (I/O Model) và các giải thuật tối ưu hóa cây R-tree cho dữ liệu bán cấu trúc.
• Giảng viên và nhà nghiên cứu trong lĩnh vực Tin sinh học và Cơ sở dữ liệu: Cung cấp bức tranh toàn cảnh về các nguồn dữ liệu sinh học quốc tế (NCBI, EMBL/EBI, DDBJ), hệ thống các thuật toán so sánh chuỗi (Smith - Waterman, BLAST, FASTA, PatternHunter) và các kỹ thuật xử lý dữ liệu XML.
• Kỹ sư phát triển phần mềm và kiến trúc sư hệ thống dữ liệu y sinh: Có thể tham khảo trực tiếp mô hình kết hợp Hadoop - Kho dữ liệu ở Chương 1 để xây dựng hệ thống tiền xử lý tệp gen lớn, cũng như tham khảo mã giả của các thuật toán Insertion, FindSiblingNode, CreateNewLeafNode và các thuật toán truy vấn ở Chương 2 và Chương 3 để cài đặt các module tìm kiếm XPath hiệu năng cao.

---

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

1. Tại sao thao tác I/O trên đĩa cứng lại được xem là nút thắt cổ chai trong việc xử lý tài liệu XML tin sinh học?

Tài liệu XML tin sinh học có kích thước rất lớn (Gigabyte đến Terabyte), vượt quá dung lượng bộ nhớ RAM nên bắt buộc phải lưu trữ trên ổ đĩa cứng. Đĩa cứng đọc/ghi dữ liệu theo từng khối (block/sector) với cơ chế quay vật lý tuần tự, có tốc độ chậm hơn truy xuất bộ nhớ RAM hơn 100.000 lần. Mỗi lần đọc một khối dữ liệu $B$ từ đĩa lên RAM làm tiêu tốn thời gian rất lớn; do đó số lượng thao tác đọc/ghi (I/O) là yếu tố quyết định tốc độ thực thi của thuật toán xử lý dữ liệu lớn.

2. Nguyên lý chuyển đổi một thẻ XML thành tọa độ 2 chiều trong luận án được thực hiện như thế nào?

Luận án áp dụng phương pháp đánh số thứ tự duyệt cây của Dietz. Cây XML được duyệt theo hai cách: duyệt theo thứ tự trước (pre-order, đánh số tăng dần từ trên xuống dưới) và duyệt theo thứ tự sau (post-order, đánh số tăng dần từ trái qua phải). Mỗi thẻ được gán một cặp số $(pre, post)$ đóng vai trò là tọa độ điểm trên mặt phẳng 2 chiều Đề-các. Quan hệ tổ tiên - hậu duệ được xác định chính xác qua điều kiện: node $x$ là tổ tiên của node $y$ khi và chỉ khi $pre(x) < pre(y)$ và $post(x) > post(y)$.

3. Cải tiến cốt lõi của cấu trúc BioX-tree so với R-tree truyền thống là gì?

Cây R-tree truyền thống chỉ tổ chức các MBR theo vùng không gian hình học. Khi cần tìm các phần tử anh em (cùng cấp cha) trong cây XML, R-tree phải duyệt ngược lên node cha rồi duyệt xuống các cây con khác, gây ra nhiều phép đọc đĩa dư thừa. BioX-tree khắc phục điểm này bằng cách thiết lập đường liên kết trực tiếp giữa các node lá đại diện cho các phần tử cùng cấp, cho phép thuật toán nhảy trực tiếp giữa các node lá lân cận mà không cần duyệt ngược lên các tầng trên của cây.

4. Tại sao tác giả đổi tên phương pháp từ XR-tree thành BioX-tree?

Trong các công bố khoa học ban đầu, tác giả đặt tên cho phương pháp cải tiến là XR-tree. Tuy nhiên, sau đó tác giả phát hiện tên gọi XR-tree đã trùng với tên của một phương pháp chỉ số khác đã được công bố trong y văn quốc tế. Do đó, trong văn bản luận án chính thức, tác giả đã đổi tên thành BioX-tree để đảm bảo tính phân định học thuật.

5. Phương pháp BioX+-tree mang lại cải tiến gì so với BioX-tree?

BioX+-tree phân tích sâu đặc thù phân bố điểm dữ liệu $(pre, post)$ trên mặt phẳng và nhận thấy các MBR trong BioX-tree vẫn còn khoảng không gian chết (dead space) và diện tích chồng lấn (overlap). BioX+-tree tái cấu trúc giải thuật chèn và phân chia node để tạo ra các MBR ôm sát dữ liệu hơn, từ đó cải thiện thêm tốc độ và giảm số phép I/O trên các truy vấn anh em, truy vấn con cái và truy vấn phạm vi.

---

Kết luận

Luận án tiến sĩ của tác giả Đinh Đức Lương đã giải quyết bài toán tối ưu hóa truy vấn XPath trên các tệp dữ liệu bán cấu trúc XML tin sinh học quy mô lớn. Bằng cách kết hợp phép chuyển đổi tọa độ số $(pre, post)$ với việc tái cấu trúc cây R-tree thành BioX-tree và BioX+-tree thông qua liên kết trực tiếp các node lá, công trình đã cắt giảm hiệu quả số lượng thao tác truy xuất đĩa cứng (I/O). Các kết quả thực nghiệm trên các tập dữ liệu DNA và protein thực tế đã khẳng định tính khả thi và hiệu năng vượt trội của phương pháp đề xuất đối với các trục truy vấn XPath quan trọng.

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

MỞ ĐẦU Tài liệu XML là dữ liệu văn bản có cấu trúc, hay còn gọi là dữ liệu bán cấu trúc, chúng đã phổ biến hàng thập kỷ nay vì khả năng lưu trữ dữ liệu rất linh hoạt và dễ dàng chia sẻ, sử dụng qua internet. Trước đây, các tài liệu XML thường có kích thước không lớn, nhưng những năm gần đây bắt đầu xuất hiện các tài liệu XML tin sinh học có kích thước rất lớn có thể lên tới Giga, Tera Byte bởi sự phát triển như vũ bảo của công nghệ sinh học trong kỷ nguyên này. Dữ liệu đó có thể tìm thấy từ các nguồn dữ liệu uy tín như SRA (công khai các trình tự được giải mã), NCBI Genome (các loài đã được giải trình tự), ensembl.org (tổng hợp rất nhiều dữ liệu thành BioMart)… Các tài liệu XML tin sinh học là dữ liệu gồm có 2 phần, dữ liệu sinh học (DNA, Protein, phân loài,…) và các dữ liệu mô tả dữ liệu sinh học. Cấu trúc dữ liệu được định nghĩa theo các thẻ (tag) và các cấu trúc dữ liệu này thường linh hoạt, có thể khác biệt bởi vì chúng được tùy biến theo các cá nhân, tổ chức sinh học thực hiện.

Vì có kích thước lớn như vậy, các tài liệu cơ bản phải lưu trữ và khai thác trên đĩa cứng, hoặc trong hệ thống lưu trữ phân tán, trước khi có thế truy xuất 1 phần nhỏ để đưa lên bộ nhớ chính (RAM) mỗi khi cần phân tích sâu hơn. Cơ chế truy xuất đĩa cứng là tuần tự và thời gian tiêu tốn chậm hơn rất nhiều lần so với truy xuất trên RAM. Do vậy, các phương pháp truy vấn cần truy xuất đĩa cứng luôn tìm cách sao cho tối thiểu số lần cần truy xuất đĩa cứng và tối đa tận dụng bộ nhớ chính, như là Cache, Buffer. Các truy xuất thực thi theo thuật toán của các truy vấn đặc thù, được thiết kế để đạt kết quả mong muốn trong thời gian ngắn và phù hợp với truy vấn.

Ví dụ: - Truy vấn Xpath cho 01 tài liệu XML (tìm kiếm chính xác). Trích xuất tất cả các dữ liệu có tags có quan hệ cùng nguồn gốc/anh em với nhau của 1 loại Chuột Bạch. Trích xuất toàn bộ các dữ liệu là hậu duệ của heo giống Châu Phi. - Truy vấn tương đồng cho dữ liệu các đoạn DNA (tìm kiếm xấp xỉ) 1.

Tìm kiếm tất cả các Gen tương đồng với 1 đoạn Gen mẫu của một loài mới. Giải pháp truyền thống cho các truy vấn như trên là lựa chọn và cài đặt các phương pháp đánh chỉ số (indexing) phù hợp một số loại dữ liệu và truy vấn đặc thù. Các phương pháp này có nhưng gặp nhiều hạn chế với dữ liệu văn bản kích thước lớn như vậy. - Với dữ liệu văn bản, kích thước dữ liệu chỉ số sinh ra thường cũng rất lớn, thậm chí lớn hơn nhiều so với dữ liệu gốc, như vậy gây nên các vấn đề: 1.

Lưu trữ dữ liệu chỉ số này là vấn đề nan giải. Nén dữ liệu và khai thác dữ liệu đồng thời kém hiệu quả. - Hơn nữa, nếu chỉ số là dữ liệu văn bản thì vấn đề tốc độ truy vấn vẫn là vấn đề khó giải quyết. Do vậy, các nghiên cứu gần đây về đánh chỉ số một tài liệu XML có xu hướng: - Tách tài liệu XML thành 2 phần dữ liệu và áp dụng các phương pháp đánh chỉ số khác nhau cho phù hợp với dạng dữ liệu và loại truy vấn đặc thù.

Cụ thể là: 1. Phương pháp đánh chỉ số dữ liệu cấu trúc (dữ liệu các thẻ) và hỗ trợ các truy vấn đặc thù như Xpath. Phương pháp đánh chỉ số dữ liệu sinh học (như các đoạn DNA) và hỗ trợ các truy vấn đặc thù như tìm kiếm các chuỗi DNA tương đồng. - Chuyển đổi dữ liệu văn bản gốc về dạng số nhằm mục đích: 1.

Giảm kích thước dữ liệu gốc ban đầu. Áp dụng các phương pháp đánh chỉ số phù hợp. Cải thiện tốc độ các truy vấn. Các vấn đề cần giải quyết rất rộng gồm tin học và sinh học, vì vậy nghiên cứu của luận án tập trung giải bài toán Phương pháp đánh chỉ số hỗ trợ cho các truy vấn đặc thù về tốc độ bằng cách giảm số lần cần truy cập đĩa cứng mà vẫn đạt được kết quả mong đợi.

Kết quả luận án đã giải bài toán Phương pháp đánh chỉ số dữ liệu cấu trúc (dữ liệu các thẻ) và hỗ trợ các truy vấn Xpath. Ngoài ra, với bài toán Phương pháp đánh chỉ số dữ liệu sinh học (như các đoạn DNA) và hỗ trợ các truy vấn đặc thù như tìm kiếm các chuỗi DNA tương đồng, luận án đã khảo sát được phương pháp và có định hướng cho nghiên cứu tiếp theo. Cụ thể mục tiêu và kết quả của luận án như sau. Mục tiêu thực hiện của luận án: - Nghiên cứu phương pháp đánh chỉ số dựa trên phương pháp R-tree nhằm tăng hiệu quả các truy vấn Xpath trên dữ liệu XML, thông qua dữ liệu trung gian được chuyển đổi về dạng tọa độ số của các tags.

Dữ liệu XML mục tiêu là từ một tài liệu XML tin sinh học. - Sử dụng phương pháp chuyển đổi dữ liệu văn bản có cấu trúc XML về dữ liệu dạng số mà biểu diễn được trên không gian 2 chiều (có thể mở rộng lên nhiều chiều). Mục tiêu là nhằm giảm kích thước dữ liệu gốc và áp dụng được phương pháp đánh chỉ số đề xuất. Kết quả đạt đƣợc của luận án nhƣ sau: - Bằng thực nghiệm đã chỉ ra rằng phương pháp chuyển đổi dữ liệu XML tin sinh học về dữ liệu không gian là có hiệu quả về giảm kích thước với tỷ lệ khá tốt nói chung.

Tuy nhiên, tỷ lệ nén không có có kểt quả tốt đồng đều giữa các thực nghiệm với dạng tài liệu XML tin sinh học DNA, Protein, và cây phân loài… luan an 4 - Đề xuất được phương pháp đánh chỉ số BioX-tree và phương pháp mở rộng BioX+ tree. Các phương pháp đề xuất (cải tiến phương pháp R-tree) đã chứng tỏ hiệu quả hơn phương pháp R-tree khi áp dụng để đánh chỉ số dữ liệu chuyển đồi từ dữ liệu XML qua các thực nghiệm. Đặc biệt, các truy vấn anh em, hoặc các truy vấn có tận dụng truy vấn anh em trong thuật toán, có kết quả tốt. Lý thuyết và thực nghiệm đã chứng mình được rằng: các truy vấn đã giảm được các bước duyệt cây dư thừa trên cây chỉ số (lưu trữ trên đĩa cứng), nhờ đó giảm số lần truy xuất trên đĩa cứng để lấy dữ liệu lên bộ nhớ chính, mà vẫn có được kết quả như mong muốn.

- Hạn chế của các phương pháp đề xuất là việc cải tiến cấu trúc cây R-tree để hiệu quả hơn với các truy vấn Xpath đã làm suy yếu cấu trúc tối ưu về không gian của phương pháp R-tree gốc. Hậu quả là, các truy vấn thông thường của R-tree như truy vấn phạm vị (không phải truy vấn Xpath), hai loại truy vấn Xpath (toàn bộ) các tags trước và sau của một tag bất kỳ có kết quả không tốt và thất thường, khó dự đoán. Tất nhiên, các truy vấn này ít ý nghĩa với các truy vấn Xpath. Nhưng để mở rộng phạm vi áp dụng, NCS sẽ tiếp tục nghiên cứu sau này.

Trong quá trình thực hiện các nghiên cứu, NCS đã đặt tên phương pháp là XR-tree trong các công bố của mình nhưng sau đó phát hiện trùng với tên 1 phương pháp trong một bài báo khác, vì vậy, trong luận án, NCS đã đổi tên thành BioX-tree thay cho XR-tree. luan an 5 Chƣơng 1. Tin sinh học và các nguồn dữ liệu 1. Tin sinh học Tin sinh học (BioInformatics) là một lĩnh vực khoa học sử dụng các công nghệ của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, sinh học, hóa học, vật lý… và toán sinh học.

Tin sinh học thường gắn liền với sinh học tính toán (computational biology) hoặc sinh học hệ thống (system biology). Thuật ngữ tin sinh học là một phần của sinh học tính toán. Sự kết hợp giữa các nghành khoa học nói trên có sự đan xen với nhau và tương hỗ lẫn nhau, vì vậy thành quả nghiên cứu mang lại của ngành học này không chỉ đóng góp cho sinh học mà còn đóng góp cho các ngành khoa học khác. Một ví dụ rõ ràng nhất là trong quy trình nghiên cứu về hệ thần kinh của động vật, con người đã phát hiện ra các nơ ron thần kinh và cách xung thần kinh được dẫn truyền qua các tế bào thần kinh.

Kết hợp với những tính toán vật lý, trí tuệ nhân tạo, những lý thuyết sinh học trên được áp dụng vào tin học, để hình thành một mạng tính toán (mạng nơ ron - Neuron network). Nội dung chính của sinh học tính toán là sử dụng các công cụ tách chiết các thông tin hữu ích từ tập rất lớn các dữ liệu thu nhận được bằng các kỹ thuật sinh học mà các dữ liệu này thay đổi và được bổ sung liên tục với lưu lượng và mức độ lớn. Bài toán đặc trưng trong sinh học tính toán bao gồm việc lắp ráp những trình tự DNA chất lượng cao từ những đoạn ngắn DNA thu nhận được từ kỹ thuật xác định DNA và việc dự đoán quy luật điều hòa gen với dữ liệu từ các mARN, microway hay khối phổ. Các lĩnh vực nghiên cứu chính của tin sinh học bao gồm [10][18][23]: Hệ gen học phân tích trình tự; Tìm kiếm gen; Tìm kiếm các đột biến; Phân loại học phân tử; Phân tích chức năng gen; Bảo tồn đa dạng sinh học; Phân tích hình ảnh mức độ cao; Công cụ phần mềm… luan an 6 1.

Các nguồn dữ liệu Dữ liệu sinh học ngày càng tăng theo cấp số mũ do sự phát triển của các kỹ thuật giải trình tự. Như vậy, vấn đề đặt ra là cần phải có biện pháp lưu trữ, quản lý, sử dụng và chia sẻ nguồn dữ liệu này. Hơn thế nữa, với việc hệ thống hóa toàn bộ dữ liệu trên, chúng ta dễ dàng thực hiện việc chia sẻ những thông tin ấy qua mạng hay kết nối thêm vào những tập dữ liệu phân tán ở nơi khác. Trên thế giới, một số cơ sở dữ liệu lớn, trực tuyến đã được xây dựng để cung cấp thông tin cho các nhà nghiên cứu sinh học.

Các thông tin này được sắp xếp và lưu trữ bởi một hệ thống các máy chủ rất mạnh của ba ngân hàng gen lớn nhất thế giới hiện nay là: NCBI, EMBL/EBI, CIB-DDBJ…. Chúng được gọi là các CSDL sinh học.