Tổng quan luận án

Luận án tiến sĩ với đề tài "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), được thực hiện tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội dưới sự hướng dẫn khoa học của PGS.TS. Hoàng Xuân Huấn và GS.TS. Thái Trà My (bảo vệ năm 2019).

Tính cấp thiết và khoảng trống nghiên cứu

Trong sinh học phân tử và tin sinh học, việc phân tích tính tương đồng hoặc dị biệt cấu trúc tuần tự của các chuỗi DNA và protein không đủ để giải thích đầy đủ các đặc tính chức năng cũng như cơ chế hoạt động phức tạp trong tế bào sống. Các phân tử sinh học thường thực hiện chức năng thông qua tương tác phối hợp, được mô hình hóa dưới dạng các mạng sinh học như mạng vị trí liên kết protein và mạng tương tác protein - protein (PPI). Việc dóng hàng các mạng này cho phép chuyển giao tri thức về chức năng tế bào từ các sinh vật mô hình đã được nghiên cứu kỹ sang các loài chưa được khảo sát đầy đủ hoặc khó tiến hành thực nghiệm trên người do rào cản đạo đức.

Về mặt tính toán, bài toán dóng hàng nhiều mạng các vị trí liên kết protein (Multigraph Alignment - MGA) và bài toán dóng hàng toàn cục mạng tương tác protein - protein (Global Network Alignment - GNA) đều thuộc lớp bài toán tối ưu tổ hợp NP-khó. Các thuật toán heuristic cổ điển (như thuật toán Greedy) thường chỉ tìm được lời giải chấp nhận được trên các bài toán quy mô nhỏ và suy giảm chất lượng rõ rệt khi kích thước dữ liệu tăng. Ngược lại, các phương pháp tiến hóa truyền thống (như thuật toán di truyền GAVEO) gặp hạn chế do tốc độ hội tụ chậm, sử dụng lặp lại nhiều lời giải cũ và chưa khai thác triệt để các thông tin heuristic định hướng tìm kiếm. Do đó, yêu cầu đặt ra là cần xây dựng các thuật toán tối ưu tổ hợp mềm có khả năng cân bằng giữa chất lượng dóng hàng và thời gian tính toán.

Mục tiêu và nhiệm vụ nghiên cứu

Mục tiêu chính của luận án là nghiên cứu ứng dụng các kỹ thuật tối ưu tổ hợp mềm (đặc biệt là tối ưu đàn kiến, giải thuật memetic và tìm kiếm Tabu) để đề xuất các thuật toán 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, nhằm nâng cao chất lượng hàm mục tiêu và rút ngắn thời gian xử lý so với các thuật toán đã công bố.

Các nhiệm vụ cụ thể được xác định trong văn bản gồm:

  1. Tìm hiểu các dạng bài toán dóng hàng mạng protein và đánh giá ưu nhược điểm của các thuật toán giải đã được đề xuất; khảo sát các kỹ thuật tính toán mềm để làm 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 có chất lượng lời giải tốt hơn trong thời gian ngắn hơn.
  2. Cài đặt và thực nghiệm các thuật toán đề xuất trên các bộ dữ liệu mô phỏng và dữ liệu sinh học thực tế để đánh giá hiệu quả so với các thuật toán đối sánh.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các bài toán tối ưu tổ hợp dóng hàng đồ thị sinh học (dóng hàng nhiều đồ thị biểu diễn vị trí liên kết protein, dóng hàng toàn cục hai đồ thị tương tác protein - protein) và các phương pháp metaheuristic (tối ưu đàn kiến ACO, giải thuật memetic, tìm kiếm Tabu, kỹ thuật heuristic xây dựng và tái cấu trúc).
  • Phạm vi không gian và dữ liệu:
    • Mô hình túi liên kết protein trích xuất từ cơ sở dữ liệu Cavbase sử dụng thuật toán LIGSITE trên cấu trúc ngân hàng dữ liệu protein (Protein Data Bank - PDB), với ngưỡng khoảng cách không gian Ơclit giữa các tâm giả nhỏ hơn 12Å ($1\text{Å} = 10^{-10}\text{ m}$).
    • Dữ liệu mạng tương tác protein - protein chuẩn từ cơ sở dữ liệu IsoBase cho bốn loài sinh vật: nấm men (Saccharomyces cerevisiae - SC), ruồi giấm (Drosophila melanogaster - DM), người tinh khôn (Homo sapiens - HS) và giun tròn (Caenorhabditis elegans - CE).
    • Dữ liệu tổng hợp gồm các tập 4, 8, 16 và 32 đồ thị với số đỉnh trung bình mỗi đồ thị là 20 và 50 đỉnh.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu liên quan trong tài liệu

