Luận văn tiến sĩ công nghệ thông tin một số thuật toán dóng hàng các mạng protein

Tin sinh học là một lĩnh vực nghiên cứu quan trọng, kết hợp giữa sinh học và công nghệ thông tin. 132 trang · Đại học Quốc gia Hà Nội · 2019.

• Người hướng dẫn: TS. Hoàng Xuân Huấn
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Một Số Thuật Toán Dóng Hàng Các Mạng Protein
• Loại tài liệu: luận án
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: DÓNG HÀNG CÁC MẠNG PROTEIN VÀ TỐI ƯU MỀM
• 1.1. Tin sinh học và dóng hàng các mạng protein
• 1.2. Bài toán dóng hàng nhiều mạng các vị trí liên kết protein
• 1.3. Bài toán dóng hàng mạng tương tác protein - protein
• 1.4. Bài toán tối ưu tổ hợp và tiếp cận mềm
• 1.5. Phương pháp tối ưu đàn kiến
• 1.6. Tính toán tiến hóa và các thuật toán memetic
• 1.7. Thuật toán tìm kiếm Tabu
• 1.8. Động cơ nghiên cứu
• 1.9. Kết luận chương
• 2. CHƯƠNG 2: DÓNG HÀNG CÁC MẠNG CÁC VỊ TRÍ LIÊN KẾT PROTEIN
• 2.1. Bài toán dóng hàng nhiều đồ thị
• 2.2. Tập nhiều đồ thị
• 2.3. Dóng hàng nhiều đồ thị
• 2.4. Hàm đánh giá chất lượng dóng hàng
• 2.5. Thuật toán dựa trên ACO
• 2.5.1. Đồ thị cấu trúc
• 2.5.2. Thủ tục bước ngẫu nhiên để xây dựng một dóng hàng
• 2.5.3. Qui tắc cập nhật mùi
• 2.5.4. Thủ tục tìm kiếm cục bộ
• 2.5.5. Thuật toán theo lược đồ memetic
• 2.6. Thuật toán memetic mới kết hợp ACO và tìm kiếm Tabu
• 2.6.1. Đồ thị cấu trúc
• 2.6.2. Vết mùi và thông tin heuristic
• 2.6.3. Thủ tục bước ngẫu nhiên xây dựng một dóng hàng
• 2.6.4. Qui tắc cập nhật vết mùi
• 2.6.5. Thủ tục tìm kiếm cục bộ
• 2.7. Các kết quả thực nghiệm
• 2.7.1. Dữ liệu thực nghiệm
• 2.7.2. Thực nghiệm so sánh thuật toán ACO-MGA với thuật toán Greedy và GAVEO
• 2.7.3. Thực nghiệm so sánh các thuật toán ACOTS-MGA, ACO-MGA2, GAVEO và Greedy
• 2.8. Kết luận chương
• 3. CHƯƠNG 3: DÓNG HÀNG TOÀN CỤC HAI MẠNG TƯƠNG TÁC PROTEIN-PROTEIN
• 3.1. Bài toán dóng hàng toàn cục mạng tương tác protein
• 3.2. Phát biểu bài toán
• 3.3. Đánh giá chất lượng dóng hàng toàn cục
• 3.4. Thuật toán FASTAN
• 3.4.1. Xây dựng dóng hàng ban đầu
• 3.4.2. Thủ tục Rebuild
• 3.4.3. Độ phức tạp của thuật toán FASTAN so với SPINAL
• 3.5. Thuật toán ACOGNA
• 3.5.1. Đồ thị cấu trúc
• 3.5.2. Vết mùi và thông tin heuristic
• 3.5.3. Thủ tục bước ngẫu nhiên để xây dựng dóng hàng
• 3.5.4. Quy tắc cập nhật vết mùi
• 3.5.5. Thủ tục tìm kiếm cục bộ
• 3.6. Thuật toán ACOGNA++
• 3.6.1. Mô tả thuật toán
• 3.7. Thủ tục xác định cặp đỉnh dóng hàng
• 3.8. Qui tắc cập nhật vết mùi
• 3.9. Thủ tục tìm kiếm cục bộ
• 3.10. Kết quả thực nghiệm
• 3.10.1. Dữ liệu thực nghiệm
• 3.10.2. Thực nghiệm so sánh thuật toán FASTAN với thuật toán SPINAL
• 3.10.3. Thực nghiệm so sánh thuật toán ACOGNA với các thuật toán FASTAN và MAGNA++
• 3.10.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
• 3.11. Kết luận chương
• DANH MỤC BẢNG BIỂU
• DANH MỤC CÁC HÌNH
• DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về tin sinh học và dóng hàng các mạng protein

Tin sinh học là một lĩnh vực nghiên cứu quan trọng, kết hợp giữa sinh học và công nghệ thông tin. Nó giúp phân tích và hiểu rõ hơn về các quá trình sinh học phức tạp. Trong đó, dóng hàng các mạng protein là một trong những bài toán chính, cho phép xác định mối quan hệ và chức năng của các protein trong cơ thể sống. Việc dóng hàng này không chỉ giúp hiểu rõ hơn về cấu trúc mà còn về chức năng của protein, từ đó hỗ trợ trong việc phát triển các phương pháp điều trị bệnh. Các nghiên cứu gần đây đã chỉ ra rằng việc áp dụng các thuật toán tối ưu mềm có thể cải thiện đáng kể hiệu quả của quá trình dóng hàng này. Theo đó, các thuật toán như ACO (Tối ưu đàn kiến) và các phương pháp học máy đã được áp dụng để giải quyết các bài toán NP-khó trong lĩnh vực này.

