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

LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, được hoàn thành dưới sự hướng dẫn của TS. Hoàng Đỗ Thanh Tùng và PGS. Đặng Hữu Đạo. Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác.

Tôi xin chịu trách nhiệm về những lời cam đoan của mình. Hà nội, tháng 10 năm 2019 Tác giả LỜI CẢM ƠN Luận án này được hoàn thành với sự nỗ lực không ngừng của tác giả và sự giúp đỡ hết mình từ các thầy giáo hướng dẫn, bạn bè và người thân. Đầu tiên, tác giả xin bày tỏ lời tri ân sâu sắc tới PGS. Đặng Hữu Đạo và TS.

Hoàng Đỗ Thanh Tùng, những thầy giáo đã tận tình hướng dẫn tác giả hoàn thành luận án này. Tác giả xin gửi lời cảm ơn tới các thầy, cô giáo và cán bộ của Viện Công nghệ thông tin, Học viện Khoa học và Công nghệ (Viện Hàn lâm Khoa học và Công nghệ Việt Nam) đã nhiệt tình giúp đỡ và tạo ra môi trường nghiên cứu tốt để tác giả hoàn thành công trình của mình; trân trọng cảm ơn các thầy, cô và các đồng nghiệp ở các nơi mà tác giả tham gia viết bài đã có những góp ý chính xác để tác giả có được những công bố như ngày hôm nay. Tác giả xin cảm ơn Ban Giám hiệu trường Cao đẳng Công nghiệp Thực phẩm, các đồng nghiệp nơi tác giả công tác đã ủng hộ, tạo mọi điều kiện tốt nhất để luận án được hoàn thành đúng thời hạn. Cuối cùng, tác giả xin gửi tới bạn bè, người thân lời cảm ơn chân thành nhất vì đã đồng hành cùng tác giả trong suốt thời gian qua.

Hà Nội, tháng 10 năm 2019 Đinh Đức Lƣơng i MỤC LỤC MỤC LỤC. i Danh mục các thuật ngữ. iii Bảng các ký hiệu, từ viết tắt. iv Danh sách bảng.

v Danh sách các thuật toán. vi Danh sách hình vẽ. vii MỞ ĐẦU. Tin sinh học và các nguồn dữ liệu.

Tin sinh học. Các nguồn dữ liệu. Vấn đề tin sinh học và cơ sở dữ liệu sinh học. Các phương pháp đánh chỉ số dữ liệu sinh học và tin sinh học.

Chỉ số và mô hình bộ nhớ ngoài. Các phương pháp đánh chỉ số cho dữ liệu sinh học. Các thuật toán so sánh tương đồng thông qua chuỗi đại diện14 1. Các thuật toán sử dụng sự thay đổi cấu trúc chỉ số.

Các phương pháp đánh chỉ số cho dữ liệu tin sinh học. Phương pháp đánh chỉ số tài liệu XML. Tài liệu XML và Xpath. Các phương pháp theo hướng nghiên cứu chuyển đổi dữ liệu XML sang không gian số trước khi thực hiện đánh chỉ số.

Đánh số trên lược đồ. Phép nối có cấu trúc. Chuyển đổi lên không gian đa chiều. Ánh xạ sang cơ sở dữ liệu quan hệ.

Phương pháp R-tree. Khái niệm R-tree. Cấu trúc R-tree. Một số thuật toán cơ bản trong phương pháp R-tree.

Một số phương pháp cải tiến R-tree đánh chỉ số tài liệu XML. Các vấn đề còn tồn tại. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ BIOX-TREE. Phương pháp đánh chỉ số cải tiến BioX-tree.

Chuyển đổi tài liệu XML. Cấu trúc chỉ số trên cây BioX-tree. Thuật toán chèn. Thuật toán truy vấn.

Xử lý truy vấn. Thuật toán cho các truy vấn anh em. Thuật toán cho các truy vấn khác. Đánh giá độ phức tạp của các thuật toán.

Kết quả thực nghiệm phương pháp BioX-tree. Mô hình và môi trường thử nghiệm. Xây dựng chương trình. Đánh giá hiệu quả giảm kích thước dữ liệu.

