Giải thuật lai cho bài toán sắp hàng đa trình tự sinh học

Tóm tắt

Việc phân tích các trình tự sinh học như DNA, Protein để có được thông tin hữu ích từ sự tương đồng giữa các trình tự là một việc vô cùng quan trọng. Hiện nay có nhiều phương pháp giải quyết bài toán này, tuy nhiên các kết quả xác định mức tương đồng thường được đánh giá chưa tốt lắm. Trong bài báo này chúng tôi đưa ra một giải pháp kết hợp GA-SA (Genetic Algorithm – Simulated Annealing) với mong muốn có thể dung hòa được các yêu cầu đặt ra, đó là thời gian đáp ứng và chất lượng của lời giải. Quá trình giải quyết bài toán được thực hiện qua các bước như sử dụng các thông tin về tiến hoá giữa các trình tự ; một số luật heuristic để tạo thông tin ban đầu, qua đó điều chỉnh hướng lai tạo, chọn lọc của quần thể trong giải thuật di truyền. Bên cạnh đó, một phần quần thể cũng bị tác động bởi quá trình “mô phỏng luyện kim” SA giúp tìm được các cá thể mới tốt hơn.