Phân cụm dữ liệu và ứng dụng trong phân loại cấu trúc Protein

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG

TRẦN ĐỨC THUẬN

PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG

TRONG PHÂN LOẠI CẤU TRÚC PROTEIN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG

TRẦN ĐỨC THUẬN

PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG

TRONG PHÂN LOẠI CẤU TRÚC PROTEIN

Chuyên ngành: Khoa học máy tính

Mã số: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: PGS.TS. ĐOÀN VĂN BAN

THÁI NGUYÊN - 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

LỜI CAM ĐOAN

Tôi xin cam đoan bản luận văn “Phân cụm dữ liệu và ứng dụng trong phân

loại cấu trúc protein" là công trình nghiên cứu riêng của tôi. Các số liệu trong

luận văn đƣợc sử dụng trung thực. Kết quả nghiên cứu đƣợc trình bày trong luận

văn này chƣa từng đƣợc công bố tại bất kỳ công trình nào khác.

Tôi cũng xin chân thành cảm ơn các thầy cô trong Viện Công nghệ

Thông tin, các thầy cô trong Trƣờng Công Nghệ Thông Tin và Truyền thông

Thái Nguyên, thầy giáo Trần Đăng Hƣng - Giảng viên Khoa Công nghệ thông

tin và Trung tâm khoa học tính toán, Đại học Sƣ phạm Hà Nội, các bạn bè,

đồng nghiệp tại Trung tâm Thông tin Công nghệ - Sở Khoa học Công nghệ

Thái Nguyên, Cục Dự trữ Nhà nƣớc khu vực Bắc Thái đã giúp đỡ tôi rất

nhiều trong quá trình học tập, sƣu tầm, tìm tòi tài liệu và trong công tác để tôi

có thể hoàn thành bản luận văn này.

Tôi xin bày tỏ lòng kính trọng, và biết ơn sâu sắc tới PGS.TS Đoàn Văn

Ban, ngƣời đã trực tiếp hƣớng dẫn, giúp đỡ tôi trong suốt thời gian thực hiện

luận văn này.

Thái Nguyên, tháng 08 năm 2012

Học viên

Trần Đức Thuận

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ii

MỤC LỤC

Lời cam đoan ..........................................................................................................................i

Mục lục ..................................................................................................................................ii

Danh mục bảng biểu ..............................................................................................................v

Danh mục các hình ................................................................................................................v

Mở đầu...................................................................................................................................1

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

2. Mục tiêu nghiên cứu ......................................................................................................1

3. Phƣơng pháp nghiên cứu ...............................................................................................2

4. Tổng quan luận văn........................................................................................................2

CHƢƠNG 1-TỔNG QUAN LÝ THUYẾT VỀ PHÂN CỤM DỮ LIỆU .............................3

1.1. Tổng quan về phân cụm dữ liệu..................................................................................3

1.2. Phân cụm trong phân loại dữ liệu ...............................................................................4

1.3. Các yêu cầu của phân cụm dữ liệu.............................................................................6

1.4. Các kiểu dữ liệu trong phân cụm................................................................................8

1.4.1. Phân loại kiểu dữ liệu dựa trên kích thƣớc miền .................................................9

1.4.2. Phân loại kiểu dữ liệu dựa trên hệ đo .................................................................9

1.5. Các phép đo độ tƣơng tự và khoảng cách đối với các kiểu dữ liệu ..........................10

1.5.1. Khái niệm tƣơng tự và phi tƣơng tự ..................................................................10

1.5.2. Thuộc tính khoảng cách....................................................................................11

1.5.3. Thuộc tính nhị phân ..........................................................................................13

1.5.4. Thuộc tính định danh ........................................................................................15

1.5.5. Thuộc tính có thứ tự..........................................................................................16

1.5.6. Thuộc tính tỉ lệ...................................................................................................16

1.6. Kết luận chƣơng........................................................................................................17

CHƢƠNG 2 - KỸ THUẬT PHÂN CỤM DỮ LIỆU ỨNG DỤNG TRONG PHÂN LOẠI

CẤU TRÚC PROTEIN .......................................................................................................18

2.1. Giới thiệu ..................................................................................................................18

2.2. Thuật toán K-means..................................................................................................18

2.3. Thuật toán PAM........................................................................................................22

2.4. Thuật toán CLARA...................................................................................................24

2.5. Thuật toán CLARANS..............................................................................................26

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iii

2.6. Kết luận chƣơng........................................................................................................28

CHƢƠNG 3 - TIN SINH HỌC VÀ PHÂN LOẠI CẤU TRÚC PROTEIN .......................29

3.1. Tổng quan về tin sinh học.........................................................................................29

3.1.1. Chủ thuyết trung tâm của sinh học phân tử .......................................................29

3.1.2. DNA (DesoxyriboNucleic Acid) .......................................................................30

3.1.3. RNA (RiboNucleic Acid) ..................................................................................31

3.1.4. Protein................................................................................................................31

3.1.5. Các dạng protein. ...............................................................................................32

3.2. Các phƣơng pháp phân loại cấu trúc protein ............................................................34

3.2.1. Phân loại cấu trúc với SCOP .............................................................................38

3.2.2. Phân loại cấu trúc với CATH.............................................................................39

3.2.3. Phân loại cấu trúc với phân loại miền Dali (DDD) ...........................................40

