Phương Pháp Tối Ưu Đàn Kiến Dóng Hàng Hai Đồ Thị Nén: Nghiên Cứu Chi Tiết Trong Luận Văn Thạc Sĩ

Luận văn thạc sĩ nghiên cứu phương pháp tối ưu đàn kiến áp dụng trong bài toán dóng hàng hai đồ thị compressed, mang lại hiệu quả cao.

• Tác giả: Đỗ Xuân Quyền
• Người hướng dẫn: TS. Đỗ Đức Đông
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phương Pháp Tối Ưu Đàn Kiến Dóng Hàng Hai Đồ Thị
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Tóm tắt

I. Giới thiệu về bài toán dóng hàng hai đồ thị

Bài toán dóng hàng hai đồ thị là một vấn đề quan trọng trong lý thuyết đồ thị và tin sinh học. Nó giúp xác định tính tương đồng giữa hai đồ thị, đặc biệt là trong việc phân tích các mạng tương tác protein (PPI). Bài toán này được chứng minh là thuộc lớp NP-khó, với nhiều ứng dụng thực tiễn trong sinh học và khoa học máy tính. Phương pháp tối ưu đàn kiến (ACO) được đề xuất như một cách tiếp cận metaheuristic để giải quyết bài toán này một cách hiệu quả.

1.1. Mục tiêu và ý nghĩa

Mục tiêu của bài toán là tìm một đơn ánh từ tập đỉnh của đồ thị này sang tập đỉnh của đồ thị kia sao cho cực đại hóa một hàm mục tiêu nhất định. Hàm mục tiêu này thường kết hợp giữa sự tương đồng về cấu trúc đồ thị và sự tương đồng giữa các nút. Bài toán có ý nghĩa lớn trong việc phân tích các mạng PPI, giúp xác định các protein tương đồng giữa các loài sinh vật khác nhau.

1.2. Các phương pháp tiếp cận hiện nay

Hiện nay, có hai hướng tiếp cận chính: dóng hàng cục bộ và dóng hàng toàn cục. Các phương pháp như IsoRank, SPINAL và FastNA đã được đề xuất để giải quyết bài toán này. Trong đó, SPINAL và FastNA là hai phương pháp được đánh giá cao về hiệu quả và tốc độ thực thi.

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

Phương pháp tối ưu đàn kiến (ACO) là một kỹ thuật metaheuristic dựa trên hành vi tìm kiếm thức ăn của loài kiến trong tự nhiên. ACO được áp dụng rộng rãi trong các bài toán tối ưu tổ hợp, đặc biệt là các bài toán NP-khó. Trong bài toán dóng hàng hai đồ thị, ACO được sử dụng để tìm kiếm lời giải tối ưu bằng cách mô phỏng quá trình kiến di chuyển và để lại dấu vết pheromone trên đồ thị.

2.1. Nguyên lý hoạt động của ACO

ACO hoạt động dựa trên nguyên lý kiến di chuyển trên đồ thị và để lại pheromone trên các cạnh. Các kiến sẽ chọn đường đi dựa trên lượng pheromone và thông tin heuristic. Pheromone được cập nhật sau mỗi vòng lặp, giúp tăng cường khả năng tìm kiếm lời giải tốt hơn.

2.2. Ứng dụng ACO trong bài toán dóng hàng hai đồ thị

Trong bài toán dóng hàng hai đồ thị, ACO được sử dụng để tìm kiếm một đơn ánh tối ưu giữa các nút của hai đồ thị. Thuật toán ACO sẽ xây dựng một đồ thị cấu trúc, sử dụng thông tin heuristic để hướng dẫn kiến di chuyển, và cập nhật pheromone dựa trên chất lượng của lời giải tìm được.

III. Thực nghiệm và đánh giá

Thực nghiệm được thực hiện trên các bộ dữ liệu PPI của các loài sinh vật như Saccharomyces cerevisiae, Drosophila melanogaster, Caenorhabditis elegans và Homo sapiens. Kết quả thực nghiệm cho thấy phương pháp tối ưu đàn kiến đạt được hiệu quả cao hơn so với các phương pháp truyền thống như SPINAL và FastNA, cả về chất lượng lời giải và thời gian thực thi.

3.1. So sánh với SPINAL và FastNA

Kết quả thực nghiệm cho thấy ACO vượt trội hơn SPINAL và FastNA về cả hai tiêu chí: Global Network Alignment Score (GNAS) và Edge Correctness (EC). Đặc biệt, ACO cho thấy khả năng hội tụ nhanh hơn và tìm được lời giải tốt hơn trong thời gian ngắn hơn.

