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 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.