ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
TRẦN NGỌC HÀ
MỘT SỐ THUẬT TOÁN DÓNG HÀNG CÁC MẠNG PROTEIN
Chuyên ngành: Khoa học máy tính
Mã số: 9480101.01
TÓM TẮT LUẬN ÁN
TIẾN SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. Hoàng Xuân Huấn
GS. TS. Thái Trà My
HÀ NỘI – 2019
Công trình được hoàn thành tại:
Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội
Người hướng dẫn khoa học: PGS. TS. Hoàng Xuân Huấn
GS.TS. Thái Trà My
Phản biện: ......................................................................................................
......................................................................................................
Phản biện: ......................................................................................................
......................................................................................................
Phản biện: ......................................................................................................
......................................................................................................
chức năng ở các loài chưa nghiên cứu kỹ từ các tri thức của các loài đã biết, nhờ đó hiểu rõ hơn quan hệ tiến
hóa sinh học, hỗ trợ thông tin để nghiên cứu thuốc điều trị các bệnh di truyền. Các bài toán này thuộc loại NPkhó và đang thu hút nhiều người nghiên cứu/ứng dụng do tính quan trọng của chúng.
Trong bối cảnh đó, chúng tôi chọn chủ đề nghiên cứu "Một số thuật toán dóng hàng các mạng protein”
với nội dung là nghiên cứu áp dụng các kỹ thuật TƯTH mềm để đề xuất một số thuật toán thông minh giải hai
bài toán dóng hàng nhiều mạng các vị trí liên kết protein và dóng hàng toàn cục 2 mạng tương tác proteinprotein với chất lượng lời giải và thời gian tính toán tốt hơn so với các thuật toán mới nhất hiện nay.
2. Mục tiêu của luận án
Tìm hiểu các dạng bài toán dóng hàng các mạng protein nêu trên và đánh giá ưu nhược điểm của các thuật
toán giải cho các bài toán này đã được đề xuất trong thời gian gần đây. Bên cạnh đó là tìm hiểu các kỹ thuật
tính toán mềm để thấy rõ ưu và nhược điểm của từng phương pháp. Trên cơ sở đó, đề xuất các thuật toán mới
với chất lượng lời giải tốt hơn các thuật toán hiện tại trong thời gian ngắn hơn cho các bài toán này.
Cài đặt và chạy thực nghiệm các thuật toán đề xuất trên các bộ dữ liệu thực để đánh giá hiệu quả của các
thuật toán mới đề xuất so với các thuật toán trước đó.
3. Các đóng góp của luận án
Trong thời gian qua, cùng với cán bộ hướng dẫn và các cộng sự, tác giả luận án đã có đóng góp sau.
- Đề xuất ba thuật toán dựa trên tối ưu đàn kiến cho bài toán dóng hàng nhiều đồ thị, bao gồm
ACO-MGA, ACO-MGA2 và ACOTS-MGA.
- Đề xuất ba thuật toán cho bài toán dóng hàng toàn cục mạng tương tác protein-protein, bao gồm
thuật toán heuristic FASTAN và hai thuật toán tối ưu đàn kiến: ACOGNA và ACOGNA++.
Các kết quả thực nghiệm cho thấy hiệu quả của các thuật toán đề xuất tốt hơn so với các thuật toán được
đề xuất trước đó và đã được công bố trong 5 báo cáo hội nghị/hội thảo quốc gia/quốc tế bao gồm 4 báo cáo
hội nghị quốc tế (Công trình 1,2,3,5) và một hội thảo toàn quốc “Nghiên cứu cơ bản và ứng dụng công nghệ
thông tin” (Công trình 4), và một bài báo đăng ở tạp chí VNU Journal of Science: Computer Science and
Communication Engineering (công trình 6).
4. Bố cục của luận án
Ngoài phần mở đầu và kết luận, luận án được tổ chức như sau:
Chương 1 giới thiệu hai bài toán dóng hàng mạng tương tác protein-protein và dóng hàng nhiều đồ thị cùng
một số vấn đề liên quan. Giới thiệu các phương pháp metaheuristic bao gồm phương pháp tối ưu đàn kiến, tính
toán tiến hóa, các thuật toán memetic và tìm kiếm Tabu.
Chương 2 trình bày ba thuật toán dựa trên phương pháp tối ưu đàn kiến để giải bài toán dóng hàng nhiều
mạng các vị trí liên kết của protein cùng các kết quả thực nghiệm trên các bộ dữ liệu mô phỏng và dữ liệu thực
chất, mạng tương tác protein-protein (protein-protein interactive network: PPI), mạng các vị trí liên kết/hoạt
tính protein. Không giống như các nghiên cứu về các chuỗi gen, nghiên cứu mạng sinh học cho phép hiểu được
các quá trình tế bào phức tạp phát sinh từ các hoạt động chung của các phân tử sinh học.
Những tiến bộ trong công nghệ sinh học hiện thời cung cấp nhiều dữ liệu cho phép ta nghiên cứu sâu hơn
về các mạng sinh học và cho ta nhiều tri thức quý giá. Chẳng hạn, việc dóng hàng mạng sinh học nhằm tìm
tương ứng đủ tốt giữa các nút mạng của các loài khác nhau cho phép xác định các vùng mạng có kiểu cấu trúc
topology và cấu trúc trình tự, nhờ đó có thể chuyển một cách hiệu quả các kiến thức về chức năng của tế bào
từ các loài đã được nghiên cứu tốt sang những loài chưa được nghiên cứu nhiều hoặc khó làm thực nghiệm.
Bởi vì việc nghiên cứu thực nghiệm trên con người gặp nhiều khó khăn bởi các rào cản đạo đức và pháp luật,
nhờ dóng hàng mạng mà người ta có thể chuyển các tri thức đã biết từ nấm men, ruồi giấm, hoặc sâu sang tri
thức của con người dựa trên phát hiện các vùng mạng được bảo tồn.
Luận án tập trung nghiên cứu hai bài toán thời sự: dóng hàng toàn cục hai mạng tương tác protein-protein
và dóng hàng nhiều mạng các vị trí liên kết/hoạt tính protein.
1.1.2. Bài toán dóng hàng nhiều mạng các vị trí liên kết protein.
Suy diễn chức năng của các protein chưa biết thông qua các protein đã biết giữ vai trò quan trọng trong lĩnh
vực khoa học sự sống nói chung và lĩnh vực hóa dược nói riêng. Trong đó, so sánh các protein giữ vai trò trung
tâm.
Dự đoán chức năng của các protein có thể thực hiện được ở cả mức chuỗi và mức độ cấu trúc. Nhận thấy
rằng các protein với sự giống nhau của chuỗi amino axit trên 40% thường có các chức năng tương tự [Todd,
Orengo, & Thornton, 2001] nên so sánh theo trình tự thường là phương pháp đầu tiên được sử dụng. Nhiều
phương pháp tiếp cận khác nhau được giới thiệu và sử dụng rộng rãi [Altschul et al., 1997; Edgar, 2004; M.A.
et al., 2007; Notredame, Higgins, & Heringa, 2000; Sjolander, 2004; Thompson, Higgins, & Gibson, 1994].
Tuy nhiên, phương pháp này không phù hợp để xác định sự tương đồng chức năng giữa các phân tử bởi vì sự
tương đồng chức năng có liên quan mật thiết với các đặc tính cấu trúc hơn là các đặc tính tuần tự
2
Để phân tích cấu trúc của các protein, một số tác giả [CONTE et al., 2004; Kinoshita & Nakamura, 2005;
Oleksii Kuchaiev & Pržulj, 2011; Mernberger, Klebe, & Hullermeier, 2011; Xifeng Yan, Feida Zhu, Jiawei
Han, & Yu, 2006; Yan et al., 2005; Zhang, Hu, & Yang, 2007] đề xuất sử dụng mô hình đồ thị để biểu diễn
1.1.2.2. Bài toán dóng hàng nhiều đồ thị
Thông qua việc mô hình hóa cấu trúc của các protein thành đồ thị, các kỹ thuật dóng hàng đồ thị được sử
dụng để xác định sự tương đồng chức năng dựa trên phân tích cấu trúc. Các phương pháp đầu tiên chủ yếu dựa
trên các kỹ thuật so khớp chính xác các cặp đồ thị. Các nghiên cứu này đã thu được một số kết quả có ý nghĩa
khi nghiên cứu tiến hóa chức năng của các phân tử không thuần nhất (non-homologous). Tuy nhiên khó có thể
áp dụng các kỹ thuật này để khám phá các mẫu sinh học có ý nghĩa được lưu lại một cách gần đúng.
Để khắc phục hạn chế của các phương pháp so khớp đồ thị, bài toán dóng hàng nhiều đồ thị (MultiGraph
Alignment: MGA) được Weskamp và các cộng sự [Weskamp et al., 2007] đề xuất đầu tiên năm 2007 và sử
dụng để phân tích cấu trúc các vị trí hoạt tính của protein. Các tác giả cũng đề xuất 1 thuật toán heuristic để
giải bài toán này. Trong cách tiếp cận này, mỗi túi liên kết protein (protein binding pocket) được mô hình bởi
một đồ thị liên thông G(V,E) và bài toán MGA được phát biểu như sau:
Cho một tập hợp G ={G1(V1,E1),…,Gn(Vn,En)} các đồ thị liên thông, mỗi đỉnh có nhãn thuộc tập cho trước
và các cạnh có trọng số; trong mỗi đồ thị có các phép toán: xóa một đỉnh, thay nhãn một đỉnh, đổi trọng số
của một cạnh; nhiệm vụ của bài toán MGA là tìm dóng hàng cho các đỉnh của các đồ thị trong tập G để tối
ưu một hàm mục tiêu định trước.
3
MGA là bài toán NP-khó, các thuật toán heuristic chỉ thích hợp cho các bài toán cỡ nhỏ, nên không phù
hợp với các ứng dụng thực tế. Fober và các cộng sự đã mở rộng sử dụng bài toán này cho phân tích cấu trúc
phân tử sinh học và đề xuất một thuật toán tiến hóa với tên gọi GAVEO [Fober et al., 2009]. Thực nghiệm cho
thấy thuật toán này hiệu quả hơn thuật toán mà Weskamp đề xuất.
Đối với các bài toán NP-khó, đã có nhiều cách tiếp cận mô phỏng tự nhiên để tìm lời giải gần đúng. Đặc
biệt, thực nghiệm cho thấy phương pháp tối ưu đàn kiến tốt hơn các thuật toán tiến hóa trong nhiều bài toán
điển hình. Trong chương 2, chúng tôi sẽ giới thiệu các thuật toán dựa trên thuật toán tối ưu đàn kiến có kết hợp
tìm kiếm địa phương để dóng hàng nhiều mạng các vị trí hoạt tính của protein.
1.1.3. Bài toán dóng hàng mạng tương tác protein
Các protein trong mỗi cơ thể sống không tồn tại một cách độc lập mà chúng tương tác với nhau. Dựa trên
nghiên cứu thực nghiệm, người ta xây dựng được các CSDL về các mạng tương tác protein (PPI). Việc dóng
hàng hai mạng PPI cho phép chúng ta phát hiện các tương đồng chức năng giữa hai loài nhờ phát hiện các
toán độ tương tự giữa các nút trong cùng một mạng.
4
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ở. Vì các mạng PPI
thường có số đỉnh lớn nên cả tính chính xác và tính khả mở (thời gian chạy) cần được quan tâm. Sử dụng tiêu
chuẩn GNAS, Aladag và các cộng sự [Aladag & Erten, 2013] đề xuất thuật toán SPINAL cho lời giải tốt hơn
các thuật toán trước đó cả về thời gian và chất lượng lời giải.
Gần đây, Saraph và các cộng sự đề xuất thuật toán MAGNA (2014) dựa trên giải thuật di truyền với quần
thể ban đầu khởi tạo ngẫu nhiên hoặc kết hợp với lời giải được tìm bởi các thuật toán như: IsoRank, MIGRAAL và GHOST. MAGNA và phiên bản cải tiến MAGNA ++ [Vijayan, Saraph, & Milenković, 2015]sử
dụng độ đo chất lượng dóng hàng S3, thực nghiệm cho thấy chúng cải thiện đáng kể chất lượng lời giải của các
thuật toán được dùng để khởi tạo.
Somaye Hashemifar và các cộng sự (2016) giới thiệu 1 thuật toán tối ưu toàn cục mới tên là ModuleAlign,
thuật toán này sử dụng thông tin tối ưu cấu trúc cục bộ để định nghĩa một hàm đánh giá tính tương đồng dựa
trên module (module-based homology score). Dựa trên một thuật toán phân cụm chức năng của các protein có
gắn kết về mặt chức năng vào trong cùng module, ModuleAlign sử dụng một cơ chế lặp mới để tìm dóng hàng
giữa 2 mạng. Các thực nghiệm đã cho thấy ModuleAlign cho kết quả chất lượng dóng hàng tốt hơn một số
thuật toán đề xuất trước đó trong một số trường hợp.
1.2. Tối ưu mềm
1.2.1. Giới bài toán tối ưu tổ hợp và tiếp cận mềm
1.2.1.1. Phát biểu bài toán tối ưu tổ hợp tổng quát
Một cách tổng quát, mỗi bài toán TƯTH có thể phát biểu như sau: Cho một bộ ba (𝑆, 𝑓, Ω), trong đó S là
tập hữu hạn trạng thái (lời giải tiềm năng hay phương án), f là hàm mục tiêu xác định trên S, còn Ω là tập các
ràng buộc. Mỗi phương án s ∈ S thỏa mãn các ràng buộc Ω gọi là phương án (hay lời giải) chấp nhận được.
Mục đích của ta là tìm phương án chấp nhận được s ∗ tối ưu hóa toàn cục hàm mục tiêu f. Chẳng hạn với bài
toán cực tiểu thì f(s ∗ ) ≤ f(s) với mọi phương án chấp nhận được s.
1.2.1.2. Tính toán mềm
Tính toán mềm (Soft Computing) cho một cách tiếp cận để giải quyết các bài toán khó, thông tin không
đầy đủ, thiếu chắc chắn và cho kết quả là những lời giải đủ tốt hoặc gần đúng mà tiếp cận truyền thông hay
tính toán cứng (hard computing) không giải quyết được. Tiếp cận này gồm các phương pháp sử dụng tập mờ/
pháp ACO để giải các bài toán tối ưu tổ hợp khó
Khi mô phỏng hành vi của đàn kiến để giải các bài toán thực, người ta dùng đa tác tử (multiagent) làm
đàn kiến nhân tạo, trong đó mỗi con kiến nhân tạo là một tác tử, có nhiều khả năng hơn kiến tự nhiên. Kiến
nhân tạo (về sau sẽ gọi là kiến) có bộ nhớ riêng, có khả năng mở rộng, chẳng hạn, ghi nhớ các đỉnh đã thăm
trong hành trình và tính được độ dài đường đi nó chọn. Ngoài ra các con kiến có thể trao đổi thông tin có được
với nhau, thực hiện tính toán cần thiết, cập nhật mùi…
Nhờ các khả năng mở rộng mà mỗi đàn kiến có thể thực hiện lặp quá trình tìm lời giải nhờ thủ tục bước
tuần tự trên đồ thị cấu trúc tương ứng của mỗi bài toán và cập nhật mùi theo phương thức học tăng cường để
tìm lời giải chấp nhận được và xác định lời giải đủ tốt toàn cục.
1.2.2.2.Lược đồ chung của phương pháp ACO
Thuật toán 2.2. Thuật toán ACO
Procedure Thuật toán ACO
Begin
Initialize: Khởi tạo vết mùi, n_ants
while Khi điều kiện dừng chưa thỏa mãn do
for i=1 to n_ants do
Xây dựng lời giải;
Cập nhật lời giải tốt;
end for
Cập nhật mùi
end while
End
1.2.2.3.Thủ tục bước ngẫu nhiên xây dựng lời giải
Giả sử kiến đã phát triển được xâu 〈𝑢0 , … , 𝑢𝑚 〉 trong đó 𝑢𝑚 = 𝑖 nhưng chưa cho lời giải chấp nhận được
và nhờ Ω ta xác định được tập đỉnh 𝐽𝑘 (𝑖) có thể phát triển thì thành phần … 𝑢𝑖+1 = 𝑗 tiếp theo được chọn với
xác suất
[𝜏𝑖𝑗 (𝑡)]𝛼 .[𝜂𝑖𝑗 (𝑡)]𝛽
𝜌. 𝜏
𝑛ế𝑢 (𝑖, 𝑗) ∉ 𝑤(𝑡)
Δ𝜏𝑖,𝑗 = { 𝑚𝑖𝑛
𝜌. 𝜏𝑚𝑎𝑥 𝑛ế𝑢 (𝑖, 𝑗) ∈ 𝑤(𝑡)
(2.8)
Trong đó w(t) là lời giải tốt nhất mà các kiến xây dựng được. Quy tắc này cũng khởi tạo 0 = max.
Đây là một phương pháp cập nhật mùi dễ cài đặt và có độ phức tạp tính toán cũng thấp hơn so với các
phương pháp trước nó. Thực nghiệm và phân tích toán học cho thấy nó tốt hơn MMAS.
1.2.2.5. Tìm kiếm địa phương
Thông thường thì các kỹ thuật tìm kiếm địa phương hội tụ đến cực trị địa phương nhanh hơn. Vì vậy người
ta thường áp dụng kỹ thuật tìm kiếm địa phương để tăng cường chất lượng lời giải cho lời giải tốt nhất hoặc
cho mọi lời giải trong mỗi bước lặp trước khi cập nhật mùi. Các kỹ thuật tìm kiếm có thể áp dụng linh hoạt
theo lược đồ memetic được nêu trong mục 1.2.3.2.
1.2.2.6. Nhận xét về phương pháp ACO
So với GA, ở mỗi bước lặp, ACO không dùng lại nhiều lời giải của bước lặp trược như GA, hơn nữa việc
kết hợp học tăng cường và thông tin heuristic sẽ tăng hiệu quả tìm kiếm.
Việc tìm kiếm ngẫu nhiên cho phép tìm kiếm linh hoạt, mềm dẻo trên miền rộng hơn phương pháp heuristic
sẵn có. Để tăng cường khả năng khám phá, ACO có thể áp dụng khởi tạo lại vết mùi sau một số bước lặp mà
không tìm được lời giải tốt hơn.
Thuật toán ACO dễ song song hóa để giảm thời gian chạy trên máy song song do mỗi con kiến tìm lời giải
một cách độc lập trong mỗi vòng lặp.
Với những lý dó trên, luận án tập trung vào phát triển các thuật toán dựa trên đàn kiến.
1.2.3. Tính toán tiến hóa và các thuật toán Memetic
1.2.3.1. Tính toán tiến hóa
Thuật ngữ tính toán tiến hóa ban đầu để chỉ các phương pháp tìm lời giải nhờ đưa về sử dụng GA. Ngày
nay nó dùng để chỉ chung cho các phương pháp tối ưu dựa trên quần thể, trong đó quần thể của thế hệ sau được
xây dựng dựa trên thông tin từ quần thể trước để tìm lời giải. Các thuật toán này thường được xây dựng dựa
tốt. Ngược lại các thuật toán lặp cho chất lượng lời giải tốt hơn nhưng lại có thời gian chạy lớn.
Mục 1.2 của luận án giới thiệu tổng quan về bài toán tối ưu tổ hợp và một số phương pháp tối ưu mềm
như ACO, lược đồ memetic, tìm kiếm Tabu. Luận án cũng đã có những nhận xét về một số ưu điểm của các
phương pháp này, trong đó có chỉ rõ những ưu điểm của phương pháp ACO so với GA. Từ những phân tích
này, luận án tập trung nghiên cứu kết hợp thuật toán ACO với các thuật toán tìm kiếm cục bộ hay tìm kiếm
Tabu theo lược đồ memetic để đề xuất các thuật toán mới giải quyết hiệu quả 2 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-protein ở trên. Chương 2
và chương 3 của luận án tập trung trình bày chi tiết các đề xuất mới này.
1.4. Kết luận chương
Chương 1 của luận án đã trình bày các kiến thức tổng quan về tin sinh học và 2 bài toán là hướng nghiên
cứu chính của luận án là 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 mạng
tương tác protein. Bên cạnh đó, chương 1 giới thiệu tổng quan về các phương pháp tối ưu theo tiếp cận tính
toán mềm, bao gồm GA, phương pháp ACO, tính toán tiến hóa, các thuật toán memetic và kỹ thuật tìm kiếm
Tabu Search. Trong đó, luận án cũng đã tập trung trình bày chi tiết về phương pháp ACO, phân tích rõ những
ưu điểm của phương pháp này so với các phương pháp tối ưu mềm khác. Đây là cơ sở để luận án đề xuất các
thuật toán mới để giải quyết các bài toán dóng hàng nhiều mạng các vị trí liên kết protein được trình bày ở
chương 2 và bài toán dóng hàng toàn cục hai mạng tương tác protein được trình bày ở chương 3.
Chương 2. DÓNG HÀNG CÁC MẠNG CÁC VỊ TRÍ LIÊN KẾT PROTEIN
Chương này giới thiệu các khái niệm liên quan đến bài toán dóng hàng nhiều đồ thị, một công cụ để phân
tích cấu trúc protein. Bên cạnh đó giới thiệu 3 thuật toán phát triển dựa trên phương pháp tối ưu hóa đàn kiến:
ACO-MGA, ACO-MGA2, ACOTS-MGA.
2.1. Bài toán dóng hàng nhiều đồ thị
Weskamp và các cộng sự đã giới thiệu bài toán dòng hàng nhiều đồ thị và các khái niệm liên quan để áp
dụng cho bài toán dóng hàng các mạng các vị trí liên kết protein như dưới đây
2.1.1. Tập nhiều đồ thị (multigraph)
Một multigraph là một tập hợp các đồ thị G ={G1(V1,E1),…,Gn(Vn,En)}, trong đó các đồ thị Gi(Vi,Ei) liên
thông, đỉnh được gán nhãn thuộc tập L cho trước, các cạnh có trọng số biểu thị khoảng cách giữa các đỉnh.
Định nghĩa 2.1. (Các toán tử chỉnh sửa) Trên các đồ thị G(V,E) của tập đồ thị G có các toán tử chỉnh sửa:
i) Chèn hoặc xóa bớt các nút: Một nút 𝑣 ∈ 𝑉 và các cạnh liên kết với nó có thể bị xóa hoặc được chèn
vào
es(a i , a j )
(2.1)
1i j m
trong đó ns là điểm đánh giá tính phù hợp của hàng tương ứng và được tính theo biểu thức (2.2), còn es đánh
giá tính tương thích của độ dài cạnh và được tính bởi biểu thức (2.3):
nsm
l(a ij )=l(aki )
a
i
i
nsmm l(a j ) l(ak )
ns
i
i
a i 1 j k n ns a j = , ak
n
i
i
ns a j , ak
i
1
giá trị tương ứng bằng esmm
2.2. Thuật toán dựa trên ACO
2.2.1. Đồ thị cấu trúc
Đồ thị cấu trúc gồm n tầng, tầng thứ i là đồ thị Gi của G, các đỉnh của
tầng trên đều có cạnh kết nối với các đỉnh tầng dưới. Hình 2.2 minh họa
đồ thị cấu trúc, trong đó không hiển thị các cạnh ở mỗi đồ thị trong mỗi
tầng, nút hình tròn là nút thực còn nút biểu diển bởi hình vuông là nút
giả.
Một dóng hàng của đồ thị theo định nghĩa 2.2 ở trên là một tập đường
đi từ G1 qua mọi tầng đến Gn sao cho mỗi đường chỉ đi qua một đỉnh của
mỗi tầng và mỗi đỉnh thực của đồ thị cấu trúc đều có đúng một đường đi
qua, riêng các đỉnh ảo thì cho phép có nhiều đường qua nó.Tập đường đi
này có thể xem là chỉ 1 đường duy nhất như quan niệm của thuật toán
ACO thông dụng với ngầm định rằng đường này khởi đầu từ một đỉnh
của G1 đi qua các đồ thị kế tiếp, khi đến tầng đầu hoặc tầng cuối
Hình 2.2. Đồ thị cấu trúc khi
thì “bước” sang đỉnh khác cùng tầng rồi quay lại cho đến khi qua
dóng hàng n đồ thị, trong đó mỗi
hết mọi đỉnh thực mỗi đỉnh đúng một lần.
đồ thị có 2 hoặc 3 nút thực
9
2.2.2. Thủ tục bước ngẫu nhiên để xây dựng một dóng hàng
Trong mỗi bước lặp, mỗi con kiến sẽ thực hiện lặp quá trình xây dựng các vectơ a = (a1,…,an) cho một
dóng hàng 𝐴 như sau.
Kiến chọn ngẫu nhiên một đỉnh thực trên đồ thị cấu trúc và dựa trên thông tin heuristic và vết mùi để bước
ngẫu nhiên xây dựng lời giải. Để dễ hình dung, ta giả thiết đỉnh thực này ở G1 (được ký hiệu là a1, kiến sẽ bước
ngẫu nhiên qua các tầng để đến Gn như sau. Nếu kiến đã xây dựng được vectơ (a1,…,ai) trong đó aq là đỉnh j
trong Gi thì nó chọn đỉnh k trong Gi+1 với xác suất cho bởi công thức (2.4):
Sau khi vectơ a được phát triển hết thành a=(a1,…an) thì các đỉnh thực trong a bị loại ra khỏi đồ thị cấu
trúc để tiếp tục lặp thủ tục dóng hàng của kiến đến khi mọi đỉnh thực đã được dóng hàng. Quá trình dóng hàng
của kiến được minh họa trong hình 2.2, trong đó đỉnh giả đánh số -1, các đỉnh khác đánh số 0,1, 2….theo thứ
tự của các đỉnh trong đồ thị thực. Lưu ý rằng nếu đỉnh thực được chọn ban đầu không thuộc G1 mà là Gm thì
thủ tục trên gồm hai quá trình dóng dần từ Gm tới Gn và dóng ngược từ Gm tới G1.
2.2.3. Qui tắc cập nhật mùi
Vết mùi được cập nhật theo quy tắc cập nhật mùi SMMAS như trong công thức 2.6:
ij ,k (1 ) ij ,k ij ,k
(2.6)
Trong đó: i . max
j ,k
. min
(i,j,k) lêi gi¶i tèt nhÊt (2.7)
(i,j,k) lêi gi¶i tèt nhÊt
Với max và min là các tham số cho trước.
2.2.4. Thủ tục tìm kiếm cục bộ
Thủ tục tìm kiếm địa phương được áp dụng cho lời giải tốt nhất theo
nguyên tắc tốt nhất thì dừng. Trong thủ tục này, các cặp đỉnh cùng nhãn
trong mỗi đồ thị Gi được chọn ngẫu nhiên sẽ đổi chỗ cho nhau trong
vectơ dóng hàng của nó để 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 và dừng thủ tục tìm kiếm
củ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
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.
count (k , a) 1
k lµ ®Ønh thùc
i
nij ,k (a )
1
k lµ ®Ønh gi¶
nV
. max
(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ự
(𝑎) 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 label (a)
là tập các nhãn của các đỉnh thuộc véctơ dóng hàng a, gọi Bi {v Gi | label (v) label (a)} 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
( ij ,k ) . ij ,k (a)]
suất là: p ij ,k
(2.9)
sB ( ij ,s ) .[ ij ,s (a)]
i 1
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.
ij ,k (1 ) ij ,k ij ,k
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
12
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.
-35
-570
-1055
Thời gian (s)
0.6
2.3
6
17
Điểm
-20
65
45
1132
Thời gian (s)
Điểm
249
8
16
-1144
-4704
-31004
-155508
4.8
11.3
49
210.8
Điểm
-101
-75
-10872
-33698
32
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ị
GAVEO
8
ACO-MGA
16
32
74
-38
1254
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 ACOMGA 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/(n2*Vmax2), 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/(n2*Vmax2) 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ị
-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.
14
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 đó 𝛼 ∈ [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.
f ( E1 )
(3.2)
EC
E1
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
15
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.
f ( E1 )
,
V12 i, f (i) : i V1 , f (i) V2 ; E12 ( u, f (u) , v, f (v) ) : (u, v) E1,( f (u), f (v)) E2
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 V1=
{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.
16
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 𝐺12 cho lần lặp tiếp theo, quá
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 V1
2.2.1. Tìm đỉnh i RV1 có số cạnh tới các đỉnh trong V 1 lớn nhất;
2.2.2. Sử dụng thuật toán ACO tìm đỉnh f(i)= j RV2 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.
1
Chú ý rằng ở bước 2.2.1, việc tìm i RV1 có số cạnh tới các đỉnh trong V 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ị Gi . 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
17
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 G1 dóng
với 1 đỉnh của G2 sau đó quay lại G1 rồi tiếp tục dóng với 1 đỉnh của G2 , lặp lại cho tới khi tất cả các đỉnh
của G1 đã đượ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 i V1 với đỉnh j V2 được khởi tạo bằng 𝜏𝑚𝑎𝑥 và sau đó được
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:
ij (1 ) ij ij
. max
ij
. min
(3.11)
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
(1i )a .[i ]b
jT (1j )a .[ j ]b
(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 i V1 đỉnh j V2 được các kiến lựa chọn theo xác suất.
pij
( ij )c .[ ij ]d
kRV2
(3.14)
( ki )c .[ki ]d
1
(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 đó
20
𝜌. 𝜏𝑚𝑖𝑛 𝑛ế𝑢 < 𝑖, 𝑓(𝑖) > 𝑘ℎô𝑛𝑔 𝑐ó đỉ𝑛ℎ 𝑘ề
Δ𝜏𝑖 = {
(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)
j=f(i)
. max
ij (1 ) ij ij
(3.19)
ij
25635
31261
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.
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
FASTAN
SPINAL
717.99
778.46
2343.0
2560.7
728.26
863.46
2370.0
2842.8
709.12
834.79
2326.0
2761.1
1883.22
7481.9
2075.14
2631.85
5150.0
6565.5
2253.66
3017.96
5593.0
7528.5
α = 0.5
FASTAN
SPINAL
1159.93
1290.11
2300.0
2567.2
1229.95
1429.89
2437.0
2844.9
1168.95
1389.21
2323.0
2769.7
3160.48
3755.36
6282.0
7429.0
2668.65
6577.4
3434.54
4520.51
5706.0
7527.0
α = 0.7
FASTAN
1801.24
2567.6
1994.87
2843.4
1936.83
2763.1
5242.32
7478.8
4603.41
6572.3
5279.88
7538.1
SPINAL
1586.87
2258.0
1764.93
2512.0
1683.13
2398.0
4451.6
6344.0
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.
2749.2
2758.2
2726.10
2728.3
2753.7
863.46
913.39 1144.17
1207.94 1429.89
1513.4 1708.81
1824.69 1994.87 2091.43
2842.8
2838.1
2844.9
2838.0
2843.4
3015.3
3001.1
3014.2
3033.0
2982.6
834.79
876.78 1109.93
1178.46 1389.21
1457.65 1663.39
1742.2 1936.83 2064.12
2761.1
2761.2
2769.7
2766.5
2763.1
7008.7
7019.2
7030.2
7000.90
7009.6
2268.21
2429.12 3017.96
3256.54 3772.96
3938.3 4520.51
4895.45 5279.88
5693.4
7531.8
7528.5
7535.2
7527
7538.1
8072.9
8182.8
7666.0
8153.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
ce-dm
ce-hs
ce-sc
0.6070
0.6747
0.6448
0.3159
0.2239
0.2608
α = 0.7
0.6126
0.6635
0.6553
0.3138
0.2240
0.2601
EC
0.5217
0.3061
0.6002
0.1921
0.1575
0.1680
MAGNA++
ICS
0.0700
0.1288
0.1449
0.0885
0.0569
α = 0.4
0.1123
0.0993
0.0953
0.1559
0.1417
0.1452
ACOGNA
α = 0.5
0.1068
0.0953
0.0925
0.156
0.1415
0.1484
α = 0.6
0.1338
0.0939
0.0911
0.1567
0.1407
0.1446
21
α = 0.7
0.1061
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 S 3, 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
ce-dm
ce-hs
ce-sc
dm-hs
sc-dm
sc-hs
α = 0.3
0.1344
0.1265
0.1063
0.1593
0.1446
0.1501
α = 0.4
0.1123
0.0993
0.0953
0.1559
ACOGNA++
0.2597
0.2639
0.2573
0.1088
0.1081
0.1166
0.1538
0.1354
0.1192
0.1117
0.1059
0.1174
0.3655
0.4165
0.2795
0.1910
0.1767
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++
30000
Thời gian (s)
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).
22
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
Copyright: Tài liệu đại học ©