Văn bản luận án đã điểm lại các công trình nền tảng và các hướng tiếp cận chính trong phân tích chuỗi, cấu trúc protein và mạng sinh học:

  1. Phân tích chuỗi và cấu trúc phân tử:

    • Các công trình về so sánh trình tự và dóng hàng chuỗi sinh học: Altschul và cộng sự (1990, 1997), Edgar (2004), Thompson, Higgins & Gibson (1994), Notredame, Higgins & Heringa (2000), Sjolander (2004).
    • Nghiên cứu về mối liên hệ giữa độ tương đồng chuỗi và chức năng: Todd, Orengo & Thornton (2001) chỉ ra các protein có độ giống nhau trên 40% chuỗi amino acid thường có chức năng tương tự.
    • Các mô hình tối ưu tổ hợp xử lý dữ liệu chuỗi, tìm kiếm DNA motif và xây dựng cây phân loài: Lê Sỹ Vinh (2014), Hoang X. Huan và cộng sự (2015).

  2. Mô hình hóa và dóng hàng vị trí liên kết protein (MGA):

    • Trích xuất khoang liên kết protein bằng thuật toán LIGSITE: Hendlich, Rippmann & Barnickel (1997); cơ sở dữ liệu Cavbase: Schmitt, Kuhn & Klebe (2002); biểu diễn túi liên kết bằng đồ thị tâm giả: Hendlich và cộng sự (2003), Weskamp và cộng sự (2007).
    • Đề xuất bài toán dóng hàng nhiều đồ thị (MGA) và thuật toán heuristic Greedy: Weskamp và cộng sự (2007).
    • Giải thuật di truyền GAVEO cho bài toán MGA: Fober, Mernberger, Klebe & Hüllermeier (2009).

  3. Dóng hàng mạng tương tác protein - protein (PPI):

    • Dóng hàng cục bộ: Berg & Lassig (2004, 2006), Kelley và cộng sự (2004), Sharan và cộng sự (2005), Flannick và cộng sự (2006), Koyutürk và cộng sự (2006), Liang và cộng sự (2006), Ciriello và cộng sự (2012), Mina & Guzzi (2012), Pache & Aloy (2012). Đánh giá thông qua bản thể gen (Gene Ontology): Ashburner và cộng sự (2000).
    • Dóng hàng toàn cục:
      • Thuật toán IsoRank: Singh, Xu & Berger (2007, 2008), kế thừa nguyên lý PageRank (Brin & Page, 1998).
      • Họ thuật toán GRAAL (GRAAL, H-GRAAL, MI-GRAAL, C-GRAAL): Kuchaiev, Milenković, Memišević, Hayes & Pržulj (2010, 2011), Memišević & Pržulj (2012).
      • Thuật toán GHOST: Patro & Kingsford (2012).
      • Thuật toán SPINAL: Aladag & Erten (2013).
      • Thuật toán MAGNA và MAGNA++: Saraph & Milenković (2014), Vijayan, Saraph & Milenković (2015).
      • Thuật toán ModuleAlign: Hashemifar, Ma, Naveed, Canzar & Xu (2016).
      • Các tổng quan và phân loại mạng sinh học: Guzzi & Milenković (2018), Junker & Schreiber (2008), Clark & Kalita (2014), Malod-Dognin & Pržulj (2014).

Khoảng trống luận án lựa chọn giải quyết

  • Đối với bài toán MGA, thuật toán Greedy dễ rơi vào cực trị địa phương, còn GAVEO chậm hội tụ do không tích hợp được thông tin dẫn đường heuristic và cơ chế bộ nhớ học tăng cường.
  • Đối với bài toán dóng hàng toàn cục PPI, các thuật toán trước đó thường chỉ tập trung vào tối ưu độ chính xác cấu trúc hoặc thời gian thực thi đơn lẻ; các phương pháp tiếp cận di truyền (như MAGNA++) phụ thuộc nhiều vào chất lượng quần thể khởi tạo, trong khi các phương pháp dựa trên phân cụm (như ModuleAlign) chưa giải quyết đồng đều trên mọi độ đo bảo tồn tô pô mạng. Luận án lựa chọn giải quyết các hạn chế này thông qua việc xây dựng đồ thị cấu trúc tìm kiếm, tích hợp heuristic sinh học và quy tắc cập nhật mùi SMMAS kết hợp tìm kiếm cục bộ/tìm kiếm Tabu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và mô hình toán học

