BÀI TOÁN TÌM KIẾM MOTIF VÀ PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN

Abstract

Tin sinh học có ứng dụng cao trong cuộc sống, đặc biệt trong lĩnh vực y – dƣợc. Về cơ bản, tin sinh học tập trung vào nghiên cứu và áp dụng các phƣơng pháp cũng nhƣ các kĩ thuật trong tin học để giải quyết các bài toán trong sinh học phân tử. Tìm kiếm motif trong các chuỗi gene là một trong những bài toán quan trọng nhất của tin sinh học và thuộc loại NP-khó. Các thành phần điều hòa gene (gene regulatory elements) đƣợc gọi là các DNA motif (về sau gọi là motif cho gọn), chúng chứa nhiều thông tin sinh học quan trọng. Vì vậy việc nhận dạng DNA motif đang là một trong những bài toán quan trọng nhất trong tin sinh học và thuộc loại NP-khó. Chủ yếu, có 2 cách tiếp cận để tìm kiếm motif: các phƣơng pháp thực nghiệm và các phƣơng pháp tính toán. Vì chi phí cao và tốn thời gian nên các phƣơng pháp thực nghiệm ít hiệu quả. Phƣơng pháp tính toán đang đƣợc dùng rộng rãi cho dự đoán motif. Ngƣời ta đƣa ra nhiều phát biểu cho bài toán tìm kiếm motif, và có nhiều thuật toán nghiên cứu và công bố giải quyết bài toán tìm kiếm motif. Trong luận văn này, tôi trình bày bài toán (ℓ,d) motif. Có nhiều thuật toán đƣa ra để giải quyết bài toán (ℓ,d) motif, các thuật toán này có thể chia thành 2 loại đó là thuật toán chính xác và thuật toán xấp xỉ. Các thuật toán chính xác luôn luôn tìm ra những motif trong những chuỗi DNA đầu vào nhƣng chỉ hiệu quả với các dữ liệu có kích thƣớc nhỏ và thực hiện mất nhiều thời gian. Các thuật toán xấp xỉ có thể không tìm ra đƣợc tất cả các motif nhƣng nó chạy hiệu quả với các dữ liệu lớn. Luận văn đề xuất giải quyết bài toán (ℓ,d) motif theo thuật toán xấp xỉ, bằng việc đề xuất thuật toán tối ƣu đàn kiến Ant colony optimization (ACO) để giải quyết bài toán (ℓ,d) motif. Đây là thuật toán mới và lần đầu đƣợc đƣa vào để giải bài toán (ℓ,d) motif. Thuật toán đƣợc đặt tên là F-ACOMotif. Và trong thực nghiệm đã chỉ ra đƣợc thuật toán F-ACOMotif tối ƣu hơn các thuật toán PairMotif+ và MEME về độ chính xác khi tìm ra (ℓ,d) motif.