1.1. Tầm quan trọng của tin sinh học

Tin sinh học đã trở thành một công cụ không thể thiếu trong nghiên cứu sinh học hiện đại. Nó cho phép các nhà khoa học phân tích dữ liệu sinh học lớn và phức tạp, từ đó rút ra những kết luận quan trọng về sự tiến hóa và chức năng của các sinh vật. Việc dóng hàng các mạng protein giúp xác định các mối quan hệ giữa các protein, từ đó hiểu rõ hơn về các quá trình sinh học diễn ra trong cơ thể. Điều này đặc biệt quan trọng trong việc phát triển các liệu pháp điều trị cho các bệnh di truyền và ung thư. Các nghiên cứu cho thấy rằng việc áp dụng các phương pháp tối ưu mềm có thể mang lại những kết quả khả quan trong việc dóng hàng các mạng protein, giúp cải thiện độ chính xác và hiệu quả của các dự đoán sinh học.

II. Các thuật toán tối ưu mềm trong dóng hàng mạng protein

Các thuật toán tối ưu mềm đã được áp dụng rộng rãi trong việc giải quyết các bài toán dóng hàng mạng protein. Những thuật toán này bao gồm tối ưu đàn kiến, giải thuật di truyền, và tính toán tiến hóa. Mỗi thuật toán có những ưu điểm và nhược điểm riêng, nhưng đều hướng đến mục tiêu tối ưu hóa chất lượng của kết quả dóng hàng. Chẳng hạn, thuật toán ACO đã cho thấy khả năng tìm kiếm hiệu quả trong không gian giải pháp lớn, giúp cải thiện đáng kể chất lượng của các giải pháp so với các phương pháp truyền thống. Việc áp dụng các phương pháp này không chỉ giúp giải quyết các bài toán NP-khó mà còn mở ra hướng đi mới trong nghiên cứu và ứng dụng tin sinh học.

2.1. Tối ưu đàn kiến ACO

Tối ưu đàn kiến (ACO) là một trong những phương pháp nổi bật trong lĩnh vực tối ưu hóa. Nó mô phỏng hành vi tìm kiếm thức ăn của đàn kiến, cho phép tìm ra đường đi ngắn nhất trong không gian giải pháp. Trong bối cảnh dóng hàng các mạng protein, ACO đã được áp dụng để giải quyết bài toán dóng hàng nhiều đồ thị. Kết quả thực nghiệm cho thấy rằng ACO có khả năng tìm kiếm các giải pháp tối ưu với thời gian tính toán hợp lý. Các thuật toán như ACO-MGA và ACOGNA đã được phát triển và chứng minh hiệu quả trong việc cải thiện chất lượng dóng hàng so với các thuật toán trước đó. Điều này cho thấy tiềm năng lớn của ACO trong việc giải quyết các bài toán phức tạp trong tin sinh học.

III. Kết quả thực nghiệm và ứng dụng

Kết quả thực nghiệm từ các thuật toán đề xuất cho thấy sự cải thiện rõ rệt về chất lượng và thời gian tính toán trong việc dóng hàng các mạng protein. Các thuật toán như ACO-MGA và ACOGNA đã được kiểm nghiệm trên nhiều bộ dữ liệu khác nhau, cho thấy khả năng vượt trội so với các phương pháp truyền thống. Việc áp dụng các thuật toán này không chỉ giúp nâng cao độ chính xác trong dóng hàng mà còn mở ra cơ hội mới trong nghiên cứu và phát triển các liệu pháp điều trị bệnh. Các kết quả này đã được công bố trong nhiều hội nghị và tạp chí khoa học, khẳng định giá trị thực tiễn của nghiên cứu.

3.1. Ứng dụng trong nghiên cứu y học

Nghiên cứu về dóng hàng các mạng protein có ứng dụng quan trọng trong y học, đặc biệt trong việc phát hiện và điều trị các bệnh di truyền. Việc hiểu rõ mối quan hệ giữa các protein giúp các nhà khoa học phát triển các liệu pháp điều trị hiệu quả hơn. Các thuật toán tối ưu mềm đã chứng minh khả năng hỗ trợ trong việc phân tích và dự đoán chức năng của các protein chưa được nghiên cứu kỹ. Điều này không chỉ giúp nâng cao hiểu biết về các cơ chế bệnh lý mà còn mở ra hướng đi mới trong phát triển thuốc và liệu pháp điều trị.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ "Một số thuật toán dóng hàng các mạng protein" được tác giả Trần Ngọc Hà 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, thuộc chuyên ngành Khoa học máy tính (mã số: 9480101.01), 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, các phân tích so sánh cấu trúc tuần tự của chuỗi DNA và protein không đủ để giải thích đầy đủ các mối quan hệ chức năng trong tế bào. Protein quyết định các đặc tính sinh học, hệ miễn dịch và quá trình phát triển của cơ thể sống thông qua các tương tác phức tạp. Việc mô hình hóa và phân tích các mạng sinh học, tiêu biểu là mạng các vị trí liên kết protein (binding pockets) và mạng tương tác protein - protein (Protein-Protein Interaction - PPI), cho phép chuyển giao tri thức chức năng từ các sinh vật mô hình đã nghiên cứu rõ sang các loài chưa được khảo sát kỹ lưỡng hoặc khó thực nghiệm trên cơ thể người do rào cản đạo đức và pháp lý.

