Tóm tắt Luận án Tiến sĩ Sinh học: Mở rộng độ đo thông tin tương hỗ để tái tạo mạng trao đổi chất

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

9
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài nghiên cứu nhằm mở rộng độ đo Thông tin tương hỗ để tái tạo mạng trao đổi chất; tái tạo mạng trao đổi chất từ dữ liệu sinh học. Để hiểu rõ hơn về đề tài, mời các bạn cùng tham khảo nội dung chi tiết luận án!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Sinh học: Mở rộng độ đo thông tin tương hỗ để tái tạo mạng trao đổi chất

Chương 1 MỞ ĐẦU 1.1 Giới thiệu Trong khoảng một thập kỷ gần đây, với sự phát triển nhanh chóng của ngành Công nghệ sinh học, dữ liệu sinh học được sinh ra ngày một nhiều. Chẳng hạn, dữ liệu biểu hiện gien (gene expression data), dữ liệu biểu sinh gien (epigenetic data), dữ liệu tương tác protein (protein interaction data), dữ liệu phổ khối lượng của mẫu sinh học (metabolomic data). Các loại dữ liệu này gọi chung là dữ liệu sinh học hệ thống (high-throughput data) và thường được coi là "ảnh chụp" của các tổ chức sinh học. Việc phân tích các dữ liệu sinh học hệ thống để từ đó có thể xây dựng lại các mạng sinh học gọi là tái tạo mạng (network reconstruction). Bài toán tái tạo mạng sinh học là một loại bài toán ngược. Đây là một bài toán quan trọng và đang là thách thức của ngành sinh học hệ thống. Việc tái tạo mạng sinh học giúp chúng ta làm sáng tỏ bản chất của các quá trình sinh học phức tạp và các cơ chế gây bệnh xảy ra bên trong tổ chức sinh học. Đặc biệt, giúp chúng ta có thể tiên lượng, chẩn đoán các tác nhân, chỉ dấu sinh học gây bệnh. Từ đó, giúp con người có thể can thiệp kịp thời và chính xác vào các quá trình đó như: lựa chọn chế độ dinh dưỡng, đưa ra phác đồ điều trị bệnh, điều chế thuốc, . . . . Trong một tổ chức sinh học, mọi tiến trình sinh học đều được điều khiển bởi các phần tử cơ bản như: gen, protein, metabolite. Quan hệ giữa các phần tử cơ bản trong tế bào sẽ quyết định đến chức năng của tế bào. Do đó, từ dữ liệu sinh học, quá trình tái tạo mạng sinh học thông qua các mối quan hệ giữa các phần tử sẽ cho chúng ta bức tranh tổng thể của sự sống. Cho đến nay, có hai cách tiếp cận tái tạo mạng sinh học: cách tiếp cận thực nghiệm trong lĩnh vực Sinh học và cách tiếp cận tính toán trong lĩnh vực Tin-Sinh. Với cách tiếp cận thực nghiệm, các nhà thực nghiệm Sinh học sử dụng các phương tiện của công nghệ sinh học để đo đạc sự liên kết giữa các phần tử, sau đó kết hợp với tri thức chuyên gia để tái tạo lại mô hình mạng sinh học. Cách tiếp cận này thường cho kết quả chính xác, nhưng chi phí thực nghiệm và thời gian tái tạo mạng sinh học hoàn chỉnh rất lớn. Cách tiếp cận tính toán trong lĩnh vực Tin-Sinh lại sử dụng sức mạnh tính toán của máy tính, các thuật toán, các mô hình để xây dựng cấu trúc mạng phù hợp với dữ liệu quan sát nhất. Kết quả là thu được mô hình mạng, ở đó các nút biểu diễn các phần tử sinh học, các cạnh biểu diễn quan hệ giữa chúng. Mặc dù, mạng tái tạo được bằng cách này có thể còn khác so với mạng được tái tạo bằng thực nghiệm, nhưng quá trình đó có ý nghĩa quan trọng trên con đường tiến tới tái tạo mạng sinh học đầy đủ. Quá trình đó sẽ giúp các nhà Sinh học có định hướng tốt hơn trong các thực nghiệm, giảm thời gian và chi phí thực nghiệm. Ngoài ra, tái tạo mạng sinh học bằng cách tiếp cận tính toán có thể dự đoán được các mối quan hệ giữa các phần tử sinh 1
học, mà có thể, với cách tiếp cận thực nghiệm chưa tìm được. Chính vì vậy, trong khuôn khổ luận án này, chúng tôi sử dụng cách tiếp cận tính toán để tái tạo mạng sinh học từ dữ liệu. 1.2 Bối cảnh thực hiện luận án Ý tưởng về mô hình hóa các quá trình sinh học bằng các mạng gồm các nút và các cạnh là một vẫn đề hấp dẫn. Việc tìm ra các cạnh nối các nút trong mạng rất quan trọng, vì từ đó sẽ xác định nhóm các phần tử cùng thực hiện một chức năng hoặc cùng tham gia vào một con đường sinh học, đây là một vấn đề quan trọng trong sinh học hệ thống. Cho đến nay, đã có nhiều hướng nghiên cứu giải quyết bài toán tái tạo mạng, mỗi hướng đều có ưu điểm và nhược điểm [He et al., 2009], [Villaverde et al., 2013], [Wang et al., 2014]. Một cách tiếp cận sử dụng mô hình toán học trong tái tạo mạng đó là dựa trên phương trình vi phân, tích phân (differential and integral equations) [Gardner et al., 2003], [Mazur et al.,2009], [Steuer et al., 2003]. Trong phương pháp này, tác động của các phần tử lên một phần tử nào đó được biểu diễn bằng một phương trình vi phân tuyến tính. Như vậy, đối với tất cả các phần tử, ta sẽ có một hệ phương trình. Mô hình này có ưu điểm là đơn giản vì đã có cách giải phương trình vi phân tuyến tính. Tuy nhiên, trong thực tế, dữ liệu biểu hiện của các phần tử trong tế bào lại thường không tuân theo qui luật đơn giản như vậy. Hơn nữa, do mô hình đòi hỏi nhiều tham số nên chi phí ước lượng lớn. Một cách tiếp cận khác để tái tạo mạng sinh học đó là sử dụng mô hình đồ thị (graphical models). Đây là cách tiếp cận được nhiều người sử dụng và đã có nhiều kết quả nghiên cứu. Mạng logic (boolean network ) là một trong những mô hình mạng sớm nhất được đề xuất năm 1969 bởi Kauffman, được biểu diễn đơn giản bằng một đồ thị có hướng. Mạng logic có ưu điểm là một mô hình đơn giản nhất để biểu diễn một mạng thực. Tuy nhiên, nhược điểm lớn nhất của mô hình này là đòi hỏi thời gian tính toán rất cao để xây dựng cấu trúc mạng đáng tin cậy. Do đó, phương pháp này thường chỉ áp dụng trên mạng nhỏ, không áp dụng để xây dựng mạng có qui mô lớn [Trairatphisan et al., 2013]. Một sự kết hợp của mô hình đồ thị và mô hình xác suất đó là mô hình đồ thị xác suất (probabilistic graphical models) [Jordan, 1998], [Kauffman et al., 2003], [Wang et al., 2014]. Đây là mô hình xác suất sử dụng đồ thị để biểu diễn sự phụ thuộc có điều kiện giữa các biến ngẫu nhiên một cách trực quan. Mục đích của cách tiếp cận mô hình đồ thị là tìm ra cấu trúc mạng phù hợp nhất với dữ liệu. Có rất nhiều mô hình đồ thị khác nhau đã được sử dụng cho bài toán tái tạo mạng. Trong đó, phải kể đến mô hình đồ thị xác suất thường được sử dụng là mô hình mạng logic xác suất (probabilistic boolean network ) [Trairatphisan et al., 2013], mô hình mạng Bayesian (Bayesian network ) và các biến thể của chúng như: mạng Bayesian động (dynamic Bayesian network ), mô hình Markov ẩn (hidden Markov model ), mạng logic Markov (Markov logic network ), trường ngẫu nhiên Markov (Markov random field ), . . . . Tuy nhiên, thời gian tính toán 2
để tìm được mô hình phù hợp nhất với dữ liệu khá cao. Ngoài ra, cách tiếp cận mô hình đồ thị hướng đến xây dựng cấu trúc mạng toàn cục, mạng được xây dựng theo kiểu top-down. Chính vì vậy, phương pháp này thường bỏ sót các quan hệ mang tính địa phương. Một hướng tiếp cận khác để tái tạo mạng là sử dụng mô hình Lý thuyết thông tin (information theory models). Ý tưởng của phương pháp này là dựa trên các độ đo để tìm ra sự phụ thuộc thống kê giữa các phần tử sinh học. Một số độ đo trong Lý thuyết thông tin, chẳng hạn độ đo Thông tin tương hỗ (mutual information), Hệ số thông tin cực đại (maximal information coefficient-MIC ) có thể phát hiện được các quan hệ cặp đôi, tức là phát hiện sự phụ thuộc giữa hai phần tử. Nhiều nghiên cứu đã sử dụng độ đo Thông tin tương hỗ để tái tạo mạng điều hòa gen và mạng tương tác protein [Butte et al. 2000], [Cakir et al., 2006], [Margolin et al., 2006]. Cách tiếp cận Lý thuyết thông tin thường hướng đến các quan hệ cục bộ, sau đó mở rộng dần dần để xây dựng mạng toàn cục. Nói cách khác, theo cách tiếp cận Lý thuyết thông tin, cấu trúc mạng được xây dựng theo kiểu bottom-up. Do đó, phương pháp này thường không bỏ sót các quan hệ mang tính địa phương. Tóm lại, có nhiều cách tiếp cận để giải quyết bài toán tái tạo mạng sinh học, mỗi cách tiếp cận đều có những ưu điểm và nhược điểm. Phần lớn các nghiên cứu trước đây chỉ tập trung vào việc tìm các quan hệ cặp đôi giữa hai phần tử và cho rằng quan hệ cặp đôi chính là cơ sở để xây dựng mạng quan hệ đa biến. Gần đây, một số nghiên cứu đã xem xét đến mối quan hệ của một phần tử với nhiều phần tử khác trong mạng sinh học. Chẳng hạn, cách tiếp cận mô hình đồ thị và độ đo Thông tin tương hỗ trong tái tạo mạng điều hòa gen [Kinney et al., 2014], [Reshef et al., 2011], [Trairatphisan et al., 2013]. Tuy nhiên, các mối quan hệ đa biến đó lại không phải là các quan hệ xảy ra đồng thời. Trong khi, một phản ứng sinh hóa trong mạng trao đổi chất lại thường chứa đựng mối quan hệ của nhiều chất, đồng thời xảy ra. Do đó, các mối quan hệ như vậy có thể sẽ không được phát hiện bằng các phương pháp đã nêu trên. 1.3 Mục tiêu nghiên cứu của luận án Để tái tạo mạng trao đổi chất, trong luận án này, chúng tôi lựa chọn hướng tiếp cận Lý thuyết thông tin, cụ thể là sử dụng các độ đo Thông tin tương hỗ. Độ đo Thông tin tương hỗ trước đây được áp dụng để phát hiện quan hệ hai biến trong mạng điều hòa gen và mạng tương tác protein do quan hệ trong các mạng này phần lớn là quan hệ hai biến hoặc các quan hệ nhiều biến nhưng có thể suy diễn từ các quan hệ hai biến. Trong mạng trao đổi chất, một phản ứng có thể có nhiều chất tham gia. Do đó, quan hệ giữa các chất thường là các quan hệ ba biến, bốn biến, . . . , hay nói cách khác là các quan hệ đa biến và hơn nữa chúng xảy ra đồng thời. Cho đến nay, một số mở rộng của độ đo Thông tin tương hỗ cũng đã xem xét đến mối quan hệ đa biến. Tuy nhiên, có những kiểu quan hệ chỉ xuất hiện khi có nhiều biến đồng thời cùng tham gia. Chính vì vậy, 3
để tái tạo mạng trao đổi chất, cần phải mở rộng độ đo Thông tin tương hỗ để có thể phát hiện được các quan hệ đa biến xảy ra đồng thời. Như vậy, mục tiêu nghiên cứu của luận án là mở rộng độ đo Thông tin tương hỗ để tái tạo mạng trao đổi chất. Để tái tạo mạng trao đổi chất từ dữ liệu sinh học, chúng tôi sẽ thực hiện hai bước, tương ứng với hai bài toán (Hình 1.1). Bài toán 1 Bài toán 2 Dữ → Tái tạo quan hệ đa biến → Loại bỏ quan hệ dư thừa → Mạng liệu ⇑ ⇑ trao Mở rộng độ đo MI Mở rộng độ đo CMI đổi chất Hình 1.1: Sơ đồ tóm tắt Mục tiêu nghiên cứu của luận án • Bài toán 1: Mở rộng độ đo Thông tin tương hỗ (MI) để tái tạo quan hệ đa biến. • Bài toán 2: Mở rộng độ đo Thông tin tương hỗ có điều kiện (CMI) để phát hiện quan hệ đa biến gián tiếp và loại bỏ quan hệ dư thừa. 1.4 Các đóng góp chính của luận án Luận án có ba đóng góp chính: Thứ nhất: Đề xuất một cách diễn giải trực quan mới và công thức mới cho Thông tin tương hỗ trong trong trường hợp hai biến và ba biến. Cách diễn giải này khắc phục được các nhược điểm của một số cách diễn giải trước đây. Thứ hai: Trên cơ sở đóng góp thứ nhất, đề xuất một công thức tổng quát cho độ đo Thông tin tương hỗ đa biến. Từ công thức tổng quát, có nhiều công thức được suy ra, mỗi công thức phản ánh một loại quan hệ tồn tại giữa các biến. Thứ ba: Đề xuất một công thức tổng quát cho độ đo Thông tin tương hỗ đa biến có điều kiện nhằm phát hiện quan hệ đa biến gián tiếp và loại bỏ các quan hệ dư thừa. 1.5 Tổ chức luận án Luận án gồm 130 trang được chia thành 4 chương. Chương 1: Giới thiệu tổng quan về bài toán tái tạo mạng sinh học, bối cảnh thực hiện luận án, mục tiêu nghiên cứu và những đóng góp chính của luận án. Chương 2: Những kiến thức nền tảng, bao gồm những khái niệm cơ bản trong Tin-Sinh học và các kiến thức liên quan đến một số độ đo trong Lý thuyết thông tin. 4
Chương 3: Giới thiệu một số mở rộng độ đo Thông tin tương hỗ của các tác giả khác. Đề xuất một diễn giải trực quan mới và công thức mới cho Thông tin tương hỗ trong trường hợp hai biến và ba biến. Từ đó, đề xuất một công thức tổng quát cho Thông tin tương hỗ trong trường hợp đa biến. Cuối cùng là một ứng dụng của các độ đo Thông tin tương hỗ đa biến vào bài toán tái tạo mạng trao đổi chất và đánh giá các độ đo này. Chương 4: Đề xuất một công thức tổng quát của độ đo Thông tin tương hỗ đa biến có điều kiện. Ứng dụng của các độ đo Thông tin tương hỗ đa biến có điều kiện trong việc phát hiện các quan hệ đa biến gián tiếp để loại bỏ các quan hệ dư thừa trong mạng trao đổi chất. Cuối cùng là phần Kết luận của luận án. Chương 2 KIẾN THỨC NỀN TẢNG 2.1 Một số khái niệm cơ bản trong Sinh học Mọi sinh vật đều được tạo thành từ vô số tế bào. Tất cả các quá trình sinh học trong tế bào đều được điều khiển bới các phần tử cơ bản trong tế bào như: gien, protein, metabolite. Các phần tử này không hoạt động riêng rẽ mà chúng thường kết hợp với nhau để tạo thành các phức hợp và thực hiện một chức năng nào đó. Tập các phần tử sinh học và các quan hệ giữa chúng tạo thành một mạng sinh học (biological network ). Về mặt hình thức, mạng sinh học thường được biểu diễn bằng đồ thị gồm các nút và các cạnh. Trong đó, nút đại diện cho các phần tử cơ bản trong tế bào, cạnh đại diện cho quan hệ giữa các phần tử cơ bản đó. Mạng tương tác protein (protein-protein interaction network-PIN ) là một mạng sinh học. Trong đó, các nút của mạng là các protein, các cạnh là các tương tác vật lý giữa các protein. Tương tác protein-protein xảy ra khi các protein kết hợp với nhau, thường là để thực hiện chức năng sinh học của chúng. Trong mạng điều hòa gien (gene regulatory network-GRN ), mỗi nút là một gien, mỗi cạnh là một quan hệ điều khiển của gien này đối với gien kia. Một trong các nguồn dữ liệu quan trọng là dữ liệu biểu hiện gien (gene expression data). Dữ liệu biểu hiện gien thường cho dưới dạng ma trận, trong đó mỗi cột tương ứng với mỗi gien và mỗi dòng tương ứng với một thời điểm lấy mẫu hay một điều kiện thí nghiệm. Mỗi ô của ma trận chứa mức độ biểu hiện của gien trong điều kiện tương ứng. Trong mạng trao đổi chất (metabolic network-MN ), mỗi nút là một chất trao đổi (metabolite), là phân tử nhỏ có trong mẫu sinh học. Các chất trao đổi này thường là các chất tham gia phản ứng, các chất xúc tác, các sản phẩm của các phản ứng hóa sinh trong cơ thể sinh học. Mỗi cạnh trong mạng biểu diễn cho một quan hệ chuyển hóa từ chất này sang chất kia. 5
Dữ liệu chuỗi thời gian (time-series) là tập hợp các dữ liệu thu được tại các mốc thời gian, cách nhau một khoảng thời gian nhất định. Dữ liệu time-series được sử dụng trong thống kê, xử lý tín hiệu, nhận dạng mẫu, tài chính, dự báo,. . . . Dựa vào dữ liệu time-series, ta có thể tìm thấy các qui luật của các sự kiện. Vì vậy, mô hình time-series còn được sử dụng để sinh ra các dữ liệu dựa trên các quan sát đã có. Trong quá trình thu thập dữ liệu thường xuất hiện các dữ liệu nhiễu (per- turbation). Dữ liệu nhiễu thường sinh ra do lỗi chương trình, lỗi thiết bị dùng để thu thập dữ liệu hoặc do ảnh hưởng của điều kiện thí nghiệm, . . . . Chúng thường làm ảnh hưởng xấu đến các kết quả phân tích hoặc khai phá dữ liệu. Dữ liệu In silico là dữ liệu sinh học được sinh ra từ máy tính thông qua các mô hình mô phỏng, không phải thu được từ các thí nghiệm sinh học. Nghiên cứu In silico có khả năng làm tăng tốc độ thực hiện và đồng thời làm giảm chi phí khi tiến hành trong phòng thí nghiệm và trên các thử nghiệm lâm sàng. 2.2 Một số khái niệm cơ bản trong Lý thuyết thông tin Định nghĩa 2.1. Entropy của biến ngẫu nhiên rời rạc X, ký hiệu là H(X), đo lượng thông tin không chắc chắn của biến X, được định nghĩa như sau [Shannon, 1948]: X 1 X H(X) = p(x) log =− p(x) log p(x) (2.1) x p(x) x trong đó, p(x) là hàm phân phối xác suất (probability mass function) của X. Khi các biến là liên tục, phép tính tổng trong các công thức được thay bởi phép tính tích phân. Tính chất: H(X) ≥ 0 Định nghĩa 2.2. Entropy đồng thời (joint entropy) của cặp hai biến ngẫu nhiên rời rạc (X, Y ), ký hiệu H(X, Y ), được định nghĩa như sau: X H(X, Y ) = − p(x, y) log p(x, y) (2.2) x,y Tính chất: H(X, Y ) ≤ H(X) + H(Y ) Định nghĩa 2.3. Cho hai biến ngẫu nhiên rời rạc X và Y . Entropy có điều kiện (conditional entropy) của biến X trên điều kiện Y , ký hiệu là H(X|Y ), đo lượng thông tin không chắc chắn của biến X khi đã biết biến Y , được xác định như sau: X p(x, y) H(X|Y ) = − p(x, y) log (2.3) x,y p(y) Tính chất (i) H(X|Y ) ≥ 0 (ii) H(X, Y ) = H(X) + H(Y |X); H(X, Y ) = H(Y ) + H(X|Y ) 6
(iii) H(X|Y ) ≤ H(X) Định nghĩa 2.4. Entropy của n biến ngẫu nhiên rời rạc X1 , . . . , Xn với phân bố xác suất đồng thời p(x1 , . . . , xn ) được xác định bởi: X H(X1 , . . . , Xn ) = − p(x1 , . . . , xn ) log p(x1 , . . . , xn ) (2.4) x1 ,...,xn n P Tính chất: H(X1 , . . . , Xn ) ≤ H(Xi ) i=1 Định nghĩa 2.5. Thông tin tương hỗ (mutual information) của hai biến ngẫu nhiên X và Y , ký hiệu là M I(X, Y ), đo mức độ tương hỗ của hai biến X và Y , được định nghĩa như sau: X p(x, y) M I(X, Y ) = p(x, y) log (2.5) x,y p(x).p(y) = H(X) + H(Y ) − H(X, Y ) (2.6) Khi giá trị độ đo này lớn, có nghĩa rằng mức độ tương hỗ giữa hai biến lớn và ngược lại, giá trị của độ đo bé nghĩa là mức độ tương hỗ của hai biến nhỏ. Tính chất (i) M I(X, Y ) ≥ 0 (ii) M I(X, Y ) = M I(Y, X) (iii) M I(X, Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X) (iv) M I(X, Y ) ≤ H(X); M I(X, Y ) ≤ H(Y ) Định nghĩa 2.6. Thông tin tương hỗ có điều kiện (conditional mutual infor- mation) của hai biến ngẫu nhiên X và Y trên điều kiện Z đo mức độ tương hỗ của hai biến X và Y khi có điều kiện Z, được định nghĩa như sau: X p(x, y|z) M I(X, Y |Z) = p(x, y, z) log (2.7) x,y,z p(x|z).p(y|z) X = p(z)M I(X, Y |Z = z) (2.8) z Một số biểu diễn khác của CMI: M I(X, Y |Z) = H(X, Z) + H(Y, Z) − H(Z) − H(X, Y, Z) (2.9) M I(X, Y |Z) = H(X|Z) + H(Y |Z) − H(X, Y |Z) (2.10) Tính chất: M I(X, Y |Z) ≥ 0 Định nghĩa 2.7. Ba biến ngẫu nhiên X, Y, Z được gọi là tạo thành chuỗi Markov (Markov chain), ký hiệu X → Y → Z, nếu: p(x, y, z) = p(x).p(y|x).p(z|y) (2.11) 7
Bổ đề 2.1. X → Y → Z khi và chỉ khi X và Z độc lập với nhau trên điều kiện Y , tức là M I(X, Z|Y ) = 0 Bổ đề 2.2. Nếu X → Y → Z thì Z → Y → X Định lý 2.1. Bất đẳng thức xử lý dữ liệu (data processing inequality-DPI) Nếu X → Y → Z thì: M I(X, Y ) ≥ M I(X, Z) (2.12) Dấu đẳng thức xảy ra khi và chỉ khi M I(X, Y |Z) = 0 Bổ đề 2.3. Nếu X → Y → Z thì M I(X, Z) ≤ min M I(X, Y ); M I(Y, Z) (2.13) Bổ đề 2.4. Nếu X → Y → Z thì: M I(X, Y |Z) ≤ M I(X, Y ) (2.14) 2.3 Đánh giá tính chính xác của dự đoán Trong phân lớp nhị phân hay trong dự đoán, các kết quả được gán nhãn hoặc là dương (positive-P ) hoặc âm (negative-N ). Có bốn khả năng có thể xảy ra: Nếu kết quả dự đoán là P và giá trị thực tế cũng là P thì khi đó được gọi là true positive-TP. Nếu kết quả dự đoán là P mà giá trị thực là N , thì được gọi là false positive-FP. Ngược lại, nếu kết quả dự đoán và giá trị thực đều là N thì gọi là true negative-TN, và là false negative-FN khi kết quả dự đoán là N , trong khi giá trị thực tế là P . Quan sát dương (P) Quan sát âm (N) Dự đoán dương (P) TP FP Dự đoán âm (N) FN TN Có nhiều thước đo độ chính xác của dự đoán như: Precision, Recall, độ chính xác (Accuracy-ACC ), độ đo F (F-measure), đường cong ROC và diện tích dưới đường cong ROC (area under the curve-AUC ). Trong đó, TP P recision = (2.15) TP + FP TP Recall = (2.16) TP + FN TP + TN ACC = (2.17) TP + FP + TN + FN P recision.Recall 2T P F − measure = 2 = (2.18) P recision + Recall 2T P + F P + F N Một thước đo được sử dụng phổ biến nhất trong khoa học đó là đường cong ROC (Receiver Operating Characteristic). Đường cong ROC được tạo thành từ 8
tập hợp các điểm ứng với các ngưỡng khác nhau. Với mỗi ngưỡng sẽ cho ta một điểm. Mỗi điểm được xác định bởi 2 tọa độ: 1-Specificity (hay còn gọi là False Positive Rate) và Sensitivity (hay còn gọi là True Positive Rate). Trong đó, TP Sensitivity = (2.19) TP + FN FP 1 − Specif icity = (2.20) FP + TN Đường cong ROC có một tính chất quan trọng là: nếu đường cong càng đi dọc theo biên trái và rồi đi dọc theo biên phía trên của không gian ROC, thì chứng tỏ kết quả của dự đoán càng chính xác. Đường cong càng tiến tới thành đường chéo 45o trong không gian ROC, thì độ chính xác của dự đoán càng kém. Tuy nhiên, nếu căn cứ vào các đường cong ROC thì rất khó để kết luận được dự đoán nào tốt hơn. Vì vậy, người ta thường sử dụng phần diện tích dưới đường cong ROC, ký hiệu là AUC, để đánh giá tính chính xác của dự đoán. Đường cong nào có AUC càng lớn thì độ chính xác của dự đoán càng cao và ngược lại, đường cong nào có AUC càng bé thì độ chính xác của dự đoán càng thấp. Chương 3 MỞ RỘNG ĐỘ ĐO THÔNG TIN TƯƠNG HỖ ĐỂ TÁI TẠO QUAN HỆ ĐA BIẾN 3.1 Một số mở rộng độ đo Thông tin tương hỗ 3.1.1 Mở rộng của Watanabe Mở rộng đầu tiên của độ đo Thông tin tương hỗ là độ đo Tương quan tổng hợp (total correlation) do Watanabe đưa ra năm 1960 [Watanabe, 1960]. Định nghĩa 3.1. Cho n biến ngẫu nhiên X1 , . . . , Xn , tương quan tổng hợp của n biến, ký hiệu là T C(X1 , . . . , Xn ), được định nghĩa: X p(x1 , . . . , xn ) T C(X1 , . . . , Xn ) = p(x1 , . . . , xn ) log (3.1) x1 ,...,xn p(x1 ). . . . p(xn ) n X = H(Xi ) − H(X1 , . . . , Xn ) (3.2) i=1 Trong trường hợp ba biến, công thức (3.2) có dạng: T C(X, Y, Z) = H(X) + H(Y ) + H(Z) − H(X, Y, Z) (3.3) Một mở rộng nữa của Watanabe là Tương quan tổng hợp có điều kiện được định nghĩa như sau: 9
Định nghĩa 3.2. Tương quan tổng hợp có điều kiện của n biến ngẫu nhiên X1 , . . . , Xn trên điều kiện Y , ký hiệu là T C(X1 , . . . , Xn |Y ), được định nghĩa: n X T C(X1 , . . . , Xn |Y ) = H(Xi |Y ) − H(X1 , . . . , Xn |Y ) (3.4) i=1 Trong trường hợp ba biến, công thức (3.4) có dạng: T C(X, Y, Z|T ) = H(X|T ) + H(Y |T ) + H(Z|T ) − H(X, Y, Z|T ) (3.5) Độ đo Thông tin tương tác chỉ phản ánh được kiểu quan hệ đồng thời của n biến, không phản ánh được các kiểu quan hệ khác giữa các biến. 3.1.2 Mở rộng của Fano Mở rộng thứ hai của độ đo Thông tin tương hỗ là độ đo Thông tin tương tác (interaction information) do Fano đưa ra năm 1961 [Fano, 1961]. Định nghĩa 3.3. Thông tin tương tác của n biến ngẫu nhiên X1 , . . . , Xn−1 , Xn (với n > 2), được định nghĩa như sau: n X X n+1 M I(X1 , . . . , Xn ) = H(Xi ) − H(Xi , Xj ) + . . . + (−1) H(X1 , . . . , Xn ) (3.6) i=1 1≤i
Hình 3.2: Biểu diễn Thông tin tương hỗ bằng biểu đồ Venn. tương tác giữa hai biến được biểu diễn bằng một hình tròn nhỏ nằm trên đường nối giữa hai hình tròn lớn (Hình 3.3). Khi mở rộng sang trường hợp ba biến, Jakulin và Bratko đưa thêm khái niệm tương tác dương và tương tác âm. Để biểu diễn điều này, các tác giả dùng hình tròn nhỏ màu trắng biểu diễn tương tác dương và hình tròn nhỏ màu xám biểu diễn tương tác âm. Hình 3.3: Biểu đồ tương tác giữa các biến của Jakulin-Bratko. Trong cách biểu diễn này, Jakulin và Bratko chỉ tập trung mô tả cấu trúc tương tác mà không mô tả được mức độ mạnh/yếu của tương tác đó. Cách biểu diễn này có tính trực quan thấp. Nhìn vào hình vẽ, chúng ta không thể nói gì về hình tròn nhỏ trong sự tương quan với các hình tròn lớn biểu diễn các biến X, Y, Z. Tóm lại, trong những mở rộng độ đo Thông tin tương hỗ vừa trình bày, mỗi mở rộng đều có nhược điểm. Mở rộng của Watanabe, Cover và Thomas không biểu diễn được đầy đủ các kiểu quan hệ tồn tại trong trường hợp đa biến. Công thức mở rộng của Fano không biểu diễn chính xác mức độ quan hệ giữa các biến. Mở rộng của Jakulin và Bratko lại chỉ biểu diễn được cấu trúc của tương tác mà không biểu diễn được mức độ của tương tác đó. 3.2 Đề xuất một mở rộng độ đo Thông tin tương hỗ 3.2.1 Đề xuất một diễn giải trực quan và công thức mới cho MI của hai biến Từ những nhược điểm của các mở rộng trình bày trong phần 3.1, chúng tôi đề xuất một phương pháp trực quan mới để biểu diễn Thông tin tương hỗ. Ở đây, chúng tôi mô tả quan hệ giữa hai biến trong một không gian hai chiều (Hình 3.4). Giả sử, ta có dữ liệu quan sát trên hai biến X, Y . Khi đó, entropy 11
của phân bố xác suất của dữ liệu quan sát, ký hiệu là H(pX,Y ), được biểu diễn bằng một hình S có dạng bất kỳ (phần diện tích kẻ ca rô). Khi hai biến X, Y độc lập, entropy của phân bố xác suất của dữ liệu được biểu diễn bằng hình chữ nhật nhỏ nhất chứa S, ký hiệu là H(pX × pY ). Do entropy được biểu diễn qua logarit nên H(pX × pY ) = H(pX ) + H(pY ) = H(X) + H(Y ). Hình 3.4: Đề xuất biểu diễn trực quan mới cho MI của hai biến. Do đó, công thức (2.6) của Shannon, tương đương với công thức (3.8) M I(X, Y ) = H(pX × pY ) − H(pX,Y ) (3.8) Ở đây, H(pX,Y ) và H(pX × pY ) là ký hiệu mới mà chúng tôi đưa ra để sử dụng trong diễn giải của mình. Nếu hình kẻ ca rô S biểu diễn cho H(pX,Y ) càng lớn gần với hình chữ nhật biểu diễn cho H(pX × pY ), khi đó ta kết luận rằng hai biến X và Y độc lập. Ngược lại, nếu S càng thu hẹp so với hình chữ nhật thì điều đó có nghĩa là Thông tin tương hỗ giữa hai biến X, Y càng lớn. Như vậy, từ cách diễn giải trực quan mới cho MI trong trường hợp hai biến, chúng tôi đã đề xuất một công thức biểu diễn mới cho Thông tin tương hỗ (công thức (3.8)). Theo đó, Thông tin tương hỗ của hai biến chính là phần chênh lệch giữa entropy của phân bố xác suất đồng thời với entropy của phân bố xác suất trong trường hợp giả định hai biến độc lập. Về mặt trực quan, Thông tin tương hỗ của hai biến được biểu diễn bằng phần diện tích (kẻ chéo) nằm giữa hình chữ nhật và hình kẻ ca rô S. Công thức (3.8) sẽ là cơ sở cho việc mở rộng độ đo Thông tin tương hỗ cho trường hợp ba biến trong phần tiếp theo. 3.2.2 Đề xuất một diễn giải trực quan và công thức mới cho MI của ba biến Khi mở rộng sang trường hợp ba biến, ngoài các quan hệ cặp đôi giữa các biến, ta có thêm các kiểu quan hệ khác như: quan hệ đồng thời giữa ba biến và quan hệ giữa một biến với cặp hai biến còn lại. Chúng tôi sẽ tiếp tục mở rộng công thức (3.8) đối với hai kiểu quan hệ trên. 12
• Kiểu quan hệ thứ nhất: ba biến có quan hệ đồng thời với nhau. Từ dạng công thức (3.8), chúng tôi đề xuất công thức mở rộng cho kiểu quan hệ này như sau: M I(X, Y, Z) = H(pX × pY × pZ ) − H(pX,Y,Z ) (3.9) Giả sử, ta có dữ liệu quan sát, được biểu diễn trực quan bằng một khối S 0 có hình dạng méo mó như trong Hình 3.5. Khi đó, H(pX,Y,Z ) là entropy của phân bố xác suất của dữ liệu quan sát trên ba biến X, Y, Z. Trong trường hợp ba biến độc lập, entropy của phân bố xác suất của dữ liệu là hình hộp chứa khối S 0 . Khi đó, H(pX,Y,Z ) = H(pX × pY × pZ ) = H(pX ) + H(pY ) + H(pZ ) = H(X) + H(Y ) + H(Z). Do đó, công thức (3.9) tương đương với công thức: M I(X, Y, Z) = H(X) + H(Y ) + H(Z) − H(X, Y, Z) (3.10) Hình 3.5: Biểu diễn trực quan M I(X, Y, Z). Chúng tôi gọi độ đo thông tin tương hỗ của ba biến trong trường hợp này là Thông tin tương hỗ tổng hợp của ba biến. Công thức (3.10) chính là công thức T C(X, Y, Z) đo tương quan tổng hợp của ba biến mà Watanabe đã đưa ra. Nếu hình S 0 khớp với hình hộp, ta nói rằng ba biến X, Y, Z độc lập. Ngược lại, nếu S 0 càng thu hẹp so với hình hộp thì chúng ta có thể khẳng định rằng ba biến X, Y, Z phụ thuộc. Như vậy, căn cứ vào khoảng chênh lệch giữa S 0 và hình hộp, có thể đi đến kết luận rằng ba biến là độc lập hay phụ thuộc. • Kiểu quan hệ thứ hai: một biến có quan hệ với cặp hai biến còn lại. Chúng tôi đề xuất công thức mở rộng cho kiểu quan hệ này như sau: M I(Z, [X, Y ]) = H(pZ × pX,Y ) − H(pX,Y,Z ) (3.11) Khi X và Y độc lập với Z, entropy của phân bố xác suất của dữ liệu là hình trụ chứa khối S 0 (Hình 3.6). Khi đó, H(pX,Y,Z ) = H(pZ × pX,Y ) = 13
H(pZ ) + H(pX,Y ) = H(Z) + H(X, Y ). Do đó, công thức (3.11) tương đương với công thức: M I(Z, [X, Y ]) = H(Z) + H(X, Y ) − H(X, Y, Z) (3.12) Chúng tôi gọi độ đo thông tin tương hỗ của ba biến trong trường hợp này là Thông tin tương hỗ bộ phận giữa một biến với cặp hai biến. Hình 3.6: Biểu diễn trực quan M I(Z, [X, Y ]). Tương tự, trong trường hợp X có quan hệ với cặp biến [Y, Z]; Y có quan hệ với cặp biến [Z, X], ta có các công thức: M I X, [Y, Z] = H(pX × pY,Z ) − H(pX,Y,Z ) (3.13) = H(X) + H(Y, Z) − H(X, Y, Z) (3.14) M I Y, [Z, X] = H(pY × pZ,X ) − H(pX,Y,Z ) (3.15) = H(Y ) + H(Z, X) − H(X, Y, Z) (3.16) Từ đó, ta thấy mỗi loại thông tin tương hỗ cung cấp cho ta một kiểu quan hệ trong mối quan hệ đa biến. Ví dụ, M I(X, Y ) cho biết mức độ tương hỗ giữa biến X và Y ; M I Z, [X, Y ] đo mức độ tương hỗ giữa biến Z và cặp biến [X, Y ]; thông tin tương hỗ tổng hợp M I(X, Y, Z) cho ta biết mức độ tương hỗ đồng thời giữa ba biến X, Y, Z. 3.2.3 Mở rộng độ đo Thông tin tương hỗ cho nhiều biến Từ các diễn giải trong trường hợp ba biến, chúng ta thấy rằng, khi mở rộng sang nhiều biến, sẽ xuất hiện nhiều kiểu quan hệ. Mỗi một kiểu quan hệ sẽ tương ứng với một phân bố xác suất biên hay một phân hoạch {D1 , . . . , Dk } của tập các biến X1 , . . . , Xn . Từ các công thức mở rộng độ đo MI trong trường hợp ba biến vừa trình bày, chúng tôi đề xuất một công thức tổng quát cho Thông tin tương hỗ đa biến như sau: 14
Định nghĩa 3.4. Thông tin tương hỗ của n biến X1 , . . . , Xn với tập phân hoạch {D1 , . . . , Dk } được định nghĩa: M I{D1 ,...,Dk } (X1 , . . . , Xn ) = H(pD1 × . . . × pDk ) − H(pX1 ,...,Xn ) (3.17) tương đương với k X M I{D1 ,...,Dk } (X1 , . . . , Xn ) = H(Di ) − H(X1 , . . . , Xn ) (3.18) i=1 trong đó, {X1 , . . . , Xn } = D1 ⊕ . . . ⊕ Dk ; pDi là phân bố xác suất biên của phân bố xác suất đồng thời pX1 ,...,Xn trên tập con Di của các biến. Trong trường hợp đặc biệt Di = {Xi }, công thức (3.18) được viết như sau: n X M I(X1 , . . . , Xn ) = H(Xi ) − H(X1 , . . . , Xn ) (3.19) i=1 Đây chính là công thức T C(X1 , . . . , Xn ) đo tương quan tổng hợp của n biến. 3.3 Ứng dụng MI đa biến trong tái tạo mạng trao đổi chất 3.3.1 Tái tạo quan hệ đa biến Trong phần này, chúng tôi sử dụng dữ liệu trao đổi chất trong tế bào hồng cầu (red blood cell-RBC ) được công bố bởi Nemenman và các cộng sự [Nemen- man et al.,2007] để tái tạo mạng. Đây là dữ liệu biểu diễn dưới dạng một ma trận 1000 × 39 mô tả nồng độ phân tử Mol của 39 chất trao đổi, tham gia trong 44 phản ứng được đo tại 1000 mốc thời gian. Dữ liệu này có thể tải về từ địa chỉ http://menem.com/∼ilya/wiki/index.php/RBC _Metabolic_Network. Chúng tôi sử dụng MATLAB để tính toán tái tạo mạng RBC gồm 39 chất trao đổi. Ở đây, chúng tôi sử dụng phương pháp ước lượng thông tin tương hỗ dựa trên phân bố xác suất Gaussian. Trước hết, để tái tạo quan hệ cặp đôi, chúng tôi sẽ sử dụng công thức tính MI của hai biến. Số lượng các cặp đôi trong mạng trao đổi chất 2 RBC là C39 = 741. Sau khi có được 714 giá trị M I(X, Y ), chúng tôi có một ma trận 4 cột và 714 dòng. Cột thứ nhất tương ứng với biến X, cột thứ hai tương ứng với Y , cột thứ ba là giá trị M I(X, Y ) tương ứng, cột thứ tư nhận giá trị 1 nếu trong mạng RBC tồn tại cạnh nối giữa X và Y , ngược lại cột thứ tư sẽ nhận giá trị 0. Sau đó, chúng tôi sắp xếp ma trận theo thứ tự giảm dần của cột M I(X, Y ). Độ chính xác của dự đoán tái tạo quan hệ cặp đôi là AUC=0.753. 3 Tương tự như vậy, để tái tạo quan hệ giữa ba biến, chúng tôi tính C39 = 9.139 giá trị MI tổng hợp M I(X, Y, Z) và 27.417 giá trị MI bộ phận. Kết quả thực nghiệm cho thấy các độ đo đề xuất có khả năng tái tạo được các tương tác đa biến, chẳng hạn, diện tích dưới đường cong ROC của mạng tái tạo bằng độ đo Thông tin tương hỗ tổng hợp là AUC=0.874. Sau đây, chúng tôi sẽ minh họa quá trình tái tạo mạng con gồm 10 chất đầu tiên (viết tắt là RBC10) của mạng RBC. Bảng 3.1 hiển thị 20 quan hệ cặp đôi 15
Bảng 3.1: Các quan hệ cặp đôi được tái tạo trong mạng RBC10 n X, Y Thứ tự M I(X, Y ) Phản ứng 1 G6P,F6P (1,2) 8.22 pgi 2 DHAP,GAP (4,5) 7.58 tip 3 PG2,PEP (9,10) 5.77 en 4 PG3,PG2 (8,9) 5.44 pgm 5 PG3,PEP (8,10) 5.07 pgm,en 6 FDP,DHAP (3,4) 3.78 ald 7 FDP,GAP (3,5) 3.77 ald 8 GAP,PG3 (5,8) 1.87 gapdh,pgk 9 DPG13,PG3 (6,8) 1.33 pgk 10 DPG13,PG2 (6,9) 1.33 pgk,pgm 11 DPG13,DPG23 (6,7) 1.26 dpgm 12 GAP,DPG13 (5,6) 1.21 gapdh 13 F6P,FDP (2,3) 1.06 pfk 14 G6P,FDP (1,3) 1.05 hk,pgi 15 F6P,DHAP (2,4) 0.98 pfk,ald 16 F6P,GAP (2,5) 0.96 tald 17 DHAP,DPG13 (4,6) 0.82 tpi,gapdh 18 DPG23,PG2 (7,9) 0.71 dpgase, pgm 19 DPG23,PG3 (7,8) 0.70 dpgase 20 DHAP,PG3 (4,8) 0.68 tpi,gap,pgk có giá trị M I(X, Y ) lớn nhất trong mạng RBC10, được sắp theo thứ tự giảm dần. Bảng 3.2 hiển thị 7 quan hệ bộ ba có giá trị M I(X, Y, Z) lớn nhất trong mạng RBC10. Đây là các quan hệ bộ ba thường là các sản phẩm hoặc chất nền của cùng một phản ứng hoặc các phản ứng liền kề trong mô hình trao đổi chất RBC. Ví dụ, (3, 4, 5) là (F DP, DHAP, GAP ) liên quan tới hai phản ứng liền kề là ald và tpi; (8, 9, 10) là (P G3, P G2, P EP ) liên quan tới hai phản ứng liền kề là pgm và en. Bảng 3.2: Các quan hệ bộ ba được tái tạo trong mạng RBC10 n X, Y, Z Thứ tự M I X, [Y, Z] M I Y, [Z, X] M I Z, [X, Y ] M I(X, Y, Z) 1 FDP, DHAP, GAP (3,4,5) 3.78 7.58 7.58 11.36 2 PG3,PG2, PEP (8,9,10) 5.52 6.21 5.85 11.29 3 G6P, F6P, FDP (1,2,3) 8.22 8.22 0.75 9.98 4 DHAP,GAP, DPG13 (4,5,6) 7.57 7.57 1.00 8.57 5 DHAP,GAP, PG3 (4,5,8) 7.58 7.58 1.87 8.54 6 DPG13,PG3,PG2 (6,8,9) 1.35 5.46 5.46 6.98 7 G6P, F6P, DHAP (1,2,4) 5.22 5.22 0.72 6.95 Chọn ngưỡng θ2 = 0.9 đối với MI của hai biến và ngưỡng θ3 = 10 đối với MI của ba biến. Khi đó, chúng tôi tái tạo được mạng gồm các quan hệ cặp đôi và bộ ba của RBC10. Trong Hình 3.7, chúng tôi so sánh mạng được tái tạo bằng các độ đo MI đa biến với mạng được tái tạo bằng thực nghiệm của các nhà 16
Sinh học (gọi tắt là mạng đích). Nét liền là những quan hệ cặp đôi được tái tạo trùng khớp với mạng đích và nét đứt là những quan hệ cặp đôi được tái tạo không khớp với mạng đích. Chấm tròn nối ba đường nét liền là những quan hệ bộ ba được tái tạo trùng khớp với mạng đích và chấm tròn nối ba đường nét đứt biểu diễn cho quan hệ bộ ba được tái tạo không khớp với mạng đích. (a) (b) Hình 3.7: So sánh mạng tái tạo nhờ MI đa biến (b) với mạng đích (a) Với mạng kết quả tái tạo được, chúng tôi đánh giá tính chính xác của dự đoán tái tạo các quan hệ cặp đôi và quan hệ bộ ba thông qua các độ đo đã trình bày trong Chương 2 (Bảng 3.3). Bảng 3.3: Độ chính xác của dự đoán tái tạo các quan hệ trong mạng RBC10 Kiểu quan hệ TP FP FN TN Precision Recall ACC F-measure Cặp đôi 11 5 1 28 0.69 0.92 0.87 0.79 Bộ ba 1 1 0 118 0.5 1 0.99 0.67 Mạng được tái tạo bằng độ đo MI đa biến gồm 16 quan hệ cặp đôi, 2 quan hệ bộ ba. So với mạng đích được tái tạo bằng thực nghiệm, ta thấy có 5 quan 17
hệ cặp đôi và 1 quan hệ bộ ba tái tạo không khớp. Ngoài ra, có 1 quan hệ cặp đôi không được tái tạo là (DP G23, P G3). 3.3.2 Đánh giá các độ đo đề xuất Để so sánh các độ đo chúng tôi đề xuất với các độ đo của các tác giả khác, chúng tôi sử dụng dữ liệu DREAM3 gồm 15 tập dữ liệu, trong đó có 5 tập dữ liệu kích thước 10 (dữ liệu của mạng 10 gien), 5 tập kích thước 50 và 5 tập kích thước 100. Chúng tôi sẽ so sánh hiệu năng của ba độ đo: Thông tin tương tác do Fano đưa ra (viết tắt là InteractInfo), Thông tin tương hỗ tổng hợp (viết tắt là TotalMI ) và Thông tin tương hỗ bộ phận. Trong trường hợp ba biến, có ba giá trị Thông tin tương hỗ bộ phận. Vì vậy, chúng tôi chọn giá trị nhỏ nhất trong ba giá trị đó để so sánh, gọi giá trị đó là RelationshipMI. RelationshipM I(X, Y, Z) = min M I X, [Y, Z] ; M I Y, [Z, X] ; M I Z, [X, Y ] (3.20) Bảng 3.4 cho thấy hiệu năng của các độ đo trong việc tái tạo các quan hệ bộ ba trên các mạng khác nhau của dữ liệu DREAM3. Trung bình AUC của InteractInfo, TotalMI và RelationshipMI trên 15 bộ dữ liệu tương ứng là 0.52, 0.66 và 0.68. Kết quả thực nghiệm cho thấy, độ đo RelationshipMI và TotalMI có hiệu năng tái tạo quan hệ bộ ba tốt hơn độ đo InteractInfo. Bảng 3.4: So sánh hiệu năng của các độ đo trong tái tạo các quan hệ bộ ba trên dữ liệu DREAM3. Các độ đo K.thước Ecoli1 Ecoli2 Yeast1 Yeast2 Yeast3 TB TB trên mạng 15 bộ dl 10 0.20 0.56 0.34 0.62 0.51 0.45 InteractInfo 50 0.70 0.64 0.38 0.51 0.57 0.56 0.52 100 0.69 0.57 0.49 0.45 0.48 0.54 10 0.66 0.73 0.83 0.69 0.56 0.69 TotalMI 50 0.85 0.73 0.53 0.60 0.68 0.68 0.66 100 0.79 0.63 0.59 0.50 0.52 0.61 10 0.74 0.79 0.89 0.66 0.52 0.72 RelationshipMI 50 0.85 0.75 0.58 0.63 0.68 0.70 0.68 100 0.80 0.68 0.61 0.50 0.53 0.63 3.4 Kết luận Chương 3 Trong Chương 3, chúng tôi đã đề xuất một cách diễn giải trực quan và công thức mới cho Thông tin tương hỗ trong trường hợp hai biến và ba biến. Từ đó, chúng tôi đề xuất một công thức tổng quát cho Thông tin tương hỗ đa biến. Trong phần cuối của Chương 3, chúng tôi đã trình bày một ứng dụng các độ đo mở rộng vào bài toán tái tạo mạng trao đổi chất trong tế bào hồng cầu gồm 39 chất. Kết quả thực nghiệm cho thấy các độ đo mà chúng tôi đề xuất có khả năng tái tạo tốt các quan hệ đa biến. Ngoài ra, để đánh giá hiệu năng của các độ đo đề xuất, chúng tôi đã tiến hành thực nghiệm trên các loại dữ liệu khác nhau với các kích thước khác nhau, kết quả cho thấy các độ đo đề xuất có thể sử dụng để phát hiện các quan hệ đa biến trong mạng sinh học. Như vậy, so với mục tiêu nghiên cứu của Luận án, chúng tôi đã giải quyết được Bài toán 1. 18
Chương 4 MỞ RỘNG ĐỘ ĐO THÔNG TIN TƯƠNG HỖ CÓ ĐIỀU KIỆN ĐỂ PHÁT HIỆN QUAN HỆ ĐA BIẾN GIÁN TIẾP Mặc dù các độ đo Thông tin tương hỗ đề xuất trong Chương 3 đã tái tạo được các quan hệ đa biến nhưng một số quan hệ được tái tạo lại dư thừa do đã tồn tại các mối quan hệ gián tiếp. Trong Chương 4, chúng tôi sẽ tiếp tục mở rộng độ đo Thông tin tương hỗ có điều kiện để phát hiện các quan hệ đa biến gián tiếp. 4.1 Thông tin tương hỗ có điều kiện của hai biến Thông tin tương hỗ có điều kiện (conditional mutual information-CMI ) dùng để đo mức độ tương hỗ của hai biến khi có sự xuất hiện của một hay nhiều biến khác. Thông tin tương hỗ có điều kiện của hai biến trên biến thứ ba là trung bình thông tin tương hỗ của hai biến đó tại các giá trị mà biến thứ ba có thể nhận. X M I(X, Y |Z) = p(z)M I(X, Y |Z = z) z = H(X|Z) + H(Y |Z) − H(X, Y |Z) Khi các biến X và Y có mối quan hệ gián tiếp thông qua biến thứ ba (chẳng hạn biến Z), dựa vào độ đo MI ta sẽ phát hiện được sự tồn tại quan hệ giữa X và Y . Nếu quan sát thêm được biến Z thì ta có thể biết thêm thông tin về mối quan hệ này. Bằng cách lấy trung bình thông tin tương hỗ của hai biến X và Y trên biến Z, ta có thể biết được X và Y có quan hệ gián tiếp thông qua Z (ký hiệu, X ↔ Z ↔ Y ) hay không. Khi có sự xuất hiện của biến Z, Thông tin tương hỗ của hai biến X và Y có thể tăng lên hoặc giảm đi. Trong khi M I(X, Y |Z) đo mức độ tương hỗ trung bình giữa hai biến X và Y trên các giá trị của Z thì M I(X, Y ) đo mức độ tương hỗ trên không gian dữ liệu của hai biến X và Y . Nếu M I(X, Y ) lớn và M I(X, Y |Z) cũng lớn, điều đó có nghĩa là Z không ảnh hưởng đến mối quan hệ của X và Y . Khi đó, X và Y hoặc có quan hệ trực tiếp hoặc có quan hệ gián tiếp nhưng không phải qua Z. Nếu M I(X, Y ) lớn nhưng M I(X, Y |Z) nhỏ, điều đó có nghĩa là Z chi phối mối quan hệ giữa X và Y , khi đó ta có quan hệ gián tiếp X ↔ Z ↔ Y . Như vậy, dựa vào độ đo CMI ta có thể phát hiện được các quan hệ gián tiếp giữa hai biến thông qua biến trung gian. Tuy nhiên, độ đo CMI chỉ phát hiện được quan hệ gián tiếp giữa hai biến. Vì vậy, trong phần tiếp theo, chúng tôi đề xuất một mở rộng độ đo CMI cho nhiều biến để phát hiện kiểu quan hệ đa biến gián tiếp. 19
4.2 Mở rộng thông tin tương hỗ có điều kiện Tương tự như đề xuất công thức tổng quát của MI trong Chương 3, chúng tôi đề xuất một mở rộng độ đo Thông tin tương hỗ có điều kiện như sau: Định nghĩa 4.1. Thông tin tương hỗ có điều kiện của n biến X1 , . . . , Xn với phân hoạch {D1 , . . . , Dk } trên điều kiện C được định nghĩa: k X M I{D1 ,...,Dk } (X1 , . . . , Xn |C) = H(Di |C) − H(X1 , . . . , Xn |C) (4.1) i=1 trong đó, {D1 , . . . , Dk } là các phân hoạch của tập các biến {X1 , . . . , Xn }; {X1 , . . . , Xn } = D1 ⊕ . . . ⊕ Dk . Trong trường hợp ba biến, ta có các độ đo sau: • Thông tin tương hỗ tổng hợp của ba biến X, Y, Z trên điều kiện T M I(X, Y, Z|T ) = H(X|T ) + H(Y |T ) + H(Z|T ) − H(X, Y, Z|T ) (4.2) • Thông tin tương hỗ bộ phận giữa một biến với cặp hai biến trên điều kiện T M I(X, [Y, Z]|T ) = H(X|T ) + H(Y, Z|T ) − H(X, Y, Z|T ) (4.3) M I(Y, [Z, X]|T ) = H(Y |T ) + H(Z, X|T ) − H(X, Y, Z|T ) (4.4) M I(Z, [X, Y ]|T ) = H(Z|T ) + H(X, Y |T ) − H(X, Y, Z|T ) (4.5) Ví dụ 4.1. Để khảo sát kiểu quan hệ giữa biến X với cặp hai biến [Y, Z] trên điều kiện T , chúng tôi sinh ngẫu nhiên hai biến Y, Z độc lập. Biến T phụ thuộc vào Y và Z theo quan hệ T = f (Y, Z) + noise1. Biến X phụ thuộc vào biến T , giả sử X = g(T ) + noise2. Bảng 4.5 hiển thị các giá trị tính MI và CMI. Bảng 4.5: Phát hiện quan hệ gián tiếp X ↔ T ↔ [Y, Z] nhờ CMI. n MI(Y,Z) MI T,[Y,Z] MI X,[Y,Z] MI T,[Y,Z]|X MI X,[Y,Z]|T 1 0.0019 2.6680 1.4355 1.2326 0.0001 2 0.0002 2.6469 1.5718 1.0890 0.0138 3 0.0040 2.7685 1.5094 1.2775 0.0184 4 0.0012 2.6481 1.6885 0.9748 0.0152 5 0.0003 2.6646 1.3962 1.2699 0.0015 6 0.0001 2.6413 1.6344 1.0353 0.0284 7 0.0020 2.7581 1.4426 1.3253 0.0097 8 0.0054 2.5400 1.2922 1.2746 0.0269 9 0.0051 2.6122 1.4902 1.1236 0.0017 10 0.0002 2.7149 1.6008 1.1272 0.0130 20