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

h 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 [Hoang Xuan Huan et al., 2013], 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á. 95 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 rebuild 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++ Mục này giới thiệu một thuật toán được phát triển từ thuật toán ACOGNA gọi là ACOGNA++. Như đã giới thiệu ở mục 3.3, thuật toán ACOGNA sử dụng tiêu chuẩn GNAS là tiêu chuẩn tối ưu và chỉ sử dụng phương pháp ACO để tìm ảnh của các đỉnh của đồ thị G1. Ý tưởng của thuật toán ACOGNA++ có một số điểm mới so với thuật toán ACOGNA là:  Thứ nhất ACOGNA++ cho phép thay đổi tùy chọn tiêu chuẩn tối ưu theo các hàm mục tiêu là GNAS, EC, và S3. Đặc điểm này cho phép ACOGNA++ có thể tối ưu theo các hàm mục tiêu khác nhau.  Thứ 2 là giải thuật đàn kiến được áp dụng cho cả 2 giai đoạn là tìm thứ tự các đỉnh của đồ thị G1 được dóng hàng và tìm ảnh của các đỉnh này trên đồ thị G2. Ưu điểm của cải tiến này là ACOGNA++ có thể khai thác thông tin học tăng cường ngay từ giai đoạn tìm đỉnh tiếp theo của G1 được dóng hàng mà ACOGNA không làm được.  Thứ 3 là thay đổi cách xác định thông tin heuristic, cách lựa chọn đỉnh của đồ thị đích để dóng hàng với 1 đỉnh thuộc đồ thị nguồn và cách tổ chức và cập nhật thông tin vết mùi. 96 Các mục tiếp theo sẽ phân tích chi tiết những điểm mới này. 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ả 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 do các kiến tìm được trong vòng lặp để nâng cao chất lượng. Sau đó sử dụng quy tắc cập nhật mùi SMMAS để cập nhật thông tin vết mùi theo lời giải tốt nhất tìm được. 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 thuộc đồ thị nguồn sẽ được ưu tiên lựa chọn để dóng hàng. 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. 97 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.4.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 cho bởi công thức 3.14. 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 98 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) với Δ𝜏𝑖 = { 𝜌. 𝜏𝑚𝑖𝑛 𝑛ế𝑢 𝑘ℎô𝑛𝑔 𝑐ó đỉ𝑛ℎ 𝑘ề 𝜌. 𝜏𝑚𝑎𝑥𝑛ế𝑢 𝑐ó í𝑡 𝑛ℎấ𝑡 𝑚ộ𝑡 đỉ𝑛ℎ 𝑘ề , (3.18) trong đó f(i)G2 là đỉnh thuộc đồ thị G2 được lựa chọn để dóng hàng với đỉnh i trên đồ thị G1 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) 99 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 Việc lựa chọn các bộ dữ liệu để so sánh các thuật toán rất quan trọng. Bộ dữ liệu thường được sử dụng để so sánh các phương pháp dóng hàng mạng tương tác protein là bộ dữ liệu IsoBase được giới thiệu bởi Daniel Park và các cộng sự [Park, Singh, Baym, Liao, & Berger, 2010]. Bộ dữ liệu IsoBase được cung cấp miễn phí tại địa chỉ Trong các nghiên cứu gần đây nhất, khi đề xuất các thuật toán mới cho bài toán dóng hàng toàn cục mạng tương tác protein-protein như Spinal năm 2013 [Aladag & Erten, 2013], MAGNA và MAGNA++ năm 2015 [V Vijayan et al., 2015] hay ModuleAlign năm 2016 [Hashemifar et al., 2016] các tác giả cũng sử dụng bộ dữ liệu này để đánh giá chất lượng các thuật toán đề xuất. Luận án cũng sử dụng bộ dữ liệu này để so sánh các thuật toán đề xuất với các thuật toán hiện thời để đảm bảo độ tin cậy và sự khách quan. IsoBase là bộ dữ liệu mạng tương tác protein-protein của các loài động vật trong tự nhiên, trong đó bao gồm các mạng tương tác protein-protein của các loài như: giun, ruồi giấm, khỉ và người. 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). 100 Bảng 3.1. Mô tả bộ dữ liệu Tập dữ liệu Ký hiệu Số lượng protein Số tương tác 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. Chú ý rằng trong công thức 3.1 tính giá trị GNAS, 𝛼 ∈ [0,1] là tham số thể hiện sự tương quan giữa độ tương đồng về mặt cấu trúc và sự tương đồng về mặt trình tự. Nếu 𝛼 dần về 0 có nghĩa là độ tương đồng về trình tự giữ vai trò quan trọng hơn, ngược lại khi 𝛼 dần về 1 nghĩa là độ tương đồng về mặt cấu trúc giữ vai trò quan trọng hơn. Giống như các thực nghiệm được tiến hành trong đề xuất thuật toán SPINAL của Aladag [Aladag & Erten, 2013], ở đây 101 luận án tiến hành các thực nghiệm ứng với các giá trị của 𝛼 thay đổi lần lượt là 0,3; 0,4; 0,5; 0,6; 0,7 để đảm bảo lời giải của thuật toán đề xuất không quá thiên về 1 trong 2 độ tương đồng trình tự hoặc độ tương đồng về mặt cấu trúc. Thuật toán FASTAN được chạy với các giá trị khác nhau của tham số 𝑛𝑘𝑒𝑒𝑝 lần lượt là 1%, 5%, 10%, 20% và 50%. Kết quả thực nghiệm cho thấy 𝑛𝑘𝑒𝑒𝑝= 1% thuật toán FASTAN sẽ thu được kết quả tốt nhất. Vì vậy các kết quả được trình bày dưới đây tương ứng với giá trị 𝑛𝑘𝑒𝑒𝑝 = 1%. Các thực nghiệm được chạy trên máy tính có cấu hình như sau: CPU Intel Core 2 Duo 2.53GHz, RAM DDR2 4GB sử dụng hệ điều hành Ubuntu 13.10 64 bit. Như đã trình bày ở trên thuật toán FASTAN là thuật toán ngẫu nhiên nên sẽ được chạy 100 lần với từng cặp mạng PPI. Các kết quả GNAS, |E12| và thời gian chạy được tính theo giá trị trung bình của 100 lần chạy. Các kết quả so sánh về điểm dóng hàng và thời gian chạy được thể hiện ở các bảng 3.2 và 3.3, kết quả tốt hơn được thể hiện bởi chữ in đậm. 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. 102 . . Datasets α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL ce-dm 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 ce-hs 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 ce-sc 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 dm-hs 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 dm-sc 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 hs-sc 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 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 103 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.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 khi chạy với cùng bộ dữ liệu. 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++ Thực nghiệm được tiến hành để so sánh thuật toán ACOGNA với thuật toán FASTAN. Thuật toán được chạy với nhiều giá trị 𝑛𝑏𝑒𝑠𝑡 khác nhau bao gồm 1%, 5%, 10%, 20% và 50%. Các kết quả thực nghiệm chỉ ra rằng với nbest=1% sẽ cho chất lượng lời giải tốt nhất. Đối với thuật toán đàn kiến, các tham số  được khởi tạo từ đầu và số lượng kiến trong mỗi vòng lặp ảnh hưởng nhiều đến chất lượng lời giải. Qua nhiều thực nghiệm chúng tôi thấy với =0.3 sẽ cho chất lượng lời giải tốt nhất. Đối với số lượng kiến, nếu sử dụng nhiều kiến để xây dựng lời giải có thể cho được kết quả tốt hơn, tuy nhiên lại khiến thuật toán chạy lâu. Để cân bằng giữa hai yếu tố này, trong thực nghiệm chúng tôi chọn số kiến là 6. Các tham số max được khởi tạo bằng 1 và min 1 2 1 | | | |V V    . Vì vậy các kết quả được 104 trình bày ở đây tương ứng với giá trị nbest=1%, 0.3  , nants=6 như đã phân tích ở trên. Các thuật toán được so sánh dựa trên 2 tiêu chí là tiêu chuẩn GNAS và giá trị |E12| (Số cạnh của đồ thị nguồn được bảo tồn trên đồ thị đích khi dóng hàng). Các thực nghiệm được chạy trên cùng một máy tính có cấu hình như sau: CPU Intel Core 2 Duo 2.53GHz, RAM DDR2 3GB và hệ điều hành Windows 7 32 bit. 3.5.3.1. Thực nghiệm so sánh ACOGNA và FASTAN theo tiêu chuẩn GNAS ACOGNA, FASTAN và Spinal là các thuật toán dóng hàng tối ưu theo tiêu chuẩn GNAS. Các thực nghiệm đã chứng minh rằng FASTAN tốt hơn Spinal nên thực nghiệm này chỉ tiến hành so sánh tiêu chuẩn GNAS của 2 thuật toán ACOGNA và thuật toán FASTAN. Vì thuật toán ACOGNA và FASTAN là thuật toán ngẫu nhiên nên chúng tôi tiến hành chạy thuật toán 10 lần và sử dụng kết quả trung bình của 10 lần chạy để so sánh. Các thực nghiệm so sánh các thuật toán với các giá trị α lần lượt là 0.3, 0.4, 0.5, 0.6 và 0.7 như trong [Aladag & Erten, 2013]. Các kết quả so sánh được thể hiện trong Bảng 3.4. Mỗi ô trong bảng gồm 2 dòng, dòng đầu là tiêu chuẩn GNAS và dòng thứ 2 là giá trị |E12| (số cạnh được bảo tồn qua dóng hàng). Các kết quả tốt hơn được chúng tôi thể hiện bằng chữ in đậm. 105 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 Qua bảng 3.4 ta có thể thấy rõ 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|. 106 3.5.3.2. Thực nghiệm so sánh ACOGNA và MAGNA++ theo tiêu chuẩn S3 và EC Các tiêu chuẩn EC, ICS và S3 được sử dụng để đánh giá độ tương đồng về cấu trúc của các thuật toán dóng hàng hai mạng. Thực nghiệm này sẽ so sánh kết quả của ACOGNA so với MAGNA++, một thuật toán được xây dựng với 3 tùy chọn tiêu chuẩn tối ưu như trên khi dóng hàng 2 đồ thị. Bảng 3.5 trình bày các kết quả so sánh của 2 thuật toán với tiêu chuẩn EC, thuật toán ACOGNA được chạy với các giá trị của tham số α lần lượt là 0.3, 0.4, 0.5, 0.6, 0.7. Giá trị điểm EC của thuật toán ACOGNA được thể hiện trong các cột tương ứng. Thuật toán MAGNA++ được chạy với 3 tùy chọn tối ưu theo các tiêu chuẩn EC, ICS và S3. Các giá trị điểm EC được hiển thị trong các cột EC, ICS và S3 tương ứng với các tùy chọn chạy thuật toán MAGNA++ tối ưu theo các tiêu chuẩn EC, ICS và S3. Kết quả tốt nhất khi so sánh các thuật toán được thể hiện bằng chữ in đậm. 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 107 Nhận xét: Các kết quả ở 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.6 thể hiện các kết quả so sánh của 2 thuật toán theo độ đo S3. Điểm S3 của ACOGNA được thể hiện trong các cột tương ứng với các giá trị α lần lượt là 0.3, 0.4, 0.5, 0.6, 0.7, và kết quả S3 của thuật toán MAGNA ++ khi được chạy lần lượt với 3 tiêu chuẩn tối ưu là EC, ICS và S3 được thể hiện trong các cột tương ứng. Các kết quả tốt nhất được in đậm. Bảng 3.6. So sánh ACOGNA và MAGNA++ theo tiêu chuẩn S3 Nhận xét: 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 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. Về mặt thời gian chạy, do ACOGNA là thuật toán metaheuristic được thực hiện với nhiều vòng lặp, nên thời gian chạy chậm hơn so với thuật toán 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 108 FASTAN là một thuật toán theo hướng tiếp cận heuristic, vì vậy ở đây chúng tôi không đưa ra các bảng so sánh về mặt thời gian chạy. 3.5.4. Thực nghiệm so sánh thuật toán ACOGNA++ với các thuật toán ACOGNA, MAGNA++ và ModuleAlign Để đánh giá hiệu quả của các thuật toán, chúng tôi 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 và EC. Thuật toán ACOGNA++ được so sánh với các thuật toán ACOGNA, MAGNA++, và ModuleAlign. Đ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) nên trong phần này chúng tôi trình bày kết quả so sánh khi chạy thuật toán ACOGNA++ với tiêu chuẩn tối ưu là S3. Các thực nghiệm được tiến hành trên máy tính có cấu hình như sau: CPU Intel Core 2 Duo 2.53Ghz, RAM DDR2 4GB và hệ điều hành Windows 7. Các tham số được thiết lập như sau: số lượng kiến trong mỗi vòng lặp là 10, 𝑎 = 1.5; 𝑏 = 1; c=1; d=2; max = 1.0 và min 1 2 1 | | | |V V    . Qua các thực nghiệm thuật toán cho kết quả tốt nhất khi chọn giá trị nbest = 1%. 3.5.4.1. So sánh các thuật toán theo tiêu chuẩn tối ưu S3 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. 109 Bảng 3.7. So sánh các thuật toán theo tiêu chuẩn S3 Kết quả thể hiện trong bảng cho thấy với tất cả các bộ dữ liệu, thuật toán ACOGNA++ đều cho kết quả tốt hơn các thuật toán còn lại. 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 110 3.5.4.2. So sánh thời gian chạy Các thuật toán FASTAN, Spinal và ModuleAlign là các thuật toán heuristic nên có thời gian chạy nhanh hơn, nhưng lại không cải thiện được chất lượng khi tăng thời gian chạy, vì vậy luận án không so sánh thời gian chạy với 3 thuật toán này. Khi so sánh thời gian chạy của 2 thuật toán ACOGNA++ và MAGNA++ ta có kết quả thể hiện trên hình 3.2: Hình 3.2. So sánh thời gian chạy tính theo giâ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 - protein và đề xuất các thuật toán mới để giải quyết bài 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++ 111 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). 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 112 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. Các thuật toán đề xuất trong chương này tạo ra các dóng hàng toàn cục giữa hai mạng PPI có chất lượng dóng hàng tốt hơn so với các thuật toán trước đó đồng nghĩa với việc xác định được các vùng mạng được bảo tồn giữa các mạng PPI chính xác hơn. Các vùng mạng được bảo tồn này sẽ giúp chuyển hiệu quả các kiến thức về chức năng của tế bào từ mô hình các loài đã được nghiên cứu sâu, chẳng hạn như nấm men, ruồi giấm, hoặc sâu sang con người ít được nghiên cứu hơn [Guzzi & Milenković, 2018; R. Sharan & Ideker, 2006]. Ngoài ra, các kết quả của bài toán dóng hàng hai mạng PPI còn được sử dụng để phục vụ cho bài toán xây dựng cây phân loài [O. Kuchaiev et al., 2010]. 113 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 hai 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 đó. 114 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 đó. Đối 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 115 đồ 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. 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 hai 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 [Dohrmann & Singh, 2016; Vipin Vijayan & Milenkovic, 2018], hay bài toán dóng hàng các mạng động [V Vijayan, Critchlow, & Milenković, 2017]. Bên cạnh đó là việc nghiên 116 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 [J. Zhang & Yu, 2015; Y. Zhang, Tang, Yang, Pei, & Yu, 2015]. 117 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN 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. 118 TÀI LIỆU THAM KHẢO Tiếng Việt 1. Lê Sỹ Vinh (2014), Nhập môn Tin sinh học, NXB Đại học Quốc gia Hà Nội, Hà Nội. Tiếng Anh 2. Aladag, A. E., & Erten, C. (2013). "SPINAL: scalable protein interaction network alignment". Bioinformatics, 29(7), pp. 917–924. 3. Alföldi, J., & Lindblad-Toh, K. (2013). "Comparative genomics as a tool to understand evolution and disease". Genome Res., 23(7), pp. 1063–1068. 4. Alkan, F., & Erten, C. (2014). "BEAMS: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks". Bioinformatics, 30(4), pp. 531–539. 5. Altschul, S. F., Gish, W., Miller, W., & Lipman, D. J. (1990). "Basic local alignment search tool". J. Mol. Biol., 215(3), pp. 403–410. 6. Altschul, S. F., Madden, T. L., Schffer, A. A., Zhang, J., Zhang, Z., Miller, W., & Lipman, D. J. (1997). "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs". Nucleic Acids Res., 25(17), pp. 3389–3402. 7. Ashburner, M., Ball, C. A., Blake, J. A., Botstein, D., Butler, H., Cherry, J. M., Sherlock, G. (2000). "Gene ontology: tool for the unification of biology". Nat. Genet., 25(1), pp. 25–29. 119 8. Berg, J., & Lassig, M. (2004). "Local graph alignment and motif search in biological networks". Proceedings of the National Academy of Sciences, 101(41), pp. 14689–14694. 9. Berg, J., & Lassig, M. (2006). "Cross-species analysis of biological networks by Bayesian alignment". Proc. Natl. Acad. Sci., 103(29), pp. 10967–10972. 10. Berman, H. M., Battistuz, T., Bhat, T. N., Bluhm, W. F., Bourne, P. E., Burkhardt, K., Zardecki, C. (2002). "The protein data bank". Acta Crystallographica Section D: Biological Crystallography, 58(6 I), pp. 899–907. 11. Biesecker, L. G., Mullikin, J. C., Facio, F. M., Turner, C., Cherukuri, P. F., Blakesley, R. W., Green, E. D. (2009). "The ClinSeq project: piloting large-scale genome sequencing for research in genomic medicine". Genome Res., 19, pp. 1665–1674. 12. Borrel, A. (2016). Development of Computational Methods to Predict Pocket Druggability and Profile Ligands using Structural Data By. Thesis Phd-penting. University of Helsinki, Faculty of Pharmacy, Division of Pharmaceutical Chemistry and Technology Molécules Thérapeutiques in Silico (MTi), Inserm UMR-S 973, University Paris Diderot, France. 13. Brin, S., & Page, L. (1998). "The anatomy of a large-scale hypertextual web search engine". Comput. Net. ISDN Syst., 30(1–7), pp. 107–117. 14. Brownlee, J. (2011). Clever Algorithms: Nature Inspired Programming Recipes. Search. 120 15. Chindelevitch, L., Liao, C.-S., & Berger, B. (2010). "Local optimization for global alignment of protein interaction networks.". Pacific Symposium On Biocomputing, 132, pp. 123–132. 16. Chindelevitch, L., Ma, C.-. Y., Liao, C.-. S., & Berger, B. (2013). "Optimizing a global alignment of protein interaction networks". Bioinformatics, 29(21), pp. 2765–2773. 17. Ciriello, G., Mina, M., Guzzi, P. H., Cannataro, M., & Guerra, C. (2012). "AlignNemo: A local network alignment method to integrate homology and topology". PLoS ONE, 7(6), pp. e38107. 18. Clark, C., & Kalita, J. (2014). "A comparison of algorithms for the pairwise alignment of biological networks". Bioinformatics, 30(16), pp. 2351–2359. 19. CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004). "THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION". International Journal of Pattern Recognition and Artificial Intelligence, 18(03), pp. 265–298. 20. Correa, L., Borguesan, B., Farfan, C., Inostroza-Ponta, M., & Dorn, M. (2018). "A memetic algorithm for 3D protein structure prediction problem". IEEE/ACM Transactions on Computational Biology and Bioinformatics, 15(3), pp. 690–704. 21. Do Duc, D., Dinh, H. Q., & Hoang Xuan, H. (2008). "On the pheromone update rules of ant colony optimization approaches for the job shop scheduling problem". In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 5357 LNAI, pp. 153–160). 121 22. Dohrmann, J., & Singh, R. (2016). "The SMAL web server: global multiple network alignment from pairwise alignments". Bioinformatics, 32(21), pp. 3330–3332. 23. Dorigo, M., & Gambardella, L. M. (1997). "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem". IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 1(1), pp. 53. 24. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. Cambridge, Massachusetts, London England: MIT Press. 25. Edgar, R. C. (2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research, 32(5), pp. 1792–1797. 26. El-Kebir, M., Heringa, J., & Klau, G. W. (2011). "Lagrangian relaxation applied to sparse global network alignment". In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7036 LNBI, pp. 225–236). 27. Flannick, J., Novak, A., Balaji, S. S., Harley, H. M., & Batzglou, S. (2006). "Graemlin general and robust alignment of multiple large interaction networks". Genome Res., 16(9), pp. 214–231. 28. Fober, T., Mernberger, M., Klebe, G., & Hüllermeier, E. (2009). "Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules". Bioinformatics, 25(16), pp. 2110– 2117. 122 29. Garbelini, J. M. C., Kashiwabara, A. Y., & Sanches, D. S. (2018). "Sequence motif finder using memetic algorithm". BMC Bioinformatics, 19(1), pp. 4. 30. Gligorijević, V., Malod-Dognin, N., & Prulj, N. (2015). "Fuse: Multiple network alignment via data fusion". Bioinformatics, 32(8), pp. 1195– 1203. 31. Glover, F. (1986). "Future Paths for Integer Programming". Elsevier, 13(5), pp. 533–549. 32. Gong, M., Peng, Z., Ma, L., & Huang, J. (2016). "Global Biological Network Alignment by Using Efficient Memetic Algorithm". IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13(6), pp. 1117–1129. 33. Guzzi, P. H., & Milenković, T. (2018). "Survey of local and global biological network alignment: the need to reconcile the two sides of the same coin". Briefings in Bioinformatics, 19(3), pp. bbw132. 34. Hashemifar, S., Ma, J., Naveed, H., Canzar, S., & Xu, J. (2016). "ModuleAlign: Module-based global alignment of protein-protein interaction networks". Bioinformatics, 32(17), pp. i658–i664. 35. Hendlich, M., Bergner, A., Günther, J., & Klebe, G. (2003). "Relibase: Design and Development of a Database for Comprehensive Analysis of Protein–Ligand Interactions". Journal of Molecular Biology, 326(2), pp. 607–620. 36. Hendlich, M., Rippmann, F., & Barnickel, G. (1997). "LIGSITE: automatic and efficient detection of potential small molecule-binding 123 sites in proteins". Journal of Molecular Graphics and Modelling, 15(6), pp. 359–363. 37. Holland, J. H. (1975). "Adaptation in Natural and Artificial Systems". Ann Arbor MI University of Michigan Press. 38. Hu, J., Kehr, B., & Reinert, K. (2014). "NetCoffee: A fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks". Bioinformatics, 30(4), pp. 540–548. 39. Huan, H. X., Linh-Trung, N., Huynh, H.-T., & others. (2013). "Solving the Traveling Salesman Problem with Ant Colony Optimization: A Revisit and New Efficient Algorithms". REV Journal on Electronics and Communications, 2(3–4). 40. Huan, H. X., Tuyet, D. T. A., Ha, D. T. T., & Hung, N. T. (2015). "An Efficient Ant Colony Algorithm for DNA Motif Finding" (pp. 589– 601). Springer, Cham. 41. Ibragimov, R., Malek, M., Baumbach, J., & Guo, J. (2014). "Multiple graph edit distance". In Proceedings of the 2014 conference on Genetic and evolutionary computation - GECCO ’14 (pp. 277–284). New York, New York, USA: ACM Press. 42. Jukič, M., Konc, J., Gobec, S., & Janežič, D. (2017). "Identification of Conserved Water Sites in Protein Structures for Drug Design". Journal of Chemical Information and Modeling, 57(12), pp. 3094–3103. 43. Junker, B, H., & Schreiber, H. (2008). An introduction to biological networks and methods for their analysis. John Wiley &Sons. 124 44. Kelley, B. P., Bingbing, Y., Lewitter, F., Sharan, R., Stockwell, B. R., Ideker, T., Ideker. (2004). "PathBLAST: a tool for alignment of protein interaction networks". Nucleic Acids Res., 32(suppl_2), pp. W83–W88. 45. Kinoshita, K., & Nakamura, H. (2005). "Identification of the ligand binding sites on the molecular surface of proteins". Protein Science, 14(3), pp. 711–718. 46. Koyutürk, M., Kim, Y., Topkara, U., Subramaniam, S., Szpankowski, W., & Grama, A. (2006). "Pairwise alignment of protein interaction networks". J. Comput. Biol., 13(2), pp. 182–199. 47. Kuchaiev, O., Milenković, T., Memišević, V., Hayes, W., & Pržulj, N. (2010). "Topological network alignment uncovers biological function and phylogeny". J. R. Soc. Interface, 7. 48. Kuchaiev, O., & Pržulj, N. (2011). "Integrative network alignment reveals large regions of global network similarity in yeast and human". Bioinformatics, 27(10), pp. 1390–1396. 49. Liang, Z., Xu, M., Teng, M., & Niu, L. (2006). "NetAlign: a web-based tool for comparison of protein interaction networks". Bioinformatics, 22. 50. Liao, C., Lu, K., Baym, M., Singh, R., & Berger, B. (2009). "IsoRankN: spectral methods for global alignment of multiple protein networks". Bioinformatics, 25(12), pp. i253–i258. 51. M. Dorigo, V. M. and A. C. (1991). "Ant System: An Autocatalytic Optimizing Process". Technical Report 91-016, pp. 21. 125 52. M.Lesk, A. (2002). Introduction to Bioinformatics. New York: Oxford University Press Inc. 53. Malod-Dognin, N., & Pržulj, N. (2014). "GR-Align: fast and flexible alignment of protein 3D structures using graphlet degree similarity". Bioinformatics, 30(9), pp. 1259–1265. 54. Mamano, N., & Hayes, W. B. (2017). "SANA: simulated annealing far outperforms many other search algorithms for biological network alignment". Bioinformatics, 33(14), pp. 2156–2164. 55. Memišević, V., & Pržulj, N. (2012). "C-GRAAL: Common-neighbors- based global graph alignment of biological networks". Integr. Biol., 4(7), pp. 734–743. 56. Meng, L., Crawford, J., Striegel, A., & Milenkovic, T. (2016). "IGLOO: Integrating global and local biological network alignment". 57. Mernberger, M., Klebe, G., & Hullermeier, E. (2011). "SEGA: Semiglobal Graph Alignment for Structure-Based Protein Comparison". IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5), pp. 1330–1343. 58. Milenković, T., Ng, W. L., Hayes, W., & Pržulj, N. (2010). "Optimal network alignment with graphlet degree vectors". Cancer Inform., 9, pp. 121. 59. Mina, M., & Guzzi, P. H. (2012). "AlignMCL: Comparative analysis of protein interaction networks through Markov clustering". In Proceedings - 2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops, BIBMW 2012 (pp. 174–181). IEEE. 126 60. Neri, F. (2011). Handbook of memetic algorithms. (F. Neri, C. Cotta, & P. Moscato, Eds.), Studies in Computational Intelligence (Vol. 379). Berlin, Heidelberg: Springer Berlin Heidelberg. 61. Notredame, C., Higgins, D. G., & Heringa, J. (2000). "T-coffee: a novel method for fast and accurate multiple sequence alignment". Journal of Molecular Biology, 302(1), pp. 205–217. 62. Pache, R., & P Aloy. (2012). "A novel framework for the comparative analysis of biological networks". PLOS ONE, 7(2), pp. e31220. 63. Park, D., Singh, R., Baym, M., Liao, C.-S., & Berger, B. (2010). "IsoBase: a database of functionally related proteins across PPI networks". Nucleic Acids Research, 39(suppl_1), pp. D295--D300. 64. Patro, R., & Kingsford, C. (2012). "Global network alignment using multiscale spectral signatures". Bioinformatics, 28(23), pp. 3105–3114. 65. Sahraeian, S., & Yoon, B.-J. (2013). "SMETANA: Accurate and scalable algorithm for probabilistic alignment of large-scale biological networks.". PLOS ONE, 8(7), pp. e67995. 66. Saraph, V., & Milenković, T. (2014). "MAGNA: maximizing accuracy in global network alignment". Bioinformatics, 30(20), pp. 2931–2940. 67. Schmitt, S., Kuhn, D., & Klebe, G. (2002). "A New Method to Detect Related Function Among Proteins Independent of Sequence and Fold Homology". Journal of Molecular Biology, 323(2), pp. 387–406. 68. Schrijver, A. (2006). A Course in Combinatorial Optimization. Department of Mat., University of Amsterdam. 127 69. Sharan, R., & Ideker, T. (2006). "Modeling cellular machinery through biological network comparison". Nat. Biotechnol., 24(4), pp. 427–433. 70. Sharan, R., Suthram, S., Kelley, R. M., Kuhn, T., McCuine, S., Uetz, P., Ideker, T. (2005). "Conserved patterns of protein interaction in multiple species". In National Academy of Sciences (Vol. 102, pp. 1974–1979). National Academy of Sciences. 71. Singh, R., Xu, J., & Berger, B. (2007). "Pairwise global alignment of protein interaction networks by matching neighborhood topology". In Annual International Conference on Research in Computational Molecular Biology (pp. 16–31). Oakland, CA, USA: Springer. 72. Singh, R., Xu, J., & Berger, B. (2008). "Global alignment of multiple protein interaction networks". Proc. Pac. Symp. Biocomput., 13, pp. 303–314. 73. Sjolander, K. (2004). "Phylogenomic inference of protein molecular function: advances and challenges". Bioinformatics, 20(2), pp. 170– 179. 74. Stützle, T., & Hoos, H. H. (2000). "MAX–MIN Ant System". Future Generation Computer Systems, 16(8), pp. 889–914. 75. Thompson, J. D., Higgins, D. G., & Gibson, T. J. (1994). "CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice". Nucleic Acids Research, 22(22), pp. 4673– 4680. 128 76. Todd, A. E., Orengo, C. A., & Thornton, J. M. (2001). "Evolution of function in protein superfamilies, from a structural perspective". Journal of Molecular Biology, 307(4), pp. 1113–1143. 77. Tsai, S. Q., Iafrate, A. J., & Joung, J. K. (2014). "Genome editing: a tool for research and therapy: towards a functional understanding of variants for molecular diagnostics using genome editing". Nat. Med., 20(10), pp. 1103–1104. 78. Vijayan, V., Critchlow, D., & Milenković, T. (2017). "Alignment of dynamic networks". Bioinformatics, 33(14), pp. i180–i189. 79. Vijayan, V., & Milenkovic, T. (2018). "Multiple network alignment via multiMAGNA++". IEEE/ACM Transactions on Computational Biology and Bioinformatics, pp. 1–1. 80. Vijayan, V., Saraph, V., & Milenković, T. (2015). "MAGNA++: maximizing accuracy in global network alignment via both node and edge conservation". Bioinformatics, 31(14), pp. 2409–2411. 81. Volna, E. (2013). Introduction to Soft Computing. bookboon.com. 82. Weskamp, N., Hüllermeier, E., Kuhn, D., & Klebe, G. (2007). "Multiple graph alignment for the structural analysis of protein active sites". IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(2), pp. 310–320. 83. Xifeng Yan, Feida Zhu, Jiawei Han, & Yu, P. S. (2006). "Searching Substructures with Superimposed Distance". In 22nd International Conference on Data Engineering (ICDE’06) (pp. 88–88). IEEE. 129 84. Yan, X., Yu, P. S., & Han, J. (2005). "Substructure similarity search in graph databases". In Proceedings of the 2005 ACM SIGMOD international conference on Management of data - SIGMOD ’05 (pp. 766–777). New York, New York, USA: ACM Press. 85. Yang, W., & Lai, L. (2017). "Computational design of ligand-binding proteins". Current Opinion in Structural Biology, 45, pp. 67–73. 86. Yang, X.-S. (2014). "Nature-Inspired Optimization Algorithms". In Nature-Inspired Optimization Algorithms. Elsevier. 87. Yang, X.-S., & Wiley InterScience (Online service). (2010). Engineering optimization : an introduction with metaheuristic applications. John Wiley. 88. Yuan, X., Xu, Y., Yuan, X., & Xu, Y. (2018). "Recent Trends and Applications of Molecular Modeling in GPCR–Ligand Recognition and Structure-Based Drug Design". International Journal of Molecular Sciences, 19(7), pp. 2105. 89. Zaslavskiy, M., Bach, F., & Vert, J. P. (2009). "Global alignment of protein-protein interaction networks by graph matching methods". Bioinformatics, 25(12), pp. i259-1267. 90. Zhang, J., & Yu, P. S. (2015). "Multiple Anonymized Social Networks Alignment". In 2015 IEEE International Conference on Data Mining (pp. 599–608). IEEE. 91. Zhang, S., Hu, M., & Yang, J. (2007). "TreePi: A Novel Graph Indexing Method". In 2007 IEEE 23rd International Conference on Data Engineering (pp. 966–975). IEEE. 130 92. Zhang, Y., Tang, J., Yang, Z., Pei, J., & Yu, P. S. (2015). "COSNET". In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD’15 (pp. 1485–1494). New York, New York, USA: ACM Press.