Nghiên cứu phát triển mô hình động lực cạnh tranh trong mạng thông tin phức hợp và ứng dụng dự đoán gen điều trị ung thư

Nghiên cứu mô hình động lực cạnh tranh trong mạng thông tin phức hợp. Ứng dụng dự đoán gen điều trị ung thư hiệu quả. Giải pháp mới cho y học.

• Tác giả: Phạm Đức Tĩnh
• Người hướng dẫn: TS. Trần Tiến Dũng
• Trường học: Học Viện Khoa Học Và Công Nghệ
• Chuyên ngành: Hệ Thống Thông Tin
• Đề tài: Nghiên Cứu Phát Triển Mô Hình Động Lực Cạnh Tranh Trong Mạng Thông Tin Phức Hợp Và Ứng Dụng Dự Đoán Gen Điều Trị Ung Thư
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2024
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• DANH MỤC CÁC KÝ HIỆU
• DANH MỤC CÁC TỪ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• DANH MỤC THUẬT TOÁN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ XẾP HẠNG ĐỂ DỰ ĐOÁN GEN MỤC TIÊU ĐIỀU TRỊ UNG THƯ
• 1.1. Bài toán xếp hạng để dự đoán gen bệnh
• 1.2. Khái niệm cơ bản về lý thuyết đồ thị và mạng phức hợp
• 1.3. Các phương pháp và nghiên cứu liên quan dự đoán gen điều trị bệnh dựa trên mạng phức hợp
• 2. CHƯƠNG 2: MÔ HÌNH ĐỘNG LỰC CẠNH TRANH NGOÀI TRÊN MẠNG PHỨC HỢP, ỨNG DỤNG TRONG DỰ ĐOÁN GEN MỤC TIÊU ĐIỀU TRỊ UNG THƯ
• 2.1. Mô hình động lực cạnh tranh trên mạng phức hợp
• 2.2. Đề xuất mô hình động lực cạnh tranh ngoài trên mạng phức hợp
• 2.3. Xây dựng thuật toán của mô hình động lực cạnh tranh ngoài
• 2.3.1. Ý tưởng của thuật toán
• 2.3.2. Chức năng, đầu vào, đầu ra của thuật toán
• 2.3.3. Sơ đồ luồng và mã giả của thuật toán
• 2.3.4. Đánh giá độ phức tạp của thuật toán
• 2.4. Xây dựng hệ thống dự đoán gen điều trị ung thư sử dụng mô hình động lực cạnh tranh ngoài
• 2.4.1. Bài toán dự đoán gen mục tiêu điều trị ung thư
• 2.4.2. Dữ liệu thực nghiệm. Sự tương quan giữa các phép đo
• 2.4.3. Mô hình tổng thể hệ thống chẩn đoán gen ung thư dựa trên mạng phức hợp
• 2.4.4. Kết quả dự đoán gen mục tiêu điều trị ung thư
• 2.4.5. So sánh kết quả dự đoán
• 3. CHƯƠNG 3: TƯƠNG TÁC GIÁN TIẾP TRONG MÔ HÌNH ĐỘNG LỰC CẠNH TRANH NGOÀI VÀ ỨNG DỤNG DỰ ĐOÁN GEN ĐIỀU TRỊ UNG THƯ
• 3.1. Đề xuất mô hình tính toán tương tác gián tiếp động lực cạnh tranh ngoài
• 3.2. Mô hình tính toán tương tác trực tiếp động lực cạnh tranh ngoài
• 3.3. Đề xuất mô hình tính toán gián tiếp động lực cạnh tranh ngoài
• 3.4. Xây dựng thuật toán tính toán tương tác gián tiếp động lực cạnh tranh ngoài
• 3.4.1. Thuật toán tính toán ma trận khoảng cách
• 3.4.2. Thuật toán tính toán ma trận ảnh hưởng
• 3.4.3. Thuật toán tính tổng sự ảnh hưởng trên mỗi đỉnh mạng
• 3.5. Tính toán hiệu năng cao cho mô hình động lực cạnh tranh ngoài
• 3.5.1. Xây dựng thuật toán tính toán hiệu năng cao cho mô hình
• 3.5.2. Thiết kế công cụ phần mềm tính toán hiệu năng cao
• 3.5.3. Đánh giá tốc độ tính toán của thuật toán
• 3.6. Dữ liệu thực nghiệm. Kiến trúc của mô hình dự đoán
• 3.7. Kết quả dự đoán gen mục tiêu điều trị ung thư
• 3.8. So sánh kết quả dự đoán với các nghiên cứu khác
• 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Dự Đoán Gen Ung Thư Khái Niệm Cơ Bản