3.3. Kết luận chƣơng........................................................................................................41

CHƢƠNG 4 - CHƢƠNG TRÌNH DEMO VỚI PHẦN MỀM CLUSTERS 3.0.................42

4.1. Phần mềm Clusters 3.0 .............................................................................................42

4.1.1. Yêu cầu phần cứng.............................................................................................42

4.1.2. Nguồn dữ liệu demo chƣơng trình.....................................................................42

4.1.3. Sử dụng thƣ viện phân cụm ...............................................................................42

4.2. Sử dụng thuật toán K-mean, K-medians...................................................................43

4.2.1. Khởi tạo .............................................................................................................43

4.2.2. Tìm trọng tâm cụm ............................................................................................44

4.2.3. Tìm trung bình cụm, hoặc trung vị cụm ............................................................44

4.2.4 Tìm giải pháp tối ƣu với K-means và K-medians...............................................46

4.3. Phần mềm demo........................................................................................................48

4.3.1. Đầu vào của chƣơng trình..................................................................................48

4.3.2. Giao diện một số chức năng chính của chƣơng trình ........................................49

4.3.3. Tệp đầu ra của chƣơng trình ..............................................................................52

KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU .........................................................................53

Kết luận............................................................................................................................53

Hƣớng nghiên cứu trong thời gian tới .............................................................................53

TÀI LIỆU THAM KHẢO ...................................................................................................54

PHỤ LỤC ............................................................................................................................56

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iv

BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT

Chữ viết tắt Nghĩa tiếng anh Nghĩa tiếng việt

DNA DesoxyriboNucleic Acid

Phân tử nucleic acid mang thông

tin di truyền mã hóa cho hoạt

động sinh trƣởng và phát triển

của các dạng sống

RNA RiboNucleic Acid

Là một trong hai loại axít

nucleic, là cơ sở di truyền ở cấp

độ phân ử.

PAM Partitioning Around Medoids Thuật toán phân cụm phân vùng

xung quanh Medoids

CLARA Clustering Large Application Thuật toán phân cụm ứng dụng

lớn

CLARANS

Clustering Large Applications

based upon RANdomized

Search

Thuật toán phân cụm với ứng

dụng lớn trên cơ sở tìm kiếm

ngẫu nhiên

rRNA ribosome RNA Là ARN mã hóa và mang thông

tin từ ADN

tRNA transfer RNA Là RNA vận chuyển

mRNA messenger RNA RNA thông tin

SCOP Structural Classification of

Proteins Phân loại cấu trúc các protein

CATH Class Architecture Topology

Homologous superfamily

Phân loại cấu trúc protein với

CATH

DDD Dali Domain Dictionary Từ điển miền Dali

PDB Protein Data Bank Ngân hàng dữ liệu protein

FSSP Families of Structurally

Similar Proteins

Dòng họ protein với cấu trúc

tƣơng tự

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

v

DANH MỤC BẢNG BIỂU

Bảng 1.1 Bảng dự đoán cho hai đối tƣợng nhị phân x và y……………... 14

Bảng 1.2 Ví dụ về độ phi tƣơng tự của thuộc tính nhị phân…………….. 15

Bảng 2.1. Bảng so sánh các thuật toán phân cụm trung tâm……………. 28

Bảng 3.1 Đƣa ra một số nguồn tài nguyên phân loại trình tự protein…... 35

Bảng 3.2 Nguồn tài nguyên cho phân loại cấu trúc protein……………... 36

Bảng 3.3 Các cấp độ chính của CATH………………………………….. 39

DANH MỤC CÁC HÌNH

Hình 1.1. Phân cụm các vector truy vấn .................................................... 5

Hình 1.2. Hình thành cụm cha ................................................................... 6

Hình 1.3. Các tỉ lệ khác nhau có thể dẫn tới các cụm khác nhau .............. 12

Hình 2.1 Sơ đồ phân loại các phƣơng pháp phân cụm………………….. 18

Hình 2.2. Các thiết lập để xác định danh giới các cụm ban đầu................ 19

Hình 2.3. Tính toán trọng tâm của các cụm mới........................................ 20

Hình 2.4 Ví dụ minh họa thuật toán K-means........................................... 21

Hình 2.5 Ví dụ minh họa thuật toán PAM ................................................ 24

Hình 3.1. Chủ thuyết trung tâm của sinh học phân tử ............................... 30

Hình 3.2. Cấu trúc DNA ............................................................................ 30

Hình 3.3. Các kiểu cấu trúc của Protein..................................................... 32

Hình 3.4. Cấu trúc bậc 2 thƣờng thấy của protein ..................................... 33

Hình 3.5. Hai ví dụ về protein màng.......................................................... 34

Hình 3.6. Sự phát triển của cấu trúc dữ liệu protein .................................. 35

Hình 4.1 Đầu vào dữ liệu………………………………………………... 48

Hình 4.2 Giao diện chọn tệp đầu vào……………………………………. 49

Hình 4.3 Giao diện tab Lọc dữ liệu…………………………………….. 49

Hình 4.4 Giao diện tab chỉnh sửa dữ liệu………………………………. 50

Hình 4.5 Giao diện Tab K-Means, sử dụng K-means hoặc K-medians để

phân cụm…………………………………………………………………

51

Hình 4.6 Đầu ra dữ liệu…………………………………………………. 52