ĐẠ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 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN HÀ NỘI – 2016 ĐẠ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 LỜI CAM ĐOAN Tôi xin cam đoan nội dung 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” sản phẩm thực hướng dẫn TS Nguyễn Thị Hậu Trong toàn nội dung luận văn, điều trình bày cá nhân tổng hợp từ nhiều nguồn tài liệu Tất tài liệu tham khảo có xuất xứ rõ ràng trích dẫn hợp pháp Tôi xin hoàn toàn chịu trách nhiệm chịu hình thức kỷ luật theo quy định cho lời cam đoan Hà Nội, ngày 20 tháng năm 2016 TÁC GIẢ Nguyễn Hoàng Anh LỜI CẢM ƠN Trước tiên xin gửi lời cảm ơn chân thành tới tập thể các thầy cô giáo Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội giúp đỡ tận tình chu có môi trường tốt học tập nghiên cứu Đặc biệt, xin bày tỏ lòng biết ơn sâu sắc tới TS Nguyễn Thị Hậu, người trực tiếp hướng dẫn, bảo tận tình suốt trình nghiên cứu hoàn thiện luận văn Một lần xin gửi lời cảm ơn đến tất thầy cô giáo, bạn bè gia đình giúp đỡ thời gian vừa qua Tôi xin kính chúc thầy cô giáo, anh chị bạn mạnh khỏe hạnh phúc Hà Nội, ngày 20 tháng năm 2016 TÁC GIẢ Nguyễn Hoàng Anh MỤC LỤC LỜI CAM ĐOAN .3 LỜI CẢM ƠN DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT .7 GIỚI THIỆU CHƢƠNG TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA 13 1.1 Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn 13 1.2 Phƣơng pháp liên kết nhạy cảm đầy đủ 15 1.3 Phƣơng pháp tìm kiếm tƣơng tự nhanh 21 1.4 Phƣơng pháp sử dụng mô hình phù hợp gần 25 1.5 Phƣơng pháp sử dụng mô hình kết hợp xác gần xác 31 CHƢƠNG N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM 35 2.1 Mô hình N-Gram 35 2.1.1 Một số khái niệm 35 2.1.2 Mô hình ngôn ngữ N-gram 36 2.1.3 Khó khăn xây dựng mô hình ngôn ngữ N-gram : 37 2.1.4 Các phương pháp khắc phục cụm N-Gram phân bố không 38 2.2 Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA 39 2.2.1 Phân đoạn DNA 39 2.2.2 Các “từ DNA” 40 2.2.3 Quá trình tìm kiếm chuỗi hiển thị kết 40 2.3 Bảng kết lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram 48 2.3.1 Định dạng chuỗi sở liệu 48 2.3.2 Bảng kết lần thử phương pháp tìm kiếm chuỗi tương tự nhanh áp dụng NGram 50 2.4 Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram51 2.4.1 Cải thiện thời gian tìm kiếm 51 2.4.2 Tiết kiệm nhớ trình tìm kiếm 52 CHƢƠNG 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 53 3.1 Môi trƣờng thực nghiệm 54 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 phƣơng pháp Smith-Water Man 56 3.3 Phân tích đánh giá kết thực nghiệm 58 KẾT LUẬN .60 TÀI LIỆU THAM KHẢO .62 DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT Kí hiệu DNA Tiếng Anh Deoxy Ribonucleic Acid NST A T G C SNP Chromosome Adenine Thymine Guanine Cytosine Single nucleotide polymorphisms CPU RAM NCBI Cental Processing Unit Random access memory National Center for Biotechnology Information Differential Direct coding HMM BLAST Hidden Markov Modeling Basic Local Alignment Search Tool High – Throughput Sequencing HTS Tiếng Việt Phân tử mang cấu trúc gen di truyền Nhiễm sắc thể Tính đa hình phân tử nucleotit Mỗi SNP biểu diễn biến đổi khối chuỗi DNA Bộ xử lý trung tâm Bộ nhớ truy cập ngẫu nhiên Trung tâm quốc gia thông tin công nghệ sinh Mã hóa trực tiếp phần khác biệt Mô hình Markov ẩn Công cụ tìm kiếm cục theo mẫu có sẵn Trình tự chuỗi đa lượng GIỚI THIỆU Việc phát DNA bước ngoặt lớn khoa học sinh học nói riêng sống người nói chung Hiện nay, nhà khoa học tìm nhiều cấu trúc DNA giải thích nhiều câu hỏi di truyền loài, bệnh, dị tật di truyền, khoa học hình sự,… ngày phát thêm nhiều cấu trúc DNA mới, điều tạo khối lượng khổng lồ liệu chuỗi gen phục vụ cho y sinh học đại Kích thước liệu ngày tăng đặt vấn đề chi phí cho không gian lưu trữ tốc độ truy cập, truyền tải DNA (DeoxyriboNucleic Acid) tên hóa học phân tử mang cấu trúc gen tất thực thể sống DNA gồm chuỗi tạo nên từ loại đơn vị nucleotide, loại gồm: đơn vị đường carbon (2’-deoxyribose), nhóm phốt phát (phosphate) thành phần Adenine, Cystosine, Guanine Thymine gọi bazơ Mỗi phân tử đường gắn với ¼ thành phần Mỗi thành phần base Số lượng base người khoảng tỷ, số vô lớn Dạng đơn giản DNA tế bào cấu trúc dây xoắn đôi, sợi DNA đơn xoắn quanh theo hình xoắn ốc thuận tay phải Bộ gen người gồm khoảng tỉ đặc trưng 23 cặp nhiễm sắc thể (NST) Do đó, sở liệu hệ gen vô lớn phức tạp Để lưu trữ, truy cập xử lý liệu cách hiệu nhiệm vụ khó khăn DNA có chức lưu trữ, bảo quản truyền đạt thông tin di truyền cấu trúc toàn loại protein thể sinh vật, quy định tính trạng thể sinh vật DNA có chức lưu giữ truyền đạt bảo quản thông tin di truyền hệ Có nhiều ứng dụng từ việc tìm kiếm chuỗi DNA khoa học đời sống người, chẳng hạn như:  Sự di truyền trí thông minh: Các nhà khoa học tiến hành lấy mẫu (có thể lấy tế bào máu, niêm mạc miệng, tế bào má, tóc có chân, móng tay, móng chân, cuống rốn sau rụng ) nghiên cứu chuỗi gen người có số thông minh cao, sau tìm đặc điểm chung Tiến hành nghiên cứu tập lớn mẫu để xác định chuỗi gen định trí thông minh Từ ứng dụng vào sinh học, y học cho người Qua nghiên cứu cụ thể, nhà khoa học nhận thấy rằng, 75% trí thông minh người gen định [1]  Kiểm tra quan hệ huyết thống: Phương pháp ứng dụng phổ biến đời sống thường gọi xét nghiệm DNA Xét nghiệm DNA lĩnh vực đòi hỏi độ xác cao Mỗi kết xét nghiệm DNA huyết thống có thay đổi sống nhiều người, cần phải đảm bảo việc xét nghiệm thực xác Tất trình tư thu mẫu, tách chiết DNA, phân tích DNA đọc kết làm kiểm soát theo quy trình chuẩn, từ kết có độ xác ổn định cao Thông thường, lấy hai mẫu xét nghiệm hai người (hoặc sinh vật khác) từ tóc, tế bào da, mẫu máu… Sau xét nghiệm chuỗi gen xem có độ tương đồng cao hay không Thông thường mẫu DNA mẹ, bố nghi vấn khớp với gene độ xác có quan hệ huyết thống 99.9999% kết luận hai mẫu gen có huyết thống [2]  Phát loại gen gây bệnh: Bác sỹ lấy mẫu máu từ bệnh nhân bị bệnh, tìm kiếm bắt cặp trình tự có độ tương đồng cao Sau đó, so sánh bắt cặp trình tự cao với mẫu gen người bình thường để xem điểm khác mẫu gen Từ đưa kết luận mẫu gen gây bệnh Tập hợp mẫu gen gây bệnh đưa vào sở liệu để làm mẫu gen thử cho lần nghiên cứu sau  Khoa học hình sự: Các điều tra viên lấy mẫu (tóc, máu, da…), dấu vết trường Sau đó, mang giám định Tiếp theo, tiến hành so sánh với sở liệu chuỗi DNA lưu Từ biết có mặt trường vào thời điểm xảy vụ việc Tiến hành lấy lời khai nhân chứng Căn vào kết luận thủ, thời gian, trình xảy vụ án ADN thường sử dụng để xác định tội phạm theo hai cách Trường hợp nghi ngờ: Một mẫu DNA người so sánh với chứng từ trường vụ án Kết so sánh giúp xác định liệu nghi can phạm tội Trường hợp nghi ngờ chưa xác định, chứng sinh học từ trường vụ án phân tích so sánh với hồ sơ phạm tội sở liệu ADN để giúp xác định thủ phạm chứng trường vụ án liên kết với cảnh tội phạm khác thông qua việc sử dụng sở liệu ADN Hiện nay, với trình đô khoa học phát triển, lớp đào tạo điều tra viên mở, giúp học viên tiếp cận công nghệ cách nhanh chóng Có dự án kêu gọi nhiều nguồn tài lên tới triệu đô la Mỹ [3]  Lý thuyết tiến hóa: Các nhà sinh vật tiến hành lẫy mẫu gen từ sinh vật hóa thạch So sánh với mẫu gen loài có hình thù, độ lớn, màu sắc, sinh vật nghi ngờ loài… Nếu mẫu gen loài giống có mức độ tương đồng cao kết luận sinh vật loài tiến hóa từ mức thấp lên mức cao [4]  ……………………………… Đặc trưng phức tạp chuỗi DNA nằm chỗ chuỗi số độ dài khác biểu diễn phạm vi dự đoán thành phần cấu tạo nên DNA Những đặc trưng phức tạp cho phép tìm kiếm cấu trúc lặp bên nhiễm sắc thể qua nhiều nhiễm sắc thể Và đặc trưng sử dụng để tìm khoảng cách tiến hóa cấu trúc nên phát sinh loài Nên khó đưa thuật toán tối ưu để tìm kiếm, giải trình tự đoạn DNA hiệu Nhiều thuật toán tìm kiếm dành riêng cho chuỗi DNA phát triển từ khoảng 30 năm trước Hiện nay, kỹ thuật tìm kiếm liệu chuỗi DNA sử dụng rộng rãi sinh học Có hàng trăm thuật toán đề xuất cho tìm kiếm liệu DNA nhìn chung thuật toán tìm kiếm thường sử dụng là:  Phương pháp áp dụng Mô hình Markov ẩn[5] phương pháp sử dụng mô hình thống kê, tính toán xác suất Thuật toán dùng phương pháp mô hình hóa trình tìm kiếm chuỗi có sử dụng tham số quan sát tham số trước – mô hình Markov Sau xác định tham số trước từ tham số quan sát Các tham số mô hình rút sau sử dụng để thực phân tích Phương pháp sử dụng rộng rãi tin sinh học nhiên chi phí thời gian lớn hàm tính toán phức tạp  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 sử dụng để tìm giống có độ tương đồng cao hai chuỗi Bằng cách lập ma trận, tính độ đo để tìm giống có độ tương đồng cao tất độ dài phân đoạn hai xâu, hai chuỗi protein nucleotide Với chuỗi tìm kiếm có độ tương đồng cao trước đó, phương pháp mở rộng phạm vi tìm kiếm hai phía (trước sau) Phương pháp có ưu điểm độ xác cao Tuy nhiên chi phí thời gian lớn Phương pháp 10 biết ký tự bắt đầu tệp Các thông tin dòng cho biết nội dung sau: tên chuỗi, thích, ký hiệu chuỗi ngân hàng CSDL (với trung tâm liệu khác nhau, mã chuỗi khác nhau), vị trí bắt đầu, vị trí kết thúc chuỗi DNA gốc, tên loài (trong định dạng FASTA, dòng sử dụng để mô tả chuỗi) Bất ký tự không thuộc mã hợp lệ (vd: khoảng trống, dấu hoa thị, v.v ), chương trình đọc dòng bỏ qua Ngoại trừ dòng đầu tiên, tất dòng dòng mô tả trình tự chuỗi nucleotide amino axiet dạng số hóa: dòng thường có 80 ký tự Chuỗi Nucleotide gồm loạt ký tự A, T, G, C nằm liên tiếp, xem kẽ với nhau, nhiều ký tự giống nằm gần Chuỗi Amino axit gồm nhiều ký tự hơn: A, B, C, D… (có thể bao gồm dấu gạch ngang “-“, dấu “*”) Do đơn giản FASTA nên nhiều công cụ Python, Ruby, PERL, C++… dễ dàng truy xuất thao tác định dạng [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 49 2.3.2 Bảng kết lần thử phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp dụng N-Gram Tất liệu thử nghiệm liệu chuẩn Dữ liệu đầu vào tệp định dạng FASTA trích xuất từ chuỗi gen gốc ngân hàng liệu gen NCBI, gen tải miễn phí phục vụ cho mục đích nghiên cứu Chuỗi cần tìm kiếm nhập từ bàn phím Chuỗi cần tìm kiếm so sánh với liệu từ điển tệp FASTA để biết chuỗi nhập từ bàn phím cần tìm kiếm có liệu từ điển không, có chuỗi có mặt liệu từ điển Kết trình tìm kiếm hiển thị lên hình Chương trình thực qua hai bước Bước một: tiền xử lý bước hai: tìm kiếm hiển thị kết Chi tiết bước người viết đề cập mục 2.2 Chương trình thực với 11 lần thử Với sở liệu mẫu trích xuất từ gen gốc sở liệu gen NCBI Chi tiết lần thử thể bảng 2.1 STT Tên loại gen 10 11 Chr-1 Chr-2 Chr-3 Chr-4 Chr-5 Chr-6 Chr-7 Chr-8 Chr-9 Ec-1 Ec-2 Dung lượng tệp đầu vào (byte) 000 000 000 10 000 12 000 100 000 008 000 107 000 12 000 000 584 860 100 000 Bộ nhớ RAM sử dụng (byte) ~ 000 000 ~ 000 000 ~ 000 000 ~ 000 000 ~ 000 000 ~ 10 000 000 ~ 15 000 000 ~ 20 000 000 ~ 400 000 000 ~ 30 000 000 ~ 40 000 000 Thời gian (giây) Tiền Tìm Hiển thị xử lý kiếm kết 10 30 58 71 308 11 100 120 Bảng Chi tiết lần chạy thử chương trình 50 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 tìm kiếm chuỗi đoạn gen lấy từ sở liệu gen NCBI Quá trình tìm kiếm thu kết nhớ sử dụng tìm kiếm, thời gian tìm kiếm hiển thị kết hình để so sánh hiệu phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram với phương pháp loại BLAST Đồng thời so sánh hiệu phương pháp với phương pháp tìm kiếm nhạy cảm đầy đủ Smith&Waterman để thấy cải tiến phương pháp đề xuất thực mang lại hiệu thời gian tìm kiếm tiết kiệm dung lượng nhớ trình tìm kiếm Do luận văn tập trung nghiên cứu cải thiện thời gian tìm kiếm nên sau người viết tập trung mô tả cách thức cải thiện đạt việc cải thiện thời gian đưa kết thuật toán Hiệu thời gian dung lượng nhớ trình tìm kiếm đưa kết việc nghiên cứu Mỗi kiểm tra thực 10 lần kết thể 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 sở liệu ban đầu thành đoạn nhỏ hơn, sau sử dụng phương pháp đánh mục cho đoạn nhỏ đó, việc truy xuất kết thực bảng mục Việc đánh mục rõ ràng đánh theo số thứ tự cụ thể nên nhập nhằng trình tìm kiếm Hơn bảng mục có liên kết với thông qua định dạng tệp chia nhỏ trình tiền xử lý Các định dạng tệp đánh mục số thứ tự, có vị trí bắt đầu, vị trí kết thúc đoạn theo sở liệu chuỗi đầu vào Chính việc tìm kiếm diễn đoạn chia Với độ lớn 51 khoảng 2000 kb đoạn, việc máy tính cá nhân tìm kiếm liệu khoảng 80 kb đến 200 kb đoạn 2000 kb hoàn toàn thực cách nhanh chóng Ví dụ: Ở bảng 2.1 từ trình tìm kiếm đến việc đưa kết cho đoạn mẫu 12 nucleotide tệp sở liệu kb đầu vào khoảng giây Trong đó, với phương pháp khác Smith&Water Man trình tìm kiếm đến hiển thị kết giây 2.4.2 Tiết kiệm nhớ trình tìm kiếm Chương trình thực qua hai bước tiền xử lý tìm kiếm, đưa kết hình Ở bước – tiền xử lý, chương trình chia nhỏ tệp sở liệu thành đoạn nhỏ – với độ dài 500 ký tự, sau lập bảng, đánh mục cho đoạn nhỏ Nên việc truy xuất trình tìm kiếm việc truy xuất vào đoạn liệu Với tốc độ máy tính nay, việc truy xuất tìm kiếm đoạn khoảng vài chục byte sở liệu độ lớn khoảng 4000 byte thực thực nhanh chóng Ví dụ: Ở bảng 2.1 từ trình tìm kiếm đến việc đưa kết cho đoạn mẫu 12 nucleotide tệp sở liệu kb đầu vào khoảng 1kb nhớ RAM với phương pháp Smith&Water Man trình tìm kiếm đến trình hiển thị kết nhớ RAM cần sử dụng tổng cộng 500 kb 52 CHƢƠNG 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 SMITHWATERMAN Ở chương này, người viết trình bày thực nghiệm bổ sung để minh họa thêm tính hiệu phương pháp tìm kiếm chuỗi DNA tương tự nhanh áp dụng Ngram so với hai thuật toán BLAST-phương pháp tìm kiếm chuỗi tương tự nhanh 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 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 trình tìm kiếm chuỗi có sử dụng tham số quan sát tham số trước – mô hình Markov Sau xác định tham số trước từ tham số quan sát Các tham số mô hình rút sau sử dụng để thực phân tích Với mô hình Markov ẩn cấu trúc mô hình thay đổi dễ dàng cho phù hợp với ứng dụng cụ thể Phương pháp thứ hai phương pháp tìm kiếm chuỗi liên kết nhạy cảm đầy đủ phương pháp sử dụng để tìm giống có độ tương đồng cao hai chuỗi Bằng cách lập ma trận, tính độ đo để tìm giống có độ tương đồng cao tất độ dài phân đoạn hai xâu, hai chuỗi protein nucleotide Với chuỗi tìm kiếm có độ tương đồng cao trước đó, phương pháp mở rộng phạm vi tìm kiếm hai phía (trước sau) Phương pháp có ưu điểm độ xác cao Tuy nhiên chi phí thời gian lớn Hiện nay, cải tiến máy tính thuật toán tìm kiếm, phương pháp tìm kiếm đồng thời nhiều chuỗi lúc khoảng (1000 chuỗi) [18] Thuật toán tìm kiếm chuỗi hiệu thứ ba phương pháp tìm kiếm chuỗi tương tự nhanh Phương pháp 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 việc đánh giá chuỗi sở liệu với chuỗi truy vấn theo ngưỡng định Dựa vào bảng kết đánh giá, đưa kết mức độ tương đồng hai chuỗi Mặc dù có thời gian xử lý nhanh phương pháp có độ xác không phương pháp liên kết nhạy cảm đầy đủ Thuật toán điển hình phương pháp dùng 53 phổ biến có nhiều biến thể để so sánh với trường hợp cụ thể Phương pháp tìm kiếm chuỗi thứ tư phương pháp tìm kiếm chuỗi phù hợp gần (chứ xác) Phương pháp sử dụng cách tiếp cận vét cạn (bruteforce) để tính “độ chỉnh sửa” chuỗi từ điển mẫu cho gần với tất chuỗi chuỗi cần truy vấn, sau chọn chuỗi với “độ chỉnh sửa” tối thiểu Tuy nhiên, thuật toán 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 phương pháp sử dụng mô hình kết hợp xác gần xác: Vd: mpscan[9] Phương pháp sử dụng mô hình đánh dấu tập mẫu, tức chia chuỗi cần truy vấn thành chuỗi mẫu nhỏ với chiều dài cố định Sau đó, so sánh chuỗi chia với chuỗi sở liệu để tìm kiếm tương đồng, thực xử lý đồng thời nhiều mẫu Phương pháp thường dùng có hiệu việc tìm kiếm tập lớn chuỗi DNA/RNA ngắn CSDL chuỗi DNA/RNA Phương pháp điển hình dạng Mpscan Chương trình Mpscancó thể đọc đồ giao diện Có khả tìm kiếm ngược, bổ sung mẫu Tuy nhiên, thời gian thực mức độ trung bình) Là công cụ đánh dấu tập mẫu đạt hiệu 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 người viết trình bày chương phương pháp tìm kiếm chuỗi với cải tiến tốc độ tìm kiếm tiết kiệm nhớ số phương pháp khác Sau đây, người viết trình bày thực nghiệm mà người viết thực để làm rõ nhận định tính hiệu 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 thực nghiệm thực máy tính cá nhân Dell Vostro 15 3000 Series với cấu 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 chạy Linux kernel (64bit) Chương trình viết chỉnh sửa ngôn ngữ C++ sử dụng QT Creator (build 1.7.0 40-b43) BLAST SMITH&WATERMAN viết chỉnh sửa ngôn ngữ C++ 54 Các kích thước đo byte, ví dụ 1MB có nghĩa 1024 byte Các tập liệu thực nghiệm: Người viết thực so sánh ba thuật toán tìm kiếm hai tập 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 liệu gen người lấy từ sở liệu NCBI dùng cho nghiên cứu Trích rút chuỗi liên ứng loại cho gen Sử dụng Chr-# để biểu diễn tập tất 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 Các chuỗi lấy từ nhiễm sắc thể có độ tương đồng cao chuỗi lấy từ nhiễm sắc thể khác Tập tất 23 tập liệu gen người (Chr-1 tới Chr-22, Chr-X) kí hiệu H-* Tập liệu gen người lớn Chr-1 với 65631142 byte (62,6MB), tập liệu nhỏ Chr22 với 9953567 byte (10MB) kích thước H-* khoảng 50000000 byte (5Gb) (2) Các tập liệu Escherichia coli lấy từ sở liệu NCBI Tập hợp tất tập liệu Escherichia coli kí hiệu Ec-* Tập liệu Escherichia coli nhỏ Ec_K-12 substr W3110 với 4646332 byte (4,6Mb) Tập lớn Ec_CI5 với 8,092,977 byte (8,1Mb) kích thước Ec-* vào khoảng 207008000 byte (207Mb) Dữ liệu tệp gen có dạng chuỗi Các hình 3.1, 3.2 3.3 thể định dạng chuỗi gen tập liệu thực nghiệm Hình 3.1 Định dạng Fasta chuỗi gen khuẩn E Coli K12 – DH10B 55 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 NGram với phƣơng pháp BLAST phƣơng pháp Smith-Water Man Thực nghiệm so sánh 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 sau: với loài nhiễm sắc thể, lựa chọn ngẫu nhiên số chuỗi áp dụng thuật toán lựa chọn cho chuỗi ngẫu nhiên Kết thống kê so sánh kích thước gen sau tìm kiếm, thời gian tìm kiếm tất bước thuật toán cho nhiều chuỗi gen cụ thể Kết sau thực nghiệm phương pháp tìm kiếm chuỗi cho thấy thời gian đưa kết BLAST tốt số lượng chuỗi tìm thấy mức chấp nhận Hầu hết thời gian lần tìm kiếm BLAST nhanh phương pháp Smith-Waterman tìm kiếm với chuỗi từ điển có dung lượng nhỏ tìm kiếm với chuỗi từ điểm có dung lượng lớn Số chuỗi tìm kiếm BLAST lần tìm kiếm với đoạn chuỗi dung lượng nhỏ xấp xỉ với Smith-Waterman N-Gram Ở 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 nhất, sau đến BLAST, cuối N-Gram Khi tìm kiếm với chuỗi từ điển dung lượng nhỏ (khoảng Mb), thời gian đưa kết N-Gram nhanh nhất, 56 BLAST, cuối Smith-Waterman Khi tìm kiếm với chuỗi từ điển có dung lượng lớn ( >5 Mb), phương pháp N-Gram đưa kết nhanh số kết tìm không BLAST Smith-Waterman Với dung lượng chuỗi từ điển 5Mb-10Mb, N-Gram tiết kiệm nhớ BLAST Smith-Waterman Khi dung lượng chuỗi từ điển >50Mb, nhớ sử dụng phương pháp N-Gram tăng đáng kể > 2Gb Như vậy, thấy phương pháp tìm kiếm tương tự nhanh áp dụng N-Gram đạt hiệu cao tiết kiệm nhớ, thời gian tìm kiếm, số lượng kết tìm tìm kiếm với chuỗi từ điển dung lượng nhỏ Mặc dù sử dụng phương pháp với chuỗi có dung lượng lớn, thời gian đưa kết nhanh hai phương pháp lại số kết tìm không nhiều hai phương pháp lại Hiệu số kết tìm BLAST Smith-Waterman so với N-Gram tăng dần theo độ lớn dung lượng chuỗi từ điển Hình 3.3 Minh họa kết chạy BLAST độ dài chuỗi truy vấn 12 với mẫu gen thử Chr-4 57 Hình 3.4 Minh họa kết chương trình sử dụng phương pháp Smith-Waterman với độ dài chuỗi truy vấn 12 3.3 Phân tích đánh giá kết thực nghiệm Bộ liệu tải lớn, tổng cộng khoảng gần 100GB môi trường thực nghiệm có hạn nên người viết lựa chọn số chuỗi với dung lượng phù hợp để thực trình tìm kiếm so sánh Phương pháp tìm kiếm chuỗi Smith-Waterman mô hình phương pháp tìm kiếm quy hoạch động Có thể sử dụng kết trình tìm kiếm trước để sử dụng cho lần tìm kiếm tức mở rộng phạm vi tìm kiếm từ chuỗi tìm trước Phương pháp có ưu điểm việc hiển thị kết trực quan Tuy có thời gian tìm kiếm chậm cần nhiều nhớ tìm kiếm Nhưng ba phương pháp tìm kiếm, phương pháp tìm kiếm có số lượng kết đưa nhiều tìm kiếm trường hợp, sô chuỗi tìm thấy nhiều hai phương pháp lại Phương pháp BLAST phương pháp tìm kiếm chuỗi có thời gian tìm kiếm nhanh Smith-Waterman tìm kiếm với chuỗi từ điển dung lượng lớn, số lượng kết đưa phương pháp nhiều N-Gram không phương pháp Smith-Waterman Phương pháp N-Gram đạt hiệu cao số kết tìm được, thời gian xử lý, dung lượng nhớ tìm kiếm với chuỗi từ điển dung lượng nhỏ (< 8Mb) so với BLAST Smith-Waterman Đây ưu điểm phương pháp Khi tìm kiếm với chuỗi từ điển có dung lượng > 10Mb, lần thực nghiệm, số kết tìm N-Gam không hai phương pháp lại (mặc dù thời gian tìm kiếm nhanh hơn) Số chuỗi không tìm so với hai phương pháp lại tăng dần theo độ lớn dung lượng chuỗi từ điển Nguyên nhân 58 trình chia tách tệp liệu từ điển đầu vào không triệt để Các đoạn gen cuối đoạn chia đoạn gen đầu đoạn sau nằm kết chuỗi cần tìm kiếm Bảng thể bảng thống kê kết đạt thực 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 phương pháp liên kết nhạy cảm đầy đủ Smith&Waterman tìm kiếm chuỗi DNA có độ dài 12 nucleotide Chuỗi tìm kiếm chọn ngẫu nhiên, lần tìm kiếm thử nghiệm với dung lượng chuỗi CSDL khác lần thử Kết thực nghiệm cho thấy với tệp sở liệu từ điển có dung lượng 2Mb, N-Gram đạt hiệu thời gian tìm kiếm tốt hai thuật toán khác tìm kiếm chuỗi tương tự nhanh BLAST 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 tệp sở liệu từ điển dung lượng 2Mb cỡ 100 giây Trong đó, với BLAST khoảng 160 giây, với Smith-Waterman khoảng 190 giây Như trình bày trên, N-Gram không thuật toán hiệu thời gian tìm kiếm mà hiệu dung lượng nhớ sử dụng thực chương trình Kết thực nghiệm cho thấy với chuỗi từ điển có dung lượng 2Mb, nhớ cần thiết cho N-Gram khoảng 6Mb, với BLAST 10Mb, với Smith-Waterman khoảng 14Mb 59 KẾT LUẬN Những thách thức việc khám phá cấu trúc, chức năng, tiến hóa di truyền hệ gen loài, phương pháp xếp tìm kiếm chuỗi đa lượng đặt câu hỏi tập trung vào việc biểu diễn, lưu trữ, truyền tải, truy vấn bảo vệ thông tin chuỗi gen Mặc dù việc lưu trữ tìm kiếm thông tin chuỗi DNA kiểm soát phần việc cải tiến phương pháp tìm kiếm tốt cho chuỗi DNA vấn đề quan trọng nghành tin sinh học Đặc biệt việc tìm giải thuật nhanh tốc độ tìm kiếm, đạt độ xác cao đồng thời số lượng kết trình tìm kiếm triệt để thách thức lớn Trong luận văn này, người viết trình bày phương thức thuật toán tìm kiếm tiêu biểu cho phương thức tìm kiếm 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 hiệu mà thuật toán mang lại cho tìm kiếm chuỗi DNA thời gian đưa kết nhanh, tiết kiệm nhớ sử dụng, phương pháp tính toán đơn giản tìm kiếm Thuật toán đạt hiệu việc tăng hiệu tìm kiếm chuỗi phương pháp kế thừa: (1) tìm kiếm bắt cặp trình tự ngắn, (2) đánh giá bắt cặp trình tự có điểm số cao (3) thống kê kết đạt Ở điều kiện lý tưởng chọn lựa chuỗi từ điển phù hợp hay chuỗi gen loài có độ tương đồng cao, thời gian tìm kiếm nhanh gấp ba lần so với phương pháp BLAST SmithWaterman Bên cạnh đặc trưng kế thừa từ thuật toán tìm kiếm tương tự nhan BLAST, N-Gram thực hiệu sử dụng phương pháp đánh số để tiết kiệm thời gian tìm kiếm đưa kết đáng kể Đóng góp NGram chia chuỗi gen từ điển thành đoạn có độ dài ngắn (500 ký tự), sau sử dụng phương thức đánh số cho phân đoạn độ dài theo N-gram đơn vị cho chuỗi truy vấn Cơ chế kết hợp hai đặc tính tốt là: cấu trúc đơn giản đưa kết nhanh việc truy vấn theo số Hai đặc tính giúp N-Gram đạt ưu việt thời gian tìm kiếm khả tiết kiệm nhớ N-Gram có nhược điểm tìm kiếm với chuỗi có dung lượng 8Mb, số lượng kết tìm thấp 60 BLAST Smith-Waterman Nguyên nhân việc chia chuỗi gen từ điển thành đoạn nhỏ, điểm cuối đoạn chia điểm đầu đoạn kết tìm kiếm nằm điểm nối hai đoạn chia Dung lượng nhớ sử dụng thực thi N-Gram nhược điểm tìm kiếm với chuỗi từ điển dung lượng lớn 20Mb với máy tính cá nhân Việc chia thành tệp nhỏ đánh số cho đoạn liệu chia làm tăng vọt theo hàm số mũ với phương pháp Độ lớn tệp chia theo phương pháp phụ thuộc vào số N (trong N-Gram) Trong DNA với nucleotide (A, T, G, C) số lượng đoạn cần tìm kiếm 4N với N lớn, dung lượng tệp truy vấn lớn lên theo hàm mũ Tuy gặp số bất lợi thời gian tìm kiếm dung lượng máy ảo sử dụng ngôn ngữ C++ làm công cụ phát triển N-Gram chứng minh tính hiệu việc tìm kiếm chuỗi gen thuật toán tìm kiếm tương tự nhanh Trong tương lai N-Gram tiếp tục cải tiến để đạt tốc độ tìm kiếm khả tiết kiệm nhớ đáng mong đợi Cùng với nghiên cứu nhận định trình bày, người viết thực 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 tìm kiếm chuỗi theo phương pháp liên kết nhạy cảm đầy đủ Smith-Waterman phương pháp tìm kiếm tương tự nhanh BLAST để bổ sung cho kết nghiên cứu đạt Kết thực nghiệm chưa đạt hiệu tiết kiệm nhớ hay kết tìm kiếm mong đợi cao thuật toán tìm kiếm chuỗi tương tự nhanh số hạn chế môi trường thực nghiệm, bước đầu khẳng định tối ưu thuật toán tìm kiếm tương tự nhanh mà tiêu biểu N-Gram cho tìm kiếm chuỗi gen Những kết thực nghiệm tiền đề để người viết tiếp tục nghiên cứu cải tiến cho việc tìm kiếm chuỗi gen tương lai 61 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 62 [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 63 ... 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 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 trình... CÁC THUẬT TOÁN TÌM KIẾM CHUỖI DNA 13 1.1 Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn 13 1.2 Phƣơng pháp liên kết nhạy cảm đầy đủ 15 1.3 Phƣơng pháp tìm kiếm tƣơng. .. tƣơng tự nhanh 21 1.4 Phƣơng pháp sử dụng mô hình phù hợp gần 25 1.5 Phƣơng pháp sử dụng mô hình kết hợp xác gần xác 31 CHƢƠNG N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI TƢƠNG TỰ NHANH ÁP DỤNG