Ung thư là một nhóm bệnh phức tạp, liên quan đến hơn 200 loại bệnh khác nhau, và là một trong những nguyên nhân gây tử vong hàng đầu trên toàn cầu. Việc điều trị ung thư tốn kém và thường có tiên lượng thấp, đặc biệt khi bệnh được phát hiện ở giai đoạn muộn. Các đột biến gen được cho là nguyên nhân chính gây ra ung thư, nhưng không phải tất cả các gen đột biến đều dẫn đến bệnh. Chỉ một số gen, được gọi là gen điều khiển, đóng vai trò quan trọng trong sự phát triển của ung thư và thường là mục tiêu điều trị. Việc xác định các gen bệnh này là rất quan trọng. Hiện nay, việc xác định các gen đột biến gây bệnh ung thư chủ yếu dựa vào các xét nghiệm sinh học lâm sàng, đòi hỏi nhiều thời gian và chi phí. Các phương pháp tiếp cận công nghệ, như thống kê và học máy, đang được phát triển để giảm thiểu khối lượng công việc thực nghiệm và cải thiện độ chính xác của việc xác định gen ung thư.

1.1. Gen Ung Thư và Vai Trò Trong Sự Phát Triển Bệnh

Gen đóng vai trò then chốt trong quá trình phát triển và hoạt động của cơ thể. Đột biến gen có thể dẫn đến nhiều bệnh, trong đó có ung thư. Các gen ung thư hoặc gen điều khiển đóng vai trò quan trọng trong sự phát triển của bệnh và là mục tiêu chính của các phương pháp điều trị. Nghiên cứu sâu hơn về cơ chế phân tử ung thư là yếu tố quan trọng để phát triển các phương pháp điều trị hiệu quả.

1.2. Các Phương Pháp Chẩn Đoán Ung Thư Truyền Thống

Các phương pháp chẩn đoán truyền thống dựa trên các xét nghiệm sinh học lâm sàng, thường tốn kém và mất nhiều thời gian. Các xét nghiệm này được thực hiện thủ công trong phòng thí nghiệm trên các mẫu bệnh phẩm. Mặc dù có độ chính xác cao, nhưng chúng đòi hỏi nhiều nguồn lực. "Việc xác định các gen đột biến gây ra bệnh (bệnh nói chung và bệnh ung thư nói riêng) hay còn được gọi là gen bệnh ở các cơ sở y tế được thực hiện chủ yếu bằng các thực nghiệm xét nghiệm sinh học lâm sàng trên các mẫu bệnh phẩm [3]."

II. Thách Thức Trong Dự Đoán Gen Ung Thư Vấn Đề Cần Giải Quyết

Mặc dù đã có nhiều tiến bộ trong việc xác định gen ung thư, vẫn còn nhiều thách thức cần vượt qua. Các phương pháp thống kê có thể gặp khó khăn khi các gen bệnh có mối quan hệ gián tiếp. Các phương pháp học máy yêu cầu một lượng lớn dữ liệu huấn luyện, và việc xác định các gen đột biến liên quan đến bệnh vẫn là một thách thức. Dữ liệu sinh học, với khoảng 22.000 gen, tồn tại trong trạng thái "động" với sự tương tác phức tạp giữa các gen. Do đó, cần có các mô hình tính toán hiệu quả để khai thác dữ liệu sinh học và dự đoán gen mục tiêu. Các mô hình tính toán trên mạng tĩnh và tuần tự có thể không hiệu quả do thời gian tính toán lớn.