Về mặt tính toán, 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 đề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 tham lam) chỉ phù hợp với dữ liệu quy mô nhỏ và chất lượng nghiệm thấp khi kích thước tăng. Ngược lại, các thuật toán di truyền (GA) hay tối ưu toàn cục hiện có gặp hạn chế lớn về thời gian hội tụ, khả năng khai thác thông tin định hướng (heuristic), hoặc chỉ tối ưu đơn lẻ hàm mục tiêu mà chưa cân bằng được tính khả mở và độ chính xác. Do đó, khoảng trống nghiên cứu đặt ra là xây dựng các giải thuật tối ưu tổ hợp mềm thông minh nhằm nâng cao chất lượng dóng hàng và tối ưu hóa thời gian tính toán trên các tập dữ liệu sinh học thực tế quy mô lớn.

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

Mục tiêu tổng quát 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 để đề 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, đạt chất lượng lời giải cao hơn và thời gian tính toán tối ưu hơn các thuật toán cùng thời điểm.

Tác giả xác định hai nhiệm vụ cụ thể được đánh số trong văn bản:

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ông bố; tìm hiểu các kỹ thuật tính toán mềm để xác định ư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.
2. 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 đó.

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

• Đối tượng nghiên cứu: Mô hình đồ thị biểu diễn cấu trúc không gian 3 chiều của các túi liên kết protein; mô hình đồ thị biểu diễn mạng tương tác protein - protein; các giải thuật tối ưu hóa mềm, trọng tâm là thuật toán tối ưu đàn kiến (Ant Colony Optimization - ACO), giải thuật tìm kiếm cục bộ (Local Search), giải thuật tìm kiếm Tabu (Tabu Search) và lược đồ memetic.
• Phạm vi dữ liệu và không gian thực nghiệm:
  • Dữ liệu túi liên kết protein: Trích xuất từ cơ sở dữ liệu Cavbase thông qua thuật toán LIGSITE trên ngân hàng dữ liệu protein (PDB), khảo sát các tập dữ liệu gồm 4, 8, 16 và 32 đồ thị với số đỉnh trung bình 20 và 50 đỉnh.
  • Dữ liệu mạng tương tác protein - protein: Tập dữ liệu chuẩn IsoBase của các loài sinh vật mô hình gồm: 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).
  • Về phạm vi bài toán: Tập trung vào bài toán dóng hàng đồng thời nhiều đồ thị vị trí liên kết protein (Multigraph Alignment - MGA) và bài toán dóng hàng toàn cục giữa hai mạng tương tác protein - protein (Global Network Alignment).

---

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

Các hướng nghiên cứu về dóng hàng mạng vị trí liên kết protein

Để phân tích cấu trúc 3 chiều của protein, các tác giả Schmitt et al. (2002), Hendlich et al. (2003) và Weskamp et al. (2007) đã đề xuất mô hình hóa túi liên kết protein thành đồ thị dựa trên cơ sở dữ liệu Cavbase. Các nghiên cứu ban đầu áp dụng so khớp chính xác đồ thị nhưng gặp trở ngại trước các biến đổi sinh học xấp xỉ.

• Weskamp et al. (2007) chính thức phát biểu bài toán dóng hàng nhiều đồ thị (MGA) và đề xuất thuật toán heuristic Greedy. Thuật toán này chạy nhanh nhưng chất lượng nghiệm giảm mạnh khi kích thước đồ thị tăng.
• Fober et al. (2009) mở rộng bài toán MGA cho phân tích cấu trúc phân tử và đề xuất thuật toán di truyền GAVEO. Nhược điểm của GAVEO là không tích hợp được thông tin heuristic từ các bước trước, lặp lại nhiều nghiệm cũ nên tốc độ hội tụ chậm khi không gian tìm kiếm mở rộng.

Các hướng nghiên cứu về dóng hàng mạng tương tác protein - protein

Luận án phân loại tổng quan các nghiên cứu dóng hàng mạng PPI theo hai nhánh chính:

• Dóng hàng cục bộ (Local Network Alignment): Đại diện bởi các nghiên cứu của Berg & Lassig (2004, 2006), Kelley et al. (2004), Flannick et al. (2006), Koyutürk et al. (2006), Liang et al. (2006), Roded Sharan et al., Mina & Guzzi (2012), Ciriello et al. (2012), Pache & Aloy (2012). Dóng hàng cục bộ xác định các đồ thị con tương đồng về cấu trúc tô-pô và trình tự. Hạn chế của hướng này là sinh ra ánh xạ nhiều - nhiều, tạo ra các mạng con chồng lấn, gây nhập nhằng và khó xác định ranh giới bảo tồn chức năng tổng thể.
• Dóng hàng toàn cục (Global Network Alignment): Tìm một đơn ánh từ mạng có số đỉnh nhỏ hơn sang mạng có số đỉnh lớn hơn nhằm bảo tồn cấu trúc toàn mạng. Các thuật toán dóng hàng toàn cục tiêu biểu được tác giả hệ thống hóa gồm:
  • IsoRank (Singh et al., 2007, 2008): Lấy cảm hứng từ thuật toán PageRank của Brin & Page (1998) để tính toán điểm tương đồng nút thông qua các nút lân cận.
  • Họ thuật toán GRAAL: Gồm GRAAL, H-GRAAL, MI-GRAAL (Kuchaiev et al., 2010; Kuchaiev & Pržulj, 2011; Milenković et al., 2010) và C-GRAAL (Memišević & Pržulj, 2012), kết hợp kỹ thuật tham lam với thông tin heuristic graphlet, hệ số phân nhóm và giá trị E-value từ BLAST.
  • GHOST (Patro & Kingsford, 2012): Giải bài toán quy hoạch bậc hai heuristic để tính toán độ tương đồng nội mạng.
  • SPINAL (Aladag & Erten, 2013): Sử dụng hàm mục tiêu GNAS, phối hợp tính toán độ tương đồng và chiến lược dóng hàng hai pha.
  • MAGNA (Saraph & Milenković, 2014) và MAGNA++ (Vijayan et al., 2015): Sử dụng giải thuật di truyền tối ưu trực tiếp độ đo $S^3$.
  • ModuleAlign (Hashemifar et al., 2016): Dựa trên việc phân cụm chức năng protein thành các module và áp dụng cơ chế dóng hàng lặp.
  • Các phương pháp lặp cập nhật ma trận tương đồng khác: Zaslavskiy et al. (2009), El-Kebir et al. (2011), Ibragimov et al. (2014), Meng et al. (2016).

Vị trí và khoảng trống giải quyết của luận án

Các thuật toán heuristic hiện hành cho kết quả nhanh nhưng chất lượng nghiệm chưa tối ưu, trong khi các thuật toán tiến hóa (như GA trong GAVEO, MAGNA++) gặp khó khăn trong việc khai thác thông tin học tăng cường và kiểm soát thời gian tính toán. Luận án lựa chọn phương pháp tối ưu đàn kiến (ACO) làm nền tảng cốt lõi, phối hợp với các kỹ thuật tìm kiếm cục bộ và tìm kiếm Tabu theo lược đồ memetic, nhằm tạo ra sự cân bằng giữa khả năng khám phá không gian tìm kiếm toàn cục và khả năng tăng cường khai thác tại các vùng nghiệm cục bộ có triển vọng.

---

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

Khung lý thuyết và mô hình hóa bài toán

1. Mô hình đồ thị túi liên kết protein:

   • Túi liên kết được biểu diễn bằng đồ thị $G(V, E)$, trong đó các đỉnh $V$ đại diện cho các tâm giả (pseudocenters) mang các thuộc tính lý hóa xác định bởi luật chiết xuất Cavbase.
   • Nhãn đỉnh thuộc tập $L = {A, B, C, D, E, F, G}$ (đại diện cho các nhóm chức năng: hydrogenbond donor, acceptor, mixed donor/acceptor, hydrophobic aliphatic, metal ion, pi...).
   • Một cạnh $e \in E$ được thiết lập giữa hai đỉnh nếu khoảng cách Euclid giữa chúng nhỏ hơn $12\text{Å}$ ($1\text{Å} = 10^{-10}\text{m}$), trọng số cạnh $w(e)$ phản ánh khoảng cách không gian.
   • Các phép biến đổi đồ thị gồm: chèn/xóa đỉnh (bổ sung nút giả), đổi nhãn đỉnh, đổi trọng số cạnh. Khoảng cách chỉnh sửa giữa hai đồ thị là dãy phép biến đổi nhỏ nhất để chuyển đổi giữa chúng.

2. Mô hình bài toán tối ưu tổ hợp tổng quát:

   • Bài toán tối ưu tổ hợp được định nghĩa bởi bộ ba $(S, f, \Omega)$, với $S$ là tập không gian trạng thái, $f$ là hàm mục tiêu cần tối ưu hóa, và $\Omega$ là tập các ràng buộc. Mỗi phương án $s \in S$ thỏa mãn $\Omega$ là lời giải chấp nhận được.
   • Không gian tìm kiếm được mô hình hóa qua đồ thị cấu trúc $G(V, E)$, tập thành phần $C = {c_1, \dots, c_n}$, tập đỉnh ban đầu $C_0 \subseteq V$, và vector trạng thái $X$.