1. Bài toán tối ưu tổ hợp tổng quát

Một bài toán tối ưu tổ hợp (Combinatorial Optimization) được biểu diễn bằng bộ ba $(S, f, \Omega)$, trong đó $S$ là tập hữu hạn các trạng thái (phương án lời giải tiềm năng), $f: S \to \mathbb{R}$ là hàm mục tiêu cần tối ưu, và $\Omega$ là tập hợp các ràng buộc xác định không gian lời giải chấp nhận được. Không gian tìm kiếm được mô hình hóa thông qua việc mở rộng tuần tự các thành phần $C = {c_1, \dots, c_n}$ trên tập vectơ $X$ có độ dài không quá $h$.

2. Mô hình hóa vị trí liên kết protein

Túi liên kết protein được biểu diễn bằng đồ thị vô hướng có trọng số $G(V, E)$, trong đó:

  • Tập đỉnh $V$ là các tâm giả (pseudocenter) mang đặc trưng lý hóa không gian, nhận nhãn thuộc tập $L = {A, B, C, D, E, F, G}$ (tương ứng với các nhóm chức năng: donor, acceptor, mixed donor/acceptor, hydrophobic aliphatic, metal ion, pi...).
  • Cạnh $e = (u, v) \in E$ tồn tại khi khoảng cách Ơclit giữa hai tâm giả nhỏ hơn 12Å, trọng số $w(e)$ biểu diễn khoảng cách thực tế giữa chúng.
  • Các phép toán chỉnh sửa đồ thị gồm: (i) Chèn hoặc xóa một đỉnh (sử dụng đỉnh giả đại diện cho khoảng trống); (ii) Thay đổi nhãn đỉnh $l(v)$; (iii) Thay đổi trọng số cạnh $w(e)$.
  • Bài toán MGA tìm một dóng hàng đồng thời cho tập hợp $\mathcal{G} = {G_1(V_1, E_1), \dots, G_n(V_n, E_n)}$ nhằm tối ưu hàm đánh giá chất lượng dóng hàng $S(A)$.

3. Mô hình hóa dóng hàng toàn cục mạng PPI

Xét hai mạng PPI biểu diễn bởi hai đồ thị $G_1(V_1, E_1)$ và $G_2(V_2, E_2)$ với $|V_1| \le |V_2|$. Dóng hàng toàn cục là một đơn ánh $f: V_1 \to V_2$. Bài toán tìm ánh xạ $f$ nhằm tối đa hóa mức độ bảo tồn cấu trúc mạng và độ tương đồng sinh học giữa các cặp protein được ghép đôi.

+-------------------------------------------------------------------------------+
|                       MÔ HÌNH HÓA ĐỒ THỊ VÀ DÓNG HÀNG                         |
+-----------------------------------+-------------------------------------------+
| Bài toán dóng hàng nhiều đồ thị   | Biểu diễn túi liên kết thành đồ thị tâm   |
| (MGA - Vị trí liên kết protein)   | giả L = {A,B,C,D,E,F,G}, ngưỡng < 12Å     |
+-----------------------------------+-------------------------------------------+
| Bài toán dóng hàng toàn cục       | Biểu diễn 2 mạng PPI, tìm đơn ánh         |
| (GNA - Mạng tương tác PPI)        | f: V1 -> V2 (với |V1| <= |V2|)            |
+-----------------------------------+-------------------------------------------+

Phương pháp tối ưu tổ hợp mềm

