Tài liệu Khám phá tương tác trội nhờ phương pháp tối ưu đàn kiến

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHI KHÁM PHÁ TƢƠNG TÁC TRỘI NHỜ PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI, 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHI KHÁM PHÁ TƢƠNG TÁC TRỘI NHỜ PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN Ngành : Công nghệ thông tin Chuyên ngành : Hệ thống thông tin Mã số : 60 48 05 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. Đỗ Đức Đông Hà Nội, 2014 1 LỜI CẢM ƠN Trước hết, tôi xin gửi lời biết ơn sâu sắc đến hai người thầy TS. Đỗ Đức Đông và thầy PGS. TS Hoàng Xuân Huấn, hai thầy đã dành rất nhiều thời gian và tâm huyết hướng dẫn nghiên cứu và giúp tôi hoàn thành tốt luận văn tốt nghiệp này. Thầy đã mở ra cho tôi những vấn đề khoa học rất lý thú, định hướng nghiên cứu các lĩnh vực hết sức thiết thực và vô cùng bổ ích, đồng thời tạo điều kiện thuận lợi tốt nhất cho tôi học tập và nghiên cứu. Tôi cũng xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể và cá nhân tôi nói riêng. Tôi xin cảm ơn tới các thầy và các anh chị đã thường xuyên giúp đỡ, trao đổi, góp ý về những vấn đề khoa học liên quan tới luận văn. Trên tất cả, tôi xin gửi lời biết ơn tới bố mẹ, gia đình người thân. Bố mẹ đã phải làm việc vất vả tạo cơ hội cho tôi chọn con đường đi của mình. Một lần nữa, tôi xin chân thành cảm ơn! Hà Nội, tháng 10 năm 2014. Học viên Nguyễn Thị Chi 2 LỜI CAM ĐOAN Những kiến thức trình bày trong luận văn là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Tôi xin cam đoan đây là công trình nghiên cứu của tôi và không sao chép của bất kỳ ai. Hà Nội, tháng 10 năm 2014. Học viên Nguyễn Thị Chi 3 MỤC LỤC LỜI CẢM ƠN ................................................................................................................1 LỜI CAM ĐOAN ..........................................................................................................2 MỤC LỤC ......................................................................................................................3 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT ............................................................6 DANH MỤC CÁC BẢNG BIỂU ..................................................................................7 DANH MỤC CÁC HÌNH VẼ .......................................................................................8 MỞ ĐẦU .........................................................................................................................9 CHƢƠNG I. TƢƠNG TÁC TRỘI QUY VỀ BÀI TOÁN TƢƠNG TÁC GEN......11 1.1 Tương tác gen và các hiệu ứng gây ra .................................................................11 1.1.1 Khái niệm về tương tác gen ...........................................................................11 1.1.2 Hệ quả của tương tác tác gen và hướng nghiên cứu ......................................13 1.1.2.1 Hệ quả của tương tác gen............................................................................13 1.1.2.2 Hướng nghiên cứu ......................................................................................14 1.2 Bài toán phát hiện tương tác gen ..........................................................................15 1.2.1 Mục đích vì sao cần phát hiện tương tác gen ................................................15 1.2.2 Khái quát quá trình nghiên cứu tìm tương tác gen ........................................15 1.2.3 Phát biểu bài toán tương tác gen ....................................................................16 1.2.3.1 Phát biểu bài toán........................................................................................16 1.2.3.2 Mô hình hóa bài toán ..................................................................................17 CHƢƠNG II. GIỚI THIỆU VỀ THUẬT TOÁN ANT COLONY OPTIMIZATION (ACO) ............................................................................................18 2.1 Lịch sử ra đời của thuật toán ACO ......................................................................18 2.1.1 ACO ra đời từ việc quan sát hành vi của đàn kiến trong quá trình di chuyển tìm kiếm thức ăn .....................................................................................................18 2.1.2 Mùi và ý nghĩa vết mùi trên đường đi trong quá trình di chuyển của kiến ...18 2.2 Thuật toán ACO ...................................................................................................20 2.2.1 Đồ thị cấu trúc ...............................................................................................20 2.2.2 Trình bày về thuật toán ACO cơ bản ............................................................21 2.2.3 Quy tắc cập nhật vết mùi ..............................................................................23 4 2.2.3.1 Thuật toán AS .............................................................................................23 2.2.3.2 Thuật toán ACS ..........................................................................................24 2.2.3.3 Thuật toán Max-Min ...................................................................................24 2.2.3.4 Thuật toán Max- Min trơn ..........................................................................25 2.3 Ứng dụng thuật toán ACO trong việc giải quyết bài toán Người chào hàng Sale Man ............................................................................................................................25 2.3.1 Bài toán người chào hàng trong thực tế .........................................................25 2.3.2 Phát biểu bài toán người đưa hàng trên mô hình hóa đồ thị ..........................25 2.3.3 Áp dụng thuật toán ACO giải quyết bài toán người chào hàng.....................26 CHƢƠNG III. GIẢI BÀI TOÁN TƢƠNG TÁC GEN BẰNG PHƢƠNG PHÁP ACO ..............................................................................................................................29 3.1 Các phương pháp tiếp cận, và ưu nhược điểm .....................................................29 3.1.1 Thuật toán BEAM..........................................................................................29 3.1.2 Thuật toán SNPHarvester ..............................................................................29 3.1.3 Ưu, nhược điểm .............................................................................................30 3.1.3.1 Ưu điểm ......................................................................................................30 3.1.3.2 Nhược điểm ................................................................................................ 30 3.2 Tương quan giữa bài toán tương tác gen với bài toán người chào hàng ..............31 3.3 Thuật toán ACO để giải quyết bài toán tương tác gen .........................................31 3.3.1 Trình bày thuật toán .......................................................................................31 3.3.1.1 Thuật toán Generic ACO ............................................................................31 3.3.1.2 Thuật toán AntEpiSeeker ............................................................................34 3.3.2 Ý nghĩa các tham số .......................................................................................37 3.3.3 Xác suất Chi-square và trị số Pvalue.............................................................38 3.3.3.1 Xác suất Chi-square ....................................................................................38 3.3.3.2 Trị số Pvalue...............................................................................................40 3.3.3.3 Vận dụng Chi-square trong bài toán ...........................................................41 CHƢƠNG IV. KẾT QUẢ THỰC NGHIỆM ............................................................44 4.1 Kết quả thực nghiệm ............................................................................................44 4.1.1 Các thông số cài đặt .......................................................................................44 5 4.1.2 Các kết quả thực nghiệm của bài báo ............................................................45 4.1.3 Xử lý song song và quy tắc cập nhật mùi mới Max-Min trơn (SMMAS) ....50 4.1.4 Phần mềm sử dụng.........................................................................................61 4.2 Ý nghĩa kết quả thực nghiệm ...............................................................................61 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................................ 62 TÀI LIỆU THAM KHẢO...........................................................................................63 6 DANH MỤC CÁC KÍ HIỆU, TỪ VIẾT TẮT ACO Ant colony optimization ACS Ant colony system ADN Acid deoxyribo nucleic AMD Age related macular ANTS Approximate nondeterministic tree search AS Ant system ARN Axit ribonucleic BEAM Bayesian epistasis association mapping GWA Genome wide apporoach HGP Human genome project MCMC Markov chain monte carlob MMAS Max min ant system SMMAS Smoothed max min ant system 3-LAS Three level ant system 7 DANH MỤC CÁC BẢNG BIỂU Bảng 1.1 Minh họa đầu vào của bài toán ..................................................................17 Bảng 1.2Minh họa đầu ra của bài toá n .........................................................................17 Bảng 2.1 Một số thuật toán ACO .............................................................................176 Bảng 3.1 Minh họa tương quan đồ thị ...........................................................................31 Bảng 3.2 Tuổi và kết quả học tập của sinh viên ............................................................39 Bảng 3.3 Kết quả của trị số 𝑶 và 𝑬 của ví dụ ...............................................................40 Bảng 3.4 Ví dụ đầu vào của bài toán với 2 vị trí ...........................................................41 Bảng 3.5 Các giá trị của T với mẫu cá thể ....................................................................41 Bảng 3.6 Kết quả của trị số 𝑶 và 𝑬 của ví dụ ...............................................................43 Bảng 4.1 So sánh tỉ lệ giảm thiểu dương tính giả..........................................................48 Bảng 4.2 Kết quả trước khi chưa giảm thiểu dương tính giả ........................................49 Bảng 4.3 Kết quả sau khi giảm thiểu dương tính giả ....................................................49 Bảng 4.4 So sánh tỉ lệ phần trăm phát hiện trên bộ dữ liệu lớn ....................................50 Bảng 4.5 Thời gian chạy của các thuật toán ..................................................................50 Bảng 4.6 Kết quả thực nghiệm chung iItCountLarge = 150; iItCountSmall =300 .......53 Bảng 4.7 Liệt kê những bộ SNPs giống nhau iItCountLarge = 150; iItCountSmall =300 ..........54 Bảng 4.8 Liệt kê những vị trí giống nhau iItCountLarge = 150; iItCountSmall =300 .......................................................................................................................................55 Bảng 4.9 Kết quả thực nghiệm chung iItCountLarge = 2500; iItCountSmall =5000 ...57 Bảng 4.10 Liệt kê những bộ SNPs giống nhau iItCountLarge = 2500; iItCountSmall =5000.......58 Bảng 4.11 Liệt kê những vị trí giống nhau iItCountLarge = 2500; iItCountSmall =5000.............58 8 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Cấu trúc nhiễm sắc thể ...................................................................................11 Hình 1.2 Minh họa gen trên nhiễm sắc thể ....................................................................11 Hình 1.3 Một đột biến điểm xảy ra trong phân tử DNA thay thế .................................12 cặp nucleotide A-T bằng cặp nucleotide G-C ..............................................................12 Hình 1.4 Đột biến gen KIT trong u mô đệm đường tiêu hóa ........................................14 Hình 2.1 Thực nghiệm hành vi của kiến .......................................................................19 Hình 2.2 Thực nghiệm bổ sung .....................................................................................20 Hình 2.3 Đặc tả thuật toán ACO ..................................................................................23 Hình 2.4 Minh họa hình ảnh bài toán người đưa hàng ..................................................25 Hình 2.5 Đặc tả thuật toán ACO cho bài toán TSP .......................................................28 Hình 3.1 Đặc tả thuật toán SNPHarvester .....................................................................30 Hình 3.2 Đặc tả thuật toán Generic ACO ......................................................................30 Hình 3.3 Mô tả hoạt động của kiến ...............................................................................33 Hình 3.4 Mô tả thuật toán AntEpiSeeker tổng quát ......................................................36 Hình 3.5 Đặc tả thuật toán AntEpiSeeker .....................................................................37 Hình 4.1 Mô tả INPFILE ...............................................................................................44 Hình 4.2 Mô tả OUTFILE .............................................................................................45 Hình 4.3 Minh họa ý nghĩa ba mô hình 1,2,3 ................................................................ 46 Hình 4.4 Đánh giá hiệu năng giữa các thuật toán AntEpiSeeker. SNPHarvester, BEAM và Generic ACO ................................................................................................ 47 Hình 4.5 Minh họa OpenMP .........................................................................................51 9 MỞ ĐẦU Tin sinh học là một lĩnh vực khoa học liên ngành, trong đó sinh học phân tử và tin học đóng vai trò chủ đạo. Sinh học làm môi trường dữ liệu cơ sở, trên đó xây dựng và hoàn thiện các chương trình xử lý dữ liệu ứng dụng làm công cụ hỗ trợ hiệu quả cho việc nghiên cứu, thu nhận và sản xuất ra các sản phẩm sinh học mong muốn khác nhau phục vụ đời sống con người…Về cơ bản, tin sinh học tập trung vào nghiên cứu và áp dụng các phương pháp cũng như các kĩ thuật trong tin học để giải quyết các bài toán trong sinh học phân tử. Tin sinh học có tính ứng dụng cao trong cuộc sống, đặc biệt trong lĩnh vực nông nghiệp và lĩnh vực y-dược. Vấn đề về sức khỏe và bệnh tật của con người là những vấn đề rất được quan tâm và chú ý. Hiện nay có rất nhiều các căn bệnh như: Bệnh ung thư, bệnh thoái hóa điểm vàng, bệnh tim mạch… Tất cả đều là những căn bệnh di truyền. Có nhiều các tác nhân liên quan đến bệnh như: Tác nhân vật lý, chế độ ăn uống, tác nhân hóa học,…, nhưng yếu tố di truyền vẫn là tác nhân chính. Gen di truyền được công nhận rộng khắp rằng nhiều căn bệnh có thể là nguyên nhân bởi những tác động của nhiều loại gen biến đổi, trong mỗi gen của các cá thể, những gen đó chiếm số ít nhưng lại có tác động mạnh. Vấn đề đang được quan tâm hiện nay là tiến hành nghiên cứu về các gen di truyền: Xác định vị trí gen trên một bệnh chứng, gen xác định là nguyên nhân chính để dẫn đến các căn bệnh. Phần lớn trong số những biến thể di truyền là hàng triệu các điểm tại những vị trí nucleotide nhất định đã làm thay đổi mã di truyền do sự biến đổi của đơn nucleotide trong bộ gen. Khi xảy ra đột biến điểm làm cho một đơn nucleotide bị biến đổi hoặc ngược lại tạo ra một “single nucleotide polymorphism (SNP)” còn gọi là đa hình đơn nucleotide. Khi SNPs xảy ra trong gen hoặc trong một khu vực gần một gen quy định, nó có thể có vai trò trực tiếp đến sự xuất hiện bệnh bằng cách ảnh hưởng đến chức năng của gen. SNPs hiện đang được Dự án quốc tế HapMap tiến hành một cách hệ thống. Các nhà khoa học tin rằng SNP bản đồ sẽ giúp họ có nhiều gen liên quan tới các bệnh phức tạp. Đã có nhiều thuật toán được nghiên cứu và công bố giải quyết bài toán tương tác gen để đưa ra tập các vị trí nucleotide biến đổi (hay còn gọi là SNP) tương tác với nhau trội được dự đoán là có khả năng cao liên quan đến căn bệnh. Dựa trên đó, các nhà nghiên cứu có thể tìm kiếm ra vị trí các gen liên quan đến các căn bệnh cụ thể mà họ quan tâm. Trong luận văn này, tôi sẽ trình bày khảo cứu lại của tác giả bài báo[22] về cách giải quyết bài toán tương tác gen sử dụng thuật toán Ant Colony Optimization (ACO) để giải quyết. Mục đích để chỉ ra thuật toán AntEpiSeeker có thể giải quyết bài toán với những bộ dữ liệu lớn và đưa ra được kết quả tối ưu hơn so với các thuật toán trước 10 đó. Ngoài ra, trong luận văn tôi thực hiện xử lý song song hóa các tác vụ trong tính toán của Chi-square giúp đẩy nhanh trong quá trình việc cập nhật mùi của kiến mà vẫn đảm bảo tính đúng đắn của thuật toán, cài đặt thực nghiệm với quy tắc cập nhật mùi mới Max-Min trơn (Smoothed Max Min Ant System – SMMAS) được Đỗ Đức Đông đề xuất năm 2012[1]. Ngoài phần kết luận, cấu trúc nội dung của luận văn bao gồm 4 chƣơng: Chương 1: Trình bày sơ lược các khái niệm về sinh học, phát biểu bài toán tương tác gen, hệ quả của tương tác gen và mục đích của việc phát hiện tương tác gen. Chương 2: Trình bày tổng quan về ACO và một vài thuật toán cập nhật mùi khác nhau trong ACO. Ví dụ về bài toán người chào hàng giải quyết bằng thuật toán ACO. Chương 3: Giới thiệu một vài thuật toán giải quyết bài toán tương tác gen với những ưu, nhược điểm. Trình bày lại thuật toán AntEpiSeeker và trình bày về hàm kiểm định thống kê Chi-square. Chương 4: Đưa ra kết quả mà bài báo công bố, giải thích ý nghĩa của các tham số và ý nghĩa đánh giá các thuật toán với nhau khi nào là tốt khi nào là xấu. Chạy thực nghiệm lại với một bộ dữ liệu mô phỏng để so sánh tốc độ của thuật toán ban đầu với tốc độ sau khi xử lý song song hóa các tác vụ của kiến và kiểm tra khả năng tìm ra tập các vị trí nucleotide biến đổi ở phương pháp cập nhật mùi mới. 11 CHƢƠNG I TƢƠNG TÁC TRỘI QUY VỀ BÀI TOÁN TƢƠNG TÁC GEN 1.1 Tƣơng tác gen và các hiệu ứng gây ra 1.1.1 Khái niệm về tƣơng tác gen Một số khái niệm di truyền: Nhiễm sắc thể: Là một cấu trúc trong tế bào chứa hai loại thông tin gồm chuỗi DNA và Protein. Trong đó chuỗi DNA mang thông tin di truyền xác định chức năng và đặc điểm của sinh vật, Protein quyết định đến chức năng và quá trình phát triển của sinh vật. Tập hợp tất các nhiễm sắc thể của một sinh vật được gọi là hệ gen của sinh vật đó. Hình 1.1 Cấu trúc nhiễm sắc thể Chuỗi DNA (Deoxyribonucleic Acid): Là một chuỗi cấu trúc xoắn kép gồm hai sợi liên kết, bắt cặp với nhau (A-T, G-C). Trên mỗi một sợi được biểu diễn bởi một xâu kí tự chứa 4 loại kí tự: A,T,G,C (tên viết tắt của 4 loại nucleotide). Ví dụ, xâu kí tự “CAGTTGACGGCGAACCGTGCGAGCAGACGGTCGTT“ là một chuỗi DNA. Gen: Là một đoạn DNA mang thông tin hướng dẫn tổng hợp protein và có một vị trí nhất định trên nhiễm sắc thể. Gen chịu trách nhiệm về những đặc điểm di truyền. Hình 1.2 Minh họa gen trên nhiễn sắc thể 12 Alen: Các dạng khác nhau của một gen (không cùng xảy ra) nằm tại cùng một vị trí xác định trên một nhiễm sắc thể cụ thể. Locus: Vị trí riêng biệt của một đoạn DNA mang thông tin (hay còn gọi là gen) trên nhiễm sắc thể. Nhiều locus được gọi là loci. SNP: Được viết tắt của “single nucleotide polymorphism” được gọi là đa hình đơn nucleotide (đọc là sờ-níp ), là những biến thể trình tự DNA xảy ra khi một đơn nucleotide (A, T, C, hoặc G) trong trình tự bộ gen bị thay đổi. Được minh họa bằng hình ảnh 1.3: Hình 1.3 Một đột biến điểm xảy ra trong phân tử DNA thay thế cặp nucleotide A-T bằng cặp nucleotide G-C Tương tác gen: Sự tác động qua lại giữa các gen trong quá trình hình thành kiểu hình. Tương tác gen gồm có hai kiểu: Tương tác giữa các gen alen và tương tác giữa các gen không alen (thường được gọi tắt là tương tác gen)[2]. Tương tác giữa các gen alen là tương tác giữa trạng thái khác nhau của cùng một gen tồn tại trên một vị trí nhất định của cặp nhiễm sắc thể tương đồng. Ví dụ 1: Lai giữa hai giống hoa (màu sắc hoa) Quy ước: A- màu đỏ, a- màu trắng (A là trội hoàn toàn so với a) Ptc: Hoa đỏ (AA) x Hoa trắng (aa) F1: Hoa hồng (Aa) Tương tác giữa các gen không alen là tương tác giữa các trạng thái khác nhau của cặp gen, mỗi gen nằm trên các vị trí khác nhau, có thể nằm trên cùng một nhiễm sắc thể hoặc trên các cặp nhiễm sắc thể tương đồng khác nhau. Trong luận văn về sau khi nói tới tương tác gen, sẽ hiểu tương tác giữa các gen không alen. Ví dụ 2: Ví dụ: Lai giữa hai giống hoa (màu sắc hoa) Quy ước: A-B-: Màu đỏ; A- bb-, aaB-, aabb: Màu trắng Ptc: Hoa đỏ (AABB) x Hoa trắng (aabb) F1: Hoa hồng (AaBb) 13 Nhìn vào ví dụ một và ví dụ hai thấy có sự khác nhau. Trong ví dụ một, có Ahay a- quy ước màu hoa đỏ và màu hoa trắng. Trong ví dụ hai, quy ước màu hoa đỏ lại là của hai alen: A-B-, trong đó alen A và alen B ở hai vị trí khác nhau và được gọi là không alen. 1.1.2 Hệ quả của tƣơng tác tác gen và hƣớng nghiên cứu 1.1.2.1 Hệ quả của tƣơng tác gen Môi trường và thực phẩm là hai yếu tố phổ biến gây bệnh cho con người. Tuy nhiên gen là nguyên nhân chính để gây ra các căn bệnh. Có thể nói, yếu tố di truyền đóng vai trò rất lớn. Các căn bệnh phổ biến như: Ung thư, tim mạch, bệnh tai nhĩ, bệnh tiểu đường, bệnh thoái hóa điểm vàng hay mù màu…. Đều liên quan tới gen di truyền. Các bệnh xảy ra khi có sự thay đổi trong các gen chịu trách nhiệm cho sự tăng trưởng và sửa chữa các tế bào. Những thay đổi này là kết quả của sự tương tác giữa các yếu tố di truyền và các tác nhân bên ngoài như: Tác nhân vật lý (tia phóng xạ: Tia X, ..), tác nhân hóa học (thuốc trừ sâu, thuốc diệt cỏ,…), tác nhân sinh học như virus có trong cơ thể hoặc môi trường bên ngoài cơ thể, chế độ ăn uống và lối sống…Sự biến đổi cấu trúc phân tử của gen có thể dẫn đến biến đổi cấu trúc của loại protein mà nó mã hóa, cuối cùng có thể dẫn đến biến đổi ở kiểu hình. Các đột biến gen biểu hiện ra kiểu hình ở từng cá thể riêng lẻ, không tương ứng với điều kiện sống, thường là đột biến lặn là có hại cho bản thân vì chúng đã phá vỡ sự thống nhất hài hòa trong kiểu gen đã qua chọn lọc tự nhiên và duy trì lâu đời trong điều kiện tự nhiên, gây ra những rối loạn trong quá trình tổng hợp protein. Đa số đột biến gen tạo ra các gen lặn là có hại, một số trung tính, một số có lợi. Những gen lặn chỉ biểu hiện ra kiểu hình khi ở thể đồng hợp và trong điều kiện môi trường thích hợp. Qua giao phối, nếu một cặp tổ hợp gen thích hợp một đột biến vốn là có hại có thể trở thành có lợi . Đột biến gen gây ra những thay đổi trong nucleotide dẫn đến biến đổi m ARN và quá trình tổng hợp protein nên thường gây ra hậu quả có hại, làm giảm khả năng sống của sinh vật. Chẳng hạn như bệnh u mô đệm đường tiêu hóa. Đột biến gen KIT trong u mô đệm đường tiêu hóa, đột biến mất 6 nucleotide từ vị trí 1669 tới 1674 trong cADN (c.1669_1674del) hoặc đột biến mất 2 amino acid trong proterin (từ Tryptophan 557 tới Lysine 558 (p.W557_K558del). 14 Hình 1.4 Đột biến gen KIT trong u mô đệm đƣờng tiêu hóa Tương tác gen gồm có các tương tác như: Tương tác át chế gen [2,3,5], tương tác cộng gộp và tương tác bổ trợ [2]… 1.1.2.2 Hƣớng nghiên cứu Di truyền học là một môn khoa học nghiên cứu về tính di truyền và biến dị của sinh vật. Tính di truyền được biểu hiện ở sự giống nhau giữa con cái với cha mẹ. Tính biến dị biểu hiện sự sai khác giữa cha mẹ và con cái cũng như giữa các con cái với nhau. Mặc dù, quá trình xác định bản đồ gen dựa trên phương pháp di truyền Mendel đã có những bước tiến lớn, tuy nhiên những gen cơ bản tiềm ẩn gây lên các căn bệnh phức tạp vẫn chưa được biết đến. Gen của loài người có những biến thể di truyền khác nhau và điểm đó làm nên sự khác nhau giữa người này với người kia. Dự án gen người đã chỉ ra rằng bộ gen của hai người bất kì giống nhau 99,9%. Giờ thì các nhà khoa học đã hoàn tất một bản đồ chi tiết hơn (còn gọi là HapMap), chỉ ra các biến thể gen để giải thích 0,1% khác biệt. Phần lớn trong số những biến thể đó là hàng triệu các điểm đa hình tại những vị trí nucleotide nhất định đã làm thay đổi mã di truyền. Những điểm khác biệt đó được gọi là những đa hình đơn nucleotide (single nucleotide polymorphisms, SNPs) hiện đang được Dự án quốc tế HapMap tiến hành thống kê một cách hệ thống. Các nhà khoa học tin rằng SNP bản đồ sẽ giúp họ có nhiều gen liên quan với các bệnh phức tạp như: Ung thư, bệnh tiểu đường, bệnh mạch máu, và một số hình thức bệnh tâm thần. Một vài nhóm làm việc để tìm SNPs và cuối cùng tạo ra SNP bản đồ hệ gen của con người. Trong số đó là Mỹ Human Genome Project (HGP) và một dự án song song cũng được thực hiện bởi một công ty tư nhân tên là Celera Genomics. Gần đây có những nghiên cứu xác định tương tác át chế trong các căn bệnh phức tạp như bệnh ung thư, bệnh tiểu đường, bệnh tai nhĩ[4,17,21]. Từ việc tìm, khám phá tương tác gen để từ đó tìm ra được các gen là nguyên nhân gây lên các căn bệnh. Dựa vào đó các nhà nghiên cứu tìm ra các hướng để điều 15 trị bệnh một cách thích hợp và hiệu quả nhất, chẳng hạn như hướng: Tác động gen để trị bệnh, đây cũng là một hướng đi mới trong tương lai[30]. 1.2 Bài toán phát hiện tƣơng tác gen 1.2.1 Mục đích vì sao cần phát hiện tƣơng tác gen Gen là nhân tố di truyền nằm trên nhiễm sắc thể trong tế bào quy định một hay một số tính trạng nào đó của cơ thể. Đột biến gen là những biến đổi trong cấu trúc của gen xảy ra ở cấp độ phân tử tại một điểm nào đó trên phân tử DNA và có liên quan đến sự thay đổi về số lượng, thành phần, trật tự các cặp nucleotide trong gen. Sự thay đổi trật tự các nucleotide đã làm thay đổi mã di truyền. Vật liệu di truyền của mỗi người có một mô hình SNP độc đáo được tạo thành nhiều biến thể di truyền khác nhau. Các nhà nghiên cứu đã tìm thấy rằng, hầu hết các SNPs không chịu trách nhiệm cho một bệnh tật nào. Thay vào đó, nó như là các dấu hiệu sinh học để xác định chính xác một căn bệnh trên bản đồ gen của con người. Bởi vì, những SNPs thường nằm gần một gen được tìm thấy có liên quan đến một căn bệnh nào đó. Thỉnh thoảng một SNPs thực sự có thể gây ra một căn bệnh, và do đó có thể được sử dụng để tìm kiếm và cô lập các gen gây bệnh. SNP yếu khi đứng một mình nhưng có tác động mạnh khi xảy ra tương tác. Chẳng hạn, tương tác gen được áp dụng trong nghiên cứu bệnh thoái hóa điểm vàng và được kí hiệu là AMD (Age-related Macular Degeneration)[14]. Các nhà nghiên cứu phân tích dựa trên việc phát hiện ra các tương tác gen trội và đưa ra được gen CFH bị đột biến trong hệ miễn dịch, đây là một loại protein đóng vai trò điều tiết phản ứng viêm nhiễm. Người mắc bệnh AMD có nguy cơ bị biến đổi gen CFH cao gấp 4 lần so với người bình thường. Các nhà nghiên cứu vẫn đang tiến hành nghiên cứu tiếp để đưa ra những chất gây bệnh khác để từ đó có những hướng điều trị thích hợp và hiệu quả. 1.2.2 Khái quát quá trình nghiên cứu tìm tƣơng tác gen Nghiên cứu về một bệnh chứng liên quan tới cá thể bị bệnh và không bệnh. Trong nghiên cứu về cá thể bị bệnh và không bệnh, mục đích để tìm hiểu mối quan hệ giữa một yếu tố nguy cơ với một bệnh cụ thể. Thứ nhất: Chọn một nhóm đối tượng đã bị bệnh (hay còn gọi là case) mà nhà nghiên cứu muốn tìm hiểu. Thứ hai: Chọn một nhóm đối chứng không bị mắc bệnh (hay còn gọi là control), nhưng những người trong nhóm này phải có những điều kiện nhất định: Cùng độ tuổi, cùng giới tính và các yếu tố lâm sàng khác với cùng đối tượng… Thứ ba: Qua lấy mẫu nghiên cứu và phân tích, các nhà nghiên cứu đưa ra bộ dữ liệu SNP được xác định kiểu gen của nhóm cá thể bị bệnh và không bị bệnh. 16 Thứ tư: Tiến hành phân tích bộ dữ liệu SNP trên để tìm ra vị trí các SNP tương tác với nhau. Ví dụ nghiên cứu về một bệnh chứng sốt rét có ảnh hưởng tới người Viêt Nam[25]. Bệnh viện Bệnh Nhiệt đới TP. Hồ Chí Minh và Đơn vị Nghiên cứu Lâm sàng Đại học Oxford tại Việt Nam. Tiến hành nghiên cứu với trên 1030 trường hợp sốt rét nặng và 2840 trường hợp đối chứng ở Việt Nam. Lấy mẫu các đối tượng đối chứng dựa trên các trường hợp: Độ tuổi, giới tính, chủng tộc và địa bàn cư trú. Kết quả đưa ra nghiên cứu các SNP ứng viên sốt rét liên quan tới sốt rét nặng ở Việt Nam xác định được kiểu gen của 67 SNP. Tiến hành nghiên cứu trên bộ dữ liệu SNP (tùy từng yêu cầu nghiên cứu của mỗi bài toán). 1.2.3 Phát biểu bài toán tƣơng tác gen 1.2.3.1 Phát biểu bài toán Để tạo ra những thử nghiệm di truyền, những gen có ảnh hưởng đến bệnh đã được xác định bởi các nhà khoa học bằng cách làm cuộc xét nghiệm các cá thể bị ảnh hưởng tới căn bệnh nào đó qua quá trình phân tích DNA đưa ra các mẫu SNP. Tương tự, các nhà nghiên cứu so sánh mô hình với các mẫu thu được bằng cách phân tích DNA từ các cá thể không bị ảnh hưởng tới căn bệnh này. Cuối cùng, thu được hồ sơ các SNP khả nghi liên quan tới bệnh. Sau đó chỉ là vấn đề thời gian, các nhà nghiên cứu có thể xác định một người nhạy cảm với một căn bệnh nào đó bằng cách phân tích các mẫu DNA của họ đưa ra mô hình cụ thể SNP. Bài toán được phát biểu như sau: Có 𝑛 cá thể, cá thể thứ 𝑖 được mô tả bởi 𝑚 vị trí: 𝑆𝑖1 , … , 𝑆𝑖𝑗 , … , 𝑆𝑖𝑚 (trong đó 𝑆𝑖𝑗 =0|1|2, mô tả SNP) và giá trị 𝐶𝑖 =0|1 (mô tả cá thể không bị bệnh hoặc bị bệnh). Yêu cầu của bài toán tìm ra k vị trí tương tác với nhau liên quan đến bệnh dựa trên hàm kiểm định thống kê Chi-square (X2) và mức ý nghĩa thống kê P-Value. Trong nghiên cứu GWA (Genome Wide Apporoach ), người ta quy định các chữ cái hoa: A,B,C… đại diện alens trội và chữ cái thường: a,b,c… đại diện cho alens lặn. Mỗi một SNP có 3 kiểu gen: AA, Aa, aa được kí hiệu tương ứng bởi các giá trị 1,2,0[23]. Nghiên cứu GWA đó là cách tiếp cận cả bộ gen để nhận diện các gen bệnh trên mô hình người với những điều kiện nhiễm khuẩn tự nhiên có thể có tiềm năng phát hiện các gen mã hóa nhưng đáp ứng cho việc miễn dịch quan trọng còn chưa biết. Vì vậy các nghiên cứu GWA quyết định trong việc xác định sự góp phần của tất cả các gen đã biết và chưa biết trong việc dính líu liên quan đến bệnh. 17 1.2.3.2 Mô hình hóa bài toán Input: Đầu vào của bài toán gồm có n cá thể và m SNPs được biểu diễn dưới dạng bảng ma trận S[n+1][m+1]. Trong đó: + S[0][j]: Chứa số thứ tự của các SNPs trong tập dữ liệu dataSNPS và được kí hiệu: 𝑟𝑠𝑗, với j=0,..,m-1 + S[0][m]: Chứa thông tin về cá thể được kí hiệu: class. + S[i][j]=0|1|2, với i=1,..,n và j=0,..,m-1 +S[i][m]= 0: cá thể không mắc bệnh 1: cá thể mắc bệnh với i=1,..,n Ví dụ: Đầu vào của bài toán được biểu diễn dưới dạng bảng ma trận như sau: Bảng 1.1 Minh họa đầu vào của bài toán rs0 rs1 … rsj … rsm-1 class 2 2 … 1 … 0 1 1 0 … 2 … 2 0 … … … Sij … … … 1 1 … 2 … 0 0 0 2 … 0 … 1 1 Output: Là một tập các bộ, mỗi bộ gồm k vị trí tương tác với nhau liên quan đến bệnh nhất, được xác định dựa theo hàm kiểm định thống kê Chi-square (X2) và mức ý nghĩa thống kê 𝑃 − 𝑉𝑎𝑙𝑢𝑒. Đầu ra của bài toán được biểu diễn trong bảng 1.2: Bảng 1.2 Minh họa đầu ra của bài toán Loci Chi-square Pvalue 𝑆𝑗 1 , 𝑆𝑗 2 …., 𝑆𝑗 𝑘 X Y … … … Chú ý: Giá trị 𝑃 − 𝑉𝑎𝑙𝑢𝑒 khác so với giá trị 𝑃𝑣𝑎𝑙𝑢𝑒. 𝑃 − 𝑉𝑎𝑙𝑢𝑒 là một ngưỡng nhận một giá trị cụ thể đã được xác định trước hay được gọi là mức ý nghĩa thống kê, 𝑃𝑣𝑎𝑙𝑢𝑒 được xác định sau khi tính được hàm X2. Lựa chọn ra các bộ gồm 𝑘 𝑣ị 𝑡𝑟í với hàm kiểm định thống kê X2 có giá trị lớn nhất và phải thỏa mãn điều kiện 𝑃𝑣𝑎𝑙𝑢𝑒 < 𝑃 − 𝑉𝑎𝑙𝑢𝑒. 18 CHƢƠNG II GIỚI THIỆU VỀ THUẬT TOÁN ANT COLONY OPTIMIZATION (ACO) 2.1 Lịch sử ra đời của thuật toán ACO 2.1.1 ACO ra đời từ việc quan sát hành vi của đàn kiến trong quá trình di chuyển tìm kiếm thức ăn Thuật toán tối ưu hóa đàn kiến (ACO) được xem là một trong những phương pháp hiệu quả trong vấn đề giải quyết các bài toán tối ưu tổ hợp NP-khó. Trong thực tế và trong các hệ thống thông tin, ta thường có những bài toán thuộc dạng NP-khó chẳng hạn như: Bài toán người chào hàng, bài toán tô màu đồ thị, định tuyến các gói tin trên mạng Internet hay trong các tổng đài điện thoại, bài toán phân bậc hai, bài toán định tuyến xe [6-8,15,18,20]. Thuật toán hệ kiến (Ant System -AS) ACO đầu tiên được đề xuất bởi Dorigo, Maniezo và Colorni giải bài toán người chào hàng (Traveling Salesman ProblemTSP)[11]. Ý tưởng được tác giả lấy dựa trên việc nghiên cứu từ các hành vi của kiến thực, sau cơ sở lý thuyết được nghiên cứu vào năm 1989[13]. Một trong những vấn đề quan tâm là tại sao trong quá trình tìm kiếm thức ăn từ tổ tới nguồn thức ăn của các con kiến chúng lại có khả năng tìm ra đường đi ngắn nhất để đi mặc dù chúng không có khả năng đo độ dài đường đi. Trong quá trình nghiên cứu người ta phát hiện ra đàn kiến tìm đường đi như thế nào. Trên đường đi, mỗi con kiến để lại một vết hóa chất gọi là vết mùi (pheromone trail), chúng có khả năng ứ đọng, bay hơi và có thể nhận biết bởi các con kiến khác. Bằng cách cảm nhận vết mùi, kiến có thể lần đi theo đường mà các con kiến khác khám phá theo phương thức chọn ngẫu nhiên có định hướng theo nồng độ vết mùi. Kiến hoạt động dựa trên ảnh hưởng vết mùi của các con kiến khác chính là ý tưởng thiết kế thuật toán ACO. 2.1.2 Mùi và ý nghĩa vết mùi trên đƣờng đi trong quá trình di chuyển của kiến Các vết mùi chính là phương tiện giao tiếp gián tiếp giữa các con kiến. Đường có nồng độ vết mùi càng cao thì càng có nhiều khả năng được các con kiến chọn, nhờ cách giao tiếp gián tiếp mà đàn kiến sẽ tìm được đường đi ngắn nhất từ tổ tới nguồn thức ăn. Deneubourg và các đồng nghiệp tiến hành thực nghiệm hành vi để lại vết mùi và đi theo vết mùi của kiến từ tổ tới nguồn thức ăn và ngược lại (1989) [13]. Thí nghiệm này là cơ sở lý thuyết và cũng tạo ra ý tưởng về thuật toán ACO mà Dorigo đưa ra sau này. Xem minh họa trong hình 2.1 [10], dựa vào hình ta có thể phân ra làm hai cuộc thực nghiệm.