So sánh kết quả của phương pháp BioX-tree và R-tree. Kết luận chương 2. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ MỞ RỘNG BIOX+-TREE. Phương pháp BioX+-tree.

Phân tích không gian dữ liệu chuyển đổi của tài liệu XML. Các thuật toán đề xuất. Kết quả thực nghiệm phương pháp BioX+-tree. Mô hình và môi trường thử nghiệm.

So sánh kết quả của phương pháp BioX+-tree và BioX-tree. Kết luận chương 3. 105 Danh mục các công trình của tác giả. 107 Tài liệu tham khảo.

108 iii Danh mục các thuật ngữ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Đánh chỉ số Indexing Tin sinh học BioInformatics Ngân hàng gen GenBank Ngôn ngữ truy vấn dữ liệu XML dựa trên đường dẫn Xpath Tên một thẻ trong tài liệu XML Tag name Phần tử Element Thuộc tính Attribute Bộ tăng tốc XPath XPath Accelerator Phép nối Join Bao đóng Kleene Kleene Đa chiều Multi dimension Duyệt cây theo thứ tự trước Post order Duyệt cây theo thứ tự sau Pre order Một node trên cây R-tree, BioX-tree, BioX+-tree Node Một mục thuộc node trên cây R-tree, BioX-tree, BioX+- tree Entry Truy vấn tổ tiên Ancestor query Truy vấn hậu duệ Descendant query Truy vấn cha mẹ Parent query Truy vấn con cái Child query Truy vấn các node theo sau Following query Truy vấn các node phía trước Preceding query Truy vấn anh em Sibling query iv Bảng các ký hiệu, từ viết tắt Ký hiệu, Diễn giải từ viết tắt CSDL Cơ sở dữ liệu DNA Phân tử mang thông tin di truyền ARN Đại phân tử sinh học NCBI Trung tâm Thông tin Công nghệ sinh học Quốc gia Hoa Kỳ EMBL/EBI Viện tin sinh học Châu Âu CIB-DDBJ Ngân hàng dữ liệu DNA của Nhật Bản SQL Ngôn ngữ truy vấn có cấu trúc .NET, PHP, JAVA Tên một số ngôn ngữ lập trìnhphổ biến Tính nguyên tử, nhất quán, độc lập và bền vững trong CSDL ACID quan hệ XML Ngôn ngữ đánh dấu mở rộng A-D Mối quan hệ tổ tiên - hậu duệ MBR Hình chữ nhật bao quanh tối thiểu trong R-tree pre(E) Giá trị duyệt cây theo thứ tự trước của node bối cảnh E post(E) Giá trị duyệt cây theo thứ tự sau của node bối cảnh E v Danh sách bảng Bảng 1.1: Thông tin cấu trúc của file trên đĩa .2: Thông tin của BioX-tree .3: Thông tin Block.4: Thông tin phần tử .5: Chức năng của các lớp.6: Kết quả truy vấn anh em BioX-tree .7: Kết quả truy vấn con cái BioX-tree.8: Kết quả truy vấn tổ tiên BioX-tree .9: Kết quả truy vấn hậu duệ BioX-tree.10: Kết quả truy vấn các node theo sau BioX-tree .11: Kết quả truy vấn các node phía trước BioX-tree .1: Kết quả truy vấn anh em BioX+-tree .2: Kết quả truy vấn anh em trước BioX+-tree .3: Kết quả truy vấn anh em sau BioX+-tree .4: Kết quả truy vấn con cái BioX+-tree .5: Kết quả truy vấn phạm vi BioX+-tree. 103 vi Danh sách các thuật toán Thuật toán 2.1: Hai thuật toán sửa đổi trong chuyển đổi tài liệu XML .2: Thuật toán chèn.3: Thuật toán FindSiblingNode .4: Thuật toán CreateNewLeafNode .5: Thuật toán truy vấn điểm .6: Thuật toán truy vấn phạm vi.7: Thuật toán truy vấn anh em .8: Thuật toán truy vấn anh em sau .9: Thuật toán truy vấn Anh em trước.10: Thuật toán truy vấn con.11: Thuật toán truy vấn tổ tiên .1: Thuật toán Insertion .2: Thuật toán truy vấn. 96 vii Danh sách hình vẽ Hình 1.1: Xây dựng và xử lý dữ liệu trong tin sinh học.2: Mô hình hadoop kết hợp kho dữ liệu để xử lý dữ liệu thô .3: Sơ đồ mô tả các phương pháp đánh chỉ số CSDL sinh học .4: Ví dụ về tài liệu XML biểu diễn dưới dạng text và dạng cây .5: Ví dụ tài liệu XML tin sinh học .6: Cây phân tích cú pháp của Q với 5 node N1 .7: Ví dụ về cách đánh chỉ số trên cây theo thứ tự duyệt cây theo thứ tự trước, duyệt cây theo thứ tự sau .8: Ví dụ minh họa về đánh chỉ số trong XISS.9: Một ví dụ sử dụng các phép join .10: Ví dụ về vectơ trong không gian 3 chiều .11: Biểu diễn cấu trúc cây R-tree .12: Biểu diễn 02 chiều của một R-tree .13: Trường hợp phân chia node (a) bad split, (b) good split.14: Phân chia phần tử thành các nhóm node mới .15: Cấu trúc cây XR-tree .16: Xây dựng MBR trên không gian 2 chiều của phương pháp AR*-tree .17: Mô hình quy trình tổng quát .18: Mô hình thể hiện quá trình chuyển đổi dữ liệu và đánh chỉ số trên đĩa cứng .1: Phạm vi quét thứ tự duyệt cây theo thứ tự trước và sau ban đầu (vùng xám) và thu nhỏ (vùng trắng) cho truy vấn con cháu được thực hiện theo truy vấn mẫu .2: Ví dụ về phân phối các điểm quy đổi cho một tài liệu XML.3: Các thành phần được đề xuất cải tiến trong phương pháp BioX-tree .4: Ví dụ về biểu diễn điểm dựa trên cặp giá trị (duyệt cây theo thứ tự trước, duyệt cây theo thứ tự sau) .5: Ví dụ về MBR trong cây BioX-tree.6: Hệ thống cây phân cấp theo các tag trong tài liệu XML DNA gạo .7: Các node lá thể hiện sự liên kết trên cây cấu trúc BioX-tree .8: Ví dụ về quy trình chèn .9: Mô hình thử nghiệm phương pháp BioX-tree và R-tree .10: Dữ liệu trong file XML DNACorn .11: Dữ liệu trong file XML DNARice.12: Dữ liệu trong file XML Swissprot .13: Dữ liệu trong file XML Allhomologies .14: Biểu đồ lớp của chương trình BioX-tree.15: Biểu đồ tuần tự của chương trình BioX-tree .16: File dữ liệu DNACorn sau chuyển đổi .17: File dữ liệu DNARice sau chuyển đổi .18: File dữ liệu Swissprot sau chuyển đổi .19: File dữ liệu Allhomologies sau chuyển đổi.20: So sánh kích thước tài liệu XML và tài liệu chuyển dổi về không gian số .21: Biểu đồ so sánh truy vấn anh em giữa BioX-tree và R-tree .22: Biểu đồ so sánh truy vấn con cái giữa BioX-tree và R-tree .23: Biểu đồ so sánh truy vấn tổ tiên giữa BioX-tree và R-tree .24: Biểu đồ so sánh truy vấn hậu duệ giữa BioX-tree và R-tree.25: Biểu đồ so sánh truy vấn các node theo sau giữa BioX-tree và R-tree .26: Biểu đồ so sánh truy vấn các node phía trước giữa BioX-tree và R-tree87 Hình 3.1: Các thành phần được cải tiến trong phương pháp mở rộng BioX+-tree .2: Cây tài liệu XML được đánh số thứ tự .3: Các MBR của node lá trong cây BioX-tree .4: Mô hình thử nghiệm thuật toán BioX+-tree và BioX-tree .5: Biểu đồ so sánh truy vấn anh em BioX+-tree và BioX-tree .6: Biểu đồ so sánh truy vấn anh em trước BioX+-tree và BioX-tree .7: Biểu đồ so sánh truy vấn anh em sau BioX+-tree và BioX-tree .8: Biểu đồ so sánh truy vấn con cái BioX+-tree và BioX-tree .9: Biểu đồ so sánh truy vấn phạm vi BioX+-tree và BioX-tree. 103 1 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.