2.1. Hạn Chế Của Phương Pháp Thống Kê và Học Máy Hiện Tại

Các phương pháp thống kê dựa trên sự tương đồng đột biến gen có thể gặp khó khăn khi các gen bệnh có mối quan hệ gián tiếp hoặc chức năng tương tự. Các phương pháp học máy yêu cầu một lượng lớn dữ liệu huấn luyện, và việc xác định các gen đột biến liên quan đến bệnh vẫn còn là một thách thức. "Các phương pháp dựa trên học 10 máy bao gồm cả học sâu đều cần một tập mẫu lớn rõ các gen ung thư đã biết, các đặc trưng trên tập mẫu rõ có thể được trích xuất và gán nhãn làm đầu vào của quá trình học, để xác định các gen trên tập kiểm tra.".

2.2. Tính Động Của Mạng Sinh Học Yêu Cầu Mô Hình Phù Hợp

Dữ liệu sinh học, với khoảng 22.000 gen, tồn tại trong trạng thái "động" với sự tương tác phức tạp giữa các gen. Các mô hình tính toán trên mạng tĩnh và tuần tự có thể không hiệu quả do thời gian tính toán lớn. Cần có các mô hình tính toán hiệu quả để khai thác dữ liệu sinh học và dự đoán gen mục tiêu. "Dữ liệu sinh học ở người được cho là gồm khoảng 22.000 gen và tồn tại trong trạng thái “động”, chúng tồn tại trong sự tương tác lẫn nhau như kích hoạt, ức chế, trao đổi chất, tuyền tín hiệu và kiểm soát lẫn nhau [11]."

2.3. Yêu Cầu Về Hiệu Suất Tính Toán Trong Phân Tích Dữ Liệu Lớn

Việc phân tích dữ liệu gen ung thư quy mô lớn đòi hỏi hiệu suất tính toán cao. Các mô hình và thuật toán cần được thiết kế để xử lý lượng lớn dữ liệu một cách hiệu quả. Các phương pháp tính toán hiệu năng cao, như tính toán song song, có thể giúp giải quyết vấn đề này.

III. Mô Hình Động Lực Cạnh Tranh Giải Pháp Dự Đoán Gen Ung Thư

Để giải quyết những thách thức trên, luận án này đề xuất một mô hình động lực cạnh tranh trong mạng thông tin phức hợp để dự đoán gen mục tiêu điều trị ung thư. Mô hình động lực cạnh tranh thể hiện sự cạnh tranh giữa các tác nhân trong mạng. Cách tiếp cận này có thể giúp xác định các đỉnh quan trọng trong mạng và có thể liên quan đến mục tiêu dự đoán. Các đỉnh có thứ hạng cao sẽ được đưa vào thực nghiệm lâm sàng để khẳng định chức năng của gen có liên quan đến bệnh hay không. Mô hình hóa toán học ung thư đóng vai trò then chốt.

3.1. Ý Tưởng Cơ Bản Về Mô Hình Động Lực Cạnh Tranh

Ý tưởng cơ bản của mô hình động lực cạnh tranh là mô hình hóa sự tương tác và cạnh tranh giữa các thành phần trong mạng sinh học. Bằng cách phân tích động lực của sự cạnh tranh này, có thể xác định các thành phần quan trọng, đóng vai trò chính trong sự phát triển của ung thư.

3.2. Ưu Điểm Của Mô Hình Động Lực So Với Mô Hình Tĩnh

Mô hình động lực có thể mô phỏng sự thay đổi và tiến triển của mạng sinh học theo thời gian, trong khi các mô hình tĩnh chỉ cung cấp một bức tranh tĩnh về mạng lưới. Điều này giúp mô hình động nắm bắt được các quá trình sinh học phức tạp hơn và đưa ra dự đoán chính xác hơn.

IV. Xây Dựng Thuật Toán Mô Hình Động Lực Cạnh Tranh

