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ố

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

Thêm vào BST

Báo xấu

26
lượt xem 2
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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 http://stdb.hnue.edu.vn 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 1 Trường Cao đẳng Y tế Lạng Sơn, 2 Trường Cao đẳng Sư phạm Nam Định 3 Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 3 Email: 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 Cho A′ 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 P′ P P P = 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á. P - 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 P 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 P P P 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 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 P đầ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í P′ 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. P 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... P 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. P P 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 gian O(| |). 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 P P 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ố P 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 P 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 P′ 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à P′ = {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 P 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 P P đả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 P 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 P 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 độ 370 C (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: http://genome-www.stanford.edu/yeast_stress/data.shtml. 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: http://arep.med.harvard.edu/biclustering. 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 Bicluster Yeaststress Bicluster CellCycle Tên Kích Số thời Khoảng Kích Số thời Khoảng Gen Gen thước điểm thời gian thước điểm thời gian Bicluster1 631 1262 2 60-80 739 1478 2 16-17 Bicluster2 1509 3018 2 40-60 645 1290 2 15-16 Bicluster3 245 735 3 40-80 61 183 3 15-17 Bicluster4 1126 3378 3 40-80 313 939 3 15-17 Bicluster5 138 414 3 40-80 271 813 3 15-17 Bicluster6 1292 2584 2 30-40 649 1298 2 14-15 Bicluster7 405 1215 3 30-60 59 177 3 14-16 Bicluster8 14 56 4 30-80 2 8 4 14-17 Bicluster9 377 1508 4 30-80 37 148 4 14-17 Bicluster10 14 56 4 30-80 20 80 4 14-17 Với tập dữ liệu của loài Yeast, chúng ta thấy trong mười bicluster trên tổng số 1993 bicluster của tập dữ liệu Yeaststress, Bicluster1 là bicluster xấu nhất và Bicluster9 là bicluster tốt nhất. Dựa vào danh sách bicluster, chúng tôi chọn Bicluster8 để làm ví dụ mô tả chi tiết về hình ảnh sự biến thiên về giá trị các thành phần của chúng: Nhóm gen: {PHO3, YCR016w, PMP1, SWM1, CCA1, TAF6, MNT2, RPL26b, CBP1, BIR1, YNL089c, WTM2, YOR283w, FHL1}. Nhóm thời điểm: {30, 40, 60, 80}. 55
Nguyễn Văn Trung, Đỗ Văn Dư, Trần Đăng Hưng Hình 2.5. Đồ thị thể hiện dữ liệu biểu hiện các gen của Bicluster 8 Với tập dữ liệu CellCycle. Ở đây chúng tôi cũng không đưa ra cụ thể và toàn bộ các bicluster mà chỉ đưa ra cụ thể kích thước của mười bicluster trên tổng số 16186 bicluster. P Được thực hiện trên ma trận đã chuẩn hóa với tập kí tự trong bảng chữ cái . Nhìn chung các bicluster có thể hiện biến thiên tương đối tập trung trong nhóm gen, một số bicluster chỉ thể hiện trên một số lượng ít gen như Bicluster8, số lượng gen giữa các bicluster có chênh lệch lớn. Bicluster1 là bicluster xấu nhất và Bicluster5 là bicluster tốt nhất. Dựa vào danh sách bicluster, chúng tôi chọn Bicluster10 để làm ví dụ mô tả chi tiết về hình ảnh sự biến thiên về giá trị các thành phần của chúng: Hình 2.6. Đồ thị biểu hiện gen của 10 Bicluster trong tập dữ liệu CellCycle Dưới đây chúng tôi chọn Bicluster10 để làm ví dụ mô tả chi tiết về hình ảnh sự biến thiên về giá trị các thành phần của chúng: Nhóm gồm: 20 gen và 4 điều kiện (14, 15, 16, 17). 56
Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gien... Hình 2.7. Đồ thị thể hiện dữ liệu biểu hiện các gen của Bicluster 10 2.2.3. Thảo luận Việc tìm kiếm bicluster là một bài toán khó, dựa trên từng loại dữ liệu cụ thể mà chúng ta quyết định sử dụng thuật toán nào cho phù hợp. Đặc biệt với dữ liệu biểu hiện gen theo chuỗi thời gian, đòi hỏi bicluster tìm được phải nằm trong một khoảng thời điểm liên tục, với kết dính các cột liên tục. Ngoài ra, số lượng cũng ảnh hưởng đến chất lượng của các bicluster tìm được. Với ma trận biểu hiện gen theo chuỗi thời gian việc xác định tất cả bicluster dựa trên cây hậu tố tổng quát là một đề xuất hiệu quả. Với hai bộ dữ liệu Yeaststress và CellCycle chúng tôi đã chạy thử nghiệm trên thuật toán CCC-biclustering, chọn mười bicluster đầu tiên chúng tôi thấy khả năng thể hiện của các gen trong một bicluster là rất tương đồng, chẳng hạn như Bicluster8 (Hình 2.5) có 14 gen trong 4 thời điểm liên tục. Điều này có nghĩa nhóm gen trong cùng một phản ứng nhiệt có sự biến thiên tương đồng trong khoảng thời gian. Ngoài ra, để tham khảo chức năng sinh học của các gen trong bicluster tìm được, chúng tôi sử dụng thông tin chú giải gen từ dữ liệu từ điển gen GO (Gene Ontology) là GoToolBox mô tả cấu trúc gen gồm: từ điển chức năng phân tử (molecular function), từ điển các tiến trình sinh học (boilogical processes), và từ điển các thành phần tế bào (cellular componets). Mỗi nút của một cấu trúc được gọi là một term và được đánh số duy nhất, có thể có nhiều gen liên kết với một term. Như trong Bicluster8 (Hình 2.5) có một gen là PMP1 có từ điển sinh học là: Gene: PMP1 Annotated GO Terms: 5 GO:0030234 enzyme regulator activity GO:0016020 membrane GO:0006812 cation transport GO:0005886 plasma membrane 57
Nguyễn Văn Trung, Đỗ Văn Dư, Trần Đăng Hưng GO:0016021 integral to membrane Những phát triển gần đây của các kĩ thuật DNA và công nghệ hiện đại, người ta có thể đo được mức độ biểu hiện của một số lượng lớn các gen trong các điều kiện thực nghiệm khác nhau. Phương pháp học máy không có giám sát đã được sử dụng trong phân tích dữ liệu biểu hiện gen. Gần đây biclustering, một cách tiếp cận không giám sát thực hiện phân nhóm đồng thời kích thước gen và điều kiện của ma trận biểu hiện gen, đã được chứng minh là hiệu quả đáng kể trong một loạt các ứng dụng. Những lợi thế của biclustering trong việc khám phá mẫu cục bộ, mô tả liên kết chặt chẽ của tập các gen trong tập các điều kiện đã được nghiên cứu. Một kiểu đặc biệt của dữ liệu biểu hiện gen được thể hiện theo thời gian thu được từ thí nghiệm microarray thực hiện trong thời gian chốc lát, là một phương thức ngày càng phổ biến để nghiên cứu một loạt các tiến trình sinh học phức tạp chuyên nghiệp, chẳng hạn như tiến triển bệnh, tăng trưởng, phát triển và phản ứng thuốc. Tuy nhiên, khi phân tích các nhà nghiên cứu thí nghiệm phải đối mặt với nhiều thách thức tính toán mới. Các thuật toán được thiết kế đặc biệt cho các thí nghiệm riêng, được yêu cầu để tận dụng lợi thế của các tính năng độc đáo và giải quyết những vấn đề duy nhất, mặc dù hầu hết các công thức của biclustering vẫn là NP- khó khi làm việc với các dữ liệu biểu hiện gen theo chuỗi thời gian. Thuật toán CCC-biclustering là một thuật toán hiệu quả trong việc tìm và đưa ra tất cả các bicluster cực đại gắn kết cột liên tục có thời gian tuyến tính với kích thước ma trận thể hiện. Phương pháp chấm điểm để xếp hạng CCC-biclusters dựa trên ý nghĩa thống kê. Các kết quả thu được bằng cách sử dụng một bản dịch mô hình hiện tượng xảy ra trong phản ứng stress nhiệt, cho thấy không chỉ khả năng của phương pháp đề xuất để trích xuất thông tin có liên quan tương thích với kiến thức sinh học mà còn tiện ích của thuật toán. Hơn nữa, những thí nghiệm đã chứng minh rằng việc chuẩn hóa ma trận dữ liệu được sử dụng như một bước tiền xử lí của biclustering không tác động tiêu cực đến ý nghĩa thống kê của kết quả tìm được. Việc xác định các gen, đồng thời tham gia vào các tiến trình sinh học, vẫn là một trong những con đường mở cho các nhà nghiên cứu, khả năng hiệu quả của các phương pháp được đề xuất để xác định các bộ gen theo thống kê và sinh học, hiển thị các mẫu có liên quan phát hiện ra các hiện tượng sinh học, dẫn đến bằng chứng thuyết phục của cơ chế cụ thể. 3. Kết luận Phân tích dữ liệu biểu hiện gen là một trong những cách hiệu quả để tìm ra chức năng của một gen hoặc một nhóm gen. Dựa trên giả thuyết các gen có mức thể hiện giống nhau trong một điều kiện nào đó thì khả năng có chức năng giống nhau là rất cao. Với lượng dữ liệu biểu hiện gen được đưa ra ngày càng nhiều, yêu cầu có các phương pháp 58
Một thuật toán tìm các biclusters trong dữ liệu biểu hiện gien... tính toán hiệu quả để tìm ra được các mẫu (pattern) đặc biệt xuất hiện trong dữ liệu. 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 để phân tích dữ liệu biểu hiện gen, sử dụng thuật toán biclustering dựa trên cây hậu tố. Thuật toán quy việc tìm các biclusters về bài toán tìm các chuỗi con chung cực đại trên cây hậu tố. Thực nghiệm trên dữ liệu sinh học phân tử, chúng tôi thấy rằng việc tìm ra các biclusters có chất lượng cao sẽ giúp cho các nhà sinh học tiên lượng và dự đoán được chức năng của các phần tử sinh học. TÀI LIỆU THAM KHẢO [1] A.P. Gasch, P. T. Spell man, C. M. Kao, O. Carmel-Harel, M. B. Eisen, G. Storz, D. Botstein and P. O. Brown, 2000. Genomic expression programs in the response of yeast cells to environmental changes. Molecular Biology of the Cell, Vol. 11, pp. 4241-4257. [2] BiGGEsTS: http://kdbio.inesc-id.pt/software/biggests/ [October 6, 2008] [3] CCC- Biclustering. http://kdbio.inesc-id.pt/software/ccc-biclutering [October 6, 2008]. [4] Cheng & Church, 2000. Biclustering of Expression Data. In proc, of the 8th International Conference on Intelligent Systems for Molecular Biology, pp. 93-103. [5] D. Gusfield, 1997. Algorithms on strings, trees and sequences. Computer Science and Computational Biology Series. Cambridge University Press. [6] E. Ukkonen, 1995. On-line construction of suffix trees. Algorithmica, Vol.14, pp. 249-260. [7] S. Tavazoie, J. D. Hughes, M. J. Campbell, R . J. Cho and G. M. Church, 1999. Systematic determination of genetic network architecture. Nature Genetics, Vol. 22, pp. 281-285. ABSTRACT An algorithm finding biclusters from time series gene expression data based on the suffix tree Analyzing time series gene expression data is one of the important tasks to elucidate the functions of the biological elements. With increasing amounts of data, the classical statistical methods are no longer suitable. This creates the need to develop new computational methods for effective analysis of gene expression data sources. In this paper, we present a new approach based on biclustering algorithms (two-way clustering) to find important patterns from large amounts of time series gene expression data. Specifically, we first present an algorithm based on the suffix tree, namely CCC-biclustering, then carry out experiments on two data sets. The results show that the found patterns contain highly similar expression and these pattern can be used to predict new functions of the biological elements. 59