Dự đoán chức năng protein bằng phương pháp phân cụm dữ liệu

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

Thêm vào BST

Báo xấu

36
lượt xem 2
download

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

Dựa trên giả thuyết “các protein có tương tác với nhau thường có chung một số chức năng nào đó”, trong nghiên cứu này, tác giả đưa ra một phương pháp dự đoán chức năng của protein dựa vào mạng tương tác protein và dữ liệu chú giải chức năng trong từ điển genes. Phương pháp của chúng tôi dựa trên các thuật toán phân cụm (clustering) proteins.

Chủ đề:

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

Lưu

Nội dung Text: Dự đoán chức năng protein bằng phương pháp phân cụm dữ liệu

JOURNAL OF SCIENCE OF HNUE FIT., 2011, Vol. 56, pp. 3-16 DỰ ĐOÁN CHỨC NĂNG PROTEIN BẰNG PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU Nguyễn Quỳnh Diệp, Trần Đăng Hưng(∗) Trần Thị Thu Bình và Phạm Thọ Hoàn Khoa Công nghệ Thông tin - Trường Đại học Sư phạm Hà Nội (∗) E-mail: hungtd@hnue.edu.vn Tóm tắt. Dự đoán chức năng của protein là một trong những bài toán quan trọng trong sinh học phân tử. Bằng nhiều phương pháp khác nhau người ta đã dự đoán được chức năng của rất nhiều protein. Tuy nhiên, có một lượng không nhỏ protein của các loài sinh vật hiện nay còn chưa biết chức năng. Các nhà sinh học thường sử dụng các phương pháp hoá sinh để phân tích và tìm ra chức năng của các protein riêng lẻ. Ngày nay, với sự hỗ trợ của máy tính điện tử và các phương pháp khai phá dữ liệu hiệu quả, các nhà tin học kết hợp với các nhà sinh học đã đưa ra các phương pháp tính toán hiệu quả để đưa ra được chức năng của các protein. Dựa trên giả thuyết “các protein có tương tác với nhau thường có chung một số chức năng nào đó”, trong nghiên cứu này, chúng tôi đưa ra một phương pháp dự đoán chức năng của protein dựa vào mạng tương tác protein và dữ liệu chú giải chức năng trong từ điển genes. Phương pháp của chúng tôi dựa trên các thuật toán phân cụm (clustering) proteins. 1. Mở đầu Có nhiều cách tiếp cận khác nhau để thu được chức năng của protein chưa biết chức năng, nhưng tất cả đều dựa trên những thông tin thu nhận được từ chuỗi gene. Mục đích của chúng tôi, trong bài báo này, là tìm cách gán chức năng cho protein dựa vào việc phân nhóm (clustering) các protein. Để phân nhóm được các protein chúng tôi dựa vào mạng tương tác giữa các protein. Chúng ta biết rằng một protein có thể có tương tác với một hoặc nhiều protein khác, các nghiên cứu [3] cho thấy rằng các protein tương tác với nhau thường có một vài chức năng nào đó khá giống nhau. Cách tiếp cận của chúng tôi là dựa vào tương tác giữa protein-protein và coi đó như là một đồ thị mà mỗi protein là một đỉnh, mỗi tương tác là một cạnh. Dựa vào đồ thị tương tác này sẽ tính được độ đo sự giống nhau giữa các protein, sau đó phân nhóm các protein bằng một thuật toán phân nhóm phù hợp. Những protein cùng nhóm thì có ít nhất một chức năng chung [3]. Vì vậy, việc phân nhóm các protein có thể có ý nghĩa khi phân loại theo chức năng. Về nguyên tắc mỗi protein có thể được gán vào một hoặc nhiều lớp chức năng khác nhau. Một cách làm bình 3
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn thường là gán chức năng cho các protein chưa biết chức năng bằng cách dựa trên chức năng chung mà hầu hết các protein trong nhóm đều có. Bằng các nghiên cứu thực nghiệm [3] người ta phát hiện ra rằng có từ 70%-80% các cặp protein có tương tác với nhau thì có chung ít nhất một chức năng. Phân cụm (clustering) dữ liệu là một kỹ thuật quan trọng trong phân tích dữ liệu và được áp dụng trong nhiều ngành khoa học khác nhau như: sinh học, tâm lý học, y học. . . [4]. Phân cụm là chia dữ liệu thành các nhóm (groups) mà các đối tượng (objects) trong cùng một nhóm thì giống nhau (similary) theo một nghĩa nào đó và khác (dissimilary) với các đối tượng trong các nhóm khác. Mỗi nhóm được gọi là một cluster. Mỗi đối tượng được mô tả bởi một tập các độ đo hoặc bằng mối quan hệ với các đối tượng khác. Phân cụm dữ liệu là một chủ đề được nghiên cứu tích cực trong các lĩnh vực nhận dạng và học máy. Trong nghiên cứu này, chúng tôi đưa ra một lược đồ dựa trên các thuật toán phân cụm dữ liệu để nhóm các protein thành nhiều nhóm khác nhau, sau đó dựa trên thông tin về chức năng của các protein đã biết trong từng nhóm để dự đoán chức năng cho các protein khác. Chúng tôi đã cài đặt và thử nghiệm phương pháp đề xuất trên dữ liệu về protein của loài Yeast. 2. Nội dung nghiên cứu 2.1. Phương pháp 2.1.1. Bài toán Việc tìm ra chức năng mới của các Protein dựa trên mạng tương tác là một trong những bài toán quan trọng. Bài toán này cũng đã được nhiều tác giả trên thế giới giải quyết. Tuy nhiên, khi tham khảo các cách giải quyết của các tác giả, chúng tôi nhận thấy đây là một bài toán hoàn toàn mở và có thể thu được kết quả từ nhiều phương pháp khác nhau. Vấn đề quan trọng nhất trong bài toán này là tìm ra được một độ đo để đánh giá được sự "gần nhau" giữa các protein và phương pháp dùng để phân nhóm các protein. Điểm tựa lớn nhất trong cách giải quyết bài toán của chúng tôi là nhận xét "những protein tương tác với nhau thì thường có chúng một số chức năng nào đó". Bài toán có thể phát biểu như sau: Hình 1. Bài toán dự đoán chức năng Protein 4
Dự đoán chức năng protein bằng phương pháp cụm dữ liệu 2.2. Phân cụm dữ liệu Phân cụm (clutering) là một tiến trình nhóm các đối tượng của một CSDL vào các lớp hoặc các cụm sao cho các đối tượng trong cùng một lớp thì giống nhau hơn so với một đối tượng khác lớp. Sự giống và khác nhau của các đối tượng thường được mô tả dựa trên giá trị các thuộc tính của các đối tượng. Sự giống và khác nhau dùng nhiều nhất là độ đo về khoảng các giữa các đối tượng. Phân cụm là một kỹ thuật được sử dụng trong nhiều lĩnh vực khác nhau như: khai phá dữ liệu, học máy, phân tích dữ liệu, sinh học,... Có nhiều hướng tiếp cận để xây dựng các cluster, cụ thể trong bài báo này chúng tôi trình bày một số hướng tiếp cận chính sau đây: 2.2.1. Phương pháp phân cấp Phương pháp phân nhóm theo kiểu phân cấp (hierarchical) là một thủ tục biến đổi ma trận độ đo thành một chuỗi các phần lồng nhau. Một thuật toán kiểu phân cấp là một dãy các thao tác để thực hiện phương pháp phân cấp. Một cách phân nhóm theo kiểu phân cấp là một dãy các phép chia nhóm sao cho phép chia trước lồng phép chia sau. Có hai thuật toán phân nhóm theo kiểu phân cấp là: chất đống (agglomerative) và phân rã (divisive). Ý tưởng của thuật toán chất đống là: ban đầu ta coi mỗi đối tượng là một nhóm, như vậy có n nhóm. Bước tiếp theo là căn cứ vào độ đo giữa các nhóm và tìm cách trộn hai hoặc nhiều nhóm thành một nhóm. Lặp lại quá trình đó cho đến khi chỉ còn một nhóm chứa n đối tượng. Ý tưởng của thuật toán phân rã thì hoàn toàn ngược lại với thuật toán chất đống. Nghĩa là, ban đầu ta coi cả n đối tượng nằm trong cùng một nhóm, sau đó tìm cách chia dần các đối tượng trong cùng một nhóm thành các nhóm. Tiếp theo, ta chia dần các đối tượng trong cùng nhóm thành nhiều nhóm. Quá trình lặp lại cho đến khi các đối tượng trong cùng nhóm đạt được điều kiện đặt ra. 2.2.2. Phương pháp phân hoạch Kỹ thuật phân nhóm phân cấp được dùng phổ biến trong các ngành khoa học khác nhau như sinh học, xã hội học, tâm lý học,... vì nó có thể đưa ra một cấu trúc phân loại. Còn kỹ thuật phân nhóm phân hoạch được sử dụng trong các ứng dụng kỹ thuật. Phương pháp này có hiệu quả khá tốt trong việc biểu diễn và nén các cơ sở dữ liệu lớn. Vì khi đó không thể biểu diễn bằng một dendrogram. Bài toán đặt ra cho kiểu phân nhóm phân hoạch có thể được phát biểu như sau: Cho n mẫu trong không gian d chiều, tìm cách chia các mẫu đó vào k nhóm (cluster) sao cho các đối tượng trong cùng nhóm thì giống nhau hơn so với một đối tượng ở nhóm khác. Số nhóm k có thể biết trước hoặc không biết trước. Khi phân nhóm phân hoạch thì tiêu chuẩn phân nhóm phải được định nghĩa rõ ràng, chẳng hạn như tiêu chuẩn sai số bình phương (square-error). Tiêu chuẩn phân nhóm có thể chia làm hai loại: Tiêu chuẩn toàn cục biểu diễn mỗi cluster như là một nguyên mẫu (prototype) và như vậy khi phân nhóm chỉ việc gán các đối tượng giống với một nguyên mẫu nhất. Tiêu chuẩn cục bộ xác định cấu trúc của các phần tử trong cùng một nhóm. 5
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn Tuy nhiên, không có tiêu chuẩn nào là tốt nhất cả [5]. Vì mỗi nhóm có các hình dạng bất kì, tùy thuộc vào từng lĩnh vực nghiên cứu. Một trong những tiêu chuẩn phân nhóm phân cấp là dựa trên tiêu chuẩn sai số bình phương. Mục đích là tạo ra các cluster mà tổng sai số bình phương giữa các mẫu là nhỏ nhất. Nói chung, một thuật toán phân cụm phân hoạch áp dụng tiêu chuẩn sai số bình phương thường có các bước như sau: • Khởi tạo phân hoạch: Chọn ra K mẫu vào K cluster, K mẫu này có thể lấy là K mẫu đầu tiên hoặc lấy một cách ngẫu nhiên. Coi như lúc này mỗi cluster có một mẫu. Và trọng tâm của mỗi cluster chính là các mẫu vừa chọn. Sau đó, tính khoảng cách theo công thức sai số bình phương của từng mẫu còn lại đối với K mẫu đã chọn, rồi gán các mẫu này vào cluster mà có khoảng cách đến mẫu là nhỏ nhất. Khi đó, ta được một phân hoạch. Phân hoạch này được gọi là phân hoạch khởi tạo. • Hiệu chỉnh phân hoạch: Bước này thực hiện hiệu chỉnh lại phân hoạch bằng cách: tính lại trọng tâm của từng nhóm. Gán lại các mẫu vào từng nhóm dựa vào khoảng cách theo tiêu chuẩn sai số bình phương. Sau bước này, ta được một phân hoạch mới với xu thế giảm được tổng sai số bình phương. Như vậy, ở bước này ta thấy có sự trộn (merge) và chia (split) các cluster trong phân hoạch hiện thời. Nếu sau bước này mà phân hoạch được tạo ra không có sự sai khác nữa, hay nói cách khác là tổng sai số bình phương không thay đổi nữa thì chuyển sang bước kết thúc. Ngược lại thì lặp lại bước này. • Kết thúc: Thuật toán kết thúc và phân hoạch hiện thời chính là kết quả của thuật toán. Có rất nhiều các thuật toán nổi tiếng đi theo hướng tiếp cận này, như k-means, k-medoids, CLARA [8], CLARANS [9], ... 2.2.3. Phương pháp mật độ Các thuật toán phân cụm theo kiểu phân hoạch và phân cấp làm việc tốt với các cụm có các hình dạng xác định như hình vuông, hình tròn, hình cầu, ... Tuy nhiên, trong nhiều CSDL, các cụm không phải lúc nào cũng có hình dạng xác định. Nhất là các CSDL không gian, các dữ liệu này được thu nhận từ các ảnh vệ tinh và từ các thiết thu thập dữ liệu khác. Chẳng hạn, trong CSDL quan sát trái đất thì các cụm dân cư dọc theo hai bờ sông sẽ có hình dạng bất kì. Ngày nay, các CSDL dữ liệu không gian trên thế giới ngày càng lớn, vì vậy các ứng dụng trên các CSDL không gian đòi hỏi đối với các thuật toán phân cụm phải thỏa mãn một số yêu cầu: • Thứ nhất: Tối thiểu hóa tri thức miền để xác định tham số đầu vào, vì các giá trị tham số thích hợp không được xác định trước khi làm việc với CSDL không gian. • Thứ hai: Phát hiện ra các cụm với hình dạng bất kì (arbitrary shape), vì hình dạng của các cụm trong CSDL không gian có thể là hình cầu, hình thon dài,... hoặc không có hình dạng cụ thể. 6
Dự đoán chức năng protein bằng phương pháp cụm dữ liệu • Thứ ba: Có hiệu quả cao trên các CSDL lớn, tức là thực hiện được trong thời gian cho phép đối với CSDL lớn. Với các yêu cầu như trên thì các thuật toán phân cụm hiện thời không đáp ứng được và một hướng tiếp cận mới dựa trên mật độ (density-based method) của các đối tượng trong CSDL đã ra đời. Ý tưởng cơ bản của hướng tiếp cận này là dựa vào mật độ cao của các điểm trong CSDL để gom chúng vào trong một cụm với một lý luận đơn giản là hai điểm thuộc một cụm thì ta có thể đi từ điểm này sang điểm kia với một bước đủ nhỏ. Tư tưởng đầu tiên của phương pháp mật độ được Jain đưa ra lần đầu tiên vào năm 1988 [5]. Dựa vào mật độ các điểm, Jain đã xác định được các cụm trong các tập điểm k-chiều. Nhưng Ester mới là người đã phát triển và đưa ra các thuật toán phân cụm dựa trên mật độ [10]. Một số thuật toán phân cụm theo hướng tiếp cận mật độ như DBSCAN, DENCLUE. 2.3. Lược đồ giải bài toán Nghiên cứu này đưa ra một lược đồ giải quyết bài toán đặt ra trong phần 2.1.1., tư tưởng chủ đạo của chúng tôi là dựa vào các nguồn thông tin đã có của các protein để phân nhóm và dự đoán ra chức năng mới cho các protein. Bài toán được giải quyết theo lược đồ 5 bước như trong hình vẽ dưới đây. Hình 2. Lược đồ của bài toán • Bước 1: Xử lý dữ liệu Từ các file dữ liệu download trên các trang web, chúng tôi viết các tools để làm sạch và chỉ giữ lại những thông tin cần thiết cho bài toán: - Liệt kê danh sách các protein gồm ID, tên và các Alias của protein. 7
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn - Xử lý các file từ điển để đưa ra một danh sách protein với cả ba loại từ điển là biologicl process, molecular function và cellular component. - Liên kết file danh sách protein và file interactions bằng các Alias của các protein để đưa ra được danh sách các protein có tham gia tương tác với ít nhất một protein khác. Vì mục đích của chúng tôi là dự đoán chức năng dựa vào tương tác giữa các protein, nên những protein không tham gia tương tác thì được loại ngay từ đầu. - Xây dựng danh sách tương tác mới dựa trên file interactions ban đầu bằng cách chỉ giữ lại tên và ID của protein. Đây là file được sử dụng để xây dựng ma trận độ đo giữa các protein. • Bước 2: Xây dựng mạng tương tác từ file dữ liệu tương tác. Đặt ngưỡng tương tác, để hạn chế các protein có ít tương tác, với ngưỡng T hreshold = 4, nghĩa là chỉ xem xét các protein có ít nhất bốn protein khác tương tác với nó thì mới được giữ lại. Do vậy, sau khi đặt ngưỡng, từ danh sách protein ban đầu chỉ còn lại 2003 protein. Từ file tương tác protein-protein đã xây dựng trong Bước 1, chúng tôi xây dựng một đơn đồ thị vô hướng. Mỗi protein là một đỉnh của đồ thị, mỗi tương tác là một cạnh. Đồ thị được xây dựng dưới dạng ma trận quan hệ. • Bước 3: Xây dựng một độ đo giữa các protein có tham gia tương tác Độ đo được xây dựng nhằm đánh giá sự “gần nhau" giữa các protein, sự gần nhau của hai protein A và B được hiểu là số lượng protein chung mà cả hai protein A và B đều tương tác. Độ đo này có tính đối xứng. Kết quả của bước này là một ma trận hai chiều D, mà D(i, j) = D(j, i) và là độ đo sự gần nhau giữa protein i và protein j. Tạm gọi ma trận D là ma trận khoảng cách. • Bước 4: Phân nhóm protein Sử dụng một phương pháp clustering để phân nhóm các protein theo ma trận khoảng cách đã xây dựng trong Bước 3. Trong bước này, chúng tôi sử dụng một chương trình phân nhóm có sẵn để phân nhóm các protein bằng nhiều phương pháp phân nhóm khác nhau, nhằm so sánh và tìm ra cách phân nhóm tốt nhất. Kết quả của bước này là một danh sách các nhóm protein, số lượng protein trong mỗi nhóm có thể khác nhau. • Bước 5: Dự đoán chức năng - Dựa vào danh sách nhóm protein đã đưa ra trong Bước 4, danh sách protein với tên đầy đủ đã xây dựng trong Bước 1 và kết hợp với các từ điển chú giải về ba loại chức năng protein lấy từ GO, chúng tôi đưa ra được một danh sách chi tiết về các protein gồm: tên, ID, các chức năng. - Dựa vào danh sách chi tiết này, chúng tôi phân tích và gán cho các protein chưa biết chức năng theo chức năng của các protein trong cùng nhóm. Ở bước này, chúng tôi sẽ xây dựng một tool để xử lý kết quả trong Bước 4. 8
Dự đoán chức năng protein bằng phương pháp cụm dữ liệu Để dự đoán được chức năng, chúng tôi thống kê tỉ lệ của các chức năng trong cùng nhóm, phân tích xem chức năng nào chiếm tỉ lệ đa số trong nhóm. Nếu trong một nhóm có một chức năng mà hơn 50% protein trong nhóm cùng có, thì có thể gán chức năng này cho các protein chưa biết chức năng trong nhóm đó. 2.4. Định nghĩa độ đo giữa các Protein Một vấn đề quan trọng trong lược đồ giải bài toán của chúng tôi là cách tính độ đo giữa các protein. Độ đo nhằm đánh giá sự "gần nhau" giữa các protein trong danh sách protein. Trong mục Mở đầu, chúng tôi đã nói rằng việc so sánh tập hợp các protein chung mà hai protein cùng tương tác thì cho phép chúng ta tìm ra các chức năng giống nhau giữa các protein. Phương pháp của chúng tôi dựa trên nguyên tắc: các protein có càng nhiều tương tác chung thì chúng càng dễ có các chức năng nào đó chung. Trong phương pháp này chúng tôi sử dụng độ đo Czekanowski-Dice. Giả sử, gọi khoảng cách giữa protein i và j là D(i, j), thì: |Int(i) △ Int(j)| D(i, j) = (2.1) |Int(i) ∪ Int(j)||Int(i) ∩ Int(j)| Trong đó: Int(i) : là số lượng tương tác của protein i. Int(j) : là số lượng tương tác của protein j. Int(i) △ Int(j) : là tổng số tương tác của hai protein i và j sau khi đã loại các tương tác chung (tương tác chung là tương tác mà cả hai protein cùng tương tác với một protein khác). Như vậy: Khi i và j không có tương tác chung nào thì khoảng cách là lớn nhất và bằng 1. Còn khi i và j không có tương tác riêng nào thì khoảng cách là cực tiểu và bằng 0. Ví dụ: Giả sử có 5 protein X, Y, Z, T, U và các tương tác được biểu diển trong hình vẽ sau: Hình 3. Ví dụ về tương tác giữa các protein 9
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn Theo công thức tính khoảng cách trên ta có: |Int(X) △ Int(Y )| 8+3 11 D(X, Y ) = = = = 0.58 |Int(X) ∪ Int(Y )||Int(X) ∩ Int(Y )| 4 + 15 19 Tương tự như thế ta có ma trận khoảng cách D như sau: X Y Z T U X - 0.58 0.27 0.44 0.60 Y 0.58 - 0.5 0.46 0.87 Z 0.27 0.5 - 0.37 0.77 T 0.44 0.46 0.37 - 1.00 U 0.60 0.87 0.77 1.00 - 2.5. Lựa chọn phương pháp clustering Chúng tôi đã sử dụng chương trình CLUTO của đại học Minnesota để lựa chọn phương pháp phân nhóm phù hợp. CLUTO là một chương trình phân nhóm với nhiều tham số đầu vào khác nhau. Chúng tôi đã thử nghiệm rất nhiều phương pháp phân nhóm và số lượng nhóm khác nhau trên ma trận khoảng cách đã xây dựng từ các nguồn dữ liệu được chuẩn bị. Dữ liệu cần phân nhóm là một ma trận khoảng cách, nên chúng tôi lựa chọn phương pháp phân nhóm theo kiểu k − medoid, vì phương pháp phân nhóm này cho ra các cụm dữ liệu tương đối đồng nhất. Chúng tôi cũng đã thử nghiệm các phương pháp phân nhóm theo hướng mật độ nhưng hướng này không cho kết quả tốt trên tập dữ liệu này, vì số lượng nhóm có mật độ cao rất ít, và các protein chưa biết chức năng chỉ tập trung vào một số nhóm nào đó. 3. Kết quả và thảo luận 3.1. Dữ liệu Dữ liệu của bài toán được chúng tôi lấy tại các trang web công cộng dành cho việc nghiên cứu trong lĩnh vực genome. Đây là những kho dữ liệu khổng lồ được cập nhật hàng ngày và miễn phí đối với tất cả mọi người trên thế giới. Trong bài toán cụ thể này, chúng tôi đã lấy dữ liệu từ hai trang web sau: http://www.yeastgenome.org (1) http://www.genontology.org (2) (1) là trang web chứa các thông tin chú giải về các protein của loài Yeast. Các chú giải này bao gồm các thông tin về chuỗi gene, chuỗi protein. Trên trang này cũng chứa một file về tương tác giữa các protein. Các thông tin chỉ nhằm mục đích phục vụ cho các nhà nghiên cứu, nó không được dùng như một thư viện để tra cứu về bệnh tật. (2) là trang từ điển về chức năng của các protein. Đây là một dự án được bắt đầu vào năm 1998, dự án này nhằm xây dựng một hệ thống từ điển về chức năng của các protein của nhiều loài sinh vật khác nhau. 10
Dự đoán chức năng protein bằng phương pháp cụm dữ liệu Sơ đồ các file dữ liệu được xử lý và sử dụng trong chương trình. Hình 4. Sơ đồ các file dữ liệu 3.2. Cài đặt và thử nghiệm chương trình Trên cơ sở tìm hiểu bài toán và phân tích, tổng hợp dữ liệu, chúng tôi đã xây dựng được một chương trình thực nghiệm giải quyết bài toán. Chương trình cho phép từ những dữ liệu đầu vào (mạng tương tác protein và danh sách chức năng protein của một số protein), sẽ cho ra kết quả là dự đoán về chức năng của những protein cùng tương tác. Giao diện chính của chương trình như sau: Hình 5. Giao diện chính của chương trình Chương trình được cài đặt gồm 4 bước như sau: 11
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn • Bước 1: Tính ma trận khoảng cách. Hình 6. Giao diện tính ma trận khoảng cách Với dữ liệu đầu vào là tập danh sách protein và mạng tương tác protein, và danh sách tên protein, cho kết quả là một ma trận 2 chiều chứa thông tin về khoảng cách (độ đo) giữa các protein. • Bước 2: Sử dụng chương trình CLUTO để phân cụm dữ liệu với một số thuật toán phân cụm cổ điển. Dữ liệu cần phân cụm là ma trận khoảng cách giữa các protein (kết quả của Bước 1). Sau bước này, kết quả nhận được là một file dữ liệu chứa danh sách các cụm được liệt kê theo thứ tự của các protein đã sắp xếp trong tập dữ liệu đầu vào. • Bước 3: Tổng hợp tất cả dữ liệu có liên quan đến các protein thành một tập dữ liệu để dự đoán chứa năng của các protein chưa biết chức năng. Hình 7. Giao diện gán chức năng của chương trình 12
Dự đoán chức năng protein bằng phương pháp cụm dữ liệu Dữ liệu vào gồm danh sách tên của các protein, kết quả phân cụm các protein (Bước 2) và file danh sách protein đã biết chức năng. • Bước 4: Thống kê các chức năng của các protein trong cùng một nhóm và dựa vào tỉ lệ thống kê đó để “gán” những chức năng nổi trội (đạt tỷ lệ % cao trong nhóm) cho những protein chưa biết chức năng còn lại trong nhóm đó. Hình 8. Giao diện dự đoán chức năng của chương trình Dữ liệu đầu vào cho Bước 4 chính là file kết quả thu được sau khi thực hiện Bước 3. Chương trình còn cho phép người sử dụng xem các file dữ liệu đầu vào và các file kết quả tương ứng. 3.3. Kết quả và thảo luận Như chúng tôi đã trình bày ở trên, vấn đề quan trọng nhất để giải quyết bài toán là tìm ra được một độ đo để đánh giá sự "gần nhau" giữa các protein và phương pháp dùng để phân nhóm các protein. Về độ đo, chúng tôi đã sử dụng độ đo Czekanowski-Dice và đã đưa ra được một ma trận vuông được mô tả trong hình sau: Hình 9. Ma trận khoảng cách 13
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn Từ ma trận khoảng cách này, chúng tôi đã tiến hành phân cụm protein bằng cách sử dụng chương trình CLUTO của nhóm tác giả George Karypis của trường đại học Minnesota [6]. Chương trình gồm 2 tập tin: vcluster.exe (file chạy chính của chương trình), libcluto.lib (file thư viện của chương trình). Để chạy chương trình, cần sao chép các tập tin này và tập ma trận khoảng cách sang thư mục gốc của ổ đĩa C. Sau đó, vào Start/run/ gõ cmd. Tại thư mục gốc của ổ đĩa C, gõ lệnh vcluster với các tham số cần thiết. Từ một tập gồm n đối tượng (đã xác định ma trận khoảng cách giữa chúng), với yêu cầu cần phân chia thanh k cụm, chương trình cần các tham số: Tham số −clmethod cho phép lựa chọn thuật toán phân cụm, tham số −clf un cho phép lựa chọn hàm tiêu chuẩn phân cụm, Tham số −sim cho phép lựa chọn cách tính độ đo, hai tham cuối cùng là tên tệp ma trận khoảng cách và số cụm. Các tham số được sử dụng lần lượt như sau: −Clmethod = string. Tham số này lựa chọn phương pháp được sử dụng cho cụm các đối tượng. Các giá trị có thể là: rb: Với thuật toán này, k-cụm được tạo thành bằng cách chia đôi liên tiếp k − 1 lần các tập đối tượng. Tập đối tượng ban đầu được chia thành 2 nhóm, sau đó một trong 2 nhóm sẽ được lựa chọn và chia đôi sau đó. Quá trình này sẽ tiếp tục cho đến khi số cụm đạt yêu cầu. Tại mỗi bước chia, kết quả đạt được dựa theo một hàm tiêu chuẩn được lựa chọn trong tham số −clf un. direct: Từ tập gồm n đối tượng ban đầu, chia ngẫu nhiên để được k-cụm. Phương pháp này sẽ hiệu quả hơn phương pháp rb trong trường hợp k tương đối nhỏ (10 - 20), tuy nhiên khi k tăng thì phương pháp rb lại tỏ ta hiệu quả hơn. agglo: Phương pháp này dựa theo thuật toán chất đống đã nêu ở Mục 2.1.1.. −sim = string. Lựa chọn các chức năng tương tự sẽ được sử dụng cho clus- tering, các giá trị có thể là: cos: Sự tương đồng giữa các đối tượng được tính toán bằng cách sử dụng hàm cosin. Đây là thiết lập mặc định. corr: Sự tương đồng giữa các đối tượng được tính toán bằng cách sử dụng hệ số tương quan. Như vậy, có 2 tham số cần quan tâm để đánh giá chương trình này. Chúng tôi đã thực hiện chương trình lần lượt với các thuật toán và đạt được kết quả như sau (trong các thuật toán chúng tôi chỉ giữ lại những kết quả có tỉ lệ dự đoán ≥ 20%): -Clmethod = rb -sim=cos matrankhoangcach.txt 50 YPL246C cell wall organization and biogenesis* 30.8% -Clmethod = rb -sim=cos matrankhoangcach.txt 100 YDR091C translational initiation 60.0% 14
Dự đoán chức năng protein bằng phương pháp cụm dữ liệu YPL246C actin filament organization* 33.3% -Clmethod = direct -sim=cos matrankhoangcach.txt 100 YNL132W processing of 20S pre-rRNA 35.7% YML056C meiotic recombination 50.0% YLR096W establishment of cell polarity (sensu Fungi)* 40.0% YDL105W chromosome segregation 31.3% -Clmethod = direct -sim=corr matrankhoangcach.txt 100 YEL005C chromatin silencing at telomere* 75.0% YNL132W processing of 20S pre-rRNA 39.4% YCR030C protein biosynthesis 50.0% YBR162C ER to Golgi transport* 61.9% -Clmethod = agglo -sim=cos matrankhoangcach.txt 100 YER047C cell wall organization and biogenesis* 36.4% YDR091C translational initiation 66.7% YJR070C gluconeogenesis* 50.0% YNL132W processing of 20S pre-rRNA 33.3% YGL068W chromatin assembly or disassembly 66.7% YDR032C actin filament organization* 50.0% 4. Kết luận Trong nghiên cứu này, chúng tôi đưa ra một phương pháp dự đoán chức năng của các protein dựa trên các thuật toán phân cụm (clustering). Phương pháp chúng tôi đề xuất gồm 5 bước, nhằm tích hợp thông tin từ nhiều nguồn dữ liệu khác nhau (như PPIs, Gene Ontology) để dự đoán chức năng của các protein. Chúng tôi đã xây dựng chương trình và thử nghiệm trên dữ liệu chú giải gene và mạng tương tác protein của loài Yeast. Việc tích hợp các nguồn dữ liệu này cho phép chúng tôi dự đoán được chức năng của các protein với độ chính xác cao. REFERENCES [1] http://www.yeastgenome.org [2] http://www.genontology.org [3] Alexei, 2003. Global protein function prediction from protein-protein interaction networks. Nature Biotechnology, 21, 697-700. [4] Anthony K.H.Tung, Jean Hou, Jiawei Han, 2001. Spatial Clustering in the Pres- ence of Obstacles. Proceedings of 17th International Conference on Data Engi- neering, 359-367. [5] Anil K.Jain, Richard C. Dubes, “Algorithms for clustering data”, Prentice Hall, 1988. [6] George Karypis, 2003. CLUTO – A Clustering Toolkit. University of Minnesota, Department of Computer Science Minneapolis, November 28. 15
Nguyễn Quỳnh Diệp, Trần Đăng Hưng, Trần Thị Thu Bình và Phạm Thọ Hoàn [7] Kaufman and Rousseeuw, 1987. Clustering by Means of Medoids. Statistical Data Analysis based on the L1 Norm”, Elsevier, Berlin. [8] Raymond T. Ng, Jiawei Han, 1994. Efficient and Effective Clustering Methods for Spatial Data Mining. Proceedings of the 20th International Conference on Very Large Data, 145-156. [9] Raymond T. Ng, Jiawei Han, 2002. CLARANS: a method for clustering objects for spatial data mining. IEEE Transaction on Knowledge and Data Engineering, 14(5), 1003-1016. [10] Ester M., Kriegel H., Sander J., Xu X., 1996. A density-based algorithm for dis- covering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), 125-131. ABSTRACT Prediction of protein functions by a clustering-based algorithm Prediction of protein function is one of the most important problems in the molecular biology research. By using different methods, the function of most pro- teins are revealed. However, some of the remains still are unknown proteins. The biologists usually use the bio-technical methods to find out the function of one by one protein. Nowadays, with support from the strong computers and the modern data mining methods, efficient computational methods have been proposed for dis- covering protein functions. Based on the assumption that if two proteins interact with each other, they may have the same functions. In this research we propose a novel method that incorporates the protein-protein interaction network and the protein annotations to infer the new protein functions. The method is based on a clustering algorithms. 16