Một thuật toán cho mô hình động lực cạnh tranh đã được xây dựng. Thuật toán này xác định các đỉnh điều khiển trong mạng, có khả năng ứng dụng dự đoán gen điều trị ung thư. Từ đó cho ra thuật toán động lực cạnh tranh ngoài để xác định đỉnh điều khiển mục tiêu trong mạng phức hợp. Thuật toán tập trung vào việc xem xét tất cả các tương tác trực tiếp và gián tiếp từ các đỉnh đến mỗi đỉnh trong mạng, mô hình mạng phức hợp. Nó cũng được thiết kế theo hướng tính toán hiệu năng cao để đảm bảo năng lực thực thi trên các mạng quy mô lớn.

4.1. Các Bước Chính Trong Thuật Toán Mô Hình Cạnh Tranh

Các bước chính trong thuật toán bao gồm khởi tạo trạng thái của các đỉnh, mô phỏng quá trình cạnh tranh giữa các đỉnh, và đánh giá kết quả cạnh tranh để xác định các đỉnh quan trọng. Việc thiết kế thuật toán cần đảm bảo tính hiệu quả và khả năng mở rộng để xử lý các mạng sinh học lớn.

4.2. Tối Ưu Hóa Hiệu Năng Thuật Toán Cho Dữ Liệu Lớn

Để xử lý dữ liệu lớn trong phân tích mạng lưới, cần tối ưu hóa hiệu năng của thuật toán. Các kỹ thuật như tính toán song song, phân tích dữ liệu theo lô, và sử dụng các cấu trúc dữ liệu hiệu quả có thể giúp tăng tốc quá trình tính toán.

V. Ứng Dụng Dự Đoán Gen và Điều Trị Ung Thư Hiệu Quả Hơn

Luận án áp dụng mô hình động lực cạnh tranh trong mạng thông tin phức hợp để dự đoán gen mục tiêu điều trị ung thư. Ứng dụng trên 17 mạng bệnh tín hiệu ung thư. Kết quả dự đoán cho thấy mô hình có khả năng xác định các gen ung thư liên quan đến bệnh, cho thấy ứng dụng thực tiễn cao. Dược lý gen cũng đóng vai trò quan trọng trong việc cá nhân hóa điều trị.

5.1. Kết Quả Dự Đoán Trên Các Mạng Ung Thư Thực Tế

Kết quả dự đoán cho thấy mô hình động lực cạnh tranh có khả năng xác định các gen ung thư liên quan đến bệnh trên các mạng ung thư thực tế. Điều này chứng minh tính khả thi và tiềm năng của mô hình trong việc ứng dụng vào thực tiễn.

5.2. So Sánh Với Các Phương Pháp Dự Đoán Gen Khác

So sánh kết quả dự đoán của mô hình động lực cạnh tranh với các phương pháp dự đoán khác giúp đánh giá hiệu quả của mô hình. Các tiêu chí so sánh có thể bao gồm độ chính xác, độ nhạy, và độ đặc hiệu.

VI. Kết Luận Hướng Phát Triển Của Mô Hình Dự Đoán Gen

Luận án đề xuất một mô hình động lực cạnh tranh ngoài để xác định đỉnh điều khiển mục tiêu trong mạng phức hợp, với khả năng ứng dụng dự đoán gen điều trị ung thư. Đề xuất một mô hình động lực cạnh tranh ngoài cải tiến với khả năng xử lý tương tác gián tiếp giữa các đỉnh mô hình mạng phức hợp, giúp nâng cao khả năng dự đoán gen mục tiêu điều trị ung thư, đặc biệt trên các mạng sinh học có kích thước lớn.

6.1. Tóm Tắt Đóng Góp Của Nghiên Cứu

Nghiên cứu đã đề xuất một mô hình động lực cạnh tranh mới trên các mạng thông tin phức hợp và ứng dụng nó để dự đoán gen mục tiêu điều trị ung thư. Mô hình này có khả năng xử lý tương tác gián tiếp và tính toán hiệu năng cao trên các mạng quy mô lớn.

6.2. Hướng Phát Triển Nghiên Cứu Trong Tương Lai

