Phương pháp tối ưu đàn kiến dóng hàng toàn cục các mạng tương tác protein
Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016
DOI: 10.15625/vap.2016.00077
PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN DÓNG HÀNG TOÀN CỤC
CÁC MẠNG TƯƠNG TÁC PROTEIN
Đỗ Xuân Quyền1, Nguyễn Hoàng Đức2, Thái Đình Phúc2, Đỗ Đức Đông2
1 Trƣờng THPT Quang Trung, Hải Phòng
2 Trƣờng đại học Công nghệ, Đại học Quốc gia Hà Nội
TÓM TẮT— Dóng hàng toàn cục các mạng tương tác protein (PPI) cung cấp thông tin giúp phát hiện các chức năng của protein,
vì vậy bài toán này đang được nghiên cứu rộng rãi. Bài báo này giới thiệu một thuật toán metaheuristics hiệu quả, ACOPPI, để
dóng hàng mạng PPI. Thuật toán ứng dụng phương pháp tối ưu đàn kiến xây dựng dóng hàng và kết hợp tìm kiếm cục bộ. Thực
nghiệm cho thấy thuật toán đề xuất có điểm dóng hàng tốt hơn so với các thuật toán SPINAL, FastNA đã công bố.
Từ khóa— Protein-protein interraction network, ant colony optimization.
I.GIỚI THIỆU
Cách tiếp cận trƣớc đây để phát hiện các chức năng của protein là dựa trên các quan hệ tiến hóa, với tiêu chí
thƣờng đƣợc sử dụng là độ tƣơng tự giữa các trình tự [3, 23]. Tuy nhiên, chỉ tính tƣơng đồng trình tự thƣờng không đủ
để nhận dạng các phức hợp protein đƣợc bảo tồn [12, 24, 26]. Sự phát triển của các kỹ thuật công nghệ sinh học trong
hơn thập kỷ qua đã cho phép xây dựng đƣợc các mạng tƣơng tác protein (Protein-Protein Interraction Network – PPI
Network) cho nhiều loài sinh vật. Từ các dữ liệu này, một số bài toán về phân tích mạng PPI đã đƣợc đặt ra (xem [5, 8,
15-17]), chẳng hạn nhƣ: phân tích cấu trúc tô pô mạng [10], phát hiện mô-đun [4]... Trong đó, đặc biệt quan trọng là
các bài toán dóng hàng mạng PPI dựa trên kết hợp thông tin về sự tƣơng tác giữa các protein cùng với mối quan hệ tiến
hóa giữa các trình tự. Việc so sánh tính tƣơng đồng của các mạng PPI này cung cấp nhiều thông tin hữu ích cho dự
đoán các chức năng chƣa biết hoặc kiểm định các chức năng đã biết của các proteins [9, 11, 25].
Các kỹ thuật dóng hàng mạng PPI phát triển theo hai hƣớng tiếp cận: dóng hàng cục bộ và dóng hàng toàn cục.
Với dóng hàng cục bộ, mục tiêu sẽ là xác định các mạng con gần nhau về tô pô mạng hoặc tƣơng tự xâu (xem [13, 14,
21, 24]). Thông thƣờng, kết quả của dóng hàng cục bộ sẽ thể hiện nhiều mạng con chồng lấn nhau, điều này có thể dẫn
đến sự nhập nhằng khi một protein có thể đƣợc dóng hàng với nhiều protein khác. Mục tiêu của dóng hàng toàn cục
mạng là đƣa ra một đơn ánh giữa các protein của các mạng khác nhau để tránh các nhập nhằng trong dóng hàng cục bộ.
Bài toán này đƣợc Aladag và Erten [3] chứng minh là NP-hard.
Thuật toán dóng hàng toàn cục đáng chú ý đầu tiên là IsoRank [25]đƣợc Sing et al. (2008) đề xuất, phát triển
dựa trên dóng hàng cục bộ. Sau IsoRank, một số thuật toán tƣơng tự đã đƣợc đề xuất nhƣ PATH và GA [26], PISwap
[6, 7] nhờ đƣa thêm các nới lỏng thích hợp của hàm đánh giá trên tập các ma trận ngẫu nhiên hoặc ứng dụng tìm kiếm
cục bộ trên dóng hàng lời giải có sẵn từ một thuật toán khác.MI-GRAAL [15, 16] và các biến thể [19, 20] dựa trên kết
hợp kỹ thuật tham ăn với thông tin heuristics nhƣ: graphlet, hệ số phân nhóm, độ lập dị và độ tƣơng tự (giá trị E-values
từ chƣơng trình BLAST). Các thuật toán này đều đƣa ra kết quả nhanh và tốt hơn so với các thuật toán trƣớc đó. Tuy
nhiên, những thuật toán đã nêu chỉ tối ƣu cho độ chính xác (hàm mục tiêu) hoặc tính khả mở (thời gian chạy). Vì các
mạng PPI có thƣờng số nút lớn nên cả tính chính xác và tính khả mở cần đƣợc quan tâm. Gần đây, Aladag và Erten
(2013) đề xuất thuật toán SPINAL [3], là thuật toán cho kết quả tốt nhất và nhanh nhất là hiện nay. SPINAL là một
thuật toán heuristic thời gian đa thức, gồm hai pha: pha đầu tính điểm tƣơng đồng cho tất cả cặp protein; pha sau xây
dựng đơn ánh xạ bằng cách cải tiến một cách cục bộ từng tập con của lời giải hiện có. Năm 2015, Do, D. D, cùng các
cộng sự, đã đề xuất một thuật toán mới là FastNA [25] để dóng hàng toàn cục mạng PPI. Thuật toán gồm hai pha: pha
thứ nhất xây dựng dóng hàng ban đầu bằng một thuật toán heuristic dựa trên sự tƣơng quan giữa cấu trúc tô pô và sự
tƣơng đồng trình tự giữa các nút, sau pha này FastNA thu đƣợc một dóng hàng toàn cục ban đầu, pha thứ hai với thủ
tục Rebuild là một ý tƣởng độc đáo, nó trở điểm mạnh của thuật toán, ý tƣởng là giữ lại những phần dóng hàng tốt và
dựa vào đó để dựng lại toàn bộ dóng hàng, điều này khắc phục nhƣợc điểm của pha thứ nhất và cho một kết quả tốt hơn
hẳn về chất lƣợng dóng hàng và cả thời gian thực hiện so với SPINAL.
Phƣơng pháp tối ƣu đàn kiến (Ant Colony Optimization - ACO) [26] là cách tiếp cận metaheuristic, đƣợc giới thiệu
bởi Dorigo năm 1991 đang đƣợc nghiên cứu và ứng dụng rộng rãi cho các bài toán tối ƣu t hợp khó. Bài báo này đề thuật
toán ACOPPI sử dụng phƣơng pháp tối ƣu đàn kiến, kết hợp với thủ tục rebuild của FastNA nhƣ một thủ tục tìm kiếm cục
bộ. Thực nghiệm cho thấy thuật toán đề xuất có điểm dóng hàng tốt hơn so với các thuật toán SPINAL, FastNA.
Phần còn lại của bài báo đƣợc t chức nhƣ sau. Mục 2 phát biểu bài toán dóng hàng mạng và giới thiệu một số
vấn đề liên quan. Thuật toán ACOPPI đƣợc trình bày trong mục 3. Mục 4 mô tả thực nghiệm so sánh ACOPPI với
FastNA và SPINAL. Các kết luận và công việc tiếp theo đƣợc trình bày trong mục cuối.
II. BÀI TOÁN DÓNG HÀNG MẠNG VÀ CÁC VẤN ĐỀ LIÊN QUAN
Giả sử và là hai mạng tƣơng tác protein, trong đó ký hiệu tập các nút mô tả
các protein trong mạng tƣơng ứng; ký hiệu tập các cạnh mô tả mối quan hệ tƣơng tác giữa các protein
|
|
| |
| |
trong các mạng . Không giảm t ng quát, ta xem trong đó ký hiệu số phần tử của tập .
Đỗ Xuân Quyền, Nguyễn Hoàng Đức, Thái Đình Phúc, Đỗ Đức Đông
627
Dóng hàng mạng là tìm một đơn ánh từ vào tốt nhất theo một tiêu chí đánh giá nào đó. Hiện nay chƣa có
định nghĩa rõ ràng cho tiêu chí này, dƣới đây phát biểu toán học cho định nghĩa bài toán dóng hàng theo tiêu chí thông
dụng đƣợc dùng trong [1,4,5,14, 23].
Định nghĩa 1: (Dóng hàng mạng) Đồ thị là một mạng dóng hàng của hai đồ thị nếu nó
thỏa mãn:
i) Mỗi nút của đƣợc ký hiệu là tƣơng ứng với một cặp nút thuộc và thuộc .
ii) Hai nút phân biệt và thuộc thì và
iii) Cạnh thuộc nếu và chỉ nếu ( và .
Định nghĩa 2: Một dóng hàng mạng là lời giải của bài toán dóng hàng toàn cục của các mạng
proteins nếu nó cực đại global network alignment score (GNAS) cho bởi:
∑
| |
(1)
trong đó là tham số cân bằng giữa sự tƣơng đồng về tô pô mạng và sự tƣơng đồng trình tự giữa các
nút, giá trị ( )đƣợc tính xấp xỉ dựa trên BLAST bit-scores hoặc E-values.
Trong [1] Aladag và Erten [1] đã chứng minh bài toán tìm dóng hàng tối ƣu này là NP-hard.
III. THUẬT TOÁN ACOPPI
Khi áp dụng phƣơng pháp tối ƣu đàn kiến giải một bài toán cụ thể, cần giải quyết các vấn đề sau:
-
-
Cách xây dựng hành trình của mỗi kiến;
Chọn quy tắc cập nhật mùi.
3.1. Cách xây dựng hành trình của mỗi kiến
Mỗi kiến xây dựng hành trình tƣơng ứng với việc tạo ra một lời giải của bài toán. Trong bài toán này, khi kiến
xây dựng xong một hành trình cũng tƣơng ứng với việc tạo ra một phƣơng án dóng hàng mạng. Để kiến xây dựng hành
trình, đầu tiên ta khởi tạo là rỗng. Sau đó, ta lặp lại công việc sau cho tới khi tất cả các nút của đều đƣợc ghép:
kiến sẽ lựa chọn một nút (chƣa đƣợc ghép) thuộc , đồng thời xác định nút (chƣa đƣợc ghép) thuộc để ghép với
và thêm nút vào . Nút đƣợc lựa chọn với tiêu chí là nút mang nhiều thông tin nhất, là nút có nhiều cạnh
nối với các nút đã đƣợc ghép đƣợc trong . Nút đƣợc lựa chọn ngẫu nhiên với xác suất lựa chọn nút với
nút là:
∑
{
(2)
Trong đó là giá trị thông tin heuristic, là hai tham số quyết định đến sự ảnh
hƣởng tƣơng quan giữa thông tin mùi và thông tin heuristic, R là tập các đỉnh thuộc mà chƣa đƣợc ghép .
Sau khi mỗi kiến xây dựng xong một hành trình, tƣơng ứng với một phƣơng án dóng hàng mạng, phƣơng án
này sẽ đƣợc cải tiến nhờ thủ tục rebuild trong thuật toán FastNA [25].
3.2. Cập nhật mùi
Vết mùi thể hiện thông tin học tăng cƣờng qua mỗi vòng lặp. Trong bài toán này, đánh giá độ tốt khi ghép
nút với nút . Thuật toán ACOPPI sử dụng phƣơng pháp cập nhật mùi SMMAS [27], đây là cách cập nhật
mùi đơn giản và hiệu quả, cụ thể:
với {
3.3. Mô tả thuật toán
Dữ liệu đầu vào bao gồm: Đồ thị , tham số , Sự tƣơng đồng trình tự giữa các nút tƣơng ứng
{
}
{
của . Với mỗi tập con các cặp nút của tập , ký hiệu
}
Kết quả ra là một dóng hàng toàn cục .
Lƣợc đồ thuật toán trong Hình 1 và đƣợc thực hiện theo các bƣớc sau:
Bước 1. Khởi tạo: , | |
| |
với | |
Khởi tạo ma trận mùi
Bước 2. Thuật toán thực hiện chạy trong nhiều vòng lặp tiến hóa, điều kiện dừng có thể thiết đặt là giới hạn số vòng lặp
tiến hóa hoặc giới hạn thời gian chạy. Trong mỗi vòng lặp tiến hóa, sẽ có n_ants kiến xây dựng hành trình, mỗi kiến
thực hiện xây dựng hành trình nhƣ sau:
628
PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN DÓNG HÀNG TOÀN CỤC CÁC MẠNG TƢƠNG TÁC PROTEIN
Lặp với tới | | //mỗi kiến xây dựng hành trình
2.1. Kiến chọn nút trong có nhiều cạnh nối với các nút của
2.2. Kiến tìm nút j trong để ghép với theo (2)
2.3. B sung vào ;
2.4. Cập nhật dựa trên ;
2.5. Cải tiến lời giải do kiến xây dựng bằng thủ tục rebuild;
Bước 3. Chọn lời giải của kiến có kết quả tốt nhất tính theo (1);
Bước 4. Cập nhật mùi .
Algorithm 1 ACOPPI
Input: Đồ thị 1: ( ) Đồ thị 2: ( )
Sự tƣơng đồng trình tự giữa các nút:
Tham số cân bằng
Output: Dóng hàng mạng
Begin
Khởi tạo ma trận mùi và các tham số;
while (điều kiện kết thúc) do
for ant = 1 to n_ants do
|
|
for to do
= next_node_align( ); // chọn nút i có nhiều cạnh ghép với thành
= best_node_align( ); // kiến tìm nút để dóng hàng với
Update( )//
Update( // cập nhật các cạnh của
end-for
Cải tiến lời giải do kiến xây dựng bằng thủ tục rebuild;
end-for
Update(GNAS); //chọn kết quả tốt nhất
Update( );// cập nhật mùi
end-while
End
Hình 1. Lƣợc đồ thuật toán ACOPPI
IV. THỰC NGHIỆM, SO SÁNH KẾT QUẢ VỚI PHƯƠNG PHÁP SPINAL VÀ FastNA
Chúng tôi tiến hành thực nghiệm với các bộ dữ liệu mà SPINAL và FastNA dùng thực nghiệm theo tiêu chí
GNAS, từ đó làm cơ sở để so sánh hiệu quả với hai phƣơng pháp này.
4.1. Thực nghiệm
Bảng 1. Thông tin về dữ liệu
Dữ liệu
Ce
Dm
Sc
Số lƣợng protein (số nút)
Số lƣợng tƣơng tác (số cạnh)
2805
7518
5499
9633
4495
25635
31261
34327
Hs
Với 4 bộ dữ liệu mạng PPI: Saccharomyces cerevisiae (sc), Drosophila melanogaster (dm), Caenorhabditis
elegans (ce) và Homo sapiens (hs). Các dữ liệu này lấy từ [20] với số protein (số nút) và tƣơng tác (số cạnh) đƣợc cho
trong bảng 1. Thực nghiệm trên 6 cặp mạng khác nhau (ce-dm, ce-hs, ce-sc, dm-hs, dm-sc, hs-sc. Tham số nhận 5 giá
trị lần lƣợt bằng 0.3, 0.4, 0.5, 0.6, 0.7 nhƣ trong [1]. Số kiến sử dụng là n_ants = 10 kiến và số vòng lặp tiến hóa là 100.
Với mỗi cặp mạng PPI và một tham số , chúng tôi cho chƣơng trình ACOPPI chạy 20 lần, thống kê kết quả tốt
nhất, tồi nhất, trung bình của 20 lần chạy. Ngoài ra, chúng tôi thống kê cả độ lệch chuẩn để đánh giá sự n định của
thuật toán.
Kết quả thực nghiệm cho thấy chỉ có 03 bộ dữ liệu có độ lệch chuẩn trên 5% (ce-dm, =0.4; dm-hs, =0.3; ce-
hs, =0.3), còn lại đều dƣới 5%. Điều đó cho thấy thuật toán tƣơng đối n định.
Đỗ Xuân Quyền, Nguyễn Hoàng Đức, Thái Đình Phúc, Đỗ Đức Đông
629
Bảng 2. Kết quả thực nghiệm của ACOPPI theo tiêu chí GNAS
GNAS
Tồi nhất
832.52
1098.48
1370.75
1640.24
1882.64
879.68
Độ lệch
chuẩn
28.2
17.1
30.9
25.5
49.8
14.0
28.1
47.1
22.0
43.1
16.2
23.4
37.1
29.8
56.4
31.4
24.2
67.1
34.3
83.6
22.6
21.5
35.7
46.6
45.8
25.8
37.5
39.5
64.3
50.1
Dữ liệu
Tốt nhất
871.90
Trung bình
845.87
0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
0.3
0.4
0.5
0.6
0.7
1132.28
1423.58
1695.37
1988.85
907.83
1204.98
1533.92
1814.15
2125.83
947.17
1253.58
1584.46
1881.86
2209.16
2338.23
3100.49
3903.09
4643.84
5418.28
2064.87
2745.92
3440.56
4146.21
4823.11
2470.01
3292.55
4121.73
4948.06
5770.44
1117.88
1398.01
1675.85
1948.93
897.11
1182.04
1490.97
1794.66
2091.70
933.16
1233.45
1552.57
1856.31
2161.71
2311.71
3078.24
3843.51
4614.06
5355.05
2045.85
2728.14
3408.96
4107.10
4782.83
2448.04
3262.86
4090.46
4893.83
5733.31
ce-dm
1151.3
ce-sc
ce-hs
dm-hs
dm-sc
hs-sc
1464.01
1777.82
2038.63
921.03
1216.44
1526.57
1827.45
2093.65
2279.92
3065.58
3807.47
4592.64
5237.49
2016.55
2709.92
3387.25
4072.89
4734.98
2430.87
3224.92
4047.1
4823.59
5678.02
4.2. So sánh
Từ dữ liệu trong bảng 2, chúng tôi tiến hành lấy kết quả trung bình của 20 lần chạy để so sánh với kết quả của hai thuật
toán SPINAL và FastNA, thể hiện trong bảng 3.
Bảng 3. So sánh kết quả thực nghiệm của ACOPPI với SPINAL và FastNA
Dữ liệu
Thuật toán
SPINAL
FastNA
ACOPPI
SPINAL
FastNA
ACOPPI
SPINAL
FastNA
ACOPPI
SPINAL
FastNA
ACOPPI
SPINAL
FastNA
ACOPPI
SPINAL
FastNA
717.99
778.46
845.87
728.26
863.46
933.16
709.12
834.79
897.11
1883.22
2260.31
2311.71
1579.06
1977.82
2045.85
1731.81
2268.21
2448.04
941.19
1034.20
1117.88
993.07
1144.17
1233.45
963.28
1109.93
1182.04
2517.23
3007.11
3078.24
2075.14
2631.85
2728.14
2253.66
3017.96
3262.86
1159.93
1290.11
1398.01
1229.95
1429.89
1552.57
1168.95
1389.21
1490.97
3160.48
3755.36
3843.51
2668.65
3290.03
3408.96
2839.00
3772.96
4090.46
1350.59
1545.86
1675.85
1501.61
1708.81
1856.31
1422.74
1663.39
1794.66
3790.79
4496.45
4614.06
3180.27
3950.16
4107.10
3434.54
4520.51
4893.83
1586.87
1801.24
1948.93
1764.93
1994.87
2161.71
1683.13
1936.83
2091.70
4451.60
5242.32
5355.05
3759.07
4603.41
4782.83
4066.22
5279.88
5733.31
ce-dm
ce-hs
ce-sc
dm-hs
dm-sc
hs-sc
ACOPPI
Với mỗi bộ dữ liệu là một cặp mạng PPI và một giá trị tham số chúng tôi so sánh kết quả của thuật toán
ACOPPI với SPINAL và FastNA theo hai tiêu chí GNAS. Bảng dữ liệu III cho thấy toàn bộ kết quả của ACOPPI đều
vƣợt trội so với SPINAL và hơn đáng kể so với FastNA. Đặc biệt, kết quả tồi nhất trong 20 lần chạy của ACOPPI cũng
đều tốt hơn FastNA và SPINAL.
V. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
ACOPPI là phƣơng pháp meta heuristic cho bài toán dóng hàng toàn cục các mạng tƣơng tác protein. So với
các phƣơng pháp heuristic trƣớc đây, thấy thuật toán đề xuất có tính n định và có điểm dóng hàng vƣợt trội so với
SPINAL và tốt hơn đáng kể so với FastNA.
630
PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN DÓNG HÀNG TOÀN CỤC CÁC MẠNG TƢƠNG TÁC PROTEIN
Trong [1], các tác giả có đề xuất một phiên bản của SPINAL cho tiêu chí GOC. Trong thời gian tới, chúng tôi
sẽ nghiên cứu, phát triển ACOPPI theo hƣớng này.
VI. LỜI CẢM ƠN
Bài báo đƣợc hoàn thành trong khuôn kh của đề tài KHCN cấp ĐHQGHN, Mã số đề tài: QG.15.21.
TÀI LIỆU THAM KHẢO
[1] Aladag, A. E. and Erten,C. (2013), SPINAL: scalable protein interaction network alignment. Bioinformatics, Vol. 29 no 7,
917–924
[2] Bader, G. D. and Hogue, C. W. (2002), Analyzing yeast protein-protein interaction data obtained from different sources. Nat.
Biotechnol., 20, 991–997.
[3] Banks, E. et al., (2008), NetGrep: fast network schema searches in interactomes. Genome Biology, 9,R138
[4] Chindelevitch, L. et al. (2010), Local optimization for global alignment of protein interaction networks. In: Pacific Symposium
on Biocomputing, Hawaii, USA, pp. 123–132
[5] Chindelevitch L. et al. (2013), Optimizing a global alignment of protein interaction networks, Bioinformatics ,Vol. 29 no. 21,
2765–2773
[6] Dost, B. et al. (2008), QNet: a tool for querying protein interaction networks. J. Comput. Biol., 15, 913–925
[7] Dutkowski, J. and Tiuryn, J. (2007), Identification of functional modules from conserved ancestral protein–protein interactions.
Bioinformatics, 23, i149–i158.
[8] Han, J. D. et al. (2004), Evidence for dynamically organized modularity in the yeast protein-protein interaction network.
Nature, 430, 88–93.
[9] B. H. Junker and F. Schreiber, Analysis of Bological Networks, wiley, 2008
[10] Kelley, B. P. et al. (2003), Conserved pathways within bacteria and yeast as revealed by global protein network alignment.
Proc. Natl Acad. Sci. USA, 100, 11394–11399.
[11] Kelley, B. P. et al. (2004), Pathblast: a tool for alignment of protein interaction networks. Nucleic Acids Res., 32,83–88.
[12] Koyuturk, M. et al. (2006), Pairwise alignment of protein interaction networks. J. Comput. Biol., 13, 182–199.
[13] Kuchaiev, O. et al. (2010), Topological network alignment uncovers biological function and phylogeny. J. R. Soc. Interface., 7,
1341–1354.
[14] Kuchaiev, O. and Przulj, N. (2011) Integrative network alignment reveals large regions of global network similarity in yeast
and human. Bioinformatics, 27, 1390–1396.
[15] Kuhn HW: The Hungarian Method for the assignment problem. Naval Res Logistics Q 1955, 2:83-97.
[16] Liao, C.S. et al. (2009) IsoRankN: spectral methods for global alignment of multiple protein networks. Bioinformatics, 25,
i253–i258.
[17] Memisevic,V. and Przulj,N. (2012), C-graal: common-neighbors-based global graph alignment of biological networks. Integr.
Biol., 4, 734–743.
[18] Milenkovic, T. et al. (2010), Optimal network alignment with graphlet degree vectors. Cancer Inform., Vol.9, 121–137.
[19] Narayanan, M. and Karp, R. M. (2007), Comparing protein interaction networks via a graph match-and-split algorithm. J.
Comput. Biol., Vol. 14, 892–907.
[20] Park, D. et al. (2011) IsoBase: a database of functionally related proteins across PPI networks. Nucleic Acids Res., 39, 295–300
[21] Remm, M. et al. (2001), Automatic clustering of orthologs and in-paralogs from pairwise species comparisons. J. Mol. Biol.,
314, 1041–1052.
[22] Sharan, R. et al. (2005), Conserved patterns of protein interaction in multiple species. Proc. Natl Acad. Sci. USA, 102, 1974–
1979.
[23] Singh, R. et al. (2008), Global alignment of multiple protein interaction networks. In: Pacific Symposium on Biocomputing.
pp. 303–314.
[24] Zaslavskiy, M. et al. (2009) Global alignment of protein-protein interaction networks by graph matching methods.
Bioinformatics, Vol.25, 259–267.
[25] Do, D. D. et al. (2015), An efficient algorithm for global alignment of protein-protein interaction networks. Int. Conf. ATC
2015, pp. 332-336.
[26] M. Dorigo and T. Stutzle. Ant Colony Optimization. The MIT Press, Cambridge, Masachusetts, 2004.
[27] Do, D. D., Dinh, Q. H, & Hoang, X. H. (2008). On the pheromone update rules of antcolony optimization approaches for the
job shop scheduling problem. In Bui, T. D., Ho,T. V, Ha, Q. T., editors, The 11th Paci_c Rim International Conference on
Multi-Agents:Intelligent Agents and Multi-Agent Systems, volume 5357 of Lecture Notes in ComputerScience, 153-160,
Springer, Heidelberg.
AN EFFICIENT ANT COLONY OPTIMIZATION FOR GLOBAL
ALIGNMENT OF PROTEIN-PROTEIN INTERACTION NETWORK
Do Xuan Quyen, Nguyen Hoang Duc, Thai Dinh Phuc, Do Duc Dong
ABSTRACT— Global alignment of protein-protein interaction (PPI) network provides helpful information to discover features of
protein, therefore the problem has been well studied worldwide. We present an effective metaheuristics algorithm ACOPPI, to tackle
this problem. The algorithm applies Ant Colony Optimization (ACO) method to align PPI network combined with local search.
Based on experiments, our algorithm showed better results than the published SPINAL algorithm and fastNA algorithm.
5 trang
19800
Free
Bạn đang xem tài liệu "Phương pháp tối ưu đàn kiến dóng hàng toàn cục các mạng tương tác protein", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- phuong_phap_toi_uu_dan_kien_dong_hang_toan_cuc_cac_mang_tuon.pdf