Luận án dựa trên các phương pháp metaheuristic:

  • Tối ưu đàn kiến (Ant Colony Optimization - ACO): Mô phỏng hành vi tìm đường đi ngắn nhất của đàn kiến thông qua nồng độ vết mùi pheromone $\tau$ và thông tin heuristic $\eta$. Xác suất kiến $k$ tại đỉnh $i$ chọn chuyển sang đỉnh $j \in J_k(i)$ được tính theo công thức: $$P_{ij}^k(t) = \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in J_k(i)} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}]^\beta}$$ trong đó $\alpha, \beta > 0$ là các tham số trọng số; $J_k(i)$ là tập các đỉnh hợp lệ chưa thăm.
  • Quy tắc cập nhật mùi Max-Min trơn (Smooth Max-Min Ant System - SMMAS): Luận án lựa chọn quy tắc SMMAS (Do Duc, Dinh & Hoang Xuan, 2008; Hoang Xuan Huan et al., 2013) nhằm khắc phục nhược điểm của Hệ kiến AS (Dorigo, 1991), Hệ đàn kiến ACS (Dorigo & Gambardella, 1997) và Hệ kiến Max-Min MMAS (Stützle & Hoos, 2000). Công thức cập nhật vết mùi toàn cục cho mọi cạnh: $$\tau_{ij}(t+1) = (1 - \rho)\tau_{ij}(t) + \Delta \tau_{ij}$$ với $\Delta \tau_{ij} = \rho \cdot \tau_{max}$ nếu cạnh $(i, j)$ thuộc lời giải tốt nhất $w(t)$, ngược lại $\Delta \tau_{ij} = 0$; vết mùi ban đầu được gán $\tau_0 = \tau_{max}$.
  • Giải thuật Memetic và Tìm kiếm Tabu (Tabu Search): Kết hợp lược đồ tìm kiếm ngẫu nhiên trên quần thể của ACO với các thủ tục tìm kiếm cục bộ (local search) và cấu trúc danh sách cấm Tabu (Glover, 1986) gồm bộ nhớ ngắn hạn (TabuList kích thước $t$), bộ nhớ trung hạn (tiêu chuẩn mong đợi) và bộ nhớ dài hạn (đa dạng hóa lời giải).

Dữ liệu và chỉ số đánh giá thực nghiệm

Phân loại bài toán Nguồn dữ liệu thực nghiệm Kích thước / Đặc điểm mẫu Tiêu chuẩn / Chỉ số đánh giá
Dóng hàng nhiều đồ thị (MGA) Dữ liệu mô phỏng & Cavbase (LIGSITE / PDB) Các tập gồm 4, 8, 16, 32 đồ thị; số đỉnh trung bình 20 và 50 đỉnh Điểm chất lượng dóng hàng $S(A)$, Thời gian thực thi (giây) tại các mốc 50s, 150s, 200s, 300s, 600s, 1000s–6000s
Dóng hàng toàn cục PPI Cơ sở dữ liệu chuẩn IsoBase Mạng PPI của 4 loài: Nấm men (SC), Ruồi giấm (DM), Người (HS), Giun tròn (CE) Điểm dóng hàng toàn cục (GNAS), Số cạnh bảo tồn $|E_{12}|$, Độ chính xác cạnh (EC), Điểm cấu trúc con đối xứng ($S^3$), Thời gian chạy

Nội dung chính theo từng chương

Chương 1: Dóng hàng các mạng protein và tối ưu mềm

Chương 1 thiết lập bức tranh tổng quan về tin sinh học và nền tảng lý thuyết của các phương pháp tối ưu mềm:

  • Cơ sở sinh học phân tử: Trình bày cơ chế truyền đạt thông tin di truyền từ DNA qua phiên mã thành RNA (thay thế Thymine bằng Uracil) và dịch mã thành chuỗi 20 loại amino acid, sau đó cuộn gập thành cấu trúc protein không gian ba chiều. Phân tích vai trò của mạng sinh học (mạng điều hòa gen, mạng trao đổi chất, mạng tương tác PPI, mạng vị trí liên kết protein) trong việc làm sáng tỏ chức năng tế bào.
  • Phát biểu hai bài toán trọng tâm:
    1. Bài toán dóng hàng nhiều mạng các vị trí liên kết protein: Mô hình hóa túi liên kết thành đồ thị gắn nhãn, phân tích hạn chế của các phương pháp so khớp đồ thị cặp đôi và thuật toán Greedy, GAVEO.
    2. Bài toán dóng hàng mạng tương tác protein - protein: So sánh giữa dóng hàng cục bộ (cho kết quả nhiều-nhiều, dễ chồng lấn, nhập nhằng) và dóng hàng toàn cục (đơn ánh một-một, loại bỏ sự nhập nhằng). Khảo sát các thuật toán tiêu biểu: IsoRank, GRAAL, H-GRAAL, MI-GRAAL, C-GRAAL, GHOST, SPINAL, MAGNA, MAGNA++, ModuleAlign.
  • Lý thuyết tối ưu tổ hợp mềm: Khái quát hóa bài toán tối ưu tổ hợp $(S, f, \Omega)$ thông qua ví dụ bài toán người chào hàng (TSP). Phân tích chi tiết phương pháp tối ưu đàn kiến (ACO), so sánh ưu thế của ACO so với GA (không tái sử dụng lời giải cũ một cách thụ động, tích hợp học tăng cường với heuristic, dễ song song hóa). Trình bày cơ chế các quy tắc cập nhật mùi AS, ACS, MMAS, SMMAS, lược đồ memetic và thuật toán tìm kiếm Tabu.