3. Thuật toán tối ưu đàn kiến (ACO) và các biến thể:

   • Xác suất kiến $k$ tại đỉnh $i$ chọn di chuyển sang đỉnh $j$ ở bước lặp $t$: $$p_{ij}^k(t) = \begin{cases} \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in J_k(i)} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}]^\beta} & \text{nếu } j \in J_k(i) \ 0 & \text{nếu } j \notin J_k(i) \end{cases}$$ Trong đó $\tau_{ij}(t)$ là nồng độ vết mùi, $\eta_{ij}$ là thông tin heuristic, $\alpha, \beta$ là các tham số trọng số, $J_k(i)$ là tập các đỉnh hợp lệ có thể mở rộng từ $i$.
   • Quy tắc bay hơi vết mùi tổng quát với hệ số $\rho \in (0, 1]$: $$\tau_{ij}(t+1) = (1 - \rho)\tau_{ij}(t) + \Delta \tau_{ij}$$
   • Luận án phân tích 4 quy tắc cập nhật mùi: Ant System (AS), Ant Colony System (ACS), Max-Min Ant System (MMAS) của Stützle & Hoos (2000), và Smooth Max-Min Ant System (SMMAS) của Đỗ Đức Đông, Đinh Bá Tiến, Hoàng Xuân Huấn (2008).
   • Quy tắc cập nhật mùi SMMAS được lựa chọn làm nòng cốt trong luận án: Khởi tạo $\tau_0 = \tau_{max}$, khi cập nhật toàn cục cho mọi cạnh với bước tăng $\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)$, giúp duy trì sự cân bằng giữa tính tăng cường và tính khám phá mà không đòi hỏi tính toán cận phức tạp.

4. Lược đồ Memetic và Tìm kiếm Tabu (Tabu Search):

   • Thuật toán Memetic kết hợp tìm kiếm quần thể toàn cục với các chiến lược tìm kiếm cục bộ trên tập lời giải triển vọng $\Omega(t)$ ở cuối mỗi vòng lặp.
   • Thuật toán tìm kiếm Tabu (Fred W. Glover, 1986) sử dụng danh sách cấm (TabuList) lưu các bước chuyển vừa thực hiện trong $t$ bước lặp (kích thước Tabu) để tránh rơi vào cực trị địa phương, kết hợp 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).

Phương pháp nghiên cứu và nguồn dữ liệu

• Phương pháp tiếp cận: Phương pháp nghiên cứu định lượng kết hợp mô hình hóa toán học và thuật toán thực nghiệm. Xây dựng các đồ thị cấu trúc đặc thù cho từng bài toán dóng hàng, thiết lập hàm heuristic, tích hợp thuật toán tìm kiếm cục bộ và Tabu Search vào pha khai thác của ACO.
• Tiêu chuẩn và hàm mục tiêu đánh giá:
  • Dóng hàng nhiều đồ thị túi liên kết: Hàm chất lượng dóng hàng tổng thể $S(A)$.
  • Dóng hàng toàn cục mạng PPI: Điểm dóng hàng toàn cục GNAS (Global Network Alignment Score), số lượng cạnh tương ứng $|E_{12}|$, độ chính xác về cạnh $EC$ (Edge Correctness), độ bảo tồn cấu trúc cảm sinh $ICS$ (Induced Conserved Structure), và điểm cấu trúc con đối xứng $S^3$ (Symmetric Substructure Score).
• Dữ liệu thực nghiệm: Cơ sở dữ liệu Cavbase và IsoBase.

---

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, làm rõ vai trò của sinh học phân tử từ học thuyết tiến hóa của Darwin, cấu trúc xoắn kép DNA của Watson và Crick (1953), đến quá trình biểu hiện gen gồm hai giai đoạn phiên mã và dịch mã tạo nên chuỗi 20 loại amino acid cấu thành protein. Chương này phân tích hạn chế của việc phân tích chuỗi tuần tự và khẳng định sự cần thiết của việc nghiên cứu 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).

Tiếp đó, chương 1 đi sâu vào cơ sở toán học của bài toán tối ưu tổ hợp tổng quát thông qua ví dụ bài toán người chào hàng (TSP), phân biệt giữa tiếp cận tính toán cứng và tính toán mềm. Tác giả trình bày chi tiết thuật toán tối ưu đàn kiến (ACO), phân tích bản chất sinh học và mô hình toán của đàn kiến nhân tạo, so sánh chi tiết các quy tắc cập nhật mùi (AS, ACS, MMAS, SMMAS). Chương 1 cũng trình bày nguyên lý tính toán tiến hóa, thuật toán memetic và thuật toán tìm kiếm Tabu, đặt nền tảng phương pháp luận cho việc đề xuất các thuật toán ở Chương 2 và Chương 3.

+-----------------------------------------------------------------------------------+
|               KHUNG PHƯƠNG PHÁP LUẬN TỐI ƯU TỔ HỢP MỀM CỦA LUẬN ÁN                |
+-----------------------------------------------------------------------------------+
|  [Đồ thị cấu trúc G(V,E)]  +  [Thông tin Heuristic]  +  [Học tăng cường vết mùi]  |
|                 [Thuật toán Tối ưu đàn kiến cơ sở (ACO/SMMAS)]                     |
|        [Lược đồ Memetic: Tích hợp Tìm kiếm cục bộ / Tìm kiếm Tabu (TS)]           |
| [Chương 2: Bài toán MGA]                             [Chương 3: Bài toán PPI]     |
| 1. ACO-MGA                                           1. FASTAN (Heuristic)        |
| 2. ACO-MGA2 (Memetic)                                2. ACOGNA (ACO)              |
| 3. ACOTS-MGA (ACO + Tabu)                            3. ACOGNA++ (Cải tiến)       |
+-----------------------------------------------------------------------------------+

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

Chương 2 trình bày chi tiết việc mô hình hóa bài toán dóng hàng nhiều đồ thị (MGA) cho các túi liên kết protein và đề xuất ba thuật toán giải:

