ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
MỘT SỐ THUẬT TOÁN DÓNG HÀNG CÁC MẠNG PROTEIN
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2019
ĐẠ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
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS.TS Hoàng Xuân Huấn
2. GS. TS. Thái Trà My
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2019
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết
quả được viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả
trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa
từng được ai công bố trong các công trình nào khác.
Tác giả
1
LỜI CẢM ƠN Luận án được thực hiện tại trường ĐH Công nghệ - ĐHQG Hà Nội, dưới
sự hướng dẫn của PGS.TS Hoàng Xuân Huấn và GS.TS Thái Trà My.
Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Hoàng Xuân Huấn, cô Thái
Trà My, những người đã có những định hướng giúp tôi thành công trong việc
nghiên cứu của mình. Thầy cũng đã động viên và chỉ bảo giúp tôi vượt qua
những khó khăn để tôi hoàn thành được luận án này.
Tôi xin chân thành cảm ơn tới TS. Đỗ Đức Đông, TS. Đặng Cao Cường
và các thầy cô ở Bộ môn Khoa học máy tính trường Đại học Công nghệ đã
đóng góp cho tôi nhiều kiến thức quý báu về kiến thức khoa học để tôi có thể
hoàn thành luận án.
Tôi cũng xin cảm ơn tới các thầy, cô thuộc khoa Công nghệ thông tin –
Trường ĐH Công Nghệ, đã tạo mọi điều kiện thuận lợi giúp tôi trong quá trình
làm nghiên cứu sinh.
Tôi cũng xin cảm ơn tới các thầy cô ở khoa Toán, và lãnh đạo trường
Đại học Sư Phạm – Đại học Thái Nguyên, đã tạo mọi điều kiện thuận lợi về
mặt thời gian và công tác chuyên môn giúp tôi trong quá trình làm nghiên cứu
sinh.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè nơi đã cho
tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay.
2
MỤC LỤC
DANH MỤC BẢNG BIỂU .............................................................................. 7
DANH MỤC CÁC HÌNH ................................................................................. 9
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ........................................... 10
MỞ ĐẦU ......................................................................................................... 12
Chương 1. DÓNG HÀNG CÁC MẠNG PROTEIN VÀ TỐI ƯU MỀM ...... 16
1.1. Tin sinh học và dóng hàng các mạng protein ...................................... 16
1.1.2. Bài toán dóng hàng nhiều mạng các vị trí liên kết protein. ................. 22
1.1.3. Bài toán dóng hàng mạng tương tác protein - protein ......................... 26
1.2. Tối ưu mềm .......................................................................................... 31
1.2.1. Bài toán tối ưu tổ hợp và tiếp cận mềm ............................................... 31
1.2.2. Phương pháp tối ưu đàn kiến ............................................................... 35
1.2.3. Tính toán tiến hóa và các thuật toán memetic ..................................... 44
1.2.4. Thuật toán tìm kiếm Tabu .................................................................... 45
1.3. Động cơ nghiên cứu ............................................................................. 47
1.4. Kết luận chương ................................................................................... 48
Chương 2. DÓNG HÀNG CÁC MẠNG CÁC VỊ TRÍ LIÊN KẾT PROTEIN
......................................................................................................................... 49
2.1. Bài toán dóng hàng nhiều đồ thị .......................................................... 49
2.1.1. Tập nhiều đồ thị ................................................................................... 50
2.1.2. Dóng hàng nhiều đồ thị ........................................................................ 50
2.1.3. Hàm đánh giá chất lượng dóng hàng ................................................... 51
3
2.2. Thuật toán dựa trên ACO ..................................................................... 54
2.2.1. Đồ thị cấu trúc ...................................................................................... 55
2.2.2. Thủ tục bước ngẫu nhiên để xây dựng một dóng hàng ........................ 56
2.2.3. Qui tắc cập nhật mùi ............................................................................ 59
2.2.4. Thủ tục tìm kiếm cục bộ ...................................................................... 59
2.3. Thuật toán theo lược đồ memetic ........................................................ 60
2.3.1. Lược đồ chung ..................................................................................... 61
2.3.2. Đồ thị cấu trúc ...................................................................................... 63
2.3.3. Vết mùi và thông tin heuristic .............................................................. 63
2.3.4. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng ............................ 64
2.3.5. Qui tắc cập nhật vết mùi ...................................................................... 64
2.3.6. Thủ tục tìm kiếm cục bộ ...................................................................... 65
2.4. Thuật toán memetic mới kết hợp ACO và tìm kiếm Tabu .................. 65
2.4.1. Đồ thị cấu trúc ...................................................................................... 67
2.4.2. Thông tin heuristic ............................................................................... 67
2.4.3. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng ............................ 67
2.4.4. Qui tắc cập nhật vết mùi ...................................................................... 68
2.4.5. Thủ tục tìm kiếm Tabu ......................................................................... 68
2.5. Các kết quả thực nghiệm ...................................................................... 69
2.5.1. Dữ liệu thực nghiệm ............................................................................ 69
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 ........................................................................................................... 70
4
2.5.3. Thực nghiệm so sánh các thuật toán ACOTS-MGA, ACO-MGA2,
GAVEO và Greedy ......................................................................................... 75
2.6. Kết luận chương ................................................................................... 80
Chương 3. DÓNG HÀNG TOÀN CỤC HAI MẠNG TƯƠNG TÁC
PROTEIN-PROTEIN ...................................................................................... 81
3.1. Bài toán dóng hàng toàn cục mạng tương tác protein ......................... 81
3.1.1. Phát biểu bài toán ................................................................................. 81
3.1.2. Đánh giá chất lượng dóng hàng toàn cục ............................................. 82
3.2. Thuật toán FASTAN ............................................................................ 84
3.2.1. Xây dựng dóng hàng ban đầu .............................................................. 85
3.2.2. Thủ tục Rebuild .................................................................................... 87
3.2.3. Độ phức tạp của thuật toán FASTAN so với SPINAL ........................ 88
3.3. Thuật toán ACOGNA .......................................................................... 89
3.3.1. Lược đồ chung ..................................................................................... 91
3.3.2. Đồ thị cấu trúc ...................................................................................... 92
3.3.3. Vết mùi và thông tin heuristic .............................................................. 93
3.3.4. Thủ tục bước ngẫu nhiên để xây dựng dóng hàng ............................... 94
3.3.5. Quy tắc cập nhật vết mùi ..................................................................... 94
3.3.6. Thủ tục tìm kiếm cục bộ ...................................................................... 95
3.4. Thuật toán ACOGNA++ ...................................................................... 95
3.4.1. Mô tả thuật toán ................................................................................... 96
3.4.2. Vết mùi ................................................................................................. 96
5
3.4.3. Thủ tục xác định cặp đỉnh dóng hàng .................................................. 97
3.4.4. Quy tắc cập nhật vết mùi ..................................................................... 98
3.4.5. Thủ tục tìm kiếm cục bộ ...................................................................... 99
3.5. Kết quả thực nghiệm ............................................................................ 99
3.5.1. Dữ liệu thực nghiệm ............................................................................ 99
3.5.2. Thực nghiệm so sánh thuật toán FASTAN với thuật toán SPINAL . 100
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++ .............................................................................................. 103
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 ..................................................... 108
3.6. Kết luận chương ................................................................................. 110
KẾT LUẬN ................................................................................................... 113
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN
QUAN ĐẾN LUẬN ÁN ............................................................................... 117
TÀI LIỆU THAM KHẢO ............................................................................. 118
6
DANH MỤC BẢNG BIỂU
Bảng 2.1. So sánh chất lượng dóng hàng S(A) và thời gian chạy với các bộ dữ
liệu gồm 4, 8, 16 và 32 đồ thị, số đỉnh trung bình của mỗi đồ thị là 20 đỉnh.
................................................................................................................. 71
Bảng 2.2. So sánh chất lượng dóng hàng S(A) và thời gian chạy với các bộ dữ
liệu gồm 4, 8, 16 và 32 đồ thị, số đỉnh trung bình của mỗi đồ thị là 50 đỉnh
................................................................................................................. 71
Bảng 2.3. So sánh điểm 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à 50s. .............................................................................................. 73
Bảng 2.4. So sánh điểm 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à 150s ............................................................................................. 73
Bảng 2.5. So sánh điểm 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 ............................................................................................. 73
Bảng 2.6. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4, 8,16
và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời gian
chạy là 200s ............................................................................................. 74
Bảng 2.7. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4, 8,16
và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời gian
chạy là 300s ............................................................................................. 74
Bảng 2.8. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4, 8,16
và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời gian
chạy là 600s ............................................................................................. 74
7
Bảng 2.9. So sánh chất lượng lời giải 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ị ................................................................................. 76
Bảng 2.10. So sánh thời gian chạy (tính theo giây) 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ị ...................................................... 77
Bảng 2.11. So sánh điểm chất lượng dóng hàng S(A) của 3 thuật toán với cùng
thời gian chạy với các tập gồm 4,8,16 và 32 đồ thị. ............................... 79
Bảng 3.1. Mô tả bộ dữ liệu ............................................................................ 100
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 .......... 102
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. .................. 103
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. ............................... 105
Bảng 3.5. So sánh ACOGNA và MAGNA++ theo tiêu chuẩn EC .............. 106
Bảng 3.6. So sánh ACOGNA và MAGNA++ theo tiêu chuẩn S3 ............... 107
Bảng 3.7. So sánh các thuật toán theo tiêu chuẩn S3 .................................... 109
8
DANH MỤC CÁC HÌNH
Hình 1.1. Quá trình tổng hợp protein .............................................................. 17
Hình 1.2. Dóng hàng cục bộ và dóng hàng toàn cục ...................................... 27
Hình 1.3. Cách các con kiến thực chọn đường đi ngắn nhất để tha mồi về tổ 36
Hình 2.1. Một dóng hàng nhiều đồ thị của tập 4 đồ thị, đỉnh hình vuông là giả
còn các đỉnh tròn là đỉnh thực có nhãn là các ký tự tương ứng. ..................... 51
Hình 2.2. Ví dụ dóng hàng 2-đồ thị. ............................................................... 53
Hình 2.3. Đồ thị cấu trúc khi dóng hàng n đồ thị, trong đó mỗi đồ thị có 2 hoặc
3 nút thực ......................................................................................................... 56
Hình 2.4. Kiến xây dựng lời giải ..................................................................... 58
Hình 2.5. Một hoán vị cặp đỉnh có cùng nhãn trong thủ tục tìm kiếm địa phương
......................................................................................................................... 60
Hình 2.6. So sánh chất lượng lời giải các thuật toán với bộ dữ liệu gồm 16 đồ
thị và thời gian tăng từ 1000s đến 6000s. ....................................................... 78
Hình 3.1. Đồ thị cấu trúc của thuật toán ACOGNA ....................................... 93
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++ .............................................................................................. 110
9
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Viết tắt, SốTT Tiếng Việt Tiếng Anh ký hiệu
1
Tối ưu hóa đàn kiến
Ant Colony Optimization ACO
2
Giải thuật di truyền
Genetic Algorithm GA
3
Bài toán người chào hàng
Travelling Salesman Problem TSP
4
Tối ưu tổ hợp
Combinatorial Optimization TƯTH
5
Bầy ong nhân tạo
Artificial Bee Colony ABC
6
Tối ưu bầy đàn
Particle Swarm Optimization PSO
7
Hệ đàn kiến
Ant Colony System ACS
8
Hệ kiến
Ant System AS
9
Hệ kiến max - min
Max – Min Ant System MMAS
10 Hệ kiến max – min trơn
Smooth Max – Min Ant System SMMAS
11 Tương tác protein
Protein – Protein Interaction PPI
12 Sự chính xác về cạnh
Edge Correctness EC
13 Bảo tồn cấu trúc cảm sinh
Induced Conserved Structure ICS
14 Điểm cấu trúc con đối xứng Symmetric substructure score
15 Điểm dóng hàng toàn cục Global Network Aligment Score GNAS
S3
16 Nấm men
Saccharomyces Cerevisiae SC
17 Ruồi giấm
Drosophila Melanogaster DM
10
18 Người tinh khôn
Homo Sapiens HS
19 Giun tròn
Caenorhabditis Elegans CE
20 Dóng hàng nhiều đồ thị Multigraph Alignment
MGA
11
MỞ ĐẦU
Những phát hiện về cơ chế di truyền trong cơ thể sống đã thúc đẩy sinh
học phân tử nói riêng và công nghệ sinh học nói chung phát triển mạnh mẽ
trong nửa thế kỷ qua, trở nên lĩnh vực nghiên cứu và ứng dụng hấp dẫn. Tuy
nhiên các nghiên cứu trong phòng thí nghiệm đòi hỏi nhiều thời gian và tốn
kém. Cùng với sự phát triển của công nghệ thông tin, tin-sinh học [Junker, B &
Schreiber, 2008; M.Lesk, 2002] ra đời và là công cụ trợ giúp hiệu quả cho các
nghiên cứu sinh-y-dược.
Ngày nay, người ta hiểu rõ rằng các protein trong mỗi cơ thể sống quyết
định các đặc điểm sinh học quan trọng như kiểu hình, hệ miễn dịch… và việc
tổng hợp chúng được quy định bởi DNA hay là các bộ gene tương ứng theo
quá trình biểu diễn gene. Các mã di truyền của mỗi cá thể được lưu trong DNA
của nó, phát triển tuân theo quá trình tiến hóa đã được Darwin phát hiện và
Watson và Crick củng cố dựa trên các nghiên cứu vật lý.
Thoạt tiên, các kỹ thuật học máy được áp dụng để phân tích các trình tự
DNA và protein để phát hiện tính tương đồng/dị biệt cấu trúc giữa chúng. Các
phương pháp TƯTH mềm đã giải quyết hiệu quả các bài NP-khó trong lĩnh vực
này như dóng hàng các trình tự, xây dựng cây phân loài, suy diễn haplotype,
phát hiện motif và vị trí của nó trong bộ gene… Các kết quả này hỗ trợ đắc lực
cho lĩnh vực y học và sinh học trong phân tích các bộ gen, nghiên cứu đặc điểm
tiến hóa giữa các loài, phát hiện và điều trị bệnh di truyền…
Tuy nhiên, việc nghiên cứu tính tương đồng/khác biệt cấu trúc tuần tự là
không đủ để phát hiện tính tương đồng/khác biệt về chức năng trong cơ thể
sống. Việc nghiên cứu các mạng sinh học [Junker, B & Schreiber, 2008] như
mạng tương tác protein-protein (PPI), mạng điều hòa gen, mạng các vị trí liên
kết protein, mạng trao đổi chất …mang lại tiếp cận nghiên cứu hiệu quả hơn về
12
phân tích chức năng trong sinh học phân tử. Đặc biệt, việc dóng hàng các mạng
các vị trí liên kết protein và các mạng tương tác protein-protein cho phép chúng
ta dự đoán đặc điểm 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
NP-khó 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.
Hiểu rõ tầm quan trọng của tin-sinh học đối với phát triển công nghệ sinh
học của nước nhà, trong hơn 10 năm qua, ở khoa Công nghệ thông tin, Đại học
Công nghệ, Đại học Quốc gia Hà Nội đã hình thành và phát triển một nhóm
nghiên cứu các bài toán cơ bản và thời sự trong tin-sinh học nhằm góp phần tạo
tiền đề phát triển công nghệ sinh học nước nhà.
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 hai mạng
tương tác protein-protein 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.
Nhiệm vụ cụ thể đặt ra đối với tác giả luận án là:
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.
13
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 đó.
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++.
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 đó.
Các kết quả của luận án đã đượ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).
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 tổng quan về tin sinh học, hai 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à dóng hàng mạng tương tác
protein-protein cùng một số vấn đề liên quan. Giới thiệu các phương pháp
metaheuristic bao gồm giải thuật di truyền, 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.
14
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 đồng thời nhiều mạng các vị trí liên kết của protein.
Thuật toán thứ nhất là thuật toán ACO-MGA 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 đồ thị. Thuật toán thứ hai là thuật toán
ACO-MGA2 dựa trên lược đồ memetic, trong đó sử dụng phương pháp tối ưu
đàn kiến để tạo ra tập các lời giải và sử dụng các chiến lược tìm kiếm cục bộ
khác nhau để cải thiện chất lượng lời giải tốt nhất do các kiến tìm được. Thuật
toán thứ ba ACOTS-MGA là một thuật toán memetic dựa trên kết hợp ACO và
tìm kiếm cấm. 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 cho thấy các thuật toán đề xuất tốt hơn so với các thuật toán mới nhất
để giải bài toán dóng hàng đồng thời nhiều mạng các vị trí liên kết protein.
Chương 3 trình bày ba thuật toán đề xuất để giải bài toán dóng hàng toàn
cục hai mạng tương tác protein-protein. Thuật toán thứ nhất là thuật toán
FASTAN theo hướng tiếp cận heuristic. Tiếp theo là 2 thuật toán ACOGNA và
ACOGNA++ dựa trên phương pháp tối ưu đàn kiến. Hiệu quả của các thuật
toán được kiểm nghiệm trên các bộ dữ liệu chuẩn (IsoBase) được sử dụng bởi
các thuật toán mới nhất hiện nay. Các thực nghiệm đã cho thấy hiệu quả nổi
trội của các thuật toán đề xuất.
15
Chương 1. DÓNG HÀNG CÁC MẠNG PROTEIN VÀ TỐI ƯU MỀM
Trong chương này, đầu tiên luận án giới thiệu ngắn gọn bức tranh chung
của tin sinh học và giới thiệu 2 bài toán tối ưu tổ hợp quan trọng trong lĩnh vực
Tin sinh học là: Bài toán dóng hàng mạng nhiều mạng vị trí liên kết protein và
bài toán dóng hàng tương tác protein-protein. Tiếp theo đó, luận án giới thiệu
về các phương pháp tối ưu mềm là cơ sở để đề xuất các thuật toán mới để giải
quyết 2 bài toán dóng hàng các mạng protein.
1.1. Tin sinh học và dóng hàng các mạng protein
1.1.1. Giới thiệu về tin sinh học
Trong thế kỷ 19, nhà tự nhiên học đồng thời là nhà địa lý và sinh vật học
người Anh C. R. Darwin (1809 –1882) đã nhận thấy rằng theo thời gian, mỗi
loài sinh vật luôn biến đổi tiến hóa để phù hợp với môi trường sinh tồn của
chúng và đưa ra học thuyết tiến hóa nổi tiếng của ông. Nhờ các thành tựu của
khoa học và kỹ thuật vật lý, năm 1953, Crick và Watson đã khám phá cấu trúc
DNA mở đầu cho kỷ nguyên chinh phục cơ chế di truyền trong sinh vật phù
hợp với học thuyết Darwin.
Hơn 60 năm qua, sinh học phân tử nói riêng và công nghệ sinh học nói
chung phát triển mạnh mẽ, trở nên lĩnh vực nghiên cứu và ứng dụng hấp dẫn,
tạo ra cuộc cách mạng đối với sự hiểu biết của chúng ta về chức năng của tế
bào, mở ra con đường để phát hiện ra cơ chế sinh học phức tạp và sự liên quan
của chúng đến bệnh tật và sự phát triển của cơ thể sống. Trong đó, hiểu biết về
quá trình tổng hợp protein đặt nền tảng cho sinh học phân tử.
1.1.1.1. Quá trình tổng hợp protein
DNA mang thông tin di truyền và điều khiển tổng hợp protein của sinh
vật, còn protein quyết định đặc tính, chức năng và quá trình phát triển của cơ
16
thể sống [Lê Sỹ Vinh, 2014]. DNA là chuỗi xoắn kép được cấu tạo từ 4 loại
nucleotide: Adenine, Cytosine, Guanine và Thymine, chúng được ký hiệu
tương ứng là A, C, G và T. Một đoạn của chuỗi DNA mang thông tin cần thiết
để tạo nên protein gọi là một đoạn gen hay gọn hơn là một gen. Mỗi sinh vật
có nhiều gen, chẳng hạn con người có khoảng 25 nghìn gen khác nhau.
Quá trình tổng hợp protein từ thông tin ở DNA gồm 2 giai đoạn: phiên
mã và dịch mã [Lê Sỹ Vinh, 2014] như được minh họa trong hình 1.1.
Trong giai đoạn phiên mã, đoạn gen mang thông tin hướng dẫn tổng hợp
protein được chuyển sang đoạn RNA có nội dung tương tự đoạn gen nhờ thay
Thymine bởi Uracil, được ký hiệu là U.
Trong giai đoạn dịch mã, đoạn RNA được dịch mã để tạo nên chuỗi các
amino acid và chuỗi này được cuộn gấp (folded) tạo thành protein. Các protein
được cấu tạo từ 20 loại amino acid.
Hình 1.1. Quá trình tổng hợp protein
Trong quá trình tiến hóa, các gen/RNA/protein được di truyền và có thể
biến đổi nhờ các biến dị của các nucleotide/amino acid thành phần dưới dạng
xóa/chèn/ thay thế một nucleotide bằng một nucleotide khác. Tùy theo việc đặc
điểm sinh học của sinh vật do protein quy định có phù hợp với môi trường hay
không mà biến dị được củng cố tồn tại/ phát triển hoặc tiếp tục biến đổi bởi
17
biến dị khác nếu không triệt tiêu cùng các cá thể mang nó. Sự biến đổi theo thời
gian của các bộ gen tạo nên quá trình tiến hóa của các loài sinh vật. Nhận thức
này đặt cơ sở cho các nghiên cứu và ứng dụng trong sinh học phân tử và
tin-sinh học.
1.1.1.2. Sinh học phân tử và phân tích các trình tự trong tin sinh học
Thoạt tiên, các nghiên cứu sinh học phân tử được thực hiện và kiểm
chứng bằng thực nghiệm trong các phòng thí nghiệm. Tuy nhiên việc nghiên
cứu trong phòng thí nghiệm đòi hỏi nhiều thời gian và chi phí cao nên kìm hãm
tiến trình nghiên cứu. Các tri thức về quá trình tổng hợp protein và cấu trúc của
quá trình tổng hợp protein cùng sự phát triển, ứng dụng rộng rãi của công nghệ
thông tin cho phép thực hiện các phân tích Tin-Sinh để trợ giúp các dự đoán và
nghiên cứu trong sinh học phân tử.
Các bài toán và kỹ thuật dóng hàng trình tự [Lê Sỹ Vinh, 2014]
Dựa trên sự phân tích tương đồng/dị biệt cấu trúc của các trình tự DNA và
protein, người ta có được các nhận biết về quan hệ giữa các loài sinh vật và các
cá thể, dự đoán các đặc tính sinh học từ các loài mới dựa trên đặc tính của các
loài đã nghiên cứu kỹ gần với nó.
Như đã nói ở trên, trong quá trình tiến hóa của các loài, các gen/RNA/protein
được di truyền và có thể biến đổi nhờ các biến dị của các nucleotide/amino acid
thành phần dưới dạng xóa/chèn/ thay thế một nucleotide bằng một nucleotide
khác. Sau khi giải trình tự gen/RNA/protein người ta sử dụng các kỹ thuật học
máy để phân tích chúng, bắt đầu từ các bài toán đơn giản như dóng hàng 2 hoặc
nhiều trình tự, xác định trình tự con đến các bài toán phức tạp hơn như: xây
dựng cây phân loài, tìm kiếm motif và vị trí của chúng (xác định miền điều hòa
gen), suy diễn haplotype, dự đoán biến đổi amino acid, v.v.
18
Các bài toán phức tạp này được mô hình hóa dựa trên các nhận xét của các
nhà sinh học. Nhiều bài toán trong chúng là những bài toán tối ưu tổ hợp xử lý
dữ liệu tuần tự và thuộc loại NP-khó. Để dễ hình dung cách đặt bài toán và sử
dụng, ta trở lại với bài toán tìm kếm motif và làm quen với bài toán xây dựng
cây phân loài.
Bài toán tìm kiếm DNA motif và mô hình hóa tổng quát
DNA motif là một đoạn ngắn trong DNA, chúng thường có chức năng đặc
biệt đối với các gen trong bộ gen, chẳng hạn, điều hòa gen [Hoang X. Huan,
Tuyet, Ha, & Hung, 2015]. Đoạn này thường lặp đi lặp lại trong bộ gen. Các
thuật toán tin sinh sẽ tìm ra các đoạn nghi ngờ là motif và vị trí của chúng trên
các bộ gen để các nhà sinh vật kiểm tra lại bằng thực nghiệm thay vì tìm kiếm
mù để làm thực nghiệm.
Bài toán được mô hình hóa tổng quát như sau [Hoang X. Huan et al., 2015]:
Xét tập S = {S1,S2, ..., SN } các trình tự độ dài m trên bộ chữ cái Σ . Với giá trị l
< m cho trước , cần tìm trình tự x = {𝑥1,𝑥2, ..., 𝑥𝑖, ...𝑥𝑙 } trên bộ chữ cái Σ với
độ dài l và tập xâu con M = {𝑚1, 𝑚2,..., 𝑚𝑁} có cùng độ dài l được lấy ra từ
các chuỗi Si tương ứng sao cho nó tốt nhất theo một tiêu chuẩn định trước nào
đó.
Tiêu chuẩn đồng thuận xác định bởi tổng khoảng cách Hamming tới các xâu
trong tập là nhỏ nhất. Tuy nhiên người ta cũng có thể định nghĩa motif là xác
định hàm mục tiêu khác theo mục đích của nhà sinh học, chẳng hạn số trình tự
trong tập S có khoảng cách Hamming tới x là nhỏ nhất.
Với tiêu chuẩn được chọn, các thuật toán đề xuất sẽ cho ta các motif và vị
trí của chúng trên các trình tự để nhà sinh học xem xét quyết định làm thực
nghiệm kiểm định hay không (trợ giúp quyết định).
19
Bài toán xây dựng cây phân loài [Lê Sỹ Vinh, 2014]
Trong bài toán này, dựa trên phân tích tính tương đồng thể hiện qua dữ liệu
sinh học phân tử (DNA/protein) của các loài, người ta dự đoán quan hệ giữa
các loài và xây dựng cây phân loài. Hai loài có hệ gen và protein càng gần nhau
thì quan hệ tiến hóa càng gần nhau. Dựa trên phân tích quan hệ như vậy, người
ta xây dựng cây nhị phân không gốc với cấu trúc như sau:
Mỗi nút là ứng với một loài sinh vật hiện thời
Mỗi nút trong ứng với một loài sinh vật tổ tiên mà thông thường ta
không có thông tin về loài này.
Mỗi cạnh của cây nối nút của cây ứng với hai loài sinh vật có quan
hệ tiến hóa trực tiếp.
Khoảng cách nối hai nút ứng với hai loài trên cây cho biết khoảng
cách tiến hóa giữa chúng
Các quan hệ trên cây xây dựng được cho ta kết qủa dự đoán dựa trên kỹ
thuật phân tích hiện có, khi có thêm kỹ thuật mới để xét tính tương đồng, chẳng
hạn, tính tương tự mạng protein (sẽ đề cập ở dưới) ta sẽ điều chỉnh cho chính
xác hơn. Mặc dù các cây được xây dựng như thế không hoàn toàn chính xác
với tiến hóa thực nhưng nó rất hữu ích cho các nhà sinh học khi nghiên cứu các
loài sinh vật. Nhờ nó mà các nhà sinh học có thể dự đoán một số đặc điểm sinh
học có tính di truyền từ các đặc điểm của những loài gần gũi với nó.
Việc nghiên cứu tính tương đồng các trình tự DNA/Protein không đủ thông
tin cho nghiên cứu chức năng và đặc tính y học nên người ta quan tâm đến các
bài toán phân tích dữ liệu 3 chiều. Chẳng hạn, người ta nhận thấy trong quá
trình tổng hợp protein, nếu các amino acid được cuộn gấp sai sẽ gây nên các
bệnh di truyền. Nếu ta dự báo và phát hiện được lỗi cuộn gấp thì có thể phát
hiện bệnh và tìm được phương thức điều trị. Để phát triển nghiên cứu, người ta
đã xây dựng các CSDL không gian và các mạng sinh học.
20
1.1.1.3. Các mạng sinh học
Dóng hàng các chuỗi thuộc hệ gen đã tăng cường kiến thức y sinh học nhờ
phát hiện các vùng trình tự có sự tương đồng giữa các gen ở các loài khác nhau,
các vùng đó có khả năng phản ánh các mối quan hệ chức năng và tiến hóa giữa
các trình tự [Alföldi & Lindblad-Toh, 2013; Altschul, Gish, Miller, & Lipman,
1990; Biesecker et al., 2009; Tsai, Iafrate, & Joung, 2014]. Tuy nhiên, các gen
hoặc các sản phẩm protein của chúng không hoạt động một cách độc lập mà
chúng thực hiện các quá trình tế bào bằng cách tương tác với nhau.
Các tương tác này được mô hình hóa bởi mạng sinh học, chẳng hạn như:
mạng điều hòa gen, mạng trao đổi chất, mạng tương tác protein-protein
(protein-protein interactive: PPI), mạng các vị trí liên kết 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 ánh xạ 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ó sự tương đồng về kiểu cấu trúc tô pô 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 (Saccharomyces cerevisiae),
ruồi giấm (Drosophila melanogaster), hoặc sâu (Caenorhabditis elegans) 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 [Clark
& Kalita, 2014; Malod-Dognin & Pržulj, 2014; R. Sharan & Ideker, 2006].
21
Luận án này tập trung nghiên cứu hai bài toán thời sự: 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 hai mạng tương tác
protein-protein (về sau sẽ gọi gọn là mạng tương tác 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 [Borrel, 2016; W. Yang & Lai, 2017; Yuan, Xu, Yuan,
& Xu, 2018]. 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; 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ự [Aladag & Erten, 2013; CONTE,
FOGGIA, SANSONE, & VENTO, 2004; Notredame et al., 2000; Yan, Yu, &
Han, 2005].
Để phân tích cấu trúc của các protein, một số tác giả [Aladag & Erten,
2013; 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; S. Zhang, Hu, & Yang, 2007] đề
xuất sử dụng mô hình đồ thị để biểu diễn cấu trúc 3 chiều của protein.
22
1.1.2.1. Mô hình hóa mạng các vị trí liên kết protein thành đồ thị
Để nghiên cứu cấu trúc của các protein, bước đầu tiên là cần biểu diễn
cấu trúc của các protein theo mô hình đồ thị. Các nghiên cứu [Fober,
Mernberger, Klebe, & Hüllermeier, 2009; Weskamp, Hüllermeier, Kuhn, &
Klebe, 2007] được thực hiện trên cơ sở dữ liệu Cavbase [Schmitt, Kuhn, &
Klebe, 2002] – một hệ thống cơ sở dữ liệu sử dụng thuật toán LIGSITE
[Hendlich, Rippmann, & Barnickel, 1997] để tự động phát hiện, trích xuất và
lưu trữ các khoang protein (các túi liên kết – binding pockets) từ các cấu trúc
protein được xác định qua thực nghiệm (có sẵn từ ngân hàng dữ liệu protein
[Berman et al., 2002]). Trong cơ sở dữ liệu này, các túi liên kết được biểu diễn
xấp xỉ bằng các đồ thị [Hendlich, Bergner, Günther, & Klebe, 2003; Schmitt et
al., 2002].
Để mô hình hóa một túi liên kết thành 1 đồ thị, sự sắp xếp trong không
gian và các thuộc tính lý hóa của một túi liên kết được gọi là tâm giả
(pseudocenter)- các điểm trong không gian biểu thị cho tâm của một đặc trưng
riêng [Weskamp et al., 2007]. Kiểu và vị trí không gian của các tâm phụ thuộc
vào các amino axit được bao quanh bởi các túi liên kết và biểu hiện các nhóm
chức năng của chúng. Chúng thu được từ cấu trúc của protein sử dụng một tập
các luật định trước [Schmitt et al., 2002]. Các loại tâm giả bao gồm:
pseudocenters, hydrogenbond donor, acceptor, mixed donor/acceptor,
hydrophobic aliphatic, metal ion, pi.
Một túi liên kết được mô hình hóa bởi đồ thị G(V,E), trong đó V là tập
các đỉnh, E là tập các cạnh. Nhãn của các đỉnh thuộc một tập L = {A, B, C, D,
E, F, G}, trong đó A đại diện cho donor, B đại diện cho acceptor, v.v. Hai đỉnh
được xem như có kết nối với nhau và được biểu diễn bởi 1 cạnh trong đồ thị G
23
nếu khoảng cách Ơclit giữa chúng nhỏ hơn 12Å (1Å =10-10 mét). Trọng số w(e)
của nó có thể coi là nhãn của cạnh.
Để mô hình hóa sự biến đổi cấu trúc của các protein trong tự nhiên, trong
mỗi đồ thị, người ta định nghĩa 3 phép toán chỉnh sửa:
i) Chèn hoặc xóa một nút: Một nút và các cạnh tương ứng với nó có
thể được xóa hoặc thêm vào.
ii) Thay đổi nhãn của một đỉnh: Nhãn 𝑙(𝑣) của một nút 𝑣 ∈ 𝑉 có thể được
thay thế bởi một nhãn khác trong tập L.
iii) Thay đổi trọng số của một cạnh: Trọng số 𝑤(𝑒) của một cạnh 𝑒 có thể
được thay đổi tùy theo các hình thể.
Khoảng cách chỉnh sửa của 2 đồ thị G1 và G2 được định nghĩa là dãy các
phép biến đổi nhỏ nhất để biến đổi đồ thị G1 thành đồ thị G2. Cũng như dóng
hàng chuỗi, ta có thể định nghĩa khái niệm dóng hàng của 2 hoặc nhiều đồ thị.
Tương ứng với khái niệm khoảng trống của dóng hàng chuỗi, khái niệm nút giả
được định nghĩa để thay thế cho vị trí của các nút đã bị xóa.
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 . 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ị được Weskamp và các cộng sự [Weskamp et al., 2007] đề
24
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 có tên là Greedy để 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 đượ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
[Weskamp et al., 2007]:
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.
MGA là bài toán NP-khó [Fober et al., 2009; Weskamp et al., 2007], các
thuật toán heuristic như Greedy chỉ thích hợp cho các bài toán cỡ nhỏ, đối với
các bài toán có kích thước dữ liệu lớn, lời giải mà các thuật toán heuristic thu
được thường không sát với lời giải tối ưu, nên thuật toán Greedy 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 MGA cho phân tích
cấu trúc phân tử sinh học và đề xuất một thuật toán di truyền 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 Greedy mà Weskamp đề xuất [Weskamp et al., 2007]. Tuy nhiên
thuật toán GAVEO dựa trên giải thuật di duyền nên có nhược điểm là không
tận dụng được các thông tin heuristic của các thuật toán đã đề xuất trước đó;
bên cạnh đó thuật toán còn sử dụng lại nhiều lời giải của các bước lặp trước, vì
vậy thường lâu hội tụ hơn.
Đố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.
25
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 để giải bài toán dóng hàng
nhiều mạng các vị trí hoạt tính của protein. Phát biểu toán học của bài toán,
hàm đánh giá chất lượng dóng hàng và các dữ liệu thực nghiệm được sử dụng
cho bài toán này được sẽ được trình bày chi tiết ở chương 2.
1.1.3. Bài toán dóng hàng mạng tương tác protein - 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 - protein.
Một mạng tương tác Protein được biểu thị bởi một đồ thị G(V,E) trong
đó V là tập đỉnh mà mỗi nút ứng với một protein, E là tập cạnh, mỗi cạnh nối 2
nút biểu hiện tương tác của hai protein tương ứng. Ngoài tính topology thể hiện
trên mạng, nhiều khi người ta còn quan tâm tới cả đặc tính cấu trúc của mỗi
protein mà chúng không được biểu diễn trên đồ thị.
Dựa trên số lượng mạng tương tác được dóng hàng cùng một lúc bài toán
dóng hàng mạng tương tác protein - protein có thể phân loại thành bài toán
dóng hàng hai mạng và bài toán dóng hàng đa mạng. Trong đó, dóng hàng hai
mạng chỉ ghép cặp 2 đồ thị cùng lúc còn bài toán dóng hàng đa mạng cho phép
dóng hàng đồng thời nhiều hơn hai mạng. Trong 2 bài toán này, bài toán dóng
hàng đồng thời nhiều mạng tương tác protein – protein có độ phức tạp lớn nên
ít được nghiên cứu hơn [Alkan & Erten, 2014; Gligorijević, Malod-Dognin, &
Prulj, 2015; Liao, Lu, Baym, Singh, & Berger, 2009; Vipin Vijayan &
Milenkovic, 2018]. Trong khi đó, 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/cá thể nhờ phát hiện các vùng
tương tự giữa chúng. Vì vậy bài toán này được nghiên cứu rất nhiều trong thời
26
gian gần đây (xem thêm [Guzzi & Milenković, 2018]). Luận án sẽ tập trung
nghiên cứu bài toán này.
Ngoài cách phân loại trên, bài toán dóng hàng mạng còn được chia thành
2 loại dựa trên hai hướng tiếp cận: dóng hàng cục bộ và dóng hàng toàn cục
[Guzzi & Milenković, 2018].
1.1.3.1. Dóng hàng cục bộ
Các nghiên cứu đầu tiên về dóng hàng mạng PPI là dóng hàng cục bộ
[Berg & Lassig, 2004, 2006; Ciriello, Mina, Guzzi, Cannataro, & Guerra, 2012;
Flannick, Novak, Balaji, Harley, & Batzglou, 2006; Kelley et al., 2004;
Koyutürk et al., 2006; Liang, Xu, Teng, & Niu, 2006; Mina & Guzzi, 2012;
Pache & P Aloy, 2012; Roded Sharan et al., 2005]. Dóng hàng cục bộ có mục
tiêu là xác định các mạng/đồ thị con gần nhau về topology và về trình tự nhờ
một ánh xạ từ mạng nguồn vào mạng đích như minh họa trong hình 1.2 (a).
Hình 1.2. Dóng hàng cục bộ và dóng hàng toàn cục
Các thuật toán dóng hàng cục bộ thường cho kết quả nhiều-nhiều, trong
đó một nút từ một mạng có thể được ánh xạ tới một vài nút từ các mạng khác
(Hình 1.2a).
Có nhiều cách tiếp cận khác nhau đã được sử dụng để đánh giá chất lượng
của một dóng hàng cục bộ. Các độ đo để đánh giá chất lượng dóng hàng cục bộ
27
phổ biến là tương đồng bản thể gen [Ashburner et al., 2000], đặc trưng và độ
nhạy [Ashburner et al., 2000; Flannick et al., 2006].
Dóng hàng cục bộ có nhược điểm là khó tìm ra các đồ thị con với kích
thước lớn có cấu trúc và chức năng tương tự, kết quả của dóng hàng cục bộ là
nhiều nhiều nên thường chứa nhiều các mạng con chồng lấn nhau nên thường
dẫn tới sự nhập nhằng dẫn đến khó ứng dụng. Vì vậy, hầu hết các nghiên cứu
hiện nay tập trung vào dóng hàng mạng toàn cục.
1.1.3.2. Dóng hàng toàn cục
Xét hai mạng PPI được mô hình hóa bởi 2 đồ thị G1(V1,E1) và G2(V2,E2)
một dóng hàng toàn cục mạng PPI là một đơn ánh từ mạng có số đỉnh nhỏ hơn
vào mạng có số đỉnh lớn (xem hình 1.2b), nhờ đó mà xác định các vùng mạng
được bảo tồn. Việc xác định đơn ánh như vậy tránh được các nhập nhằng
thường gặp ở phương pháp dóng hàng cục bộ.
Để xác định dóng hàng đủ tốt, người ta dựa vào một tiêu chuẩn cụ thể và
đưa về giải bài toán tối ưu tổ hợp. Các tiêu chuẩn dóng hàng toàn cục chủ yếu
dựa trên tính tương tự tôpô kết hợp với thông tin trình tự. Có nhiều tiêu chuẩn
dóng hàng đã được đề xuất, trong đó có 4 tiêu chuẩn thông dụng và hợp lý nhất
sẽ được trình bày trong chương 4. Bài toán tối ưu dóng hàng toàn cục mạng
PPI được chứng minh thuộc loại NP-khó nên đang là bài toán quan trọng trong
sinh học phân tử và đã có nhiều thuật toán heuristic và metaheurristics đề xuất
để giải chúng.
Hầu hết các thuật toán dóng hàng toàn cục nổi bật trước đây thực hiện theo
hai bước và chia thành hai nhóm.
Nhóm thứ nhất sử dụng hai bước như sau:
28
Bước 1, dùng một hàm chi phí tính toán độ tương tự giữa các cặp nút trong
các mạng khác nhau;
Bước 2, sử dụng một chiến lược dóng hàng để xác định nhanh một dóng
hàng bắt đầu từ cặp nút có điểm tương tự cao nhất [Aladag & Erten, 2013;
Gligorijević et al., 2015; Hu, Kehr, & Reinert, 2014; O. Kuchaiev, Milenković,
Memišević, Hayes, & Pržulj, 2010; Oleksii Kuchaiev & Pržulj, 2011; Liao et
al., 2009; Mamano & Hayes, 2017; Memišević & Pržulj, 2012; Milenković,
Ng, Hayes, & Pržulj, 2010; Patro & Kingsford, 2012; Sahraeian & Yoon, 2013;
Singh, Xu, & Berger, 2007, 2008].
Nhóm thứ hai cũng thực hiện hai bước, nhưng trong bước 2, sau khi xác
định ma trận đo độ tương đồng giữa các nút được tính toán trước từ trên bước
1 để tạo ra một dóng hàng như nhóm thứ nhất thì thực hiện lặp việc sử dụng
thông tin từ dóng hàng đã có để tính lại ma trận đo độ tương đồng để dóng hàng
tiếp [El-Kebir, Heringa, & Klau, 2011; Ibragimov, Malek, Baumbach, & Guo,
2014; Meng, Crawford, Striegel, & Milenkovic, 2016; Zaslavskiy, Bach, &
Vert, 2009].
Phần dưới đây giới thiệu một số thuật toán dóng hàng toàn cục tiêu biểu
được sử dụng để so sánh với các thuật toán luận án đề xuất.
Thuật toán dóng hàng toàn cục đáng chú ý đầu tiên là IsoRank [Singh et
al., 2008] được Sing và các cộng sự đề xuất năm 2008, phát triển dựa trên dóng
hàng cục bộ. IsoRank có ý tưởng xuất phát từ thuật toán PageRank của Google
[Brin & Page, 1998] để định nghĩa hàm đánh giá sự tương đồng. Ý tưởng chính
của IsoRank là hai nút được dóng hàng với nhau, nếu các nút kề với chúng
tương ứng được dóng hàng.
Họ các thuật toán GRAAL [O. Kuchaiev et al., 2010; Oleksii Kuchaiev &
Pržulj, 2011; Milenković et al., 2010] bao gồm GRAAL, H-GRAAL, MI-
29
GRALL và sau đó là C-GRAAL [Memišević & Pržulj, 2012] được phát triển
song song với họ các thuật toán IsoRank dựa trên kết hợp kỹ thuật tham lam
với thông tin heuristic 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 đó.
Gần đây hơn là thuật toán GHOST, chiến lược dóng hàng của GHOST
cũng tương tự như của MI-GRAAL, ngoại trừ việc thuật toán MI-GRAAL giải
bài toán quy hoạch tuyến tính để tính toán độ tương tự giữa các nút trên các
mạng khác nhau, trong khi GHOST giải bài toán quy hoạch bậc 2 theo phương
pháp heuristic để tính toán độ tương tự giữa các nút trong cùng một mạng.
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.
Saraph và các cộng sự [Saraph & Milenković, 2014] đề 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,
MI-GRAAL và GHOST. MAGNA và phiên bản cải tiến MAGNA ++ [V
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) [Hashemifar, Ma, Naveed,
Canzar, & Xu, 2016] giới thiệu một 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. Dựa trên một thuật
30
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 hai 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.
Trong chương 3, luận án đề xuất các thuật toán mới để giải bài toán dóng
hàng toàn cục hai mạng tương tác protein - protein. Phát biểu toán học của bài
toán dóng hàng toàn cục hai mạng tương tác protein - protein, các hàm đánh
giá chất lượng dóng hàng và dữ liệu thực nghiệm cho bài toán được trình bày
ở mục 3.1 và 3.5.1 của chương 3.
1.2. Tối ưu mềm
1.2.1. 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
Trong các bài toán thực tiễn, ta thường gặp các bài toán TƯTH, trong đó
cần tìm cực trị của một hàm với biến nhận giá trị trong một tập hữu hạn.
Một cách tổng quát, mỗi bài toán TƯTH có thể phát biểu như sau: (xem
[Dorigo & Stützle, 2004; Schrijver, 2006]). 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.
Đối với mỗi bài toán, đều có thể chỉ ra một tập hữu hạn gồm n thành
phần C = {c1, … , cn} sao cho mỗi phương án s trong S đều biễu diễn được nhờ
31
liên kết các thành phần trong nó. Cụ thể hơn, các tập S, C và Ω có các đặc tính
sau:
1) Ký hiệu 𝑋 là tập các vectơ trên 𝐶 có độ dài không quá
ℎ: 𝑋 = {< 𝑢0, . . . , 𝑢𝑘 > 𝑢𝑖𝐶𝑖𝑘ℎ}. Khi đó, mỗi phương án 𝑠 trong 𝑆 được
xác định nhờ ít nhất một vectơ trong 𝑋 như ở điểm 2) dưới đây.
2) Tồn tại tập con 𝑋∗của 𝑋 và ánh xạ từ 𝑋∗ lên 𝑆 sao cho −1(𝑠) không rỗng với mọi 𝑠𝑆,trong đó tập 𝑋∗có thể xây dựng được từ tập con 𝐶0 nào đó của 𝐶 nhờ thủ tục mở rộng tuần tự ở điểm 3) dưới đây.
3) Từ 𝐶0ta mở rộng tuần tự thành 𝑋∗như sau:
i) Ta xem 𝑥0 = < 𝑢0 >là mở rộng được với mọi 𝑢0 𝐶0.
ii) Giả sử 𝑥𝑘 =< 𝑢0, . . . , 𝑢𝑘 > là mở rộng được và chưa thuộc 𝑋∗. Từ tập ràng buộc Ω, xác định tập con 𝐽(𝑥𝑘) của 𝐶, sao cho với mọi 𝑢𝑘+1 𝐽(𝑥𝑘)
thì 𝑥𝑘+1 =< 𝑢0, . . . , 𝑢𝑘, 𝑢𝑘+1 >là mở rộng được.
iii) Áp dụng thủ tục mở rộng từ các phần tử 𝑢0 𝐶0 cho phép ta xây
dựng được mọi phần tử của 𝑋∗.
Như vậy, mỗi bài toán TƯTH được xem là một bài toán cực trị hàm có ℎ
biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn 𝐶 kể cả giá trị rỗng. Nói
một cách khác, nó là bài toán tìm kiếm trong không gian vectơ độ dài không
quá ℎ trên đồ thị đầy đủ có các đỉnh có nhãn trong tập 𝐶.
Để hiểu rõ hơn về bài toán tối ưu tổ hợp và tiếp cận tính toán mềm, phần
này giới thiệu bài toán TƯTH điển hình thuộc loại NP-khó: bài toán người chào
hàng.
32
Bài toán TSP [Dorigo & Stützle, 2004] là bài toán TƯTH có nhiều ứng
dụng và được xem là bài toán chuẩn để đánh giá hiệu quả các lược đồ giải bài
toán TƯTH mới. Bài toán này được phát biểu như sau:
𝑛 độ dài , 𝑖=1
Cho một tập gồm 𝑛 thành phố (hoặc điểm tiêu thụ) 𝐶 = {𝑐𝑖}
đường đi trực tiếp từ thành phố ci đến thành phố cj là di,j . Một người chào hàng
muốn tìm một hành trình ngắn nhất từ nơi ở, đi qua mỗi thành phố đúng một
lần để giới thiệu sản phẩm, sau đó trở về nơi xuất phát.
Như vậy, ta cần tìm chu trình Hamilton của một đồ thị đầy đủ có trọng số
𝐺 = (𝑉, 𝐸), trong đó 𝑉 là tập đỉnh với nhãn là các thành phố trong 𝐶, 𝐸 là các
cạnh nối các thành phố tương ứng, độ dài các cạnh chính là độ dài đường đi
giữa các thành phố đã biết.
Trong bài toán này, tập 𝑆 là các chu trình Hamilton trên 𝐺, 𝑓 là độ dài của
chu trình, Ω là ràng buộc đòi hỏi chu trình là chu trình qua tất cả các đỉnh, mỗi
đỉnh đúng một lần (Hamilton), 𝐶 là tập thành phố được xét (trùng với 𝑉),
𝐶0 trùng với 𝐶, tập 𝑋 là vectơ độ dài 𝑛: 𝑥 = (𝑥1, … , 𝑥𝑛) với 𝑥𝑖 ∈ 𝐶 ∀ 𝑖 ≤ 𝑛, còn 𝑋∗là các vectơ trong đó 𝑥𝑖 khác 𝑥𝑗 đối với mọi cặp (𝑖, 𝑗).
Các tiếp cận giải các bài toán TƯTH khó
Với các bài toán TƯTH NP-khó có cỡ nhỏ, người ta có thể tìm lời giải
tối ưu nhờ tìm kiếm vét cạn. Tuy nhiên, với các bài toán cỡ lớn thì đến nay chưa
thể có thuật toán tìm lời giải đúng với thời gian đa thức nên chỉ có thể tìm lời
giải gần đúng hay đủ tốt.
Theo cách tiếp cận truyền thống hay là tiếp cận cứng, các thuật toán gần
đúng phải được chứng minh tính hội tụ hoặc ước lượng được tỷ lệ tối ưu. Với
việc đòi hỏi khắt khe về toán học như vậy làm hạn chế số lượng các thuật toán
công bố, không đáp ứng được nhu cầu ngày càng phong phú và đa dạng trong
nghiên cứu và ứng dụng. Để khắc phục tình trạng này, người ta dùng tiếp cận
33
đủ tốt để xây dựng các thuật toán tối ưu mềm.
1.2.1.2. Tính toán mềm
Tính toán mềm [Volna, 2013] 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 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ờ/ tập thô,
các phương pháp học máy như mạng nơ ron nhân tạo, máy tựa véctơ (SVM),
các giải thuật tiến hóa như các giải thuật di truyền, tối ưu bầy đàn, tối ưu đàn
kiến, tối ưu bầy ong, giải thuật memetic, hệ miễn dịch nhân tạo, v.v.
Đối với các bài toán TƯTH khó, các phương pháp tính toán mềm được
đánh giá chất lượng dựa trên thực nghiệm mà không nhất thiết phải chứng minh
tính hội tụ hoặc ước lượng tỷ lệ tối ưu. Các thuật toán thường được xây dựng
dựa trên một ý tưởng “có lý” và hiệu quả của chúng được đánh giá dựa vào kết
quả thử nghiệm trên tập dữ liệu đủ tin cậy.
Các phương pháp này phát triển theo hai hướng heuristic và metaheuristic
[X.-S. Yang, 2014; X.-S. Yang & Wiley InterScience (Online service), 2010].
Các thuật toán heuristic đề xuất riêng biệt cho từng bài toán cụ thể, cho phép
tìm nhanh một lời giải đủ tốt hoặc xấp xỉ tối ưu địa phương
Theo cách hiểu chung nhất, mỗi thuật toán metaheuristic tổng quát là một
lược đồ tính toán đề xuất cho lớp bài toán rộng, khi dùng cho các bài toán cụ
thể cần thêm các vận dụng chi tiết cho phù hợp. Nhờ các lược đồ này, người
dùng có thể xây dựng được thuật toán cho bài toán trong thực tế mà không đòi
hỏi có kiến thức tốt về toán học tính toán, vì vậy, hiện nay chúng đang được
dùng phổ biến trong ứng dụng. Các thuật toán này thường có thời gian chạy lâu
hơn các thuật toán truyền thống và tìm kiếm địa phương nhưng lời giải hướng
tới tối ưu toàn cục. Khi đề xuất thuật toán metaheuristic mới, người ta phải thử
34
nghiệm trên bài toán chuẩn để kiểm định chất lượng so với các thuật toán khác,
sau đó, người dùng vận dụng cho các bài toán khác. Các thuật toán tổng quát
này thường dựa trên ý tưởng mô phỏng tự nhiên với ngầm định rằng qua quá
trình chọn lọc tự nhiên, các đặc điểm và đặc tính sinh học hiện có thường mang
tính tối ưu.
Dưới đây sẽ giới thiệu các phương pháp và khái niệm cần dùng cho các
thuật toán được đề xuất trong luận án bao gồm phương pháp ACO, tính toán
tiến hóa và các thuật toán memetic, tìm kiếm Tabu. Trong đó tập trung giới
thiệu và phân tích sâu về thuật toán ACO, vì ACO là thuật toán cơ sở để đề
xuất các thuật toán mới được trình bày ở chương 2 và chương 3.
1.2.2. Phương pháp tối ưu đàn kiến
Phương pháp tối ưu đàn kiến là thuật toán mô phỏng cách tìm đường đi
tới tổ của kiến tự nhiên để giải các bài toán tối ưu tổ hợp khó. Phương pháp này
được Dorigo giới thiệu vào năm 1991 [M. Dorigo, 1991] dưới dạng hệ kiến
ngày nay đã được phát triển dưới nhiều biến thể và được ứng dụng rộng rãi
Về bản chất, ACO là phương pháp tìm kiếm ngẫu nhiên dựa trên quần thể
nhờ kết hợp thông tin heuristic và thông tin học tăng cường thể hiện qua vết
mùi để tìm lời giải gần đúng tối ưu toàn cục. Để hiểu rõ các thuật toán, trước
hết cần nắm được ý tưởng mô phỏng của thuật toán
1.2.2.1. Kiến tự nhiên và kiến nhân tạo
Kiến tự nhiên.
Trên đường đi đến nguồn thức ăn và trở về tổ, mỗi con kiến thực để lại
một vết hoá chất gọi là vết mùi và theo vết mùi của các con kiến khác để tìm
đường đi. Đường có nồng độ vết mùi càng cao thì càng có nhiều khả năng được
các con kiến chọn. Nhờ cách giao tiếp gián tiếp này đàn kiến tìm được đường
đi ngắn nhất từ tổ tới nguồn thức ăn (xem minh họa trong hình 1.3).
35
Hình 1.3. Cách các con kiến thực chọn đường đi ngắn nhất để tha mồi về tổ
Việc tìm đường đi của các con kiến tự nhiên dựa trên nồng độ vết mùi làm
ta liên tưởng tới cách học tăng cường cho bài toán chọn tác động tối ưu, gợi mở
một mô hình mô phỏng cho các con kiến thực để tìm đường đi ngắn nhất giữa
hai nút (tương ứng là tổ và nguồn thức ăn) trên đồ thị. Trên cơ sở đó, mở rộng
thành phương pháp ACO để giải các bài toán tối ưu tổ hợp khó
Kiến nhân tạo.
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ử 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.
36
1.2.2.2. Lược đồ chung của phương pháp ACO
Để giải bài toán TƯTH tổng quát được cho bởi bộ ba (S,f, Ω), ta cần xây
dựng một đồ thị cấu trúc G(V,E) trong đó V là tập đỉnh sao cho có các tập con
C0 và C của V để có thể xây dựng các lời giải chấp nhận được trong tập trạng
thái S nhờ xuất phát từ thành phần ban đầu trong C0 và phát triển tuần tự bởi
các thành phần trong C theo định hướng trong E như đã nêu trong mục 1.2.1.1.
Để đơn giản, ta xét thuật toán ACO có vết mùi 𝜏𝑖𝑗và thông tin heuristic 𝜂𝑖𝑗 định
hướng tìm kiếm để ở các cạnh (𝑖, 𝑗) trong E. Bây giờ ta có thể thực hiện thuật
toán ACO trên đồ thị cấu trúc mở rộng G(V, E, 𝜏, 𝜂) trong đó 𝜏, 𝜂 tương ứng là
ma trận mùi và ma trận thông tin heuristic.
Lược đồ thông dụng nhất hiện nay của phương pháp ACO không áp dụng
tìm kiếm địa phương như sau:
Thuật toán 1.1. Thuật toán ACO
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;
Begin end for; Cập nhật mùi; end while; End
Khi đã có thông tin heuristic (thông tin này như nhau nếu không tìm
được) 𝜂𝑖𝑗 cho mỗi cạnh (𝑖, 𝑗) ∈ 𝐸 định hướng ưu tiên phát triển tuần tự từ đỉnh
𝑖 tới 𝑗 trong V, ta khởi tạo vết mùi ban đầu 𝜏𝑖𝑗 bởi cùng giá trị 𝜏0, khởi tạo m
kiến để thực hiện việc lặp tìm lời giải tuần tự nhờ thủ tục bước ngẫu nhiên
(được mô tả ở mục 1.2.2.3) và trao đổi để cập nhật mùi (học tăng cường, được
37
mô tả ở mục 1.2.2.4). Lược đồ của một thuật toán ACO không áp dụng tìm
kiếm địa phương được đặc tả trong thuật toán 1.1.
Lời giải tốt nhất tìm được sau số vòng lặp định trước sẽ được dùng làm
xấp xỉ tối ưu toàn cục.
1.2.2.3. Thủ tục bước ngẫu nhiên xây dựng lời giải
Ban đầu mỗi kiến k sẽ chọn ngẫu nhiên một đỉnh ở tập C0, nhờ tập ràng
buộc Ω, kiến sẽ xác định được tập phát triển trong C để phát triển tuần tự một
cách tổng quát như sau.
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
𝑙∈𝐽𝑘(𝑖)
𝑘 = { 𝑝𝑖𝑗
[𝜏𝑖𝑙(𝑡)]𝛼.[𝜂𝑖𝑙(𝑡)]𝛽 0 𝑛ế𝑢 𝑗 ∉ 𝐽𝑘(𝑖)
𝑛ế𝑢 𝑗𝐽𝑘(𝑖) , (1.1)
trong đó 𝛼, 𝛽 là các hằng số dương chọn trước. Thủ tục này tiếp tục cho đến
khi xâu 〈𝑢0, … , 𝑢𝑡〉 tương ứng với một lời giải s trong S. Bằng cách này mỗi kiến xây dựng được lời giải trong mỗi vòng lặp và cùng thực hiện đánh giá lời
giải để câp nhật mùi theo một quy tắc được chọn.
1.2.2.4. Các quy tắc cập nhật mùi
Việc cập nhật mùi, phản ánh cơ chế học tăng cường và ảnh hưởng quyết
định chất lượng thuật toán nên thường dùng để làm tên gọi cho lớp thuật toán
dùng nó. Để đảm bảo vết mùi hội tụ, người ta sử dụng hằng số bay hơi vết mùi
0<≤1 hay hệ số chiết khấu trong học tăng cường, khi một cạnh được cập nhật
mùi thì vết mùi biến đổi theo công thức:
. (1.2)
38
Điểm then chốt là cạnh nào được cập nhật và lượng thêm vào thế nào là
tùy theo quy tắc được chọn. Có nhiều quy tắc cập nhật mùi đã được đề xuất,
trong đó điển hình là các quy tắc hệ kiến, hệ đàn kiến, hệ kiến Max-Min và hệ
kiến Max-min trơn.
Ký hiệu 𝑤𝑘(𝑡) là lời giải kiến k tìm được ở bước lặp t, 𝑤(𝑡) và 𝑤∗(𝑡)
tương ứng là lời giải tốt nhất tìm được ở bước lặp t và lời giải tốt nhất tìm được
tới bước đó.
Quy tắc cập nhật AS
Hệ kiến AS áp dụng quy tắc cập nhật mùi địa phương, và là quy tắc đầu
tiên được áp dụng trong số các thuật toán ACO. Theo quy tắc này, ở bước lặp
t, mỗi kiến k áp dụng cập nhật mùi cho tất cả các cạnh (𝑢𝑖, 𝑢𝑖+1) thuộc lời giải 𝑤𝑘(𝑡) theo công thức (1.3)
1 𝐿𝑘
𝜌. , 𝑛ế𝑢 (𝑖, 𝑗) ∈ 𝑤𝑘(𝑡) , (1.3) Δ𝜏𝑖𝑗 = { 0 𝑛ế𝑢 (𝑖, 𝑗) ∉ 𝑤𝑘(𝑡)
trong đó 𝐿𝑘 là giá trị hàm mục tiêu 𝑓(𝑤𝑘(𝑡)) (không giảm tổng quát,được
giả thiết là dương).
Nhược điểm của quy tắc là vết mùi ở các cạnh không được cập nhật sẽ
nhanh chóng dần về không nên hạn chế không gian tìm kiếm và thuật toán kém
hiệu quả.
Quy tắc ACS
Quy tắc này do Dorigo đề xuất năm 1997 [Dorigo & Gambardella, 1997].
Trong thuật toán ACS, việc cập nhật mùi bao gồm cả hai hình thức địa phương
và toàn cục. Cập nhật mùi địa phương áp dụng cho mọi cạnh có kiến 𝑘 sử dụng
khi nó tìm lời giải. Có hai cách cập nhật mùi toàn cục.
39
a) Cập nhật mùi toàn cục áp dụng cho các cạnh thuộc lời giải tốt nhất của bước
lặp (𝑤(𝑡)hay toàn cục 𝑤∗(𝑡) và gọi tương ứng là i-best hay G-best. Theo cách
i-besst, Δ𝜏𝑖𝑗 được xác định theo công thức:
(1.4) Δ𝜏𝑖𝑗 = 𝜌. 𝑓(𝑤(𝑡)).
Nếu trong công thức (1.4) thay 𝑤(𝑡) bởi 𝑤∗(𝑡) thì ta nói là G-best
b) Cập nhật mùi toàn cục áp dụng cho tất cả các cạnh và cũng các hai cách i-
best hay G-best, với G-best thì Δ𝜏𝑖𝑗xác định theo công thức:
1 𝑓( 𝑤∗(𝑡)) 0 𝑛ế𝑢 (𝑖, 𝑗) ∉ 𝑤∗(𝑡)
𝜌. , 𝑛ế𝑢 (𝑖, 𝑗) ∈ 𝑤∗(𝑡) . . (1.5) Δ𝜏𝑖𝑗 = {
Khi thay 𝑤∗(𝑡) bởi 𝑤(𝑡) thì ta có i-best.
Các quy tắc này tăng chất lượng thuật toán so với AS nhưng không tránh
được nhược điểm của nó
Quy tắc MMAS
Để khắc phục nhược điểm nêu trên của AS và ACS, Stutzle & Hoos đề
xuất MMAS năm 2000 [Stützle & Hoos, 2000] gồm 2 bước:
Bước thứ nhất, cập mùi toàn cục cho tất cả các cạnh theo phương
thức i-best hoặc G-best.
Bước thứ hai, so sánh các lượng 𝜏𝑖𝑗với hai đại
𝜏𝑚𝑎𝑥và 𝜏𝑚𝑖𝑛 (𝜏𝑚𝑎𝑥 > 𝜏min > 0) để giới hạn vết mùi trong đoạn
[𝜏𝑚𝑖𝑛, 𝜏𝑚𝑎𝑥], cụ thể như sau:
. (1.6) 𝜏𝑖𝑗 = {
𝜏𝑚𝑎𝑥 𝑛ế𝑢 𝜏𝑖𝑗 > 𝜏𝑚𝑎𝑥 𝜏𝑖𝑗 𝑛ế𝑢 𝜏𝑖𝑗 ∈ [𝜏𝑚𝑖𝑛, 𝜏𝑚𝑎𝑥] 𝜏𝑚𝑖𝑛 𝑛ế𝑢 𝜏𝑖𝑗 < 𝜏𝑚𝑖𝑛
40
Nói chung, MMAS dùng i-best tốt hơn G-best nhưng cũng có thể dùng
luân phiên cho các bước lặp. Khi bắt đầu thuật toán, vết mùi thường được thiết
đặt bằng ước lượng cận trên của vết mùi 𝜏𝑚𝑎𝑥. Cách khởi tạo như vậy kết hợp
với tham số bay hơi nhỏ làm chậm sự khác biệt vết mùi của các cạnh, do đó
giai đoạn đầu của MMAS mang tính khám phá. Nhờ giới hạn vết mùi trong
đoạn [𝜏𝑚𝑖𝑛, 𝜏𝑚𝑎𝑥], MMAS hạn chế được tình trạng vết mùi dần về không, khắc
phục được nhược điểm của AS và ACS nên là thuật toán được nghiên cứu nhiều
nhất trong các thuật toán ACO và nó có rất nhiều phát triển. Một phát triển hiệu
quả là SMMAS
Quy tắc SMMAS
Quy tắc SMMAS lần đầu tiên được Đỗ Đức Đông và cộng sự dùng cho
bài toán lập lịch sản xuất [Do Duc, Dinh, & Hoang Xuan, 2008] và được trình
bày chặt chẽ cho bài toán TSP trong [Hoang Xuan Huan, Linh-Trung, Huynh,
& others, 2013].
SMMAS được đề xuất dựa trên nhận xét hai nhược điểm của MMAS:
Thứ nhất, nếu chọn 𝜏𝑚𝑖𝑛, 𝜏𝑚𝑎𝑥 lệch nhau ít thì làm triệt tiêu hiệu quả
học tăng cường, còn nếu chọn lệch nhau nhiều thì vết mùi ở các cạnh
ít được cập nhật sẽ nhanh chóng về 𝜏𝑚𝑖𝑛 làm hạn chế không gian tìm
kiếm mặc dù có nhẹ hơn AS và ACS.
Thứ hai là đại lượng ∆𝜏𝑖𝑗 phụ thuộc giá trị hàm mục tiêu làm cho thuật
toán phải tính toán phức tạp, tuy nhiên trong học tăng cường thì không
cần thiết.
Một trong các cải tiến là khi khởi tạo lại vết mùi, việc cập nhật mùi
thường xuyên bằng lời giải tốt nhất tìm được mới nhất thay vì cố định.
41
Với nhận xét trên, SMMAS không giảm vết mùi ở các cạnh không thuộc
lời giải tốt quá nhanh như quy tắc MMAS mà dùng quy tắc Max-Min trơn bằng
cách cập nhật 𝜏𝑖𝑗 toàn cục cho mọi cạnh với Δ𝜏𝑖𝑗 xác định bởi:
(1.7) Δ𝜏𝑖𝑗 = { 𝜌. 𝜏𝑚𝑖𝑛 𝑛ế𝑢 (𝑖, 𝑗) ∉ 𝑤(𝑡) . 𝜌. 𝜏𝑚𝑎𝑥 𝑛ế𝑢 (𝑖, 𝑗) ∈ 𝑤(𝑡)
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
Lược đồ ACO ở trên thực hiện tìm kiếm ngẫu nhiên để tìm lời giải gần
đúng nên không gian tìm kiếm rộ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. Ví dụ
Như vậy, để xây dựng thuật toán ACO cho bài toán cụ thể theo lược đồ
nêu trên, có 4 yếu tố quyết định:
1) Đồ thị cấu trúc. Trước hết ta cần xác định được đồ thị cấu trúc G(V, E)
và các tập C0, C phù hợp với bài toán sao cho thủ tục bước ngẫu nhiên
dễ áp dụng với các ràng buộc Ω đã cho và không gian tìm kiếm càng nhỏ
càng tốt.
2) Thông tin heuristic. Sau khi cho đồ thị cấu trúc, cần chọn thông tin
heuristic để tăng hiệu quả tìm kiếm khi học tăng cường. Tuy nhiên, khi
42
không có thông tin này thì có thể xem chúng như nhau và cùng bằng đơn
vị.
3) Quy tắc cập nhật mùi. Trong luận án này chúng tôi chọn quy tắc cập nhật
mùi SMMAS vì nó đơn giản, dễ dùng và hiệu quả hơn các thuật toán
khác.
4) Các kỹ thuật tìm kiếm địa phương và các áp dụng. Tùy theo bài toán mà
có thể áp dụng đơn giải một kỹ thuật tìm kiếm địa phương hoặc theo lược
đồ memetic được nói ở mục 1.2.3.2.
Các tham số cho thuật toán ACO được chọn dựa trên kết quả thực nghiệm.
Để hiểu rõ hơn, ta xét ví dụ giải bài toán cho bài toán TSP.
Với bài toán TSP cho bởi G(V, E) và độ dài 𝑑𝑖𝑗 của các cạnh (i,j) đã biết
như trong mục 1.2.1.1, ta có thể dùng luôn đồ thị này làm đồ thị cấu trúc với
C0=C=V. Với mỗi kiến k ở đỉnh i khi tìm kiếm, tậ𝑝 𝐽𝑘(𝑖) là các đỉnh mà kiến
chưa đi qua.
1 𝑑𝑖𝑗
. Thông tin heuristic là nghịch đảo khoảng cách 𝜂𝑖𝑗 =
Việc tìm kiếm địa phương cho một chu trình Hamilton được áp dụng cho
các chu trình có p đỉnh liền nhau trong chu trình này được hoán vị (p-láng
giềng), trong đó p chọn trước. Chiến lược tìm kiếm có thể là tốt hơn (better)
hoặc tốt nhất (the best). Trong chiến lược tốt hơn, việc tìm kiếm cho mỗi lời
giải ở mỗi lần lặp sẽ dừng khi tìm được một lời giải tốt hơn nó, còn chiến lược
tốt nhất sẽ tìm kiếm lời giải tốt nhất trong p-láng giềng. Một cách áp dụng
memetics là chỉ áp dụng tìm kiếm địa phương cho một số lời giải tốt trong một
số lần lặp sau thay vì ở những vòng lặp đầu, khi lời giải chưa đủ tốt có cải tiến
thì cũng chưa tốt bao nhiêu mà tốn thời gian.
43
1.2.2.7. 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ý do 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 [Holland, 1975]. 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 trên các lược đồ metaheuristic, chẳng hạn
như các thuật toán tối ưu bầy đàn, đom đóm, dơi, v.v.
Chất lượng các thuật toán metaheuristic được quyết định nhờ hai đặc tính
định hướng quá trình tiến hóa: tính tăng cường và khám phá/đa dạng. Tính tăng
cường thực hiện nhờ ưu tiên tìm kiếm từ thông tin của các cá thể có hàm đánh
giá tốt trong quần thể hiện thời cho tạo sinh quần thể kế tiếp. Tính khám phá/đa
dạng nhằm tạo sinh ra các lời giải tiềm năng mới nhờ mở rộng miền tìm kiếm.
44
1.2.3.2. Các thuật toán memetic
Memetic [Neri, 2011] là thuật toán tìm kiếm dựa trên quần thể, ban đầu
áp dụng cho giải thuật di truyền và nay ứng dụng hiệu quả cho các thuật toán
khác.
Người ta nhận thấy các thuật toán tìm kiếm địa phương có thể tìm kiếm
nhanh một lời giải đủ tốt (có tính gần tối ưu địa phương) hơn các thuật toán dựa
trên quần thể nên khi áp dụng kỹ thật này cho các cá thể nổi trội của quần thể
trong mỗi bước lặp thì chất lượng lời giải được cải thiện đáng kể.
Trong các thuật toán memetic, chẳng hạn GA hoặc ACO, cuối mỗi vòng
lặp t, người ta tìm ra tập lời giải Ω(t) và tập thuật toán tìm kiếm địa phương
𝒜(𝑡) để áp dụng các thuật toán tìm kiếm tăng cường một cách linh hoạt phù
hợp với đặc điểm từng bài toán. Kết quả thực nghiệm cho thấy việc áp dụng
tìm kiếm địa phương đa dạng và linh hoạt ở mỗi bước lặp tùy theo các ràng
buộc và đặc điểm hàm mục tiêu cải thiện đáng kể chất lượng thuật toán so với
các thuật toán sử dụng đơn điệu một thuật toán tìm kiếm cho mọi bước lặp. Với
ưu điểm đó, thời gian gần đây, có rất nhiều thuật toán mới được đề xuất để giải
quyết các bài toán NP khó nói chung và các bài toán trong lĩnh vực tin sinh học
nói riêng [Correa, Borguesan, Farfan, Inostroza-Ponta, & Dorn, 2018;
Garbelini, Kashiwabara, & Sanches, 2018; Gong, Peng, Ma, & Huang, 2016].
1.2.4. Thuật toán tìm kiếm Tabu
Tabu Search (Tabu xuất phát từ từ Taboo trong tiếng Anh có nghĩa là
cấm kỵ) là thuật toán metaheuristic được đề xuất bởi Fred W.Glover năm 1986
[Glover, 1986] và được áp dụng rộng rãi để giải quyết các bài toán tối ưu tổ
hợp.
Thuật toán tìm kiếm Tabu gồm nhiều vòng lặp. Tại mỗi bước lặp, thuật
toán sẽ duyệt trong một miền lân cận của lời giải hiện tại để chọn ra lời giải có
45
chất lượng tốt nhất. Thao tác chuyển từ lời giải hiện tại thành một lân cận của
nó được gọi là bước chuyển. Thuật toán tìm kiếm Tabu duy trì bộ nhớ ngắn
hạn được gọi là một danh sách Tabu. Danh sách này sẽ lưu các bước chuyển
vừa được thực hiện trong một số bước lặp ngay trước đó. Các bước chuyển
Tabu này sẽ bị cấm sử dụng lại chừng nào nó còn nằm trong danh sách Tabu.
Mỗi bước chuyển Tabu sẽ nằm trong danh sách Tabu trong khoảng t
vòng lặp, sau đó nó sẽ được loại khỏi danh sách Tabu và có thể được sử dụng
lại. Số t này được gọi là kích thước của danh sách Tabu và có thể được gán cố
định cho tất cả các bước chuyển hoặc cũng có thể là được chọn ngẫu nhiên cho
từng bước chuyển.
Lược đồ tổng quát của thuật toán tìm kiếm Tabu được mô tả trong thuật
toán 1.2.
Thuật toán 1.2. Thuật toán tìm kiếm Tabu
Begin
TabuList =; Sbest = Lời giải khởi tạo; while (điều kiện dừng chưa thỏa mãn) begin
bestCandidate = s; if ( (s TabuList)) and (cost(s) >cost(bestCandidate)) )
NS = Tập lân cận của Sbest; bestCandidate=phần tử đầu tiên của NS; for each (NS as s) if (cost(bestCandidate) > cost(sBest)) sBest ← bestCandidate;
Cập nhật lại danh sách TabuList;
end; return sBest;
end;
46
Ngoài bộ nhớ ngắn hạn, thuật toán tìm kiếm Tabu còn có 2 loại cấu trúc
bộ nhớ khác là bộ nhớ trung hạn và bộ nhớ dài hạn [Brownlee, 2011]. Trong
đó:
Bộ nhớ trung hạn nhằm ưu tiên tìm kiếm tăng cường trong những khu
vực hứa hẹn trong không gian tìm kiếm được gọi là tiêu chuẩn mong
đợi.
Bộ nhớ dài hạn nhằm ưu tiên tính khám phá trong không gian tìm kiếm
và được gọi là sự đa dạng hóa lời giải. Nó là chiến lược tạo ra các lời
giải mới với các thành phần ít được sử dụng và thường có các thành
phần khác xa so với các lời giải thường được sử dụng nhất.
1.3. Động cơ nghiên cứu
Trong mục 1.1, luận án đã giới thiệu các kiến thức chung về Tin sinh học
trong đó giới thiệu hai bài toán tối ưu tổ hợp quan trọng trong lĩnh vực Tin sinh
học: Thứ nhất bài toán dóng hàng đồng thời nhiều mạng các vị trí liên kết
protein; thứ hai là bài toán dóng hàng toàn cục hai mạng tương tác protein-
protein. Luận án cũng đã giới thiệu một số thuật toán được các tác giả đề xuất
để giải 2 bài toán này trong thời gian gần đây. Các thuật toán này sử dụng cách
tiếp cận heuristic hoặc các thuật toán lặp chẳng hạn như GA. Các thuật toán
theo cách tiếp cận heuristic có ưu điểm là cho lời giải nhanh, tuy nhiên thường
có chất lượng lời giải chư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
47
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, trong đó tập trung giới thiệu 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. Đây là các kiến thức nền tảng để phục vụ
cho các nghiên cứu được giới thiệu ở chương 2 và chương 3 của luận án.
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 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. Đây là các phương pháp tối
ưu mềm được sử dụng phổ biến trong việc giải quyết các bài toán tối ưu tổ hợp
khó. 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.
48
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. Thuật toán đầu tiên ACO-MGA được xây dựng
dựa trên phương pháp tối ưu đàn kiến thuần túy. Thuật toán ACO-MGA2 được
xây dựng dựa trên lược đồ memetic theo 2 giai đoạn, giai đoạn đầu chỉ sử dụng
ACO, không có tìm kiếm cục bộ, giai đoạn sau có áp dụng tìm kiếm cục bộ.
Thuật toán thứ 3 là ACOTS-MGA có sự kết hợp giữa thuật toán ACO và tìm
kiếm Tabu theo lược đồ memetic để tìm lời giải cho bài toán dóng hàng nhiều
đồ thị.
Các thực nghiệm được tiến hành trên các bộ dữ liệu mô phỏng và dữ liệu
thực đã cho thấy hiệu quả nổi trội của các thuật toán đề xuất so với các thuật
toán mới nhất hiện nay cả về thời gian lẫn chất lượng lời giải.
2.1. Bài toán dóng hàng nhiều đồ thị
Mục 1.1.2 đã giới thiệu về bài toán dóng hàng các mạng các vị trí liên kết
protein. Để dóng hàng các mạng này, đầu tiên cấu trúc của các protein sẽ được
mô hình hóa dưới dạng đồ thị như mô tả ở mục 1.1.2.1. Sau đó việc dóng hàng
các mạng các vị trí liên kết protein sẽ được quy về 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 trong bài báo [Weskamp et al., 2007] như dưới đây.
49
2.1.1. Tập nhiều đồ thị
Một multigraph [Weskamp et al., 2007] 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, các đỉnh
(nút) đượ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.
Trong các đồ thị có các toán tử chỉnh sửa được định nghĩa như sau.
Đị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
ii) Thay đổi nhãn của một nút: Nhãn 𝑙(𝑣) của một nút 𝑣 ∈ 𝑉 có thể thay
bằng nhãn khác thuộc tập L
iii) Thay đổi trọng số của một cạnh: Trọng số w(e) của một cạnh e có thể
thay đổi tùy theo những hình thể khác nhau.
2.1.2. Dóng hàng nhiều đồ thị
Cho tập đồ thị G ={G1(V1,E1),…,Gn(Vn,En)}, với mọi tập đỉnh Vi ta thêm
vào nút giả (ký hiệu là ) không có cạnh kết nối với các đỉnh khác, khi đó một
dóng hàng của G được định nghĩa như sau.
Định nghĩa 2.2. (Dóng hàng nhiều đồ thị) [Weskamp et al., 2007].
Tập 𝐴 {V1 {}} … {Vn {}} là một dóng hàng của đa đồ thị G nếu
và chỉ nếu:
1. Với mọi i=1,…,n và với mỗi 𝑣 ∈ 𝑉𝑖, tồn tại đúng một a = (a1,…,an) ∈ 𝐴
sao cho 𝑣 = 𝑎𝑖
2. Với mỗi a = (a1,…,an) ∈ 𝐴, tồn tại ít nhất một 1 ≤ i ≤ n sao cho 𝑎𝑖 ≠
50
Hình 2.1 minh họa một dóng hàng của một 4-đồ thị với các đỉnh giả dạng
hình vuông và các đỉnh có nhãn là các ô tròn có nhãn là các ký tự. Lưu ý rằng
mỗi đồ thị chỉ dùng một đỉnh giả nhưng để dễ hình dung, đồ thị thứ nhất và thứ
tư ta để hai đỉnh có nhãn giả với nghĩa rằng các nút ở hàng tương ứng được
dóng với nút giả ở đồ thị này.
Hình 2.1. Một dóng hàng nhiều đồ thị của tập 4 đồ thị, đỉnh hình vuông là giả
còn các đỉnh tròn là đỉnh thực có nhãn là các ký tự tương ứng.
Để đánh giá chất lượng của một dóng hàng nhiều đồ thị, người ta dùng
hàm tính điểm cho khoảng cách chỉnh sửa. Hàm này xác định dựa trên tập phép
toán chỉnh sửa dẫn ra ở trên để đối sánh các cặp đồ thị theo cách dóng hàng đã
chọn.
Để dễ trình bày, về sau ta qui ước giữ nguyên ký hiệu G
={G1(V1,E1),…,Gn(Vn,En)} để chỉ tập đồ thị mà trong đó các đồ thị Gi đã bổ
sung nút giả vào Vi với mọi i=1,…,n.
2.1.3. Hàm đánh giá chất lượng dóng hàng
Định nghĩa 2.3 (Hàm đánh giá chất lượng dóng hàng)
Với mỗi dóng hàng A của tập đồ thị G, hàm đánh giá chất lượng s(A)
được xác định theo biểu thức (2.1) [Weskamp et al., 2007]:
51
, (2.1)
trong đó ai là véctơ dóng hàng ở cột i của dóng hàng A, 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):
, (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):
,
(2.3)
Trong công thức (2.3) là giá trị tuyệt đối
của độ chênh lệch giữa 2 trọng số cạnh. Để đảm bảo sự khách quan khi so sánh
các thuật toán dóng hàng, các tham số (nsm, nsmm, ns, esm, esmm, ε) được thiết
lập như trong -5.0; [Fober et al., 2009]: nsm = 1.0; nsmm =
ns = -2.5; esm = 0.2; esmm =-0.1; ε=0.2.
Theo công thức 2.2, điểm số ns sẽ đánh giá sự tương thích của các nút nằm
trên một hàng. Các nút có nhãn trùng nhau sẽ được thưởng một giá trị nsm, việc
dóng hàng với các nút khác nhãn hoặc dóng hàng với nút giả sẽ bị phạt tương
ứng với các giá trị nsmm và ns.
52
Tương tự, công thức 2.3 sử dụng để đánh giá về sự tương thích về trọng
số của các cạnh, trong đó định nghĩa một ngưỡng là độ dung sai về độ lệch
trọng số của các cạnh. Hai cạnh được coi là khớp với nhau nếu trọng số của
chúng sai khác nhau không quá giá trị . Khi phép dóng hàng tạo ra các cạnh
khớp với nhau thì sẽ được thưởng điểm dóng hàng bằng giá trị esm. Ngược lại
khi hai cạnh không khớp với nhau được dóng hàng, hoặc dóng hàng một cạnh
thực với một cạnh không tồn tại trên đồ thị khác thì điểm dóng hàng sẽ bị trừ
A
đi giá trị tương ứng bằng esmm.
A A
3
3
3
C
3
3
C
B
B
3
5
3
2
D
D
3
E
Hình 2.2. Ví dụ dóng hàng 2-đồ thị.
Để dễ hình dung các công thức tính điểm chất lượng dóng hàng đa đồ
thị, xét dóng hàng 2-đồ thị với nhãn các đỉnh và trọng số các cạnh được cho
như trên hình 2.2 (các đường liền nét thể hiện các cạnh của đồ thị và các đường
đứt nét thể hiện các dóng hàng).
Đối với sự tương đồng về nhãn của các đỉnh, từ hình vẽ ta thấy trên 5
vectơ dóng hàng, có 4 cặp đỉnh được dóng hàng có nhãn giống nhau và đỉnh E
của đồ thị thứ 2 được dóng với đỉnh giả của đồ thị thứ nhất. Do vậy điểm tương
đồng về nhãn của đỉnh là 4 1 – 1 2.5=1.5.
53
Đối với sự tương đồng về trọng số cạnh, chỉ có 2 cạnh AC, BC của 2 đồ
thị là khớp với nhau về trọng số. Cạnh CD có trên cả 2 đồ thị nhưng trọng số
không khớp nhau (Độ chênh lệch trọng số của cạnh CD trên đồ thị 1 và đồ thị
2 là 2 lớn hơn ngưỡng giá trị ). Cạnh BD chỉ xuất hiện ở đồ thị thứ nhất mà
không có trên đồ thị thứ 2; trong khi đó các cạnh AB, CE, DE lại chỉ có ở đồ
thị thứ 2 mà không có trên đồ thị thứ nhất. Tổng hợp lại ta sẽ có tổng điểm
tương thích về cạnh là 2 0.2 – 1 0.1 – 4 0.1=-0.1.
Tổng hợp lại ta có điểm chất lượng dóng hàng là S= 1.5 - 0.1=1.4.
Việc lựa chọn hàm mục tiêu s(A) tính theo công thức 2.1 là do đặc thù
của bài toán dóng hàng nhiều mạng các vị trí liên kết protein. Mục tiêu của bài
toán là tìm ra sự tương đồng trong cấu trúc của các protein. Chính vì vậy, cần
ưu tiên dóng các đỉnh có cùng nhãn với nhau, bên cạnh đó khi các cấu trúc
tương đồng với nhau thì khoảng cách giữa các đỉnh cũng sẽ ít có sự chênh lệch.
Lời giải cần tìm của bài toán MGA là dóng hàng làm cực đại hàm đánh
giá 𝑠(𝐴). Đây là bài toán NP-khó, nếu dùng phương pháp vét cạn độ phức tạp sẽ là O((𝑉𝑚𝑎𝑥)!𝑛) với Vmax là số đỉnh của đồ thị có nhiều đỉnh nhất và n là số đồ thị.
Các phần tiếp theo của chương này trình bày các thuật toán mà luận án
đề xuất. Các kết quả thực nghiệm đã cho thấy các thuật toán đề xuất cho kết
quả nổi trội so với các thuật toán giải bài toán dóng hàng nhiều mạng các vị trí
liên kết protein mới nhất.
2.2. Thuật toán dựa trên ACO
Trong chương 1, chúng tôi đã giới thiệu hai thuật toán Greedy do
Weskamp [Weskamp et al., 2007] và GAVEO do Fober [Fober et al., 2009] đề
xuất để giải quyết bài toán dóng hàng nhiều mạng các vị trí liên kết protein.
Thuật toán Greedy theo cách tiếp cận tham lam nên có thời gian chạy nhanh,
54
tuy nhiên chất lượng lời giải rất thấp. Thuật toán GAVEO áp dụng giải thuật di
truyền nên có chất lượng lời giải tốt, tuy nhiên thời gian chạy lâu và sử dụng
lại nhiều lời giải của các bước lặp trước.
Để khắc phục các nhược điểm trên, trong mục này luận án đề xuất thuật
toán mới dựa trên thuật toán tối ưu hóa đàn kiến kết hợp với tìm kiếm cục bộ
có tên là ACO-MGA để giải bài toán dóng hàng nhiều mạng các vị trí liên kết
protein.
Như đã phân tích ở mục 1.2.2.7 của chương 1, phương pháp ACO phù
hợp với các bài toán trên mô hình đồ thị và có một số ưu điểm so với giải thuật
di truyền. Thuật toán đề xuất áp dụng phương pháp ACO để xây dựng các dóng
hàng nhiều đồ thị vừa khai thác được các thông tin heuristic của thuật toán
Greedy, vừa khai thác được thông tin học tăng cường thông qua việc cập nhật
vết mùi.
Các kết quả mà chúng tôi trình bày dưới đây đã được giới thiệu trong
công trình 1.
2.2.1. Đồ thị cấu trúc
Xét bài toán dóng hàng cho đa đồ thị G ={G1(V1,E1),…,Gn(Vn,En), trong
đó mỗi đồ thị biểu diễn một mạng các vị trí liên kết protein, sau khi bổ sung nút
giả vào tập đỉnh của các đồ thị Gi như đã nói ở trên, đồ thị cấu trúc và thủ tục
xây dựng lời giải như sau.
Đồ 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.3 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ả.
55
Hình 2.3. Đồ thị cấu trúc khi dóng hàng n đồ thị, trong đó mỗi đồ thị có 2
hoặc 3 nút thực
Một dóng hàng của n đồ 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 giả 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 thì “bước” sang đỉnh khác cùng tầng rồi
quay lại cho đến khi qua hết mọi đỉnh thực mỗi đỉnh đúng một lần.
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.
56
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):
, (2.4)
trong đó:
𝑖 [0,1] là cường độ vết mùi của cạnh nối đỉnh j của Gi tới đỉnh k của
R_Vi là số đỉnh còn lại chưa dóng hàng trên Vi kể cả nút giả,
𝜏𝑗,𝑘
Gi+1 , cường độ vết mùi được tính theo các công thức giới thiệu ở mục
2.3.3.
α, β là 2 hằng số chọn trước để thể hiện mức độ ảnh hưởng của thông
tin heuristic và thông tin vết mùi đối với việc lựa chọn đỉnh tiếp theo
được dóng hàng. Trong các thuật toán đề xuất 2 tham số này thường
được chọn là 1, thể hiện thông tin heuristic và thông tin vết mùi có ảnh
𝑖 (𝑎) là thông tin heuristic được tính bởi công thức (2.5).
hưởng như nhau trong quá trình kiến xác định đỉnh được dóng hàng.
𝑁𝐿(𝑘,𝑎)
𝜂𝑗,𝑘
𝑖 (𝑎) = { 𝜂𝑗,𝑘
𝑖 𝜂𝑚𝑖𝑛
𝑘 là đỉnh thực , (2.5) 𝑘 là đỉnh giả
trong đó NL(k,a) là số đỉnh trong {a1,…ai} có nhãn trùng với nhãn l(k)
của đỉnh k, 𝜂𝑚𝑖𝑛 > 0 là giá trị đủ bé cho trước. Theo công thức 2.5, các
đỉnh có nhãn trùng với nhãn của các đỉnh đã được dóng hàng trên vectơ
57
dóng hàng a sẽ được ưu tiên dóng hàng trước, và các đỉnh giả sẽ có xác
suất được lựa chọn nhỏ.
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.4, trong đó đỉnh giả đánh số -1, các đỉnh khác đánh số
0,1, 2, v.v. 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
Hình 2.4. Kiến xây dựng lời giải
58
2.2.3. Qui tắc cập nhật mùi
Ban đầu thông tin vết mùi được khởi tạo bằng giá trị max cho trước. Sau
khi các con kiến đã tìm được lời giải, các lời giải của bước lặp được đánh giá
và chọn lời giải tốt nhất để thực hiện tìm kiếm địa phương cải tiến chất lượng
lời giải rồi thực hiện 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:
, (2.6)
Trong đó: . (2.7)
Với hệ số bay hơ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. 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.5,
trong đó các vectơ dóng hàng là một hàng dọc, các chữ cái là nhãn của thành
phần tương ứng.
59
Hình 2.5. Một hoán vị cặp đỉnh có cùng nhãn trong thủ tục tìm kiếm địa
phương
2.3. Thuật toán theo lược đồ memetic
Ở mục 2.2, chúng tôi đã trình bày về thuật toán ACO-MGA áp dụng để
giải bài toán dóng hàng nhiều mạng. Mặc dù thuật toán ACO-MGA cho chất
lượng lời giải tốt hơn so với thuật toán GAVEO, tuy nhiên vẫn có những hạn
chế nhất định trong cách xác định thông tin heuristic và thủ tục tìm kiếm cục
bộ được thực hiện trong tất cả các vòng lặp kể cả khi chất lượng lời giải chưa
đủ tốt dẫn tới thuật toán chưa đạt hiệu quả cao.
Mục này chúng tôi sẽ trình bày về một thuật toán mới là sự cải tiến của
thuật toán ACO-MGA, thuật toán mới đề xuất gọi là ACO-MGA2 có một số
cải tiến sau:
Thay đổi cách xác định thông tin heuristic, không phụ thuộc tham
số min như thuật toán ACO-MGA.
Sử dụng cách cập nhật vết mùi mới chia thành 2 giai đoạn để khai
thác hiệu quả thông tin học tăng cường hoặc tăng cường tính khám
phá của thuật toán theo từng giai đoạn khác nhau.
Chiến lược tìm kiếm cục bộ áp dụng theo lược đồ memetic, chỉ áp
dụng trong giai đoạn cuối của thuật toán khi chất lượng lời giải do
các kiến xây dựng đủ tốt. Thủ tục tìm kiếm cục bộ trong ACO-
60
MGA2 ngoài việc hoán vị các đỉnh có cùng nhãn còn xét các cặp
đỉnh có nhãn khác nhau nên có thể cải thiện chất lượng lời giải tốt
hơn ACO-MGA.
Các thực nghiệm cũng được tiến hành trên các bộ dữ liệu sinh học đã
được công bố trong các bài báo khoa học có uy tín như mô tả trong mục 2.5.1
Các kết quả thực nghiệm được trình bày ở mục 2.5.2 cho thấy thuật toán
ACO-MGA2 cho chất lượng lời giải tốt hơn so với các cách tiếp cận trước đó.
Các kết quả nghiên cứu đã được trình bày trong công trình 2. Các phần
dưới đây giới thiệu chi tiết về thuật toán này.
2.3.1. Lược đồ chung
Xét bài toán dóng hàng một tập G các đồ thị
G ={G1(V1,E1),…,Gn(Vn,En) trong đó mỗi đồ thị được bổ sung các đỉnh giả.
Thuật toán ACO-MGA2 được xây dựng theo lược đồ memetic, trong đó sử
dụng thuật toán ACO để sinh ra tập các lời giải. ACO-MGA2 sử dụng đồ thị
cấu trúc giống thuật toán ACO-MGA nhưng khai thác thông tin heuristic hiệu
quả hơn và chỉ sử dụng tìm kiếm cục bộ trong các vòng lặp cuối.
Thuật toán ACO-MGA2 được đặc tả trong thuật toán 2.1.
61
Thuật toán 2.1: Thuật toán ACO-MGA2
Input: Tập các đồ thị G ={G1(V1,E1),…,Gn(Vn,En)
Output: Dóng hàng tốt nhất cho tập đồ thị G:
Begin
Khởi tạo;
while (Chưa thỏa mãn điều kiện dừng) do
for each a A do
Kiến a xây dựng một dóng hàng cho tập các đồ thị;
Tìm kiếm cục bộ trên lời giải tốt nhất //Chỉ áp dụng ở giai đoạn 2
//Tìm kiếm bằng cách đổi vị trí của các đỉnh khác nhãn.
//Tìm kiếm bằng cách đổi vị trí của các đỉnh cùng nhãn.
Cập nhật vết mùi theo quy tắc SMMAS;
Cập nhật lại lời giải tốt nhất;
end for;
end while;
Lưu lại lời giải tốt nhất;
end;
Đầu tiên thuật toán khởi tạo các tham số và các kiến nhân tạo. Sau bước
khởi tạo, thuật toán ACO-MGA2 thực hiện các vòng lặp theo 2 giai đoạn như
mô tả trong thuật toán 2.1.
Giai đoạn đầu, trong mỗi vòng lặp, các kiến xây dựng lời giải trên đồ thị cấu
trúc dựa trên thông tin heuristic và vết mùi. Sau đó lời giải tốt nhất của các kiến
được lựa chọn để cập nhật vết mùi theo quy tắc cập nhật mùi SMMAS, đồng
thời cập nhật lại lời giải tốt nhất toàn cục.
62
Giai đoạn 2 của thuật toán, trong mỗi vòng lặp, sau khi các kiến xây dựng
xong các lời giải, 2 kỹ thuật tìm kiếm cục bộ được áp dụng để tìm lời giải tốt
nhất của mỗi vòng lặp. Do sự phù hợp về nhãn của các đỉnh được tính điểm cao
hơn so với sự phù hợp về trọng số cạnh (theo công thức 2.1) nên thủ tục thay
đổi vị trí của các đỉnh khác nhãn trên các véctơ dóng hàng được thực hiện trước.
Thủ tục này được áp dụng theo chiến lược tìm được lời giải tốt nhất thì dừng,
có nghĩa là sẽ tìm kiếm từ đồ thị đầu tiên cho đến đồ thị cuối cùng để tìm lời
giải tốt nhất có thể. Chiến lược tìm kiếm thứ 2 là hoán đổi vị trí của các đỉnh
cùng nhãn nhằm mục đích tăng số cạnh có sự tương đồng về trọng số.
Sau khi tìm kiếm cục bộ, thuật toán sẽ cập nhật lại vết mùi theo qui tắc
SMMAS dựa trên lời giải tốt nhất tìm được.
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
𝑖 (𝑎)được tính bởi công thức 2.8.
tạo bằng 𝜏𝑚𝑎𝑥 và được cập nhật lại sau các vòng lặp.
Thông tin heuristic 𝜂𝑗,𝑘
, (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.
63
Ý tưởng của việc khai thác thông tin heuristic ở đây là ưu tiên những đỉnh
có cùng nhãn với các đỉnh đã được dóng hàng sẽ được dóng hàng trước và đặt
tỷ lệ rất nhỏ cho việc lựa chọn các đỉnh giả để dóng hàng.
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 như sau.
Kiến chọn ngẫu nhiên một đỉnh thực chưa được dóng hàng từ đồ thị cấu
trúc làm đỉnh xuất phát. Kiến tiếp tục dựa trên thông tin heuristic và vết mùi
để tuần tự xác định các đỉnh được dóng với đỉnh xuất phát trên các đồ thị ở
các tầng tiếp theo. Các đỉnh này được lựa chọn một cách ngẫu nhiên với xác
suất được cho bởi công thức 2.4 tương tự như thuật toán ACO-MGA.
2.3.5. Qui tắc cập nhật vết mùi
Sau khi các con kiến đã tìm được lời giải (ở giai đoạn đầu) hoặc đã thực
hiện tìm kiếm địa phương (trong giai đoạn 2), các cường độ vết mùi được
cập nhật theo quy tắc cập nhật mùi SMMAS như trong các công thức 2.6 và
2.7.
Lưu ý rằng trong công thức 2.6, tham số quy định hai tính chất: tìm
kiếm tăng cường quanh lời giải tốt tìm được và khám phá lời giải mới, nhỏ
thì chú trọng tìm kiếm tăng cường còn lớn thì chú trọng tính khám phá.
Việc cập nhật mùi của thuật toán ACO-MGA2 cải tiến so với thuật toán
ACO-MGA ở điểm thuật toán ACO-MGA2 sử dụng 2 tham số ở 2 giai
đoạn khác nhau. Giai đoạn đầu không sử dụng tìm kiếm địa phương nên
tham số được thiết lập nhỏ hơn để khai thác tốt thông tin học tăng cường,
64
còn giai đoạn 2 khi áp dụng tìm kiếm cục bộ thì tham số này được thiết lập
lớn hơn để tăng tính khám phá.
2.3.6. Thủ tục tìm kiếm cục bộ
Thủ tục tìm kiếm cục bộ thực hiện tuần tự trên đồ thị G1 đến đồ thị Gn
theo nguyên tắc tìm được kết quả tốt nhất thì dừng. Thủ tục này gồm hai kỹ
thuật: đổi các đỉnh cùng nhãn và đổi các đỉnh khác nhãn.
1) Đổi các đỉnh khác nhãn. Đổi vị trí trên cặp vectơ dóng hàng tương
ứng với mỗi cặp đỉnh khác nhãn của đồ thị Gi đang xét nếu việc đổi chỗ đó
làm tăng số lượng các đỉnh cùng nhãn trên các véctơ dóng hàng.
2) Đổi các đỉnh cùng nhãn. Đổi vị trí trên cặp vectơ dóng hàng tương
ứng với mỗi cặp đỉnh cùng nhãn của đồ thị Gi đang xét nếu việc đổi vị trí đó
cải thiện độ phù hợp của trọng số ở các cạnh liên quan.
Nếu sau khi đổi chỗ, hàm đánh giá chất lượng tăng lên thì lời giải nhận
được sẽ thay thế cho lời giải tốt nhất lúc đó. Quá trình này được lặp lại cho
đến khi tìm được lời giải tốt nhất.
Trong công thức 2.1 tính tương thích của các đỉnh cải thiện giá trị hàm
mục tiêu nhiều hơn sự phù hợp trọng số cạnh nên ta ưu tiên đổi đỉnh khác
nhãn trước. Vì vậy, với mỗi dóng hàng, ta chỉ thực hiện đổi đỉnh cùng nhãn
sau khi đã thực hiện xong quá trình tìm kiếm nhờ đổi đỉnh khác nhãn.
Vì thủ tục tìm kiếm cục bộ tốn thời gian nên chỉ áp dụng cho giai đoạn
hai, khi lời giải tốt nhất tìm được đủ tốt.
2.4. Thuật toán memetic mới kết hợp ACO và tìm kiếm Tabu
Mục 2.3 giới thiệu một thuật toán memetic để giải bài toán dóng hàng
nhiều mạng các vị trí liên kết protein có tên là ACO-MGA2, các đánh giá so
sánh đã cho thấy ưu điểm của thuật toán này với các thuật toán trước đó được
65
thực hiện trên các bộ dữ liệu thực. Tuy nhiên ACO-MGA2 có những hạn chế
trong cách xác định thông tin heuristic và thủ tục tìm kiếm cục bộ nên mục này
giới thiệu một thuật toán memetic mới gọi là ACOTS-MGA với một số cải tiến
so với ACO-MGA2 để giải bài toán dóng hàng các mạng các vị trí liên kết
protein.
Thuật toán ACOTS-MGA có những cải tiến so với thuật toán ACO-
MGA2 bao gồm:
Khi sử dụng phương pháp tối ưu đàn kiến để tìm lời giải, thuật
toán ACOTS-MGA cải tiến thủ tục bước ngẫu nhiên sử dụng chiến
lược Beam search. Thay vì tìm kiếm trên toàn bộ tập các đỉnh chưa
được dóng hàng, thuật toán mới chỉ tìm kiếm trên tập các đỉnh có
cùng nhãn với các đỉnh đã được dóng hàng, điều này làm giảm
không gian tìm kiếm, và cách xác định thông tin heuristic cũng có
sự thay đổi cho phù hợp.
Về quy tắc cập nhật mùi, thuật toán ACOTS-MGA cập nhật vết
mùi theo 3 mức, trong đó thể hiện sự phân biệt mức độ ưu tiên
khác nhau của lời giải tốt nhất của vòng lặp, với lời giải tốt nhất
toàn cục.
Cải tiến thứ 3 là sử dụng tìm kiếm Tabu thay cho tìm kiếm cục bộ
để hạn chế việc lặp lại những bước chuyển đã được xét như trong
thuật toán ACO-MGA2.
Các kết quả nghiên cứu đã được trình bày trong công trình 6. Phần dưới
đây chúng tôi sẽ phân tích chi tiết về thuật toán này.
66
2.4.1. Đồ thị cấu trúc
Đồ thị cấu trúc của thuật toán ACOTS-MGA được sử dụng giống như thuật
toán ACO-MGA2.
2.4.2. Thông tin heuristic
Vì thuật toán ACOTS-MGA sử dụng chiến lược Beam search trong quá
trình bước ngẫu nhiêu của các kiến. Trong đó chỉ xét các đỉnh có cùng nhãn với
các đỉnh đã dóng hàng trên véctơ dóng hàng, nên thông tin heuristic sẽ không
𝑖 (𝑎) là số
xét đến sự phù hợp về nhãn của các đỉnh mà tập trung vào tính tương thích về
cạnh của các đỉnh được dóng hàng. Vì vậy, thông tin heuristic 𝜂𝑗,𝑘
đ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 là tập các nhãn của các đỉnh thuộc véctơ dóng
hàng a, gọi là tập các đỉnh thuộc đồ thị Gi có
nhãn trùng với nhãn của các đỉnh thuộc véctơ dóng hàng. Trong trường hợp
không có đỉnh nào có nhãn trùng với nhãn của các đỉnh đã được dóng hàng, Bi
sẽ là tập các đỉnh còn lại chưa được dóng hàng. Kiến sẽ lựa chọn ngẫu nhiên 1
đỉnh trong Bi với xác suất được cho ở công thức 2.9.
Để dễ hình dung, giả sử véctơ dóng hàng đã được xây dựng từ đỉnh a1 của
đồ thị G1 và thực hiện thủ tục bước ngẫu nhiên để phát triển đến đỉnh ai của đồ
thị Gi khi đó sẽ lựa chọn đỉnh thứ k thuộc đồ thị Gi +1 với xác suất là:
67
. (2.9)
Sau khi xây dựng đầy đủ véctơ a=(a1,…,an), các đỉnh thực thuộc véctơ này
sẽ bị loại bỏ khỏi đồ thị cấu trúc để tiếp tục quá trình xây dựng các véctơ dóng
hàng cho đến khi tất cả các đỉnh đều được dóng hàng.
2.4.4. Qui tắc cập nhật vết mùi
Khác với thuật toán ACO-MGA2, việc cập nhật mùi của ACOTS-MGA
được thực hiện theo các công thức 2.10 và 2.11.
, (2.10)
(2.11) .
Các tham số max,min và ∈ (0,1) được khởi tạo tương tự như thuật toán
ACO-MGA2. Trong thuật toán ACOTS-MGA luận án sử dụng thêm tham số
mid để cập nhật mùi trong trường hợp lời giải mới mà các kiến tìm được là lời
giải tốt nhất của vòng lặp nhưng chưa phải là lời giải tốt nhất toàn cục. Tham
số này được thiết lập nhỏ hơn max với ý nghĩa là lời giải tốt nhất toàn cục sẽ để
lại lượng vết mùi lớn hơn so với lời giải tốt nhất của vòng lặp.
2.4.5. Thủ tục tìm kiếm Tabu
Trong các vòng lặp cuối của thuật toán ACOTS-MGA, thuật toán tìm kiếm
Tabu được áp dụng để tăng cường chất lượng lời giải.
Thủ tục tìm kiếm Tabu sẽ duyệt lần lượt các đỉnh của các đồ thị, với mỗi đồ
thị sẽ thực hiện việc hoán vị các cặp đỉnh trên các véctơ dóng hàng. Nếu việc
68
hoán vị này làm tăng điểm đánh giá thì lời giải tốt nhất sẽ được cập nhật bằng
lời giải hiện tại. Khác với thủ tục tìm kiếm cục bộ, thủ tục Tabu Search này có
sử dụng một danh sách Tabu để lưu lại các bước chuyển. Các bước chuyển nằm
trong danh sách Tabu sẽ không được xét lại nữa để tránh lặp lại các bước
chuyển. Vì vậy với cùng thời gian như tìm kiếm cục bộ, số lần áp dụng tìm
kiếm Tabu sẽ nhiều hơn để tăng chất lượng lời giải.
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 Tabu đượ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 hoặc có thể ấn định số lần thực
hiện.
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 Greedy do
Weskamp [Weskamp et al., 2007] và thuật toán GAVEO do Thomas Fober
[Fober et al., 2009] đề xuất. Các công trình do 2 tác giả đề xuất đã được đăng
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.
69
Trong bộ dữ liệu này, mỗi đồ thị sinh ra có từ 42 đến 95 đỉnh. Từ 74 cấu
trúc đó, các đồ thị được lựa chọn ngẫu nhiên để sinh ra các tập dữ liệu gồm 4,
8, 16, 32 đồ thị để tiến hành chạy thực nghiệm các thuật toán.
2.5.2. Thực nghiệm so sánh thuật toán ACO-MGA với thuật toán Greedy
và GAVEO
Thực nghiệm nhằm so sánh ACO-MGA với hai thuật toán Greedy và
thuật toán tiến hóa GAVEO về chất lượng lời giải và thời gian chạy. Các thực
nghiệm bao gồm:
1) Chạy các thuật toán trên cùng một bộ dữ liệu với số vòng lặp định trước
để so sánh về chất lượng dóng hàng và thời gian chạy.
2) Chạy các thuật toán trên cùng một bộ dữ liệu với cùng một thời gian
định trước để so sánh về chất lượng dóng hàng.
Các thí nghiệm của chúng tôi được thực hiện trên máy tính có cấu hình:
CPU Dual Core 2.2Ghz, RAM DDR3 3GB trên hệ điều hành Windows XP
SP3.
Đối với thuật toán ACO-MGA, sau khi tiến hành thực nghiệm với các
giá trị khác nhau của từng tham số, chúng tôi thấy rằng với các giá trị của các
tham số như dưới đây sẽ cho kết quả lời giải tốt nhất, vì vậy trong các thực
nghiệm các tham số của thuật toán được thiết lập như sau:
Số kiến trong mỗi lần lặp là 20 ;
=0.06, 𝛼 = 𝛽 = 1;
2), trong đó n là số đồ thị, Vmax là số đỉnh
max = 1.0 và min = max/(n2.Vmax
của đồ thị có nhiều đỉnh nhất.
Trong thời gian đầu tiến hành nghiên cứu bài toán MGA, do chưa có dữ
liệu thực, chúng tôi sinh ngẫu nhiên các tập dữ liệu thực nghiệm là các tập đồ
thị với các đồ thị có 20 và 50 đỉnh, số đồ thị lần lượt là 4,8,16 và 32.
70
2.5.2.1. So sánh về hiệu quả và thời gian chạy
Bảng 2.1 và bảng 2.2 dưới đây là kết quả so sánh các thuật toán
ACO-MGA, GAVEO và Greedy về điểm chất lượng dóng hàng và thời gian
chạy của các thuật toán. Bảng 2.1 là kết quả dóng hàng ứng với các đồ thị có
trung bình là 20 đỉnh và bảng 2.2 là kết quả ứng với các đồ thị có trung bình là
50 đỉnh. Các kết quả tốt hơn được thể hiện bằng chữ in đậm, thời gian chạy
ngắn hơn được thể hiện bằng chữ in nghiêng, đậm.
Bảng 2.1. So sánh chất lượng dóng hàng S(A) và thời gian chạy với các bộ dữ
liệu gồm 4, 8, 16 và 32 đồ thị, số đỉnh trung bình của mỗi đồ thị là 20 đỉnh.
Thuật toán/Số đồ thị 4 8 16 32
Điểm -40 -570 -1055 -35 Greedy Thời gian (s) 0.6 2.3 6 17
Điểm -20 65 45 1132 GAVEO 249 Thời gian (s) 501 1087.7 2484.1
Điểm 124 696 1480 7289 ACO-MGA Thời gian (s) 33.6 231.5 481.2 1266
Bảng 2.2. So sánh chất lượng dóng hàng S(A) và thời gian chạy với các bộ dữ
liệu gồm 4, 8, 16 và 32 đồ thị, số đỉnh trung bình của mỗi đồ thị là 50 đỉnh
Thuật toán/Số đồ thị 4 8 16 32
Điểm -1144 -4704 -31004 -155508 Greedy Thời gian (s) 4.8 11.3 49 210.8
Điểm -101 -75 -10872 -33698 GAVEO Thời gian (s) 1164 2739.1 6921.3 16340.8
Điểm 685 3338 1273 -18643 ACO-MGA Thời gian (s) 763.4 6523.5 12670.5 28859.8
Kết quả thực nghiệm cho thấy rằng:
71
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 chất lượng dóng hàng 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.
Trong một số trường hợp, điểm chất lượng dóng hàng của các thuật toán
là số âm. Điều này có thể giải thích là do khi tính điểm dóng hàng theo
các công thức 2.1, 2.2 và 2.3. Điểm dóng hàng phụ thuộc vào các tham
số nsm = 1.0; nsmm = -5.0; ns = -2.5; esm = 0.2; esmm =-0.1, ε =0.2. Trong
đó nsmm = -5.0; ns = -2.5 là điểm phạt khi 2 đỉnh dóng hàng có nhãn
khác nhau hoặc dóng hàng một đỉnh thực với 1 đỉnh giả (ký hiệu ).
Tham số esmm =-0.1 là điểm phạt khi các cạnh được dóng hàng không
tương thích về trọng số. Khi dóng hàng cùng lúc nhiều đồ thị với số lượng
các đỉnh khác nhau nhiều sẽ dẫn tới hàm đánh giá có kết quả âm.
2.5.2.2. So sánh ACO-MGA với GAVEO với cùng thời gian chạy
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.
Thực nghiệm thứ nhất các thuật toán được chạy trên cùng một bộ dữ liệu
và cùng thời gian chạy. Các bộ dữ liệu thực nghiệm gồm có 8, 16 và 32 đồ thị.
72
mà các đồ thị có trung bình là 20 đỉnh và thời gian chạy là 50s, 150s và 200s.
Kết quả thí nghiệm được thể hiện ở bảng 2.3, bảng 2.4 và bảng 2.5.
Bảng 2.3. So sánh điểm 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à 50s.
Thuật toán/Số đồ thị 8 16 32
GAVEO 57 46 -1327
ACO-MGA 690 2004 6511
Bảng 2.4. So sánh điểm 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à 150s
Thuật toán/Số đồ thị 8 16 32
GAVEO 75 35 953
ACO-MGA 690 2181 7166
Bảng 2.5. So sánh điểm chất lượng dóng hàng S(A)với các bộ dữ liệu là 8,16
và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 20 đỉnh và thời gian
chạy là 200s
Thuật toán/Số đồ thị 8 16 32
GAVEO 74 -38 1254
ACO-MGA 690 2262 10060
Thực nghiệm thứ 2, luận án tiến hành chạy các thuật toán ACO-MGA và
GAVEO trên các bộ dữ liệu gồm có lần lượt là 4, 8, 16 và 32 đồ thị, các đồ thị
có trung bình là 50 đỉnh và thời gian chạy lần lượt là 200s, 300s và 600s. Kết
73
quả của thực nghiệm này được thể hiện trong bảng 2.6, 2.7 và bảng 2.8. Các
kết quả tốt hơn thể hiện bằng chữ in đậm.
Bảng 2.6. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4,
8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời
gian chạy là 200s
Thuật toán/Số đồ thị 4 8 16 32
GAVEO -107 -98 -16341 -150400
ACO-MGA 674 2699 -99 -30583
Bảng 2.7. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4,
8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời
gian chạy là 300s
Thuật toán/Số đồ thị 4 8 16 32
GAVEO -103 57 -6977 -124198
ACO-MGA 737 2744 637 -25648
Bảng 2.8. So sánh điểm chất lượng dóng hàng S(A) với các bộ dữ liệu là 4,
8,16 và 32 đồ thị, với số đỉnh trung bình của mỗi đồ thị là 50 đỉnh và thời
gian chạy là 600s
Thuật toán/Số đồ thị 4 8 16 32
GAVEO -107 -77 -5282 -96123
ACO-MGA 673 2898 744 -16945
Các kết quả thực nghiệm được trình bày ở các bảng trên cho thấy khi so
sánh 2 thuật toán ACO-MGA và GAVEO với cùng một bộ dữ liệu, trên cùng
74
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.3 đả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.
Thực nghiệm thực hiện như sau:
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. Thời gian chạy được thay đổi
tăng dần để đánh giá tính hội tụ
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;
75
2), trong đó n là số đồ thị, Vmax là số
max = 1.0 và min = max/(n2.Vmax
nút của đồ thị có nhiều nút nhất.
Thủ tục tìm kiếm cục bộ đượ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;
2) và mid=0.8;
max = 1.0, min = max/(n2.Vmax
Thủ tục tìm kiếm cục bộ được gọi trong 20% số vòng lặp cuối cùng.
2.5.3.1. So sánh về chất lượng lời giải và thời gian chạy
Trong thực nghiệm này, chúng tôi chạy các thuật toán trên cùng bộ dữ
liệu đã được giới thiệu ở mục 2.5.1 với số vòng lặp định trước. Để so sánh chất
lượng lời giải và thời gian chạy của các thuật toán, chúng tôi chạy mỗi thuật
toán trên các máy tính có cùng cấu hình, mỗi thuật toán chạy 20 lần và lấy giá
trị trung bình của 20 lần chạy để so sánh.
Chất lượng lời giải và thời gian chạy của các thuật toán được thể hiện lần
lượt trong các bảng 2.9 và 2.10.
Bảng 2.9. So sánh chất lượng lời giải của các thuật toán với các tập dữ liệu
gồm 4, 8, 16 và 32 đồ thị
Thuật toán/Số đồ thị 4 8 16 32
-4098 -11827 -56861 -267004 Greedy
-1224 -2729 -10604 -63205 GAVEO
-972 -2277 -7857 -53960 ACO-MGA2
ACOTS-MGA -963 -1089 -5671 -42216
76
Bảng 2.10. So sánh thời gian chạy (tính theo giây) của các thuật toán với các
tập dữ liệu gồm 4, 8, 16 và 32 đồ thị
Thuật toán/Số đồ thị 4 8 16 32
1892 2851 10067 GAVEO 20671
272 1374 18005 ACO-MGA2 4151
6839 53800 ACOTS-MGA 171 809
Nhận xét: Các kết quả thực nghiệm trong bảng 2.9 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.
Kết quả so sánh ở bảng 2.10 cho thấy thời gian chạy của thuật toán
ACOTS-MGA thấp hơn so với thuật toán GAVEO và ACO-MGA2 khi số
lượng đồ thị gồm 4 đến 8 đồ thị. Trong trường hợp số đồ thị lớn gồm 16 hoặc
32 đồ thị thì các thuật toán GAVEO và ACO-MGA2 có thời gian chạy nhanh
hơn.
Lý do ACOTS-MGA chạy lâu hơn ACO-MGA2 khi số đồ thị lớn là do
trong thuật toán ACOTS-MGA thủ tục tìm kiếm Tabu được thực hiện lặp nhiều
lần, trong khi trong thuật toán ACO-MGA2 thủ tục tìm kiếm cục bộ chỉ thực
hiện 1 lần, trong khi đó các thủ tục này có thời gian thực hiện rất lớn. Trong
trường hợp số lượng đồ thị nhỏ, thuật toán ACOTS-MGA chạy nhanh hơn là
do số lượng trạng thái tìm kiếm nhỏ, vì vậy thuật toán đạt đến lời giải tốt nhanh
hơn do thuật toán tìm kiếm Tabu được thực hiện với số lần lặp ít hơn.
77
2.5.3.2. So sánh các thuật toán khi chạy với cùng khoảng thời gian ấn định
trước
Vì thuật toán Greedy có thời gian chạy rất nhanh nhưng lại cho chất
lượng lời giải quá thấp, nên trong thực nghiệm này chỉ so sánh chất lượng lời
giải của thuật toán GAVEO, ACO-MGA2 và ACOTS-MGA khi chạy trong
cùng một khoảng thời gian.
Thực nghiệm tiến hành chạy các thuật toán trên cùng bộ dữ liệu gồm 16
đồ thị, thời gian chạy các thuật toán được tăng dần từ 1000s đến 6000s. Các kết
Thời gian
0
1000s 2000s 3000s 4000s 5000s 6000s
-5000
g n à h
-10000
GAVEO
g n ó d
-15000
ACO-MGA2
ACOTS-MGA
-20000
-25000
g n ợ ư l t ấ h c m ể i Đ
-30000
-35000
quả được thể hiện qua biểu đồ ở hình 2.6.
Hình 2.6. So sánh chất lượng lời giải các thuật toán với bộ dữ liệu gồm 16 đồ
thị và thời gian tăng từ 1000s đến 6000s.
Biểu đồ ở hình 2.6 cho thấy khi tăng thời gian chạy từ 1000s đến 6000s
chất lượng lời giải của thuật toán ACOTS-MGA luôn luôn tốt hơn thuật toán
ACO-MGA2 và GAVEO.
Biểu đồ trên cho ta thấy giai đoạn đầu trước 2000s thì cả 2 thuật toán
ACO-MGA2 và thuật toán ACOTS-MGA đều cho chất lượng lời giải chưa cao
là vì giai đoạn này chỉ áp dụng thuật toán ACO thuần túy mà chưa có kết hợp
78
sử dụng tìm kiếm cục bộ. Tuy nhiên ACOTS-MGA cho chất lượng lời giải tốt
hơn ACO-MGA2 là do sự cải tiến của thủ tục bước ngẫu nhiên của
ACOTS-MGA theo chiến thuật beam search, các kiến ưu tiên lựa chọn các đỉnh
cùng nhãn với các đỉnh đã được dóng hàng trước đó trên cùng véctơ dóng hàng.
Vì vậy sẽ làm tăng độ tương đồng về nhãn của các đỉnh.
Sau thời điểm 2000s, chất lượng lời giải của các thuật toán tăng nhanh
hơn là vì khi đó đã có áp dụng kỹ thuật tìm kiếm cục bộ và tìm kiếm bằng Tabu
Search. Thuật toán ACOTS-MGA2 cho chất lượng lời giải tốt hơn
ACO-MGA2 vì thuật toán tìm kiếm Tabu được gọi lặp lại nhiều lần trên các lời
giải tốt nhất tìm được, còn trong thuật toán ACO-MGA2, thủ tục tìm kiếm cục
bộ chỉ được gọi 1 lần sau mỗi vòng lặp.
Sau thời điểm 6000s thì chất lượng lời giải các thuật toán ổn định nên
luận án chỉ tiến hành so sánh đến thời điểm này.
Ngoài ra, để kiểm tra chất lượng lời giải của các thuật toán ACOTS-
MGA với ACO-MGA2 và GAVEO trong cùng thời gian. Chúng tôi lần lượt
chạy thuật toán các thuật toán GAVEO và ACO-MGA2 trên cùng bộ dữ liệu
với thời gian tương đương với thời gian chạy của thuật toán ACOTS-MGA
được cho trong bảng 2.10. Kết quả thu được như sau:
Bảng 2.11. So sánh điểm chất lượng dóng hàng S(A) của 3 thuật toán với
cùng thời gian chạy với các tập gồm 4,8,16 và 32 đồ thị.
Thuật toán/Số đồ thị 4 8 16 32
-1224 -2879 -10744 -63205 GAVEO
-989 -1524 -7757 -53960 ACO-MGA2
ACOTS-MGA -963 -1089 -5672 -42216
79
Qua bảng 2.11 có thể thấy khi chạy trong cùng một thời gian bằng với
thời gian chạy của thuật toán ACOTS-MGA được cho trong bảng 2.10, 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
Bài toán MGA là cách tiếp cận mới để phân tích cấu trúc của sinh học
phân tử. Trong chương này, chúng tôi trình bày các khái niệm liên quan đến
bài toán dóng hàng tập gồm nhiều đồ thị và đề xuất 3 thuật toán là ACO-MGA,
ACO-MGA2 và ACOTS-MGA để giải quyết bài toán dóng hàng nhiều đồ thị.
Kết quả thực nghiệm trên các bộ dữ liệu mô phỏng và dữ liệu thực cho
thấy các thuật toán đề xuất cho kết quả tốt hơn nhiều so với thuật toán GAVEO
khi chạy với cùng bộ dữ liệu và cùng thời gian chạy. Khi số đỉnh của đồ thị
tăng lên thì thời gian tìm kiếm địa phương trong ACO-MGA, ACO-MGA2 và
ACOTS-MGA làm tăng thời gian chạy nên các thuật toán đề xuất chạy lâu hơn
GAVEO trong một số trường hợp.
Các thuật toán đề xuất dóng hàng nhiều mạng các vị trí liên kết protein
cho chất lượng dóng hàng tốt hơn các thuật toán GAVEO và Greedy sẽ giúp
xác định được sự tương đồng về cấu trúc của các protein chính xác hơn. Thông
qua tính tương đồng về mặt cấu trúc đó có thể suy diễn chức năng của các
protein chưa biết thông qua các protein đã biết [Yuan et al., 2018]. Đó là ý
nghĩa sinh học mà các thuật toán đề xuất mang lại.
Trong các nghiên cứu tiếp theo chúng tôi sẽ cải tiến kỹ thuật tìm kiếm
cục bộ để giảm thời gian chạy và tăng hiệu quả thuật toán.
80
Chương 3. DÓNG HÀNG TOÀN CỤC HAI MẠNG TƯƠNG TÁC PROTEIN-PROTEIN
Chương này giới thiệu 3 thuật toán mà luận án đề xuất để giải bài toán
dóng hàng toàn cục mạng tương tác protein là FASTAN, ACOGNA và
ACOGNA++. Hai thuật toán đầu tối ưu theo tiêu chuẩn GNAS trong đó thuật
toán FASTAN theo hướng tiếp cận heuristic và thuật toán ACOGNA dựa trên
giải thuật tối ưu đàn kiến. Thuật toán thứ 3 là ACOGNA++ cho phép tùy chọn
tối ưu theo một trong các tiêu chuẩn GNAS, EC và S3.
Các thực nghiệm đã chứng minh các thuật toán này cho chất lượng lời giải
tốt hơn so với các phương pháp mới nhất hiện nay. Bênh cạnh đó thời gian chạy
của các thuật toán đề xuất cũng nhanh hơn so với các thuật toán metaheuristic
khác có chất lượng lời giải tương đương.
Để người đọc dễ theo dõi, trước tiên chúng ta đến với phát biểu toán học
của bài toán dóng hàng toàn cục mạng tương tác protein.
3.1. Bài toán dóng hàng toàn cục mạng tương tác protein
Bài toán dóng hàng toàn cục mạng tương tác protein đã được giới thiệu ở
chương 1. Tuy nhiên để thuận tiện cho việc trình bày các thuật toán mới đề
xuất, phần dưới đây phát biểu lại bài toán dưới dạng toán học.
3.1.1. Phát biểu bài toán
Mạng tương tác protein là mạng được mô hình hóa bởi một đồ thị
G = (V, E) trong đó V là tập các đỉnh của đồ thị đại diện cho các protein và E
là tập các cạnh tương ứng của đồ thị mô tả tương tác giữa các protein.
Giả sử G1 = (V1, E1) và G2 = (V2, E2) là 2 đồ thị biểu diễn hai mạng tương
tác protein, trong đó V1, V2 tương ứng là tập các đỉnh của các đồ thị G1 và G2;
E1, E2 là tập các cạnh tương ứng của G1, G2. Không mất tính tổng quát ta có thể
81
giả sử trong đó |V| là ký hiệu cho số phần tử của tập V. Dưới đây là
định nghĩa về bài toán dóng hàng toàn cục được sử dụng chủ yếu trong các
nghiên cứu trước đây [Aladag & Erten, 2013; L. Chindelevitch, Ma, Liao, &
Berger, 2013; Leonid Chindelevitch, Liao, & Berger, 2010; Oleksii Kuchaiev
& Pržulj, 2011; Singh et al., 2008].
Định nghĩa 3. 1. Dóng hàng toàn cục hai mạng tương tác protein là xác
định một đơn ánh trong đó mỗi đỉnh của V1 được khớp với duy nhất
1 đỉnh .
Trong trường hợp thì f là một song ánh.
Bài toán dóng hàng toàn cục hai mạng tương tác protein - protein là tìm
một dóng hàng tối ưu theo một hàm đánh giá chất lượng dóng hàng dựa trên sự
tương đồng về mặt trình tự và/hoặc cấu trúc được cho trước.
3.1.2. Đánh giá chất lượng dóng hàng toàn cục
Ở mỗi nghiên cứu, người ta đề xuất các tiêu chuẩn đánh giá chất lượng
dóng hàng khác nhau, mỗi tiêu chuẩn đều có ưu và nhược điểm riêng. Dưới đây
chúng tôi giới thiệu các tiêu chuẩn dóng hàng được sử dụng phổ biến nhất trong
các nghiên cứu về bài toán dóng hàng toàn cục mạng tương tác protein.
.
Cho một dóng hàng mạng f ký hiệu và
Tiêu chuẩn GNAS được Aladag [Aladag & Erten, 2013] giới thiệu được
tính theo công thức sau:
𝑢∈𝑉1
(3.1) 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢)) , 𝐺𝑁𝐴𝑆 = 𝛼. |𝑓(𝐸1)| + (1 − 𝛼). ∑
82
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 [Aladag & Erten, 2013; Altschul et al., 1990] (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ề sự tương
đồng về topology và độ tương đồng về trình tự giữa hai mạng tương tác protein-
protein được dóng hàng.
Kuchaiev và các cộng sự [O. Kuchaiev et al., 2010] đề xuất dùng độ đo
EC như trong công thức 3.2. EC là độ đo tỷ lệ của các cạnh trong đồ thị nguồn
được dóng hàng chính xác đến các cạnh trong đồ thị thứ hai với số lượng cạnh
của đồ thị nguồn.
. (3.2)
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.
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 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, độ đ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
83
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.
, (3.3)
trong đó 𝐸(𝐺2[𝑓(𝐸1)]) là tập cạnh trong 𝐺2 của đồ thị con có tập đỉnh là 𝑓(𝑉1).
Qua các công thức 3.2 và 3.3 có thể thấy, độ đo EC chú trọng đến đồ thị
nguồn, trong khi độ đo ICS chú trọng đến đồ thị đích. Vì vậy độ đo EC không
tốt khi đánh giá chất lượng dóng hàng nếu ta dóng hàng một mạng có mật độ
cạnh thưa với một mạng có mật độ cạnh dày. Ngược lại độ đo ICS không tốt
khi ta dóng hàng một mạng dày với 1 mạng thưa.
Nhận thấy nhược điểm trên của 2 độ đo EC và ICS, Saraph và các cộng
sự [Saraph & Milenković, 2014] đề xuất độ đo S3 như công thức 3.4.
. (3.4)
Sự khác biệt của S3 với EC và ICS là ở mẫu số, S3 xét đến cả số cạnh của
đồ thị nguồn và số cạnh của đồ thị con được sinh ra bởi các đỉnh của đồ thị đích
được dóng hàng, vì vậy nó khắc phục được các nhược điểm của EC và ICS như
đã phân tích ở trên.
3.2. Thuật toán FASTAN
Mục này chúng tôi giới thiệu một thuật toán dóng hàng nhanh để giải bài
toán dóng hàng mạng tương tác protein. Mục tiêu đặt ra là xây dựng một thuật
toán dóng hàng hai mạng tương tác protein - protein có thời gian chạy nhanh
với chất lượng lời giải đủ tốt so với các thuật toán dóng hàng đã có, mục tiêu
này nhằm đảm bảo thuật toán có thể thích hợp với các bộ dữ liệu có số lượng
dữ liệu tương tác protein lớn với thời gian chạy ngắn.
84
Với mục tiêu như trên, thuật toán được xây dựng gồm 2 giai đoạn:
Giai đoạn đầu xây dựng nhanh một dóng hàng thô ban đầu dựa trên
chiến lược tham lam kết hợp với lựa chọn ngẫu nhiên các đỉnh được
dóng hàng. Việc lựa chọn ngẫu nhiên làm tăng tính đa dạng của lời
giải.
Giai đoạn thứ 2 sử dụng thủ tục rebuild để tăng chất lượng lời giải
của dóng hàng đã xây dựng ở giai đoạn 1. Ý tưởng của thủ tục này
là giữ lại một số cặp đỉnh đã được dóng hàng tốt trước đó làm tập
hạt giống, sau đó tiếp tục dóng hàng lại cho các đỉnh còn lại. Nếu
lời giải mới cho chất lượng tốt hơn sẽ cập nhật lại lời giải tốt nhất
theo lời giải này.
Việc sử dụng chiến lược tham lam để xây dựng thuật toán nên thời gian
chạy thuật toán nhanh, do đó thuật toán này được đặt tên là FASTAN. Chi tiết
hơn về thuật toán sẽ được trình bày trong các phần dưới đây.
Để dễ theo dõi các thuật toán đã đề xuất, hệ thống các ký hiệu và cách
trình bày các thuật toán trong luận án có một số thay đổi nhỏ so với cách trình
bày trong các bài báo.
Thuật toán FASTAN gồm hai giai đoạn: giai đoạn thứ nhất xây dựng
dóng hàng ban đầu và giai đoạn sau cải tiến nó nhờ thủ tục tối ưu cục bộ
Rebuild.
3.2.1. Xây dựng dóng hàng ban đầu
Cho các đồ thị G1, G2; tham số α và các độ tương tự của các cặp đỉnh
85
của đồ thị Gi. Gọi A12= (V12, E12) là kết quả của phép dóng hàng đồ thị G1 với
đồ thị G2, trong đó:
;
.
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
∗ là các cạnh của đồ thị G1 có các đỉnh thuộc tập
đạt giá trị lớn (1 − 𝛼)(∑ 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢)) + 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑖, 𝑗))
nhất. Trong đó 𝐸1 𝑉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.
86
Thuật toán 3.1: Thuật toán FASTAN Input: Cặp đồ thị: 𝐺1 = (𝑉1, 𝐸1); 𝐺2 = (𝑉2, 𝐸2); Độ tương đồng giữa các cặp đỉnh 𝑠𝑖𝑚𝑖𝑙𝑎𝑟; Hệ số α
Output: Dóng hàng mạng 𝐴12 = (𝑉12, 𝐸12) begin Xác định cặp đỉnh (i,j) có độ tương đồng similar(i,j) lớn nhất;
f(i)=j; V1= {i};V2= {j}; for 𝑘=2 to|𝑉1|do
𝑖 = find_next_node(𝐺1); 𝑓(𝑖) = choose_best_matched_node(𝑖, 𝐺1, 𝐺2); V1=V1{i}; V2=V2{j};
end for; Rebuild(𝐴12); end;
Sau khi xây dựng được dóng hàng ban đầu FASTAN chuyển sang giai
đoạn 2. Trong giai đoạn này, thủ tục Rebuild được thực hiện lặp để cải tiến
dóng hàng đã có.
3.2.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 rebuild như dưới đây.
Với 𝐴12 đã được xây dựng trong giai đoạn 1 và số 𝑛𝑘𝑒𝑒𝑝 cho trước, thủ
tục này được đặc tả trong thuật toán 3.2 và thực hiện như sau:
87
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 4.5:
(3.5) 𝑠𝑐𝑜𝑟𝑒(𝑢) = 𝛼. 𝑤(𝑢) + (1 − 𝛼). 𝑠𝑖𝑚𝑖𝑙𝑎𝑟(𝑢, 𝑓(𝑢)),
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á trình này lặp lại cho đến khi không cải tiến được
GNAS(A12) nữa.
Thuật toán 3.2: Thủ tục Rebuild
Input: Dóng hàng 𝐴12; tham số 𝑛𝑘𝑒𝑒𝑝 Output: Dóng hàng 𝐴12 = (𝑉12, 𝐸12) mới tốt hơn Begin
Giữ lại nkeep cặp đỉnh (i,f(i))đã được dóng hàng tốt trong V12 Giữ lại nkeep đỉnh đã dóng hàng tương ứng trong tập V1 và V2
for 𝑘=𝑛𝑘𝑒𝑒𝑝+1 to|𝑉1|do
𝑖 = find_next_node(𝐺1); 𝑓(𝑖) = choose_best_matched_node(𝑖, 𝐺1, 𝐺2); V1=V1{i}; V2=V2{j};
end for; End;
3.2.3. Độ phức tạp của thuật toán FASTAN so với SPINAL
Trong nghiên cứu của Aladag và Erten [Aladag & Erten, 2013], bài toán
dóng hàng toàn cục mạng tương tác protein đã được chứng minh là NP-khó.
Các tác giả cũng đã đề xuất thuật toán SPINAL có độ phức tạp với thời gian đa
thức là:
88
(3.6) ,
trong đó k là số lần lặp chính khi chạy thuật toán, theo [Aladag & Erten,
2013] thuật toán sẽ hội tụ sau 10 đến 15 lần lặp; ∆1, ∆2 lần lượt là bậc của đỉnh
thuộc các đồ thị G1 và G2 có bậc lớn nhất.
Dễ dàng kiểm tra được độ phức tạp của giai đoạn 1 và mỗi bước lặp trong
giai đoạn 2 của thuật toán FASTAN là:
(3.7) O(|V1|.(E1|+|E2|)).
Các thực nghiệm được tiến hành với các bộ dữ liệu thực nghiệm IsoBase
cho thấy số lần lặp của giai đoạn 2 của thuật toán không vượt quá 20 lần.
Bởi vì |V1|.∆1 ≥ E1 nên chú ý tới độ phức tạp của SPINAL trong công
thức (3.6) ta có:
(3.8) |V1|.|V2|.∆1.∆2 ≥ E1. E2 > (|V1|.(E1|+|E2|)).
Như vậy độ phức tạp của FastAn so với độ phức tạp của SPINAL thấp
hơn nhiều.
3.3. Thuật toán ACOGNA
Mục 3.2 chúng tôi đã giới thiệu thuật toán FASTAN cho bài toán dóng
hàng toàn cục hai mạng tương tác protein-protein. Ưu điểm của thuật toán
FASTAN là thời gian chạy nhanh và chất lượng lời giải tốt hơn so với các thuật
toán trước đó tối ưu theo tiêu chuẩn GNAS. Tuy nhiên vì thuật toán FASTAN
theo hướng tiếp cận heuristic nên chất lượng lời giải cải thiện không đáng kể
khi tăng thời gian chạy thuật toán. Để cải thiện chất lượng lời giải hiệu quả hơn,
thuật toán mới đề xuất cần khai thác tốt thông tin heuristic kết hợp với thông
tin học tăng cường trong quá trình xây dựng các dóng hàng.
Trong chương 1, chúng tôi đã giới thiệu về thuật toán tối ưu đàn kiến và
89
đã phân tích các ưu điểm của thuật toán này khi giải quyết các bài toán tối ưu
tổ hợp, vì vậy trong phần này chúng tôi sẽ giới thiệu thuật toán mới áp dụng
phương pháp ACO để giải bài toán dóng hàng mạng tương tác protein-protein
gọi là thuật toán ACOGNA.
Ý tưởng của thuật toán mới là thay vì sử dụng chiến lược tham lam như
FASTAN sẽ dẫn tới các lời giải tối ưu cục bộ, thuật toán mới sử dụng phương
pháp ACO để xây dựng các dóng hàng. Ưu điểm khi áp dụng phương pháp
ACO là có thể sử dụng chiến lược tham lam của FASTAN làm thông tin
heuristic cho thuật toán mới và thông qua việc cập nhật thông tin vết mùi qua
các vòng lặp sẽ khai thác tốt thông tin học tăng cường. Với đặc điểm đó, thuật
toán mới sẽ cho chất lượng lời giải tốt hơn khi tăng thời gian chạy thuật toán.
Các kết quả thực nghiệm được trình bày ở mục 3.5.3 đã cho thấy thuật
toán ACOGNA cho chất lượng lời giải tốt hơn so với thuật toán FASTAN và
Spinal.
90
3.3.1. Lược đồ chung
có toán ACOGNA liệu vào các đồ là
Thuật thị dữ 𝐺1 = (𝑉1, 𝐸1); 𝐺2 = (𝑉2, 𝐸2); độ tương đồng giữa các cặp đỉnh: 𝑠𝑖𝑚𝑖𝑙𝑎𝑟 và tham số cân bằng α. Để tìm dóng hàng mạng 𝐴12 = (𝑉12, 𝐸12) thuật toán được xây dựng như dưới đây: Bước 1. Khởi tạo ma trận vết mùi, và tập A gồm m kiến.
Bước 2. Thực hiện lặp trong khi chưa thoả mãn điều kiện dừng
Với mỗi kiến ta tiến hành các bước sau:
2.1. Gán f(i)=j trong đó i, j là cặp đỉnh có độ tương đồng similar (i,j) lớn
nhất. Khởi tạo V1 = {i}; V2 = {j};
2.2 Thực hiện lặp với k= 2 tới
2.2.1. Tìm đỉnh có số cạnh tới các đỉnh trong lớn nhất;
theo thủ tục
2.2.2. Sử dụng thuật toán ACO tìm đỉnh f(i)= bước ngẫu nhiên (thủ tục antMove) 2.2.3. Lần lượt thêm 2 đỉnh i và j vào các tập đỉnh V1 và V2
2.3. Thực hiện tìm kiếm cục bộ trên lời giải tốt nhất do các kiến tìm được
để cải thiện chất lượng lời giải.
2.4. Cập nhật lại lời giải tốt nhất.
2.5. Cập nhật vết mùi theo quy tắc SMMAS dựa trên lời giải tốt nhất.
Bước 3. Lưu lại lời giải tốt nhất.
Chú ý rằng ở bước 2.2.1, việc tìm có số cạnh tới các đỉnh trong
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.
91
Thuật toán 3.3: Thuật toán ACOGNA
Input: Đồ thị 1: 𝐺1 = (𝑉1, 𝐸1); Đồ thị 2: 𝐺2 = (𝑉2, 𝐸2); Độ tương đồng giữa các cặp đỉnh: 𝑠𝑖𝑚𝑖𝑙𝑎𝑟 Tham số cân bằng α
Output: Dóng hàng mạng 𝐴12 = (𝑉12, 𝐸12) Begin
Khởi tạo; // Khởi tạo ma trận vết mùi và m kiến (A); while (Chưa thỏa mãn điều kiện dừng) do
là cặp đỉnh có độ tương tự similar(i,j) lớn nhất.
for each kiến a A do // V1 = {i}; V2 = {j};
for 𝑘=2 to|𝑉1|do
𝑖 = find_next_node(𝐺1);
V1 = V1{i}; V2 = V2{j};
end for;
end for; Tìm kiếm cục bộ;Cập nhật lời giải tốt nhất; Cập nhật vết mùi theo quy tắc SMMAS;
end while;
Ghi lại lời giải tốt nhất;
End;
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ị . 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 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).
92
Hình 3.1. Đồ thị cấu trúc của thuật toán ACOGNA
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 dóng với 1 đỉnh của sau đó quay lại rồi tiếp tục
dóng với 1 đỉnh của , lặp lại cho tới khi tất cả các đỉnh của đã được dóng
hàng.
𝑖 trên cạnh
3.3.3. Vết mùi và thông tin heuristic
dóng đỉnh với đỉnh được khởi tạo Vết mùi 𝜏𝑗
𝑖 được tính theo công thức 3.9.
bằng 𝜏𝑚𝑎𝑥 và sau đó được cập nhật lại sau mỗi vòng lặp theo công thức 3.11
Thông tin heuristic 𝜂𝑗
, (3.9)
trong đó là số cạnh được bảo tồn nếu tiếp tục dóng hàng đỉnh j với đỉnh i,
α là hằng số thể hiện mối tương quan giữa độ tương đồng về cấu trúc và tính
tương đồng về trình tự, là độ tương đồng giữa 2 đỉnh i và j.
Việc tính toán thông tin heuristic như công thức 3.9 là do mục tiêu của
bài toán dóng hàng toàn cục hai mạng tương tác protein cần bảo tồn tối đa số
tương tác protein khi dóng hàng một mạng PPI nguồn vào một mạng PPI đích.
Ngoài ra thông tin về sự tương đồng trình tự giữa 2 protein được dóng hàng
cũng được thể hiện qua độ tương tự similar(i,j).
93
3.3.4. Thủ tục bước ngẫu nhiên để xây dựng dóng hàng
Tại mỗi vòng lặp, sau khi chọn một đỉnh
find_next_node tương tự thuật toán FASTAN, kiến chọn đỉnh bằng thủ tục theo
xác suất được cho bởi công thức 3.10
. (3.10)
Sau khi lựa chọn được đỉnh để dóng với , kiến quay lại lựa
chọn đỉnh tiếp theo của đồ thị G1 để tiếp tục dóng hàng. Quá trình lặp lại cho
đến khi tất cả các đỉnh của G1 được dóng hàng với các đỉnh của G2.
3.3.5. Quy tắc cập nhật vết mùi
Sau khi tất cả các kiến đã xây dựng lời giải, lời giải của kiến tốt nhất được
áp dụng thủ tục tìm kiếm cục bộ để tăng chất lượng lời giải. Lời giải tốt nhất
này được sử dụng để cập nhật vết mùi trên các cạnh theo quy tắc cập nhật mùi
SMMAS [Hoang Xuan Huan et al., 2013], như dưới đây:
, (3.11)
, (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á.
94
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.
95
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
𝑖 đặt trên các đỉnh của đồ thị G1 để xác định các đỉnh thuộc đồ
mùi.
Vết mùi 𝜏1
𝑖 đặt trên cạnh (i,j) của đồ thị cấu trúc, dùng để xác định đỉnh
thị nguồn sẽ được ưu tiên lựa chọn để dóng hàng.
. Các vết mùi được khởi tạo bằng giá trị Vết mùi 𝜏𝑗 được dóng hàng với đỉnh
𝜏𝑚𝑎𝑥 và được cập nhật lại sau mỗi vòng lặp.
96
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 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.
và có nhiều cạnh nối với các Gọi tập T chứa các đỉnh 𝑖 sao cho
đỉnh của nhất. Khi đó, đỉnh 𝑖 ∈ 𝑇 được chọn ngẫu nhiên theo xác suất:
, (3.13)
𝑖 𝑖 là vết mùi 𝜏1
trong đó 𝜂𝑖 là số lượng đỉnh kề của trong đồ thị 𝐺1, 𝜏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 đỉnh được các kiến lựa chọn theo
xác suất cho bởi công thức 3.14.
.
(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
97
𝑖 lần lượt được tính theo các công thức 3.15 hoặc 3.16.
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 𝜂𝑗
, (3.15)
.
(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)
.
(3.19)
(3.20)
98
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ỉ http://isobase.csail.mit.edu/
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).
99
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
100
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.
101
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 .
α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 Datasets
FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL FASTAN SPINAL
717.99 941.19 1159.93 1350.59 1586.87 778.46 1034.20 1290.11 1545.86 1801.24 ce-dm 2343.0 2320.0 2300.0 2237.0 2258.0 2560.7 2564.6 2567.2 2567.7 2567.6
728.26 993.07 1229.95 1501.61 1764.93 863.46 1144.17 1429.89 1708.81 1994.87 ce-hs 2370.0 2446.0 2437.0 2487.0 2512.0 2842.8 2838.1 2844.9 2838.0 2843.4
709.12 963.28 1168.95 1422.74 1683.13 834.79 1109.93 1389.21 1663.39 1936.83 ce-sc 2326.0 2384.0 2323.0 2361.0 2398.0 2761.1 2761.2 2769.7 2766.5 2763.1
1883.22 2517.23 3160.48 3790.79 4451.6 2260.31 3007.11 3755.36 4496.45 5242.32 dm-hs 6189.0 6235.0 6282.0 6291.0 6344.0 7478.3 7481.9 7429.0 7478.2 7478.8
1579.06 2075.14 2668.65 3180.27 3759.07 1977.82 2631.85 3290.03 3950.16 4603.41 dm-sc 5203.0 5150.0 5311.0 5283.0 5360.0 6569.7 6565.5 6570.7 6577.4 6572.3
1731.81 2253.66 2839.00 3434.54 4066.22 2268.21 3017.96 3772.96 4520.51 5279.88 hs-sc 5703.0 5593.0 5651.0 5706.0 5798.0 7531.8 7528.5 7535.2 7527.0 7538.1
.
102
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
. Vì vậy các kết quả được tham số max được khởi tạo bằng 1 và
103
trình bày ở đây tương ứng với giá trị nbest=1%, , 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.
104
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.
α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 Datasets
FASTAN ACOGNA FASTAN ACOGNA FASTAN ACOGNA FASTAN ACOGNA FASTAN ACOGNA
ce-dm 778.46 2560.7 1109.92 2564.6 1290.11 2567.2 1545.86 2567.7 1801.24 2567.6 833.14 2749.2 1109.92 2758.2 1368.35 2726.10 1641.35 2728.3 1930.84 2753.7
ce-hs 863.46 2842.8 1144.17 2838.1 1429.89 2844.9 1708.81 2838.0 1994.87 2843.4 913.39 3015.3 1207.94 3001.1 1513.4 3014.2 1824.69 3033.0 2091.43 2982.6
ce-sc 834.79 2761.1 1109.93 2761.2 1389.21 2769.7 1663.39 2766.5 1936.83 2763.1 876.78 2902.9 1178.46 2934.8 1457.65 2907.9 1742.2 2898.3 2064.12 2945
dm-hs 2260.31 7478.3 3007.11 7481.9 3755.36 7429.0 4496.45 7478.2 5242.32 7478.8 3226.76 8038.7 4039.68 8060.1 4828.29 8034.29 5648.18 8060.9 2431.59 8058.4
dm-sc 1977.82 6569.7 2631.85 6565.5 3290.03 6570.7 3950.16 6577.4 4603.41 6572.3 2108.13 7008.7 2811.97 7019.2 3518.87 7030.2 4203.53 7000.90 4908.90 7009.6
hs-sc 2268.21 7531.8 3017.96 7528.5 3772.96 7535.2 4520.51 7527 5279.88 7538.1 2429.12 8072.9 3256.54 8182.8 3938.3 7666.0 4895.45 8153.4 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|.
105
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
0.6116 0.6136 0.6065 0.6070 0.6126 0.5217 0.0700 0.2983
0.6708 0.6677 0.6706 0.6747 0.6635 0.3061 0.1288 0.3065
ce-dm
0.6458 0.6529 0.6469 0.6448 0.6553 0.6002 0.1449 0.2901
ce-hs
ce-sc
0.3144 0.3136 0.3144 0.3159 0.3138 0.1921 0.0885 0.1464
0.2242 0.2245 0.2249 0.2239 0.2240 0.1575 0.0569 0.1357
dm-hs
0.2582 0.2600 0.2608 0.2608 0.2601 0.1680 0.0390 0.1439
dm-sc
hs-sc
106
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
ACOGNA MAGNA++ Datasets
α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7 EC
0.1344 0.1123 0.1068 0.1338 0.1061 0.1580 0.0700 0.2597
ICS S3
0.1265 0.0993 0.0953 0.0939 0.0909 0.2621 0.1284 0.2639
ce-dm
0.1063 0.0953 0.0925 0.0911 0.0922 0.1198 0.1446 0.2573
ce-hs
0.156 0.1567 0.1555 0.0988 0.0785 0.1088
ce-sc
0.1593 0.1559
dm-hs
0.1446 0.1417 0.1415 0.1407 0.1406 0.1030 0.0554 0.1081
dm-sc
0.1501 0.1452 0.1484 0.1446 0.1433 0.1043 0.0387 0.1166
hs-sc
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
107
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à
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.
108
Bảng 3.7. So sánh các thuật toán theo tiêu chuẩn S3
ACOGNA MAGNA++ ModuleAlign ACOGNA++ Datasets α = 0.3 α = 0.4 α = 0.5 α = 0.6 α = 0.7
0.1344 0.1123 0.1068 0.1338 0.1061 0.2597 0.1538 ce-dm 0.3655
0.1265 0.0993 0.0953 0.0939 0.0909 0.2639 0.1354 ce-hs 0.4165
0.1063 0.0953 0.0925 0.0911 0.0922 0.2573 0.1192 ce-sc 0.2795
0.1593 0.1559 0.156 0.1567 0.1555 0.1088 0.1117 dm-hs 0.1910
0.1446 0.1417 0.1415 0.1407 0.1406 0.1081 0.1059 sc-dm 0.1767
0.1501 0.1452 0.1484 0.1446 0.1433 0.1166 0.1174 sc-hs 0.2096
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.
109
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à
30000
25000
20000
) s (
15000
n a i g
MAGNA++
ACOGNA++
10000
i ờ h T
5000
0
ce-dm ce-hs
sc-dm dm-hs
sc-hs
ce-sc Bộ dữ liệu
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
110
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
111
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].
112
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 đó. 113
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
114
đồ 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
115
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].
116
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 for International Conference on Advanced Technologies Communications, pp. 181-186. (Scopus)
interaction networks”, Proceedings of
Technologies Advanced on
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 the 2015 protein-protein for International Conference Communications, pp. 332-336. (Scopus)
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.
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.
117
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.
118
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.
119
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).
120
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.
121
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
122
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.
123
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.
124
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.
125
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.
126
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.
127
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.
128
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.
129
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.
130