Chương 2: Dóng hàng các mạng các vị trí liên kết protein

Chương 2 tập trung giải quyết bài toán dóng hàng nhiều đồ thị (MGA) mô hình hóa từ các vị trí liên kết protein:

  • Mô hình toán học và đồ thị cấu trúc: Định nghĩa hình thức bài toán MGA trên tập đồ thị $\mathcal{G} = {G_1, \dots, G_n}$, thiết lập hàm đánh giá chất lượng dóng hàng $S(A)$ dựa trên sự tương đồng nhãn đỉnh và trọng số cạnh tương ứng. Xây dựng đồ thị cấu trúc mở rộng phục vụ việc tìm kiếm của đàn kiến.
  • Đề xuất ba thuật toán:
    1. Thuật toán ACO-MGA: Ứng dụng đàn kiến nhân tạo xây dựng lời giải dóng hàng thông qua thủ tục bước ngẫu nhiên, áp dụng quy tắc cập nhật mùi SMMAS và thủ tục tìm kiếm cục bộ cơ bản.
    2. Thuật toán ACO-MGA2: Thiết kế theo lược đồ memetic; sau khi đàn kiến tạo ra tập lời giải ở mỗi bước lặp, thuật toán áp dụng các chiến lược tìm kiếm cục bộ đa dạng (hoán vị các cặp đỉnh có cùng nhãn) nhằm tối ưu hóa lời giải tốt nhất tìm được.
    3. Thuật toán ACOTS-MGA: Kết hợp tối ưu đàn kiến với thuật toán tìm kiếm Tabu. Quá trình tìm kiếm lân cận sử dụng danh sách Tabu để cấm các bước chuyển đã thực hiện trong $t$ vòng lặp gần nhất, kết hợp bộ nhớ trung hạn và dài hạn để tránh rơi vào bẫy cực trị địa phương.
  • Kết quả thực nghiệm:
    • So sánh chất lượng $S(A)$ và thời gian chạy giữa ACO-MGA với thuật toán Greedy và GAVEO trên các bộ dữ liệu 4, 8, 16, 32 đồ thị (với số đỉnh trung bình 20 và 50 đỉnh). Kết quả cho thấy ACO-MGA đạt điểm $S(A)$ cao hơn và thời gian hội tụ nhanh hơn.
    • So sánh mở rộng giữa bốn thuật toán: ACOTS-MGA, ACO-MGA2, GAVEO và Greedy ở các mốc thời gian cố định (50s, 150s, 200s, 300s, 600s) và khảo sát quá trình tăng thời gian từ 1000s đến 6000s trên bộ dữ liệu 16 đồ thị. Thuật toán ACOTS-MGA đạt điểm chất lượng dóng hàng cao nhất trong hầu hết các kịch bản thử nghiệm.

Chương 3: Dóng hàng toàn cục hai mạng tương tác protein-protein

