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ố

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.
Nội dung trích xuất từ tài liệu:
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ểuhiệ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ậttoá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ểuhiệ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 genthườ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 nhautrong đ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 clusteringlà 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ênlà 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 conthoả 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 sinhhọ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ọcthườ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 sinhhọ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ộtkhoả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ếntrì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 chophé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âmsà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êntụ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ácthuậ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ácbicluster 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óasang 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 conchung 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ộtcấ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ậttoá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 nhaucủ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ậutố, 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éptì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ứcnăng mới cho các gen.2. Nội dung nghiên cứu2.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ántì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 ...