Hướng phát triển nghiên cứu trong tương lai có thể tập trung vào việc cải thiện độ chính xác của mô hình, mở rộng phạm vi ứng dụng, và tích hợp thêm các loại dữ liệu khác nhau. Ngoài ra, việc phát triển các công cụ và giao diện người dùng thân thiện có thể giúp các nhà nghiên cứu và bác sĩ dễ dàng sử dụng mô hình này.

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

Chương 1. Tổng quan về xếp hạng để dự đoán gen bệnh. Nội dung Chương trình bày tổng quan về bài toán xếp hạng để dự đoán gen điều khiển mà cũng là gen mục tiêu điều trị ung thư. Tiếp theo là các kiến thức cơ bản về lý thuyết đồ thị và mạng phức hợp.

Cuối cùng, luận án trình bày các nghiên cứu liên quan và đề ra nội dung luận án cần giải quyết; - Chương 2. Mô hình động lực cạnh tranh ngoài trên mạng phức hợp, ứng dụng trong dự đoán gen mục tiêu điều trị ung thư. Nội dung Chương đề xuất một mô hình động lực mạng mới trên các mạng phức hợp, gọi là mô hình động lực học cạnh tranh ngoài. Mô hình thể hiện sự cạnh tranh giữa một tác nhân (đỉnh) trong mạng và một tác nhân đối thủ cạnh tranh bên ngoài mạng.

Cuối cùng, ứng dụng mô hình vào dự đoán gen mục tiêu điều trị ung thư trên 17 mạng bệnh tín hiệu ung thư. Tương tác gián tiếp trong mô hình động lực cạnh tranh ngoài, ứng dụng nâng cao hiệu quả dự đoán gen mục tiêu điều trị ung thư. Nội dung Chương đề xuất một mô hình động lực cạnh tranh ngoài cải tiến, mô hình xem xét tất cả các tương tác trực tiếp và gián tiếp từ các đỉnh đến mỗi đỉnh trong mạng. Ngoài ra, luận án thiết kế thuật toán của mô hình theo hướng tính toán hiệu năng cao để đảm bảo năng lực thực thi trên các mạng quy mô lớn.

Áp dụng dự đoán các gen mục tiêu điều trị ung thư cho nhiều loại ung thư khác nhau. - Kết luận và hướng phát triển. TỔNG QUAN VỀ XẾP HẠNG ĐỂ DỰ ĐOÁN GEN MỤC TIÊU ĐIỀU TRỊ UNG THƯ 1. Bài toán xếp hạng để dự đoán gen bệnh Gen là một đoạn xác định của phân tử axit nuclêic (DNA (Deoxyribonucleic Acid) hoặc RNA (Ribonucleic Acid)) có chức năng di truyền nhất định.

Gen có thể thu nạp các đột biến sinh học nằm trong trình tự của chúng, dẫn đến những đột biến, biến thể. Đột biến gen có thể xuất hiện trong quá trình phiên mã tự nhiên hoặc chịu sự tác động của các yếu tố bên ngoài. Gen bị đột biến có thể gây ra một bệnh nào đó ở người [17]. Thuốc được thiết kế nhắm đến các gen đột biến liên quan đến bệnh, có thể làm nhiễu loạn bản sao hoặc ức chế khả năng đột biến của chúng, từng bước kìm hãm sự tiến triển của bệnh, khôi phục chức năng của gen về trạng thái khỏe mạnh [2, 17].

Việc xác định một gen mà đột biến của nó liên quan đến một bệnh nào đó có ý nghĩa quan trọng trong quy trình phát triển thuốc và điều trị bệnh [13]. Bài toán đặt ra là làm thế nào để giảm bớt thời gian và chi phí, đồng thời vẫn đảm bảo được độ chính xác trong việc dự đoán các gen gây bệnh ?.1: Bức tranh tổng quan dự đoán gen mục tiêu điều trị ung thư trên các mạng sinh học. (a) hướng tiếp cận thống kê, (b) hướng tiếp cận học máy, (c) hướng tiếp cận dựa trên mạng, (d) thực nghiệm lâm sàng. 14 quyết vấn đề đó, cách tiếp cận theo hướng mạng lưới đã được giới thiệu, cách tiếp cận này được tiến hành dựa trên việc quan sát thấy rằng các gen liên quan đến cùng một bệnh hoặc những bệnh tương tự thường có xu hướng nằm gần nhau trong cấu trúc tương tác của mạng sinh học [13].