Chương 3 trình bày các đề xuất thuật toán cho bài toán dóng hàng toàn cục hai mạng PPI:

  • Phát biểu bài toán và độ đo đánh giá: Định nghĩa bài toán dóng hàng toàn cục hai mạng PPI thành bài toán tìm đơn ánh giữa hai đồ thị $G_1$ và $G_2$. Xác lập các tiêu chuẩn đánh giá chất lượng dóng hàng gồm: GNAS (Global Network Alignment Score), số cạnh bảo tồn $|E_{12}|$, EC (Edge Correctness), ICS (Induced Conserved Structure) và điểm cấu trúc con đối xứng $S^3$ (Symmetric substructure score).
  • Đề xuất ba thuật toán:
    1. Thuật toán heuristic FASTAN: Xây dựng dóng hàng ban đầu dựa trên ma trận tính toán độ tương tự sinh học kết hợp cấu trúc, tiếp theo sử dụng thủ tục Rebuild để tinh chỉnh dóng hàng. Phân tích lý thuyết chứng minh độ phức tạp tính toán của FASTAN thấp hơn so với thuật toán SPINAL.
    2. Thuật toán ACOGNA: Thuật toán metaheuristic dựa trên tối ưu đàn kiến; thiết lập đồ thị cấu trúc cho bài toán dóng hàng toàn cục, khởi tạo vết mùi và thông tin heuristic, thực hiện thủ tục bước ngẫu nhiên, cập nhật mùi theo quy tắc SMMAS và tích hợp tìm kiếm cục bộ.
    3. Thuật toán ACOGNA++: Phiên bản nâng cao của ACOGNA; cải tiến thủ tục xác định cặp đỉnh dóng hàng nhằm giảm không gian tìm kiếm, tối ưu hóa quy tắc cập nhật vết mùi và tăng cường hiệu quả của thủ tục tìm kiếm cục bộ.
  • Kết quả thực nghiệm:
    • So sánh FASTAN và SPINAL trên bộ dữ liệu IsoBase theo tiêu chuẩn GNAS và $|E_{12}|$ với các giá trị tham số $\alpha$ khác nhau, kèm theo phân tích thời gian chạy trung bình (giây). FASTAN đạt chất lượng tương đương hoặc cao hơn SPINAL nhưng có thời gian thực thi ngắn hơn.
    • So sánh ACOGNA với FASTAN và MAGNA++ theo tiêu chuẩn EC và $S^3$.
    • So sánh tổng thể ACOGNA++ với ACOGNA, MAGNA++ và ModuleAlign theo tiêu chuẩn $S^3$ và thời gian chạy. Thực nghiệm chỉ ra ACOGNA++ đạt điểm $S^3$ vượt trội so với các thuật toán đối sánh trên dữ liệu mạng protein của các cặp loài (SC, DM, HS, CE).

Kết quả và những đóng góp mới

Đóng góp về mặt học thuật và thuật toán

  1. Đề xuất ba thuật toán giải bài toán dóng hàng nhiều đồ thị (MGA):
    • Xây dựng thành công thuật toán ACO-MGA dựa trên đàn kiến nguyên bản cho bài toán dóng hàng nhiều vị trí liên kết protein.
    • Phát triển thuật toán memetic ACO-MGA2 tích hợp các chiến lược tìm kiếm cục bộ linh hoạt.
    • Thiết kế thuật toán memetic lai ghép ACOTS-MGA kết hợp tối ưu đàn kiến và tìm kiếm Tabu, duy trì bộ nhớ danh sách cấm giúp mở rộng khả năng khám phá không gian tìm kiếm.
  2. Đề xuất ba thuật toán giải bài toán dóng hàng toàn cục hai mạng PPI:
    • Xây dựng thuật toán heuristic FASTAN với thủ tục Rebuild có độ phức tạp tính toán thấp hơn thuật toán SPINAL.
    • Đề xuất hai thuật toán tối ưu đàn kiến ACOGNA và ACOGNA++, áp dụng thành công quy tắc cập nhật mùi SMMAS và thủ tục xác định cặp đỉnh dóng hàng cải tiến cho bài toán dóng hàng mạng sinh học quy mô lớn.

