Luận Văn Nghiên cứu và ứng dụng các thuật toán biclustering trong việc khai phá các bicluster trong dữ liệu b

MỞ ĐẦU

1. Lý do chọn đề tài

Việc phân tích dữ liệu biểu hiện gien, mà cụ thể là phân nhóm các gien

có sự biểu hiện giống nhau trong từng thời điểm thành các nhóm (cluster)

được thực hiện bởi các thuật toán phân cụm (clustering methods). Các thuật

toán này thường tìm cách nhóm các gien 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 gien 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 gien 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 (hoặc co-clustering). 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 (gien) và

cột (condition) của ma trận dữ liệu biểu hiện gien 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 gien trong các cá thể. Nhưng gần như tất cả các

phương pháp tiếp cận đến nay là heuristic và không đảm bảo để tìm giải pháp

tối ưu.

Trong trường hợp dữ liệu biểu hiện gien theo chuỗi thời gian, thì các

mẫu sinh học thường được đo theo một thời điểm 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 1 tiến trình sinh học, hoặc một giai đoạn

chức năng sinh học nào đó. Việc phân tích trên dữ liệu thể hiện gien cho phép

hiểu được cơ chế điều khiển gien 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

2



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 gien 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 là 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ố.

Trong luận văn này, chúng tôi đặt mục tiêu nghiên cứu và ứng dụng các

thuật toán này trong việc khai phá các bicluster trong dữ liệu biểu hiện gien

theo chuỗi thời gian dựa trên cây hậu tố.

2. Mục đích nghiên cứu

- Nghiên cứu các thuật toán biclustering cho trường hợp dữ liệu biểu

hiện gien theo chuỗi thời gian (nội dung chính)

- Áp dụng một số thuật toán biclustering vào các tập dữ liệu biểu

hiện gien theo chuỗi thời gian cụ thể, phân tích và đánh giá các biclusters

thu được.

3. Đối tượng nghiên cứu

- Các lý thuyết cơ bản về cây hậu tố.

- Các lý thuyết cơ bản về phân cụm dữ liệu và dữ liệu biểu hiện gien

theo chuỗi thời gian.

4. Giả thuyết khoa học

- Việc sử dụng các thuật toán biclustering sẽ cho phép tìm ra được các

gien thể hiện giống nhau trên một khoảng điều kiện, từ đó có thể tìm ra các

gien liên quan đến một số tiến trình sinh học cụ thể.

5. Nhiệm vụ nghiên cứu

- Tìm hiểu một số thuật toán biclustering hiệu quả

- Cài đặt một số thuật toán và thử nghiệm với dữ liệu thực tế

- Phân tích các ưu nhược điểm và cải tiến các thuật toán nếu có thể được.

6. Phạm vi nghiên cứu

- Các thuật toán phân cụm dữ liệu và dữ liệu biểu hiện gien theo chuỗi

thời gian của một số loài.

7. Phương pháp nghiên cứu

- Phương pháp đọc tài liệu, phân tích, tổng hợp lý thuyết

- Phương pháp xây dựng giả thuyết

- Phương pháp quan sát, thực nghiệm và đối chứng.


71



MỤC LỤC



MỞ ĐẦU 1

NỘI DUNG 4

Chương I. GIỚI THIỆU 4

1.1. Dữ liệu biểu hiện gien theo chuỗi thời gian 4

1.2. Các kiểu thuật toán Biclustering . 5

1.2.1. Thuật toán CC-TSB . 6

1.2.2. Thuật toán q-Clustering 7

1.2.3. Thuật toán q-Subsequences . 7

1.2.4. Thuật toán ts-Clustering . 8

1.3. Định nghĩa và bài toán bicluster trong dữ liệu thể hiện gien theo chuỗi

thời gian 10

1.4. Các hướng tiếp cận chính để tìm bicluster trong dữ liệu biểu hiện gien

theo chuỗi thời gian 12

1.5. Mục đích của luận văn 12

1.6. Cấu trúc của luận văn 13

Chương II. CÂY HẬU TỐ . 14

2.1. Giới thiệu chung 14

2.2. Các khái niệm cơ bản. . 14

2.3. Biểu diễn cây hậu tố tổng quát trong máy tính . 17

2.4. Thuật toán dựng cây hậu tố. 18

2.4.1. Dựng cây hậu tố ngầm định (implicit suffix tree) . 18

2.4.2. Dựng cây hậu tố tổng quát 23

2.5. Ứng dụng cây hậu tố. 24

Chương III. THUẬT TOÁN DỰA TRÊN CÂY HẬU TỐ TỔNG QUÁT ĐỂ

TÌM KIẾM CÁC BICLUSTER TRONG DỮ LIỆU BIỂU HIỆN GIEN THEO

CHUỖI THỜI GIAN 26

3.1. Thuật toán CCC-Biclustering 26

3.1.1. Chuẩn hóa dữ liệu biểu hiện gien . 26

3.1.2. CC-Bicluster trong dữ liệu biểu hiện gien theo chuỗi thời gian . 28

3.1.3. Tìm tất cả các bicluster với mẫu biểu hiện hoàn hảo . 29

3.2. Thuật toán e-CCC-Biclustering. . 39

3.2.1. CCC- Bicluster với mẫu biểu hiện xấp xỉ 39

3.2.2 Tìm kiếm e-CCC-Bicluster với các Motif phổ biến. . 42

3.2.3. Tìm và đưa ra tất cả e-CCC-Bicluster cực đại. 47

Chương IV. KẾT QUẢ THỰC NGHIỆM . 56

4.1. Các bộ dữ liệu . 56

4.1.1. Tập dữ liệu Yeaststress 56

4.1.2. Tập dữ liệu CellCycle 58

4.2. Kết quả thực nghiệm . 59

4.2.1. Sử dụng thuật toán CCC-Biclustering. . 59

4.2.2. Sử dụng thuật toán e-CCC-Biclustering . 62

4.3. Đánh giá thuật toán biclustering . 63

4.4. Kết quả và thảo luận 64

KẾT LUẬN 67

TÀI LIỆU THAM KHẢO 69