Cách tiếp cận mạng sử dụng các mô hình tính toán trên mạng để sắp xếp các gen, sao cho các gen có khả năng liên quan nhiều nhất đến bệnh được xếp hạng cao hơn. Sau khi xếp hạng, một nhóm nhỏ các gen (một vài gen) có thứ hạng cao sẽ được kiểm tra bằng thực nghiệm, để khẳng định xem các gen này có phải là gen gây bệnh hay không [18]. Để sử dụng được các kỹ thuật xếp hạng gen theo hướng mạng lưới, cần phải có dữ liệu mạng sinh học và các thuật toán, mô hình tính toán để phân tích. Có nhiều nghiên cứu đã sử dụng các thuật toán, mô hình tính toán xếp hạng các đỉnh trong mạng xã hội ứng dụng trong xếp hạng các mạng sinh học, do tính tương đồng về cấu trúc của mạng sinh học với các mạng xã hội [19].

Các thuật toán xếp hạng gen dựa trên mạng đã được phát triển để khai phá chức năng các phân tử sinh học và các liên kết quan trọng giữa chúng [13]. Các nhà khoa học dữ liệu và tin sinh học thường áp dụng xếp hạng tương tác gen/protein dựa trên bộ gen để phục vụ cho các thực nghiệm tiếp sau. Gần đây, trong nước có một số nhóm nghiên cứu đã có những công bố liên quan đến hướng nghiên cứu này, như nhóm của TS. Trần Tiến Dũng ở Trường Đại học Công nghiệp Hà Nội, với một số công bố về dự đoán gen bệnh và gen chỉ dấu ung thư dựa trên việc xếp hạng đỉnh theo thuộc tính mức độ gần gũi theo thứ bậc [12, 20].

Nhóm nghiên cứu của PGS.TS Lê Đức Hậu ở Trường Đại học Thủy lợi, với một số công bố về dự đoán gen bệnh dựa trên xếp hạng gen theo thuộc tính của đỉnh được xác định bởi thuật toán bước nhảy ngẫu nhiên và bước nhảy ngẫu nhiên có quay lại (RWR), nhóm đã cải tiến phương pháp RWR bằng cách tăng cường trọng số hàng xóm của các gen gây bệnh đã biết [21], hay sử dụng mô hình mạng Boolean Network với thử nghiệm dự đoán được 27 gene có liên quan đến bệnh ung thư vú [18]. Nhóm nghiên cứu của PGS.TS Trần Đăng Hưng và TS. Nguyễn Văn Tỉnh ở Trường Đại học Sư phạm Hà Nội, với một số công bố về dự đoán mối liên quan giữa miRNA và bệnh bằng cách sử dụng thuật toán bước nhảy ngẫu nhiên có quay lại và tích hợp nhiều điểm tương đồng [22], hay sử dụng thuật toán lọc cộng tác và phân bổ nguồn lực trên biểu đồ ba bên miRNA-bệnh-lncRNA [23]. Chi tiết nội dung 15 của hai công bố này cũng đã được thể hiện và bảo vệ thành công trong bản luận án tiến sĩ của TS.

Nguyễn Văn Tỉnh năm 2023 tại Trường Đại học Sư phạm Hà Nội. Các phương pháp xếp hạng gen/protein dựa trên mạng phức hợp nhìn chung đã được chứng minh là có độ chính xác cao, nhờ vào việc tích hợp các mối quan hệ liên kết gen đã được chú thích từ các tập nguồn toàn diện vào cơ sở tri thức, như cơ sở dữ liệu STRING [24] và cơ sở dữ liệu HAPPYI 2. Ví dụ về các ứng dụng xếp hạng gen dựa trên mạng bao gồm khám phá các gen bệnh cho các trật tự di truyền phức tạp của người [26], tìm mục tiêu và định vị lại thuốc [27]. Sau đây, luận án phát biểu bài toán xếp hạng để dự đoán gen mục tiêu điều trị ung thư: - Phát biểu bài toán: Cho một mạng sinh học gồm các gen/protein được cho là có liên quan đến bệnh, các đỉnh biểu thị các gen/protein và các cạnh thể hiện sự tương tác giữa chúng.