3.2. Phân tích kết quả

Phân tích kết quả cho thấy ACO có khả năng tìm kiếm lời giải tối ưu một cách hiệu quả nhờ cơ chế cập nhật pheromone và sử dụng thông tin heuristic. Điều này giúp ACO vượt qua được các hạn chế của các phương pháp truyền thống, đặc biệt là trong việc xử lý các đồ thị có kích thước lớn.

IV. Kết luận và hướng phát triển

Phương pháp tối ưu đàn kiến đã chứng minh được hiệu quả trong việc giải quyết bài toán dóng hàng hai đồ thị. Với khả năng tìm kiếm lời giải tối ưu và thời gian thực thi nhanh, ACO là một phương pháp tiềm năng trong lĩnh vực tin sinh học và lý thuyết đồ thị. Hướng phát triển trong tương lai có thể bao gồm việc cải tiến thuật toán ACO để xử lý các đồ thị có cấu trúc phức tạp hơn và ứng dụng trong các bài toán thực tế khác.

4.1. Giá trị thực tiễn

ACO không chỉ có giá trị trong lý thuyết mà còn có nhiều ứng dụng thực tiễn, đặc biệt là trong việc phân tích các mạng PPI và các bài toán tối ưu tổ hợp khác. Phương pháp này có thể được áp dụng trong các lĩnh vực như y sinh, dược phẩm và công nghệ sinh học.

4.2. Hướng phát triển

Trong tương lai, có thể nghiên cứu cải tiến ACO bằng cách kết hợp với các kỹ thuật học máy hoặc tối ưu hóa đa mục tiêu để nâng cao hiệu quả của thuật toán. Ngoài ra, việc ứng dụng ACO trong các bài toán thực tế khác cũng là một hướng nghiên cứu đầy tiềm năng.

Trích đoạn nội dung tài liệu

MỞ ĐẦU Tin sinh học là một lĩnh vực khoa học mới rất đƣợc quan tâm trong hơn thập kỷ gần đây, với sự phát triển của khoa học công nghệ, mối liên kết giữa sinh học và tin học trở lên khăng khít hơn, Tin học hỗ trợ cho việc giải quyết các bài toán với dữ liệu lớn của Sinh học, đồng thời đó cũng là một hƣớng phát triển mới của ngành Tin học về giải thuật và ứng dụng. 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ó [4] 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ị. Phƣơng pháp tố i ƣu đàn kiế n (Ant Colony Optimization - ACO) là cách tiế p câ ̣n metaheuristic , đƣơ ̣c giới thiê ̣u bởi Dorigo năm 1991 đang đƣợc nghiên cứu và ứng dụng rộng rãi cho các bài toán tối ƣu tổ hợp khó.

Chính vì vậy tác giả chọn đề tài khoa học phương pháp tối ưu đàn kiến dóng hàng hai đồ thị. Thực nghiệm, tác giả sẽ sử dụng bộ dữ liệu vào Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 2 (Input) mà Spinal và FastNA đã dùng, từ đó sẽ đánh giá và so sánh kết quả ra để thấy đƣợc hiệu quả của phƣơng pháp tác giả đề xuất với những phƣơng pháp có trƣớc, cụ thể là so sánh với hai phƣơng pháp tốt nhất hiện nay Spinal và FastNA. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 3 CHƢƠNG I DÓNG HÀNG HAI ĐỒ THỊ VÀ CÁC PHƢƠNG PHÁP TIẾP CẬN HIỆN NAY 1. Bài toán dóng hàng hai đồ thị Giả sử 𝐺1 = (𝑉1 , 𝐸1 ) và 𝐺2 = (𝑉2 , 𝐸2 ) là hai mạng tƣơng tác protein (đơn đồ thị), trong đó 𝑉1 , 𝑉2 ký hiệu tập các nút mô tả các protein trong mạng 𝐺1 , 𝐺2 tƣơng ứng;𝐸1 , 𝐸2 ký hiệu tập các cạnh mô tả mối quan hệ tƣơng tác giữa các protein trong các mạng 𝐺1 , 𝐺2.

