Mở rộng độ đo thông tin tương hỗ có điều kiện cho trường hợp nhiều biến

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 3-12 This paper is available online at MỞ RỘNG ĐỘ ĐO THÔNG TIN TƯƠNG HỖ CÓ ĐIỀU KIỆN CHO TRƯỜNG HỢP NHIỀU BIẾN Nguyễn Quỳnh Diệp∗, Nguyễn Thị Bích Ngọc, Phạm Thọ Hoàn và Trần Đăng Hưng Khoa Công nghệ Thông tin, Trường Đại học Sư Phạm Hà Nội ∗E-mail: diepnq@hnue.edu.vn Tóm tắt. Phân tích dữ liệu biểu hiện gen là một trong những thao tác quan trọng để tìm ra chức năng của các phần tử sinh học. Để có thể hiểu được cơ chế phức tạp của hệ thống sinh học, việc tái tạo mạng điều khiển gen (Gene Regulatory Networks-GRNs) là một nhiệm vụ hết sức quan trọng và đã trở thành một vấn đề thách thức. Trong bài báo này, chúng tôi đề xuất một mở rộng độ đo thông tin tương hỗ có điều kiện (Conditional Mutual Information-CMI) cho trường hợp nhiều biến. Sau đó, chúng tôi trình bày thuật toán Path Consistency Algorithm-PCA. Đây là một phương pháp mới để tái tạo GRNs từ dữ liệu biểu hiện gen bằng cách sử dụng thông tin tương hỗ (MI) và thông tin tương hỗ có điều kiện (CMI). Trong thuật toán này, sự phụ thuộc có điều kiện giữa một cặp gen được biểu diễn bằng CMI giữa chúng. Kết quả thử nghiệm đã xác nhận hiệu quả của phương pháp PCA-CMI tốt hơn so với các phương pháp trước đây. Từ khóa: Phần tử sinh học, mở rộng độ đo, thông tin tương hỗ có điều kiện, phương pháp PCA-CMI. 1. Mở đầu Trong lĩnh vực sinh học phân tử, việc tìm hiểu về tương tác giữa các phân tử của hệ thống sinh học là hết sức quan trọng, đây có thể được xem như là mục tiêu cuối cùng của di truyền học. Mặc dù, toàn bộ hệ gen của con người đã được nghiên cứu và sắp xếp theo trình tự, nhưng hiểu biết về mạng điều khiển gen ở người còn rất hạn chế. Hiện nay, có nhiều phương pháp tiếp cận để tái tạo mạng điều khiển gen GRNs từ dữ liệu biểu hiện gen như: Mô hình đồ thị, chẳng hạn như đồ thị Gauss [9]; mạng Bayes [10]; Phương trình vi phân, tích phân [1, 6]; Phương pháp hồi quy, quy hoạch tuyến tính [2, 8]; Lí thuyết thông tin [3, 4]. Mặc dù, nhiều giải thuật xây dựng mạng đã được công bố nhưng vẫn còn một số hạn chế. Trong bài báo này, theo hướng tiếp cận của Lí thuyết thông tin, chúng tôi đề xuất một mở rộng của độ đo thông tin tương hỗ có điều kiện trong trường hợp nhiều biến. Sau đó, chúng tôi giới thiệu một phương pháp mới sử dụng cả hai độ đo là độ đo thông tin 3 Nguyễn Quỳnh Diệp, Nguyễn Thị Bích Ngọc, Phạm Thọ Hoàn, Trần Đăng Hưng tương hỗ (MI) và độ đo thông tin tương hỗ có điều kiện (CMI) để phát hiện các mối quan hệ giữa các gen, từ đó tái tạo mạng điều khiển gen. Chúng tôi đã tiến hành thực nghiệm trên dữ liệu của loài men nấm với kích thước 10. Kết quả cho thấy mạng xây dựng được nhờ phương pháp này tương đối khớp với mạng thực. 2. Nội dung nghiên cứu 2.1. Một số khái niệm cơ bản 2.1.1. Entropy của một biến Một khái niệm cơ bản của Lí thuyết thông tin là Entropy. Entropy của một biến ngẫu nhiên X , kí hiệu là H(X), chỉ độ bất định hay lượng thông tin về biến X . NếuX là một biến ứng với một tập biến cố rời rạc thì entropy củaX được tính theo công thức sau [15]: H(X) = ∑ x p(x)log 1 p(x) = − ∑ x p(x)logp(x) (2.1) Trong đó, p(x) là hàm phân phối xác suất của biến ngẫu nhiênX . 2.1.2. Entropy đồng thời Giả sử, cho cặp biến ngẫu nhiên X và Y . Khi đó, entropy của X và Y được định nghĩa như sau: H(X, Y ) = ∑ x,y p(x, y)log 1 p(x, y) = − ∑ x,y p(x, y)logp(x, y) (2.2) Trong đó, p(x, y) là phân phối đồng thời của hai biếnX và Y . 2.1.3. Entropy có điều kiện Cho biến ngẫu nhiên Y . Entropy có điều kiện H(X|Y ) đo lượng thông tin không chắc chắn của biến ngẫu nhiên X khi đã biết Y và được tính theo công thức: H(X | Y ) = − ∑ y p(y) ∑ x p(x | y)logp(x | y) = − ∑ x,y p(x, y)log p(x, y) p(y) (2.3) Trong đó, p(x | y) là xác suất có điều kiện của biến X với điều kiện Y Từ định nghĩa, entropy có điều kiện có thể biểu diễn như sau: H(X | Y ) = H(X, Y )−H(Y ) (2.4) 4 Mở rộng độ đo thông tin tương hỗ có điều kiện cho trường hợp nhiều biến Do tính chất đối xứng của H(X,Y), nên ta có: H(Y | X) = H(X, Y )−H(X) (2.5) 2.1.4. Entropy của nhiều biến Trong trường hợp có nhiều biến ngẫu nhiên, ta có công thức tổng quát: H(X1, ..., Xn) = − ∑ x1,...,xn p(x1, . . . , xn)logp(x1, ..., xn) (2.6) Sử dụng quy tắc xích, ta có thể phân rã entropy của nhiều biến theo công thức (2.7): H(X1, ..., Xn) = n∑ i=1 H(Xi | Xi−1, ..., X1) (2.7) Trong trường hợp ba biếnX, Y, Z, công thức (2.7) được viết như sau: H(X, Y, Z) = H(X) +H(Y | X) +H(Z | X, Y ) (2.8) 2.1.5. Thông tin tương hỗ của hai biến Độ đo thông tin tương hỗ (Mutual Information-MI) là một độ đo trong Lí thuyết thông tin dùng để đo mức độ tương hỗ của hai biến. Thông tin tương hỗ của hai biến ngẫu nhiên X và Y , kí hiệu làMI(X, Y ) và được định nghĩa như sau [5]: MI(X, Y ) = ∑ x,y p(x, y)log p(x, y) p(x)p(y) (2.9) = H(X) +H(Y )−H(X, Y ) (2.10) Từ công thức (2.10) và công thức (2.4), ta có thể biểu diễn mối quan hệ của entropy, entropy có điều kiện và MI như sau: MI(X, Y ) = H(X) +H(Y )−H(X, Y ) = H(X)−H(X | Y ) (2.11) = H(Y )−H(Y | X) (2.12) 2.1.6. Thông tin tương hỗ có điều kiện Thông tin tương hỗ có điều kiện (Conditional Mutual Information-CMI) là một độ đo được dùng để đo lường sự 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ủa hai biến rời rạcX và Y khi biết biến Z được định nghĩa: MI(X, Y | Z) = ∑ z p(z) ∑ x,y p(x, y | z)log p(x, y | z) p(x | z)p(y | z) = ∑ x,y,z p(x, y, z)log p(x, y | z) p(x | z)p(y | z) (2.13) 5 Nguyễn Quỳnh Diệp, Nguyễn Thị Bích Ngọc, Phạm Thọ Hoàn, Trần Đăng Hưng Trong đó, p(x, y | z) là xác suất đồng thời của 2 biếnX và Y với điều kiện Z. p(x, y, z) là xác suất đồng thời của 3 biến X, Y, Z. Ngoài công thức trên, CMI còn có thể biểu diễn dựa trên entropy : MI(X, Y | Z) = H(X,Z) +H(Y, Z)−H(Z)−H(X, Y, Z) (2.14) Cũng giống như MI, nếu giá trị CMI càng lớn thì mối quan hệ giữa hai biến X và Y với điều kiện Z càng chặt chẽ. Theo công thức (2.5), vì H(X | Z) = H(X,Z) − H(Z) nên công thức (2.14) có thể viết thành: MI(X, Y | Z) = H(X | Z) +H(Y | Z)−H(X, Y | Z) (2.15) 2.2. Mở rộng thông tin tương hỗ có điều kiện Khi xuất hiện thêm biến thứ ba, mối quan hệ giữa các biến trở nên phức tạp hơn. Do đó, giữa các biến không chỉ còn tồn tại tương hỗ giữa cặp hai biến nữa mà còn có thêm các mối quan hệ khác. Trong [13], chúng tôi đã đề xuất một mở rộng độ đo thông tin tương hỗ MI cho trường hợp ba biến, bao gồm các kiểu tương hỗ sau: 1. Tương hỗ tổng hợp của ba biến: MI(X, Y, Z) = TC(X, Y, Z) = H(X) +H(Y ) +H(Z)−H(X, Y, Z) (2.16) 2. Tương hỗ bộ phận giữa một biến với cặp hai biến: MI(X,) = H(X) +H(Y, Z)−H(X, Y, Z) (2.17) MI(Y,) = H(Y ) +H(Z,X)−H(X, Y, Z) (2.18) MI(Z,) = H(Z) +H(X, Y )−H(X, Y, Z) (2.19) Nhìn vào công thức (2.10): M(X, Y ) = H(X) +H(Y )−H(X, Y ) và công thức (2.15): M(X, Y | Z) = H(X | Z) +H(Y | Z)−H(X, Y | Z) ta thấy có một sự tương ứng giữa MI và CMI. Từ đó, chúng tôi đề xuất một mở rộng độ đo thông tin tương hỗ có điều kiện của ba biến với các công thức tương tự như đã đề xuất đối vớiMI như sau: 1. Tương hỗ tổng hợp của ba biếnX, Y, Z khi có biến T xảy ra: MI(X, Y, Z | T ) = H(X | T ) +H(Y | T ) +H(Z | T )−H(X, Y, Z | T ) (2.20) 2. Tương hỗ bộ phận giữa một biến với cặp hai biến khi có biến T xảy ra: MI(X,| T ) = H(X | T ) +H(Y, Z | T )−H(X, Y, Z | T ) (2.21) MI(Y,| T ) = H(Y | T ) +H(Z,X | T )−H(X, Y, Z | T ) (2.22) MI(Z,| T ) = H(Z | T ) +H(X, Y | T )−H(X, Y, Z | T ) (2.23) Trong phần tiếp theo, chúng tôi sẽ trình bày một ứng dụng của độ đo MI và CMI để tái tạo mạng điều khiển gen từ dữ liệu biểu hiện gen. 6 Mở rộng độ đo thông tin tương hỗ có điều kiện cho trường hợp nhiều biến 2.3. Tái tạo mạng điều khiển gen 2.3.1. Thuật toán PCA Như đã trình bày trong phần Mở đầu, hiện nay đã có nhiều giải thuật xây dựng mạng được nghiên cứu nhưng những mô hình này vẫn còn một số hạn chế, cần được hoàn thiện hơn. Gần đây, lí thuyết thông tin đề cập tới việc tái tạo GRNs, sử dụng độ đo thông tin tương hỗ như thuật toán ARACNE [11], CLR [7]... Từ ma trận MI này, ta sẽ xác định được mối quan hệ giữa 2 gen. Ưu điểm lớn nhất của phương pháp này là nó có khả năng tính toán với hàng ngàn gen. Mặc dù, phương pháp dựa vào độ đo MI có ưu điểm nổi bật, nhưng độ đo thông tin tương hỗ chỉ làm việc trên cặp gen mà không xét đến tác động của các điều kiện hay sự ảnh hưởng của các gen khác. Phương pháp dựa vào độ đo CMI có khả năng phát hiện các mối quan hệ giữa các gen khi có các điều kiện xảy ra. Trong bài báo này, chúng tôi giới thiệu phương pháp dựa trên cả hai độ đo MI và CMI để phát hiện tương tác giữa các gen. Phương pháp chúng tôi trình bày có tên Path Consistency Algorithm-PCA, tái tạo mạng điều khiển gen từ dữ liệu biểu hiện gen bằng thuật toán PC. Thuật toán PC được sử dụng để loại bỏ các cạnh tương quan độc lập từ đồ thị. PCA được mô tả chi tiết như sau: Path Consistency Algorithm -PCA - Input: A: dữ liệu biểu hiện của gen θ: ngưỡng quyết định sự phụ thuộc order0: tham số kết thúc chương trình (khi order = order0) - Output: G: mạng liên kết giữa các gen order: bậc của mạng tái tạo • Bước 0: Khởi tạo. Xây dựng mạng đầy đủ G từ tất cả các gen đã cho. Chọn ngưỡng θ. Đặt L = -1. • Bước 1: L = L+1. Đối với cạnh G(i, j) 6= 0. Tìm các gen kề với cả 2 gen i, j. Gọi T là tập các gen kề với i, j (không tính i, j). • Bước 2: Nếu T<L thì dừng thuật toán. Nếu T ≥ L, chọn ra L gen từ tập T gen, giả sử đó làK = [k1, . . . , kL], có CLT cách lựa chọn tập K. Tính CMI bậc L,MI(i, j | K) cho tất cả CLT lựa chọn và chọn raMImax(i, j | K). NếuMImax(i, j | K) < θ thì G(i, j) = 0. Quay lại Bước 1. Đầu vào cho bài toán là tập dữ liệu biểu hiện gen được đo trong các điều kiện hoặc các thời điểm khác nhau. Đầu tiên, tạo ra một đồ thị đầy đủ từ các gen đã cho. Thứ hai, với cặp gen liền kề (i, j), tính thông tin tương hỗ MI(i, j). Nếu các cặp gen (i, j) có 7 Nguyễn Quỳnh Diệp, Nguyễn Thị Bích Ngọc, Phạm Thọ Hoàn, Trần Đăng Hưng MI(i, j) = 0 (tức là, chúng độc lập với nhau) hoặcMI(i, j) 6= 0 nhưng nhỏ hơn ngưỡng θ (ta coi chúng độc lập nhau), thì sẽ xóa các cạnh giữa gen i và j. Thứ ba, tìm các gen liền kề với cặp gen (i, j) (không tính gen i, j). Tính thông tin tương hỗ bậc 1 (1 điều kiện) giữa i và j với điều kiện k,MI(i, j | k). NếuMI(i, j | k) = 0 hoặc nhỏ hơn ngưỡng thì ta tiến hành xóa bỏ cạnh giữa chúng. Bước tiếp theo là tính CMI bậc cao hơn (nhiều điều kiện) cho đến khi không còn cạnh liền kề nào. Để hiểu rõ hơn về thuật toán PC, sau đây chúng tôi sẽ diễn giải thuật toán này với trường hợp dữ liệu biểu hiện của 5 gen X, Y, Z,W và V được minh họa trong Hình 1. Hình 1: Sơ đồ biểu diễn thuật toán PC Đầu tiên, ta tạo ra một mạng đầy đủ của 5 gen X, Y, Z, T, V . Ta tính MI của tất cả các cặp gen. Nếu MI của cặp gen nào < ngưỡng θ, ta xóa cạnh giữa hai gen đó. Ở đây, ta giả sử MI(X,Z) và MI(W,V ) xấp xỉ bằng 0, do đó các cạnh (X,Z) và (W,V ) được xóa. Ta thu được mạng gen bậc 0. Bước tiếp theo, ta tính CMI bậc 1 giữa các gen với các gen liền kề trong mạng bậc 0. Giả sử, thông tin tương hỗ có điều kiện MI(X,W |Y ) và MI(X, V |Y ) bằng 0, khi đó các cạnh (X,W ) và (X, V ) được xóa và ta thu được mạng gen bậc 1. Dựa vào kết quả của mạng bậc 1 này, ta tính CMI bậc 2 giữa các gen. Ở đây, ta có MI(Y, Z|W,V ) được giả định xấp xỉ bằng không, vì vậy cạnh (Y, Z) được xóa và ta có mạng bậc 2. Trong ví dụ này, ta không có CMI với 3 điều kiện (CMI bậc 3). Vì vậy, thuật toán kết thúc và mạng bậc 2 là mạng cuối cùng được tái tạo. 2.3.2. Thực nghiệm Trong bài báo này, chúng tôi sử dụng những tập dữ liệu được lấy từ trang web Với đầu vào là file dữ liệu biểu hiện gen, ngưỡng θ và bậc của CMI (order = 1, 2, ..., n). Đầu ra của chương trình là file cmi.txt chứa giá trị CMI của các cặp gen (sắp xếp theo chiều giảm dần) và file output.txt thể hiện các quan hệ của các gen trên mạng cùng với bậc tương ứng. Ở đây, chúng tôi sử dụng file dữ liệu có kích thước 10 (mạng gồm 8 Mở rộng độ đo thông tin tương hỗ có điều kiện cho trường hợp nhiều biến 10 gen) có tên là InSilicoSize10-Yeast1-null-mutants.txt. Hình 2: File đích Yeast1-null-mutants Hình 3: Kết quả CMI Chọn ngưỡng θ = 0.03 Mạng bậc 0 (order=0) có 12 cạnh Mạng bậc 1 (order=1) có 10 cạnh Hình 4: Kết quả CMI với ngưỡng θ và các bậc khác nhau Sau khi có được kết quả như trên, ta tái tạo được mạng gen như Hình 5. Trong đó: (A) là mạng thực với 10 gen và 10 cạnh. (B) là mạng bậc 0 được xây dựng bởi thuật toán PC với CMI bậc 0 với những cạnh nét đứt là những cạnh suy ra sai, còn những cạnh nét liền là những cạnh suy ra đúng. Mạng gen bậc 0 này có ba cạnh biểu thị bằng nét đứt là G2−G4, G4−G5, G2−G9 bị dư thừa, trong khi cạnh G4−G9 lại không được suy ra. 9 Nguyễn Quỳnh Diệp, Nguyễn Thị Bích Ngọc, Phạm Thọ Hoàn, Trần Đăng Hưng (A): mạng thực (B): mạng bậc 0 (C): mạng bậc 1 Hình 5: Mạng điều khiển gen của tập dữ liệu InSilicoSize10-Yeast1-null-mutants.txt (C) là mạng bậc 1 được xây dựng từ dữ liệu, đây cũng là mạng cuối cùng, là mạng bậc cao nhất được tái tạo dựa vào thuật toán PC. Và ở mạng bậc 1 này, ta thấy hai cạnh G2−G4 vàG4−G5 đã được xóa thành công. Tuy nhiên, cạnhG2−G9 chưa được xóa và cạnh G4−G9 vẫn chưa được suy ra. Mạng cuối cùng được tái tạo trong trường hợp này là mạng bậc 1 khi đem so sánh với mạng thực thì ta thấy kết quả cũng gần như chính xác hoàn toàn. Như vậy, ta có thể kết luận, đối với tập dữ liệu InSilicoSize10-Yeast1-null-mutants, mạng điều khiển gen được tìm ra bởi thuật toán PC dựa trên CMI tương đối khớp với mạng thực. Trên đây là một cách ta dùng để đánh giá mạng điều khiển gen được tái tạo. Cách đánh giá này sử dụng tới ngưỡng θ để xác định có tồn tại mối quan hệ giữa hai gen hay không. Tiếp theo, chúng tôi giới thiệu cách đánh giá thứ hai dựa vào đường cong ROC (Receiver Operating characteristic Curve) và diện tích dưới đường cong ROC (AUROC – Area Under ROC curve). Đường cong ROC có một tính chất vô cùng quan trọng như sau: nếu đường cong càng đi dọc theo biên trái và đi dọc theo biên phía trên của không gian ROC, thì chứng tỏ kết quả kiểm tra càng chính xác. Các kết quả dự đoán được đánh giá dựa trên các thông số sau: độ nhạy Sensitivity hay còn được gọi là TPR (true positive rate), FPR (false positive rate) thông số này bằng 1-Sensitivity, PPV (positive predictive value) và độ chính xác ACC (accuracy). Chúng được biểu diễn thông qua các công thức toán học sau: TPR = TP/(TP+FN) FPR = FP/(FP+TN) PPV = TP/(TP+FP) ACC = (TP+TN)/(TP+FP+TN+FN) Trong đó, TP là true positive, FP là false positive, TN là true negatives và FN là false negatives. Hai thông số TPR và FPR được sử dụng để vẽ đường cong ROC và thể hiện diện tích dưới đường cong (AUROC). Nếu biểu diễn dựa vào đường cong ROC, cho phép ta kết luận về độ đo ta sử dụng. Đối với tập dữ liệu InSilicoSize10-Yeast1-null-mutants diện tích dưới đường cong ROC ta thu được là khá cao AUROC = 0.9914. Tức là, ta sử dụng độ đo CMI trong 10 Mở rộng độ đo thông tin tương hỗ có điều kiện cho trường hợp nhiều biến trường hợp này là rất hiệu quả. Hình 6: Biểu diễn đường cong ROC tập dữ liệu InSilicoSize10-Yeast1-null-mutants 3. Kết luận Độ đo thông tin tương hỗ có điều kiện đã được đề cập từ rất sớm trong Lí thuyết thông tin. Song, việc sử dụng độ đo này trong việc tái tạo mạng sinh học vẫn còn là một vấn đề mới mẻ. Gần đây, đã có một số tác giả sử dụng độ đo này trong việc tái tạo mạng điều khiển gen. Tuy nhiên, một số mạng sinh học thường chứa các tương tác phức tạp hơn, chẳng hạn tương tác của ba hay bốn chất, v.v. Vì vậy, bài báo này đã đề xuất một mở rộng của độ đo thông tin tương hỗ có điều kiện CMI cho trường hợp nhiều biến. Để làm sáng tỏ ý nghĩa của độ đo CMI, chúng tôi đã trình bày một ứng dụng của độ đo CMI trong việc tái tạo mạng điều khiển gen. Ở đây, chúng tôi sử dụng cả hai độ đo MI và CMI để phát hiện mối quan hệ giữa các gen. Thuật toán PC được sử dụng để loại bỏ các cạnh có tương quan độc lập từ đồ thị đầy đủ ban đầu. Từ đó, tái tạo được mạng điều khiển gen. Kết quả chạy thực nghiệm đã cho thấy mạng gen được xây dựng bằng phương pháp này tương đối khớp với mạng thực. Mặc dù, dữ liệu chạy thực nghiệm có kích thước chưa lớn nhưng kết quả này sẽ là tiền đề cho những nghiên cứu tiếp theo. TÀI LIỆU THAM KHẢO [1] O. Alter, P.O. Brown and D. Botstein, 2000. Singular value decomposition for genome-wide expression data processing and modeling. Proccedings of the National Academy of Science of the USA, 97, pp. 10101 - 10106. [2] M. Bansal, G.D. Gatta and D. Bernardo, 2006. Inference of Gene Regulatory Networks and Compound Mode of Action from Time Course Gene Expression Profiles. Bioinformatics, 22(7), pp. 815-822. [3] K. Basso, A.A. Margolin, G. Stolovitzky, U. Klein, R. Dalla-Favera and A. Califano, 2005. Reverse engineering of regulatory networks in human B cells. Nat Genet, 37(4), pp. 382 - 390. 11 Nguyễn Quỳnh Diệp, Nguyễn Thị Bích Ngọc, Phạm Thọ Hoàn, Trần Đăng Hưng [4] A. Butte and I. Kohane, 1999. Unsupervised knowledge discovery in medical databases using relevance networks. Proc. AMIA Symp, pp. 711-715. [5] T.M. Cover and J.A. Thomas, 2006. Elements of Information Theory. Molecular Systems Biology. Wiley-Interscience, A John wiley & Sons, Inc., Publication. [6] I. Cantone, 2009. A yeast synthetic network for in vivo assessment of reverse engineering and modeling approaches. Cell, 137, pp. 172-181. [7] J.J. Faith,J.J, 2007. Large-scale mapping and validation of Escherichia coli transcriptional regulation from a compendium of expression profiles. PLoS Biology, 5, pp. 54-66. [8] T.S. Gardner, 2003. Inferring genetic networks and identifying compound mode of action via expression profiling. Science, 301, pp. 102-105. [9] M.I. Jordan,1998. Learning in Graphical Models. MIT Press, Cambridge. [10] S. Kauffman, C. Peterson, B. Samuelsson and C. Troein, 2003. Random Boolean network models and the yeast transcriptional network. Proccedings of the National Academy of Science of the USA, 100, pp. 14796-14799. [11] A.A. Margolin, K. Wang, W.K. Lim, M. Kustagi, I. Nemenman, A. Califano, 2006. Reverse engineering cellular networks. Nat. Protoc, 1(2), pp. 663-672. [12] S.C. Madeira, A.L. Oliveira, 2004. Biclustering Algorithms for Biological Data Analysis: A Survey. IEEE Transactions on Computational Biology and Bioinformatics, 1(1), pp. 24–45. [13] T.H. Pham, T.B. Ho, Q.D. Nguyen, D.H. Tran and V.H. Nguyen, 2012.Multivariate Mutual Information Measures for Discovering Biological Networks. Proceedings of Conference IEEE-RIVF 2012, pp. 103-108. [14] A. Rakesh, G. Johannes, G. Dimitrios and R. Prabhakar, 1998. Automatic subspace clustering of high dimensional data for data mining applications. In Proceedings of the ACM/SIGMOD International Conference on Management of data, pp. 94-105. [15] C.E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, pp. 379-423, 623-656. ABSTRACT Proposing an extension of the conditional mutual information measure to the multivariate case Analysis of gene expression data is essential in discovering the functions of biological elements. In order to understand the complex mechanisms of biological systems, gene regulatory network (GRN) reconstruction is very important and is also a challenging problem. In this paper, we propose an extension of the conditional mutual information measure to the multivariate case. Then, we present algorithm PCA (Path Consistency Algorithm), a new method to reconstruct GRNs from gene expression data by using mutual information (MI) and conditional mutual information (CMI). In this algorithm, the conditional dependence between a pair of genes is represented by the CMI between them. Experimetal results have confirmed that the PCA-CMI method is more effective than that of previous methods. 12