Luận án tiến sĩ công nghệ thông tin một số thuật toán dóng hàng các mạng protein

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ MỘT SỐ THUẬT TOÁN DÓNG HÀNG CÁC MẠNG PROTEIN LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN NGỌC HÀ MỘT SỐ THUẬT TOÁN DÓNG HÀNG CÁC MẠNG PROTEIN Chuyên ngành: Khoa học máy tính Mã số: 9480101.01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1.TS Hoàng Xuân Huấn 2. Thái Trà My Hà Nội - 2019 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào khác.

Tác giả 1 LỜI CẢM ƠN Luận án được thực hiện tại trường ĐH Công nghệ - ĐHQG Hà Nội, dưới sự hướng dẫn của PGS.TS Hoàng Xuân Huấn và GS.TS Thái Trà My. Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Hoàng Xuân Huấn, cô Thái Trà My, những người đã có những định hướng giúp tôi thành công trong việc nghiên cứu của mình. Thầy cũng đã động viên và chỉ bảo giúp tôi vượt qua những khó khăn để tôi hoàn thành được luận án này. Tôi xin chân thành cảm ơn tới TS.

Đỗ Đức Đông, TS. Đặng Cao Cường và các thầy cô ở Bộ môn Khoa học máy tính trường Đại học Công nghệ đã đóng góp cho tôi nhiều kiến thức quý báu về kiến thức khoa học để tôi có thể hoàn thành luận án. Tôi cũng xin cảm ơn tới các thầy, cô thuộc khoa Công nghệ thông tin – Trường ĐH Công Nghệ, đã tạo mọi điều kiện thuận lợi giúp tôi trong quá trình làm nghiên cứu sinh. Tôi cũng xin cảm ơn tới các thầy cô ở khoa Toán, và lãnh đạo trường Đại học Sư Phạm – Đại học Thái Nguyên, đã tạo mọi điều kiện thuận lợi về mặt thời gian và công tác chuyên môn giúp tôi trong quá trình làm nghiên cứu sinh.

Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè nơi đã cho tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay. 2 MỤC LỤC DANH MỤC BẢNG BIỂU. 7 DANH MỤC CÁC HÌNH. 9 DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT.

DÓNG HÀNG CÁC MẠNG PROTEIN VÀ TỐI ƯU MỀM. Tin sinh học và dóng hàng các mạng protein. Bài toán dóng hàng nhiều mạng các vị trí liên kết protein. Bài toán dóng hàng mạng tương tác protein - protein.

Bài toán tối ưu tổ hợp và tiếp cận mềm. Phương pháp tối ưu đàn kiến. Tính toán tiến hóa và các thuật toán memetic. Thuật toán tìm kiếm Tabu.

Động cơ nghiên cứu. Kết luận chương. DÓNG HÀNG CÁC MẠNG CÁC VỊ TRÍ LIÊN KẾT PROTEIN. Bài toán dóng hàng nhiều đồ thị.

Tập nhiều đồ thị. Dóng hàng nhiều đồ thị. Hàm đánh giá chất lượng dóng hàng. Thuật toán dựa trên ACO.

Đồ thị cấu trúc. Thủ tục bước ngẫu nhiên để xây dựng một dóng hàng. Qui tắc cập nhật mùi. Thủ tục tìm kiếm cục bộ.

Thuật toán theo lược đồ memetic. Đồ thị cấu trúc. Vết mùi và thông tin heuristic. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng.

Qui tắc cập nhật vết mùi. Thủ tục tìm kiếm cục bộ. Thuật toán memetic mới kết hợp ACO và tìm kiếm Tabu. Đồ thị cấu trúc.

Thông tin heuristic. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng. Qui tắc cập nhật vết mùi. Thủ tục tìm kiếm Tabu.

Các kết quả thực nghiệm. Dữ liệu thực nghiệm. Thực nghiệm so sánh thuật toán ACO-MGA với thuật toán Greedy và GAVEO. Thực nghiệm so sánh các thuật toán ACOTS-MGA, ACO-MGA2, GAVEO và Greedy.

Kết luận chương. DÓNG HÀNG TOÀN CỤC HAI MẠNG TƯƠNG TÁC PROTEIN-PROTEIN. Bài toán dóng hàng toàn cục mạng tương tác protein. Phát biểu bài toán.

Đánh giá chất lượng dóng hàng toàn cục. Thuật toán FASTAN. Xây dựng dóng hàng ban đầu. Thủ tục Rebuild.

Độ phức tạp của thuật toán FASTAN so với SPINAL. Thuật toán ACOGNA. Đồ thị cấu trúc. Vết mùi và thông tin heuristic.

Thủ tục bước ngẫu nhiên để xây dựng dóng hàng. Quy tắc cập nhật vết mùi. Thủ tục tìm kiếm cục bộ. Thuật toán ACOGNA++.

Mô tả thuật toán. Thủ tục xác định cặp đỉnh dóng hàng. Quy tắc cập nhật vết mùi. Thủ tục tìm kiếm cục bộ.

Kết quả thực nghiệm. Dữ liệu thực nghiệm. Thực nghiệm so sánh thuật toán FASTAN với thuật toán SPINAL. Thực nghiệm so sánh thuật toán ACOGNA với các thuật toán FASTAN và MAGNA++.

Thực nghiệm so sánh thuật toán ACOGNA++ với các thuật toán ACOGNA, MAGNA++ và ModuleAlign. Kết luận chương. 113 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN. 117 TÀI LIỆU THAM KHẢO.

