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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:130

Thêm vào BST

Báo xấu

30
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài 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).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… ĐINH ĐỨC LƢƠNG 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Ĩ TOÁN HỌC Hà Nội - 2019
VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… ĐINH ĐỨC LƢƠNG 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Ĩ TOÁN HỌC Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10 Ngƣời hƣớng dẫn khoa học: 1. TS. Hoàng Đỗ Thanh Tùng 2. PGS. TS. Đặng Hữu Đạo Hà Nội - 2019
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.TS. Đặ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.TS. Đặ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 ................................................................................................................................... 1 Chƣơng 1. TỔNG QUAN....................................................................................................... 5 1.1. Tin sinh học và các nguồn dữ liệu ................................................................. 5 1.1.1. Tin sinh học ................................................................................5 1.1.2. Các nguồn dữ liệu .......................................................................6 1.1.3. Vấn đề tin sinh học và cơ sở dữ liệu sinh học ............................ 10 1.2. Các phương pháp đánh chỉ số dữ liệu sinh học và tin sinh học.................... 13 1.2.1. Chỉ số và mô hình bộ nhớ ngoài ................................................ 13 1.2.2. Các phương pháp đánh chỉ số cho dữ liệu sinh học ................... 14 1.2.2.1. Các thuật toán so sánh tương đồng thông qua chuỗi đại diện14 1.2.2.2. Các thuật toán sử dụng sự thay đổi cấu trúc chỉ số ............... 15 1.2.3. Các phương pháp đánh chỉ số cho dữ liệu tin sinh học .............. 17 1.3. Phương pháp đánh chỉ số tài liệu XML ....................................................... 18 1.3.1. Tài liệu XML và Xpath ............................................................. 18 1.3.2. 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ố............................... 24 1.3.2.1. Đánh số trên lược đồ............................................................ 24 1.3.2.2. Phép nối có cấu trúc ............................................................ 25 1.3.2.3. Chuyển đổi lên không gian đa chiều .................................... 28 1.3.2.4. Ánh xạ sang cơ sở dữ liệu quan hệ....................................... 29 1.4. Phương pháp R-tree..................................................................................... 31 1.4.1. Khái niệm R-tree....................................................................... 31 1.4.2. Cấu trúc R-tree.......................................................................... 31 1.4.3. Một số thuật toán cơ bản trong phương pháp R-tree .................. 33 1.4.4. Một số phương pháp cải tiến R-tree đánh chỉ số tài liệu XML... 41
ii 1.5. Các vấn đề còn tồn tại ................................................................................. 43 1.6. Kết luận ....................................................................................................... 45 Chƣơng 2. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ BIOX-TREE ........................................ 46 2.1. Mở đầu ........................................................................................................ 46 2.2. Phương pháp đánh chỉ số cải tiến BioX-tree ............................................... 52 2.2.1. Chuyển đổi tài liệu XML .......................................................... 52 2.2.2. Cấu trúc chỉ số trên cây BioX-tree ............................................ 54 2.2.3. Các thuật toán ........................................................................... 58 2.2.3.1. Thuật toán chèn ..................................................................... 58 2.2.3.2. Thuật toán truy vấn ................................................................ 62 2.2.4. Xử lý truy vấn ........................................................................... 64 2.2.4.1. Thuật toán cho các truy vấn anh em ....................................... 64 2.2.4.2. Thuật toán cho các truy vấn khác ........................................... 65 2.2.5. Đánh giá độ phức tạp của các thuật toán ................................... 67 2.3. Kết quả thực nghiệm phương pháp BioX-tree............................................. 68 2.3.1. Mô hình và môi trường thử nghiệm........................................... 68 2.3.2. Xây dựng chương trình ............................................................. 72 2.3.3. Đánh giá hiệu quả giảm kích thước dữ liệu ............................... 79 2.3.4. So sánh kết quả của phương pháp BioX-tree và R-tree.............. 82 2.4. Kết luận chương 2 ....................................................................................... 87 Chƣơng 3. PHƢƠNG PHÁP ĐÁNH CHỈ SỐ MỞ RỘNG BIOX+-TREE ................ 89 3.1. Mở đầu ........................................................................................................ 89 3.2. Phương pháp BioX+-tree ............................................................................. 91 3.2.1. Phân tích không gian dữ liệu chuyển đổi của tài liệu XML ....... 91 3.2.2. Các thuật toán đề xuất ............................................................... 94 3.3. Kết quả thực nghiệm phương pháp BioX+-tree ........................................... 96 3.3.1. Mô hình và môi trường thử nghiệm........................................... 96 3.3.2. So sánh kết quả của phương pháp BioX+-tree và BioX-tree ...... 98 3.4. Kết luận chương 3 ..................................................................................... 104 KẾT LUẬN........................................................................................................................... 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: Các trục Xpath....................................................................................... 22 Bảng 2.1: Thông tin cấu trúc của file trên đĩa ........................................................ 73 Bảng 2.2: Thông tin của BioX-tree ........................................................................ 73 Bảng 2.3: Thông tin Block..................................................................................... 73 Bảng 2.4: Thông tin phần tử .................................................................................. 73 Bảng 2.5: Chức năng của các lớp........................................................................... 74 Bảng 2.6: Kết quả truy vấn anh em BioX-tree ....................................................... 83 Bảng 2.7: Kết quả truy vấn con cái BioX-tree........................................................ 83 Bảng 2.8: Kết quả truy vấn tổ tiên BioX-tree ......................................................... 85 Bảng 2.9: Kết quả truy vấn hậu duệ BioX-tree....................................................... 85 Bảng 2.10: Kết quả truy vấn các node theo sau BioX-tree ..................................... 86 Bảng 2.11: Kết quả truy vấn các node phía trước BioX-tree .................................. 87 Bảng 3.1: Kết quả truy vấn anh em BioX+-tree ...................................................... 99 Bảng 3.2: Kết quả truy vấn anh em trước BioX+-tree ........................................... 100 Bảng 3.3: Kết quả truy vấn anh em sau BioX+-tree .............................................. 101 Bảng 3.4: Kết quả truy vấn con cái BioX+-tree .................................................... 102 Bảng 3.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 ................... 54 Thuật toán 2.2: Thuật toán chèn............................................................................. 59 Thuật toán 2.3: Thuật toán FindSiblingNode ......................................................... 60 Thuật toán 2.4: Thuật toán CreateNewLeafNode ................................................... 60 Thuật toán 2.5: Thuật toán truy vấn điểm .............................................................. 63 Thuật toán 2.6: Thuật toán truy vấn phạm vi.......................................................... 63 Thuật toán 2.7: Thuật toán truy vấn anh em ........................................................... 64 Thuật toán 2.8: Thuật toán truy vấn anh em sau ..................................................... 65 Thuật toán 2.9: Thuật toán truy vấn Anh em trước................................................. 65 Thuật toán 2.10: Thuật toán truy vấn con............................................................... 66 Thuật toán 2.11: Thuật toán truy vấn tổ tiên .......................................................... 67 Thuật toán 3.1: Thuật toán Insertion ...................................................................... 95 Thuật toán 3.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.......................................... 10 Hình 1.2: Mô hình hadoop kết hợp kho dữ liệu để xử lý dữ liệu thô ...................... 12 Hình 1.3: Sơ đồ mô tả các phương pháp đánh chỉ số CSDL sinh học ..................... 16 Hình 1.4: Ví dụ về tài liệu XML biểu diễn dưới dạng text và dạng cây .................. 19 Hình 1.5: Ví dụ tài liệu XML tin sinh học ............................................................. 20 Hình 1.6: Cây phân tích cú pháp của Q với 5 node N1 .... N5 ................................ 23 Hình 1.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 ................................................................................ 25 Hình 1.8: Ví dụ minh họa về đánh chỉ số trong XISS............................................. 26 Hình 1.9: Một ví dụ sử dụng các phép join ............................................................ 27 Hình 1.10: Ví dụ về vectơ trong không gian 3 chiều .............................................. 28 Hình 1.11: Biểu diễn cấu trúc cây R-tree ............................................................... 32 Hình 1.12: Biểu diễn 02 chiều của một R-tree ....................................................... 33 Hình 1.13: Trường hợp phân chia node (a) bad split, (b) good split. ...................... 38 Hình 1.14: Phân chia phần tử thành các nhóm node mới ........................................ 39 Hình 1.15: Cấu trúc cây XR-tree ........................................................................... 41 Hình 1.16: Xây dựng MBR trên không gian 2 chiều của phương pháp AR*-tree ... 42 Hình 1.17: Mô hình quy trình tổng quát ................................................................. 44 Hình 1.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 ............................................................................................................... 44 Hình 2.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 ................................................................................................................ 49 Hình 2.2: Ví dụ về phân phối các điểm quy đổi cho một tài liệu XML................... 50 Hình 2.3: Các thành phần được đề xuất cải tiến trong phương pháp BioX-tree ...... 52 Hình 2.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) ............................................................................... 53 Hình 2.5: Ví dụ về MBR trong cây BioX-tree........................................................ 56
viii Hình 2.6: Hệ thống cây phân cấp theo các tag trong tài liệu XML DNA gạo ......... 57 Hình 2.7: Các node lá thể hiện sự liên kết trên cây cấu trúc BioX-tree ................... 58 Hình 2.8: Ví dụ về quy trình chèn .......................................................................... 61 Hình 2.9: Mô hình thử nghiệm phương pháp BioX-tree và R-tree ......................... 69 Hình 2.10: Dữ liệu trong file XML DNACorn ....................................................... 70 Hình 2.11: Dữ liệu trong file XML DNARice........................................................ 70 Hình 2.12: Dữ liệu trong file XML Swissprot ........................................................ 71 Hình 2.13: Dữ liệu trong file XML Allhomologies ................................................ 72 Hình 2.14: Biểu đồ lớp của chương trình BioX-tree............................................... 77 Hình 2.15: Biểu đồ tuần tự của chương trình BioX-tree ........................................ 78 Hình 2.16: File dữ liệu DNACorn sau chuyển đổi ................................................. 79 Hình 2.17: File dữ liệu DNARice sau chuyển đổi .................................................. 80 Hình 2.18: File dữ liệu Swissprot sau chuyển đổi .................................................. 80 Hình 2.19: File dữ liệu Allhomologies sau chuyển đổi........................................... 80 Hình 2.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ố ....................................................................................................................... 81 Hình 2.21: Biểu đồ so sánh truy vấn anh em giữa BioX-tree và R-tree .................. 83 Hình 2.22: Biểu đồ so sánh truy vấn con cái giữa BioX-tree và R-tree ................... 84 Hình 2.23: Biểu đồ so sánh truy vấn tổ tiên giữa BioX-tree và R-tree .................... 85 Hình 2.24: Biểu đồ so sánh truy vấn hậu duệ giữa BioX-tree và R-tree.................. 86 Hình 2.25: Biểu đồ so sánh truy vấn các node theo sau giữa BioX-tree và R-tree .. 86 Hình 2.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 ... 91 Hình 3.2: Cây tài liệu XML được đánh số thứ tự ................................................... 92 Hình 3.3: Các MBR của node lá trong cây BioX-tree ............................................ 93 Hình 3.4: Mô hình thử nghiệm thuật toán BioX+-tree và BioX-tree ....................... 97 Hình 3.5: Biểu đồ so sánh truy vấn anh em BioX+-tree và BioX-tree .................... 99 Hình 3.6: Biểu đồ so sánh truy vấn anh em trước BioX+-tree và BioX-tree ......... 100 Hình 3.7: Biểu đồ so sánh truy vấn anh em sau BioX+-tree và BioX-tree ............ 101
ix Hình 3.8: Biểu đồ so sánh truy vấn con cái BioX+-tree và BioX-tree .................. 102 Hình 3.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. 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).
2 1. 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. 2. 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. 2. 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. 2. 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. 2. Áp dụng các phương pháp đánh chỉ số phù hợp.
3 3. 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…
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.
5 Chƣơng 1. TỔNG QUAN 1.1. Tin sinh học và các nguồn dữ liệu 1.1.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…
6 1.1.2. 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. Cơ sở dữ liệu sinh học thường chứa các thông tin về trình tự axit nucleic (DNA, ARN), trình tự axit amin của các phân tử protein, thông tin về cấu trúc và giải phẫu của một số genome, mô hình cấu trúc không gian của các đại phân tử. Cơ sở dữ liệu NCBI: NCBI - National Center for BioInformatic Information là trung tâm quốc gia về công nghệ sinh học thuộc viện sức khỏe quốc gia Hoa Kỳ. NCBI được thành lập ngày 04/10/1988, đảm nhiệm việc quản lý CSDL trình tự DNA và từ đó còn được gọi là GenBank. NCBI là nơi cung cấp, trao đổi thông tin về sinh học phân tử của Mỹ thông qua những CSDL trực tuyến. Ngoài ra, còn tham gia những nghiên cứu về sinh học tính toán, phát triển các công cụ phân tích bộ gen, protein…. Trong NCBI, chứa đựng nhiều CSDL chuyên dụng khác như: - CSDL tài liệu (Literature Database): Bookshelf, PubMed, PubMed Central: Tìm kiếm những thông tin cơ bản hoặc các chủ đề nghiên cứu mới, miễn phí. PubMed chứa phần tóm tắt của hơn 15.000.000 kết quả nghiên cứu trong lĩnh vực sinh y học. - CSDL Nucleotide (Nucleotide databases)
7 + GenBank: Tập hợp tất cả các trình tự nucleotide và axit amin hiện có. Trong lần công bố gần đây nhất, INSDC cho biết CSDL trình tự DNA đã vượt quá 100 TeraByte. + GenBank® là CSDL trình tự di truyền của NIH. Có khoảng 51.674.486.881 base trong 46.947.388 bản trình tự trong các nhánh của GenBank và 53.346.605.784 base trong 10.276.161 bản ghi trình tự ở nhánh WGS vào 8/2005. + Ngoài ra còn có các CSDL chủ đề trực thuộc GenBank như: dbEST (data base of Expressed Sequence Tags), HomoloGene, MGC (Mamalian Gene Collection), PopSet, TPA: Third Party Annotation (TPA) Sequence. - CSDL Protein (Protein Databases) 3D Domains: Bao gồm các trình tự và cấu trúc 3 chiều của các domain trong các phân tử protein. + Cơ sở dữ liệu cấu trúc (Structure Databases) 3D Domain: MMDB (Molecular Modeling Database) là CSDL mô hình cấu trúc phân tử 3D, bao gồm các protein và các polynucleotide. MMDB chứa hơn 28.000 cấu trúc và được liên kết với phần còn lại của CSDL ở NCBI. - Cơ sở dữ liệu hệ thống học (Taxonomy database) chứa tên của các sinh vật có mặt trong cơ sở dữ liệu di truyền với ít nhất một trình tự nucleotide hoặc protein. NCBI cung cấp một hệ thống hệ thống phân loại cùng với các đơn vị phân loại (taxa). - Cơ sở dữ liệu genome (genome database) + Các nhiễm sắc thể ung thư: Cancer Chromosomes: 3 cơ sở dữ liệu NCI/NCBI SKY/M-FISH và CGH. + Cơ sử dữ liệu các Gene, Genome Project, Genomes: Các gen, các trình tự được lưu trữ trong một hệ thống, để truy cập có thể sử dụng các công cụ như Entrez Gene. Cơ sở dữ liệu EMBL/EBI