1. Thuật toán ACO-MGA: Xây dựng đồ thị cấu trúc cho phép đàn kiến thực hiện bước ngẫu nhiên tạo lập dóng hàng nhiều đồ thị, cập nhật vết mùi theo quy tắc SMMAS và tích hợp thủ tục tìm kiếm cục bộ cơ bản.
2. Thuật toán ACO-MGA2: Phát triển dựa trên lược đồ memetic, sử dụng ACO để tạo sinh tập lời giải đa dạng và áp dụng luân phiên các chiến lược tìm kiếm cục bộ linh hoạt trên các cá thể tốt nhất nhằm tăng tốc độ hội tụ.
3. Thuật toán ACOTS-MGA: Kết hợp thuật toán ACO với kỹ thuật tìm kiếm Tabu. Cấu trúc bộ nhớ cấm được áp dụng để kiểm soát các phép hoán vị cặp đỉnh có cùng nhãn trong thủ tục tìm kiếm lân cận, ngăn chặn việc quay lại các cấu hình nghiệm đã duyệt và thúc đẩy quá trình khám phá vùng nghiệm mới.

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 tế từ Cavbase được tổng hợp nhằm so sánh chất lượng dóng hàng $S(A)$ và thời gian tính toán giữa các thuật toán đề xuất (ACO-MGA, ACO-MGA2, ACOTS-MGA) với hai thuật toán đối sánh là Greedy và GAVEO:

Bộ dữ liệu thực nghiệm	Số đỉnh trung bình / đồ thị	Thuật toán đối sánh	Thuật toán đề xuất	Tiêu chí đánh giá chính
4, 8, 16, 32 đồ thị	20 đỉnh	Greedy, GAVEO	ACO-MGA, ACO-MGA2, ACOTS-MGA	Điểm $S(A)$, Thời gian chạy (giây)
4, 8, 16, 32 đồ thị	50 đỉnh	Greedy, GAVEO	ACO-MGA, ACO-MGA2, ACOTS-MGA	Điểm $S(A)$, Thời gian chạy (giây)
8, 16, 32 đồ thị (20 đỉnh)	20 đỉnh	GAVEO	ACOTS-MGA, ACO-MGA2	$S(A)$ tại các mốc 50s, 150s, 200s
4, 8, 16, 32 đồ thị (50 đỉnh)	50 đỉnh	GAVEO	ACOTS-MGA, ACO-MGA2	$S(A)$ tại các mốc 200s, 300s, 600s
16 đồ thị	Khảo sát dài hạn	GAVEO, Greedy	ACOTS-MGA, ACO-MGA2	Điểm $S(A)$ khi thời gian tăng từ 1000s đến 6000s

Kết quả thực nghiệm cho thấy trên cùng một giới hạn thời gian chạy, các thuật toán dựa trên ACO và Memetic (đặc biệt là ACOTS-MGA) đạt điểm chất lượng dóng hàng $S(A)$ cao hơn rõ rệt so với thuật toán Greedy và GAVEO.

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

Chương 3 tập trung vào bài toán dóng hàng toàn cục hai mạng tương tác protein (PPI), phát biểu bài toán dưới dạng đơn ánh tối ưu hóa cấu trúc tô-pô và thông tin trình tự, đồng thời đề xuất ba thuật toán:

1. Thuật toán FASTAN: Tiếp cận theo hướng heuristic hai pha cải tiến; pha đầu xây dựng dóng hàng ban đầu nhanh, pha sau sử dụng thủ tục Rebuild để tinh chỉnh các cặp đỉnh chưa tối ưu. Độ phức tạp tính toán của FASTAN được chứng minh là thấp hơn so với thuật toán SPINAL.
2. Thuật toán ACOGNA: Áp dụng thuật toán tối ưu đàn kiến cho bài toán dóng hàng toàn cục mạng PPI. Thuật toán thiết lập đồ thị cấu trúc ánh xạ giữa hai mạng tương tác, kết hợp thông tin tương đồng sinh học làm heuristic $\eta_{ij}$, áp dụng quy tắc cập nhật mùi SMMAS và tìm kiếm cục bộ.
3. Thuật toán ACOGNA++: Phiên bản nâng cấp của ACOGNA với thủ tục xác định cặp đỉnh dóng hàng cải tiến, quy tắc cập nhật vết mùi tối ưu hóa và thủ tục tìm kiếm cục bộ tăng cường, giúp nâng cao tính chính xác của dóng hàng trên các mạng sinh học lớn.

Luận án thực hiện kiểm nghiệm trên bộ dữ liệu chuẩn IsoBase (chứa dữ liệu tương tác của SC, DM, HS, CE) để so sánh các thuật toán đề xuất với các thuật toán tiêu biểu:

