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

Phương pháp Bowtie (do Langmead và cộng sự đề xuất năm 2010) là phương pháp nhanh và tiết kiệm bộ nhớ. Mô hình của phương pháp là mô hình sử dụng một tập đầu vào với số lượng lớn các liên kết từ gen mẫu (tách mẫu thành các đoạn ngắn- mục đích để đọc thông tin, đưa ra các chỉ số tạo bảng đánh giá. Sau đó, từ bảng đánh giá, mô hình sẽ đánh thứ tự các chuỗi con được tách. Cuối cùng, so sánh chuỗi được tách đó với các đoạn gen mẫu theo các chỉ số đã đưa ra từ ban đầu. Vd: gen người. Các thành phần chương trình chứa các công cụ đánh giá chỉ số cho các thành phần bộ gen tham khảo, sau đó đọc các trình tự ngắncủa bộ gen mẫu theo các chỉ số đã được đưa ra. Đây là bước đầu tiên trong nhiều nhiều bước ở quy trình so sánh gen theo phương pháp này. Phương pháp có thêm chức năng phát hiện biến thể gen. Mỗi lần đọc chuỗi DNA, đầu vào có thể gồm nhiều giá trị chỉ số, các giá trị này đã được đánh giá bởi tiến trình trước đó. Trình tự các chuỗi con sẽ được đánh thứ tự. Các giá trị thứ tự này được tham chiếu đến chuỗi gốc. 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. 27 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). 28 Một đoạn mã nguồn của thuật toán. [8] sub quote_params { my %params_2_quote = ('--rg' => 1, '--rg-id' => 1, '-S' => 1, '-U' => 1, '-1' => 1, '-2' => 1 ); my $param_list = shift; my $quoting = 0; for (my $i=0; $i<scalar(@{$param_list}); $i++){ if($quoting){ $quoting = 0; $param_list->[$i] = "\"".$param_list->[$i]."\""; next; } $quoting = 1 if(exists($params_2_quote{$param_list->[$i]})); } } Ví dụ Gen GRCh37 hay được lấy mẫu để đưa ra tham chiếu các trình tự. Để đạt được hiệu quả về tốc độ và bộ nhớ, Bowtie sắp xếp các quá trình đọc dữ liệu tham chiếu đến trình tự của mẫu gen tham khảo. Chỉ số Bowtie là một sàng lọc của các chỉ số FM (Ferragina & Manzini 2000) [9], trong đó sử dụng các “Burrows- Wheeler Transform” (Burrows & Wheeler 1994) [8] để đạt được hiệu quả cả về tốc độ và không gian lưu trữ. Để đòi hỏi điều này, người dùng đã phải xây dựng hoặc có được một chỉ số thích hợp trước khi quá trình đọc liên kết đến các mẫu. Khi một chỉ số được xây dựng, nó có thể được truy vấn nhiều lần. Chỉ số cho bộ gen tham 29 chiếu thường được sử dụng có thể tải về từ trang web Bowtie tại bio.sf.net. Chương trình sử dụng các giao thức: + Giao thức cơ bản sẽ sắp xếp một bộ các lần “đọc” cho một gen mẫu. + Giao thức đánh chỉ số (Indexing Protocol – Alternate Protocol 1) sẽ xây dựng chỉ số cho gen mẫu. + Giao thức “The Consensus and SNP Calling” nhận các giá trị từ đầu ra của công cụ SAM tools (Li et al. 2009) sẽ đánh giá chuỗi có tương đồng hay không. + Các giao thức tùy chọn dòng lệnh (Alternate Protocol 3) thể hiện một loạt các tùy chọn liên kết thường được sử dụng. + Các giao thức hỗ trợ (Support) hướng dẫn cách lưu trữ và cài đặt phần mềm Bowtie. + Giao thức hỗ trợ 1 (Support Protocol 1) hướng dẫn cách “build” phần mềm Bowtie từ mã nguồn. + Giao thức hỗ trợ 2 (Support Protocol 2) hướng dẫn cách tạo chỉ số “pre-build” từ website bowtie (giao thức hỗ trợ 3). Mỗi giao thức này có thể chạy trên các môi trường khác nhau: Unix (môi trường Unix), Linux, Mac OS X và Windows. Chương trình Bowtie viết dưới dạng mã nguồn mở và có thể được sử dụng miễn phí. Có thể download tại địa chỉ: license-1.0.php Hình 1.5. Hình ảnh một phiên chương trình Bowtie 30 Các dòng cuối mô tả: + Số chuỗi được xử lý. + Thông tin chạy chương trình, đầu ra chuẩn sẽ thể hiện tính hợp lệ. + Thông báo về phương pháp thực hiện - phương pháp Bowtie. + Có thể có thêm thông tin về chuỗi tìm kiếm Hình 1.6. Ví dụ quá trình chạy phương pháp Bowtie với đầu ra định dạng SAM. 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. Ư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. 31 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 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/RNA. 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. Tuy nhiên, thời gian thực hiện ở mức độ trung bình). Phương pháp điển hình của thuật giải này là Mpscan. Phương pháp này do các nhà khoa học (Eric Rivals, Leena Salmela, Petteri Kiiskinen, Petri Kalsi, and Jorma Tarhio) từ đại học LIRMM, CNRS and Université de Montpellier 2, Montpelier, Pháp đăng lần đầu vào năm 2009. 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. [9] Thuật toán: Bước 1: Lọc các mẫu. Đầu vào gồm n mẫu. Mỗi mẫu có độ dài l. Bước này, chương trình sẽ tìm kiếm các đoạn giống nhau trong các mẫu đầu vào có độ dài q=5. Chương trình giả mã cho quá trình lọc mpscan [9] 1: i ← l − q + 1 2: while i ≤ n − q +1 do 3: j = 1; last ← l − q + 1 4: E = B[si] {si is the ith q-mer of the scanned sequence} 5: while true do 6: if first bit in E is one then 32 7: {the scanned window is a prefix of the pattern} 8: if j = l − q + 1 then 9: verify an occurrence; break 10: end if 11: last ← l − q + 1 − j 12: end if 13: if E = 0 then 14: break {the scanned window is not a factor of the pattern} 15: end if 16: E ← (E _ 1) & B[si−j ] {si−j is the (i−j) the q-mer of the scanned sequence} 17: j ← j + 1 18: end while 19: i ← i + last 20: end while Bước 2: Tối ưu độ phức tạp của thuật toán. Định lý 1. Thời gian trung bình của độ phức tạp thuật toán mpscan để tìm kiếm r mẫu có chiều dài l trong văn bản có độ dài n trong bảng gồm c ký tự là: O(n logc(rl)/l) nếu q = Θ(logc(rl)). Ví dụ: Cho 3 tập mẫu chiều dài l = 8: {P1, P2, P3} = {accttggc, gtcttggc, accttcca}. Tìm các mẫu tương tự trong 3 chuỗi đầu vào có độ dài q = 5. {P1, P2, P3} = {accttggc, gtcttggc, accttcca} (a) 33 (a): Tập 3 mẫu thử. (b): Đánh dấu sự trùng khớp các mẫu tại các vị trí. (c): Đưa ra kết quả giữa các đoạn tương đồng. Ƣu điểm: 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/RNA. 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. Chương này, người viết đã trình bày về một số phương pháp phổ biến tìm kiếm chuỗi DNA, các thuật toán điển hình của từng phương pháp. Trong các phương pháp đã trình bày, phương pháp tìm kiếm tương tự nhanh thường được sử dụng nhất vì có thời gian tìm kiếm nhanh nhất. Ngày nay, nhờ các cải tiến về kỹ thuật tìm kiếm, thuật toán tương tự nhanh đã được cải thiện đáng kể về thời gian tìm kiếm, độ chính xác, cũng như độ dài chuỗi tìm kiếm đầu vào. Có thể tìm kiếm đồng thời khoảng 1000 mẫu (MegaBLAST) cùng lúc [5]. Phương pháp sử dụng mô hình Markov ẩn và phương pháp Smith & Waterman tuy có độ chính xác cao hơn thuật toán BLAST nhưng phải tính toán nhiều. Các tính toán sau phải dựa vào 34 kết quả của quá trình tính toán trước, các hàm tính toán tương đối phức tạp nên chi phí thời gian đưa ra kết quả lớn. Độ phức tạp của hai thuật toán này cỡ hàm mũ. Phương pháp Bowtie là phương pháp mới hơn so với các phương pháp sử dụng mô hình Markov ẩn và phương pháp Smith & Waterman. Áp dụng nhiều thuật toán cải tiến mới nên phương pháp này nhanh và tiết kiệm bộ nhớ. Mô hình của phương pháp là mô hình sử dụng một tập đầu vào với số lượng lớn các liên kết từ gen mẫu, đọc thông tin từ gen mẫu, đưa ra các chỉ số tạo bảng đánh giá. Sau đó, từ bảng đánh giá, mô hình sẽ đánh thứ tự các chuỗi con được tách. Cuối cùng, so sánh chuỗi được tách đó với các đoạn gen mẫu theo các chỉ số đã đưa ra từ ban đầu. Thuật toán này có ưu điểm đưa ra kết quả nhanh. Có thể tìm kiếm nhiều mẫu đồng thời. 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 là phương pháp áp dụng quá trình đánh dấu tập mẫu để đối sánh với chuỗi đầu vào. Phương pháp này đạt hiệu quả chính xác cao cho việc giải trình tự DNA/RNA, thực hiện xử lý nhiều mẫu. Phương pháp 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/RNA. 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. Tuy nhiên, thời gian thực hiện ở mức độ trung bình. 35 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. Từ năm 2005, trong Sinh học đã áp dụng sự đổi mới về giải trình tự thông lượng cao HTS (High-throughput Sequencing) (công nghệ mới thường được gọi là thế hệ giải trình tự kế tiếp – Next Generation Sequencing). Do sự phát triển của giải trình tự đồng thời các phân tử lớn trên một cùng một máy nên kết quả giải trình tự mỗi lần chạy đã tăng vượt bậc so với kỹ thuật Sanger truyền thống, và dự kiến sẽ tiếp tục tăng. Do những lợi ích và hiệu quả mà thuật toán N-Gram trong việc tìm kiếm mang lại mà ở chương này, người viết sẽ trình 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 mô hình N-gram, sử dụng mã nguồn mở được phát hành miễn phí cho cộng đồng sử dụng và mở rộng. Hiệu quả thực hiện đạt được cao hơn các phương pháp tìm kiếm chuỗi khác. Thêm vào đó, người viết sẽ trình bày các đặc trưng của phương pháp tương tự nhanh mà thuật toán đã kết thừa. Đồng thời, trình bày những đặc trưng mà thuật toán áp dụng N- Gram đã cải tiến và mang lại hiệu quả thực sự về tốc độ tìm kiếm cũng như bộ nhớ sử dụng khi thực hiện. Thuật toán được đánh giá trên tập dữ liệu từ 3 loài: 120 gen người và 58 gen E.Coli. 2.1. Mô hình N-Gram 2.1.1. Một số khái niệm  Ngữ liệu: 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 ngữ liệu. 36 - Với n = 1, unigram, và tính trên kí tự, ta có thông tin về tần suất xuất hiện nhiều nhất của các chữ cái. Điều này được ứng dụng để làm keyboard : các phím hay xuất hiện nhất sẽ ở những vị trí dễ sử dụng nhất. - Với n = 2, ta có khái niệm bigram.Ví dụ với các chữ cái tiếng Anh “th”, “he”, “in”, “an”, “er” là các cặp ký tự hay xuất hiện nhất. Ngoài ra, ta có thể biết thêm rằng sau ký tự “q” thì phần lớn đều là ký tự “u”. - Với n = 3, ta có trigram.Nhưng vì n càng lớn thì số trường hợp càng lớn nên thường người ta chỉ sử dụng với n = 1,2 hoặc đôi lúc là 3.Ví dụ với các ký tự tiếng Việt, tiếng Việt sử dụng 29 ký tự, vậy với n = 1 thì số trường hợp là 29, n = 2 thì số trường hợp là 292 = 841 trường hợp, n = 3 có 23489 trường hợp. Bigram được sử dụng nhiều trong việc phân tích hình thái (từ, cụm từ, từ loại) cho các ngôn ngữ khó phân tích như tiếng Việt, tiếng Nhật, tiếng Trung,..Dựa vào tần suất xuất hiện cạnh nhau của các từ người ta sẽ tính cách chia 1 câu thành các từ sao cho tổng bigram là cao nhất có thể.Với thuật giải phân tích hình thái dựa vào trọng số nhỏ nhất, người ta sử dụng n = 1 để xác định tần suất xuất hiện của các từ và tính trọng số. Để đảm bảo tính thống kê chính xác đòi hỏi các “ngữ liệu” (corpus) phải lớn và có tính đại diện cao. 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) [10] 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 nếu biết rằng sự kiện A đã xảy ra, thì: 37 P(w 1w 2w m) = P(w 1) * P(w 2|w 1) * P(w 3|w 1w 2) ** P(w m|w 1w 2w m-1) [10] Theo công thức này, mô hình ngôn ngữ cần phải có một lượng bộ nhớ vô cùng lớn để có thể lưu hết xác suất của tất cả các chuỗi độ dài nhỏ hơn m. Điều này là không thể khi m là độ dài của các văn bản ngôn ngữ tự nhiên (m có thể tiến tới vô cùng). Để có thể tính được xác suất của văn bản với lượng bộ nhớ chấp nhận được, ta sử dụng xấp xỉ Markov bậc n: P(w m|w 1,w 2,, w m-1) = P(w m|w m-n,w n-m+1, ,w m-1) [10] Nếu áp dụng xấp xỉ Markov, xác suất xuất hiện của một từ (w m) được coi như chỉ phụ thuộc vào n từ đứng liền trước nó (w m-nw m-n+1w m-1) chứ không phải phụ thuộc vào toàn bộ dãy từ đứng trước (w 1w 2w m-1). Như vậy, công thức tính xác suất văn bản được tính lại theo công thức: P(w 1w 2w m) = P(w 1) * P(w 2|w 1) * P(w 3|w 1w 2) ** P(w m-1|w m-n-1w m-n w m-2)* P(w m|w m-nw m-n+1 w m-1) [10] Với công thức này, ta có thể xây dựng mô hình ngôn ngữ dựa trên việc thống kê các cụm có ít hơn n+1 từ. Mô hình ngôn ngữ này gọi là mô hình ngôn ngữ N-gram. 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. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : Phân bố không đều Vơí mô hình N-gram, sự phân bố không đều trong tập văn bản huấn luyện có thể dẫn đến các ước lượng không chính xác. Khi các cụm 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. Tuy nhiên, thực tế thì số cụm N-gram có nghĩa và thường gặp chỉ chiếm rất ít. 38 Ví dụ: tiếng Việt có khoảng hơn 5000 âm tiết khác nhau, ta có tổng số cụm 3- gram có thể có là: 5.0003 = 125.000.000.000 Tuy nhiên, số cụm 3-gram thống kê được chỉ xấp xỉ 1.500.000. Như vậy sẽ có rất nhiều cụm 3-gram không xuất hiện hoặc chỉ xuất hiện rất ít. Khi tính toán xác suất của một câu, có rất nhiều trường hợp sẽ gặp cụm N-gram chưa xuất hiện trong dữ liệu huấn luyện bao giờ. Điều này làm xác suất của cả câu bằng 0, trong khi câu đó có thể là một câu hoàn toàn đúng về mặt ngữ pháp và ngữ nghĩa. Đề khắc phục tình trạng này, người ta phải sử dụng một số phương pháp “làm mịn”. 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ũ). Nó không những gây khó khăn trong việc lưu trữ mà còn làm tốc độ xử lý của mô hình ngôn ngữ giảm xuống do bộ nhớ của máy tính là hạn chế. Để xây dựng mô hình ngôn ngữ hiệu quả, chúng ta phải giảm kích thước của mô hình ngôn ngữ mà vẫn đảm bảo độ chính xác. 2.1.4. Các phƣơng pháp khắc phục cụm N-Gram phân bố không đều Để khắc phục tình trạng các cụm N-gram phân bố không đều như đã đề cập, người ta đã đưa ra các phương pháp đánh giá chính xác hơn xác suất của các cụm N-gram (làm mịn). Các phương pháp “làm mịn” đánh giá lại xác suất của các cụm N-gram bằng cách: Gán cho các cụm N-gram có xác suất 0 (không xuất hiện) một giá trị khác 0. Thay đổi lại giá trị xác suất của các cụm N-gram có xác suất khác 0 (có xuất hiện khi thống kê) thành một giá trị phù hợp (tổng xác suất không đổi). Các phương pháp làm mịn có thể được chia ra thành loại như sau: Chiết khấu: giảm xác suất của các cụm N-gram có xác suất lớn hơn 0 để bù cho các cụm Ngram không xuất hiện trong tập huấn luyện. 39 Truy hồi : tính toán xác suất các cụm N-gram không xuất hiện trong tập huấn luyện dựa vào các cụm Ngram ngắn hơn có xác suất lớn hơn 0 Nội suy: tính toán xác suất của tất cả các cụm N-gram dựa vào xác suất của các cụm N-gram ngắn. 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ê. Dữ liệu DNA là rất lớn nên việc tạo bảng chỉ số tuần tự có lợi cho việc truy xuất dữ liệu. Giúp việc truy xuất kết quả tìm kiếm nhanh hơn do được giảm tải dữ liệu tìm kiếm. Tuy vậy trong nghiên cứu chuỗi DNA, chúng ta có hai vấn đề cần thảo luận. Thứ nhất: Dữ liệu DNA trong các định dạng dữ liệu là các đoạn dài liên tục, không phân cách, vậy làm thế nào để chia chúng thành các “từ DNA”. Thứ hai: Chúng ta phải bảo đảm các “từ DNA” không được quá dài. Vì nếu dài việc tìm kiếm sẽ tăng theo cơ số mũ. Khó khăn cho việc đưa ra kết quả. Do đó, trong tài liệu này, người viết sử dụng n=12 là vừa phải, có thể thực hiện được trên máy tính cá nhân để tìm kiếm. Việc lưu trữ chuỗi DNA phải dùng dung lượng khá lớn. Trong tài liệu này, người viết chia dữ liệu gốc thành các đoạn ngắn hơn để thuận tiện cho việc truy xuất, tìm kiếm dữ liệu và đưa ra kết quả. 2.2.1. Phân đoạn DNA Chuỗi DNA là chuỗi gồm nhiều ký tự A, T, G, C nằm liền kề, liên tiếp với nhau. Giữa các ký tự không có khoảng trống. Để thuận tiện cho việc tìm kiếm. Ta chia chuỗi DNA thành các đoạn 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 40 bao nhiêu thì hợp lý, Có thể chia chuỗi DNA thành các đoạn có độ dài 100, 500, 1000, 10000 ký tự... Trong tài liệu này tác giả chia một chuỗi DNA dài thành các đoạn có độ dài 500 ký tự - phân đoạn DNA. Sau đó, đánh ID cho từng đoạn để thuận tiện cho quá trình truy xuất. 2.2.2. Các “từ DNA” 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. Ví dụ 41 Cho bảng inverted Word Document ID W1 D1 W2 D0, D2, D3 W3 D0, D2, D4 W4 D0, D2 Chuỗi đầu vào cần search là {W1, W3, W4}. Tìm trong bảng trên R(“W1”) = {D1} R(“W3”) = {D2, D0, D4} R(“W4”) = {D0, D2} Tính giao của các tập R1 = R(“W1”) ̯ ∩ R(“W3”) ={D1}∩{D2, D0, D4}={} R2= R(“W3”) ̯ ∩ R(“W4”) ={D2,D0,D4}∩{D0, D2 }={D0,D2} Tập R2 được đánh giá tốt hơn tập R1 vì nó chứa cả 2 tập từ của giá trị đầu vào, tốt hơn chỉ một tập từ so với tập R1 Hình 2.1. Định dạng FASTA gen Caenorhabdit elegans I 42 Chương trình được thực hiện có đầu vào gồm các gen mẫu có định dạng theo chuẩn FASTA. Bài toán: Cho một chuỗi gen (có sẵn trong CSDL) và một chuỗi khác(được nhập từ bàn phím (trong tài liệu này người viết sử dụng chuỗi có độ dài là 12 - với độ dài này, máy tính cá nhân thông thường có thể xử lý được. VD: Với DNA có 4 ký tự A,T, G, C, khi n=12 tổng số chuỗi có thể có là 412 chuỗi. Với n càng lớn, việc thống kê kết quả tăng theo cơ số mũ). Đưa ra các đoạn giống nhau của hai chuỗi gen đã cho. Giải quyết bài toán: - Tạo tệp n-gram thống kê tất cả các trường hơp̣ có thể taọ nên từ 4 ký tự (A, T, G,C). - Tách chuỗi gen CSDL thành các phân đoạn có độ dài 500 ký tự, thống kê, lưu thành file, đánh chỉ số cho các đoạn được tách. lưu lại vị trí các đoạn đó trong chuỗi gen CSDL gốc. - Từ các phân đoaṇ có đô ̣dài 500 ký tự, chia tiếp thành các đoaṇ nhỏ hơn có đô ̣dài 12 ký tự. Lưu laị điạ chỉ các đoạn trong chuỗi CSDL vào têp̣ để tiêṇ truy xuất. - Quá trình tìm kiếm chuỗi là việc so sánh chuỗi nhập từ bàn phím với chuỗi đa ̃đươc̣ đánh chỉ muc̣ trước đó. Với chuỗi đươc̣ tìm thấy, quá trình hiển thị kết quả là quá trình truy xuất ngược lại để tìm địa chỉ chuỗi trong chuỗi gen CSDL. - Hiển thị kết quả lên màn hình. 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: 43 *.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. Hình 2.2. Nội dung file *.n-gram. *.div: file chia nhỏ nội dung file FASTA thành nhiều doc. Mỗi doc gồm 2 dòng: + Dòng 1: FIELD_TI (field title): Bao gồm tiêu đề chuỗi DNA, vị trí bắt đầu, vị trí kết thúc chuỗi trong file gốc. + Dòng 2: FIELD_CO (field content): Nội dung chuỗi DNA được tách. Trong bài viết này, người viết chọn chiều dài “field content” là 500 ký tự. (Nếu file 44 FASTA gồm nhiều chuỗi DNA thì length của doc có thể sẽ nhỏ hơn 500 nếu chuỗi DNA không chia hết cho 500). Đánh thứ tự docId cho chuỗi được tách. Hình 2.3. Nội dung file *.div *.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. Hình 2.4. Nội dung file *.idx 45 *.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. Hình 2.5. Nội dung file *.seg *.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. 46 Hình 2.6. Nội dung file *.frd *.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. Hình 2.7. Nội dung file *.inv.idx 47 Hình 2.8. Nội dung file *.inv  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ả: + Nếu có nhiều file FASTA thì sắp xếp theo file nào có nhiều kết quả nhất. + 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. 48 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 này ban đầu được sử dụng làm đầu vào cho chương trình phần mềm FASTA của NCBI (Trung tâm quốc gia công nghệ tin sinh - Mỹ). Do cấu trúc định dạng tệp đơn giản và tiện dụng nên hiện nay FASTA đã trở thành một chuẩn trong lĩnh vực tin - sinh học. Đị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 lớn hơn) hoặc ";" (dấu chấm phẩy - ít gặp). Ký tự này nhằm giúp chương trình 49 biết được đây là ký tự đầu tiên bắt đầu của tệp. Các thông tin tiếp theo của dòng đầu tiên cho biết các nội dung lần lượt như sau: tên chuỗi, chú thích, ký hiệu chuỗi trong ngân hàng CSDL (với mỗi trung tâm dữ liệu khác nhau, mã chuỗi là khác nhau), vị trí bắt đầu, vị trí kết thúc trong chuỗi DNA gốc, tên loài (trong định dạng FASTA, chỉ dòng đầu tiên được sử dụng để mô tả chuỗi). Bất cứ ký tự nào không thuộc mã hợp lệ (vd: khoảng trống, dấu hoa thị, v.v ...), khi chương trình đọc dòng đầu tiên này sẽ được bỏ qua. Ngoại trừ dòng đầu tiên, tất cả các dòng tiếp theo là các dòng mô tả trình tự chuỗi nucleotide hoặc amino axiet dưới dạng số hóa: mỗi dòng thường có ít hơn 80 ký tự. Chuỗi Nucleotide gồm một loạt các ký tự A, T, G, C nằm liên tiếp, xem kẽ với nhau, cũng có thể nhiều ký tự giống nhau nằm gần nhau. Chuỗi Amino axit gồm nhiều ký tự hơn: A, B, C, D (có thể bao gồm cả dấu gạch ngang “-“, dấu “*”). Do sự đơn giản của FASTA nên nhiều công cụ như Python, Ruby, PERL, C++ có thể dễ dàng truy xuất và thao tác trên định dạng này. [17] >MCHU - Calmodulin - Human, rabbit, bovine, rat, and chicken ADQLTEEQIAEFKEAFSLFDKDGDGTITTKELGTVMRSLGQNPTEAELQDMINEVDADGNGTID FPEFLTMMARKMKDTDSEEEIREAFRVFDKDGNGYISAAELRHVMTNLGEKLTDEEVDEMIREA DIDGDGQVNYEEFVQMMTAK* >gi|5524211|gb|AAD44166.1| cytochrome b [Elephas maximus maximus] LCLYTHIGRNIYYGSYLYSETWNTGIMLLLITMATAFMGYVLPWGQMSFWGATVITNLFSAIPYIGTNLV EWIWGGFSVDKATLNRFFAFHFILPFTMVALAGVHLTFLHETGSNNPLGLTSDSDKIPFHPYYTIKDFLG LLILILLLLLLALLSPDMLGDPDNHMPADPLNTPLHIKPEWYFLFAYAILRSVPNKLGGVLALFLSIVIL GLMPFLHTSKHRSMMLRPLSQALFWTLTMDLLTLTWIGSQPVEYPYTIIGQMASILYFSIILAFLPIAGX IENY Hình 2.10. Ví dụ định dạng tệp FASTA 50 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, gen được tải về miễn phí phục vụ cho mục đích nghiên cứu. Chuỗi cần tìm kiếm được nhập từ bàn phím. Chuỗi cần tìm kiếm sẽ được so sánh với dữ liệu từ điển trong tệp FASTA để biết được chuỗi nhập từ bàn phím cần tìm kiếm có trong dữ liệu từ điển đó không, có bao nhiêu chuỗi có mặt trong dữ liệu từ điển đó. Kết quả quá trình tìm kiếm sẽ được hiển thị lên màn hình. Chương trình được thực hiện qua hai bước. Bước một: tiền xử lý và bước hai: tìm kiếm và hiển thị kết quả. Chi tiết các bước đã được người viết đề cập ở mục 2.2. 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 2.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. 51 2.4. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram Ở phần đánh giá này, người viết trình bày kết quả tìm kiếm chuỗi trong một đoạn gen được lấy từ cơ sở dữ liệu gen của NCBI. Quá trình tìm kiếm thu được kết quả về bộ nhớ được sử dụng khi tìm kiếm, thời gian tìm kiếm và hiển thị kết quả ra màn hình để so sánh hiệu quả của phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram với phương pháp cùng loại là BLAST. Đồng thời so sánh hiệu quả của phương pháp này với phương pháp tìm kiếm nhạy cảm đầy đủ Smith&Waterman để thấy được những cải tiến của phương pháp đề xuất đã thực sự mang lại hiệu quả về thời gian tìm kiếm và tiết kiệm dung lượng bộ nhớ trong quá trình tìm kiếm. Do luận văn tập trung nghiên cứu chính là cải thiện thời gian tìm kiếm nên sau đây người viết sẽ tập trung mô tả cách thức và những cải thiện đạt được về việc cải thiện thời gian đưa ra kết quả của các thuật toán. Hiệu quả về thời gian và dung lượng bộ nhớ trong quá trình tìm kiếm cũng được đưa ra như một kết quả của việc nghiên cứu. Mỗi kiểm tra được thực hiện 10 lần và kết quả thể hiện giá trị trung bình. 2.4.1. Cải thiện thời gian tìm kiếm 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 52 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. 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 3 giây. Trong khi đó, với phương pháp khác là Smith&Water Man quá trình tìm kiếm đến hiển thị kết quả là 4 giây. 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. 53 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 Ở chương này, người viết trình bày thực nghiệm bổ sung để minh họa thêm về tính hiệu quả của phương pháp tìm kiếm chuỗi DNA tương tự nhanh áp dụng N- gram so với hai thuật toán là BLAST-phương pháp tìm kiếm chuỗi tương tự nhanh và Smith&Waterman – phương pháp tìm kiếm chuỗi liên kết nhạy cảm đầy đủ. Như đã trình bày ở chương 1, có năm loại thuật toán được sử dụng cho tìm kiếm chuỗi gen. 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ể. Phương pháp thứ hai là phương pháp tìm kiếm chuỗi liên kết nhạy cảm đầy đủ là 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. 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]. Thuật toán tìm kiếm chuỗi hiệu quả thứ ba là phương pháp tìm kiếm chuỗi tương tự nhanh. Phương pháp này là 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. Dựa vào bảng kết quả đánh giá, sẽ đưa ra kết quả về mức độ tương đồng của hai chuỗi. Mặc dù có thời gian xử lý nhanh nhưng phương pháp này có độ chính xác không bằng phương pháp liên kết nhạy cảm đầy đủ. Thuật toán điển hình của phương pháp này hiện nay được dùng rất 54 phổ biến và có nhiều biến thể để so sánh với từng trường hợp cụ thể. Phương pháp tìm kiếm chuỗi thứ tư là phương pháp tìm kiếm chuỗi phù hợp gần đúng (chứ không phải là chính xác). Phương pháp này sử dụng cách tiếp cận vét cạn (brute- force) để tính “độ chỉnh sửa” chuỗi từ điển 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 lớn( cỡ hàm mũ). Phương pháp tìm kiếm chuỗi thứ năm là 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]. Phương pháp sử dụng mô hình đá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 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, có thể thực hiện xử lý đồng thời 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/RNA. Phương pháp điển hình của dạng này là Mpscan. Chương trình của Mpscancó 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. Tuy nhiên, thời gian thực hiện ở mức độ trung bình). Là công cụ đánh dấu tập mẫu đạt hiệu quả chính xác cao cho việc giải trình tự DNA/RNA. Phương pháp tìm kiếm chuỗi tương tự nhanh áp dụng N-Gram đã được người viết trình bày ở chương 2 là phương pháp tìm kiếm chuỗi với những cải tiến về tốc độ tìm kiếm và tiết kiệm bộ nhớ hơn một số phương pháp khác. Sau đây, người viết trình bày về thực nghiệm mà người viết đã thực hiện để làm rõ hơn nhận định về tính hiệu quả mà phương pháp tìm kiếm chuỗi DNA áp dụng N-Gram mang lại cho việc tìm kiếm chuỗi gen. 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++. 55 Các kích thước đo bằng byte, ví dụ 1MB có nghĩa là 1024 byte. Các tập dữ liệu thực nghiệm: Người viết thực hiện so sánh ba thuật toán tìm kiếm trên hai tập dữ liệu sinh học: (1) tập hợp gen người, (2) tập hợp gen từ khuẩn Escherichia coli. (1) Tập dữ liệu đầu tiên là 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. Sử dụng Chr-# để biểu diễn tập tất cả chuỗi cho nhiễm sắc thể người #, ví dụ Chr-1 biểu diễn nhiễm sắc thể người 1. Các chuỗi lấy từ cùng nhiễm sắc thể sẽ có độ tương đồng cao hơn các chuỗi lấy từ các nhiễm sắc thể khác nhau. Tập tất cả 23 tập dữ liệu gen người (Chr-1 tới Chr-22, Chr-X) được kí hiệu là H-*. Tập dữ liệu gen người lớn nhất là Chr-1 với 65631142 byte (62,6MB), tập dữ liệu nhỏ nhất là Chr- 22 với 9953567 byte (10MB) và kích thước H-* khoảng 50000000 byte (5Gb). (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-*. Tập dữ liệu Escherichia coli nhỏ nhất là Ec_K-12 substr. W3110 với 4646332 byte (4,6Mb). Tập lớn nhất là Ec_CI5 với 8,092,977 byte (8,1Mb) và kích thước Ec-* vào khoảng 207008000 byte (207Mb). Dữ liệu trong tệp gen có dạng chuỗi. Các hình 3.1, 3.2 và 3.3 dưới đây thể hiện định dạng chuỗi gen trong các tập dữ liệu thực nghiệm. Hình 3.1. Định dạng Fasta chuỗi gen khuẩn E. Coli K12 – DH10B 56 Hình 3.2. Định dạng FASTA chuỗi gen Hs7_807 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 Thực nghiệm so sánh được tiến hành với ba phương pháp tìm kiếm: Phương pháp tìm kiếm tương tự nhanh BLAST, phương pháp N-Gram, phương pháp liên kết nhạy cảm đầy đủ Smith-Waterman. Cách làm như sau: với mỗi loài và mỗi nhiễm sắc thể, lựa chọn ngẫu nhiên một số chuỗi và áp dụng mỗi thuật toán lựa chọn cho các chuỗi ngẫu nhiên đó. Kết quả được thống kê và so sánh về kích thước gen sau khi tìm kiếm, thời gian tìm kiếm ở tất cả các bước của từng thuật toán cho một hoặc nhiều chuỗi gen cụ thể. Kết quả sau khi thực nghiệm các phương pháp tìm kiếm chuỗi cho thấy thời gian đưa ra kết quả của BLAST khá tốt trong khi số lượng chuỗi tìm thấy được ở mức chấp nhận được. 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 57 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 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 58 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 3.3. Phân tích và đánh giá kết quả thực nghiệm Bộ dữ liệu được tải về khá lớn, tổng cộng khoảng gần 100GB nhưng do môi trường thực nghiệm có hạn nên người viết chỉ lựa chọn ra một số chuỗi với dung lượng phù hợp để thực hiện quá trình tìm kiếm và so sánh. Phương pháp tìm kiếm chuỗi Smith-Waterman là mô hình phương pháp tìm kiếm quy hoạch động. Có thể sử dụng kết quả của quá trình tìm kiếm trước đó để sử dụng cho lần tìm kiếm tiếp theo tức là có thể mở rộng phạm vi tìm kiếm từ các chuỗi đã tìm được trước đó. Phương pháp này có ưu điểm là việc hiển thị kết quả rất trực quan. Tuy có thời gian tìm kiếm chậm và cần nhiều bộ nhớ khi tìm kiếm. Nhưng trong ba phương pháp tìm kiếm, đây là phương pháp tìm kiếm có số lượng kết quả đưa ra nhiều nhất khi tìm kiếm trong mọi trường hợp, sô chuỗi được tìm thấy bao giờ cũng nhiều hơn hai phương pháp còn lại. Phương pháp BLAST là phương pháp tìm kiếm chuỗi tuy có thời gian tìm kiếm nhanh hơn Smith-Waterman nhưng khi tìm kiếm với các chuỗi từ điển dung lượng lớn, số lượng kết quả đưa ra của phương pháp này tuy nhiều hơn N-Gram nhưng không bằng phương pháp Smith-Waterman. 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 59 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. Bảng 2 thể hiện bảng thống kê kết quả đạt được khi thực hiện tìm kiếm chuỗi DNA theo phương pháp BLAST, phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram và phương pháp liên kết nhạy cảm đầy đủ Smith&Waterman khi tìm kiếm chuỗi DNA có độ dài 12 nucleotide. Chuỗi tìm kiếm được chọn ngẫu nhiên, các lần tìm kiếm được thử nghiệm với dung lượng chuỗi CSDL khác nhau ở các lần thử. 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. Như đã trình bày ở trên, N-Gram không chỉ là thuật toán hiệu quả về thời gian tìm kiếm mà còn hiệu quả về dung lượng bộ nhớ sử dụng khi thực hiện chương trình. Kết quả thực nghiệm cho thấy với những chuỗi từ điển có dung lượng dưới 2Mb, bộ nhớ cần thiết cho N-Gram chỉ khoảng 6Mb, với BLAST là 10Mb, trong khi với Smith-Waterman là khoảng 14Mb. 60 KẾT LUẬN Những thách thức trong việc khám phá ra cấu trúc, chức năng, tiến hóa và di truyền hệ gen của các loài, những phương pháp sắp xếp và tìm kiếm chuỗi đa lượng cũng đặt ra câu hỏi và tập trung vào việc biểu diễn, lưu trữ, truyền tải, truy vấn và bảo vệ thông tin chuỗi gen. Mặc dù việc lưu trữ và tìm kiếm thông tin chuỗi DNA cho tới nay đã có thể kiểm soát phần nào nhưng việc cải tiến phương pháp tìm kiếm tốt hơn cho chuỗi DNA vẫn là một vấn đề quan trọng đối với nghành tin - sinh học. Đặc biệt là việc tìm ra giải thuật nhanh về tốc độ tìm kiếm, đạt độ chính xác cao đồng thời số lượng kết quả quá trình tìm kiếm triệt để vẫn còn là thách thức lớn. Trong luận văn này, người viết đã trình bày các phương thức và thuật toán tìm kiếm tiêu biểu cho mỗi phương thức tìm kiếm dữ liệu chuỗi DNA. Trong đó, người viết chọn phương thức tìm kiếm chuỗi tương tự nhanh áp dụng N-gram làm mục tiêu nghiên cứu chính vì những hiệu quả mà thuật toán này mang lại cho tìm kiếm chuỗi DNA như thời gian đưa ra kết quả nhanh, tiết kiệm bộ nhớ sử dụng, phương pháp tính toán đơn giản khi tìm kiếm. 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. Ở điều kiện lý tưởng về chọn lựa chuỗi từ điển phù hợp hay chuỗi gen cùng loài có độ tương đồng cao, thời gian tìm kiếm có thể nhanh hơn gấp ba lần so với phương pháp BLAST và Smith- Waterman. 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 61 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. Độ lớn của tệp được chia theo phương pháp này phụ thuộc vào chỉ số N (trong N-Gram). Trong DNA với 4 nucleotide (A, T, G, C) số lượng các đoạn cần tìm kiếm sẽ là 4N vì vậy với N càng lớn, dung lượng tệp truy vấn sẽ lớn lên theo hàm mũ. Tuy gặp một số bất lợi về thời gian tìm kiếm và dung lượng máy ảo do sử dụng ngôn ngữ C++ làm công cụ phát triển nhưng N-Gram đã chứng minh được tính hiệu quả trong việc tìm kiếm chuỗi gen của thuật toán tìm kiếm tương tự nhanh. Trong tương lai N-Gram có thể được tiếp tục cải tiến để đạt được tốc độ tìm kiếm và khả năng tiết kiệm bộ nhớ đáng mong đợi. Cùng với những nghiên cứu và nhận định đã trình bày, người viết cũng đã thực hiện thực nghiệm so sánh thuật toán tìm kiếm chuỗi DNA với thuật toán tìm kiếm thuộc phương thức khác là tìm kiếm chuỗi theo 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. 62 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. [12] Songfang Huang, Steve Renals. Power Law Discouting for N-gram Language Models. The Centre for Speech Technology Research, University of Edinburgh, United Kingdom 63 [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.