MỞ ĐẦU Tin sinh học có ứng dụng cao trong cuộc sống, đặc biệt trong lĩnh vực y – dƣợc. 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ử. Tìm kiếm motif trong các chuỗi gene là một trong những bài toán quan trọng nhất của tin sinh học và thuộc loại NP-khó. Các thành phần điều hòa gene (gene regulatory elements) đƣợc gọi là các DNA motif (về sau gọi là motif cho gọn), chúng chứa nhiều thông tin sinh học quan trọng.
Vì vậy việc nhận dạng DNA motif đang là một trong những bài toán quan trọng nhất trong tin sinh học và thuộc loại NP-khó. Chủ yếu, có 2 cách tiếp cận để tìm kiếm motif: các phƣơng pháp thực nghiệm và các phƣơng pháp tính toán. Vì chi phí cao và tốn thời gian nên các phƣơng pháp thực nghiệm ít hiệu quả. Phƣơng pháp tính toán đang đƣợc dùng rộng rãi cho dự đoán motif.
Ngƣời ta đƣa ra nhiều phát biểu cho bài toán tìm kiếm motif, và có nhiều thuật toán nghiên cứu và công bố giải quyết bài toán tìm kiếm motif. Trong luận văn này, tôi trình bày bài toán (ℓ,d) motif. Có nhiều thuật toán đƣa ra để giải quyết bài toán (ℓ,d) motif, các thuật toán này có thể chia thành 2 loại đó là thuật toán chính xác và thuật toán xấp xỉ. Các thuật toán chính xác luôn luôn tìm ra những motif trong những chuỗi DNA đầu vào nhƣng chỉ hiệu quả với các dữ liệu có kích thƣớc nhỏ và thực hiện mất nhiều thời gian.
Các thuật toán xấp xỉ có thể không tìm ra đƣợc tất cả các motif nhƣng nó chạy hiệu quả với các dữ liệu lớn. Luận văn đề xuất giải quyết bài toán (ℓ,d) motif theo thuật toán xấp xỉ, bằng việc đề xuất thuật toán tối ƣu đàn kiến Ant colony optimization (ACO) để giải quyết bài toán (ℓ,d) motif. Đây là thuật toán mới và lần đầu đƣợc đƣa vào để giải bài toán (ℓ,d) motif. Thuật toán đƣợc đặt tên là F-ACOMotif.
Và trong thực nghiệm đã chỉ ra đƣợc thuật toán F-ACOMotif tối ƣu hơn các thuật toán PairMotif+ và MEME về độ chính xác khi tìm ra (ℓ,d) motif. 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 nhƣ sau: Chƣơng 1: Trình bày sơ lƣợc các khái niệm về tin sinh học, bài toán tối ƣu tổ hợp và phát biểu bài toán (ℓ,d) motif. 9 Chƣơng 2: Giới thiệu thuật toán Ant colony optimization (ACO) và một vài thuật toán cập nhật mùi khác nhau trong ACO. Chƣơng 3: Đề xuất thuật toán, đó là thuật toán Ant colony optimization (ACO) để giải quyết bài toán (ℓ,d) motif.
Chƣơng 4: Đƣa ra kết quả thực nghiệm của luận văn, so sánh kết quả của thuật toán ACO với các thuật toán PairMotif+ và thuật toán MEME. 10 CHƢƠNG 1: TIN SINH HỌC VÀ BÀI TOÁN TÌM KIẾM (L,D) MOTIF 1. Tin sinh học 1.1 Giới thiệu về tin sinh học Tin sinh học (Bioinformatics) đƣợc tạo thành bởi cụm từ “Bio” là tƣơng ứng với “Molecular Biology” nghĩa là sinh học phân tử còn “Informatics” thì tƣơng đƣơng với “Computer science” chính là khoa học máy tính. Ngoài ra Computational biology, Computational molecular biology, Biocomputing cũng đồng nghĩa với “Bioinformatics” [1].
Vậy Tin sinh học là gì? Fredj Tekaia Thuộc viện Pasteur đã đƣa ra một định nghĩa về tin sinh học nhƣ sau: “Tin sinh học là sử dụng toán học, thống kê và khoa học máy tính để giải quyết các vấn đề về sinh học với DNA, chuỗi axit amin và các thông tin có liên quan”.2 Khái niệm trong sinh học Mọi cơ thể sống đều đƣợc cấu thành từ một lƣợng rất lớn các tế bào. Mỗi tế bào đều đƣợc cấu tạo gồm hạt nhân, ribôxom và nội bào. Hạt nhân của tế bào chứa các nhiễm sắc thể đặc trƣng cho mỗi tế bào đó. Nhiễm sắc thể lại đƣợc tạo thành bởi các axit nucleic và protein.
Axit nucleic là những đại phân tử có cấu trúc đa phân, đơn phân của nó là các nucleotide. Axit nucleic đƣợc chia làm 2 loại là DNA (deoxyribonucleic acid) và RNA. Một thành phần rất quan trọng khác của tế bào là protein, đƣợc tạo ra từ các axit amin, là các thành phần thiết yếu của mọi cơ quan và hoạt động hóa học liên quan đến toàn bộ hoạt động của tế bào, chúng đƣợc biểu hiện thành những đặc điểm về cấu tạo và chức năng của tế bào, hay chính là những tính trạng của sinh vật. Giữa protein và DNA có quan hệ chặt chẽ với nhau, cụ thể là mỗi loại protein đều đƣợc xác định bởi một đoạn trên dãy DNA gọi là gen.1: DNA phân tử của sự sống 11 Vào năm 1944, Oswald Avery phát hiện ra DNA là một loại nguyên liệu thô chứa gen.
Bắt nguồn từ phát hiện này, một vài nhóm nghiên cứu đã tập trung nghiên cứu về DNA và các thành phần hóa học cấu thành. DNA là một phân tử đƣợc cấu tạo bởi đƣờng, photphat và bốn nitrogenous bases: adenine, cytosine, guanine và thiamine, đƣợc lần lƣợt viết tắt là A, C, G, và T. Sau này, các nhà khoa học quan niệm rằng bốn nitrogen bases này là các nucleotide là cơ sở của mã di truyền. Vào năm 1953, hai nhà sinh vật học là J.Crick làm việc tại trƣờng đại học Cambridge đã xây dựng thành công mô hình không gian của phân tử DNA(deoxyribonucleic acid), đánh dấu một bƣớc ngoặt quan trọng trong sự phát triển của sinh học phân tử theo mô hình này DNA là một đại phân tử sinh học có cấu trúc nhƣ một chuỗi xoắn kép gồm hai mạch đơn, mỗi mạch đơn là một chuỗi nucleotide.
Mỗi nucleotide gồm nhóm phosphate, đƣờng desoxyribose và một trong bốn thành phần lần lƣợt đƣợc biểu thị bởi các chữ cái A, C, G và T. Hai mạch đơn kết hợp với nhau nhờ các liên kết hydro hình thành giữa các thành phần bổ sung nằm trên hai mạch. A bổ sung cho T, C bổ sung cho G.2: Hình ảnh về RNA RNA (Ribonucleic Acid) là 1 loại acid nucleic (nhƣ DNA), RNA cũng có cấu trúc đa phân mà đơn phân là 4 loại nucleotide, tuy nhiên trong RNA nucleotide loại T (pyrimidine thymine) đƣợc thay thế bằng U (uracil). RNA tồn tại ở dạng chuỗi đơn và đƣợc phân chia làm 3 loại chính dựa trên chức năng của 12 chúng: mRNA (RNA thông tin): là một mạch sao chép nguyên từ một mạch đơn của DNA trong đó T đƣợc thay bằng U và làm nhiệm vụ truyền đạt thông tin cấu trúc protein đƣợc tổng hợp.
rRNA (RNA riboxom): là thành phần cấu tạo nên riboxom. tRNA (RNA vận chuyển): có chức năng vận chuyển amino acid tƣơng ứng đến nơi tổng hợp protein snRNA: có chức năng hỗ trợ việc ghép mã mRNA. gRNA: sử dụng để điều khiển việc thay đổi mRNA. RNA có thể liên kết với một dải đơn của một phân tử DNA, bằng cách thay T bằng U, và các phân tử kiểu này có vai trò quan trọng trong các quá trình sống và công nghệ sinh học [1].3: Cấu trúc Protein Protein là một đại phân tử sinh học đƣợc hình thành từ 1 hay nhiều chuỗi polypeptide sắp xếp theo một thứ tự đặc biệt, thứ tự này đƣợc xác định bởi dãy cơ sở (peptide là một chuỗi nối tiếp nhiều axit amin với số lƣợng ít hơn 30, với số lƣợng axit amin lớn hơn chuỗi đƣợc gọi là polypeptide) đƣợc hình thành từ 20 loại axit amin khác nhau lần lƣợt đƣợc biểu thị bằng 20 kí tự khác nhau trong bảng chữ cái.
Từ “ protein” dùng để chỉ một cấu trúc phức tạp trong không gian chứ không đơn thuần chỉ là một trình tự axit amin. Các nucleotide trong gene mã 13 hóa cho protein. Các protein cần thiết cho cấu trúc, chức năng và điều chỉnh tế bào, mô và tổ chức, mỗi protein có một vai trò đặc biệt. Cấu trúc protein bao gồm 4 mức độ tổ chức: Cấu trúc bậc 1 là trình tự sắp xếp các axit amin trong chuỗi polypeptid, cấu trúc bậc 2 phát sinh từ sự uốn các thành phần của chuỗi polypeptid thành những cấu trúc đều đặn trong không gian ( dạng xoắn (alpha helix) hay lớp mỏng (Beta sheets)).
Cấu trúc bậc 3 quy định sự kết hợp các chuỗi xoắn hay lớp mỏng đó thành hình dạng ba chiều trong không gian. Cấu trúc bậc 4 là sự tổ chức nhiều chuỗi polypeptid thành một phân tử protein.4 Quá trình tổng hợp protein Tổng hợp protein là quá trình tạo ra protein dựa trên thông tin đƣợc mã hóa trong gen ( là các đoạn mã đặc biệt của DNA có chức năng điều khiển cấu trúc và hoạt động của tế bào, là đơn vị chức năng của sự di truyền) gồm ba giai đoạn chính : (1) Transcription (phiên mã) (2) Splipcing (ghép mã) (3) Translation (dịch mã) [1] có thể đƣợc mô tả nhƣ hình dƣới: Hình 1.4: Quá trình tổng hợp Protein [1] 1.5 Một số bài toán trong tin sinh học Việc hỗ trợ của công nghệ thông tin trong nghiên cứu cấu trúc các thành phần, quá trình hoạt động, đặc tính và vai trò của từng loại thành phần cùng liên kết giữa chúng dẫn đến phải giải quyết nhiều bài toán học máy phức tạp, thƣờng là các bài toán tối ƣu tổ hợp NP-khó và có tính bất định. Một số bài toán hiện đang đƣợc quan tâm nghiên cứu là: So sánh tích hợp bộ gene (comparative genome assembly), xây dựng cây phân loài (phylogenetic tree reconstruction), tìm kiếm motif (motif finding), suy diễn haplotype, dự báo hoạt động điều tiết gene, xây dựng ma trận biến đổi axít amin, phân tích chức năng protein dựa trên cấu trúc bậc cao,…. 14 Luận văn sẽ tập trung nghiên cứu “Bài toán tìm kiếm motif sử dụng phƣơng pháp tối ƣu đàn kiến” 1.1 Quá trình điều hòa gen Các vị trí điều hòa trên DNA tƣơng ứng với một chuỗi hợp nhất từ các vùng quy định của mỗi gen.
Chúng ta gọi đó những motif hoặc DNA signals. Vị trí quy định trên mỗi DNA tƣơng ứng với một motif đƣợc gọi là instances của motif đó. Xác định đƣợc các motif và các instance tƣơng ứng của nó có ý nghĩ rất quan trọng, từ đó các nhà nghiên cứu sinh học có thể phát hiện ra các tƣơng tác giữa DNA và protein, điều hòa gen cũng nhƣ sự phát triển và tƣơng tác trong một tế bào.5: Quá trình tổng hợp Protein Motif là những đoạn trình tự có kích thƣớc ngắn, có thể là nucleotide hoặc amino axit và mang ý nghĩa sinh học. Một vài đặc điểm của motif [15]: Motif là những mẫu có kích thƣớc từ 10-25 base và lặp lại nhiều lần qua các chuỗi khác nhau.
Motif là những đoạn trình tự đại diện cho vùng điều hòa của gen. Motif có kích thƣớc nhỏ, cố định, lặp lại rất nhiều lần và thƣờng xuyên.