Không giảm tổng quát, ta xem 𝑉1 ≤ 𝑉2 trong đó 𝑉 ký hiệu số phần tử của tập 𝑉. Dóng hàng mạng là tìm một đơn ánh từ 𝑉1 vào 𝑉2 tốt nhất theo một tiêu chí đánh giá nào đó. Hiện nay chƣa có định nghĩa rõ ràng cho tiêu chí này, dƣới đây phát biểu toán học cho định nghĩa bài toán dóng hàng theo tiêu chí thông dụng đã đƣợc dùng trong [4,5,6,12,27]. (Dóng hàng mạng) Đồ thị 𝐴12 = (𝑉12 , 𝐸12 ) là một mạng dóng hàng của hai đồ thị𝐺1 , 𝐺2 nếu nó thỏa mãn: i) Mỗi nút của 𝑉12 đƣợc ký hiệu là < 𝑢𝑖 , 𝑣𝑗 > tƣơng ứng với một cặp đỉnh 𝑢𝑖 thuộc 𝑉1 và 𝑣𝑗 thuộc 𝑉2.

ii) Hai nút phân biệt< 𝑢𝑖 , 𝑣𝑗 > và < 𝑢𝑖′ , 𝑣𝑗′ > thuộc 𝑉12 thì𝑢𝑖 ≠ 𝑢𝑖′ và 𝑣𝑗 ≠ 𝑣𝑗′ iii) Cạnh(< 𝑢𝑖 , 𝑣𝑗 >, < 𝑢𝑖′ , 𝑣𝑗′ >) thuộc 𝐸12 nếu và chỉ nếu (𝑢𝑖 , 𝑢𝑖′ ) ∈ 𝐸1 và (𝑣𝑖 , 𝑣𝑖′ ) ∈ 𝐸2. (Dóng hàng mạng toàn cục) Một dóng hàng 𝐴12 = (𝑉12 , 𝐸12 ) là lời giải của bài toán dóng hàng toàn cục của các mạng proteins 𝐺1 , 𝐺2 nếu nó cực đại global network alignment score cho bởi Eq(1.1) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 trong đó ∈ [0,1] là tham số cân bằng giữa sự tƣơng đồng về tô pô mạng và sự tƣơng đồng trình tự giữa các nút, giá trị 𝑆𝑖𝑚𝑖𝑙𝑎𝑟 𝑢𝑖 , 𝑣𝑗 đƣợc tính xấp xỉ dựa trên BLAST bit-scores hoặc E-values. Trong [4] Aladag và Erten đã chứng minh bài toán tìm dóng hàng tối ƣu này là NP-hard. Một số phƣơng pháp tiếp cận hiện nay Từ khi bài toán đƣợc đề xuất, các kỹ thuật dóng hàng mạng PPI phát triển theo hai hƣớng: dóng hàng cục bộ và dóng hàng toàn cục.

Với dóng hàng cục bộ, mục tiêu sẽ là xác định các mạng con gần nhau về tô pô mạng hoặc tƣơng tự xâu [11,23,27]. Thông thƣờng, kết quả của dóng hàng cục bộ sẽ thể hiện nhiều mạng con chồng lấn nhau, điều này có thể dẫn đến sự nhập nhằng khi một protein có thể đƣợc dóng hàng với nhiều protein khác. Để khắc phục nhƣợc điểm đó dóng hàng mạng toàn cục sẽ tìm ra một đơn ánh mà mỗi protein của mạng PPI này chỉ dóng với một protein ở mạng PPI kia. IsoRank [4,28] đƣợc Sing et al.

đề xuất năm 2008 là một trong những thuật toán dóng hàng mạng toàn cục đầu tiên, nó đƣợc phát triển dựa trên dóng hàng cục bộ. Ý tƣởng chính của IsoRank là hai nút đƣợc dóng hàng với nhau, nếu các nút kề với chúngtƣơng ứng đƣợc dóng hàng.Thuật toán bao gồm hai giai đoạn chính, thứ nhất thực hiện với mỗi nút i (𝑖 ∈ 𝑉1 | 𝑖 = 1. |𝑉1 |) phải duyệt tất cả nút j (𝑗 ∈ 𝑉2 | 𝑗 = 1. |𝑉2 |) để tìmđiểm sốdóng hàng Ri,j cho từng cặp nút i và j, theo 1 Ri , j    | N (u) | .2) uN ( i ) vN ( j ) ở công thức trênN(x) là tập tất cả các nút láng riềng của x.

