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 loà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ưhoàn toà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 đã hoà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ự đoá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 toán học cho bài toá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ự đoá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 loà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 10 14 và mỗi tếbào mang khoảng 3.10 9 ký tựtrong đoạn DNA của chúng. Bài toá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 toá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ự đoá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 toán so sánh nhiều trình tự được đặt ra nhưvấn đềtất yếu. Không nhưbài toán so sánh 2 trình tự, bài toán so sánh nhiều trình tự(Multiple Sequence Alignment-MSA) là một bài toá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 toá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 toán cụthể. Progressive Algorithm là một hướng giải quyết tốt cho bài toá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 toá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 toán học cho bài toá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 toá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 toán vẫn là động lực thúc đẩy nhiều công trình khoa học vềbài toán này. Xuất phát từnhững đặc điểm của bài toá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 toán MSA, các phương pháp giải quyết bài toá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 toá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 toán MSA nói riêng. ƒ Phân loại các phương pháp giải quyết bài toá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 toán MSA dựa trên việc cải thiện, tối ưu hoá bài toá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 toán PSA sửdụng Progressive Algorithm kết hợp với lời giải của bài toá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.