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.