118 6 DANH MỤC BẢNG BIỂU Bảng 2. So sánh chất lượng dóng hàng S(A) và thời gian chạy với các bộ dữ liệu gồm 4, 8, 16 và 32 đồ thị, số đỉnh trung bình của mỗi đồ thị là 20 đỉnh. So sánh chất lượng dóng hàng S(A) và thời gian chạy với các bộ dữ liệu gồm 4, 8, 16 và 32 đồ thị, số đỉnh trung bình của mỗi đồ thị là 50 đỉnh. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 20 đỉnh và thời gian chạy là 50s.

So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 20 đỉnh và thời gian chạy là 150s. So sánh điểm chất lượng dóng hàng S(A)với các bộ dữ liệu là 8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 20 đỉnh và thời gian chạy là 200s. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4, 8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời gian chạy là 200s. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4, 8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời gian chạy là 300s.

So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4, 8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời gian chạy là 600s. So sánh chất lượng lời giải của các thuật toán với các tập dữ liệu gồm 4, 8, 16 và 32 đồ thị. So sánh thời gian chạy (tính theo giây) của các thuật toán với các tập dữ liệu gồm 4, 8, 16 và 32 đồ thị. So sánh điểm chất lượng dóng hàng S(A) của 3 thuật toán với cùng thời gian chạy với các tập gồm 4,8,16 và 32 đồ thị.

Mô tả bộ dữ liệu. So sánh thuật toán FASTAN và thuật toán Spinal theo các hàm mục tiêu GNAS và giá trị | E12| với các giá trị tham số α khác nhau. Thời gian chạy trung bình của thuật toán FASTAN (tính theo đơn vị giây) và thuật toán SPINAL khi chạy với cùng bộ dữ liệu. So sánh thuật toán ACOGNA và thuật toán FASTAN theo tiêu chuẩn GNAS và giá trị |E12| với các giá trị α khác nhau.

So sánh ACOGNA và MAGNA++ theo tiêu chuẩn EC. So sánh ACOGNA và MAGNA++ theo tiêu chuẩn S3. So sánh các thuật toán theo tiêu chuẩn S3. 109 8 DANH MỤC CÁC HÌNH Hình 1.

Quá trình tổng hợp protein. Dóng hàng cục bộ và dóng hàng toàn cục. Cách các con kiến thực chọn đường đi ngắn nhất để tha mồi về tổ 36 Hình 2. Một dóng hàng nhiều đồ thị của tập 4 đồ thị, đỉnh hình vuông là giả còn các đỉnh tròn là đỉnh thực có nhãn là các ký tự tương ứng.

Ví dụ dóng hàng 2-đồ thị. Đồ thị cấu trúc khi dóng hàng n đồ thị, trong đó mỗi đồ thị có 2 hoặc 3 nút thực. Kiến xây dựng lời giải. Một hoán vị cặp đỉnh có cùng nhãn trong thủ tục tìm kiếm địa phương.

So sánh chất lượng lời giải các thuật toán với bộ dữ liệu gồm 16 đồ thị và thời gian tăng từ 1000s đến 6000s. Đồ thị cấu trúc của thuật toán ACOGNA. So sánh thời gian chạy tính theo giây của 2 thuật toán ACOGNA++ và MAGNA++. 110 9 DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Viết tắt, SốTT Tiếng Việt Tiếng Anh ký hiệu 1 Tối ưu hóa đàn kiến Ant Colony Optimization ACO 2 Giải thuật di truyền Genetic Algorithm GA 3 Bài toán người chào hàng Travelling Salesman Problem TSP 4 Tối ưu tổ hợp Combinatorial Optimization TƯTH 5 Bầy ong nhân tạo Artificial Bee Colony ABC 6 Tối ưu bầy đàn Particle Swarm Optimization PSO 7 Hệ đàn kiến Ant Colony System ACS 8 Hệ kiến Ant System AS 9 Hệ kiến max - min Max – Min Ant System MMAS 10 Hệ kiến max – min trơn Smooth Max – Min Ant System SMMAS 11 Tương tác protein Protein – Protein Interaction PPI 12 Sự chính xác về cạnh Edge Correctness EC 13 Bảo tồn cấu trúc cảm sinh Induced Conserved Structure ICS 14 Điểm cấu trúc con đối xứng Symmetric substructure score S3 15 Điểm dóng hàng toàn cục Global Network Aligment Score GNAS 16 Nấm men Saccharomyces Cerevisiae SC 17 Ruồi giấm Drosophila Melanogaster DM 10 18 Người tinh khôn Homo Sapiens HS 19 Giun tròn Caenorhabditis Elegans CE 20 Dóng hàng nhiều đồ thị Multigraph Alignment MGA 11 MỞ ĐẦU Những phát hiện về cơ chế di truyền trong cơ thể sống đã thúc đẩy sinh học phân tử nói riêng và công nghệ sinh học nói chung phát triển mạnh mẽ trong nửa thế kỷ qua, trở nên lĩnh vực nghiên cứu và ứng dụng hấp dẫn.

Tuy nhiên các nghiên cứu trong phòng thí nghiệm đòi hỏi nhiều thời gian và tốn kém. Cùng với sự phát triển của công nghệ thông tin, tin-sinh học [Junker, B & Schreiber, 2008; M.Lesk, 2002] ra đời và là công cụ trợ giúp hiệu quả cho các nghiên cứu sinh-y-dược. Ngày nay, người ta hiểu rõ rằng các protein trong mỗi cơ thể sống quyết định các đặc điểm sinh học quan trọng như kiểu hình, hệ miễn dịch… và việc tổng hợp chúng được quy định bởi DNA hay là các bộ gene tương ứng theo quá trình biểu diễn gene.