So sánh thực nghiệm	Thuật toán tham chiếu	Hàm mục tiêu / Độ đo	Kết quả ghi nhận từ dữ liệu thực nghiệm
FASTAN vs. SPINAL	SPINAL	GNAS, $|E_{12}|$, Thời gian chạy (s)	FASTAN cho giá trị GNAS và $|E_{12}|$ tương đương hoặc vượt trội với thời gian chạy trung bình ngắn hơn SPINAL
ACOGNA vs. FASTAN & MAGNA++	FASTAN, MAGNA++	GNAS, $|E_{12}|$, $EC$, $S^3$	ACOGNA vượt trội FASTAN về GNAS và $|E_{12}|$ trên nhiều giá trị tham số $\alpha$; đạt độ đo $EC$ và $S^3$ cao hơn MAGNA++
ACOGNA++ vs. MAGNA++ & ModuleAlign	ACOGNA, MAGNA++, ModuleAlign	Điểm cấu trúc con đối xứng ($S^3$), Thời gian chạy (s)	ACOGNA++ đạt điểm $S^3$ cao nhất trong các thuật toán so sánh, đồng thời duy trì thời gian thực thi thấp hơn MAGNA++

---

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

Đóng góp về mặt lý luận và thuật toán

1. Đề xuất ba thuật toán mới cho bài toán dóng hàng nhiều đồ thị vị trí liên kết protein (MGA):
   • Thuật toán ACO-MGA: Ứng dụng tối ưu đàn kiến với quy tắc SMMAS trên đồ thị cấu trúc biểu diễn túi liên kết.
   • Thuật toán ACO-MGA2: Ứng dụng lược đồ memetic kết hợp ACO với các chiến lược tìm kiếm cục bộ đa dạng.
   • Thuật toán ACOTS-MGA: Mô hình lai ghép giữa ACO và tìm kiếm Tabu, sử dụng danh sách cấm để nâng cao khả năng thoát bẫy cực trị địa phương.
2. Đề xuất ba thuật toán mới cho bài toán dóng hàng toàn cục hai mạng tương tác protein (PPI):
   • Thuật toán heuristic FASTAN: Giảm độ phức tạp tính toán so với thuật toán SPINAL nhờ thủ tục Rebuild dóng hàng.
   • Thuật toán ACOGNA: Giải thuật tối ưu đàn kiến đầu tiên được thiết kế chuyên biệt cho dóng hàng toàn cục mạng PPI sử dụng quy tắc SMMAS.
   • Thuật toán ACOGNA++: Tối ưu hóa thủ tục chọn cặp đỉnh và tìm kiếm cục bộ, nâng cao điểm bảo tồn cấu trúc mạng.

Đóng góp về mặt thực tiễn và ứng dụng

• Cung cấp bộ công cụ thuật toán hiệu quả cao cho phép dóng hàng chính xác các túi liên kết và mạng tương tác protein quy mô lớn trên các bộ dữ liệu sinh học thực nghiệm (Cavbase, IsoBase).
• Hỗ trợ công tác phân tích chức năng protein, giúp chuyển giao tri thức sinh học từ các sinh vật mô hình sang hệ gen người, phục vụ nghiên cứu cơ chế bệnh di truyền và phát triển dược phẩm sinh học.

Công trình khoa học đã công bố

Các kết quả của luận án đã được công bố trong 6 công trình khoa học, bao gồm:

• 4 báo cáo tại các hội nghị khoa học quốc tế (Công trình 1, 2, 3, 5).
• 1 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).
• 1 bài báo đăng trên tạp chí khoa học 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 các nội dung được trình bày trong văn bản luận án:

• Hạn chế về phạm vi bài toán mạng tương tác PPI: Luận án tập trung giải quyết bài toán dóng hàng hai mạng PPI thay vì dóng hàng đa mạng đồng thời (nhiều hơn hai mạng PPI), do bài toán dóng hàng đa mạng PPI có độ phức tạp tính toán rất lớn và chưa có nhiều mô hình tối ưu tương thích.
• Hạn chế về cấu trúc tham số: Các thuật toán ACO và Memetic phụ thuộc vào việc thiết lập các tham số thực nghiệm (như hệ số bay hơi $\rho$, trọng số $\alpha, \beta$, kích thước danh sách Tabu), vốn cần được tinh chỉnh theo từng bộ dữ liệu cụ thể.
• Hướng nghiên cứu tiếp: Mở rộng các lược đồ tối ưu đàn kiến và memetic để giải quyết bài toán dóng hàng đa mạng tương tác protein - protein; nghiên cứu song song hóa hoàn toàn các thuật toán trên nền tảng tính toán hiệu năng cao hoặc GPU để xử lý các mạng sinh học có quy mô hàng chục nghìn protein.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho các đối tượng và mục đích cụ thể:

1. 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:
   • 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ị.
   • Tham khảo cách thức thiết kế đồ thị cấu trúc, hàm mục tiêu và toán tử tìm kiếm cho các giải thuật metaheuristic (ACO, Memetic, Tabu Search).
2. Giảng viên và các nhóm nghiên cứu về Tối ưu hóa tổ hợp và Trí tuệ nhân tạo:
   • Sử dụng làm tài liệu giảng dạy chuyên đề về tính toán mềm, tối ưu đàn kiến (đặc biệt là quy tắc SMMAS), và kỹ thuật lai ghép thuật toán tìm kiếm cục bộ.
3. Các nhà nghiên cứu trong lĩnh vực Công nghệ sinh học và Hóa dược:
   • Ứng dụng các thuật toán FASTAN, ACOGNA++, ACOTS-MGA trong việc so sánh túi liên kết thuốc và phân tích chức năng protein từ dữ liệu PDB và IsoBase.

---

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