Dự đoán các gen/protein (đỉnh) mà đột biến của chúng có liên quan đến sự phát triển một bệnh nào đó ở người và là mục tiêu tác động của thuốc điều trị; - Đầu vào: Cho trước một mạng sinh học G = (V, E), với V là tập đỉnh (các phân tử sinh học như gen/protein) (𝑉 = {𝑣1, 𝑣2 , … , 𝑣𝑛 } E là tập cạnh (tương tác giữa các phần tử sinh học) (𝐸 = {(𝑣𝑖 , 𝑣𝑗 )|𝑣𝑖 , 𝑣𝑗 ∈ 𝑉, 𝑖, 𝑗 = 1,. , 𝑛}); - Đầu ra: Một mối quan hệ S(V, F), trong đó V là tập đỉnh; FR* cho biết khả năng đột biến của gen v gây ra ung thư và là mục tiêu điều trị. Các báo cáo trước đây đã đề cập, xếp hạng theo mức độ thuộc tính gần gũi và thuộc tính gần gũi theo thứ bậc của một đỉnh so với các đỉnh khác trong mạng được sử dụng để xếp hạng các gen bệnh [12, 13]. Trong đó thuộc tính các phép đo này coi là thuộc tính F của quan hệ đầu ra S(V, F).

Cơ sở lý thuyết Cấu trúc mạng sinh học đề cập đến các vấn đề của mối quan hệ phức tạp giữa các thành phần sinh học như gen/protein và các sản phẩm của tế bào. Vì vậy, việc khai phá dữ liệu sinh học có thể được quy về bài toán khai phá dữ liệu trên các mạng phức hợp. Việc này có thể được thực hiện bằng các mô hình tính toán và thuật toán trên mạng. Để làm được điều đó, người ta thường biểu diễn chúng dưới dạng một đồ thị và sử dụng các kỹ thuật tính toán trên đồ thị và mạng phức hợp để giải quyết.

Sau đây luận án trình bày một số kiến thức cơ 16 bản về lý thuyết đồ thị và mạng phức hợp, làm cơ sở cho việc đề xuất các mô hình tính toán và thuật toán cho việc giải quyết bài toán đặt ra. Lý thuyết đồ thị Đồ thị là một công cụ mô hình hóa quan hệ giữa các đối tượng trong một hệ thống, ở đó mỗi đối tượng là một đỉnh và quan hệ giữa chúng được hiểu là cạnh liên kết chúng. Trong phân tích mạng phức hợp, đồ thị được sử dụng để biểu diễn mạng phức hợp, trong đó các đỉnh đại diện cho các đơn vị trong hệ thống và các cạnh đại diện cho các liên kết giữa chúng. Sau đây luận án trình bày một số khái niệm cơ bản về đồ thị: - Đỉnh là các thành phần của hệ thống được biểu diễn bởi các điểm trên đồ thị; - Cạnh là thành phần liên kết giữa các đỉnh được biểu diễn bởi các đường nối trên đồ thị.

Các cạnh có thể được đánh số hoặc không (trọng số cạnh); - Đường đi là một chuỗi các đỉnh kết nối với nhau bởi các cạnh. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương. Trên đồ thị vô hướng G = (V, E) là dãy x0, x1,…, xn-1, xn; trong đó u = x0, v = xn, (xi , xi+1) E, i = 0, 1, 2,…, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), …, (xn-1, xn).

Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại; - Bậc của đỉnh: Trong lý thuyết đồ thị, bậc của một đỉnh v là số cạnh liên thuộc với v (trong đó, khuyên được tính hai lần). Bậc của v được ký hiệu là deg(v).