Tóm tắt Luận văn Nghiên cứu thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tìm kiếm tương tự nhanh

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN HOÀNG ANH NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 01 04 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: Tiến sĩ Nguyễn Thị Hậu HÀ NỘI – 2016 2 LỜI CAM ĐOAN Tôi xin cam đoan nội dung của luận văn “Nghiên cứu thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tương tự nhanh” là sản phẩm do tôi thực hiện dưới sự hướng dẫn của TS. Nguyễn Thị Hậu. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 20 tháng 9 năm 2016 TÁC GIẢ Nguyễn Hoàng Anh 3 MỤC LỤC LỜI CAM ĐOAN ......................................................................................... 2 DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ............................................ 5 GIỚI THIỆU ................................................................................................. 6 CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA ................................................................................................ 7 1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn 7 1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ ..................................... 8 1.3. Phƣơng pháp tìm kiếm tƣơng tự nhanh ..................................... 9 1.4. Phƣơng pháp sử dụng mô hình phù hợp gần đúng ................. 10 1.5. Phƣơng pháp sử dụng mô hình kết hợp chính xác và gần chính xác 10 CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM. ........................................... 12 2.1. Mô hình N-Gram ........................................................................ 12 2.1.1. Một số khái niệm .................................................................. 12 2.1.2. Mô hình ngôn ngữ N-gram ................................................... 12 2.1.3. Công thức tính “xác suất thô” ............................................... 12 2.1.4. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ........... 13 2.2. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA. ...................................................................................................... 13 2.2.1. Phân đoạn DNA .................................................................... 13 2.2.2. Các “từ DNA” ...................................................................... 13 2.2.3. Quá trình tìm kiếm chuỗi và hiển thị kết quả ....................... 14 2.3. Bảng kết quả các lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram .................................................................... 16 4 2.3.1. Định dạng chuỗi cơ sở dữ liệu .............................................. 16 2.3.2. Bảng kết quả các lần thử phương pháp tìm kiếm chuỗi tương tự nhanh áp dụng N-Gram .................................................................... 17 2.4. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram .......................................................................................... 17 2.4.1. Cải thiện thời gian tìm kiếm ................................................. 17 2.4.2. Tiết kiệm bộ nhớ trong quá trình tìm kiếm ........................... 18 CHƢƠNG 3. THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁP BLAST VÀ PHƢƠNG PHÁP SMITH-WATERMAN ........................... 19 3.1. Môi trƣờng thực nghiệm ............................................................ 19 3.2. Thực nghiệm đánh giá phƣơng pháp tìm kiếm tƣơng tự nhanh áp dụng N-Gram với phƣơng pháp BLAST và phƣơng pháp Smith- Water Man .............................................................................................. 21 KẾT LUẬN ................................................................................................. 22 TÀI LIỆU THAM KHẢO .......................................................................... 23 5 DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu Tiếng Anh Tiếng Việt DNA Deoxy Ribonucleic Acid Phân tử mang cấu trúc gen di truyền NST Chromosome Nhiễm sắc thể A Adenine T Thymine G Guanine C Cytosine SNP Single nucleotide polymorphisms Tính đa hình của phân tử nucleotit. Mỗi SNP biểu diễn một biến đổi trong một khối chuỗi DNA CPU Cental Processing Unit Bộ xử lý trung tâm RAM Random access memory Bộ nhớ truy cập ngẫu nhiên NCBI National Center for Biotechnology Information Trung tâm quốc gia thông tin công nghệ sinh Differential Direct coding Mã hóa trực tiếp phần khác biệt HMM Hidden Markov Modeling Mô hình Markov ẩn BLAST Basic Local Alignment Search Tool Công cụ tìm kiếm cục bộ theo mẫu có sẵn HTS High – Throughput Sequencing Trình tự chuỗi đa lượng 6 GIỚI THIỆU Việc phát hiện ra DNA là một bước ngoặt lớn trong khoa học sinh học nói riêng và cuộc sống của con người nói chung. DNA có chức năng chính là lưu giữ truyền đạt và bảo quản thông tin di truyền giữa các thế hệ. Có rất nhiều ứng dụng từ việc tìm kiếm chuỗi DNA cả trong khoa học và đời sống con người, chẳng hạn như:  Sự di truyền trí thông minh. [1].  Kiểm tra quan hệ cùng huyết thống [2]  Phát hiện các loại gen gây bệnh [3]  Ứng dụng trong khoa học hình sự [4]  Lý thuyết tiến hóa. Có hàng trăm thuật toán đã được đề xuất cho tìm kiếm dữ liệu DNA nhưng nhìn chung các thuật toán tìm kiếm thường được sử dụng là:  Phương pháp áp dụng Mô hình Markov ẩn[5].  Phương pháp liên kết nhạy cảm đầy đủ: Vd: thuật toán Smith&Waterman[6].  Phương pháp tìm kiếm tương tự nhanh: Vd: BLAST [7].  Phương pháp sử dụng mô hình phù hợp gần đúng: Vd: Bowtie[8].  Phương pháp sử dụng mô hình kết hợp chính xác và gần chính xác: Vd: mpscan[9]. Bố cục luận văn được chia thành 3 chương. Chương 1 trình bày về tổng quan các phương pháp sử dụng để tìm kiếm chuỗi DNA. Thuật toán tìm kiếm cụ thể mà người viết tập trung nghiên cứu là thuật toán tìm kiếm chuỗi DNA sử dụng phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram được trình bày ở chương 2. Chương 3 của luận văn mô tả môi trường thực nghiệm so sánh thuật toán tương tự nhanh áp dụng N-gram với phương pháp tìm kiếm khác và một số phân tích đánh giá của người viết về kết quả đạt được. Cuối cùng là kết luận về hiệu quả cũng như hạn chế còn tồn tại và hướng phát triển trong tương lai cho việc nghiên cứu và cải tiến phương pháp tìm kiếm chuỗi DNA. 7 CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA 1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn Thuật toán tìm kiếm chuỗi sử dụng mô hình Markov ẩn dùng phương pháp mô hình hóa quá trình tìm kiếm chuỗi trong đó có sử dụng các tham số quan sát được và các tham số không biết trước – mô hình Markov. Sau đó sẽ xác định các tham số không biết trước từ các tham số quan sát được. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp. Với mô hình Markov ẩn cấu trúc mô hình có thể thay đổi dễ dàng cho phù hợp với từng ứng dụng cụ thể. Hình 1.1: Mô hình Markov ẩn cho tìm tiếm chuỗi DNA [5] a. Sắp xếp các chuỗi ban đầu. b. Mô hình Markov ẩn (bỏ khoảng trống giữa các trạng thái). c. Mô hình hóa sự liên kết theo Mô hình Markov ẩn Ưu điểm: Phương pháp này đã được sử dụng rộng rãi trong tin sinh học vì độ chính xác cao. Cách mô hình hóa dễ sử dụng. Nhược điểm: Chi phí thời gian lớn và các hàm tính toán phức tạp. 8 1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ Phương pháp này được sử dụng để tìm sự giống nhau hoặc có độ tương đồng cao của hai chuỗi. Bằng cách lập ma trận, tính độ đo để tìm ra sự giống hoặc có độ tương đồng cao của tất cả độ dài các phân đoạn của hai xâu, hai chuỗi protein hoặc nucleotide. Với chuỗi đã được tìm kiếm và có độ tương đồng cao trước đó, phương pháp có thể mở rộng phạm vi tìm kiếm về hai phía (trước hoặc sau). Phương pháp này có ưu điểm là độ chính xác cao. Tuy nhiên chi phí thời gian lớn. Phương pháp đặc trưng của dạng này là phương pháp Smith & Waterman do hai nhà khoa học T.F.Smith & M.S.Waterman công bố năm 1981. [6] Hiện nay, do những cải tiến về máy tính và thuật toán tìm kiếm, phương pháp này có thể tìm kiếm đồng thời nhiều chuỗi cùng lúc khoảng (1000 chuỗi). [18] Hình 1.3. Bảng ma trận độ đo trong ví dụ 2 chuỗi của Smith&Waterman [2] Chuỗi A-A-U-G-C-C-A-U-U-G-A-C-G-G và chuỗi C-A-G-C-C-U-C-G-C-U-U-A-G Ưu điểm: Do phải duyệt và so sánh lần lượt thứ tự từng nucleotide nên phương pháp này có độ chính xác cao. 9 Nhược điểm: Chi phí thời gian lớn do phải lập ma trận đánh giá mức độ tương đồng, lập chỉ số so sánh giá trị của các phần tử trong ma trận của các chuỗi. Thuật toán cũng phải so sánh các giá trị ở chuỗi mẫu với chuỗi dữ liệu 1.3. Phƣơng pháp tìm kiếm tƣơng tự nhanh Phương pháp này sử dụng giải thuật so sánh chuỗi cần truy vấn với CSDL chuỗi có sẵn dựa trên việc đánh giá chuỗi cơ sở dữ liệu với chuỗi truy vấn theo một ngưỡng nhất định (đánh giá, cho điểm theo chỉ số cụ thể). Thuật toán điển hình của phương pháp này là BLAST (hiện nay phương pháp BLAST được dùng rất phổ biến và có nhiều biến thể để so sánh với từng trường hợp cụ thể). BLAST ban đầu tìm kiếm các chuỗi con ngắn với chiều dài cố định có tính tương tự cao. Sau đó, dựa vào kết quả trước, mở rộng phạm vi tìm kiếm để tìm những bắt cặp trình tự có điểm số cao giữa chuỗi truy vấn và các chuỗi trong cơ sở dữ liệu. Tốc độ và sự chính xác tương đối của BLAST là những cải tiến kĩ thuật quan trọng của các chương trình BLAST và những điều đó cho thấy lí do vì sao công cụ này lại là công cụ tìm kiếm phổ biến nhất trong tin sinh học. Hình 1.4. Thiết lập “từ” với ba “ký tự” để truy vấn theo danh sách [5] Ưu điểm: Do chỉ việc phải so sánh chuỗi cần truy vấn với thư viện hoặc CSDL chuỗi có sẵn. Sau đó, đối sánh chuỗi ở thư viện hoặc cơ sở dữ liệu với chuỗi truy vấn theo một ngưỡng nhất định nên phương pháp có thời gian xử lý nhanh. Nhược điểm: Phương pháp này có độ chính xác không cao (VD: so với phương pháp liên kết nhạy cảm đầy đủ phương pháp này độ chính xác không bằng). 10 1.4. Phƣơng pháp sử dụng mô hình phù hợp gần đúng Kỹ thuật tìm kiếm chuỗi phù hợp với một mô hình gần đúng (chứ không phải là chính xác). Mô hình này sử dụng cách tiếp cận brute-force để tính “độ chỉnh sửa” chuỗi mẫu sao cho gần đúng với tất cả các chuỗi con của chuỗi cần truy vấn, sau đó chọn các chuỗi với “độ chỉnh sửa” tối thiểu. Tuy nhiên, thuật toán này sẽ có thời gian chạy O(n3m). Ở đây m là độ dài chuỗi mẫu, n là độ dài chuỗi cần truy vấn). Phương pháp điển hình của mô hình phù hợp gần đúng là phương pháp tìm kiếm chuỗi Bowtie, được nhà khoa học Langmead và cộng sự đăng lần đầu tiên trên tạp chí Curr Protoc Bioinformatics vào năm 2010. [8] Thuật toán: [8] Bước 1: Xác định điểm chung từ các mẫu Từ tập các mẫu đầu vào, sắp xếp và tìm điểm chung giữa các tập chuỗi. Bước 2: Phân loại và đo độ ảnh hưởng: Từ các tập mẫu, tính toán và đưa ra độ dài chuỗi dài nhất có thể từ các mẫu . Bước 3: Tìm kiếm và đưa ra kết quả. Kết quả hiển thị là tập các chuỗi cần so sánh có bắt cặp trình tự với chuỗi mẫu. Thứ tự các chuỗi được sắp xếp theo thứ tự như sau: Chuỗi có ít bắt cặp trình tự đứng trước. Các chuỗi có độ dài bắt cặp trình tự lớn đứng sau (theo hình kim tự tháp). Ưu điểm: Có thể tìm kiếm cùng lúc nhiều mẫu. Độ chính xác cao. Nhược điểm: Thuật toán này có chi phí thời gian chạy O(n3m). (với m là độ dài chuỗi mẫu, n là độ dài chuỗi cần truy vấn). Sử dụng nhiều bộ nhớ trong quá trình tìm kiếm. 1.5. Phƣơng pháp sử dụng mô hình kết hợp chính xác và gần chính xác Mô hình áp dụng phương pháp đánh dấu tập mẫu, tức là chia chuỗi cần truy vấn thành các chuỗi mẫu con nhỏ với chiều dài cố định. Sau đó, so sánh 11 các chuỗi con đã được chia đó với chuỗi trong cơ sở dữ liệu để tìm kiếm sự tương đồng. Phương pháp đạt hiệu quả chính xác cho việc giải trình tự DNA/RNA, có thể thực hiện xử lý nhiều mẫu. Phương pháp này thường được dùng và rất có hiệu quả trong việc tìm kiếm một tập lớn các chuỗi DNA/RNA ngắn trong một CSDL các chuỗi DNA. Phương pháp điển hình của thuật giải này là Mpscan [9]. Chương trình này tìm kiếm đồng thời các tập mẫu ngắn. Các mẫu này có thể tìm đồng thời cùng lúc. Quá trình tìm kiếm đồng thời có thể lên tới 100000 mẫu. Ƣu điểm: Phương pháp này rất có hiệu quả trong việc tìm kiếm một tập lớn các chuỗi DNA ngắn trong một CSDL các chuỗi DNA. Có thể đọc được bản đồ ngay trên giao diện. Có khả năng tìm kiếm ngược, bổ sung mẫu. Nhƣợc điểm: So với các phương pháp khác, thời gian thực hiện của phương pháp này ở mức độ trung bình. 12 CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM. 2.1. Mô hình N-Gram 2.1.1. Một số khái niệm  Ngữ liệu (Corpus) : là tập hợp các văn bản, ngôn ngữ đã được số hóa. (kho ngữ liệu) hoặc tập huấn luyện trong một số bài báo khoa học.  N-gram : là tần suất xuất hiện của n kí tự (hoặc từ) liên tiếp nhau có trong dữ liệu corpus. 2.1.2. Mô hình ngôn ngữ N-gram Mô hình ngôn ngữ là cho biết xác suất của một câu w 1w 2...w m là bao nhiêu. Theo công thức Bayes: P(AB) = P(B|A) * P(A) [11] Với: + P(A): Xác suất xảy ra sựkiện A + P(B): Xác suất xảy ra sự kiện B + P(B|A): Xác suất (có điều kiện) xảy ra sự kiện B. Một cụm N-gram là 1 dãy con gồm n phần tử liên tiếp nhau của 1 dãy các phần tử cho trước. 2.1.3. Công thức tính “xác suất thô” Gọi C(w i-n+1...w i-1w i) là tần số xuất hiện của cụm w i-n+1...w i-1w i trong tập văn bản huấn luyện. Gọi P(w i|w i-n+1...w i-1) là xác suất w i đi sau cụm w i-n+1..w i-2w i-1. Ta có công thức tính xác suất như sau: P(w i|w i-n+1...w i-1) = C(w i-n+1...w i-1w i)  w C(w i-n+1...w i-1w) [11] Tỉ lệ ở vế phải còn gọi là tỉ lệ tần số. Cách tính xác suất dựa vào tỉ lệ tần số còn gọi là ước lượng xác suất cực đại. Cũng có thể gọi đây là công thức 13 tính “xác suất thô” để phân biệt với các cách tính xác suất theo các thuật toán hiệu quả hơn. 2.1.4. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : Phân bố không đều Khi các N-gram phân bố thưa, nhiều cụm n-gram không xuất hiện hoặc chỉ có số lần xuất hiện nhỏ, việc ước lượng các câu có chứa các cụm n-gram này sẽ có kết quả tồi. Với V là kích thước bộ từ vựng, ta sẽ có Vn cụm N- gram có thể sinh từ bộ từ vựng. Kích thƣớc bộ nhớ của mô hình ngôn ngữ : Khi kích thước tập văn bản huấn luyện lớn, số lượng các cụm N-gram và kích thước của mô hình ngôn ngữ cũng rất lớn (tăng theo hàm mũ). 2.2. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA. Việc đánh chỉ số tuần tự (sequence index) được sử dụng trong các kỹ thuật tìm kiếm nhanh, giúp chúng ta chỉ cần truy xuất kết quả dựa vào bảng các chỉ số đã được thống kê. 2.2.1. Phân đoạn DNA Trong tài liệu này, chúng ta sử dụng ví dụ chuỗi DNA để giải thích chi tiết kỹ thuật tìm kiếm. Bằng việc chia chuỗi DNA thành các chuỗi có độ dài nhỏ hơn, giống như việc chia một cuốn sách thành các chương mục, không có quy định về việc chia một chuỗi DNA có độ dài bằng bao nhiêu thì hợp lý, thông thường người ta chia thành các chuỗi có độ dài 100, 500, 1000, 10000 , sau đó ta đánh ID cho từng đoạn đó. Trong tài liệu này ta chia một chuỗi DNA dài thành các đoạn có độ dài 500 ký tự. 2.2.2. Các “từ DNA” 14 Với ngôn ngữ tự nhiên giống như tiếng anh, việc xác định câu từ là việc dễ dàng nhờ có khoảng trống hoặc các dấu ngắt câu. Nhưng với chuỗi DNA, không hề có khoảng trống để phân biệt, để có thể tách thành các chuối ngắn hơn, cách đơn giản nhất ta dùng phương thức n-gram ví dụ: T = “ABCDE” 1-gram chia chuỗi T thành tập {A, B, C, D, E}. 2-gram chia chuỗi T thành tập {AB, BC, CD, DE}. Trong bài viết này, ta chọn 12-gram để phân chia tập. 2.2.3. Quá trình tìm kiếm chuỗi và hiển thị kết quả Đầu vào chương trình gồm hai chuỗi: - Chuỗi tìm kiếm là chuỗi được nhập từ bàn phím. - Chuỗi từ điển – Chuỗi được trích ra từ cơ sở dữ liệu chuỗi có sẵn. Đầu tiên chương trình xắp xếp thứ tự các “từ” chứa trong các chuỗi tìm kiếm DNA sao cho đầu vào là các chuỗi có độ dài được xác định cụ thể. Sau đó, phân tích chuỗi tìm kiếm thành các “từ”, mỗi “từ” có độ dài bằng giá trị n trong n-gram, trong mô hình này n = 12. Với mỗi từ được tách ra sẽ được ghi vào tệp Index – tệp lưu thông tin: tên chuỗi, vị trí của chuỗi đó trong chuỗi từ điển. Mỗi từ có thể xuất hiện ở đoạn con DNA khác nhau. Lấy giao của các tập trên chúng ta có vị trí chuỗi cần tìm, giá trị này là tập các chuỗi con có thể chứa chuỗi đầu vào. Chƣơng trình đƣợc thực hiện qua hai bƣớc chính:  Tiền xử lý: + Duyệt lần lượt các file gen FASTA đầu vào. Chia đoạn gen mẫu thành các đoạn nhỏ. Mỗi đoạn gồm 500 ký tự A, T, G, C. Đồng thời đánh dấu DocID cho mỗi đoạn. Với mỗi file FASTA sẽ tạo ra các file sau: 15 *.n-gram: file tách các chuỗi DNA thành các dạng N-Gram và tần suất xuất hiện của chuỗi n-gram đó trong file FASTA. Nội dung các file được sắp xếp theo trình tự file có tần suất xuất hiện cao ở trước, tần suất xuất hiện thấp ở sau. *.div: file chia nhỏ nội dung file FASTA thành nhiều doc. *.idx: Đầu vào tạo file này là file *.div. Nội dung gồm docID (số thứ tự đếm tăng dần), vị trí offset của doc trong file *.div. *.seg: đầu vào là file *.div và *.idx. Nội dung bao gồm docId và chia nội dung của từng docId theo dạng n-gram. *.frd: đầu vào là file *.seg: tạo forward index. Nội dung gồm docId và nội dung từng đoạn chia trong file *.seg. *.inv.idx và *.inv: đầu vào là file *.frd và *.idx: tạo invert index. Nội dung file *.inv.idx bao gồm nội dung đoạn chia trong file *.frd + offset bên file *.inv. Nội dung file *.inv bao gồm đoạn chia trong file *.frd và docId.  Tìm kiếm và đƣa ra kết quả: Tìm kiếm: + Tách chuỗi tìm kiếm thành các segment theo n-gram với n được nhập vào từ bàn phím. + Lấy danh sách offset của từng segment đã tách trong file *.inv.idx + Lấy danh sách docId của từng segment đã tách trong file *.inv + Lấy danh sách của từng segment trong file *.n-gram. Do file *.n-gram đã được sắp xếp nên danh sách này cũng được sắp xếp theo tần suất xuất hiện. + Lấy 3 danh sách offset, docId, segment để đưa ra vị trí chuỗi cần tìm. Hiển thị kết quả: 16 + DocId nào có số lần xuất hiện chuỗi cần tìm kiếm nhiều nhất thì đưa ra trước. + Kết quả đưa ra màn hình hiển thị gồm Tổng số kết quả được tìm thấy, DocId, tên loại gen, vị trí đoạn tìm thấy trong mẫu gốc, thời gian tìm kiếm. Hình 2.9. Hiển thị kết quả trên màn hình. 2.3. Bảng kết quả các lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram 2.3.1. Định dạng chuỗi cơ sở dữ liệu Trong bài viết, các tệp cơ sở dữ liệu được sử dụng để tìm kiếm chuỗi con trong đó đều được định dạng theo chuẩn FASTA. Định dạng FASTA là một định dạng tệp văn bản, thể hiện cho một trong hai loại chuỗi dưới dạng số hóa: chuỗi nucleotide hoặc amino axit. Một tệp ở định dạng FASTA gồm nhiều dòng. Dòng đầu tiên (còn gọi là dòng tiêu đề) dùng để mô tả thông tin chuỗi trong ngân hàng CSDL. Ký tự đầu tiên của dòng này là ký tự ">" (dấu 17 lớn hơn) hoặc ";" (dấu chấm phẩy - ít gặp). Các dòng còn lại thể hiện thông tin mà đoạn DNA lưu trữ 2.3.2. Bảng kết quả các lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram Tất cả các dữ liệu được thử nghiệm trên các bộ dữ liệu chuẩn. Dữ liệu đầu vào là các tệp định dạng FASTA trích xuất từ chuỗi gen gốc của ngân hàng dữ liệu gen NCBI. Chương trình được thực hiện với 11 lần thử. Với các cơ sở dữ liệu mẫu được trích xuất từ bộ gen gốc trong cơ sở dữ liệu gen của NCBI. Chi tiết các lần thử được thể hiện ở bảng 1. STT Tên loại gen Dung lượng tệp đầu vào (byte) Bộ nhớ RAM sử dụng (byte) Thời gian (giây) Tiền xử lý Tìm kiếm Hiển thị kết quả 1 Chr-1 1 000 ~ 1 000 000 1 2 1 2 Chr-2 5 000 ~ 2 000 000 4 2 1 3 Chr-3 8 000 ~ 3 000 000 7 2 1 4 Chr-4 10 000 ~ 4 000 000 8 3 1 5 Chr-5 12 000 ~ 5 000 000 10 3 1 6 Chr-6 100 000 ~ 10 000 000 30 4 1 7 Chr-7 1 008 000 ~ 15 000 000 58 5 1 8 Chr-8 2 107 000 ~ 20 000 000 71 7 1 9 Chr-9 12 000 000 ~ 400 000 000 308 11 1 10 Ec-1 4 584 860 ~ 30 000 000 100 8 1 11 Ec-2 5 100 000 ~ 40 000 000 120 8 1 Bảng 1. Chi tiết các lần chạy thử chương trình. 2.4. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram 2.4.1. Cải thiện thời gian tìm kiếm 18 Với việc chia đoạn gen cơ sở dữ liệu ban đầu thành các đoạn nhỏ hơn, sau đó sử dụng phương pháp đánh chỉ mục cho các đoạn nhỏ hơn đó, việc truy xuất kết quả chỉ thực hiện trên các bảng chỉ mục này. Việc đánh chỉ mục là rõ ràng vì được đánh theo số thứ tự cụ thể nên không có sự nhập nhằng trong quá trình tìm kiếm. Hơn nữa các bảng chỉ mục có sự liên kết với nhau thông qua các định dạng tệp được chia nhỏ trong quá trình tiền xử lý. Các định dạng tệp được đánh chỉ mục bằng số thứ tự, có vị trí bắt đầu, vị trí kết thúc đoạn theo cơ sở dữ liệu chuỗi đầu vào. Chính vì vậy việc tìm kiếm chỉ diễn ra ở những đoạn đã được chia. Với độ lớn khoảng 2000 kb mỗi đoạn, việc máy tính cá nhân tìm kiếm dữ liệu khoảng 80 kb đến 200 kb trong các đoạn 2000 kb là hoàn toàn có thể thực hiện được một cách nhanh chóng. 2.4.2. Tiết kiệm bộ nhớ trong quá trình tìm kiếm Chương trình được thực hiện qua hai bước chính là tiền xử lý và tìm kiếm, đưa kết quả ra màn hình. Ở bước đầu tiên – tiền xử lý, chương trình đã chia nhỏ tệp cơ sở dữ liệu thành các đoạn nhỏ hơn – với độ dài 500 ký tự, sau đó lập bảng, đánh chỉ mục cho các đoạn nhỏ này. Nên việc truy xuất trong quá trình tìm kiếm sẽ là việc truy xuất vào các đoạn dữ liệu này. Với tốc độ của máy tính hiện nay, việc truy xuất và tìm kiếm một đoạn khoảng vài chục byte trong một cơ sở dữ liệu độ lớn khoảng 4000 byte là thực hiện được và có thể thực hiện được nhanh chóng. Ví dụ: Ở bảng 2.1 từ quá trình tìm kiếm đến việc đưa ra kết quả cho một đoạn mẫu 12 nucleotide trong một tệp cơ sở dữ liệu 1 kb đầu vào chỉ mất khoảng 1kb bộ nhớ RAM thì với phương pháp Smith&Water Man quá trình tìm kiếm đến quá trình hiển thị kết quả bộ nhớ RAM cần sử dụng tổng cộng 500 kb. 19 CHƢƠNG 3. THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾM TƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁP BLAST VÀ PHƢƠNG PHÁP SMITH- WATERMAN 3.1. Môi trƣờng thực nghiệm Tất cả thực nghiệm được thực hiện trên máy tính cá nhân Dell Vostro 15 3000 Series với cấu hình như sau: CPU: Intel(R) Core(TM) i5-5250M CPU @ 1.6GHz / L2 cache. Bộ nhớ: 4GB RAM (1x2GB, 1x2GB)/ DIMM. Dung lượng: 500GB/ SCSI/ Disk drives TOSHIBA MQ01ABF050 Phần mềm sử dụng: Các chương trình được chạy trên nền Linux kernel (64-bit). Chương trình được viết và chỉnh sửa bằng ngôn ngữ C++ sử dụng QT Creator (build 1.7.0 40-b43). BLAST và SMITH&WATERMAN được viết và chỉnh sửa bằng ngôn ngữ C++. Các tập dữ liệu thực nghiệm: (1) Tập dữ liệu gen người được lấy từ cơ sở dữ liệu của NCBI dùng cho nghiên cứu. Trích rút ra một chuỗi liên ứng mỗi loại cho các gen. (2) Các tập dữ liệu Escherichia coli được lấy từ cơ sở dữ liệu của NCBI. Tập hợp tất cả tập dữ liệu Escherichia coli được kí hiệu là Ec-*. Hầu hết thời gian các lần tìm kiếm của BLAST đều nhanh hơn phương pháp Smith-Waterman khi tìm kiếm với chuỗi từ điển có dung lượng nhỏ và khi tìm kiếm với chuỗi từ điểm có dung lượng lớn. Số chuỗi tìm kiếm được của BLAST trong các lần tìm kiếm với các đoạn chuỗi dung lượng nhỏ đều xấp xỉ với Smith-Waterman và N-Gram. Ở các lần tìm kiếm với chuỗi từ điển dung lượng lớn, phương pháp Smith-Waterman tìm thấy nhiều kết quả nhất, sau đó đến BLAST, cuối cùng là N-Gram. Khi tìm kiếm với các chuỗi từ điển dung lượng nhỏ (khoảng dưới 2 Mb), thời gian đưa ra kết quả của N- Gram là nhanh nhất, tiếp theo là BLAST, cuối cùng là Smith-Waterman. Khi tìm kiếm với chuỗi từ điển có dung lượng lớn hơn ( >5 Mb), phương pháp N-Gram vẫn đưa ra kết quả nhanh nhất nhưng số kết quả tìm được không bằng BLAST và Smith-Waterman. Với dung lượng chuỗi từ điển 5Mb- 10Mb, N-Gram vẫn tiết kiệm bộ nhớ hơn BLAST và Smith-Waterman. Khi 20 dung lượng chuỗi từ điển >50Mb, bộ nhớ sử dụng của phương pháp N-Gram tăng đáng kể > 2Gb. Như vậy, có thể thấy phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram đạt hiệu quả cao về tiết kiệm bộ nhớ, thời gian tìm kiếm, số lượng kết quả tìm được khi tìm kiếm với các chuỗi từ điển dung lượng nhỏ. Mặc dù khi sử dụng phương pháp này với các chuỗi có dung lượng lớn, thời gian đưa ra kết quả vẫn nhanh hơn hai phương pháp còn lại nhưng số kết quả tìm được không nhiều bằng hai phương pháp còn lại. Hiệu số kết quả tìm được của BLAST và Smith-Waterman so với N-Gram tăng dần theo độ lớn của dung lượng chuỗi từ điển. Hình 3.3. Minh họa kết quả chạy BLAST độ dài chuỗi truy vấn là 12 với mẫu gen thử Chr-4 Hình 3.4. Minh họa kết quả chương trình sử dụng phương pháp Smith- Waterman với độ dài chuỗi truy vấn là 12 21 3.2. Thực nghiệm đánh giá phƣơng pháp tìm kiếm tƣơng tự nhanh áp dụng N-Gram với phƣơng pháp BLAST và phƣơng pháp Smith- Water Man Phương pháp N-Gram đạt hiệu của cao về số kết quả tìm được, thời gian xử lý, dung lượng bộ nhớ khi tìm kiếm với các chuỗi từ điển dung lượng nhỏ (< 8Mb) so với BLAST và Smith-Waterman. Đây cũng chính là ưu điểm của phương pháp này. Khi tìm kiếm với các chuỗi từ điển có dung lượng > 10Mb, ở các lần thực nghiệm, số kết quả tìm được của N-Gam không bằng hai phương pháp còn lại (mặc dù thời gian tìm kiếm vẫn nhanh hơn). Số chuỗi không tìm được so với hai phương pháp còn lại tăng dần theo độ lớn dung lượng chuỗi từ điển. Nguyên nhân là do quá trình chia tách tệp dữ liệu từ điển đầu vào không triệt để. Các đoạn gen ở cuối đoạn chia này và đoạn gen ở đầu đoạn sau có thể nằm trong kết quả chuỗi cần tìm kiếm. Kết quả thực nghiệm đã cho thấy với tệp cơ sở dữ liệu từ điển có dung lượng dưới 2Mb, N-Gram đạt hiệu quả về thời gian tìm kiếm tốt hơn hai thuật toán khác là tìm kiếm chuỗi tương tự nhanh BLAST và phương pháp tìm kiếm chuỗi nhạy cảm đầy đủ Smith-Waterman. Thời gian tìm kiếm trung bình cho những tệp cơ sở dữ liệu từ điển dung lượng dưới 2Mb cỡ 100 giây. Trong khi đó, với BLAST là khoảng 160 giây, với Smith-Waterman là khoảng 190 giây. 22 KẾT LUẬN Thuật toán đã đạt được hiệu quả trong việc tăng hiệu quả tìm kiếm chuỗi bằng 3 phương pháp kế thừa: (1) tìm kiếm những bắt cặp trình tự ngắn, (2) đánh giá những bắt cặp trình tự có điểm số cao và (3) thống kê kết quả đạt được. Bên cạnh những đặc trưng kế thừa từ thuật toán tìm kiếm tương tự nhan BLAST, N-Gram còn thực sự hiệu quả khi sử dụng phương pháp đánh chỉ số để tiết kiệm thời gian tìm kiếm và đưa ra kết quả đáng kể. Đóng góp chính của N-Gram là chia chuỗi gen từ điển thành các đoạn có độ dài ngắn (500 ký tự), sau đó sử dụng phương thức đánh chỉ số cho các phân đoạn độ dài và theo N-gram đơn vị cho chuỗi truy vấn. Cơ chế này kết hợp được hai đặc tính tốt nhất đó là: một cấu trúc khá đơn giản và có thể đưa ra kết quả nhanh chỉ bằng việc truy vấn theo các chỉ số. Hai đặc tính này giúp N-Gram đạt được những ưu việt về thời gian tìm kiếm và khả năng tiết kiệm bộ nhớ. N-Gram có nhược điểm là khi tìm kiếm với chuỗi có dung lượng hơn 8Mb, số lượng các kết quả tìm được đều thấp hơn BLAST và Smith-Waterman. Nguyên nhân là do việc chia chuỗi gen từ điển thành các đoạn nhỏ, ở điểm cuối của đoạn chia này và điểm đầu của đoạn kia các kết quả tìm kiếm nằm trong điểm nối của hai đoạn được chia đó. Dung lượng bộ nhớ sử dụng khi thực thi N-Gram cũng là nhược điểm khi tìm kiếm với các chuỗi từ điển dung lượng lớn hơn 20Mb với máy tính cá nhân. Việc chia thành các tệp nhỏ hơn và đánh chỉ số cho các đoạn dữ liệu được chia đã làm tăng vọt theo hàm cơ số mũ với phương pháp này. Thực nghiệm so sánh thuật toán tìm kiếm chuỗi DNA áp dụng N- Gram với phương pháp liên kết nhạy cảm đầy đủ Smith-Waterman và phương pháp tìm kiếm tương tự nhanh BLAST bổ sung cho kết quả nghiên cứu đạt được. Kết quả thực nghiệm tuy chưa đạt được hiệu quả tiết kiệm bộ nhớ hay kết quả tìm kiếm mong đợi cao nhất của thuật toán tìm kiếm chuỗi tương tự nhanh do một số hạn chế về môi trường thực nghiệm, nhưng đã bước đầu khẳng định được sự tối ưu của thuật toán tìm kiếm tương tự nhanh mà tiêu biểu là N-Gram cho tìm kiếm chuỗi gen. Những kết quả thực nghiệm này sẽ là tiền đề để người viết tiếp tục những nghiên cứu và cải tiến cho việc tìm kiếm chuỗi gen trong tương lai. 23 TÀI LIỆU THAM KHẢO [1] Matt Atherton. Human intelligence genes identified in DNA bringing us one step close to cognitive engineering, Internationnal Business Times, 2015. [2] Jes Battis. Blood Relation, 2005. [3] Loretta E. Lynch. Using DNA to solve crimes, 2014. [4] David Michael Buss & David P. Schmitt. Evolutionary Psychology and Feminism. Springer Science + Business Media, LLC 2011. [5] SR Eddy. Profile hidden Markov models. Bioinformatics, 1998. [6] Temple F. Smith and Michael S.Waterman. Identification of common molecular subsequences, 1981. [7] S.F Altschul, T. L. Madden, A. A. Schaffer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman. Gapped blast and psi-blast: a new generation of protein database search programs. Nucleic Acids Res, 25:3389–3402, 1997. [8] Ben Langmead. Aligning short sequencing reads with Bowtie. Curr Protoc Bioinformatics. 2010. [9] Eric Rivals, Leena Salmela, Petteri Kiiskinen, Petri Kalsi, and Jorma. Fast Localisation of Multiple Reads in Genomes, 2015. [10] Daniel Jurafsky and James H.Martin. Speech and Language Processing: An Introduce to Natural Language processing, Computational linguistics and Speech recognition, 2000. [11] Peter F. Brown, Peter V. deSouza, Robert L. Mercer, Vincent J. Della Pietra, Jenifer C. Lai. Class-Based n-gram Models of Natural Language, IBM T. J. Watson Research Center. 24 [12] Songfang Huang, Steve Renals. Power Law Discouting for N-gram Language Models. The Centre for Speech Technology Research, University of Edinburgh, United Kingdom [13] Ben Langmead, Cole Trapnell, Mihai Pop and Steven L Salzberg. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology, 2009. [14] Burrows M, Wheeler DJ. Digital Equipment Corporation. Technical Report 124, 1994. [15] https://sourceforge.net/projects/bowtie-bio [16] P.Ferragina, G.Manzini. Opportunistic data structures with applications. Foundations of Computer Science, 2000. [17] Tao Tao. Single Letter Codes for Nucleotides. National Center for Biotechnology Information, 2011. [18] W.Pearson. Searching protein sequence libraries: comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms. Genomics, 1991.