Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gen theo thời gian dựa trên cây hậu tố

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 47-59 This paper is available online at MỘT THUẬT TOÁN TÌM CÁC BICLUSTERS TRONG DỮ LIỆU BIỂU HIỆN GEN THEO THỜI GIAN DỰA TRÊN CÂY HẬU TỐ Nguyễn Văn Trung1, Đỗ Văn Dư2 và Trần Đăng Hưng3 1Trường Cao đẳng Y tế Lạng Sơn, 2Trường Cao đẳng Sư phạm Nam Định 3Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 3Email: hungtd@hnue.edu.vn Tóm tắt. Phân tích dữ liệu biểu hiện gen theo thời gian 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. Với lượng dữ liệu ngày càng nhiều, các phương pháp thống kê cổ điển không còn phù hợp. Điều này đòi hỏi phải phát triển các phương pháp tính toán mới để phân tích hiệu quả các nguồn dữ liệu biểu hiện gen. Trong bài báo này, chúng tôi trình bày một hướng tiếp cận mới dựa trên các thuật toán biclustering (phân cụm hai chiều) để tìm các mẫu quan trọng từ lượng lớn dữ liệu biểu hiện gen. Cụ thể, chúng tôi giới thiệu thuật toán dựa trên cây hậu tố CCC-biclustering, sau đó thực nghiệm trên hai tập dữ liệu biểu hiện gen theo thời gian. Kết quả cho thấy các mẫu tìm được có độ biểu hiện tương đồng cao, từ các mẫu này có thể dự đoán hoặc tiên lượng các chức năng mới cho các phần tử sinh học. Từ khóa: Bicluster, dữ liệu biểu hiện gen, cây hậu tố, 1. Mở Đầu Việc phân tích dữ liệu biểu hiện gen, mà cụ thể là phân nhóm các gen có sự biểu hiện giống nhau trong từng thời điểm thành các cụm (cluster) được thực hiện bởi các thuật toán phân cụm (clustering). Các thuật toán này thường tìm cách nhóm các gen có sự biểu hiện phụ thuộc nhau trên toàn bộ các điều kiện thí nghiệm. Tuy nhiên, trên thực tế các gen thường chỉ thể hiện phụ thuộc với nhau trên một số điều kiện nào đó và độc lập với nhau trong điều kiện khác. Điều này dẫn đến một hạn chế rất lớn của các thuật toán clustering là không thể tìm ra được các gen chỉ thể hiện giống nhau trên một số điều kiện thí nghiệm. Để khắc phục hạn chế này, người ta đã đề xuất một phương pháp phân cụm mới có tên là biclustering. Các thuật toán biclustering sẽ tìm cách phân cụm đồng thời trên các hàng (gene) và cột (condition) của ma trận dữ liệu biểu hiện gen nhằm tìm ra các ma trận con thoả mãn một số tiêu chí đặt ra, từ đó có thể giúp chúng ta hiểu thêm các tiến trình sinh học giữa các gen trong các cá thể. 47 Nguyễn Văn Trung, Đỗ Văn Dư, Trần Đăng Hưng Trong trường hợp dữ liệu biểu hiện gen theo chuỗi thời gian, các mẫu sinh học thường được đo theo một khoảng thời gian nhất định nhằm quan sát các tiến trình sinh học xảy ra trong các cá thể. Vì vậy, việc tìm ra các mẫu có thể hiện giống nhau trong một khoảng thời gian liên tục nào đó có thể hình dung như chúng vừa hoàn thành một tiến trình sinh học, hoặc một giai đoạn chức năng sinh học. Phân tích dữ liệu thể hiện gen cho phép hiểu được cơ chế điều khiển gen và tương tác giữa chúng, các tri thức này có thể được sử dụng trong nghiên cứu chế tạo thuốc, phát hiện khối u,... và các nghiên cứu lâm sàng. Các mẫu dữ liệu này có thể coi như là một bicluster gồm các hàng và các cột liên tục trong ma trận. Với trường hợp dữ liệu biểu hiện gen theo chuỗi thời gian, người ta đã đề xuất các thuật toán hiệu quả với thời gian chạy tuyến tính, hoặc một hàm đa thức để tìm ra các bicluster tốt. Các thuật toán này không khai phá trực tiếp dữ liệu gốc, mà sẽ chuẩn hóa sang một dạng dữ liệu mới, sau đó xây dựng các cây hậu tố để tìm kiếm. Mỗi cây hậu tố sẽ biểu diễn một ma trận dữ liệu, và việc tìm các bicluster được coi như tìm một xâu con chung lớn nhất của một tập các xâu dựa vào cây hậu tố. Cây hậu tố (suffix trees) là một cấu trúc dữ liệu biểu diễn các hậu tố của một chuỗi. Nó cho phép thực hiện rất nhiều thuật toán hiệu quả trên dữ liệu chuỗi và được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của khoa học máy tính như: đối sánh mẫu, tìm xâu con chung, thống kê tần suất “từ”,... Trong bài báo này, chúng tôi giới thiệu một thuật toán biclustering dựa trên cây hậu tố, sau đó tiến hành thực nghiệm trên hai tập dữ liệu sinh học khác nhau. Phân tích và đánh giá kết quả với các tri thức sinh học đã biết, chúng tôi thấy rằng thuật toán cho phép tìm các bicluster với độ tương đồng cao, từ các bicluster này có thể phát hiện ra các chức năng mới cho các gen. 2. Nội dung nghiên cứu 2.1. Thuật toán CCC-biclustering Trong phần này chúng tôi giới thiệu thuật toán CCC-biclustering [3], một thuật toán tìm và đưa ra tất cả các biclusters cực đại và hoàn hảo. Một bicluster có mẫu biểu hiện hoàn hảo nếu tất cả các gen trong bicluster đều có cùng mẫu thể hiện trong một khoảng thời gian liên tục. Một bicluster là cực đại nếu nó không thể mở rộng các gen có cùng một mẫu và thời điểm tiếp theo sau. Ý tưởng chính của thuật toán sử dụng kĩ thuật xử lí chuỗi dựa trên cây hậu tố, trong đó mối quan hệ tương đồng giữa các biclusters cực đại với các nút trong của cây hậu tố tổng quát được xây dựng cho các chuỗi (các hàng) là đại diện của các mẫu thể hiện của mỗi gen trong ma trận dữ liệu biểu hiện gen. 2.1.1. Chuẩn hóa dữ liệu biểu hiện gen ChoA′ là ma trận biểu hiện gen được xác định bởi |R| hàng và |C| cột, trong đó, tập các hàng (gen) R, và tập các cột (thời điểm) C. Chúng ta xét mức độ thể hiện gen trong 48 Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gien... ma trận A′, mà mỗi phần tử là tập các kí tự trong bảng chữ cái Σ. Sau quá trình chuẩn hóa dữ liệu từ ma trận A′ sang ma trận A, mỗi phần tử Aij ∈ Σ đại diện cho các giá trị tùy thuộc vào mức độ thể hiện của gen i tại thời điểm j. Ví dụ: (a) (b) C1 C2 C3 C4 C5 C1 C2 C3 C4 C5 G1 0.07 0.73 -0.54 0.45 0.25 G1 N U D U N G2 -0.34 0.46 -0.38 0.76 -0.44 G2 D U D U D G3 0.22 0.17 -0.11 0.44 -0.11 G3 N N N U N G4 0.70 0.71 -0.41 0.33 0.35 G4 U U D U U G5 0.70 0.17 0.70 -0.33 0.75 G5 U N U D U Quy định giá trị Aij ∈ [−0.3, 0.3] là N; Aij ≤ −0.3 làD; Aij ≥ 0.3 là U Hình 2.1. Minh họa quá trình chuẩn hóa dữ liệu từ ma trận A′ (a) sang ma trận A (b) theo kĩ thuật sử dụng bảng chữ cái với ba kí tự Σ = {D,N, U} Ma trận A ở trên được xác định làm ví dụ cơ sở cho các khái niệm bicluster và mục tiêu của thuật toán biclustering sau này, dưới đây là một số khái niệm được sử dụng trong thuật toán. Định nghĩa 2.1 (bicluster): Một bicluster là một ma trận con AIJ được xác định bởi I ⊆ R là tập con các hàng và J ⊆ C là tập con các cột. Một bicluster chỉ có một hàng hoặc một cột thì gọi là bicluster tầm thường. Định nghĩa 2.2: Một bicluster kết dính theo cột AIJ (CCC-bicluster) là bicluster mà Aij = Alj với tất cả hàng i, l ∈ I và cột j ∈ J . Định nghĩa 2.3: Một bicluster kết dính theo cột liên tục AIJ = (I, J) (CCC-bicluster) là tập con của các hàng I = {i1, ..., ik} và tập con các cột láng giềng J = {r, r + 1, ..., s − 1, s} mà Aij = Alj , với mỗi i, l ∈ I và các cột j ∈ J . Mỗi CCC-bicluster xác định một chuỗi S phổ biến với mọi hàng I và cột J . Định nghĩa 2.4:Một CCC-bicluster AIJ là cực đại hàng nếu không thể thêm được bất kì hàng I nào vào nó và được xác nhận thuộc tính gắn kết như định nghĩa 2.3. Định nghĩa 2.5: Một CCC-bicluster AIJ là cực đại trái/phải nếu chúng ta không thể mở rộng nó bởi mẫu biểu thức S vào trái/phải bằng cách thêm một kí tự (cột láng giềng) vào đầu/cuối của bicluster mà không làm thay đổi tập hàng I . Định nghĩa 2.6:Một CCC-bicluster AIJ là cực đại, khi nó không có CCC-bicluster nào khác bao hàm được những thuộc tính của AIJ , có nghĩa là, nếu cho tất cả các CCC-biclusters ALM , I ⊆ L ∧ J ⊆ M ⇒ I = L ∧ J = M . Với định nghĩa như vậy chúng ta có thể hiểu rằng “CCC-bicluster cực đại là một CCC-bicluster cực đại trái/ phải và cực đại hàng”. Vấn đề đặt ra là, cho ma trận biểu hiện gen A, xác định tất cả các CCC-bicluster cực 49 Nguyễn Văn Trung, Đỗ Văn Dư, Trần Đăng Hưng đại BK = AIkJk . Để giải quyết vấn đề của bài toán đó chúng tôi xin trình bày đề xuất của thuật toán sử dụng kĩ thuật xử lí chuỗi dựa trên cây hậu tố để xác định các CCC-bicluster cực đại với thời gian tuyến tính. 2.1.2. Tìm tất cả các bicluster cực đại với mẫu biểu hiện hoàn hảo - CCC-bicluster và cây hậu tố tổng quát. Ý tưởng trọng tâm của thuật toán CCC-biclustering là mối quan hệ tương đồng giữa các CCC-bicluster với các nút trong của cây hậu tố tổng quát. Đầu tiên chúng ta chuyển các chữ cái trong ma trận A bằng cách thêm số cột cho mỗi phần tử trong ma trận (thực hiện như một bước tiền xử lí trong thuật toán). Khi đó ta có một bảng chữ cái mới∑′ =∑ x{1, ..., |C|} ở đó mỗi phần tử∑′ được ghép với một kí tự trong∑ với một số trong khoảng {1, ..., |C|}. Khi đó ta có tập các chuỗi {S1, ..., S|R|} thu được bằng cách áp dụng chuẩn hóa mỗi hàng AiC của ma trận A như sau: Hình 2.2. Minh họa quá trình chuẩn hóa dữ liệu. (a) là ma trận A trong hình 2.1, (b) là ma trận thể hiện sau khi chuẩn hóa các chữ cái và ghép thêm thứ tự cột Chúng ta thấy rằng các CCC-biclusters cực đại trong ma trận gốc A được mô tả chính xác tương ứng với các nút trên cây hậu tố tổng quát T được xây dựng từ tập các chuỗi {S1, ..., S|R|}. Sự gia tăng kích thước bảng chữ cái sau khi chuẩn hóa không ảnh hưởng đến việc xây dựng và thao tác của cây hậu tố tổng quát. Xét một nút v trong T theo chiều sâu ta có P (v) là chỉ số cột. Cho L(v) biểu thị số lượng lá trong cây con có gốc là v, trong trường hợp v là một nút trong. Bằng cách phân tích như ví dụ minh họa (Hình 2.3), dễ dàng xác định tất cả các nút trong của cây T tương ứng với một CCC-bicluster cực đại hàng, cực đại phải trong ma trận A. Vì nút trong v của cây T tương ứng với một chuỗi con (substring) phổ biến cho mọi hàng có một lá gốc tại v. Vì vậy, mỗi nút trong v xác định một CCC-bicluster có P (v) cột, và số hàng bằng L(v). Nó đúng với tất cả các nút cho phép, trừ những nút có nhãn cạnh đơn cuối cùng cũng xác định CCC-biclusters. Tuy nhiên trong số những CCC-biclusters không cực đại (như nút trong có chuỗi nhãn [D3 U4] và [N5]). Một nút trong tương ứng với một CCC-bicluster cực đại nếu và chỉ nếu nó không có liên kết hậu tố đến từ một nút có cùng giá trị L(v). 50 Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gien... Như vậy chỉ có các nút trong với chuỗi nhãn [U1], [U4], [U4 N5], [U2 D3 U4], và [N1] là xác định CCC-biclusters cực đại có ít nhất hai hàng. Những nút trong tương ứng với CCC-biclusters cực đại từ nút B1 đến B6 trong hình 2.4(b). Hình 2.3. CCC-bicluster và cây hậu tố tổng quát Lưu ý rằng các hàng trong mỗi CCC-bicluster thu được bởi nút v từ chuỗi kí tự kết thúc của nó trong cây con. Giá trị P (v) và kí tự đầu tiên trong chuỗi nhãn của nút v cung cấp thông tin cần thiết để xác định tập các cột liền kề. - Tìm và đưa ra tất cả CCC-bicluster trong thời gian tuyến tính. Thuật toán tìm và đưa ra tất cả CCC-bicluster cực đại, trong dữ liệu chuẩn hóa từ ma trận biểu hiện gen A trong thời gian tuyến tính theo kích thước của ma trận được xây dựng dựa trên cây hậu tố với tập các chuỗi {S1, ..., S|R|} thu được như đã mô tả ở trên. 51 Nguyễn Văn Trung, Đỗ Văn Dư, Trần Đăng Hưng Các nút không thỏa mãn các điều kiện được đánh dấu không hợp lệ “Invalid”. Trường hợp ngược lại, tương ứng với các nút trong của cây hậu tố là các CCC-bicluster cực đại. Thuật toán: CCC-biclustering Input:Ma trận biểu hiện gen Output: Các CCC-biclusters 1. Chuẩn hóa ma trận và thu được tập các chuỗi S1, ..., S|R|; 2. Xây dựng cây hậu tố tổng quát T cho S1, ..., S|R|; 3. for each internal node v ∈ T do 4. Đánh dấu nút v hợp lệ “Valid”; 5. Tính P(v) theo chiều sâu; 6. for each internal node v ∈ T do 7. Tính số lượng lá L(v) trong cây con có gốc v; 8. for each internal node v ∈ T do 9. Nếu có liên kết từ nút v đến u và L(u) = L(v) thì 10. Đánh dấu nút không hợp lệ (“Invalid”); 11. for each internal node v ∈ T do 12. Nếu v được đánh dấu là hợp lệ thì 13. Đưa ra CCC-bicluster tương ứng với nút v. Trong thuật toán trên chúng ta cần quan tâm đến ba vấn đề chi tiết dẫn đến hiệu quả của thuật toán như sau: Cấu trúc dữ liệu được dùng trong cây hậu tố tổng quát. Chúng ta sử dụng ba kiểu nút để xây dựng cây hậu tố tổng quát T là: nút gốc (root), nút trong và nút lá. - Nút gốc (root) lưu trữ một mảng gọi là children với |C|| ∑ |+ |R| vị trí, ở đó mỗi vị trí là một con trỏ. Mảng được sắp xếp theo thứ tự đảo ngược từ kí tự đầu tiên của nhãn cạnh trong các nút. Đầu tiên với |C|| ∑ | vị trí lưu trữ các nút trong có nhãn cạnh bắt đầu với ∑′[|C||∑ |]...∑′[1]. Cuối cùng |R| vị trí lưu trữ |R| chuỗi kết thúc. Trong thiết lập này, children[j], j ∈ 1, ..., |C|| ∑ | là null nếu không có hậu tố bất kì nào của chuỗi Si bắt đầu với kí tự trong ∑′[j], khi đó nếu các nút gọi là khả năng có nhãn cạnh bắt đầu với kí tự ∑′[j]. Sử dụng thứ tự đảo ngược vì trong thực tế bước chuẩn hóa bảng chữ cái là một tập các số nguyên dương và giá trị kết thúc được đại diện bởi số nguyên âm. - Nút trong (internal node): Mỗi nút trong v lưu trữ một con trỏ, chiều dài của nó P (v), số lượng lá trong cây con là L(v) và được đánh dấu nếu nó tương ứng với một CCC-bicluster cực đại hoặc không. Nút con thứ nhất của nút trong là phần tử đầu tiên của danh sách, các nút con tương ứng được sắp xếp đảo ngược kí tự đầu tiên của nhãn cạnh. Chèn các nút được sắp xếp theo thứ tự đảo ngược kí tự của nhãn cạnh gồm O(| ∑ |) phần 52 Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gien... tử vào danh sách tương ứng với kí tự trong ∑′ và sau đó là chèn O(|R|) kí tự kết thúc. Việc tìm kiếm kí tự ∑′ trong nút con của một nút trong v luôn luôn có thời gianO(|∑ |). Các nút anh em của mỗi nút trong v cũng là phần tử đầu của danh sách liên kết cũng được lưu trữ. - Nút lá (leaf) cũng được lưu trữ các thông tin tương tự như nút trong. Chuyển đổi bảng chữ cái và cây hậu tố tổng quát.Một cây hậu tố tổng quát được xây dựng cho tập các chuỗi (mảng kí tự) và bảng chữ cái ∑ . Khi các phần tử trong ∑ không chỉ duy nhất một kí tự, thì chuyển đổi bảng chữ cái này sang một bảng các số nguyên. Trong nội dung này, tập các chuỗi {S1, ..., S|R|} thu được bằng cách áp dụng chuyển đổi bảng chữ cái cho mỗi hàng AiC trong ma trận A và được sử dụng để xây dựng cây hậu tố tổng quát T . Trong thuật toán CCC-biclustering lúc này áp dụng với một mảng các số nguyên, mà không phải mảng kí tự. Mỗi phần tử trong ∑′ là một số nguyên thu được bằng cách ghép mã ASCII tương ứng với những kí tự trong phạm vi {1, ..., |C|}. Hình 2.4 là kết quả của việc chuyển đổi bảng chữ cái, được áp dụng thực hiện cho ví dụ minh họa trong Hình 2.1. Do đó, trong trường hợp này ∑ = {D,N, U}, mỗi phần tử trong ∑′ thu được bằng cách ghép các mã ASCII tương ứng với {68, 78, 85} và một số trong phạm vi {1, ..., 5}. Chuyển đổi bảng chữ cái được sử dụng trong quá trình là∑′ = {681, 682, 683, 684, 685; 781, 782, 783, 784, 785; 851, 852, 853, 854, 855}. Hình 2.4. Minh họa sau khi quá trình chuẩn hóa dữ liệu bằng cách ghép mã ASCII ∗(a) là ma trận A trong hình 2.1; (b) là ma trận A sau khi chuyển đổi bảng chữ cái được sử dụng trong các ví dụ trên, kết thúc chuỗi i; (c) là ma trận sau khi chuyển đổi bảng chữ cái được dùng trong thao tác kĩ thuật của CCC-biclusters. Mỗi gen được đại diện là một mảng các số nguyên. Cuối cùng là −(|R| − i+ 1) được sử dụng cho mỗi gen và |R| = 5. Chuỗi kết thúc của tập các chuỗi {S1, ..., S|R|} sử dụng trong quá trình thực hiện cũng là một tập các số nguyên, những kí tự kết thúc được sử dụng là giá trị số nguyên i cho gen i. Tuy nhiên, khi số lượng của các gen trong ma trận A có thể lớn hơn số nguyên bé nhất trong ∑′, chúng ta không thể sử dụng số nguyên tuyệt đối để đại diện cho kí tự kết thúc. Như vậy, ta sử dụng số nguyên âm. Để hiệu quả tốt nhất ta sử dụng kí tự cuối cùng là −1 tới −|R| theo thứ tự ngược. Điều này có nghĩa là kết thúc được sử dụng cho các mảng của các số nguyên đại diện cho gen i được tính (|R| − i + 1). Trong ví dụ này, và theo thuật toán CCC-biclustering thực hiện, là sử dụng tập các kí hiệu kết thúc {−5,−4,−3,−2,−1} cho tập các gen {G1, G2, G3, G4, G5}. 53 Nguyễn Văn Trung, Đỗ Văn Dư, Trần Đăng Hưng Cây hậu tố tổng quát T sau khi được xây dựng từ mảng của tập các số nguyên {S1, ..., S|R|} được tính toán như đã mô tả ở trên bằng cách sửa đổi thuật toán Ukkonen, cho phép một thời gian tuyến tính xây dựng cây hậu tố tổng quát với mảng các số nguyên thay vì các chuỗi. Thuật toán CCC-biclustering tìm kiếm và đưa ra tất cả các CCC-biclusters cực đại trong thời gian tuyến tính. Điều này có nghĩa rằng không chỉ các bước cần thiết để xác định các CCC-biclusters cực đại chạy trong thời gian tuyến tính mà cả các bước cần thiết để đưa ra tất cả CCC-biclusters cực đại xác định bởi các nút được đánh dấu là hợp lệ (valid) cũng phải có thời gian tuyến tính. Để đạt được độ phức tạp thời gian tuyến tính, thủ tục duyệt cũng phải được thực hiện theo chiều sâu, trong đó mỗi nút trong cây hậu tố tổng quát chỉ được duyệt một lần. - Độ phức tạp thuật toán Với cấu trúc dữ liệu phù hợp và sử dụng thuật toán Ukkonen [6], thời gian xây dựng cây hậu tố là tuyến tính trên kích thước của ma trận đầu vào được tính là O(|R||C|). Các bước còn lại của thuật toán CCC-biclustering cũng là tuyến tính, các vòng lặp được thực hiện bằng cách tìm kiếm theo sâu (dfs) trên cây hậu tố. Kể cả khi cây có nút trong ít hơn nút lá, độ phức tạp với thời gian tuyến tính của thuật toán CCC-biclustering là một kết quả khả thi. Trên thực tế độ phức tạp của việc dựng cây hậu tố phụ thuộc vào kích thước bảng chữ cái vì vậy mà nó trở nên quan trọng khi bảng chữ cái đủ lớn. Do đó, người ta phải đảm bảo sự gia tăng kích thước bảng chữ cái từ | ∑ | đến |C|| ∑ | là rất lớn, việc chuyển đổi bảng chữ cái được mô tả trong phần trên, không ảnh hưởng đến độ phức tạp của thuật toán. Tuy nhiên, chỉ có một nút trong, đó là nút gốc (root), có số lượng nút con phụ thuộc vào số lượng cột. Có thể quan sát thấy cây hậu tố trong ví dụ ở hình 2.4 tất cả các nút trong khác nút gốc có số lượng nút con cũng không ảnh hưởng bởi số lượng các cột. Bởi vì, sau khi việc chuyển đổi bảng chữ cái, các chuỗi nhãn của một nút trong tương ứng với một mẫu biểu hiện chung cho tập các gen giữa tập các thời điểm liên tục, luôn bắt đầu tại một thời điểm cụ thể. Điều này dẫn đến một lượng lớn nút con là O(| ∑ |) mà không phải O(|C|| ∑ |). Các nút trong chỉ có lá với nhãn cạnh là kí tự kết thúc, có thể có một số nút con sẽ phát triển với số lượng hàng trong ma trận, nhưng số lượng này không phụ thuộc vào số lượng cột. Việc phân nhánh ở gốc được thực hiện trong thời gian là hằng số. Như vậy theo các nhận xét trên thì tổng độ phức tạp của thuật toán CCC-biclustering là O(|R||C|). 2.2. Thực nghiệm 2.2.1. Các tập dữ liệu Tập dữ liệu Yeastsress: Một tập dữ liệu thu được từ Gasch [1], đo được khi cho 54 Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gien... phản ứng sốc nhiệt. Tập dữ liệu này bao gồm tám thời điểm khác nhau, ở cùng nhiệt độ 370C (5, 10, 15, 20, 30, 40, 60 và 80 phút). Kết quả thu được là một ma trận, có kích thước và kí hiệu YM(5955x8), trong đó số gen là 5955 và số thời điểm là 8. Mỗi phần tử của ma trận là thể hiện của cặp (gen, thời điểm) là một số thực. Trong một số thời điểm một số gen không biểu hiện là những giá trị khuyết thiếu. Địa chỉ dữ liệu tại: Tập dữ liệu CellCycle: Tập dữ liệu được mô tả của Tavazoie [7] được xử lí trước đó bởi Cheng and Church [4], liên quan đến phản ứng trong hai chu kì tế bào. Đây là tập dữ liệu bao gồm 17 điểm thời gian thí nghiệm và 2884 gen sau khi loại bỏ những gen không thể hiện. Địa chỉ dữ liệu tại: 2.2.2. Kết quả thực nghiệm Chúng tôi thực nghiệm thuật toán CCC-biclustering trên cả 2 tập dữ liệu. Dưới đây là tham số cụ thể của thuật toán đối với ma trận dữ liệu, bằng phần mềm BigGesTS [2]. Ở đây chúng tôi không đưa ra được cụ thể và toàn bộ các bicluster (vì lí do độ dài dữ liệu) mà chỉ đưa ra kích thước của mười bicluster dưới bảng sau: Bảng 1. Kết quả của thuật toán CCC-biclustering với hai tập dữ liệu Tên Bicluster Yeaststress Bicluster CellCycle Gen Kíchthước Số thời điểm Khoảng thời gian Gen Kích thước