Tóm tắt Luận án Một số thuật toán dóng hàng các mạng protein

a lần lặp để cập nhật mùi. Một phép hoán vị hai đỉnh cùng nhãn A được minh họa trong hình 2.3 2.3. Thuật toán theo lược đồ memetic 2.3.1. Lược đồ chung Sau khi khởi tạo các tham số và các kiến nhân tạo, thuật toán ACO-MGA2 thực hiện các vòng lặp theo 2 giai đoạn như mô tả trong thuật toán 2.1. Giai đoạn đầu trong mỗi vòng lặp, các kiến xây dựng lời giải trên đồ thị cấu trúc dựa trên thông tin heuristic và vết mùi. Sau đó lời giải tốt nhất của các kiến được lựa chọn để cập nhật vết mùi theo quy tắc cập nhật mùi SMMAS, đồng thời cập nhật lại lời giải tốt nhất toàn cục. Giai đoạn 2 của thuật toán, trong mỗi vòng lặp, sau khi các kiến xây dựng xong các lời giải, 2 kỹ thuật tìm kiếm cục bộ được áp dụng để tìm lời giải tốt nhất của mỗi vòng lặp. Thuật toán 2.1: Thuật toán ACO-MGA2 Input: Tập các đồ thị G ={G1(V1,E1),,Gn(Vn,En) Output: Dóng hàng tốt nhất cho tập đồ thị G:    1( ) ... ( )nA V V       Begin Khởi tạo; Hình 2.3. Một hoán vị cặp đỉnh có trong thủ tục Local Search 11 while (Chưa thỏa mãn điều kiện dừng) do for each a A do Kiến a xây dựng một dóng hàng cho tập các đồ thị; Tìm kiếm cục bộ trên lời giải tốt nhất //Chỉ áp dụng ở giai đoạn 2 //Tìm kiếm bằng cách đổi vị trí của các đỉnh khác nhãn. //Tìm kiếm bằng cách đổi vị trí của các đỉnh cùng nhãn. Cập nhật vết mùi theo quy tắc SMMAS; Cập nhật lại lời giải tốt nhất; End for; End while; Lưu lại lời giải tốt nhất; End; 2.3.2. Đồ thị cấu trúc Đồ thị cấu trúc của thuật toán ACO-GMA2 được sử dụng giống như thuật toán ACO-MGA. 2.3.3. Vết mùi và thông tin heuristic Vết mùi 𝜏𝑗,𝑘 𝑖 kết nối đỉnh j của đồ thị Gi với đỉnh k ở đồ thị Gi+1 được khởi tạo bằng 𝜏𝑚𝑎𝑥 và được cập nhật lại sau các vòng lặp. Thông tin Heuristic 𝜂𝑗,𝑘 𝑖 (𝑎)được tính bởi công thức 2.8. , ( , ) 1 ( ) 1 . i j k max count k a k i n a nV       lµ ®Ønh thùc k lµ ®Ønh gi¶ (2.8) Trong đó count(k,a) là số lượng đỉnh trên véc tơ {a1,ai} có nhãn trùng với nhãn của đỉnh k trong trường hợp k là đỉnh thực, Vmax là số lượng đỉnh của đồ thị có nhiều đỉnh nhất.. 2.3.4. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng Tại mỗi vòng lặp, mỗi kiến sẽ lặp lại quá trình xây dựng véc tơ a = (a1,, an) cho dóng hàng A tương tự như thuật toán ACO-MGA. 2.3.5. Qui tắc cập nhật vết mùi Thuật toán ACO-MGA2 sử dụng quy tắc cập nhật vết mùi SMMAS nhưng cải tiến so với thuật toán ACO-MGA ở điểm thuật toán ACO-MGA2 sử dụng 2 giá trị của tham số  ở 2 giai đoạn khác nhau. Giai đoạn đầu không sử dụng tìm kiếm địa phương nên tham số  được thiết lập nhỏ hơn để khai thác thông tin học tăng cường, còn giai đoạn 2 khi áp dụng tìm kiếm cục bộ thì tham số này được thiết lập lớn hơn để tăng tính khám phá. 2.3.6. Thủ tục tìm kiếm cục bộ Thủ tục tìm kiếm cục bộ thực hiện tuần tự trên đồ thị G1 đến đồ thị Gn theo nguyên tắc tìm được kết quả tốt nhất thì dừng. Thủ tục này gồm hai kỹ thuật: đổi các đỉnh cùng nhãn và đổi các đỉnh khác nhãn. 1) Đổi các đỉnh khác nhãn. Đổi vị trí trên cặp vectơ dóng hàng tương ứng với mỗi cặp đỉnh khác nhãn của đồ thị Gi đang xét nếu việc đổi chỗ đó làm tăng số lượng các đỉnh cùng nhãn trên các vector dóng hàng. 2) Đổi các đỉnh cùng nhãn. Đổi vị trí trên cặp vectơ dóng hàng tương ứng với mỗi cặp đỉnh tcùng nhãn của đồ thị Gi đang xét nếu việc đổi vị trí đó cải thiện độ phù hợp của trọng số ở các cạnh liên quan. Nếu sau khi đổi chỗ, hàm đánh giá chất lượng tăng lên thì lời giải nhận được sẽ thay thế cho lời giải tốt nhất lúc đó. Quá trình này được lặp lại cho đến khi tìm được lời giải tốt nhất. Vì thủ tục tìm kiếm cục bộ tốn thời gian nên chỉ áp dụng cho giai đoạn hai, khi lời giải tốt nhất tìm được đủ tốt. 2.4. Thuật toán memetic mới kết hợp ACO và Tabu Search 2.4.1. Đồ thị cấu trúc Đồ thị cấu trúc của thuật toán ACOTS-MGA được sử dụng giống như thuật toán ACO-MGA2. 12 2.4.2. Thông tin heuristic Heuristic information 𝜂𝑗,𝑘 𝑖 (𝑎) là số điểm cạnh tính theo công thức (2.3) khi đỉnh k của đồ thị Gi+1 được dóng với đỉnh j của đồ thị Gi 2.4.3. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng Tại mỗi vòng lặp, mỗi kiến sẽ lặp lại quá trình xây dựng các véctơ dóng hàng a = (a1,, an) cho dóng hàng A như sau: Kiến lựa chọn ngẫu nhiên một đỉnh thực ở tầng 1 là đỉnh khởi tạo. Tại các tầng tiếp theo, ký hiệu (a)label là tập các nhãn của các đỉnh thuộc véctơ dóng hàng a, gọi { | (v) (a)}i iB v G label label   là tập các đỉnh thuộc đồ thị Gi có nhãn trùng với nhãn của các đỉnh thuộc véctơ dóng hàng. Trong trường hợp không có đỉnh nào có nhãn trùng với nhãn của các đỉnh đã được dóng hàng, Bi sẽ là tập các đỉnh còn lại chưa được dóng hàng. Kiến sẽ lựa chọn ngẫu nhiên 1 đỉnh trong Bi với xác suất được cho ở công thức 2.9. Để dễ hình dung, giả sử véctơ dóng hàng đã được xây dựng từ đỉnh a1 của đồ thị G1 và thực hiện thủ tục bước ngẫu nhiên để phát triển đến đỉnh ai của đồ thị Gi khi đó sẽ lựa chọn đỉnh thứ k thuộc đồ thị Gi +1 với xác suất là: 1 , , , , , ( ) . (a)] ( ) .[ (a)] i i i j k j ki j k i i j s j ss B p            (2.9) Sau khi xây dựng đầy đủ véctơ a=(a1,,an), các đỉnh thực thuộc véctơ này sẽ bị loại bỏ khỏi đồ thị cấu trúc để tiếp tục quá trình xây dựng các véctơ dóng hàng cho đến khi tất cả các đỉnh đều được dóng hàng. 2.4.4. Qui tắc cập nhật vết mùi Khác với thuật toán ACO-MGA2, việc cập nhật mùi của ACOTS-MGA được thực hiện theo các công thức 2.10 và 2.11. , , ,(1 ) i i i j k j k j k     (2.10) , . . . max i j k mid min (i,j,k) (i,j,k)              lêi gi¶i tèt nhÊt lêi gi¶i tèt nhÊt vßng lÆp tr­êng hîp kh¸c (2.11) Các tham số max,min và ∈ (0,1) được khởi tạo tương tự như thuật toán ACO-MGA2. Trong thuật toán ACOTS-MGA luận án sử dụng thêm tham số mid để cập nhật mùi trong trường hợp lời giải mới mà các kiến tìm được là lời giải tốt nhất của vòng lặp nhưng chưa phải là lời giải tốt nhất toàn cục. Tham số này được thiết lập nhỏ hơn max với ý nghĩa là lời giải tốt nhất toàn cục sẽ để lại lượng vết mùi lớn hơn so với lời giải tốt nhất của vòng lặp. 2.4.5. Thủ tục tìm kiếm Tabu Trong các vòng lặp cuối của thuật toán ACOTS-MGA, thuật toán Tabu Search được áp dụng để tăng cường chất lượng lời giải. Thủ tục tìm kiếm Tabu sẽ duyệt lần lượt các đỉnh của các đồ thị, với mỗi đồ thị sẽ thực hiện việc hoán vị các cặp đỉnh trên các vector dóng hàng. Nếu việc hoán vị này làm tăng điểm đánh giá thì lời giải tốt nhất sẽ được cập nhật bằng lời giải hiện tại. Khác với thủ tục tìm kiếm thông thường, thủ tục Tabu Search này có sử dụng một danh sách Tabu để lưu lại các bước chuyển. Các bước chuyển nằm trong danh sách Tabu sẽ không được xét lại nữa để tránh lặp lại các bước chuyển. Một khác biệt nữa so với thuật toán ACO-MGA2 là thủ tục tìm kiếm cục bộ của ACO-MGA2 chỉ được gọi một lần trong mỗi vòng lặp, còn trong thuật toán ACOTS-MGA, thủ tục tìm kiếm được gọi lặp lại nhiều lần cho đến khi không cải thiện được chất lượng lời giải nữa. 2.5. Các kết quả thực nghiệm 2.5.1. Dữ liệu thực nghiệm Khi đánh giá hiệu quả các thuật toán, việc lựa chọn dữ liệu là rất quan trọng, để đảm bảo sự khách quan, luận án sử dụng lại các bộ dữ liệu thực đã được sử dụng để đánh giá hiệu quả của các thuật toán tham lam do Weskamp và thuật toán GAVEO do Thomas Fober đề xuất. Các công trình do 2 tác giả đề xuất đã được đăng 13 tải trên các tạp chí uy tín nên bộ dữ liệu thực nghiệm được lựa chọn có thể đảm bảo về độ tin cậy và khách quan. Dữ liệu thực nghiệm bao gồm 74 cấu trúc sinh ra từ cơ sở dữ liệu Cavbase. Mỗi cấu trúc biểu diễn cho một protein cavity thuộc họ protein của thermolysin, vi khuẩn protease thường được sử dụng trong phân tích cấu trúc protein và được chú thích với số hiệu EC 3.4.24.27 trong cơ sở dữ liệu enzyme. Trong bộ dữ liệu này, mỗi đồ thị sinh ra có từ 42 đến 95 đỉnh. Từ 74 cấu trúc đó, các đồ thị được lựa chọn ngẫu nhiên để sinh ra các tập dữ liệu gồm 4, 8, 16, 32 đồ thị để tiến hành chạy thực nghiệm các thuật toán. 2.5.2. 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 nhằm so sánh ACO-MGA với hai thuật toán Greedy và thuật toán tiến hóa GAVEO về chất lượng lời giải và thời gian chạy. Các thực nghiệm bao gồm: 1) Chạy các thuật toán trên cùng một bộ dữ liệu với số vòng lặp định trước để so sánh về chất lượng dóng hàng và thời gian chạy. 2) Chạy các thuật toán trên cùng một bộ dữ liệu với cùng một thời gian định trước để so sánh về chất lượng dóng hàng. Các thí nghiệm của chúng tôi được thực hiện trên máy tính có cấu hình: CPU Dual Core 2.2Ghz, RAM DDR3 3GB trên hệ điều hành Windows XP SP3. Đối với thuật toán ACO-MGA, sau khi tiến hành thực nghiệm với các giá trị khác nhau của từng tham số, chúng tôi thấy rằng với các giá trị của các tham số như dưới đây sẽ cho kết quả lời giải tốt nhất, vì vậy trong các thực nghiệm các tham số của thuật toán được thiết lập như sau: Số kiến trong mỗi lần lặp là 20, =0.06, 𝛼 = 𝛽 = 1, max = 1.0 và min = max/(n2*Vmax2), trong đó n là số đồ thị, Vmax là số đỉnh của đồ thị có nhiều đỉnh nhất. Trong thời gian đầu tiến hành nghiên cứu bài toán MGA, do chưa có dữ liệu thực, chúng tôi sinh ngẫu nhiên các tập dữ liệu thực nghiệm là các tập đồ thị với các đồ thị có 20 và 50 đỉnh, số đồ thị lần lượt là 4,8,16 và 32. Bảng 2.1 và bảng 2.2 dưới đây là kết quả so sánh các thuật toán ACO-MGA, GAVEO và Greedy về điểm chất lượng dóng hàng (score) và thời gian chạy của các thuật toán. Bảng 2.1 là kết quả dóng hàng ứng với các đồ thị có trung bình là 20 đỉnh và bảng 2.2 là kết quả ứng với các đồ thị có trung bình là 50 đỉnh. Các kết quả tốt hơn được thể hiện bằng chữ in đậm, thời gian chạy ngắn hơn được thể hiện bằng chữ in nghiêng, đậm. Bảng 2.1. So sánh chất lượng dóng hàng và thời gian chạy với các bộ dữ liệu gồm 4, 8, 16 và 32 đồ thị, trung bình mỗi đồ thị có 20 đỉnh. Thuật toán/Số đồ thị 4 8 16 32 Greedy Điểm -40 -35 -570 -1055 Thời gian (s) 0.6 2.3 6 17 GAVEO Điểm -20 65 45 1132 Thời gian (s) 249 501 1087.7 2484.1 ACO- MGA Điểm 124 696 1480 7289 Thời gian (s) 33.6 231.5 481.2 1266 Bảng 2.2. So sánh kết quả chất lượng dóng hàng và thời gian chạy với các bộ dữ liệu gồm 4, 8, 16 và 32 đồ thị, trung bình của mỗi đồ thị có 50 đỉnh Thuật toán/Số đồ thị 4 8 16 32 Greedy Điểm -1144 -4704 -31004 -155508 Thời gian (s) 4.8 11.3 49 210.8 GAVEO Điểm -101 -75 -10872 -33698 Thời gian (s) 1164 2739.1 6921.3 16340.8 ACO- MGA Điểm 685 3338 1273 -18643 Thời gian (s) 763.4 6523.5 12670.5 28859.8 14 Kết quả thực nghiệm cho thấy rằng: Trong cả 2 trường hợp các đồ thị gồm 20 đỉnh và đồ thị 50 đỉnh thì thuật toán Greedy đều cho thời gian chạy rất nhanh so với 2 thuật toán còn lại. Tuy nhiên kết quả về điểm dóng hàng của thuật toán này lại rất thấp so với GAVEO và ACO-MGA. Thuật toán ACO-MGA cho kết quả điểm tốt hơn thuật toán GAVEO. Với các đồ thị 20 đỉnh, thời gian chạy của ACO-MGA nhanh hơn so với GAVEO nhưng khi số đỉnh trong đồ thị tăng lên thì thời gian chạy của GAVEO nhanh hơn khi số đồ thị vượt quá 4. Tuy nhiên, thực nghiệm ở mục sau cho thấy cùng thời gian chạy thì ACO-MGA vẫn cho kết quả tốt hơn nhiều. Vì thuật toán Greedy có thời gian chạy ngắn nhưng lại có điểm thấp nên luận án chỉ tiến hành các thí nghiệm để so sánh hiệu quả của thuật toán GAVEO và thuật toán ACO-MGA với cùng thời gian chạy. Bảng 2.3. So sánh 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 Thuật toán/Số đồ thị 8 16 32 GAVEO 74 -38 1254 ACO-MGA 690 2262 10060 Bảng 2.4. So sánh 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 Thuật toán/Số đồ thị 4 8 16 32 GAVEO -107 -77 -5282 -96123 ACO-MGA 673 2898 744 -16945 Các kết quả thực nghiệm được trình bày ở các bảng trên cho thấy khi so sánh 2 thuật toán ACO- MGA và GAVEO với cùng một bộ dữ liệu mô phỏng, trên cùng một cấu hình máy và cùng thời gian chạy thì thuật toán ACO-MGA cũng cho kết quả tốt hơn nhiều so với thuật toán GAVEO. 2.5.3. Thực nghiệm so sánh các thuật toán ACOTS-MGA, ACO-MGA2, GAVEO và Greedy Vì ACO-MGA2 được cải tiến từ ACO-MGA, với nhiều cải tiến đã được phân tích trong phần đầu của mục 2.5.1 đảm bảo thuật toán cho chất lượng lời giải tốt hơn so với ACO-MGA, nên các thực nghiệm ở đây chỉ so sánh các thuật toán ACOTS-MGA, ACO-MGA2 với hai thuật toán Greedy và thuật toán tiến hóa GAVEO về chất lượng lời giải và thời gian chạy. Các thuật toán đều được chạy lại trên máy tính có cấu hình: CPU Dual Core 3 Ghz, RAM DDR2 4GB trên hệ điều hành Windows 7. Thuật toán GAVEO sử dụng các tham số được lựa chọn như trong bài báo [Fober et al., 2009]. Đối với 2 thuật toán ACO-MGA2 và ACOTS-MGA, sau khi tiến hành thực nghiệm với các giá trị khác nhau của các tham số. Các bộ tham số mà các thuật toán cho chất lượng lời giải tốt nhất được lựa chọn. Các tham số cụ thể như sau: Thuật toán ACO-MGA2: Số kiến trong mỗi lần lặp là 30 ;1=0.3, 2=0.7, 𝛼 = 𝛽 = 1;max = 1.0 và min = max/(n 2*Vmax 2), trong đó n là số đồ thị, Vmax là số nút của đồ thị có nhiều nút nhất. Thủ tục local search được gọi trong 30% số vòng lặp cuối cùng. Thuật toán ACOTS-MGA: Số kiến trong mỗi lần lặp là 30 ; 1=0.3, 2=0.7, 𝛼 = 𝛽 = 1;max = 1.0, min = max/(n 2*Vmax 2) và mid=0.8. Thủ tục local search được gọi trong 20% số vòng lặp cuối cùng. Bảng 2.5. So sánh chất lượng dóng hàng 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ị Thuật toán/Số đồ thị 4 8 16 32 Greedy -4098 -11827 -56861 -267004 GAVEO -1224 -2729 -10604 -63205 ACO-MGA2 -972 -2277 -7857 -53960 ACOTS-MGA -963 -1089 -5671 -42216 Các kết quả thực nghiệm trong bảng 2.5 cho thấy thuật toán ACOTS-MGA cho chất lượng lời giải tốt hơn Greedy, GAVEO và ACO-MGA2 đối với cả 4 tập dữ liệu. Khi số lượng đồ thị tăng thì chất lượng lời giải của ACOTS-MGA cao hơn so với các thuật toán Greedy, GAVEO và ACO-MGA2 càng thể hiện rõ rệt hơn. 15 Luận án cũng tiến hành chạy các thuật toán trong cùng một thời gian với cả 4 tập dữ liệu thì thuật toán ACOTS-MGA đều cho kết quả tốt hơn so với GAVEO và ACO-MGA2. 2.6. Kết luận chương Trong chương này, chúng tôi trình bày các khái niệm liên quan đến bài toán dóng hàng tập gồm nhiều đồ thị và đề xuất 3 thuật toán là ACO-MGA, ACO-MGA2 và ACOTS-MGA để giải quyết bài toán dóng hàng nhiều đồ thị. Kết quả thực nghiệm trên các bộ dữ liệu mô phỏng và dữ liệu thực cho thấy các thuật toán đề xuất cho kết quả tốt hơn nhiều so với thuật toán GAVEO khi chạy với cùng bộ dữ liệu và cùng thời gian chạy. Khi số đỉnh của đồ thị tăng lên thì thời gian tìm kiếm địa phương trong ACO-MGA, ACO-MGA2 và ACOTS- MGA làm tăng thời gian chạy nên các thuật toán đề xuất chạy lâu hơn GAVEO trong một số trường hợp. Các thuật toán đề xuất dóng hàng nhiều mạng các vị trí liên kết protein cho chất lượng dóng hàng tốt hơn các thuật toán GAVEO và Greedy sẽ giúp xác định được sự tương đồng về cấu trúc của các protein chính xác hơn. Thông qua tính tương đồng về mặt cấu trúc đó có thể suy diễn chức năng của các protein chưa biết thông qua các protein đã biết [Yuan et al., 2018]. Đó chính là ý nghĩa sinh học mà các thuật toán đề xuất mang lại. Chương 3. DÓNG HÀNG TOÀN CỤC HAI MẠNG TƯƠNG TÁC PROTEIN- PROTEIN Chương này giới thiệu 3 thuật toán mà luận án đề xuất để giải bài toán dóng hàng toàn cục mạng tương tác protein là FASTAN, ACOGNA và ACOGNA++. Các thực nghiệm đã chứng minh các thuật toán này cho chất lượng lời giải tốt hơn đáng kể so với các phương pháp mới nhất hiện nay. 3.1. Bài toán dóng hàng toàn cục mạng tương tác Protein 3.1.1. Phát biểu bài toán Giả sử G1 = (V1, E1) và G2 = (V2, E2) là 2 đồ thị mô tả 2 mạng tương tác protein, trong đó V1, V2 tương ứng là tập các đỉnh của các đồ thị G1 và G2; E1, E2 à tập các cạnh tương ứng của G1, G2. Không mất tính tổng quát ta có thể giả sử 1 2| | | |V V trong đó |V| là ký hiệu cho số phần tử của tập V. Định nghĩa 3.1. Dóng hàng toàn cục 2 mạng tương tác protein là xác định một đơn ánh 1 2 :f V V trong đó mỗi đỉnh của V1 được khớp với duy nhất 1 đỉnh 2 1 2 ( )v f v V  . Trong trường hợp 1 2| | | |V V thì f là một song ánh. 3.1.2. Đánh giá chất lượng dóng hàng toàn cục Cho một dóng hàng mạng f ký hiệu 1 2 1( ) {( ( ), ( )) : ( , ) }f E f u f v E u v E   và 1 2 1( ) { ( ) : }f V f v V v V   . Các tiêu chuẩn dóng hàng được sử dụng phổ biến nhất trong các nghiên cứu về bài toán dóng hàng toàn cục mạng tương tác protein được trình bày như dưới đây: Tiêu chuẩn GNAS được Aladag giới thiệu được tính theo công thức sau: 𝐺𝑁𝐴𝑆 = 𝛼|𝑓(𝐸1)| + (1 − 𝛼) ∑ 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢))𝑢∈𝑉1 , (3.1) trong đó 𝛼 ∈ [0.1] là tham số thể hiện sự tương quan về mức độ quan trọng giữa độ tương đồng về mặt cấu trúc và sự tương đồng về mặt trình tự, 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢)) là độ đo tương tự trình tự nào đó, chẳng hạn, BLAST bit-scores hay E-values (Các giá trị này đã được tính toán trước và là dữ liệu đầu vào của một số thuật toán dóng hàng toàn cục).Ưu điểm của độ đo GNAS là thể hiện được cả mối tương quan về topology và độ tương đồng về trình tự giữa 2 đồ thị được dóng hàng. Kuchaiev và các cộng đề xuất dùng độ đo EC (Edge Correctness) như trong công thức 3.2. 1 1 ( )f E EC E  (3.2) EC là độ đo tỷ lệ của các cạnh trong đồ thị nguồn được dóng hàng chính xác đến các cạnh trong đồ thị thứ hai với số lượng cạnh của đồ thị nguồn. Giá trị EC lớn có nghĩa là hai mạng có cấu trúc tương tự nhau. Tiêu chuẩn này định lượng sự giống nhau giữa hai mạng. EC chỉ bằng 100% khi và chỉ khi đồ thị thứ hai G2 chứa một bản sao đẳng cấu của G1 16 Khi dóng hàng một mạng có mật độ cạnh thưa với mạng đích có mật độ cạnh dày, có nhiều cách để dóng hàng G1 với các mạng con của G2. Tuy nhiên bằng trực giác có thể thấy việc dóng hàng G1 với mạng con thưa của G2 sẽ tốt hơn so với việc dóng hàng G1 với một mạng con dày. Để “phạt” những dóng hàng những dóng hàng mà ánh xạ đồ thị G1 với một mạng con dày của đồ thị G2, Patro và các cộng sự [Patro & Kingsford, 2012] đề xuất dùng độ đo ICS (Induced Conserved Structure), độ đo ICS thể hiện tỷ lệ các cạnh của đồ thị nguồn được bảo tồn trên đồ thị đích sau khi dóng hàng (f(E1)) với số cạnh của đồ thị con của đồ thị đích được sinh ra bởi các đỉnh được dóng hàng với các đỉnh trên đồ thị nguồn (E(G2[f(V1)])). Cụ thể ICS được tính theo công thức 3.3. 1 2 1 ( ) ( [ ( )]) f E ICS E G f V  , (3.3) trong đó 𝐸(𝐺2[𝑓(𝐸1)]) là tập cạnh trong 𝐺2 của đồ thị con có tập đỉnh là 𝑓(𝑉1). Qua các công thức 3.2 và 3.3 có thể thấy, độ đo EC chú trọng đến đồ thị nguồn, trong khi độ đo ICS chú trọng đến đồ thị đích. Vì vậy độ đo EC không tốt khi đánh giá chất lượng dóng hàng nếu ta dóng hàng một mạng có mật độ cạnh thưa với một mạng có mật độ cạnh dày. Ngược lại độ đo ICS không tốt khi ta dóng hàng một mạng dày với 1 mạng thưa. Nhận thấy nhược điểm trên của 2 độ đo EC và ICS, Saraph và các cộng sự [Saraph & Milenković, 2014] đề xuất độ đo S3 như công thức 3.4. 3 1 1 2 1 1 ( ) ( [ ( )]) ( ) f E S E E G f V f E    (3.4) S3 xét đến cả số cạnh của đồ thị nguồn và số cạnh của đồ thị con được sinh ra bởi cách đỉnh của đồ thị đích được dóng hàng, vì vậy nó khắc phục được các nhược điểm của EC và ICS như đã phân tích ở trên. 3.2. Thuật toán FASTAN 3.2.1. Đặc tả thuật toán Thuật toán FASTAN gồm hai giai đoạn: giai đoạn thứ nhất xây dựng dóng hàng ban đầu và giai đoạn sau cải tiến nó nhờ thủ tục tối ưu cục bộ Rebuild. 3.2.1.1. Xây dựng dóng hàng ban đầu Cho các đồ thị G1, G2; tham số α và các độ tương tự của các cặp đỉnh tương ứng của V1, V2 là similar(i, j). Ký hiệu Vi là tập các đỉnh đã được dóng hàng của đồ thị Gi và RVi = Vi –Vi là tập các đỉnh chưa được dóng hàng của đồ thị Gi. Gọi A12= (V12, E12) là kết quả của phép dóng hàng đồ thị G1 với đồ thị G2, trong đó  12 1 2, ( ) : , ( )V i f i i V f i V     ;  12 1 2( , ( ) , , ( ) ) : ( , ) , ( ( ), ( ))E u f u v f v u v E f u f v E       Thủ tục FASTAN được thực hiện như sau: Bước 1. Xác định cặp đỉnh i ∈ V1 và j ∈ V2 có độ tương tự similar(i, j) lớn nhất. Gán f(i):=j; Khởi tạo V 1= {i};V2= {j}; Bước 2. Thực hiện lặp với k= 2 tới |𝑉1| 2.1. Tìm nút i  RV1 có số cạnh nối với các đỉnh trong 𝑉1 lớn nhất (Thủ tục này gọi là find_next_node). 2.2. Tìm f(i) = j  RV2 mà khi dóng hàng j với i thì công thức 𝛼|𝑓(𝐸1 ∗)| + (1 − 𝛼)(∑ 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢)) +𝑢∈𝑉1 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑖, 𝑗)) đạt giá trị lớn nhất. Trong đó 𝐸1 ∗ là các cạnh của đồ thị G1 có các đỉnh thuộc tập 𝑉1 ∪ 𝑖. (Thủ tục này gọi là choose_best_matched_node). 2.3. Lần lượt thêm i,j vào các tập đỉnh đã được dóng hàng V1, V2. Bước 3. Thực hiện lặp cải tiến 𝐴12 nhờ thủ tục Rebuild. Chú ý rằng ở các bước 2.1 và 2.2 có thể tìm được nhiều đỉnh tốt nhất, khi đó sẽ chọn ngẫu nhiên một đỉnh trong số đó để tạo ra sự đa dạng về lời giải trong các lần chạy khác nhau. 3.2.1.2. Thủ tục Rebuild Sau giai đoạn 1, đã xác định được dóng hàng thô A12, để tăng chất lượng của lời giải, thuật toán sử dụng thủ tục tối ưu cục bộ rebuild. Ý tưởng của thủ tục này là sử dụng một tập giống gồm nkeep những cặp đỉnh đã được dóng hàng tốt của A12, sau đó dóng hàng lại các cặp đỉnh khác, nếu lời giải mới tốt hơn sẽ thay thế cho lời giải trước đó. Chi tiết thủ tục rebuil như dưới đây. 17 Bước 1. Xây dựng SeedV12 gồm 𝑛𝑘𝑒𝑒𝑝 đỉnh của V1 có điểm tốt nhất theo tiêu chí cho bởi công thức 3.5: 𝑠𝑐𝑜𝑟𝑒(𝑢) = 𝛼. 𝑤(𝑢) + (1 − 𝛼). 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢)) (3.5) trong đó u𝑉1 và 𝑓(𝑢)𝑉2 được dóng hàng với u trong 𝐴12, w(u) là số lượng nút v thuộc V1 mà (u,v) thuộc E1 và (f(u),f(v)) thuộc E2 Bước 2. Thực hiện lặp như bước 2 của giai đoạn 1 với k = 𝑛𝑘𝑒𝑒𝑝 + 1 tới |𝑉1| để xây dựng lại A12 Sau mỗi lần thực hiện thủ tục Rebuild ta có một dóng hàng mới làm input 𝐺12cho lần lặp tiếp theo, quá trình này lặp lại cho đến khi không cải tiến được GNAS(A12) nữa. 3.2.2. Độ phức tạp của thuật toán FASTAN so với SPINAL Trong nghiên cứu của Aladag và Erten [Aladag & Erten, 2013], bài toán dóng hàng toàn cục mạng tương tác protein đã được chứng minh là NP-khó. Các tác giả cũng đã đề xuất thuật toán SPINAL có độ phức tạp với thời gian đa thức là:   1 2 1 2 1 2 SPINALComplexity O k V V log       (3.6) Trong đó k là số lần lặp chính khi chạy thuật toán, theo [Aladag & Erten, 2013] thuật toán sẽ hội tụ sau 10 đến 15 lần lặp; ∆1, ∆2 lần lượt là bậc của đỉnh thuộc các đồ thị G1 và G2 có bậc lớn nhất. Dễ dàng kiểm tra được độ phức tạp của giai đoạn 1 và mỗi bước lặp trong giai đoạn 2 của thuật toán FASTAN là: O(|V1|×(E1|+|E2|)) (3.7) Các thực nghiệm được tiến hành với các bộ dữ liệu thực nghiệm IsoBase cho thấy số lần lặp của giai đoạn 2 của thuật toán không vượt quá 20 lần. Bởi vì |V1|×∆1 ≥ E1 nên chú ý tới độ phức tạp của SPINAL trong công thức (3.6) ta có: |V1|×|V2|×∆1×∆2 ≥ E1× E2 > (|V1|×(E1|+|E2|)). (3.8) Như vậy độ phức tạp của FASTAN so với độ phức tạp của SPINAL thấp hơn nhiều. 3.3. Thuật toán ACOGNA 3.3.1. Lược đồ chung Thuật toán ACOGNA được xây dựng như dưới đây: Bước 1. Khởi tạo ma trận vết mùi, và tập A gồm m kiến. Bước 2. Thực hiện lặp trong khi chưa thoả mãn điều kiện dừng Với mỗi kiến ta tiến hành các bước sau: 2.1. Gán f(i)=j trong đó i, j là cặp đỉnh có độ tương đồng similar (i,j) lớn nhất. Khởi tạo V1 = {i}; V2 = {j}; 2.2. Thực hiện lặp với k= 2 tới 1V 2.2.1. Tìm đỉnh 1i RV có số cạnh tới các đỉnh trong 1V lớn nhất; 2.2.2. Sử dụng thuật toán ACO tìm đỉnh f(i)= 2 j RV theo thủ tục bước ngẫu nhiên (thủ tục antMove) 2.2.3. Lần lượt thêm 2 đỉnh i và j vào các tập đỉnh V1 và V2 2.3. Thực hiện tìm kiếm cục bộ trên lời giải tốt nhất do các kiến tìm được để cải thiện chất lượng lời giải. 2.4. Cập nhật lại lời giải tốt nhất. 2.5. Cập nhật vết mùi theo quy tắc SMMAS dựa trên lời giải tốt nhất. Bước 3. Lưu lại lời giải tốt nhất. Chú ý rằng ở bước 2.2.1, việc tìm 1i RV có số cạnh tới các đỉnh trong 1V lớn nhất nhằm tăng số lượng các cạnh có thể được bảo toàn sau khi dóng hàng, nếu tìm được nhiều đỉnh tốt nhất thì sẽ lựa chọn ngẫu nhiên một đỉnh tìm được để dóng hàng. 3.3.2. Đồ thị cấu trúc Đồ thị cấu trúc của thuật toán gồm 2 tầng, tầng thứ i thể hiện đồ thị iG . Các đỉnh ở tầng trên được kết nối với tất cả các đỉnh ở tầng dưới. Hình 3.1 thể hiện đồ thị cấu trúc của thuật toán ACOGNA. Khi xây dựng lời Hình 3.1. Đồ thị cấu trúc của thuật toán ACOGNA 18 giải, kiến sẽ xuất phát từ một đỉnh thuộc tầng 1 và lựa chọn dóng hàng với 1 đỉnh thuộc tầng 2 theo công thức (3.10). Một dóng hàng toàn cục của 2 đồ thị theo định nghĩa 1 là một đường đi xuất phát từ 1 đỉnh của 1G dóng với 1 đỉnh của 2G sau đó quay lại 1G rồi tiếp tục dóng với 1 đỉnh của 2G , lặp lại cho tới khi tất cả các đỉnh của 1G đã được dóng hàng. 3.3.3. Vết mùi và thông tin heuristic Vết mùi 𝜏𝑗 𝑖 trên cạnh ,i j  dóng đỉnh 1i V với đỉnh 2j V được khởi tạo bằng 𝜏𝑚𝑎𝑥 và sau đó được cập nhật lại sau mỗi vòng lặp theo công thức 3.11 Thông tin heuristic 𝜂𝑗 𝑖 được tính theo công thức 3.9.  *1. (1 ). ( , )ij f E similar i j     (3.9) Trong đó  *1f E là số cạnh được bảo tồn nếu tiếp tục dóng hàng đỉnh j với đỉnh i, α là hằng số thể hiện mối tương quan giữa độ tương đồng về cấu trúc và tính tương đồng về trình tự, ( , )similar i j là độ tương đồng giữa 2 đỉnh i và j. 3.3.4. Thủ tục bước ngẫu nhiên để xây dựng dóng hàng Tại mỗi vòng lặp, sau khi chọn một đỉnh 1i RV bằng thủ tục find_next_node tương tự thuật toán FASTAN, kiến chọn đỉnh 2j RV theo xác suất được cho bởi công thức 3.10. 2 ( ) .[ ] ( ) .[ ] i a i b j ji j i a i b k kk RV p        (3.10) Sau khi lựa chọn được đỉnh 2j RV để dóng với 1i RV , kiến quay lại lựa chọn đỉnh tiếp theo của đồ thị G1 để tiếp tục dóng hàng. Quá trình lặp lại cho đến khi tất cả các đỉnh của G1 được dóng hàng với các đỉnh của G2 3.3.5. Quy tắc cập nhật vết mùi Sau khi tất cả các kiến đã xây dựng lời giải, lời giải của kiến tốt nhất được áp dụng thủ tục tìm kiếm cục bộ để tăng chất lượng lời giải. Lời giải tốt nhất này được sử dụng để cập nhật vết mùi trên các cạnh theo quy tắc cập nhật mùi SMMAS, như dưới đây: (1 )i i ij j j      (3.11) . . maxi j min j=f(i) j f(i)          (3.12) Trong đó max và min là các tham số được cho trước, ∈ (0,1) là tham số bay hơi cho trước quy định 2 thuộc tính,  nhỏ thể hiện việc tìm kiếm quanh thông tin học tăng cường,  lớn thể hiện tính khám phá. 3.3.6. Thủ tục tìm kiếm cục bộ Trong mỗi vòng lặp, sau khi tất cả các kiến đã xây dựng xong lời giải, lời giải tốt nhất 𝐴12 được kiến xây dựng sẽ được áp dụng tìm kiếm cục bộ. Thủ tục tìm kiếm cục bộ được cải tiến từ thủ tục rebuilt trong FASTAN. Điểm khác biệt của ACOGNA so với FASTAN là khi chất lượng dóng hàng tăng lên khi gọi thủ tục dóng hàng cục bộ thì giá trị nkeep sẽ được điều chỉnh tăng lên để giữ được nhiều cặp đỉnh tốt hơn và giảm thời gian xây dựng lại các dóng hàng. 3.4. Thuật toán ACOGNA++ 3.4.1. Mô tả thuật toán Với đồ thị cấu trúc được xây dựng giống như thuật toán ACOGNA, để xây dựng một dóng hàng, các kiến sẽ thực hiện quả trình lặp để xác định 1 đỉnh thuộc tầng 1 của đồ thị cấu trúc và một đỉnh thuộc tầng 2 sẽ được dóng hàng với nó. Quá trình này kết thúc khi tất cả các đỉnh thuộc đồ thị G1 đã được dóng hàng. Sau khi tất cả 20 các kiến xây dựng xong dóng hàng, thủ tục tìm kiếm cục bộ sẽ được áp dụng trên lời giải tốt nhất của vòng lặp để nâng cao chất lượng. Tùy theo tiêu chuẩn tối ưu được lựa chọn là GNAS, EC hay S3, tiêu chuẩn được sử dụng để lựa chọn lời giải tốt nhất sẽ được thay đổi tương ứng theo các hàm mục tiêu này. 3.4.2. Vết mùi Vết mùi lưu thông tin học tăng cường để đánh giá một cặp đỉnh được dóng hàng là tốt hay không. Thuật toán ACOGNA++ sử dụng 2 ma trận vết mùi. Vết mùi 𝜏1 𝑖 đặt trên các đỉnh của đồ thị G1 để xác định các đỉnh sẽ được ưu tiên lựa chọn để dóng hàng trước. Vết mùi 𝜏𝑗 𝑖 đặt trên cạnh (i,j) của đồ thị cấu trúc, dùng để xác định đỉnh 2j G được dóng hàng với đỉnh 1 i G . Các vết mùi được khởi tạo bằng giá trị 𝜏𝑚𝑎𝑥 và được cập nhật lại sau mỗi vòng lặp. 3.4.3. Thủ tục xác định cặp đỉnh dóng hàng Thủ tục này gồm 2 bước, đầu tiên xác định đỉnh được dóng hàng trên đồ thị G1 và sau đó là xác định ảnh của nó trên đồ thị G2. Xác định đỉnh được dóng hàng thuộc đồ thị nguồn Khác với thủ tục find_next_node trong FASTAN và ACOGNA sử dụng để xác định đỉnh 1i RV sẽ được dóng hàng. Thuật toán ACOGNA++ sử dụng thuật toán ACO để xác định đỉnh i được dóng hàng như dưới đây. Gọi tập T chứa các đỉnh 𝑖 sao cho 1i RV và có nhiều cạnh nối với các đỉnh của 1V nhất. Khi đó, đỉnh 𝑖 ∈ 𝑇 được chọn ngẫu nhiên theo xác suất: 1 1 ( ) .[ ] ( ) .[ ] i a b i i j a b jj T p        (3.13) Trong đó 𝜂𝑖 là số lượng đỉnh kề của i trong đồ thị 𝐺1, 𝜏1𝑖 là vết mùi 𝜏1𝑖 đặt trên các đỉnh của đồ thị G1 như đã mô tả ở mục 3.5.2. Việc sử dụng ACO để tìm đỉnh thuộc đồ thị nguồn được dóng hàng sẽ giúp khai thác tốt thông tin học tăng cường thông qua vết mùi mà các kiến để lại. Điều này giúp cải thiện chất lượng lời giải tốt hơn so với cách lựa chọn ngẫu nhiên trong FASTAN và ACOGNA. Xác định ảnh của điểm được dóng hàng trên đồ thị đích G2 Sau khi xác định được đỉnh 1i V đỉnh 2j V được các kiến lựa chọn theo xác suất. 2 ( ) .[ ] ( ) .[ ] i c i d j ji j i c i d k kk RV p        (3.14) Khi chạy thuật toán ACOGNA++ để tối ưu theo hàm mục tiêu GNAS thì thông tin heuristic được sử dụng giống thuật toán ACOGNA. Trong trường hợp chạy thuật toán ACOGNA++ tối ưu theo hàm mục tiêu EC, hoặc S3, thông tin heuristic 𝜂𝑗 𝑖 lần lượt được tính theo các công thức 3.15 hoặc 3.16.  11 1 ( [V i]) i j f E G E    (3.15)     1 1 1 1 1 2 1 ( [V i]) ( ( ) j ) ( [V i]) i j f E G E E G f V f E G           (3.16) 3.4.4. Quy tắc cập nhật vết mùi Sau mỗi vòng lặp, lời giải tốt nhất được xác định được sử dụng để cập nhật lại vết mùi theo quy tắc cập nhật mùi SMMAS. Vết mùi đặt trên các đỉnh của đồ thị G1 được cập nhật theo công thức 3.17 và 3.18: 𝜏1 𝑖 ← (1 − 𝜌). 𝜏1 𝑖 + Δ𝜏𝑖 (3.17) Trong đó 12 Δ𝜏𝑖 = { 𝜌. 𝜏𝑚𝑖𝑛 𝑛ế𝑢 𝑘ℎô𝑛𝑔 𝑐ó đỉ𝑛ℎ 𝑘ề 𝜌. 𝜏𝑚𝑎𝑥𝑛ế𝑢 𝑐ó í𝑡 𝑛ℎấ𝑡 𝑚ộ𝑡 đỉ𝑛ℎ 𝑘ề (3.18) Vết mùi đặt trên các cạnh của đồ thị cấu trúc được cập nhật theo công thức (3.19) và (3.20) (1 )i i ij j j      (3.19) . . ( ) maxi j min j=f(i) j f i          (3.20) 3.4.5. Thủ tục tìm kiếm cục bộ Thủ tục tìm kiếm cục bộ của ACOGNA++ được sử dụng tương tự như trong ACOGNA. 3.5. Kết quả thực nghiệm 3.5.1. Dữ liệu thực nghiệm Dữ liệu thực nghiệm là bộ dữ liệu thực gồm 4 mạng tương tác protein được sử dụng phổ biến khi đánh giá chất lượng các thuật toán dóng hàng mạng PPI. Đó là các mạng tương tác protein của các loài như: giun, ruồi giấm, khỉ và người [Park, Singh, Baym, Liao, & Berger, 2010]. Mô tả về các tập dữ liệu này được chỉ ra trong bảng 3.1. Từ các bộ dữ liệu đó chúng tôi tạo ra sáu cặp mạng tương tác để dóng hàng (ce-dm, ce-hs,ce-sc,dm- hs, dm-sc,hs-sc). Bảng 3.1. Mô tả bộ dữ liệu Tập dữ liệu Ký hiệu Số đỉnh Số cạnh C.elegans (Worm) ce 2805 4495 D. melanogaster (fly) dm 7518 25635 S.cerevisiae (yeast) sc 5499 31261 H.sapiens (human) hs 9633 34327 3.5.2. Thực nghiệm so sánh thuật toán FASTAN với thuật toán SPINAL Có nhiều thuật toán dóng hàng toàn cục hai mạng tương tác protein – protein đã được đề xuất trước đó, tuy nhiên trong bài báo [Aladag & Erten, 2013], Aladag đã tiến hành các thực nghiệm trên bộ dữ liệu IsoBase và cho thấy thuật toán SPINAL cho kết quả tốt hơn các thuật toán khác khi đánh giá theo tiêu chuẩn GNAS và |E12| (số tương tác protein được bảo tồn khi dóng hàng mạng PPI nguồn với mạng PPI đích). Vì vậy các thực nghiệm ở mục này chỉ tiến hành so sánh 2 thuật toán heuristic là thuật toán FASTAN và SPINAL trên các bộ dữ liệu đã được mô tả ở mục 3.5.1 với tiêu chuẩn GNAS và |E12|. Để đảm bảo tính công bằng về mặt thời gian, cả 2 thuật toán đều được chạy lại trên máy tính có cùng cấu hình và cùng hệ điều hành. Kết quả thực nghiệm từ bảng 3.2 chỉ ra rằng FASTAN có thể tìm ra lời giải (dóng hàng toàn cục) có điểm GNAS và |E12| tốt hơn nhiều so với Spinal (p-value <2.2e-16 được tính sử dụng t-test dựa trên kết quả GNAS và giá trị |E12| của 100 lần chạy) đối với cả 6 cặp mạng PPI. Ngoài ra, kết quả kém nhất của FASTAN từ 100 lần chạy đối với tất cả các cặp mạng protein được dóng hàng đều tốt hơn các kết quả dóng hàng tạo ra bởi Spinal. Mặc dù đã so sánh về độ phức tạp của FASTAN và Spinal, trong phần này chúng tôi so sánh cả thời gian chạy của 2 thuật toán. Kết quả so sánh thời gian chạy được thể hiện trong bảng 3.3. Bảng 3.2. 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. Trong mỗi ô, dòng trên là điểm GNAS và dòng dưới là giá trị |E12| α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL 778.46 2560.7 717.99 2343.0 1034.20 2564.6 941.19 2320.0 1290.11 2567.2 1159.93 2300.0 1545.86 2567.7 1350.59 2237.0 1801.24 2567.6 1586.87 2258.0 863.46 2842.8 728.26 2370.0 1144.17 2838.1 993.07 2446.0 1429.89 2844.9 1229.95 2437.0 1708.81 2838.0 1501.61 2487.0 1994.87 2843.4 1764.93 2512.0 834.79 2761.1 709.12 2326.0 1109.93 2761.2 963.28 2384.0 1389.21 2769.7 1168.95 2323.0 1663.39 2766.5 1422.74 2361.0 1936.83 2763.1 1683.13 2398.0 2260.31 7478.3 1883.22 6189.0 3007.11 7481.9 2517.23 6235.0 3755.36 7429.0 3160.48 6282.0 4496.45 7478.2 3790.79 6291.0 5242.32 7478.8 4451.6 6344.0 1977.82 6569.7 1579.06 5203.0 2631.85 6565.5 2075.14 5150.0 3290.03 6570.7 2668.65 5311.0 3950.16 6577.4 3180.27 5283.0 4603.41 6572.3 3759.07 5360.0 2268.21 7531.8 1731.81 5703.0 3017.96 7528.5 2253.66 5593.0 3772.96 7535.2 2839.00 5651.0 4520.51 7527.0 3434.54 5706.0 5279.88 7538.1 4066.22 5798.0 21 Bảng 3.3. 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 Data sets ce-dm dm-sc dm-hs ce-hs hs-sc ce-sc SPINAL 540.2 1912.1 1736.8 664.3 2630.6 638.2 FASTAN 221.5 1064.5 1395.9 327.9 1507.8 142.2 Về thời gian chạy, kết quả ở bảng 3.3 cho thấy thời gian chạy của FASTAN nhanh xấp xỉ gấp đôi thuật toán SPINAL trong phần lớn các cặp mạng PPI. 3.5.3. Thực nghiệm so sánh thuật toán ACOGNA với các thuật toán FASTAN và MAGNA++ Luận án so sánh thuật toán ACOGNA với thuật toán FASTAN theo tiêu chuẩn GNAS và giá trị |E12|. Kết quả thực nghiệm cho thấy trong tất cả các trường hợp thì thuật toán ACOGNA đều cho các kết quả tốt hơn so với thuật toán FASTAN đối với tiêu chuẩn là GNAS và cả giá trị |E12|. Bảng 3.4. 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. Datasets α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 FASTAN ACOGNA FASTAN ACOGNA FASTAN ACOGNA FASTAN ACOGNA FASTAN ACOGNA ce-dm 778.46 2560.7 833.14 2749.2 1109.92 2564.6 1109.92 2758.2 1290.11 2567.2 1368.35 2726.10 1545.86 2567.7 1641.35 2728.3 1801.24 2567.6 1930.84 2753.7 ce-hs 863.46 2842.8 913.39 3015.3 1144.17 2838.1 1207.94 3001.1 1429.89 2844.9 1513.4 3014.2 1708.81 2838.0 1824.69 3033.0 1994.87 2843.4 2091.43 2982.6 ce-sc 834.79 2761.1 876.78 2902.9 1109.93 2761.2 1178.46 2934.8 1389.21 2769.7 1457.65 2907.9 1663.39 2766.5 1742.2 2898.3 1936.83 2763.1 2064.12 2945 dm-hs 2260.31 7478.3 2431.59 8058.4 3007.11 7481.9 3226.76 8038.7 3755.36 7429.0 4039.68 8060.1 4496.45 7478.2 4828.29 8034.29 5242.32 7478.8 5648.18 8060.9 dm-sc 1977.82 6569.7 2108.13 7008.7 2631.85 6565.5 2811.97 7019.2 3290.03 6570.7 3518.87 7030.2 3950.16 6577.4 4203.53 7000.90 4603.41 6572.3 4908.90 7009.6 hs-sc 2268.21 7531.8 2429.12 8072.9 3017.96 7528.5 3256.54 8182.8 3772.96 7535.2 3938.3 7666.0 4520.51 7527 4895.45 8153.4 5279.88 7538.1 5693.4 8129.8 Tiến hành thực nghiệm so sánh ACOGNA với thuật toán MAGNA++, các kết quả thực nghiệm ở bảng 3.5 chỉ ra rằng với tất cả các giá trị của tham số α và tất cả các bộ dữ liệu, điểm số EC của ACOGNA luôn luôn tốt hơn MAGNA++. Bảng 3.5. So sánh ACOGNA và MAGNA++ theo tiêu chuẩn EC Datasets ACOGNA MAGNA++ α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 EC ICS S3 ce-dm 0.6116 0.6136 0.6065 0.6070 0.6126 0.5217 0.0700 0.2983 ce-hs 0.6708 0.6677 0.6706 0.6747 0.6635 0.3061 0.1288 0.3065 ce-sc 0.6458 0.6529 0.6469 0.6448 0.6553 0.6002 0.1449 0.2901 dm-hs 0.3144 0.3136 0.3144 0.3159 0.3138 0.1921 0.0885 0.1464 dm-sc 0.2242 0.2245 0.2249 0.2239 0.2240 0.1575 0.0569 0.1357 hs-sc 0.2582 0.2600 0.2608 0.2608 0.2601 0.1680 0.0390 0.1439 Với tiêu chuẩn S3 khi chạy với các bộ dữ liệu dm-hs, dm-sc, hs-sc với tất cả các giá trị của tham số α, thuật toán ACOGNA cho kết quả tốt hơn so với MAGNA++ khi chạy thuật toán này theo cả 3 tùy chọn tiêu chuẩn tối ưu là EC, ICS và S3. Tuy nhiên đối với 3 bộ dữ liệu ce-dm, ce-sc, ce-hs MAGNA++ lại cho kết quả tốt hơn ACOGNA. Bảng 3.6. So sánh ACOGNA và MAGNA++ theo tiêu chuẩn S3 Datasets ACOGNA MAGNA++ α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 EC ICS S3 ce-dm 0.1344 0.1123 0.1068 0.1338 0.1061 0.1580 0.0700 0.2597 ce-hs 0.1265 0.0993 0.0953 0.0939 0.0909 0.2621 0.1284 0.2639 ce-sc 0.1063 0.0953 0.0925 0.0911 0.0922 0.1198 0.1446 0.2573 dm-hs 0.1593 0.1559 0.156 0.1567 0.1555 0.0988 0.0785 0.1088 dm-sc 0.1446 0.1417 0.1415 0.1407 0.1406 0.1030 0.0554 0.1081 hs-sc 0.1501 0.1452 0.1484 0.1446 0.1433 0.1043 0.0387 0.1166 22 3.5.4. So sánh thuật toán ACOGNA++ với các thuật toán ACOGNA, MAGNA++ và ModuleAlign Luận án tiến hành so sánh chất lượng lời giải của các thuật toán theo các tiêu chuẩn S3, GNAS, EC và Điểm mới của thuật toán ACOGNA++ so với ACOGNA là có thể tối ưu theo các hàm mục tiêu khác nhau (tương tự như MAGNA++). Khi so sánh theo hàm mục tiêu GNAS và EC, thì 2 thuật toán ACOGNA và ACOGNA++ có chất lượng chênh lệch không nhiều (vì cả 2 thuật toán đều sử dụng hàm mục tiêu là GNAS). Bảng 3.7 thể hiện kết quả so sánh chất lượng lời giải của các thuật toán theo tiêu chuẩn S3. Chất lượng lời giải tốt nhất được định dạng chữ in đậm. Bảng 3.7. So sánh theo tiêu chuẩn S3 Datasets ACOGNA MAGNA++ ModuleAlign ACOGNA++ α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 ce-dm 0.1344 0.1123 0.1068 0.1338 0.1061 0.2597 0.1538 0.3655 ce-hs 0.1265 0.0993 0.0953 0.0939 0.0909 0.2639 0.1354 0.4165 ce-sc 0.1063 0.0953 0.0925 0.0911 0.0922 0.2573 0.1192 0.2795 dm-hs 0.1593 0.1559 0.156 0.1567 0.1555 0.1088 0.1117 0.1910 sc-dm 0.1446 0.1417 0.1415 0.1407 0.1406 0.1081 0.1059 0.1767 sc-hs 0.1501 0.1452 0.1484 0.1446 0.1433 0.1166 0.1174 0.2096 Kết quả so sánh thời gian chạy của 2 thuật toán ACOGNA++ và MAGNA++ thể hiện trên hình 3.2: Hình 3.2. So sánh thời gian chạy của 2 thuật toán ACOGNA++ và MAGNA++ Qua biểu đồ so sánh ta thấy trong 6 bộ test thì có 5 bộ test là thời gian chạy của ACOGNA++ nhanh hơn so với MAGNA++, chỉ có 1 bộ test dm-hs là thời gian chạy của MAGNA++ nhanh hơn so với ACOGNA++. 3.6. Kết luận chương Trong chương này chúng tôi đã trình bày về bài toán dóng hàng toàn cục mạng tương tác protein và đề xuất các thuật toán mới để giải quyết bài toán này. Các thuật toán đề xuất dựa trên 2 hướng tiếp cận. Hướng tiếp cận heuristic và hướng tiếp cận metaheuristic dựa trên phương pháp tối ưu đàn kiến. Với hướng tiếp cận heuristic, thuật toán FASTAN có ưu điểm là cho lời giải nhanh và kết quả tốt hơn so với các thuật toán trước đó. Tuy nhiên nhược điểm của phương pháp FASTAN là khi tăng thời gian chạy thì chất lượng lời giải được cải thiện không đáng kể. Để khắc phục nhược điểm trên của FASTAN, chúng tôi đề xuất các thuật toán mới ACOGNA và ACOGNA++ dựa trên phương pháp tối ưu đàn kiến để xây dựng các dóng hàng. Thuật toán ACOGNA bao gồm nhiều vòng lặp, trong mỗi vòng lặp của thuật toán, tất cả các kiến xây dựng lời giải, sau đó kiến có chất lượng lời giải tốt nhất được lựa chọn để cập nhật vết mùi và áp dụng tìm kiếm cục bộ để tăng chất lượng lời giải. Các thực nghiệm trên bộ dữ liệu chuẩn đã chỉ ra rằng thuật toán chúng tôi đề xuất cho kết quả tốt hơn các thuật toán gần đây đối với 2 tiêu chuẩn GNAS và EC đối với tất cả các trường hợp. Mặc dù không sử dụng tiêu chuẩn S3 làm hàm mục tiêu, nhưng trong các trường hợp mà đồ thị nguồn là đồ thị dày thuật toán ACOGNA cho kết quả S3 tốt hơn so với thuật toán MAGNA++ (Là thuật toán tốt nhất tới thời điểm đó tối ưu theo tiêu chuẩn S3). 0 5000 10000 15000 20000 25000 30000 ce-dm ce-hs ce-sc sc-dm dm-hs sc-hs T h ờ i g ia n ( s) Bộ dữ liệu MAGNA++ ACOGNA++ 23 Thuật toán ACOGNA++ sử dụng sơ đồ cấu trúc giống với thuật toán ACOGNA nhưng có nhiều điểm cải tiến trong cách xác định thông tin heuristic, cách lưu trữ và cập nhật thông tin vết mùi và sử dụng kiến trong cả 2 giai đoạn xác định đỉnh tiếp theo của đồ thị nguồn được dóng hàng và tìm ảnh của nó trên đồ thị đích. Thuật toán ACOGNA++ cho phép thay đổi các tiêu chuẩn tối ưu để tối ưu theo các hàm mục tiêu GNAS, EC và S3. Các thực nghiệm đã cho thấy thuật toán ACOGNA++ cho chất lượng lời giải tốt hơn so với các thuật toán được so sánh theo các tiêu chuẩn này. KẾT LUẬN Luận án đã trình bày các kiến thức chung về lĩnh vực tin sinh học và về 2 bài toán có ý nghĩa quan trọng trong lĩnh vực tin sinh học là bài toán dóng hàng đồng thời nhiều mạng các vị trí liên kết protein và là bài toán dóng hàng mạng tương tác protein-protein. Bên cạnh đó luận án cũng đã trình bày về các kỹ thuật tính toán mềm, trong đó tập trung trình bày chi tiết về phương pháp tối ưu hóa đàn kiến và các phương pháp tính toán mềm khác được sử dụng để giải quyết 2 bài toán dóng hàng mạng protein. Với việc phân tích đặc điểm của các thuật toán mới nhất giải quyết các bài toán dóng hàng đồng thời nhiều mạng các vị trí liên kết ptotein và bài toán dóng hàng toàn cục 2 mạng tương tác protein-protein chúng tôi đã đề xuất các thuật toán mới giải quyết hiệu quả 2 bài toán này. Với bài toán dóng hàng nhiều mạng các vị trí hoạt tính protein, luận án đề xuất 3 thuật toán để giải bài toán này là thuật toán ACO-MGA, ACO-MGA2 và ACOTS-MGA. Thuật toán ACO-MGA dựa trên phương pháp tối ưu hóa đàn kiến thuần túy để giải bài toán dóng hàng nhiều mạng. Các kết quả thực nghiệm dựa trên các bộ dữ liệu mô phỏng đã chứng minh hiệu quả nổi trội của thuật toán này so với các thuật toán GAVEO và thuật toán heuristic để giải bài toán này. Nghiên cứu đặc tính biến thiên vết mùi của các thuật toán ACO, trong thuật toán ACO-MGA2, chúng tôi áp dụng lược đồ memetic cho thuật toán, trong đó vết mùi của thuật toán ACO được cập nhật theo 2 giai đoạn khác nhau. Giai đoạn đầu tham số bay hơi được thiết lập nhỏ để khai thác thông tin học tăng cường và không áp dụng tìm kiếm cục bộ. Giai đoạn 2 có sử dụng tìm kiếm cục bộ nên tham số bay hơi được thiết lập lớn hơn để tăng tính khám phá của thuật toán. Các kết quả thực nghiệm trên các bộ dữ liệu thực đã cho thấy những ưu điểm của thuật toán mới đề xuất này so với các thuật toán trước đó. Thuật toán ACO-MGA2 có nhược điểm là khi áp dụng tìm kiếm cục bộ, việc hoán đổi vị trí giữa các đỉnh bị lặp lại trong các lần gọi khác nhau, vì vậy luận án đề xuất thuật toán ACOTS-MGA sử dụng kết hợp phương pháp ACO và tìm kiếm Tabu theo lược đồ memetic. Thuật toán Tabu search sử dụng để thay thế cho thuật toán tìm kiếm cục bộ trong ACO-MGA2 sử dụng danh sách cấm để tránh xét lại các bước chuyển đã xét trước đó. Ngoài ra trong ACOTS-MGA, còn có sự cải tiến trong cách xác định thông tin heuristic và thủ tục bước ngẫu nhiên xây dựng một dóng hàng. Các thực nghiệm trên bộ dữ liệu thực đã chứng minh những ưu điểm nổi trội của phương pháp này so với các phương pháp đề xuất trước đó. Với bài toán dóng hàng hai mạng tương tác protein, chúng tôi đề xuất các thuật toán mới theo hướng tiếp cận dóng hàng toàn cục. Thuật toán thứ nhất là thuật toán FASTAN cho phép dóng hàng nhanh và cho chất lượng lời giải tốt so với các thuật toán trước đó. Thuật toán này phù hợp với các mạng tương tác protein-protein có kích thước lớn và yêu cầu thời gian giải bài toán nhanh. Tuy nhiên khi tăng thời gian chạy thuật toán thì chất lượng của FASTAN được cải thiện không nhiều. Để khắc phục nhược điểm trên của FASTAN, chúng tôi tiếp tục đề xuất thuật toán giải bài toán dóng hàng toàn cục mạng tương tác protein-protein dựa trên phương pháp tối ưu hóa đàn kiến có tên là ACOGNA. Các kết quả thực nghiệm trên các bộ dữ liệu sinh học thực đã chứng minh những hiệu quả của phương pháp ACOGNA tốt hơn so với các thuật toán trước đó theo các tiêu chuẩn GNAS, EC; tuy nhiên với tiêu chuẩn S3 thuật toán ACOGNA còn cho chất lượng lời giải kém hơn so với thuật toán MAGNA++. Thuật toán ACOGNA++ được đề xuất sau đó cho phép thay đổi hàm mục tiêu theo các tiêu chuẩn dóng hàng khác nhau và sử dụng thuật toán kiến trong cả 2 giai đoạn xác định thứ tự các đỉnh trên đồ thị nguồn và xác định ảnh của nó trên đồ thị đích. Vì vậy ACOGNA++ cho chất lượng lời giải tốt hơn ACOGNA, ModuleAlign, MAGNA++ đối với tất cả các bộ dữ liệu. 24 Các kết quả nghiên cứu đã được công bố trong 5 bài báo công bố tại các hội nghị quốc tế cũng như trong nước có phản biện, trong đó có 3 bài được đưa vào danh mục Scopus; một bài báo đăng tại tạp chí VNU Journal of Science: Computer Science and Communication Engineering. Các thuật toán đề xuất trong luận án cho thấy hiệu quả tốt hơn hẳn so với các thuật toán đề xuất trước đó để giải các bài toán dóng hàng nhiều mạng các vị trí liên kết protein và bài toán dóng hàng toàn cục 2 mạng tương tác protein. Về thời gian chạy, các thuật toán đề xuất cũng nhanh hơn các thuật toán tính toán mềm khác được đề xuất trước đó trong phần lớn các bộ dữ liệu. Các thuật toán đề xuất đều dựa trên phương pháp tối ưu đàn kiến, vì vậy có thể cải thiện thời gian chạy theo hướng song song hóa các thuật toán, bên cạnh đó nghiên cứu sâu hơn về các phương pháp tính toán mềm khác để cải tiến các thuật toán đề xuất nhằm giảm thời gian chạy. Đối với bài toán dóng hàng các mạng các vị trí liên kết protein. Thời gian gần đây, người ta tập trung nghiên cứu việc ứng dụng bài toán này vào việc nghiên cứu thuốc [Borrel, 2016; Jukič, Konc, Gobec, & Janežič, 2017; Yuan et al., 2018]. Chúng tôi dự kiến sẽ liên hệ với các cơ sở nghiên cứu y-sinh để cùng phát triển các nghiên cứu mang tính ứng dụng. Đối với bài toán dóng hàng mạng tương tác protein, thời gian tới chúng tôi sẽ nghiên cứu để mở rộng việc áp dụng các thuật toán đề xuất cho bài toán dóng hàng đồng thời nhiều mạng tương tác protein-protein, hay bài toán dóng hàng các mạng động. Bên cạnh đó là việc nghiên cứu ứng dụng các thuật toán đề xuất vào trong các bài toán thời sự trong lĩnh vực mạng xã hội. DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 1. Trần Ngọc Hà, Đỗ Đức Đông, Hoàng Xuân Huấn (2013), “An Efficient Ant Colony Optimization Algorithm for Multiple Graph Alignment”, Proceedings of International Conference on Computing, Management and Telecommunications (ComManTel),Ho Chi Minh City, Vietnam, pp.386-391. (Scopus) 2. Trần Ngọc Hà, Đỗ Đức Đông, Hoàng Xuân Huấn (2014), “A Novel Ant Based Algorithm for Multiple Graph Alignment”, Proceedings of the 2014 International Conference on Advanced Technologies for Communications, pp. 181-186. (Scopus) 3. Đỗ Đức Đông, Trần Ngọc Hà, Đặng Thanh Hải, Đặng Cao Cường, Hoàng Xuân Huấn (2015), “An efficient algorithm for global alignment of protein-protein interaction networks”, Proceedings of the 2015 International Conference on Advanced Technologies for Communications, pp. 332-336. (Scopus) 4. Trần Ngọc Hà, Hoàng Xuân Huấn (2015), “Một thuật toán tối ưu đàn kiến dóng hàng toàn cục mạng tương tác protein”, Proceedings of Fundamental and Applied IT Research Conference 2015 (FAIR 2015), Ha Noi, Viet Nam, pp. 471-477. 5. Ha Tran Ngoc, Huan Hoang Xuan (2016), “ACOGNA: An Efficient Method for Protein-Protein Interaction Network Alignment”, Proceedings of the The Eighth International Conference on Knowledge and Systems Engineering (KSE 2016), pp. 7-12. 6. Ha Tran Ngoc, Hien Le Nhu, Huan Hoang Xuan (2018), “A new memetic algorithm for multiple graph alignment”, VNU Journal of Science: Computer Science and Communication Engineering, vol 34, no 1, pp 1-9.