Đóng góp về mặt thực nghiệm và ứng dụng

  • Cung cấp các kết quả thực nghiệm chi tiết trên dữ liệu tổng hợp và dữ liệu sinh học thực tế từ Cavbase và IsoBase, chứng minh các thuật toán đề xuất vượt trội hơn các thuật toán đã công bố (Greedy, GAVEO, SPINAL, MAGNA++, ModuleAlign) về điểm chất lượng dóng hàng ($S(A)$, GNAS, $S^3$, EC) và thời gian thực thi.
  • Các kết quả nghiên cứu trong luận án đã được công bố trong 6 công trình khoa học, bao gồm:
    • 04 báo cáo tại các hội nghị quốc tế (Công trình 1, 2, 3, 5 trong danh mục của tác giả).
    • 01 báo cáo tại Hội thảo quốc gia "Nghiên cứu cơ bản và ứng dụng công nghệ thông tin" - FAIR (Công trình 4).
    • 01 bài báo khoa học đăng trên tạp chí chuyên ngành VNU Journal of Science: Computer Science and Communication Engineering (Công trình 6).

Hạn chế và hướng nghiên cứu tiếp

Dựa trên nội dung và phạm vi nghiên cứu được trình bày trong văn bản:

  • Hạn chế:
    • Đối với mạng tương tác protein - protein, luận án mới chỉ tập trung nghiên cứu bài toán dóng hàng toàn cục hai mạng PPI (pairwise alignment); bài toán dóng hàng đồng thời nhiều mạng PPI (multiple network alignment) chưa được triển khai do độ phức tạp tính toán và không gian trạng thái tăng theo hàm mũ.
    • Các thực nghiệm dóng hàng mạng PPI chủ yếu tập trung vào 4 loài sinh vật có trong bộ dữ liệu chuẩn IsoBase (nấm men, ruồi giấm, người, giun tròn).
  • Hướng nghiên cứu tiếp:
    • Nghiên cứu mở rộng các thuật toán dựa trên tối ưu đàn kiến và lược đồ memetic để giải quyết bài toán dóng hàng đồng thời nhiều mạng tương tác protein - protein (đa mạng PPI).
    • Khảo sát khả năng song song hóa các thuật toán đề xuất trên môi trường tính toán phân tán và tính toán song song đa lõi để xử lý các mạng sinh học có quy mô nút và mật độ tương tác lớn hơn.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo chuyên môn cho các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính, Tin sinh học và Toán tin ứng dụng: Có thể tham khảo phương pháp mô hình hóa các bài toán sinh học phân tử thành các bài toán tối ưu tổ hợp trên đồ thị (Chương 1, 2, 3); kỹ thuật thiết kế đồ thị cấu trúc và xây dựng thông tin heuristic cho thuật toán tối ưu đàn kiến.
  • Nhà nghiên cứu về thuật toán tối ưu tổ hợp mềm (Metaheuristics): Tham khảo chi tiết cách cài đặt và ứng dụng quy tắc cập nhật mùi Max-Min trơn (SMMAS), lược đồ memetic kết hợp tìm kiếm cục bộ và kỹ thuật tìm kiếm Tabu trên các bài toán tối ưu NP-khó (Chương 1, 2).
  • Các nhà nghiên cứu trong lĩnh vực Tin sinh học và Công nghệ sinh học: Tham khảo hệ thống các chỉ số đánh giá dóng hàng mạng ($S(A)$, GNAS, EC, ICS, $S^3$) và phương pháp luận thực nghiệm trên các bộ dữ liệu chuẩn Cavbase, PDB và IsoBase (Chương 2, 3).

Câu hỏi thường gặp

1. Tại sao luận án lựa chọn quy tắc cập nhật mùi SMMAS thay vì các quy tắc AS, ACS hay MMAS?

Quy tắc SMMAS (Smooth Max-Min Ant System) được lựa chọn vì khắc phục được hai nhược điểm lớn của các quy tắc trước: (1) Tránh việc vết mùi ở các cạnh ít được cập nhật bị giảm quá nhanh về cận dưới $\tau_{min}$ như ở MMAS (làm thu hẹp không gian tìm kiếm) hoặc dần về không như ở AS, ACS; (2) Lượng mùi gia tăng $\Delta \tau_{ij} = \rho \cdot \tau_{max}$ không phụ thuộc trực tiếp vào giá trị hàm mục tiêu, giúp giảm đáng kể chi phí tính toán trong khi vẫn đảm bảo hiệu quả của cơ chế học tăng cường.

2. Khái niệm "tâm giả" (pseudocenter) trong mô hình hóa túi liên kết protein được định nghĩa như thế nào?