1. Tại sao việc dóng hàng mạng sinh học lại quan trọng hơn dóng hàng chuỗi tuần tự trong việc xác định chức năng protein?

Theo phân tích trong luận án, các protein có độ tương đồng chuỗi amino acid trên 40% thường có chức năng tương tự. Tuy nhiên, sự tương đồng chức năng thực tế liên quan mật thiết đến cấu trúc không gian 3 chiều và các tương tác mạng lưới hơn là trật tự tuần tự. Ngoài ra, trong tế bào, các protein không hoạt động độc lập mà tương tác qua mạng PPI hoặc liên kết qua các túi hoạt tính. Dóng hàng mạng cho phép phát hiện các vùng bảo tồn cấu trúc tô-pô và chức năng phức tạp mà so sánh chuỗi đơn lẻ không thể phát hiện được.

2. Mô hình biểu diễn túi liên kết protein trong cơ sở dữ liệu Cavbase được xây dựng như thế nào?

Túi liên kết được phát hiện tự động bằng thuật toán LIGSITE từ cấu trúc thực nghiệm trên PDB và lưu trong Cavbase. Mỗi túi liên kết được mô hình hóa thành một đồ thị $G(V, E)$, trong đó $V$ là tập các tâm giả (pseudocenters) mang các nhãn thuộc tập $L = {A, B, C, D, E, F, G}$ đại diện cho các nhóm chức năng lý hóa (donor, acceptor, ion kim loại, pi...). Hai đỉnh được nối bởi một cạnh nếu khoảng cách Euclid giữa chúng nhỏ hơn $12\text{Å}$, với trọng số cạnh là khoảng cách giữa hai tâm.

3. Quy tắc cập nhật vết mùi SMMAS có ưu điểm gì so với quy tắc MMAS truyền thống?

Quy tắc MMAS truyền thống có hai nhược điểm: nếu chọn khoảng cách giữa $\tau_{min}$ và $\tau_{max}$ quá nhỏ sẽ làm giảm hiệu quả học tăng cường, còn nếu quá lớn thì các cạnh ít được thăm sẽ nhanh chóng tụt về $\tau_{min}$ làm co hẹp không gian tìm kiếm; đồng thời lượng mùi thêm vào phụ thuộc vào giá trị hàm mục tiêu gây phức tạp tính toán. Quy tắc SMMAS khắc phục bằng cách cập nhật toàn cục với lượng tăng cố định $\Delta \tau_{ij} = \rho \cdot \tau_{max}$ cho các cạnh thuộc nghiệm tốt nhất, giúp thuật toán dễ cài đặt, giảm độ phức tạp tính toán và nâng cao chất lượng tìm kiếm.

4. Thuật toán ACOTS-MGA cải tiến hiệu năng dóng hàng nhiều đồ thị bằng cơ chế nào?

ACOTS-MGA kết hợp thuật toán tối ưu đàn kiến với tìm kiếm Tabu theo lược đồ memetic. Sau khi đàn kiến xây dựng tập dóng hàng, thuật toán áp dụng tìm kiếm Tabu trên các cặp đỉnh có cùng nhãn. Danh sách Tabu (TabuList) lưu lại các bước chuyển hoán vị vừa thực hiện trong $t$ bước lặp để cấm chọn lại, ngăn ngừa bẫy cực trị địa phương và tăng cường khả năng tìm kiếm sâu trong không gian lân cận của nghiệm.

5. Thuật toán FASTAN và ACOGNA++ vượt trội hơn các thuật toán đối sánh nào trên mạng PPI?

Trên bộ dữ liệu chuẩn IsoBase, thuật toán FASTAN cho kết quả tương đương hoặc cao hơn SPINAL về điểm GNAS và số cạnh tương ứng $|E_{12}|$ nhưng có thời gian thực thi trung bình ngắn hơn. Thuật toán ACOGNA++ đạt điểm bảo tồn cấu trúc đối xứng $S^3$ cao hơn hẳn so với MAGNA++, ModuleAlign và ACOGNA, đồng thời có thời gian chạy nhanh hơn đáng kể so với giải thuật di truyền MAGNA++.

---

Kết luận

Luận án tiến sĩ của tác giả Trần Ngọc Hà đã 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. Bằng việc ứng dụng phương pháp tối ưu đàn kiến kết hợp quy tắc cập nhật mùi SMMAS, tìm kiếm cục bộ và tìm kiếm Tabu theo lược đồ memetic, tác giả đã đề xuất thành công sáu thuật toán mới (ACO-MGA, ACO-MGA2, ACOTS-MGA, FASTAN, ACOGNA, ACOGNA++). Các kết quả thực nghiệm trên cơ sở dữ liệu Cavbase và IsoBase khẳng định tính hiệu quả của các thuật toán đề xuất về cả chất lượng dóng hàng và thời gian tính toán, đóng góp thiết thực cho lĩnh vực tin sinh học và khoa học máy tính.

Trích đoạn nội dung tài liệu

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ử. 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 Luận văn thạc sĩ Công nghệ thông tin 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.

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. 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 Luận văn thạc sĩ Công nghệ thông tin 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. 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. 18 Luận văn thạc sĩ Công nghệ thông tin 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., 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 Luận văn thạc sĩ Công nghệ thông tin 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 Luận văn thạc sĩ Công nghệ thông tin 1. 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.