Bài viết này giới thiệu một thuật toán metaheuristics hiệu quả, ACOPPI, để dóng hàng mạng PPI. Thuật toán ứng dụng phương pháp tối ưu đàn kiến xây dựng dóng hàng và kết hợp tìm kiếm cục bộ. Thực nghiệm cho thấy thuật toán đề xuất có điểm dóng hàng tốt hơn so với các thuật toán SPINAL, FastNA đã công bố. | Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR 9 Cần Thơ ngày 4-5 8 2016 DOI PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN DÓNG HÀNG TOÀN CỤC CÁC MẠNG TƯƠNG TÁC PROTEIN Đỗ Xuân Quyền1 Nguyễn Hoàng Đức2 Thái Đình Phúc2 Đỗ Đức Đông2 1 Trƣờng THPT Quang Trung Hải Phòng 2 Trƣờng đại học Công nghệ Đại học Quốc gia Hà Nội xuanquyenck13b@ dongdoduc@ TÓM TẮT Dóng hàng toàn cục các mạng tương tác protein PPI cung cấp thông tin giúp phát hiện các chức năng của protein vì vậy bài toán này đang được nghiên cứu rộng rãi. Bài báo này giới thiệu một thuật toán metaheuristics hiệu quả ACOPPI để dóng hàng mạng PPI. Thuật toán ứng dụng phương pháp tối ưu đàn kiến xây dựng dóng hàng và kết hợp tìm kiếm cục bộ. Thực nghiệm cho thấy thuật toán đề xuất có điểm dóng hàng tốt hơn so với các thuật toán SPINAL FastNA đã công bố. Từ khóa Protein-protein interraction network ant colony optimization. I. GIỚI THIỆU Cách tiếp cận trƣớc đây để phát hiện các chức năng của protein là dựa trên các quan hệ tiến hóa với tiêu chí thƣờng đƣợc sử dụng là độ tƣơng tự giữa các trình tự 3 23 . Tuy nhiên chỉ tính tƣơng đồng trình tự thƣờng không đủ để nhận dạng các phức hợp protein đƣợc bảo tồn 12 24 26 . Sự phát triển của các kỹ thuật công nghệ sinh học trong hơn thập kỷ qua đã cho phép xây dựng đƣợc các mạng tƣơng tác protein Protein-Protein Interraction Network PPI Network cho nhiều loài sinh vật. Từ các dữ liệu này một số bài toán về phân tích mạng PPI đã đƣợc đặt ra xem 5 8 15-17 chẳng hạn nhƣ phân tích cấu trúc tô pô mạng 10 phát hiện mô-đun 4 . Trong đó đặc biệt quan trọng là các bài toán dóng hàng mạng PPI dựa trên kết hợp thông tin về sự tƣơng tác giữa các protein cùng với mối quan hệ tiến hóa giữa các trình tự. Việc so sánh tính tƣơng đồng của các mạng PPI này cung cấp nhiều thông tin hữu ích cho dự đoán các chức năng chƣa biết hoặc kiểm định các chức năng đã biết của các .
