Luận văn ThS: Phương pháp tối ưu đàn kiến dóng hàng hai đồ thị

173 lượt xem
Share

Luận văn Phương pháp tối ưu đàn kiến dóng hàng hai đồ thị tìm hiểu dóng hàng hai đồ thị, các phương pháp tiếp cận hiện nay; phương pháp tối ưu đàn kiến và thựuc nghiệm.

Mục lục nội dung

Luận văn ThS: Phương pháp tối ưu đàn kiến dóng hàng hai đồ thị

1. Mở đầu

Dóng hàng hai đồ thị là một bài toán quan trọng trong lý thuyết đồ thị, nó giúp chúng ta xác định tính tương đồng của hai đồ thị. Về mặt sinh học nó giúp xác định tính tương đồng giữa các mạng tƣơng tác protein.Hiện nay có nhiều tiêu chí về cách đánh giá cho dóng hàng. Một cách đánh giá thường được sử dụng hiện nay là đánh giá dựa trên lực lượng của tập cạnh (sự tương đồng về cấu trúc) và sự tương đồng giữa các nút. Dóng hàng hai đồ thị được Aladag và Erten chứng minh là bài toán thuộc lớp NP - khó và có nhiều ứng dụng. Đặc biệt, trong những năm gần đây, với sự phát triển của các kỹ thuật sinh học công nghệ cao đã cho phép các nhà nghiên cứu xây dựng được các mạng tương tác protein (Protein-Protein Interraction Network – PPI Network) tương đối đầy đủ cho nhiều loài sinh vật. Bài toán dóng hàng mạng PPI là một bài toán quan trọng trong phân tích mạng PPI nói chung.Các mạng tương tác protein được mô tả bằng đồ thị, bài toán dóng hàng mạng được chuyển tải về bài toán dóng hàng đồ thị.

2. Nội dung

2.1 Dóng hàng hai đồ thị

Bài toán dóng hàng hai đồ thị

Một số phương pháp tiếp cận hiện nay 

  • SPINAL 
  • FastNA

2.2 Phương pháp tối ưu đàn kiến

Từ kiến tự nhiên đến kiến nhân tạo

  • Kiến tự nhiên
  • Kiến nhân tạo

Phương pháp ACO cho bài toán tối ưu tổ hợp tổng quát

  • Đồ thị cấu trúc
  • Mô tả thuật toán ACO tổng quát 

Một số vấn đề liên quan 

  • Đặc tính hội tụ 
  • Thực hiện song song
  • ACO kết hợp với tìm kiếm cục bộ
  • Thông tin heuristic 
  • Số lượng kiến 
  • Tham số bay hơi 

Tính biến thiên của vết mùi và các thuật toán cập nhật mùi

  • Thuật toán tổng quát
  • Quy tắc chuyển trạng thái 
  • Cập nhật mùi

Đánh giá

  • Tính khai thác và khám phá
  • Các thuật toán cập nhật mùi theo quy tắc ACS
  • Các thuật toán cập nhật mùi theo quy tắc MMAS 
  • Ưu điểm khi sử dụng SMMAS và 3-LAS
  • Tính bất biến.

2.3 Giải bài toán dóng hàng hai đồ thị

Thuật toán tối ưu đàn kiến giải bài toán dóng hàng hai đồ thị

  • Xây dựng đồ thị cấu trúc thích hợp 
  • Chọn thông tin heuristic
  • Cập nhật mùi

Thực nghiệm, so sánh kết quả với phương pháp SPINAL và FastNA

  • Thực nghiệm
  • So sánh

3. Kết luận

ACOPPI là phương pháp metaheuristic cho bài toán dóng hàng hai đồ thị, có ý nghĩa trong sinh học là cung cấp thông tin giúp phát hiện chức năng của các protein. Ngoài ra còn bổ sung thêm vào lý thuyết đồ thị một phương pháp mới cho bài toán dóng hàng đồ thị. Thực nghiệm cho thấy so với các phương pháp heuristic trước đây, thấy thuật toán đề xuất có tính ổn định và có điểm dóng hàng, số cạnh khớp vượt trội so với SPINAL và tốt hơn đáng kể so với FastNA.

4. Tài liệu tham khảo

Đỗ Đức Đông và Hoàng Xuân Huấn (2011), “Về biến thiên của vết mùi trong phương pháp ACO và các thuật toán mới”, Tạp chí Tin học và điều khiển học, Tập 27, tr. 263-275.

Đỗ Đức Đông, Phương pháp tối ưu đàn kiến và ứng dụng - Luận án tiến sỹ tin học Đại học Công nghệ thông tin - Đại học quốc gia Hà Nội, 2012.

Lê Sỹ Vinh, Giáo trình Tin sinh học – Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. 2014

Aladag,A.E. and Erten,C. (2013), SPINAL: scalable protein interaction network alignment. Bioinformatics, Vol. 29 no 7, 917–924

B. Doerr, F. Neumann, D. Sudholdt, and C. Witt (2007), On the influence of pheromone updates in ACO algorithms, Technical Report CI-223/07, University of Dortmund,SFB 531

Chindelevitch,L. et al. (2010), Local optimization for global alignment of protein interaction networks. In: Pacific Symposium on Biocomputing,Hawaii,USA, pp. 123–132....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn Thạc sĩ trên ---

173 lượt xem
Share
Ngày:28/08/2020 Chia sẻ bởi:
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM