Các kỹ thuật toán học cho bài toán so sánh đa trình tự

.........................Giới tính : Nam ;/ Nữ … Ngày, tháng, năm sinh : 26/2/1982....................................Nơi sinh : Phú Yên ................... Chuyên ngành : Khoa học Máy tính...................................................................................... Khố : 2005 ......................................................................................................................... 1- TÊN ĐỀ TÀI : ................................................................................................................ CÁC KỸ THUẬT TỐN HỌC CHO BÀI TỐN SO SÁNH ĐA TRÌNH TỰ ........................................................................................................................................... ........................................................................................................................................... 2- NHIỆM VỤ LUẬN VĂN : .............................................................................................. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... 3- NGÀY GIAO NHIỆM VỤ : ........................................................................................... 4- NGÀY HỒN THÀNH NHIỆM VỤ : .......................................................................... 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Nguyễn Văn Minh Mẫn .......................... Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thơng qua. CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MƠN (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) TS. Nguyễn Văn Minh Mẫn TS. Đinh Đức Anh Vũ CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : TS. Nguyễn Văn Minh Mẫn ........................................ Cán bộ chấm nhận xét 1 : ............................................................................................ Cán bộ chấm nhận xét 2 : ............................................................................................ Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . tháng . . . . năm . 2007 . Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang i LỜI CAM ĐOAN Tơi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác như đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do chính tơi thực hiện và chưa cĩ phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này hoặc trường khác. Ngày 05 tháng 11 năm 2007 Phạm Mạnh Hùng Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang ii LỜI CẢM ƠN Tơi xin gởi lời cảm ơn chân thành nhất đến TS. Nguyễn Văn Minh Mẫn, người đã tận tình hướng dẫn, giúp đỡ tơi trong suốt quá trình thực hiện luận văn và tạo điều kiện để tơi cĩ thể hồn thành luận văn này. Xin cảm ơn gia đình và những người bạn đã dành cho tơi tình thương yêu và sự hỗ trợ tốt nhất. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang iii TĨM TẮT LUẬN VĂN So sánh đa trình tự(Multiple Sequence Alignment-MSA) là một trong 10 bài tốn lớn của Sinh tin học(Bioinformatics). MSA đĩng vai trị quan trọng trong Sinh tin học nĩi chung và lĩnh vực tìm kiếm gene (Gene Finding) nĩi riêng. MSA là một bài tốn NP, và hồn tồn chưa cĩ giải pháp trọn vẹn để tìm lời giải tối ưu của bài tốn. Nhiều phương pháp sử dụng heuristic đã được đưa ra để giải quyết bài tốn khi tập dữ liệu đầu vào lớn, các phương pháp này hướng tới việc tìm 1 lời giải cận tối ưu với thời gian tính tốn và bộ nhớ sử dụng chấp nhận được. Progress Algorithm là một phương pháp tốt tiếp cận theo phương thức này. Đề tài này trình bày một giải thuật mới dựa trên Progressive Algorithm. Sử dụng lời giải của bài tốn TSP để mơ tả quá trình so sánh(align) các sequence. Để cung cấp một Progressive Algorithm cĩ chất lượng, giải thuật đã tối ưu bài tốn Pairwise Sequence Alignment(PSA) về độ chính xác và bộ nhớ sử dụng thơng qua giải thuật ”chia để trị” kết hợp với việc sử dụng 3 ma trận đánh giá BLOSUM. Thơng qua quá trình so sánh với CLUSTALW(một chương trình hiện thực Progressive Algorithm được đánh giá là cho kết quả tốt nhất), dựa trên kết quả kiểm thử với tập dữ liệu BAliBASE benchmark và một số nguồn dữ liệu từ NCBI(National Center for Biotechnology Information), chương trình hiện thực giải thuật đã cung cấp một lời giải cĩ độ chính xác khá cao, tiết kiệm bộ nhớ và cĩ thời gian tính tốn chấp nhận được. Từ khố: Algorithm, Sequence Alignment, Multiple Sequence Alignment, MSA, Pairwise Sequence Alignment, PSA, Progressive Algorithm, Dynamic Programming, Traveling Salesman Problem, TSP, CLUSTALW, BLOSUM, BAliBASE. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang iv MỤC LỤC LỜI CAM ĐOAN ...........................................................................................................i LỜI CẢM ƠN ............................................................................................................... ii TĨM TẮT LUẬN VĂN .............................................................................................. iii DANH MỤC HÌNH ..................................................................................................... vi DANH MỤC BẢNG .................................................................................................. viii Chương 1. GIỚI THIỆU...............................................................................................1 1.1. Giới thiệu ..............................................................................................................1 1.2. Kết cấu của luận văn ...........................................................................................4 Chương 2. TỔNG QUAN VỀ KHÁI NIỆM SO SÁNH TRÌNH TỰ (SEQUENCE ALIGNMENT) ...........................................................................................6 2.1. So sánh trình tự....................................................................................................6 2.1.1. Định nghĩa So sánh trình tự(Sequence Alignment) ....................................................6 2.1.2. Phân loại .....................................................................................................................7 2.1.3. So sánh 2 trình tự (Pairwise Sequence Alignment-PSA)............................................8 2.1.4. So sánh nhiều trình tự (Multiple Sequence Alignment-MSA)....................................9 2.2. Các khái niệm khác ...........................................................................................10 2.2.1. Ma trận đánh giá(Scoring Matrix) ............................................................................12 2.2.2. Gap............................................................................................................................14 2.2.3. Phương pháp đánh giá(Scoring Method) ..................................................................15 2.3. Các phương pháp giải quyết bài tốn so sánh trình tự ..................................18 2.3.1. Phương pháp Quy hoạch động(Dynamic Programming)..........................................19 2.3.2. Sử dụng các thiết bị phần cứng.................................................................................20 2.3.3. Phương pháp tìm kiếm cục bộ(Local Search)...........................................................21 2.3.4. Sử dụng giải thuật Di truyền(Genetic Algorithm) ....................................................21 2.3.5. Sử dụng Mơ hình Markov ẩn(Hidden Markov Model-HMM). ................................21 Chương 3. CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP THỰC HIỆN .................24 3.1. Giới thiệu về Dynamic Programming ..............................................................24 3.2. Bài tốn PSA và cách giải quyết bằng kỹ thuật quy hoạch động ..................24 3.2.1. Giải thuật quy hoạch động cho bài tốn PSA ...........................................................25 3.2.2. Giải thuật Gotoh........................................................................................................28 3.2.3. Giải thuật cải tiến khơng gian nhớ ...........................................................................29 3.3. Giải thuật tính tốn phép Alignment tối ưu cho bài tốn Multiple Alignment sử dụng kỹ thuật dynamic programming .........................................................................32 3.3.1. Giải thuật Center Star Alignment Algorithm............................................................33 3.3.2. Phương pháp Progressive Algorithm giải quyết bài tốn MSA................................37 3.3.3. Feng-Doolittle Algorithm .........................................................................................38 Chương 4. THIẾT KẾ GIẢI THUẬT VÀ HIỆN THỰC PHƯƠNG PHÁP GIẢI QUYẾT BÀI TỐN MSA .......................................................................42 4.1. Giải thuật sử dụng cho bài tốn PSA...............................................................42 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang v 4.1.1. Giải thuật tính tốn dựa theo kỹ thuật chia để trị......................................................43 4.2. Giải thuật hiện thực cho bài tốn MSA ...........................................................49 4.2.1. Bài tốn TSP(Travelling Salesman Problem-Bài tốn người bán hàng). .................50 4.2.2. Giải thuật 1A.............................................................................................................51 4.2.3. Giải thuật 1B(Giải thuật cải tiến gom nhĩm nhỏ nhất).............................................55 4.3. Giải thuật di truyền và bài tốn TSP. ..............................................................57 4.3.1. Đặc điểm giải thuật di truyền....................................................................................57 4.3.2. Cấu trúc thuật giải di truyền tổng quát......................................................................59 4.4. Phần hiện thực giải thuật và chương trình: ....................................................60 Chương 5. KẾT QUẢ NHẬN XÉT............................................................................66 5.1. Một số kết quả chạy chương trình. ..................................................................66 5.2. BAliBASE (Benchmark Alignment Database)................................................68 5.3. So sánh kết quả ..................................................................................................69 5.3.1. Giới thiệu về các chương trình được sử dụng...........................................................70 5.3.2. So sánh độ chính xác của kết quả .............................................................................70 5.3.3. So sánh về mặt thời gian chạy, bộ nhớ .....................................................................77 Chương 6. KẾT LUẬN ...............................................................................................78 TÀI LIỆU THAM KHẢO...........................................................................................80 Phụ lục 1. Bảng đối chiếu Thuật ngữ Anh - Việt......................................................83 Phụ lục 2. Từ viết tắt ...................................................................................................87 Tham khảo Chỉ mục....................................................................................................88 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang vi DANH MỤC HÌNH Hình 2.1 Ví dụ về PSA............................................................................................................................7 Hình 2.2 Ví dụ về so sánh trình tự theo hướng tồn cục..........................................................................8 Hình 2.3 Ví dụ về so sánh trình tự theo hướng cục bộ.............................................................................8 Hình 2.4 Cấu trúc 1 PSA..........................................................................................................................8 Hình 2.5 Giới thiệu 1 MSA......................................................................................................................9 Hình 2.6 Giới thiệu các khái niệm của MSA .........................................................................................10 Hình 2.7 Quá trình biến đổi của 2 sequence...........................................................................................10 Hình 2.8 Ví dụ về các phép thay thế gap ..............................................................................................11 Hình 2.9 Ví dụ về Gap. ..........................................................................................................................15 Hình 2.10 Mối tương quan giữa các chương trình hiện thực cho các phương pháp. .............................19 Hình 2.11 Phương pháp tính tốn chính xác bằng dynamic programming ............................................20 Hình 2.12 Mơ hình Markov cho bài tốn MSA. ....................................................................................22 Hình 3.1 Phương pháp quy hoạch động cho bài tốn PSA ....................................................................25 Hình 3.2 Các ma trận S, D, I cho 2 chuỗi AGTAC and AAG. .............................................................31 Hình 3.3 Minh hoạ quá trình tìm 1 MSA tối ưu.....................................................................................33 Hình 3.4 Mơ hình tiến hố hình sao .......................................................................................................34 Hình 3.5 Minh họa Center Star Algorithm.............................................................................................35 Hình 3.6 Hình minh hoạ cho Progressive Algorithm. ............................................................................37 Hình 3.7 Minh họa Feng-Doolittle Algorithm .......................................................................................39 Hình 3.8 Ví dụ thực thi Feng-Doolittle Algorithm ................................................................................39 Hình 4.1 Mơ hình quá trình thực hiện giải thuật PSA............................................................................43 Hình 4.2 Quá trình xây dựng ma trận của thuật giải cho bài tốn PSA .................................................48 Hình 4.3 Quá trình align của Center Star Algorithm và phiên bản cải tiến ...........................................50 Hình 4.4 Bài tốn TSP. ..........................................................................................................................50 Hình 4.5 Kết quả bài tốn TSP...............................................................................................................51 Hình 4.6 Lưu đồ thuật giải 1A ...............................................................................................................52 Hình 4.7 Lưu đồ thuật giải 1B................................................................................................................55 Hình 4.8 Cấu trúc chương trình hiện thực..............................................................................................61 Hình 4.9 Module PSA ............................................................................................................................61 Hình 4.10 Sơ đồ các khối chức năng của Module MSA. .......................................................................62 Hình 4.11 Sơ đồ các khối chức năng của module TSP. .........................................................................63 Hình 5.1 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và MULTAL ......................72 Hình 5.2 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và HMMT...........................74 Hình 5.3 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và HMMT...........................75 Hình 5.4 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW, SAGA................................75 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang vii Hình 5.5 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW, SAGA................................76 Hình 5.6 So sánh thời gian thực thi của MSAPR và CLUSTALW .......................................................77 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang viii DANH MỤC BẢNG Bảng 2.1Ma trận BLOSUM62 lưu trữ hàm đánh giá độ tương đồng của tập 23 amino acid.................12 Bảng 2.2 Một phần ma trận Identity ......................................................................................................13 Bảng 3.1 Bảng kết quả giải thuật quy hoạch động cho bài tốn PSA ....................................................26 Bảng 4.1 Định dạng của file dữ liệu đầu vào .........................................................................................63 Bảng 4.2 Định dạng của file dữ liệu đầu ra............................................................................................64 Bảng 4.3 Định dạng file dữ liệu đầu ra theo chuẩn MSF.......................................................................64 Bảng 4.4 Bảng tĩm tắt các lớp của chương trình. ..................................................................................65 Bảng 5.1 TAT Protein HIV1..................................................................................................................66 Bảng 5.2 Kết quả Alignment của MSAPR và CLUSTALW với TAT HIV1 ........................................67 Bảng 5.3 Kết quả chạy chương trình với Nhĩm 1 cĩ chiều dài nhỏ ......................................................71 Bảng 5.4 Kết quả chạy chương trình với Nhĩm 1 cĩ chiều dài trung bình............................................71 Bảng 5.5 Kết quả chạy chương trình với Nhĩm 1 cĩ chiều dài lớn .......................................................72 Bảng 5.6 Kết quả chạy của các chương trình với các sequence của nhĩm 2. ........................................73 Bảng 5.7 Kết quả chạy của các chương trình với các sequence của nhĩm 3. ........................................74 Bảng 5.8 Kết quả chạy của các chương trình với các sequence của nhĩm 4 .........................................75 Bảng 5.9 Kết quả chạy của các chương trình với các sequence của nhĩm 5 .........................................76 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 1 Chương 1. GIỚI THIỆU 1.1. Giới thiệu Cùng với sự phát triển mang tính đột phá của Khoa học kỹ thuật, trong vài thập kỷ qua, sinh học phân tử đã cĩ nhiều bước phát triển mạnh mẽ, một loạt các cơng cụ ứng dụng sinh học ra đời gĩp phần thúc đẩy quá trình giải mã một số lượng lớn trình tự bộ gen ở nhiều lồi sinh vật. Cho đến nay, nhiều bộ gen vi khuẩn và các sinh vật bậc cao đã được giải mã gần như hồn tồn. Dự án về bộ gen người được thành lập (1997), và quá trình giải trình tự tất cả 24 cặp nhiễm sắc thể của bộ gen người cũng đã hồn thành từ cuối năm 2000, cũng như đã giải được khoảng 90% bộ gen người(2001). Lượng thơng tin sinh học ngày càng trở nên phong phú và đa dạng. Ðể cĩ thể xử lý và ứng dụng khối lượng thơng tin đồ sộ như vậy , ngành Sinh tin học(hay Bioinformatics) ra đời, đĩ là sự kết hợp giữa cơng nghệ thơng tin và sinh học, một cách đơn giản sinh tin học giải quyết các vấn đề của sinh học bằng cách sử dụng các kỹ thuật của khoa học máy tính. Các lĩnh vực lớn đang được Sinh tin học giải quyết hiện nay: ƒ Genomic: nghiên cứu cấu trúc và chức năng của gene. ƒ Proteinomics: Phân tích một tỉ lệ lớn các protein của một sinh vật ƒ Pharmacogenomics: phát triển các loại thuốc mới nhắm đến một căn bệnh xác định ƒ MicroArray: nghiên cứu về DNA chip, protein chip. Mục tiêu hàng đầu của sinh tin học gắn liền với quá trình phân tích các thơng tin sinh học. Điều này được thể hiện qua các nghiên cứu về: ƒ Tìm kiếm các gene trên các trình tự DNA ở các sinh vật khác nhau. ƒ Phát triển các phương pháp nhằm dự đốn các trình tự RNA, cấu trúc và chức năng của các protein mới được phát hiện. ƒ Tập hợp các trình tự cĩ sự tương đồng cao để đưa ra mơ hình protein. ƒ So sánh các trình tự protein tương đồng và thành lập cây phả hệ mơ tả mối quan hệ tiến hĩa Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 2 Trong lĩnh vực nghiên cứu phân tích cấu trúc và chức năng của gene và protein, phân tích trình tự(chuỗi DNA, protein) đĩng vai trị quan trọng. Để đơn giản cho việc nghiên cứu, trình tự DNA, protein sẽ được tuần tự hĩa và nghiên cứu dưới dạng chuỗi các ký tự. Thơng thường khi một gene được phát hiện, một trong những yêu cầu quan trọng là làm thế nào xác định được chức năng của gene này, yêu cầu tương tự cũng được đặt ra khi phát hiện ra protein mới. Một phương pháp tiếp cận phổ biến đĩ là chúng ta sẽ so sánh, đánh giá sự giống nhau(tương đồng) của chuỗi DNA, protein này với những chuỗi DNA, protein đã biết, từ đĩ cĩ thể đưa ra dự đốn về chức năng cũng như cấu trúc của những gene mới phát hiện(Sequence Alignment). Quá trình tiến hĩa của lồi người là một quá trình biến đổi đa dạng, từ một gene(chuỗi DNA) tổ tiên dưới tác động của quá trình tiến hĩa đã biến đổi tạo nên những khác biệt so với gene gốc ban đầu. Do đĩ việc nhận định sự giống nhau của các đoạn gene, trình tự là một vấn đề lớn của sinh tin học. Vấn đề được đặt ra (trong phân tích trình tự) đĩ là làm thế nào để cĩ được phép so sánh tốt cho các trình tự DNA, khi mà số lượng tế bào trong cơ thể là khoảng 1014 và mỗi tế bào mang khoảng 3.109 ký tự trong đoạn DNA của chúng. Bài tốn so sánh 2 trình tự(Pairwise Sequence Alignment-PSA) đã được giải quyết trọn vẹn bằng nhiều phương pháp khác nhau, đồng thời với việc giải quyết bài tốn này, xuất hiện nhu cầu về việc so sánh nhiều trình tự, để so sánh nhiều đoạn gene hoặc tìm ra một phần tử đại diện cho một tập các gene nhằm đáp ứng nhu cầu ngày càng lớn của việc tìm kiếm dự đốn cấu trúc của các gene, protein, khi kho dữ liệu sinh học được tập hợp ngày càng lớn. Bài tốn so sánh nhiều trình tự được đặt ra như vấn đề tất yếu. Khơng như bài tốn so sánh 2 trình tự, bài tốn so sánh nhiều trình tự(Multiple Sequence Alignment-MSA) là một bài tốn NP mở, cho đến hiện tại (2007) vẫn chưa cĩ một giải pháp nào cĩ thể cung cấp một lời giải trọn vẹn cho bài tốn, các lời giải thường tập trung vào việc tìm ra phép so sánh “gần” tốt nhất, và mỗi phương pháp tiếp cận sẽ chỉ cho những lời giải thực sự tốt tùy từng yêu cầu tiếp cận và bài tốn cụ thể. Progressive Algorithm là một hướng giải quyết tốt cho bài tốn so sánh nhiều trình tự. Đây là phương pháp kết hợp Qui hoạch động(Dynamic Programming) với heuristic. Phương pháp này sẽ tăng tốc độ tính tốn, giảm độ phức tạp của giải thuật, cĩ thể áp dụng cho các cơ sở dữ liệu gene lớn, phục vụ cho các dự án giải mã gene của các sinh vật bậc cao. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 3 Từ khi được giới thiệu cho đến hiện nay, bài tốn MSA đã và vẫn đang là một thách thức cho các nhà khoa học. Nghiên cứu và tìm ra một giải pháp cho bài tốn vẫn là động lực thúc đẩy nhiều cơng trình khoa học về bài tốn này. Xuất phát từ những đặc điểm của bài tốn MSA đề tài này cố gắng tập trung vào giải quyết một số vấn đề sau: ƒ Khảo sát tổng quát các đặc điểm của bài tốn MSA, các phương pháp giải quyết bài tốn. ƒ Nghiên cứu về phương pháp dynamic programming, dynamic programming kết hợp với heuristic, Progressive Algorithm. ƒ Đề xuất một phương pháp giải quyết bài tốn dựa trên Progressive Algorithm. ƒ Xây dựng chương trình hiện thực giải thuật được đề xuất và kiểm thử trên tập dữ liệu thực tế được lấy từ tổ chức NCBI(National Center for Biotechnology Information), và BAliBASE benchmark. Với những mục tiêu này đề tài đã thu được một số kết quả: ƒ Cung cấp cái nhìn tổng quan nhất về so sánh trình tự nĩi chung và bài tốn MSA nĩi riêng. ƒ Phân loại các phương pháp giải quyết bài tốn MSA, phân tích các ưu điểm và nhược điểm của từng phương pháp. ƒ Xây dựng giải thuật giải quyết bài tốn MSA dựa trên việc cải thiện, tối ưu hố bài tốn PSA về độ chính xác cũng như bộ nhớ sử dụng, thơng qua việc sử dụng 3 ma trận đánh giá BLOSUM, từ kết quả này của bài tốn PSA sử dụng Progressive Algorithm kết hợp với lời giải của bài tốn TSP để thực hiện quá trình so sánh nhiều trình tự, tìm ra lời giải cận tối ưu. ƒ Xây dựng thành cơng chương trình hiện thực giải thuật, cho phép tìm lời giải cho bài tốn MSA với độ chính xác khá cao dựa trên kết quả kiểm thử trên các mẫu dữ liệu thực tế BAliBase benchmark và NCBI. Chương trình Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 4 cho phép tiết kiệm bộ nhớ sử dụng, cũng như thời gian tính tốn chấp nhận được. 1.2. Kết cấu của luận văn Luận văn bao gồm 6 chương. Chuơng 1. GIỚI THIỆU Chương này trình bày về bối cảnh, mục tiêu cũng như kết quả thu được của luận văn. Chương 2. TỔNG QUAN VỀ KHÁI NIỆM SO SÁNH TRÌNH TỰ Chương này trình bày tổng quát về khái niệm so sánh trình tự, bài tốn PSA, MSA, các phương pháp đánh giá chất lượng của MSA, các phương pháp giải quyết bài tốn MSA. Chương 3. CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP THỰC HIỆN Chương này giới thiệu chung về phương pháp quy hoạch động(dynamic programming). Giới thiệu về phương pháp quy hoạch động giải quyết bài tốn PSA, giải thuật tính giá trị PSA cải tiến về mặt bộ nhớ sử dụng. Phần tiếp theo của chương này trình bày về cách tiếp cận bài tốn MSA hướng đến bài tốn chính xác hồn tồn bằng quy hoạch động thuần tuý, những khĩ khăn khi tiếp cận theo phương pháp này, giới thiệu một cách giải quyết bài tốn MSA theo hướng gần đúng dựa trên kỹ thuật quy hoạch động kết hợp heuristic: Center Star Algorithm . Phần cuối chương này trình bày về 3 điểm chính, bao gồm giới thiệu Progressive Algorithm tổng quát, Progressive Algorithm phổ biến nhất, giải thuật Feng-Doolittle(Feng-Doolittle Algorithm) và một số chương trình hiện thực Progressive Algorithm trong thực tế. Chương 4. THIẾT KẾ GIẢI THUẬT VÀ HIỆN THỰC PHƯƠNG PHÁP GIẢI QUYẾT BÀI TỐN MSA Đây là chương dài nhất và cũng là chương giới thiệu những giải pháp mới của đề tài. Chương này trình bày về cách tiếp cận của luận văn để xây dựng giải thuật giải quyết bài tốn MSA. Đầu chương giới thiệu về giải thuật tối ưu hố tìm lời giải bài tốn PSA dựa trên việc sử dụng kết hợp giải thuật tính giá trị PSA trình bày ở chương Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 5 3 và kỹ thuật chia để trị để tìm lời giải cho bài tốn PSA. Phần này giới thiệu thêm việc sử dụng song song 3 ma trận BLOSUM làm hàm đánh giá để cải tiến độ chính xác, phù hợp với thực tế lời giải của bài tốn PSA. Tiếp theo chương này đưa ra một giải pháp mới giải quyết bài tốn MSA bằng cách kết hợp sử dụng giải thuật cho bài tốn PSA vừa thu được, và giải thuật Feng-Doolittle để mơ tả cách thức align các nhĩm chuỗi trình tự(sequence) với nhau. Sử dụng kết quả bài tốn TSP để tìm ra thứ tự align các nhĩm sequence , lựa chọn điểm bắt đầu thực hiện quá trình align các sequence thơng qua cách thức chọn điểm trung tâm của Center Star Algorithm. Sau nữa, chương này sẽ trình bày 1 cải tiến của giải thuật mới vừa nêu, nhằm nâng cao chất lượng của MSA bằng kỹ thuật gom nhĩm theo khoảng cách ngắn nhất dựa trên thứ tự align thu được từ bài tốn TSP. Gần cuối chương sẽ giới thiệu về phương pháp giải quyết bài tốn TSP bằng giải thuật di truyền(Genetic Algorithm-GA), và cuối cùng sẽ giới thiệu về các module của chương trình hiện thực giải thuật vừa nêu. Chương 5. KẾT QUẢ, NHẬN XÉT Chương này giới thiệu về kết quả của chương trình hiện thực. Đánh giá kết quả này, so sánh với một số chương trình giải quyết bài tốn MSA. Chương 6.KẾT LUẬN Chương này đề cập lại những việc đã thực hiện được của đề tài. Nêu lên hướng mở rộng và phát triển tiếp theo cho đề tài. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 6 Chương 2. TỔNG QUAN VỀ KHÁI NIỆM SO SÁNH TRÌNH TỰ (SEQUENCE ALIGNMENT) 2.1. So sánh trình tự Như đã giới thiệu Gene Finding Problem là một hướng phát triển quan trọng của sinh tin học, Gene Finding dựa vào quá trình phân tích trình tự để cĩ thể đưa ra được những kết quả. Một số các mục tiêu của quá trình phân tích trình tự: ƒ Xác định gene. ƒ Xác định chức năng của từng gene. Chúng ta giả thiết rằng các trình tự cĩ cấu trúc tương tự nhau thì sẽ cĩ chức năng tương tự nhau, do đĩ ta cĩ thể tìm kiếm chức năng của một gene thơng qua việc so sánh mức độ giống nhau của nĩ với một gene khác cĩ chức năng đã được xác định. ƒ Xác định sự lặp lại của các trình tự ƒ Xác định protein dựa trên quy tắc sắp đặt của các biểu thức gene. ƒ Xác định các vùng chức năng khác nhau của DNA… Trong quá trình phân tích trình tự thì khái niệm so sánh trình tự đĩng vai trị quan trọng. Đây là nền tảng cơ bản cho việc phân tích. So sánh trình tự sẽ giúp cho quá trình dự báo sự giống nhau về chức năng của các t._.rình tự, dự báo cấu trúc bậc 3 của DNA, protein. Trong việc tìm hiểu một gene mới, chúng ta thường quan tâm đến việc xác định những đặc điểm để phân biệt gene đồng thời đưa ra những giả thuyết về chức năng của gene. Việc đưa ra những giả thuyết về chức năng của gene thường dựa vào những giải thuật đánh giá sự giống nhau, tương đồng giữa các trình tự. 2.1.1. Định nghĩa So sánh trình tự(Sequence Alignment) So sánh trình tự(một số tài liệu gọi là phép giĩng hàng, giĩng cột) là quá trình nghiên cứu sự giống nhau giữa các chuỗi trình tự(sequence), đo lường sự giống nhau giữa các trình tự. Là cách thức so sánh giữa 2 hay nhiều trình tự dựa trên việc so sánh một chuỗi các thành phần(ký tự) của trình tự để tìm ra những điểm tương đồng, giống nhau giữa các trình tự. Các trình tự được đề cập trong phần nghiên cứu này là các các chuỗi trình tự DNA, RNA hoặc các trình tự amino acid( protein). Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 7 Xét 2 chuỗi: A C G C T G và C A T G T. Chúng ta sẽ đo lường sự giống nhau giữa 2 chuỗi này. Bên dưới là một ví dụ về một trong những khả năng alignment của 2 chuỗi trên. Tiêu chí để đánh giá sự giống nhau sẽ dựa trên một hàm đánh giá (scoring function). Hình 2.1 Ví dụ về PSA Ký tự “–“ được gọi là 1 gap, gap thể hiện cho ý nghĩa trong sinh học đĩ là một phần của trình tự đã bị mất đi do, các hành vi của quá trình tiến hĩa sinh vật như: đột biến, sự mất đi một thành phần trong chuỗi trình tự. Giá trị hàm đánh giá càng cao thì chúng ta cĩ một kết quả alignment càng tốt. Xét một hàm đánh giá đơn giản như sau, nếu 2 thành phần trong chuỗi là giống nhau thì hàm đánh giá sẽ cĩ kết quả +2, nếu 2 thành phần trong chuỗi khác nhau thì hàm đánh giá tại vị trí này sẽ cĩ kết quả -1, như vậy kết quả so sánh ở trên sẽ cĩ giá trị hàm đánh giá là: 3*(2)+(-1)*5=1 Ý nghĩa: Trên quan điểm sinh học, phép so sánh trình tự thể hiện quá trình biến đổi chọn lọc tự nhiên của các chuỗi trình tự, từ đĩ cho phép các nhà sinh học đưa ra kết luận về nguồn gốc của các đoạn gene, DNA, RNA, hay protein. 2.1.2. Phân loại Dựa trên phương pháp so sánh người ta chia ra làm 2 loại alignment: ƒ Phép alignment trình tự theo hướng tồn cục(Global Sequence Alignment): Phép tốn alignment được áp dụng trên tồn bộ chuỗi trình tự. Thường được sử dụng khi các trình tự so sánh cĩ kích thước gần tương đương và các trình tự này cĩ độ tương đồng, giống nhau cao. ƒ Phép alignment trình tự theo hướng cục bộ(Local Sequence Alignment): Phép tốn alignment được sử dụng trên một phần của chuỗi trình tự. Thường được sử dụng khi các trình tự cĩ chiều dài lớn, độ tương đồng giống nhau khơng cao, chỉ cĩ một số ít các gene giống nhau trên 2 trình tự, hoặc khi 2 trình tự cĩ kích thước khác biệt lớn. A C – – G C T G – C A T G – T – Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 8 Ví dụ về so sánh trình tự theo hướng tồn cục: Hình 2.2 Ví dụ về so sánh trình tự theo hướng tồn cục Tồn bộ 2 chuỗi trình tự L G P S S K Q T G K G S − S R I W D N và L N − I T K S A G K G A I M R L G D A được so sánh Ví dụ về so sánh trình tự theo hướng cục bộ: Hình 2.3 Ví dụ về so sánh trình tự theo hướng cục bộ Chỉ một phần của 2 chuỗi được so sánh: TGKG và AGKG Tùy thuộc vào số lượng trình tự, bài tốn so sánh trình tự được chia làm 2 mức độ: ƒ So sánh 2 trình tự ƒ So sánh nhiều trình tự. 2.1.3. So sánh 2 trình tự (Pairwise Sequence Alignment-PSA). Định nghĩa 2.1: Gọi S1 và S2 là 2 chuỗi, một sự alignment A giữa S1 và S2 sẽ tạo ra 2 chuỗi S’1 và S’2 bằng cách thêm vào các ký tự “-“ vào S1, S2, trong đĩ: ƒ |S’1|=|S’2| ƒ Nếu loại bỏ các ký tự “-“ khỏi S’1 và S’2 ta sẽ cĩ S1 và S2 Với |S1|, |S2| lần lượt là chiều dài của S1 và S2. Hình 2.4 Cấu trúc 1 PSA L G P S S K Q T G K G S − S R I W D N L N − I T K S A G K G A I M R L G D A − − − − − − − T G K G − − − − − − − − − − − − − − − A G K G − − − − − − − − A C G C T G C A T G T A C – – G C T G – C A T G – T – (S1) (S2) (S’1) (S’2) Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 9 2.1.4. So sánh nhiều trình tự (Multiple Sequence Alignment-MSA) Trong mục này ta sẽ xem xét nguồn gốc sinh học của quá trình thực hiện Multiple Squence Alignment. Nguyên nhân chính cho sự ra đời của quá trình so sánh nhiều trình tự là việc so sánh sự tương đồng về trình tự của các protein với một tập protein đã cĩ sẵn trong Cơ Sở Dữ Liệu (CSDL). Thơng thường các protein lưu trong CSDL thường được tổ chức thành các nhĩm chung(protein family), cĩ sự tương đồng về cấu trúc, chức năng, và cấu trúc bậc 3. Khi cần khảo sát một protein mới, chúng ta hy vọng cĩ thể đưa ra các giả thuyết về cấu trúc, chức năng và quá trình tiến hĩa của protein này thơng qua phép tốn alignment. Tuy nhiên, chúng ta khơng thể thực hiện việc alignment chuỗi trình tự của protein này với từng trình tự của mỗi protein trong CSDL, điều này là khơng thể về mặt thời gian xử lý. Do đĩ cách tiếp cận tốt hơn là chúng ta sẽ so sánh trình tự của protein này với mỗi tập hợp protein trong CSDL, thơng qua việc so sánh trình tự của protein này với một trình tự đại diện cho mỗi tập hợp protein. Vấn đề đặt ra là làm cách nào để tìm ra trình tự đại diện cho một tập hợp protein, câu trả lời sẽ được cung cấp thơng qua việc thực hiện phép tốn multiple alignment của tập hợp protein này, để tìm ra phần tử tương đồng nhất đại diện cho tập hợp protein. Định nghĩa 2.2: Cho k chuỗi S1, S2,…,Sk một phép tốn Multiple Sequence Alignment(MSA) của k chuỗi này sẽ tạo ra k chuỗi mới S’1, S’2,…, S’k bằng cách thêm các ký tự “-” vào các chuỗi S1, S2,…,Sk trong đĩ: ƒ |S’1|=|S’2|=…=|S’k|=n ƒ Nếu bỏ đi các ký tự “-” khỏi S’i ta sẽ được lại chuỗi ban đầu Si (1≤i≤k) Hình 2.5 Giới thiệu 1 MSA k được gọi là số sequence của MSA n: là chiều dài của MSA. MSA cĩ n cột, mỗi cột chứa các ký tự đại diện cho các sequence của MSA, các ký tự này cĩ thể là các amino acid(nucleotide) hoặc phần tử ‘-‘. A G T − G T G A G T A G T G − G T C G T G − − T A G T G A G T G T G A G T A G T G G T C G T G T A G T G (S1) (S2) (S3) (S4) (S’1) (S’2) (S’3) (S’4) Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 10 Hình 2.6 Giới thiệu các khái niệm của MSA 2.2. Các khái niệm khác Trong quá trình tiến hĩa của mình trên một đoạn gene, DNA, protein cĩ thể xuất hiện các hành vi: đột biến(mutation), mất(delete), thêm hoặc giữ lại trạng thái di truyền của các nucleotide(DNA) hoặc amino acid với protein. Hình 2.7 Quá trình biến đổi của 2 sequence Như vậy kết quả của phép so sánh giữa ACTCGATT và AGCTAATC: Chúng ta xét 2 chuỗi A=a1a2…am , B=b1b2…bn. Việc biến đổi từ chuỗi trình tự A sang B là sự kết hợp của các quá trình: quá trình thay thế, sự xuất hiện các gap. Một sự thay thế trong quá trình biến đổi từ A sang B là sự thay thế của 1 phần tử của A bằng 1 phần tử của B. Sự thay thế cĩ thể là 1 trong 2 quá 1 trình: quá trình đột biến hoặc quá trình giữ lại trạng thái di truyền. A G T − G T G A G T A G T G − G T C G T G − − T A G T G Cột 7 của MSA k=4 sequence Chiều dài của MSA n=7 ACTCGATT ACTCGATT ACGATT Mất TC tại vị trí thứ 3, 4 AGCATC ACTCGATT Đột biến thay C bằng G tại vị trí 2 Đột biến thay G bằng C tại vị trí 3 Đột biến thay T bằng C tại vị trí 6 AGCTAATC Thêm TA vào vị trí 4 A C T C G - - A T T A G - - C T A A T C Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 11 Một gap bao gồm các phần tử của 1 chuỗi mà mỗi phần tử này tương ứng với các phần tử cĩ ký hiệu là “-“ của chuỗi cịn lại. Gap gồm cĩ 2 loại: deletion gap và insertion gap, tương ứng với quá trình thêm vào hoặc mất đi các phần tử di truyền Hình 2.8 Ví dụ về các phép thay thế gap Như vậy thơng qua kết quả alignment của 2 chuỗi cĩ thể biết được quá trình biến đổi, tiến hĩa từ chuỗi này sang chuỗi khác. Chúng ta cĩ thể quan sát một ví dụ thực tế sau: GCGCTCCGGGACGCCTTCCGCCGTCGGGAGCCCTACAACTACCTGCAGAGGGCCTATTAC -------------------------||||||| ||||||||||||||||||||||| ||| GGGAGCCTTACAACTACCTGCAGAGGGCCTACTAC CAGGTGGGGAGCGGGCCGGGCAG TAG |||||| ||---||||||| |||------------------------------------- CAGGTGCGG GGGCCGGCCAGGGTGCTACCCCAAGCCTACTGACTGTCTTACTGG CCTTCCCCAGAGCCCCCTAGCCGCAGGCACCAGAGGGTCCAAGACAAGACTGGAAGGGCA -----------------------|| || ||| | ||||| || || |||| | | | CAAGCTTCAGCGAGTCCAGGAGAAAGCTGGGAAGCCC CCTCGGGTTCGG GAGGAGCTGTGAGTGGCT | ||||| |||------||||| |||||| |||||------------------------ CGCCGGGTCCGGGTCCGAGAGGAACTGTGAATGGCTGAGCCTGCTTCTCGAGGATCAGGC Mỗi một alignment cĩ một giá trị thơng qua việc đánh giá các phần tử tạo thành nĩ. Giá trị này phản ánh quá trình biến đổi chuỗi A thành chuỗi B và ngược lại. Định nghĩa giá trị này một cách tối ưu sẽ cho phép ta tìm được một quá trình biến đổi tối ưu từ A thành B(và ngược lại), điều này cũng đồng nghĩa với việc tìm phép alignment tối ưu của A và B. Việc tính tốn giá trị cho một alignment phụ thuộc vào: ƒ Ma trận đánh giá ƒ Giá trị của Gap ƒ Phương pháp đánh giá A C T C G - - A T T A G - - C T A AT C Sự thay thế Deletion gap Insertion gap Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 12 2.2.1. Ma trận đánh giá(Scoring Matrix) Kết quả của việc tính giá trị cho mỗi alignment phụ thuộc nhiều vào kết quả của hàm đánh giá sự tương đồng của mỗi cặp amino acid(nucleotide) ( , )a bσ . Trong phần ví dụ về alignment ta cĩ đưa ra một ví dụ đơn giản cho ( , )a bσ tuy nhiên trong thực tế sinh học khả năng xuất hiện của mỗi cặp amino acid(cũng như nucleotide) là khác nhau, xác suất xuất hiện cùng lúc của cặp amino acid này cĩ thể cao trong khi xác suất xuất hiện của cặp amino acid kia cĩ thể thấp. Vì thế độ tương đồng của các cặp amino acid thường được lưu trữ dưới dạng một ma trận 2 chiều gọi là ma trận đánh giá. Một ví dụ: Bảng 2.1Ma trận BLOSUM62 lưu trữ hàm đánh giá độ tương đồng của tập 23 amino acid Xét trên phương diện tốn, ma trận đánh giá là 1 ánh xạ được định nghĩa như sau: 2: ( ')σ ∑ →\ trong đĩ ' {' '}∑ = ∑∪ − và ∑ là tập các amino acid hoặc nucleotide Cĩ nhiều hình thức ma trận đánh giá khác nhau dựa trên quá trình nghiên cứu, thống kê thực tế sinh học. Hiện tại cĩ 4 hình thức ma trận đánh giá: identity matrix, genetic code matrix, chemical similarity matrix và substitution matrix. A R N D C Q E G H I L K M F P S T W Y V B Z X * A 6 -2 -2 -3 -1 -1 -1 0 -2 -2 -2 -1 -1 -3 -1 2 0 -4 -3 0 -2 -1 -1 -6 R -2 8 -1 -2 -5 1 0 -3 0 -4 -3 3 -2 -4 -3 -1 -2 -4 -3 -4 -2 0 -2 -6 N -2 -1 8 2 -4 0 0 -1 1 -5 -5 0 -3 -4 -3 1 0 -6 -3 -4 5 0 -2 -6 D -3 -2 2 9 -5 0 2 -2 -2 -5 -5 -1 -5 -5 -2 0 -2 -6 -5 -5 6 1 -2 -6 C -1 -5 -4 -5 13 -4 -5 -4 -4 -2 -2 -5 -2 -4 -4 -1 -1 -3 -4 -1 -5 -5 -3 -6 Q -1 1 0 0 -4 8 3 -3 1 -4 -3 2 -1 -5 -2 0 -1 -3 -2 -3 0 5 -1 -6 E -1 0 0 2 -5 3 7 -3 0 -5 -4 1 -3 -5 -2 0 -1 -4 -3 -4 1 6 -1 -6 G 0 -3 -1 -2 -4 -3 -3 8 -3 -6 -5 -2 -4 -5 -3 0 -2 -4 -5 -5 -1 -3 -2 -6 H -2 0 1 -2 -4 1 0 -3 11 -5 -4 -1 -2 -2 -3 -1 -3 -4 3 -5 -1 0 -2 -6 I -2 -4 -5 -5 -2 -4 -5 -6 -5 6 2 -4 2 0 -4 -4 -1 -4 -2 4 -5 -5 -2 -6 L -2 -3 -5 -5 -2 -3 -4 -5 -4 2 6 -4 3 1 -4 -4 -2 -2 -2 1 -5 -4 -2 -6 K -1 3 0 -1 -5 2 1 -2 -1 -4 -4 7 -2 -5 -2 0 -1 -4 -3 -3 -1 1 -1 -6 M -1 -2 -3 -5 -2 -1 -3 -4 -2 2 3 -2 8 0 -4 -2 -1 -2 -1 1 -4 -2 -1 -6 F -3 -4 -4 -5 -4 -5 -5 -5 -2 0 1 -5 0 9 -5 -4 -3 1 4 -1 -5 -5 -2 -6 P -1 -3 -3 -2 -4 -2 -2 -3 -3 -4 -4 -2 -4 -5 11 -1 -2 -5 -4 -4 -3 -2 -2 -6 S 2 -1 1 0 -1 0 0 0 -1 -4 -4 0 -2 -4 -1 6 2 -4 -3 -2 0 0 -1 -6 T 0 -2 0 -2 -1 -1 -1 -2 -3 -1 -2 -1 -1 -3 -2 2 7 -4 -2 0 -1 -1 -1 -6 W -4 -4 -6 -6 -3 -3 -4 -4 -4 -4 -2 -4 -2 1 -5 -4 -4 16 3 -4 -6 -4 -3 -6 Y -3 -3 -3 -5 -4 -2 -3 -5 3 -2 -2 -3 -1 4 -4 -3 -2 3 10 -2 -4 -3 -2 -6 V 0 -4 -4 -5 -1 -3 -4 -5 -5 4 1 -3 1 -1 -4 -2 0 -4 -2 6 -5 -4 -1 -6 B -2 -2 5 6 -5 0 1 -1 -1 -5 -5 -1 -4 -5 -3 0 -1 -6 -4 -5 5 0 -2 -6 Z -1 0 0 1 -5 5 6 -3 0 -5 -4 1 -2 -5 -2 0 -1 -4 -3 -4 0 5 -1 -6 X -1 -2 -2 -2 -3 -1 -1 -2 -2 -2 -2 -1 -1 -2 -2 -1 -1 -3 -2 -1 -2 -1 -2 -6 * -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 1 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 13 Identity matrix: đây là cơ chế đánh giá độ tương đồng đơn giản nhất, trong ma trận này các cặp amino acid giống nhau sẽ cĩ giá trị của phần tử tương ứng trong ma trận là 1, các cặp amino acid cịn lại sẽ nhận giá trị 0. Ví dụ Bảng 2.2 Một phần ma trận Identity Ma trận mã di truyền(Genetic code matrix): trong ma trận này hàm đánh giá của mỗi cặp amino acid dựa trên độ tương đồng về mã di truyền. Ngày nay ma trận này hiếm khi được sử dụng trong việc alignment các chuỗi amino acid. Ma trận tương đồng hĩa học(chemical similarity matrix): trong ma trận này, các amino acid cĩ cấu trúc tương đồng về cấu trúc vật lý cũng như thuộc tính hĩa học như kích thước, hình dạng, khả năng phân cực,… thì phần tử tương ứng trong ma trận sẽ nhận giá trị lớn hơn so với các cặp cịn lại. Ma trận thay thế(substitution matrix): Ma trận này được tính tốn và xây dựng dựa trên các quan sát thống kê về tần số thay đổi của các amino acid trong việc alignment các chuỗi trình tự. Ma trận thay thế được đánh giá là tốt hơn so với 3 hình thức ma trận trên và hiện nay cũng được sử dụng phổ biến nhất. Trong phần này, xin giới thiệu 1 hình thức ma trận thay thế hay được sử dụng trong các cơng trình nghiên cứu cũng như trong các cơng cụ phục vụ cho việc tính tốn sinh học: ma trận BLOSUM. Ma trận BLOSUM(Block Subtitutation Matrix): Khái niệm ma trận BLOSUM được xây dựng dựa trên 1 MSA của tập các protein cĩ sự khác biệt về quá trình tiến hĩa. Hàm đánh giá của các cặp amino acid trong ma trận được tính dựa vào tần số quan sát sự thay đổi trong các khối(block) của các local alignment của các họ protein trong cơ sở dữ liệu BLOCK(Henikoff và Henikoff 1992)[14]. Cơ sở dữ liệu này gồm 3000 block của các protein đặc trưng, đại diện cho vài trăm nhĩm protein. Các ma trận BLOSUM được thiết kế nhằm giải quyết cho các A R N D C Q A 1 0 0 0 0 0 R 0 1 0 0 0 0 N 0 0 1 0 0 0 D 0 0 0 1 0 0 C 0 0 0 0 1 0 Q 0 0 0 0 0 1 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 14 trường hợp align các sequence cĩ sự biến đổi, tiến hĩa về mặt di truyền trong một khoảng thời gian dài. Ma trận BLOSUM bao gồm nhiều cấp độ, ký hiệu BLOSUMn. Ma trận BLOSUMn(1 100n≤ ≤ ) cho biết độ tương đồng của các chuỗi được dùng để tính ra chúng. Ví dụ, chúng ta xét ma trận BLOSUM62, giá trị của các phần tử trong ma trận được tính từ tập các protein cĩ độ tương đồng khơng lớn hơn 62%. Trong tập các ma trận BLOSUMn, các ma trận cĩ chỉ số n nhỏ thường được sử dụng trong việc align các sequence cĩ độ khác biệt cao(độ tương đồng thấp), và các ma trận cĩ chỉ số n lớn thường được sử dụng cho các sequence cĩ độ tương đồng cao. Ví dụ: ma trận BLOSUM62 thường được sử dụng nhất cho việc align các sequence khi chưa xác định độ tương đồng của chúng, ma trận BLOSUM45 thường được sử dụng cho các sequence cĩ sự khác biệt cao, ma trận BLOSUM100 thường được sử dụng cho các ma trận đĩ độ tương đồng cao. Việc tính tốn tập các ma trận BLOSUM dựa trên cơng thức xác suất biến đổi: ( , ) ( , ) log( )O E Pscore a b a b k P σ= = trong đĩ OP là xác suất chuyển đổi từ amino acid a sang amino acid b trong tập quan sát EP : là xác suất xuất hiện của amino acid b trong tập quan sát. k là hệ số làm trịn. Thơng thường k=10, và giá trị hàm đánh giá được làm trịn thành số nguyên. ( , ) 0score a b > : cho biết sự thay thế giữa amino acid a và b cĩ khả năng xảy ra cao hơn so với sự thay đổi một cách ngẫu nhiên ( , ) 0score a b < : cho biết sự thay thế giữa amino acid a và b cĩ khả năng xảy ra thấp hơn so với sự thay đổi một cách ngẫu nhiên. ( , ) 0score a b = : cho biết sự thay thế giữa amino acid a và b tương đương với việc thay thế 2 amino acid một cách ngẫu nhiên. 2.2.2. Gap Việc tính giá trị của mỗi gap phụ thuộc vào bản chất tự nhiên của các chuỗi trình tự, cĩ thể tính giá trị của gap theo các hàm tuyến tính hoặc đa thức. Trong thực tế, để Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 15 đơn giản hầu hết các phương pháp đề xuất tính giá trị của gap dựa trên một hàm tuyến tính theo chiều dài của gap. Chúng ta sẽ xem xét “Phương pháp tính giá trị của gap dựa trên hàm tuyến tính”. Thơng thường khả năng xuất hiện phần tử đầu tiên của gap(khả năng mở gap) thường khác với khả năng xuất hiện của các phần tử theo sau, gọi q(q>0) là giá trị xác định khả năng mở một gap, và khả năng xuất hiện của mỗi phần tử trong gap(khả năng mở rộng của gap) là r(r>0). Gọi )(kγ là hàm giá trị của gap ta định nghĩa: ( ) ( * )γ = − +k q r k Ví dụ : CAGGTGGGGAGCGGGCCGGGCAG |||||| ||---||||||| ||| CAGGTGCGG GGGCCGGCCAG Hình 2.9 Ví dụ về Gap. Trong ví dụ trên: Khả năng xuất hiện của cặp đầu tiên A − là q+r . Khả năng xuất hiện của các phần tử tiếp theo trong gap lần lượt là r. Giá trị của gap: (3) ( *3)γ = − +q r . 2.2.3. Phương pháp đánh giá(Scoring Method) Phương pháp đánh giá cho phép đánh giá sự giống nhau, tương đồng giữa các trình tự dựa trên một số tiêu chí nào đĩ. Việc so sánh giữa 2 hay nhiều chuỗi trình tự sẽ cho ra nhiều kết quả so sánh khác nhau từ một tập chuỗi trình tự ban đầu. Cơ sở để đánh giá sự giống nhau, tương đồng giữa các trình tự sau phép alignment thường căn cứ vào một hàm đánh giá cụ thể. Việc xây dựng hàm đánh giá tốt sẽ cho phép xác định được kết quả nào của phép so sánh là tối ưu. Hàm đánh giá chính là cốt lõi của một phương pháp đánh giá. Đối với PSA, phương pháp đánh giá phổ biến nhất là dựa vào tổng giá trị của các cặp ký tự đại diện khơng phải là gap, và giá trị của các gap trong PSA. Gọi K1 là tập các phần tử khơng phải là gap của PSA, K2 là tập các gap trong PSA. Hàm đánh giá PSA của 2 chuỗi S1, S2 với kết quả S’1, S’2 cĩ dạng: 1 2( , )Score S S = Score(K1)+Score( K2) 1 1 1 2( ) ( ' [ ], ' [ ])σ ∈ = ∑ i K Score K S i S i , với S’1[i], S’2[i] là các phần tử thuộc K1. 2 2( ) ( )i i K Score K kγ ∈ = ∑ với γ(ki) là các hàm tính cho các gap thuộc K2. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 16 Đối với một MSA do bản chất phức tạp của dữ liệu sinh học nên tất cả các phương thức đánh giá đều cĩ những hạn chế, và khơng cĩ một tiêu chuẩn tổng quát nào trong việc đo lường chất lượng của nĩ. Trong phần này xin được giới thiệu một số phương pháp xây dựng hàm đánh giá phổ biến cho một MSA [1]. ƒ Sum-of-Pair(SP): Đây là phương pháp được sử dụng phổ biến nhất. Nội dung của phương pháp này là đánh giá MSA của k sequence dựa trên tổng kết quả alignment của tất cả ( k2 ) cặp sequence cĩ trong MSA. Theo phương pháp này giá trị của mỗi cột của MSA sẽ được tính bằng tổng tất cả các hàm đánh giá độ tương đồng của các cặp phần tử trong cột này. Gọi ci,j là ký tự tại dịng i, cột j trong MSA và ( , )a bσ là hàm đánh giá sự tương đồng của cặp amino acid a, b. Ta sẽ cĩ giá trị hàm đánh giá độ tương đồng SP của cột i như sau: , ,( ) ( , ) 1 , ,1x i y i x y SP i c c x y k i nσ < = ≤ ≤ ≤ ≤∑ Trong đĩ n là chiều dài của MSA. Gọi 1( ,..., )kSPScore S S là hàm đánh giá độ tương đồng của MSA theo SP. 1( ,..., )kSPScore S S sẽ bằng tổng tất cả các hàm đánh giá độ tương đồng của các cột trong MSA: 1 1 1 ( ,..., ) ( ,..., ) ( ) k k k i Score S S SPScore S S SP i = = =∑ MSA tối ưu là MSA cĩ SP tối ưu. Cơng thức này cũng cĩ thể được viết lại dưới dạng sau: 1 1 1 1 ( ,..., ) ( ,..., ) ( , ) k k k k i j i j i Score S S SPScore S S SPScore S S = = + = =∑ ∑ trong đĩ ( , )i jSPScore S S là hàm đánh giá theo SP của 2 chuỗi Si và Sj Ví dụ: Xét một MSA của 3 sequence: ACCTG , CCTGT, AGCTAT (S1) A C - C T G - (S2) - C - C T G T (S3) A - G C T A T Nếu chúng ta định nghĩa ( , )a bσ như sau: 0 ( , ) 1 a b a b a b σ ≠⎧= ⎨ =⎩ Khi đĩ SP(2)= ( , ) ( , ) ( , )C C C Cσ σ σ+ − + − =1+0+0=1 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 17 SP=SP(1)+SP(2)+SP(3)+SP(4)+SP(5)+SP(6)+SP(7)=1+1+1+3+3+1+1=11 Kết quả đánh giá độ tương đồng của 3 chuỗi này cũng cĩ thể được biểu diễn: SP(S1,S2,S3)=SP(S1,S2)+SP(S2,S3)+SP(S3,S1)=5+3+3=11 ƒ Phương pháp #LOG#: Phương pháp này đánh giá độ tương đồng của MSA dựa trên các cơng thức sau: Hàm đánh giá độ tương đồng của MSA tại cột thứ i: # ( ) # ( ) log ( )i i a LOG i c a c a ∈∑ = ∑ Cơng thức đánh giá độ tương đồng của tồn bộ MSA: 1 1 1 ( ,..., ) # ( ,..., ) # ( ) log ( ) n k k i i i a Score S S LOG S S c a c a = ∈∑ = =∑∑ Trong đĩ a∈∑ với ∑ là tập các amino acid hoặc nucleotide ( )ic a là số lần xuất hiện của a tại cột thứ i. ƒ Phương pháp Trung bình thơng tin(Average Information Content): Trong phương pháp này hàm đánh giá độ tương đồng của MSA tại cột thứ i được xây dựng dựa trên cơng thức sau: ( )1( ) ( ) log ( ) i i a f aIC i f a n p a∈∑ = ∑ fi(a) là tần số xuất hiện của a trong cột thứ i của MSA. ( ( )( ) ii c af a k = ) p(a) là tần số xuất hiện của a trong tồn bộ MSA. Khi đĩ cơng thức tính độ tương đồng của MSA: 1 1 1 ( )1( ,..., ) ( ,..., ) ( ) log ( )= ∈Σ = = ∑∑n ik k i i a f aScore S S IC S S f a n p a ƒ Phương pháp Entropy: Phương pháp này đánh giá độ tương đồng của MSA dựa trên lý thuyết về Entropy Hàm đánh giá độ tương đồng của cột thứ i trong MSA: ( ) ( ) log ( )i i a entropy i c a f a ∈∑ = −∑ Hàm đánh giá độ tương đồng của tồn bộ MSA: 1 1 1 ( ,..., ) ( ) ( ) log ( ) n n k i i i i a score S S entropy i c a f a = = ∈∑ = =∑ ∑∑ Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 18 Trong phạm vi của luận văn này phương pháp được sử dụng để đánh giá là phương pháp Sum-of-Pair. 2.3. Các phương pháp giải quyết bài tốn so sánh trình tự Hiện nay đã cĩ nhiều cách tiếp cận khác nhau của các nhà nghiên cứu về vấn đề này, Pairwise Sequence Alignment-PSA đã được giải quyết khá triệt để, tuy nhiên bài tốn Multiple Sequence Alignment-MSA dựa trên phương pháp đánh giá Sum-of-Pair vẫn cịn là một vấn đề để ngỏ. Wang và Jiang [32] đã chứng minh rằng việc tìm kiếm phép Alignment tối ưu cho bài tốn Multiple Alignment là bài tốn NP. Đã cĩ nhiều mơ hình, thuật giải được áp dụng để giải quyết bài tốn này: Kỹ thuật quy hoạch động(Dynamic Programming), sử dụng mơ hình Markov ẩn (Hidden Markov Model), các kỹ thuật tìm kiếm cục bộ(Local Search)…. Hầu hết các phương pháp giải quyết rất tốt bài tốn PSA. Tuy nhiên vì MSA là bài tốn NP nên các kỹ thuật đưa ra đều khơng thể đánh giá chính xác về mức độ tốt xấu của từng giải thuật, mỗi giải thuật sẽ cĩ ưu điểm trong từng trường hợp cụ thể [6], [28], [35]. Việc giải quyết bài tốn được chia thành 2 hướng: ƒ Phương pháp tính tốn chính xác, tìm ra MSA tối ưu ƒ Phương pháp tính tốn gần đúng tìm ra MSA cận tối ưu. Phương pháp tính tốn chính xác: bao gồm phương pháp quy hoạch động tổng quát(Needleman-Wuns)[22], và một số giải pháp phần cứng. Phương pháp tính tốn cận tối ưu: Phương pháp này sử dụng các tiếp cận heuristic để giải quyết bài tốn trên tập dữ liệu lớn theo hướng tìm ra các lời giải cận tối ưu, cĩ thể chấp nhận được về độ chính xác cũng như thời gian và khơng gian bộ nhớ sử dụng. Phương pháp này chia thành 2 nhĩm: ƒ Progressive Algorithm ƒ Iterative Algorithm Progressive Algorithm: về cơ bản phương pháp này vẫn dựa trên nền tảng của dynamic programming. Ý tưởng của Progressive Algorithm là tìm MSA gần tối ưu thơng qua việc align các sequence với nhau, dựa trên việc áp dụng bài tốn PSA lặp đi lặp lại nhiều lần. Ưu điểm của phương pháp này giúp tìm lời giải nhanh hơn. Chi tiết về phương pháp này sẽ đề cập trong chương 3. Một số chương trình hiện thực theo Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 19 phương pháp này: CLUSTALW, MULTALIGN, PILEUP, BLAST, FASTA. MULTAL, DIALIGN. Iterative Algorithm:Ý tưởng của các giải thuật theo phương pháp này là : đầu tiên sẽ xây dựng một MSA mà khơng quan tâm đến độ tốt xấu, sau đĩ sẽ cải thiện chất lượng của MSA này theo thời gian thơng qua các bước lặp. Một số các giải thuật theo phương pháp này: Giải thuật di truyền, Mơ hình Markov ẩn. So sánh Progressive Algorithm và Iterative Algorithm: Cả 2 phương pháp đều cĩ ưu điểm và khuyết điểm, tùy theo điều kiện cũng như yêu cầu cụ thể mà chúng ta cĩ thể lựa chọn phương pháp hợp lý nhất. Iterative Algorithm thơng thường cho lời giải cĩ độ chính xác cao hơn tuy nhiên trong một số trường hợp, phương pháp này cĩ thể cho ra các lời giải khơng tốt. Iterative Algorithm địi hỏi thời gian tính tốn cao, một số trường hợp giải thuật cĩ thể cho thời gian tính tốn cao hơn so với cách tiếp cận theo phương pháp tính tốn chính xác của Needlman-Wuns(Nicholas, 2002)[23]. Đây là một trong những nhược điểm lớn của phương pháp này. Hình 2.10 Mối tương quan giữa các chương trình hiện thực cho các phương pháp. 2.3.1. Phương pháp Quy hoạch động(Dynamic Programming) Đây là phương pháp phổ biến và cơ bản nhất để tiếp cận bài tốn so sánh trình tự. Kỹ thuật dynamic programming giải quyết bài tốn dựa trên lý thuyết về Edit distance được đưa ra bởi Vladimir Levenshtein, khoảng cách này định nghĩa số các thao tác nhỏ nhất để cĩ thể chuyển đổi một chuỗi trình tự này thành một chuỗi trình tự khác. Edit distance cĩ thể biểu diễn cho quá trình tiến hĩa của một đoạn gene, DNA, protein UPGMA Multalign, Pileup NJ ClustalW GA Saga HMM Hmmt Iterative Progressive Mutal Dialign Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 20 theo thời gian. Điều này hồn tồn hữu dụng cho lý thuyết về so sánh trình tự. Kỹ thuật dynamic programming cĩ thể tính được edit distance. Bằng việc xây dựng các ma trận đánh giá k chiều với mỗi chiều của ma trận tương ứng với một trong k trình tự của bài tốn, phương pháp dynamic programming cĩ thể tìm ra được giá trị hàm đánh giá tối ưu cho ma trận này, từ đĩ sử dụng kỹ thuật lưu vết để tìm ra được phép so sánh nhiều trình tự tối ưu nhất. Needleman-Wuns đã xây dựng phương pháp tìm MSA tối ưu của k sequence dựa trên việc tổng quát hĩa giải thuật quy hoạch động cho 2 sequence. Trong giải thuật này các tác giả đã thay thế việc tính tốn điền các giá trị cho ma trận 2 chiều bằng ma trận n chiều. Giải thuật phụ thuộc vào số sequence, chiều dài cũng như sự khác biệt của các sequence. Giải thuật này địi hỏi độ phức tạp là hàm số mũ theo chiều dài và số trình tự ( )knθ . Trong thực tế việc hiện thực giải thuật này địi hỏi chi phí tiêu tốn rất cao về mặt thời gian cũng như bộ nhớ sử dụng. Khi n và k đủ lớn việc thực thi giải thuật là khơng thực tế. Một mini-supercomputer với 4GB bộ nhớ cĩ thể align 20 sequence thuộc nhĩm phospholipase A2, mỗi sequence cĩ khoảng 130 amino acid[23]. Đã cĩ một số phương pháp cải thiện giải thuật của Needleman-Wuns, bằng cách áp dụng heuristic vào giải thuật này, tuy nhiên vẫn cĩ hạn chế về giá trị của n, k. 0 0 0 0 0 0000000 G A A T T C G G A T C 2 54310-1 13532-1 -3-11340 -2-2-2-112 -1-1-1-10 Hình 2.11 Phương pháp tính tốn chính xác bằng dynamic programming 2.3.2. Sử dụng các thiết bị phần cứng Phương pháp sử dụng thiết bị phần cứng để hiện thực hĩa kỹ thuật dynamic programming, hoặc sử dụng các thiết bị phần cứng để song song hĩa, chia nhỏ bài tốn. Các phương pháp này sẽ giúp thực thi bài tốn nhanh hơn tuy nhiên cả hai phương pháp này đều địi hỏi chi phí quá cao. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 21 2.3.3. Phương pháp tìm kiếm cục bộ(Local Search) Các kỹ thuật tìm kiếm cục bộ sử dụng các kỹ thuật lặp với các tham số đầu vào xác định, giải quyết bài tốn so sánh nhiều trình tự theo hướng tìm ra lời giải gần tối ưu nhất dựa trên các bước di chuyển tốt của của mỗi trạng thái của lời giải so với các trạng thái xung quanh nĩ trong mỗi vịng lặp xác định. Chủ yếu được sử dụng cho việc giải quyết bài tốn so sánh theo hướng tồn cục. Phương pháp này cĩ ưu điểm thừa kế được các ưu điểm của các giải thuật tìm kiếm cục bộ: giảm khơng gian tìm kiếm của lời giải, tốc độ tìm kiếm nhanh…, tuy nhiên do phương pháp tìm kiếm cục bộ chỉ đảm bảo tính đúng(sound) chứ khơng đảm bảo tính đầy đủ(complete), và do việc lựa chọn các bước đi để thốt khỏi tình trạng tối ưu cục bộ là ngẫu nhiên nên cĩ thể thuật tốn sẽ khơng tìm ra được lời giải tốt trong một số lần chạy(phụ thuộc vào việc ấn định các tham số đầu vào). Một số giải thuật : Tabu Search, Simulated Annealing(giải thuật luyện kim). 2.3.4. Sử dụng giải thuật Di truyền(Genetic Algorithm) Phương pháp sử dụng thuật giải di truyền cho bài tốn so sánh nhiều trình tự là một phương pháp phù hợp với bản chất sinh học [34]. Ý tưởng tạo ra một quần thể các alignment sau đĩ chọn ra các lời giải tốt nhất cĩ thể. Phương pháp này tạo dựng một quần thể các phép so sánh trình tự từ các phép tốn cơ bản của sinh học, lai tạo, đột biến và cố gắng cải thiện hàm thích nghi của quần thể các phép so sánh trình tự. Phương pháp này cho kết quả tốt, tuy nhiên hạn chế của phương pháp này là thời gian tính tốn lớn(đặc điểm chung của giải thuật di truyền). Một số phần mềm: SAGA(Notredame và Higgins, 1996)[24]. 2.3.5. Sử dụng Mơ hình Markov ẩn(Hidden Markov Model-HMM). Áp dụng mơ hình Markov ẩn để mơ hình hĩa bài tốn so sánh nhiều trình tự. Ý tưởng của phương pháp này là sử dụng mơ hình Markov ẩn để biểu diễn MSA(được giới thiệu bởi Eddy(1995) [8]), sau đĩ tối ưu khả năng mà một mơ hình HMM cĩ thể biểu diễn cho các sequence đã được align. Trong mơ hình này các nucleotide(A,C,T,G) hoặc 23 amino acid sẽ là tập các ký tự. Các trạng thái của mơ ._.SAPR cho kết quả chạy khá tốt trên BAliBASE benchmark. 5.3. So sánh kết quả Để kiểm định kết quả của MSAPR, đề tài sử dụng các file .tfa của BAliBASE, thực hiện việc tính tốn đồng thời kết quả của cả MSAPR và CLUSTALW. Ngồi ra để cung cấp một cái nhìn tồn diện hơn, chương trình cĩ sử dụng lại các kết quả tính tốn của Thompson [29] với 7 chương trình khác để thực hiện việc so sánh. Các chương trình này bao gồm: SAGA, DIALIGN, SB_PIMA, ML_PIMA, MULTALIGN, PILEUP 8, MULTAL, HMMT. Chi tiết về các chương trình và các kết quả này cĩ thể tham khảo tại trang web Bioinformatics Platform of Strasbourg [5]. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 70 5.3.1. Giới thiệu về các chương trình được sử dụng CLUSTALW: là một chương trình mã nguồn mở được phát triển bởi Gibson T. (European Molecular Biology Laboratory-EMBL), Thompson J. (National Scientific Research Centre- CNRS (France)), Higgins D. (University College Dublin(UCD) - National University of Ireland, Dublin). CLUSTALW hiện thực bằng C và sử dụng Progressive Algorithm. Đây là chương trình cho kết quả ổn định và tốt nhất trong các chương trình phát triển theo hướng Progressive Algorithm. Phiên bản được sử dụng tính tốn trong đề tài là CLUSTALW 1.83. CLUSTALX: là một phiên bản giao diện đồ họa của CLUSTALW. Phiên bản được sử dụng trong đề tài là CLUSTALX 1.83. SAGA được phát triển bởi Cédric Notredame* and Desmond G. Higgins (European Bioinformatics Institute ) sử dụng giải thuật di truyền để tìm lời giải MSA. DIALIGN được phát triển bởi Burkhard Morgenstern(University of Gưttingen), DIALIGN sử dụng Progressive Algorithm.(khơng áp dụng gap penalty). ML_PIMA, SB_PIMA được phát triển bởi Smith, R.F và Smith,T.F. Sử dụng Progressive Algorithm. MULTALIGN: được phát triển bởi Barton G.J. và Sternberg(Laboratory of Molecular Biology Department of Crystallography Birkbeck College, London). MULTALIGN sử dụng mơ hình Progressive Algorithm để tìm lời giải MSA. PILEUP 8 được phát triển bởi Genetic Computer Group(GCG) áp dụng Progressive Algorithm để tìm lời giải MSA. MULTAL được phát triển bởi Taylor, sử dụng Progressive Algorithm để hiện thực. HMMT được phát triển bởi Sean R. Eddy(Washington University School, MRC- Laboratory of Molecular Biology in Cambridge), sử dụng mơ hình Markov ẩn để tìm lời giải MSA. 5.3.2. So sánh độ chính xác của kết quả Trong phần này sẽ trình bày các kết quả thu được khi chạy MSAPR, và CLUSTALW trên tập 5 nhĩm dữ liệu của BAliBASE, và liệt kê thêm các kết quả khác của 7 chương trình nêu ở trên dựa trên một nghiên cứu của Thompson. Chúng ta sẽ xét kết quả của các chương trình khi sử dụng từng nhĩm dữ liệu MSA của BAliBASE. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 71 Nhĩm 1. Dựa vào chiều dài của các MSA, BAliBASE chia Nhĩm 1 làm 3 tập con: ƒ Tập MSA cĩ chiều dài nhỏ(từ 50-200 phần tử) ƒ Tập MSA cĩ chiều dài trung bình (từ 200-400 phần tử) ƒ Tập MSA cĩ chiều dài lớn( từ 500 phần tử trở lên) Căn cứ vào độ giống nhau I của các sequence tạo nên các MSA, trong mỗi tập con lại chia thành 3 hình thức, Các MSA thỏa mãn I 0.25< . Các MSA cĩ I thỏa 0.2 I 0.4≤ ≤ và các MSA cĩ I thỏa I 0.35≤ . Ba bảng 5.3, 5.4, 5.5 liệt kê độ chính xác của các chương trình khi sử dụng dữ liệu nhĩm 1, (cĩ độ giống nhau của các sequence I thỏa mãn I 0.25< ). Cột đầu tiên là tên của các sequence thuộc nhĩm 1(I<0.25). Các cột tiếp theo lần lượt là độ chính xác của các chương trình so với kết quả MSA của BAliBASE. Kết quả chạy chương trình với tập MSA cĩ chiều dài nhỏ(gồm 7 tập sequence). Tên MSA PR CLUST ALW SAGA DIALIG N SB_ PIMA ML_ PIMA MULTA LIGN PILE UP 8 MULT AL HMMT 1aboA 0.581 0.688 0.529 0.359 0.312 0.312 0.703 0.521 0.526 0.181 1idy 0.604 0.548 0.342 0.018 0.145 0.062 0.566 0.080 0.080 0.138 1r69 0.382 0.436 0.550 0.406 0.681 0.366 0.325 0.562 0.225 0.100 1tvxA 0.319 0.216 0.278 0.306 0.344 0.344 0.228 0.344 0.244 0.108 1ubi 0.477 0.595 0.452 0.000 0.370 0.493 0.488 0.428 0.428 0.140 1wit 0.666 0.693 0.899 0.851 0.963 0.444 0.842 0.773 0.763 0.549 2trx 0.548 0.690 0.801 0.728 0.451 0.496 0.500 0.453 0.235 0.292 Bảng 5.3 Kết quả chạy chương trình với Nhĩm 1 cĩ chiều dài nhỏ Kết quả chạy chương trình với tập MSA cĩ chiều dài trung bình(8 tập sequence). MSA PR CLUSTA LW SAGA DIALIG N SB_ PIMA ML_PI MA MULTA LIGN PILEU P8 MUL TAL HMMT 1bbt3 0.188 0.315 0.652 0.450 0.260 0.260 0.582 0.430 0.160 0.128 1sbp 0.425 0.467 0.543 0.453 0.540 0.456 0.580 0.547 0.537 0.144 1havA 0.260 0.227 0.411 0.130 0.300 0.466 0.419 0.536 0.040 0.133 1uky 0.407 0.517 0.672 0.566 0.684 0.684 0.685 0.571 0.460 0.084 2hsdA 0.529 0.537 0.771 0.679 0.470 0.470 0.470 0.646 0.463 0.117 2pia 0.565 0.601 0.690 0.660 0.740 0.740 0.760 0.850 0.560 0.057 3grs 0.293 0.310 0.689 0.327 0.416 0.416 0.380 0.446 0.347 0.056 kinase 0.615 0.655 0.862 0.764 0.733 0.703 0.643 0.730 0.650 0.277 Bảng 5.4 Kết quả chạy chương trình với Nhĩm 1 cĩ chiều dài trung bình Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 72 Kết quả chạy chương trình với tập MSA cĩ chiều dài lớn(8 tập sequence). Bảng 5.5 Kết quả chạy chương trình với Nhĩm 1 cĩ chiều dài lớn 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Testcase(Nhĩm 1)(I<0.25) Đ ộ ch ín h xá c MSA PR CLUSTALW MULTAL Độ dài nhỏ Độ dài trung bình Độ dài lớn Hình 5.1 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và MULTAL MSA PR CLUST ALW SAGA DIALI GN SB_PI MA ML_PI MA MULT ALIGN PILEU P8 MULT AL HMMT 1ajsA 0.434 0.371 0.531 0.142 0.486 0.471 0.424 0.556 0.364 0.105 1cpt 0.647 0.696 0.780 0.829 0.792 0.792 0.835 0.865 0.777 0.156 1lvl 0.460 0.394 0.619 0.699 0.559 0.559 0.570 0.587 0.572 0.064 1pamA 0.389 0.433 0.596 0.694 0.513 0.549 0.596 0.641 0.204 0.034 1ped 0.732 0.748 0.748 0.743 0.756 0.756 0.727 0.723 0.730 0.032 2myr 0.448 0.394 0.285 0.284 0.670 0.613 0.422 0.621 0.547 0.050 4enl 0.547 0.562 0.414 0.529 0.701 0.701 0.754 0.669 0.787 0.044 gal4 0.360 0.518 0.500 0.581 0.445 0.445 0.368 0.543 0.406 0.055 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 73 Nhĩm 2: Bảng 5.6 liệt kê độ chính xác của các chương trình khi thực hiện việc tính tốn MSA với tồn bộ dữ liệu của nhĩm 2. MAS PR CLUST ALW SAGA DIALI GN HMMT SB_PI MA ML_PI MA MULT ALIGN PILE UP8 1aboA 0.759 0.850 0.489 0.384 0.724 0.391 0.220 0.528 0.000 1idy 0.899 0.949 0.548 0.000 0.353 0.000 0.000 0.401 0.000 1csy 0.626 0.804 0.154 0.000 0.000 0.000 0.000 0.154 0.114 1r69 0.887 0.916 0.475 0.675 0.000 0.675 0.675 0.675 0.450 1tvxA 0.867 0.942 0.448 0.000 0.276 0.241 0.241 0.138 0.345 1tgxA 0.737 0.786 0.773 0.630 0.622 0.678 0.543 0.696 0.318 1ubi 0.756 0.826 0.492 0.000 0.053 0.129 0.129 0.000 0.000 1wit 0.648 0.800 0.694 0.724 0.641 0.469 0.463 0.500 0.476 2trx 0.933 0.950 0.870 0.734 0.739 0.850 0.702 0.870 0.870 1sbp 0.721 0.808 0.374 0.043 0.214 0.043 0.054 0.186 0.177 1havA 0.763 0.839 0.448 0.000 0.194 0.259 0.238 0.500 0.493 1uky 0.815 0.855 0.476 0.216 0.395 0.256 0.306 0.585 0.562 2hsdA 0.796 0.836 0.498 0.262 0.423 0.390 0.561 0.593 0.278 2pia 0.803 0.821 0.763 0.612 0.647 0.730 0.695 0.765 0.766 3grs 0.737 0.803 0.282 0.350 0.141 0.183 0.211 0.192 0.159 kinase 0.827 0.914 0.867 0.692 0.749 0.755 0.651 0.830 0.799 1ajsA 0.870 0.876 0.311 0.000 0.242 0.000 0.000 0.311 0.227 1cpt 0.814 0.847 0.776 0.425 0.388 0.184 0.277 0.777 0.688 1lvl 0.799 0.836 0.726 0.783 0.539 0.620 0.688 0.614 0.678 1pamA 0.798 0.812 0.623 0.576 0.530 0.393 0.386 0.566 0.702 1ped 0.878 0.895 0.835 0.773 0.696 0.651 0.647 0.741 0.749 2myr 0.822 0.895 0.825 0.840 0.443 0.727 0.750 0.894 0.786 4enl 0.844 0.869 0.739 0.122 0.213 0.096 0.092 0.384 0.224 Bảng 5.6 Kết quả chạy của các chương trình với các sequence của nhĩm 2. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 74 0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Testcase (Nhĩm 2) Đ ộ ch ín h xá c MASPR CLUSTALW HMMT Hình 5.2 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và HMMT Nhĩm 3: Bảng 5.7 liệt kê độ chính xác của các chương trình khi thực hiện việc tính tốn MSA với tồn bộ dữ liệu nhĩm 3 MSAPR CLUS TALW SAGA DIALI GN HMMT SB_PI MA ML_PI MA MULTA LIGN PILEU P8 1idy 0.506 0.591 0.364 0.000 0.227 0.000 0.000 0.045 0.000 1r69 0.342 0.555 0.524 0.524 0.000 0.000 0.905 0.000 0.000 1ubi 0.345 0.582 0.585 0.000 0.366 0.000 0.000 0.000 0.268 1wit 0.602 0.833 0.484 0.500 0.323 0.645 0.323 0.242 0.210 1uky 0.455 0.527 0.269 0.139 0.037 0.083 0.148 0.241 0.083 kinase 0.679 0.762 0.758 0.650 0.478 0.541 0.682 0.688 0.599 1ajsA 0.336 0.405 0.186 0.000 0.006 0.000 0.000 0.000 0.110 1 pamA 0.764 0.783 0.579 0.683 0.169 0.546 0.590 0.546 0.754 1ped 0.721 0.808 0.646 0.641 0.172 0.450 0.507 0.665 0.722 2myr 0.440 0.636 0.494 0.272 0.101 0.278 0.494 0.253 0.310 4enl 0.762 0.799 0.672 0.050 0.050 0.393 0.438 0.652 0.498 Bảng 5.7 Kết quả chạy của các chương trình với các sequence của nhĩm 3. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 75 0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 8 9 10 11 Testcase(Nhĩm 3) Đ ộ ch ín h xá c MSAPR CLUSTALW HMMT Hình 5.3 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và HMMT Nhĩm 4: Bảng 5.8 liệt kê độ chính xác của các chương trình khi thực hiện việc tính tốn MSA với tồn bộ dữ liệu nhĩm 4. MSAPR CLUSTALW SAGA DIALI GN SB_PI MA ML_PI MA MULTA LIGN PILEU P8 1dynA 0.313 0.566 0.000 0.600 0.600 0.600 0.000 0.000 1pysA 0.482 0.558 0.250 0.750 1.000 1.000 0.000 0.750 1ckaA 0.436 0.823 0.375 1.000 1.000 0.000 0.000 1.000 1csp 0.358 0.498 0.000 0.889 0.000 0.000 0.000 0.000 1lkl 0.707 0.718 0.000 1.000 1.000 1.000 0.000 1.000 1mfa 0.580 0.500 0.385 1.000 0.846 1.000 0.385 1.000 1ycc 0.783 0.785 0.485 0.727 0.970 0.818 0.485 0.455 2abk 0.470 0.469 0.000 1.000 0.471 0.471 0.000 0.471 kinase1 0.807 0.873 0.000 1.000 1.000 1.000 0.000 1.000 Bảng 5.8 Kết quả chạy của các chương trình với các sequence của nhĩm 4 0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 8 9 Testcase(Nhĩm 4) Đ ộ ch ín h xá c MSAPR CLUSTALW SAGA Hình 5.4 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW, SAGA. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 76 Nhĩm 5 Bảng 5.9 liệt kê độ chính xác của các chương trình khi thực hiện việc tính tốn MSA với tồn bộ dữ liệu nhĩm 5. MSAPR CLUSTALW SAGA DIALI GN SB_PIM A ML_PI MA MULTA LIGN PILEU P8 1pysA 0.590 0.580 0.429 0.762 0.190 0.762 0.429 0.190 1eft 0.236 0.459 0.000 0.579 0.000 0.000 0.000 0.211 1ivy 0.785 0.818 0.735 1.000 1.000 0.882 0.735 1.000 1qpg 0.839 0.903 0.521 1.000 1.000 1.000 1.000 1.000 1thm1 0.714 0.706 0.765 0.765 0.765 0.412 0.412 0.765 1thm2 0.755 0.852 0.774 1.000 0.194 0.194 0.774 0.645 2cba 0.744 0.769 0.767 1.000 0.533 0.767 0.550 0.600 S51 0.627 0.796 0.831 0.646 0.338 0.631 0.646 0.646 S52 0.857 0.902 1.000 1.000 0.515 0.515 1.000 0.515 kinase1 0.807 0.817 0.484 0.806 0.677 0.677 1.000 0.677 kinase2 0.698 0.812 0.667 0.667 0.556 0.444 0.333 0.689 kinase3 0.609 0.777 0.729 0.812 0.333 0.583 0.646 0.729 Bảng 5.9 Kết quả chạy của các chương trình với các sequence của nhĩm 5 0 0.2 0.4 0.6 0.8 1 1.2 1 2 3 4 5 6 7 8 9 10 11 12 Testcase(Nhĩm 5) Đ ộ ch ín h xá c MSAPR CLUSTALW SAGA Hình 5.5 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW, SAGA Như vậy thơng qua kết quả kiểm thử các chương trình trên 5 nhĩm dữ liệu của BAliBASE, MSAPR cho kết quả chạy ổn định, sự chênh lệch về độ chính xác(với MSA của BAliBASE) so với CLUSTALW là chấp nhận được. So với các chương trình cịn lại MSAPR cũng cho những kết quả đánh giá khá tốt và khả quan. Chương trình chạy tốt cho cả tập dữ liệu cĩ độ dài các sequence nhỏ, cũng như với các tập dữ liệu cĩ độ dài trung bình và lớn. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 77 Phần tiếp theo chúng ta sẽ xem xét về thời gian chạy cũng như vấn đề sử dụng bộ nhớ. 5.3.3. So sánh về mặt thời gian chạy, bộ nhớ Như đã trình bày ở phần thuật tốn, chương trình MSAPR nhắm đến việc tăng độ chính xác của chương trình, cũng như giảm thiểu bộ nhớ sử dụng nên so sánh về mặt thời gian MSAPR cĩ thời gian chạy lâu hơn so với CLUSTALW. Khi các sequence cĩ chiều dài nhỏ(50-100 phần tử), thời gian chạy của CLUSTALW và MSAPR là tương đương, khi các sequence cĩ chiều dài trung bình thì thời gian chạy giữa MSAPR và CLUSTALW chênh nhau khoảng 1,5 lần. Khi các sequence cĩ chiều dài lớn, thời gian chạy cĩ thể chênh lệch từ 3-4 lần. Hầu hết các MSA trong BAliBASE cĩ ít hơn 50 sequence, do đĩ thời gian chạy thường dao động từ 10 giây đến 10 phút, tùy theo chiều dài của các sequence. Khi xét tập sequence lớn từ 100 đến 500 sequence, thời gian chạy của chương trình dao động trong khoảng từ 3 giờ đến 15 giờ. 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 S ố s e q u e n c e Th ờ i g ia n (p hú t) M S A P R C L U S T A L W Hình 5.6 So sánh thời gian thực thi của MSAPR và CLUSTALW Xét về bộ nhớ sử dụng, như đã đề cập trong phần thiết kế giải thuật, chương trình hạn chế tối đa việc cấp phát bộ nhớ. Xét trên tập kết quả từ 5 nhĩm dữ liệu của BAliBASE, MSAPR chiếm dụng từ 3.5MB đến 10MB bộ nhớ. Đây là một kết quả khá tốt về mặt quản lý bộ nhớ. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 78 Chương 6. KẾT LUẬN Sinh tin học(Bioinformatics) đang cĩ những bước phát triển đột phá, và từng bước trở thành một ngành khoa học cĩ vai trị vơ cùng quan trọng trong sự phát triển của nhân loại. Được đánh giá là một trong 10 bài tốn lớn của Bioinformatics, từ khi được đặt ra cho đến hiện nay, bài tốn MSA đã và vẫn đang được nghiên cứu. Nhiều giải pháp được đưa ra để giải quyết bài tốn này, tuy nhiên cho đến hiện nay(2007), bài tốn MSA vẫn là một bài tốn mở, chưa cĩ một lời giải nào cĩ thể giải quyết bài tốn trọn vẹn. Đứng trên gĩc độ của một cơng trình nghiên cứu, luận văn cố gắng đưa ra một giải pháp nhằm cung cấp thêm một cách thức để giải quyết bài tốn này. Tiếp cận theo hướng kết hợp phương pháp Progressive Algorithm và một số kỹ thuật heuristic, luận văn đã tối ưu hĩa bài tốn PSA về độ chính xác, cũng như khơng gian nhớ sử dụng cho chương trình, thơng qua việc sử dụng giải thuật chia để trị kết hợp với việc sử dụng đồng thời 3 ma trận BLOSUM và các tham số về khả năng sinh gap, để phục vụ cho việc tính tốn. Cùng với việc cải thiện chất lượng bài tốn PSA, luận văn cũng đã sử dụng kết quả của bài tốn TSP để mơ tả quá trình phân hoạch cũng như gom nhĩm, để thực hiện phép tốn align cho bài tốn MSA. Với việc kết hợp những kỹ thuật này, chương trình hiện thực cho giải thuật được đề xuất đã cho kết quả khá tốt. Kiểm thử chương trình trên tập dữ liệu mẫu BAliBASE và so sánh kết quả của chương trình với một số phần mềm được đánh giá rất tốt trong việc giải quyết bài tốn MSA: CLUSTALW, SAGA, MULTALIGN,…. Về cơ bản chương trình cho lời giải cĩ độ ổn định cao, chính xác khơng thua kém CLUSTALW(phần mềm được đánh giá là cho kết quả tốt và ổn định nhất), mặc dù thời gian chạy dài hơn so với CLUSTALW tuy nhiên xét về bộ nhớ sử dụng chương trình cho kết quả sử dụng bộ nhớ khá tốt. Đây cũng là mục tiêu hướng tới của luận văn: cung cấp một giải pháp, cho phép giải bài tốn MSA cĩ độ chính xác cao, thời gian chạy chấp nhận được và tiết kiệm về mặt bộ nhớ. Thơng qua một số thử nghiệm trên một số tập dữ liệu mẫu khác, kết quả thu được của luận văn hồn tồn cĩ thể cung cấp cho các nhà sinh học một cơng cụ để giải các bài tốn MSA. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 79 Kết quả đạt được cĩ thể được mở rộng thêm để cải thiện tốc độ chạy của chương trình. Hạn chế về mặt thời gian chạy của chương trình cĩ thể được giải quyết bằng việc: ƒ Đề xuất một phương pháp song song hĩa giải thuật được nêu, và triển khai bài tốn trên một hệ thống tính tốn song song như Cluster hoặc triển khai trên hệ thống tính tốn lưới Grid. ƒ Thiết kế một giải thuật nhánh và cận nhằm tối ưu về thời gian chạy cũng như độ chính xác cho bài tốn TSP khi số đỉnh của bài tốn lớn. Với những sự mở rộng này chúng ta cĩ thể xây dựng một hệ thống tính tốn để giải quyết bài tốn MSA một cách hữu hiệu. Đây chính là hướng phát triển của luận văn. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 80 TÀI LIỆU THAM KHẢO 1. Akutsu, T., Arimura, H., and Shimozono, S., “On Approximation Algorithms for Local Multiple Alignment”, Proceedings of the fourth annual international conference on Computational molecular biology, Tokyo, Japan, 2000. 2. Attwood, T.K., Parry D.J., “Introduction to Bioinformatics”, Prentice Hall, 1999. 3. BAliBASE HomePage, 4. Bali_Score Program HomePage, 5. Bioinformatics Platform of Strasbourg, 6. Bonizzoni, P., Vedova, G.D “The complexity of multiple sequence alignment with SP-score that is a metric”, Theoretical Computer Science 2001, 259:63-79. 7. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Clifford, S., “Introduction to Algorithm”. Chapter 16, Dynamic Programming, MIT, 2001. 8. Eddy, S.R., “Multiple Alignment using Hidden Markov Model”. Proc. Int. Conf. Intell. Syst. Mol. Biol. 1995;3:114-20. 9. European Bioinformatics Institute, “CLUSTALW, CLUSTALX”, European Bioinformatics Institute HomPage, 10. Feng, D. and Doolittle, R., “Progressive alignment of amino acid sequences and construction of phylogenetic trees from them”, Method Enzymol. , 266:368-382 11. Feng, D. and Doolittle, R., “Progressive sequence alignment as a prerequisite to correct phylogenetic trees”, J. Mol. Evol , 25:351-360 12. GALib HomePage 13. Gotoh, O., “Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments”, J. Mol. Biol. 264:823-838 14. Henikoff, S. and Henikoff, J.G., “Amino acid substitution matrices from protein block”. Proc. Nat. Acd. Sci. USA. 90:10915-10919. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 81 15. Hirschberg D.S., “A linear Space Algorithm for Computing Maximal Common Subsequences”, Communication of the ACM, Volumn 18, Number 6, 1975 16. Huang, X., and Chao, K.-M,”A generalized global alignment algorithm”, Bioinformatics, Oxford University Press, Vol. 19, no. 2, 2003 pp 228–233. 17. Korostensky, C. and Gonnet,G.H. , ”Near Optimal Multiple Sequence Alignments using a Traveling Salesman Problem approach”. Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware Page, 1999, pp 105. 18. Korostensky, C. and Gonnet, G.H. , ”Using traveling salesman problem algorithms for evolutionary tree construction”. Bioinformatics, 16:619-927, 2000. 19. Lipman, D. and Pearson, W. ,” Rapid and sensitive protein similarity searches”. Science,227:1435–1441, 1985. 20. Myers, E.W., Miller W., “Optimal alignments in linear space”.Comput Appl Biosci 1988, 4:11-17. 21. NCBI HomePage, 22. Needleman, S. B. and Wunsch, C. D. , “A general method applicable to the search for similarities in the amino acid sequence of two proteins”. Journal of Molecular Biology, 48:443–453, 1970. 23. Nicholas, H.B.Jr, Ropelewski, A.J. and Deerfield, D.W., “Strategies for multiple sequence alignment”, Biotechniques, 32:572-578. 24. Notredame, C., and Higgins, D. G., “SAGA: sequence alignment by genetic algorithm”, Nucleic Acids Research, vol. 24, no. 8, 1996, pp. 1515-1524. 25. Pearson, W.R, Miller, W. , “Dynamic programming algorithms for biological sequence comparison”. Meth. Enzymol. 210:575-601, 1992. 26. Shyu, C., “Multiple Sequence Alignment with Evolutionary Computation“ ,Genetic Programming and Evolvable Machines, Vol 5, Number 2. 2005, pp 121-144. 27. Smith, T. F. and Waterman, .M. S., “Identification of common molecular subsequences”, Journal of Molecular Biology, 147(1):195–197, Mar. 1981. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 82 28. Thompson , S.M., ”Multiple Sequence Alignment & Analysis”, Florida State University School of Computational Science and Information Technology (CSIT), 2007. 29. Thompson, J.D., Plewniak, F. and Poch, O.”A comprehensive comparision of multiple sequence alignment”, Nucleic Acids Res., 27:2682-2690. 30. Tompa, M. ”Alignment by Dynamic Programming”, 31. TSPBIB HomePage, 32. Wang, L. and Jiang, T., “On the complexity of multiple sequence alignment”. Journal of Computationa Biology, 1994, pp 337–348. 33. Wallace I.M., Blackshields G., Higgins D.G., “Multiple sequence alignments” Curr Opin Struct Biol 2005, 15:261-266. 34. Wayama, W., Takahashi, K., and Shimizu, T., “An approach to amino acid sequence alignment using a genetic algorithm”. Genome Informatics, vol. 6, 1995, pp. 122-123. 35. Yang, Y., “Comparative analysis of methods for multiple sequence alignment”, Stanford University, 2001. 36. Zhong, W., “Using Traveling Salesman Problem Algorithms to Determine Multiple Sequence Alignment Orders”. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 83 Phụ lục 1. Bảng đối chiếu Thuật ngữ Anh - Việt Các thuật ngữ trong Sinh học: Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt Amino Acid Acid amin, là đơn vị cấu trúc cơ bản của protein Biology Sinh học Block Khối Chromosome Nhiễm sắc thể DNA(Deoxyribonucleic Acid) Là một phân tử nucleic acid mang thơng tin di truyền mã hĩa cho hoạt động sinh trưởng và phát triển của các dạng sống. DNA chứa các gene cấu trúc.(cịn gọi là ADN) Evolution Tree Cây tiến hố Genomic Cơng nghệ gene Gene Là một đoạn DNA mang một chức năng nhất định trong quá trình truyền thơng tin di truyền Identity Giống nhau Molecular Biology Sinh học phân tử Nucleotide Nu, là các đơn phân cấu thành DNA. Gồm 4 loại A,C,G,T Parent Thế hệ cha mẹ Phylogenetic Tree Cây sinh lồi Protein Hợp chất đại phân tử được tạo thành từ rất nhiều các đơn phân là các acid amin. Protein Family Họ các protein cĩ liên quan với nhau RNA(Ribonucleic Acid) Là cơ sở di truyền ở cấp độ phân tử(cịn gọi là ARN) Sequence Chuỗi trình tự Secondary Structure of Proteins Cấu trúc bậc 2 của Protein Similarity Tương đồng Transmembrane protein Loại Protein nối liền các lớp màng nhầy. Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 84 Tertiary Structure of Proteins Cấu trúc bậc 3 của Protein Các thuật ngữ trong chuyên ngành(Sinh tin học): Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt Align Thực hiện so sánh(giĩng hàng, giĩng cột) 2 hay nhiều trình tự. BAliBASE benchmark Dữ liệu kiểm thử BAliBASE BAliScore Độ chính xác của MSA so với MSA mẫu của BAliBASE Bioinformatics Sinh tin học BLOSUM Matrix Ma trận BLOSUM Center Star Algorithm Giải thuật chọn phần tử trung tâm Circular Tour Chu trình, lời giải bài tốn TSP Crossover Phép lai ghép Deletion Sự mất đi các phần tử Deletion gap Các gap được sinh ra bằng cách xĩa đi các phần tử của sequence. Divide and Conquer Algorithm Giải thuật chia để trị Distance Matrix Ma trận khoảng cách Dynamic Programming Quy hoạch động Execution Time Thời gian thực thi FASTA Chuẩn định dạng FASTA lưu trữ các sequence Fitness Function Hàm thích nghi Feng-Doolittle Algorithm Giải thuật của Feng-Doolittle GALib Thư viện hàm cho phép thiết kế, hỗ trợ lập trình các ứng dụng về thuật giải di truyền Gap Phần tử sinh ra trong quá trình so sánh các trình tự Gap Open Penalty Khả năng mở gap Gap Extension Penalty Khả năng mở rộng của gap Genetic Algorithm-GA Giải thuật di truyền Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 85 Gene Finding Problem Bài tốn tìm gene Global Sequence Alignment Phép so sánh trình tự theo hướng tồn cục Guide Tree Cây mơ tả quá trình so sánh của các sequence Heuristic Các kỹ thuật trong Trí tuệ nhân tạo, giúp giải quyết các bài tốn 1 cách tự nhiên. Insertion Sự thêm vào các phần tử Insertion gap Các gap được sinh ra do sự thêm các phần tử vào sequence Iterative Algorithm Giải thuật tìm MSA bằng cách sinh ra 1 MSA cĩ chất lượng thấp và cải tiến dần theo các bước lặp Local Sequence Alignment Phép so sánh trình tự theo hướng cục bộ Match Sự tương ứng, phù hợp giữa 2 thành phần của 2 sequence MSF Chuẩn định dạng MSF lưu trữ các MSA Multiple Sequence Alignment-MSA So sánh đa trình tự Mutation Phép đột biến NCBI Trung tâm quốc gia về Thơng tin Cơng nghệ sinh học của Hoa Kỳ, cung cấp ngân hàng gene, Cơ sở dữ liệu Protein, các chương trình phục vụ cho mục đích sinh học… Near Optimal MSA MSA gần tối ưu Nondeterministic Polynomial-NP Bài tốn NP, khơng thể tính với độ phức tạp đa thức Optimal MSA Phép so sánh đa trình tự tối ưu(tốt nhất) Order for Alignment Thứ tự so sánh của các sequence Pairwise Distance Khoảng cách của các cặp sequence Pairwise Sequence Alignment-PSA So sánh 2 trình tự Progressive Algorithm Giải thuật tìm MSA thơng qua việc sử dụng bài tốn PSA nhiều lần PMX(Partially Mapped Crossover) Kỹ thuật lai ghép từng phần Population Quần thể Scoring Function Hàm đánh giá Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 86 Scoring Matrix Ma trận đánh giá Scoring Method Phương pháp đánh giá Selection Phép chọn lọc Sequence Trình tự Sequence Alignment So sánh trình tự Subtitution Sự thay thế Sum of Pair Phương pháp đánh giá theo tổng các cặp trình tự Traceback Quá trình tìm alignment từ các vết Traveling Salesman Problem-TSP Bài tốn người bán hàng Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 87 Phụ lục 2. Từ viết tắt Tên viết tắt Tên đầy đủ BLOSUM Block Substitution Matrix BAliBASE Benchmark Alignment DataBase CSDL Cơ sở dữ liệu DNA Deoxyribonucleic Acid GA Genetic Algorithm FASTA Fast Alignment Search Tool HMM Hidden Markov Model MSA Multiple Sequence Alignment NCBI National Center for Biotechnology Information NP Nondeterministic Polynomial NST Nhiễm Sắc Thể PSA Pairwise Sequence Alignment RNA Ribonucleic Acid SP Sum of Pair TSP Traveling Salesman Problem Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 88 Tham khảo Chỉ mục A amino acid, 6, 9, 10, 12, 13, 14, 16, 17, 20, 21, 25, 38 Average Information Content, 17 B BAliBase, 3 BaliScore, 69 Bioinformatics, iii, 1, 70, 78 block, 13 C Center Star Alignment, 33, 37 Circular Tour, 51, 52, 53, 54, 55, 56 CLUSTALW, 19, 40, 41, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78 Crossover, 57 Chromosome, 1, 57, 58, 59, 60 D DIALIGN, 19, 69, 70, 71, 72, 73, 74, 75, 76 Distance Matrix, 51, 53, 61, 65 Divide and Conquer Algorithm, 5, 43, 65 DNA, 1, 2, 6, 7, 10, 19 Dynamic Programming, 2, 18, 19, 24 E Entropy, 17 Execution Time, v, 43, 68, 77, 78, 79 F FASTA, 19, 63, 69 Feng-Doolittle Algorithm 4, 38, 39, 40 fitness function, 58 G Gap, 11, 14, 15 deletion, 11, 27, 28 insertion, 11, 27, 28 Gap Extension Penalty, 15 Gap Open Penalty, 15 gene, 1, 2, 6, 7, 10, 19, 57, 59, 60 Gene Finding Problem, 6 Genetic Algorithm, 5, 21, 57 Genomic, 1 Giải thuật 1A, 51 Giải thuật 1B, 55, 57 Giải thuật cải tiến khơng gian nhớ, 29 Gotoh Algorithm, 28 Guide Tree, 40, 54 H heuristic, 2, 3, 4, 18, 20, 23, 24, 33, 40, 62, 78 Hidden Markov Model, 19, 21 HMMT, 22, 69, 70, 71, 72, 73, 74, 75 I Identity, 6, 68, 71 Iterative Algorithm, 18, 19 M ML_PIMA, 69, 70, 71, 72, 73, 74, 75, 76 MSAPR, 60, 66, 67, 68, 69, 70, 72, 74, 75, 76, 77 MSF, 64, 69 MULTAL, 19, 69, 70, 71, 72 MULTALIGN, 19, 40, 69, 70, 71, 72, 73, 74, 75, 76, 78 Mutation, 58 N NCBI, 3, 63 Near Optimal Alignment, 3, 18 NP, 2, 18, 23, 51, 62 nucleotide, 9, 10, 12, 17, 21, 25 O Oder for Alignment, 5, 50, 51, 52, 54, 58, 61, 62 Optimal Alignment, 11, 24, 25, 26, 33, 36, 43, 44, 47 P Pairwise Distance, 40, 49 Parent, 57 Phylogenetic Tree, 1 PILEUP, 19, 40 PMX(Partially-Mapped Crossover), 59 Population, 21, 57, 58, 59 Progressive Algorithm 2, 3, 4, 18, 19, 23, 24, 37, 39, 40, 41, 49, 50, 52, 70, 78 protein, 1, 2, 6, 7, 9, 10, 13, 14, 19, 66, 67, 68, 69 protein family, 9 R RNA, 1, 6, 7, 83 S SAGA, 21, 69, 70, 71, 72, 73, 74, 75, 76, 78 SB_PIMA, 69, 70, 72, 73, 74, 75, 76 Scoring function, 5, 7, 12, 13, 14, 15, 16, 17, 20, 22, 25, 32, 34, 36, 38, 39, 40, 44, 48 Scoring Matrix BLOSUM, 3, 5, 13, 14, 47, 48, 61, 65, 78 Chemical Similarity Matrix, 13 Genetic Code Matrix, 13 Identity Matrix, 13 Các kỹ thuật tốn học cho bài tốn so sánh đa trình tự Phạm Mạnh Hùng Trang 89 Subtitution Matrix, 13 Scoring Method, 15 Sum-of-Pair, 16, 18, 32, 40, 50 Selection, 58 Sequence Alignment Global, 7 Local, 7 Multiple, 2, 3, 4, 5, 9, 10, 13, 16, 17, 18, 19, 20, 21, 22, 23, 24, 32, 33, 34, 37, 39, 41, 42, 49, 50, 60, 61, 62, 63, 65, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79 Pairwise, 2, 3, 4, 5, 7, 8, 15, 18, 23, 24, 25, 26, 33, 34, 35, 37, 38, 42, 43, 44, 48, 49, 51, 53, 57, 60, 61, 65, 78 Similarity, 7, 12, 13, 14, 16, 17, 39, 40, 51, 68 Substitution, 10, 14 T Tertiary Structure of Protein, 6, 9, 68 Traceback, 20, 26, 27, 45 transmembrane protein, 68 Traveling Salesmans Problem(TSP), 3, 5, 50, 51, 52, 53, 55, 57, 59, 60, 62, 65, 78, 79 ._.