MỞ ĐẦU Tin sinh học là một lĩnh vực khoa học mới rất đƣợc quan tâm trong hơn thập kỷ gần đây, với sự phát triển của khoa học công nghệ, mối liên kết giữa sinh học và tin học trở lên khăng khít hơn, Tin học hỗ trợ cho việc giải quyết các bài toán với dữ liệu lớn của Sinh học, đồng thời đó cũng là một hƣớng phát triển mới của ngành Tin học về giải thuật và ứng dụng. Dóng hàng hai đồ thị là một bài toán quan trọng trong lý thuyết đồ thị, nó giúp chúng ta xác định tính tƣơng đồng của hai đồ thị. Về mặt sinh học nó giúp xác định tính tƣơng đồng giữa các mạng tƣơng tác protein.Hiện nay có nhiều tiêu chí về cách đánh giá cho dóng hàng. Một cách đánh giá thƣờng đƣợc sử dụng hiện nay là đánh giá dựa trên lực lƣợng của tập cạnh (sự tƣơng đồng về cấu trúc) và sự tƣơng đồng giữa các nút.
Dóng hàng hai đồ thị đƣợc Aladag và Erten chứng minh là bài toán thuộc lớp NP-khó [4] và có nhiều ứng dụng. Đặc biệt, trong những năm gần đây, với sự phát triển của các kỹ thuật sinh học công nghệ cao đã cho phép các nhà nghiên cứu xây dựng đƣợc các mạng tƣơng tác protein (Protein-Protein Interraction Network – PPI Network) tƣơng đối đầy đủ cho nhiều loài sinh vật. Bài toán dóng hàng mạng PPI là một bài toán quan trọng trong phân tích mạng PPI nói chung.Các mạng tương tác protein được mô tả bằng đồ thị, bài toán dóng hàng mạng được chuyển tải về bài toán dóng hàng đồ thị. Phƣơng pháp tố i ƣu đàn kiế n (Ant Colony Optimization - ACO) là cách tiế p câ ̣n metaheuristic , đƣơ ̣c giới thiê ̣u bởi Dorigo năm 1991 đang đƣợc nghiên cứu và ứng dụng rộng rãi cho các bài toán tối ƣu tổ hợp khó.
Chính vì vậy tác giả chọn đề tài khoa học phương pháp tối ưu đàn kiến dóng hàng hai đồ thị. Thực nghiệm, tác giả sẽ sử dụng bộ dữ liệu vào Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 2 (Input) mà Spinal và FastNA đã dùng, từ đó sẽ đánh giá và so sánh kết quả ra để thấy đƣợc hiệu quả của phƣơng pháp tác giả đề xuất với những phƣơng pháp có trƣớc, cụ thể là so sánh với hai phƣơng pháp tốt nhất hiện nay Spinal và FastNA. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 3 CHƢƠNG I DÓNG HÀNG HAI ĐỒ THỊ VÀ CÁC PHƢƠNG PHÁP TIẾP CẬN HIỆN NAY 1. Bài toán dóng hàng hai đồ thị Giả sử 𝐺1 = (𝑉1 , 𝐸1 ) và 𝐺2 = (𝑉2 , 𝐸2 ) là hai mạng tƣơng tác protein (đơn đồ thị), trong đó 𝑉1 , 𝑉2 ký hiệu tập các nút mô tả các protein trong mạng 𝐺1 , 𝐺2 tƣơng ứng;𝐸1 , 𝐸2 ký hiệu tập các cạnh mô tả mối quan hệ tƣơng tác giữa các protein trong các mạng 𝐺1 , 𝐺2.
Không giảm tổng quát, ta xem 𝑉1 ≤ 𝑉2 trong đó 𝑉 ký hiệu số phần tử của tập 𝑉. Dóng hàng mạng là tìm một đơn ánh từ 𝑉1 vào 𝑉2 tốt nhất theo một tiêu chí đánh giá nào đó. Hiện nay chƣa có định nghĩa rõ ràng cho tiêu chí này, dƣới đây phát biểu toán học cho định nghĩa bài toán dóng hàng theo tiêu chí thông dụng đã đƣợc dùng trong [4,5,6,12,27]. (Dóng hàng mạng) Đồ thị 𝐴12 = (𝑉12 , 𝐸12 ) là một mạng dóng hàng của hai đồ thị𝐺1 , 𝐺2 nếu nó thỏa mãn: i) Mỗi nút của 𝑉12 đƣợc ký hiệu là < 𝑢𝑖 , 𝑣𝑗 > tƣơng ứng với một cặp đỉnh 𝑢𝑖 thuộc 𝑉1 và 𝑣𝑗 thuộc 𝑉2.
ii) Hai nút phân biệt< 𝑢𝑖 , 𝑣𝑗 > và < 𝑢𝑖′ , 𝑣𝑗′ > thuộc 𝑉12 thì𝑢𝑖 ≠ 𝑢𝑖′ và 𝑣𝑗 ≠ 𝑣𝑗′ iii) Cạnh(< 𝑢𝑖 , 𝑣𝑗 >, < 𝑢𝑖′ , 𝑣𝑗′ >) thuộc 𝐸12 nếu và chỉ nếu (𝑢𝑖 , 𝑢𝑖′ ) ∈ 𝐸1 và (𝑣𝑖 , 𝑣𝑖′ ) ∈ 𝐸2. (Dóng hàng mạng toàn cục) Một dóng hàng 𝐴12 = (𝑉12 , 𝐸12 ) là lời giải của bài toán dóng hàng toàn cục của các mạng proteins 𝐺1 , 𝐺2 nếu nó cực đại global network alignment score cho bởi Eq(1.1) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 trong đó ∈ [0,1] là tham số cân bằng giữa sự tƣơng đồng về tô pô mạng và sự tƣơng đồng trình tự giữa các nút, giá trị 𝑆𝑖𝑚𝑖𝑙𝑎𝑟 𝑢𝑖 , 𝑣𝑗 đƣợc tính xấp xỉ dựa trên BLAST bit-scores hoặc E-values. Trong [4] Aladag và Erten đã chứng minh bài toán tìm dóng hàng tối ƣu này là NP-hard. Một số phƣơng pháp tiếp cận hiện nay Từ khi bài toán đƣợc đề xuất, các kỹ thuật dóng hàng mạng PPI phát triển theo hai hƣớng: dóng hàng cục bộ và dóng hàng toàn cục.
Với dóng hàng cục bộ, mục tiêu sẽ là xác định các mạng con gần nhau về tô pô mạng hoặc tƣơng tự xâu [11,23,27]. Thông thƣờng, kết quả của dóng hàng cục bộ sẽ thể hiện nhiều mạng con chồng lấn nhau, điều này có thể dẫn đến sự nhập nhằng khi một protein có thể đƣợc dóng hàng với nhiều protein khác. Để khắc phục nhƣợc điểm đó dóng hàng mạng toàn cục sẽ tìm ra một đơn ánh mà mỗi protein của mạng PPI này chỉ dóng với một protein ở mạng PPI kia. IsoRank [4,28] đƣợc Sing et al.
đề xuất năm 2008 là một trong những thuật toán dóng hàng mạng toàn cục đầu tiên, nó đƣợc phát triển dựa trên dóng hàng cục bộ. Ý 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úngtƣơng ứng đƣợc dóng hàng.Thuật toán bao gồm hai giai đoạn chính, thứ nhất thực hiện với mỗi nút i (𝑖 ∈ 𝑉1 | 𝑖 = 1. |𝑉1 |) phải duyệt tất cả nút j (𝑗 ∈ 𝑉2 | 𝑗 = 1. |𝑉2 |) để tìmđiểm sốdóng hàng Ri,j cho từng cặp nút i và j, theo 1 Ri , j | N (u) | .2) uN ( i ) vN ( j ) ở công thức trênN(x) là tập tất cả các nút láng riềng của x.
Kết quả của giai đoạn này cho ta một ma trận giá trị (điểm số dóng hàng)R tƣơng ứng với mọi cặp nút<i,j> (𝑖 ∈ 𝑉1 ,𝑗 ∈ 𝑉2 ).Giai đoạn thứ hai, từ ma trận R tìm ra một cách sắp xếp (ghép) từng cặp i,j (𝑖 ∈ 𝑉1 ,𝑗 ∈ 𝑉2 ) sao cho tổng điểm số dóng hàng là Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 tốt nhất.Việc này đƣợc cho là đơn giản vì nó chỉ là cách sắp xếp hai đồ thị dựa trên mức độ tƣơng tự giữa các nút. Sau IsoRank, một số thuật toán tƣơng tự đã đƣợc đề xuất nhƣ PATH và GA [35], PISwap [6,7] nhờ đƣa thêm các nới lỏng thích hợp của hàm đánh giá trên tập các ma trận ngẫu nhiên hoặc ứng dụng tìm kiếm cục bộ trên dóng hàng lời giải có sẵn từ một thuật toán khác. Các thuật toán này đều đƣa ra kết quả nhanh và tốt hơn so với các thuật toán trƣớc đó. Tuy nhiên, những thuật toán đã nêu chỉ tối ƣu cho độ chính xác (hàm mục tiêu) hoặc tính khả mở (scalability ).
Vì các mạng PPI có thƣờng 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. Gần đây, đã xuất hiện những thuật cho kết quả tốt với độ phức tạp thời gian đa thức điển hình là SPINAL và FastNA sẽ đƣợc giới thiệu và tìm hiểunhiều hơn. SPINAL Năm 2013 Aladag và Erten đề xuất thuật toán SPINAL [4], thuật toán này cho kết quả tốt nhất theo tiêu chí đánh giá của công thức (1.1) và nhanh nhất tính đến thời điểm nó ra đời. SPINAL là một thuật toán heuristic thời gian đa thức, gồm hai pha: Pha đầu tính điểm tƣơng đồng cho tất cả cặp protein theo công thức P ( xi , y j ) deg ( x ) deg ( y ) ( xi , y j )C T( ui ,v j ) (1 ) seq (ui , v j ) G1 i G2 j (1.3) C trong đó∈ [0,1] là tham số cân bằng giữa sự tƣơng đồng về tô pô mạng và sự tƣơng đồng trình tự giữa các nút, degG ( xi ) , deg G ( y j ) tƣơng ứng là 1 2 bậc của xi và yj trong G1 và G2,và seg(ui,vj) đƣợc tính xấp xỉ dựa trên BLAST bit-scores hoặc E-values.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 6 Pha sau xây dựng đơn ánh xạ bằng cách cải tiến một cách cục bộ từng tập con của lời giải hiện có. Algorithm 1:SPINAL global alignment algorithm 1: Input: G1 (V1 , E1 ), G2 (V2 , E2 ), seg , 2: Output: Node set V12 of the global alignment network A12 3: // Coarse-grained 4: for all ui V1 , v j V2 do 5: P(ui , v j ) DegDiff (ui , v j ) (1 ) seg (ui , v j ) 6: endfor 7: repeat 8: P ' P 9: for all ui V1 , v j V2 do 10: construct NBG({ u i , v j }, P ') 11: construct contributors set C of NBG 12: comput P (ui , v j ) as in Equation(2) 13:endfor 14:until enough iterations 15:// Fine-grained 16: SP List of ui , v j sorted w.t P, for u i V1 , v j V2 17:repeat 18: // Find new connected component in A12 19: pop unaligned ui , v j from SP, insert into V12 20:repeat 21: Construct NBG(V12 , P) 22: Construct contributors set C of NBG 23: Swap improvements for each NBG edge not in C 24: Insert xi , y j into V12, for each ( xi , y j ) C 25:until no contributors 26:until no unaligned pair in SP Hình 1.1: Thuật toán SPINAL Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.4) trong đó k là số lần chạy của vòng lặp chính (thuật toán hội tụ với số vòng lặp từ 10-15 trong các trƣờng hợp thử nghiệm), ∆1, ∆2 lần lƣợt là bậc lớn nhất của đỉnh trong đồ thị G1, G2 Thực nghiệm trên các tập dữ liệu Saccharomyces cerevisiae, Drosophila melanogaster, Caenorhabditis elegans and Homo sapiens cho thấy SPINAL tốt hơn hai thuật toán IsoRank và MI-GRAAL, là hai thuật toán tốt nhất đến lúc đó. FastNA Năm 2013, Tiến sĩ Đỗ Đức Đông và một số đồng nghiệp thuộc Viện Công nghệ thông tin, Đại học Quốc giađã đề xuất một thuật toán mới là FastNA đểdóng hàng toàn cục mạng PPI.