Kết quả của giai đoạn này cho ta một ma trận giá trị (điểm số dóng hàng)R tƣơng ứng với mọi cặp nút<i,j> (𝑖 ∈ 𝑉1 ,𝑗 ∈ 𝑉2 ).Giai đoạn thứ hai, từ ma trận R tìm ra một cách sắp xếp (ghép) từng cặp i,j (𝑖 ∈ 𝑉1 ,𝑗 ∈ 𝑉2 ) sao cho tổng điểm số dóng hàng là Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 tốt nhất.Việc này đƣợc cho là đơn giản vì nó chỉ là cách sắp xếp hai đồ thị dựa trên mức độ tƣơng tự giữa các nút. Sau IsoRank, một số thuật toán tƣơng tự đã đƣợc đề xuất nhƣ PATH và GA [35], PISwap [6,7] nhờ đƣa thêm các nới lỏng thích hợp của hàm đánh giá trên tập các ma trận ngẫu nhiên hoặc ứng dụng tìm kiếm cục bộ trên dóng hàng lời giải có sẵn từ một thuật toán khác. Các thuật toán này đều đƣa ra kết quả nhanh và tốt hơn so với các thuật toán trƣớc đó. Tuy nhiên, những thuật toán đã nêu chỉ tối ƣu cho độ chính xác (hàm mục tiêu) hoặc tính khả mở (scalability ).

Vì các mạng PPI có thƣờng số đỉnh lớn nên cả tính chính xác và tính khả mở (thời gian chạy ) cần đƣợc quan tâm. Gần đây, đã xuất hiện những thuật cho kết quả tốt với độ phức tạp thời gian đa thức điển hình là SPINAL và FastNA sẽ đƣợc giới thiệu và tìm hiểunhiều hơn. SPINAL Năm 2013 Aladag và Erten đề xuất thuật toán SPINAL [4], thuật toán này cho kết quả tốt nhất theo tiêu chí đánh giá của công thức (1.1) và nhanh nhất tính đến thời điểm nó ra đời. SPINAL là một thuật toán heuristic thời gian đa thức, gồm hai pha: Pha đầu tính điểm tƣơng đồng cho tất cả cặp protein theo công thức P ( xi , y j )  deg ( x )  deg ( y ) ( xi , y j )C T( ui ,v j )     (1   )  seq (ui , v j ) G1 i G2 j (1.3) C trong đó∈ [0,1] là tham số cân bằng giữa sự tƣơng đồng về tô pô mạng và sự tƣơng đồng trình tự giữa các nút, degG ( xi ) , deg G ( y j ) tƣơng ứng là 1 2 bậc của xi và yj trong G1 và G2,và seg(ui,vj) đƣợc tính xấp xỉ dựa trên BLAST bit-scores hoặc E-values.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 6 Pha sau xây dựng đơn ánh xạ bằng cách cải tiến một cách cục bộ từng tập con của lời giải hiện có. Algorithm 1:SPINAL global alignment algorithm 1: Input: G1  (V1 , E1 ), G2  (V2 , E2 ), seg ,  2: Output: Node set V12 of the global alignment network A12 3: // Coarse-grained 4: for all ui  V1 , v j V2 do 5: P(ui , v j )    DegDiff (ui , v j )  (1   )  seg (ui , v j ) 6: endfor 7: repeat 8: P '  P 9: for all ui  V1 , v j V2 do 10: construct NBG({  u i , v j  }, P ') 11: construct contributors set C of NBG 12: comput P (ui , v j ) as in Equation(2) 13:endfor 14:until enough iterations 15:// Fine-grained 16: SP  List of  ui , v j  sorted w.t P, for u i V1 , v j V2 17:repeat 18: // Find new connected component in A12 19: pop unaligned  ui , v j  from SP, insert into V12 20:repeat 21: Construct NBG(V12 , P) 22: Construct contributors set C of NBG 23: Swap improvements for each NBG edge not in C 24: Insert  xi , y j  into V12, for each ( xi , y j )  C 25:until no contributors 26:until no unaligned pair in SP Hình 1.1: Thuật toán SPINAL Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.4) trong đó k là số lần chạy của vòng lặp chính (thuật toán hội tụ với số vòng lặp từ 10-15 trong các trƣờng hợp thử nghiệm), ∆1, ∆2 lần lƣợt là bậc lớn nhất của đỉnh trong đồ thị G1, G2 Thực nghiệm trên các tập dữ liệu Saccharomyces cerevisiae, Drosophila melanogaster, Caenorhabditis elegans and Homo sapiens cho thấy SPINAL tốt hơn hai thuật toán IsoRank và MI-GRAAL, là hai thuật toán tốt nhất đến lúc đó. FastNA Năm 2013, Tiến sĩ Đỗ Đức Đông và một số đồng nghiệp thuộc Viện Công nghệ thông tin, Đại học Quốc giađã đề xuất một thuật toán mới là FastNA đểdóng hàng toàn cục mạng PPI.