Xem mẫu
- 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
nguon tai.lieu . vn