Tâm giả là các điểm trong không gian ba chiều biểu thị cho tâm của một đặc trưng lý hóa riêng biệt của túi liên kết protein (trích xuất từ Cavbase qua thuật toán LIGSITE). Kiểu và vị trí của tâm giả phụ thuộc vào các amino acid bao quanh túi liên kết. Nhãn của tâm giả thuộc tập $L = {A, B, C, D, E, F, G}$, đại diện cho các nhóm: donor liên kết hydro, acceptor, mixed donor/acceptor, hydrophobic aliphatic, ion kim loại, nhóm pi... Hai tâm giả được nối với nhau bằng một cạnh nếu khoảng cách Ơclit nhỏ hơn 12Å.

3. Sự khác biệt cơ bản giữa dóng hàng cục bộ và dóng hàng toàn cục mạng PPI là gì?

Dóng hàng cục bộ tìm kiếm các đồ thị con tương đồng giữa các mạng, thường cho kết quả ánh xạ dạng nhiều-nhiều, dẫn tới hiện tượng các mạng con bị chồng lấn, nhập nhằng và khó chuyển giao tri thức chức năng tổng thể. Ngược lại, dóng hàng toàn cục xác định một đơn ánh một-một từ toàn bộ tập đỉnh của mạng có kích thước nhỏ hơn vào mạng lớn hơn, giúp xác định rõ ràng các vùng mạng được bảo tồn trên toàn hệ thống và loại bỏ sự nhập nhằng.

4. Thuật toán ACOTS-MGA trong Chương 2 kết hợp tối ưu đàn kiến và tìm kiếm Tabu theo cơ chế nào?

ACOTS-MGA hoạt động theo lược đồ memetic: Đàn kiến sử dụng thủ tục bước ngẫu nhiên trên đồ thị cấu trúc để tạo ra tập các phương án dóng hàng nhiều đồ thị. Sau đó, thuật toán áp dụng tìm kiếm Tabu để cải thiện lời giải tốt nhất. Danh sách cấm (TabuList) lưu lại các bước chuyển hoán vị đỉnh vừa thực hiện trong $t$ vòng lặp để ngăn chặn việc lặp lại các trạng thái đã xét, đồng thời phối hợp bộ nhớ trung hạn và dài hạn để hỗ trợ thuật toán thoát khỏi cực trị địa phương.

5. Những tiêu chuẩn định lượng nào được sử dụng để đánh giá chất lượng dóng hàng toàn cục hai mạng PPI trong Chương 3?

Luận án sử dụng 5 tiêu chuẩn định lượng chính:

  • GNAS (Global Network Alignment Score): Điểm đánh giá kết hợp giữa độ tương đồng tô pô và độ tương đồng sinh học.
  • $|E_{12}|:$ Số lượng cạnh được bảo tồn đồng thời giữa hai mạng.
  • EC (Edge Correctness): Tỷ lệ phần trăm các cạnh của mạng nguồn được ánh xạ chính xác sang các cạnh của mạng đích.
  • ICS (Induced Conserved Structure): Điểm cấu trúc bảo tồn cảm sinh.
  • $S^3$ (Symmetric substructure score): Điểm cấu trúc con đối xứng, đo lường mức độ trùng khớp cấu trúc cảm sinh giữa hai mạng.

Kết luận

Luận án tiến sĩ của tác giả đã nghiên cứu và giải quyết hai bài toán tối ưu tổ hợp NP-khó trong tin sinh học: 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. Tác giả đã đề xuất sáu thuật toán mới bao gồm các thuật toán heuristic (FASTAN), thuật toán tối ưu đàn kiến (ACO-MGA, ACOGNA, ACOGNA++) và các thuật toán memetic kết hợp tìm kiếm cục bộ và tìm kiếm Tabu (ACO-MGA2, ACOTS-MGA) sử dụng quy tắc cập nhật mùi SMMAS. Các kết quả thực nghiệm trên cơ sở dữ liệu Cavbase và IsoBase đã chứng minh các thuật toán đề xuất đạt chất lượng dóng hàng cao hơn và thời gian tính toán tối ưu hơn so với các phương pháp đối sánh như Greedy, GAVEO, SPINAL, MAGNA++ và ModuleAlign. Các đóng góp khoa học của luận án đã được công bố qua 6 công trình khoa học tại các hội nghị quốc tế, hội thảo quốc gia và tạp chí chuyên ngành.