ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Đỗ Thị Nương
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN
CỤM CHO DỮ LIỆU GENE MICROARRAY
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI- 2010
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
ii
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Đỗ Thị Nương
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN
CỤM CHO DỮ LIỆU GENE MICROARRAY
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: Ths. Nguyễn Thị Hậu
HÀ NỘI-2010
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
i
Lời cảm ơn
Trước tiên, tôi muốn gửi lời cảm ơn sâu sắc đến cô Nguyễn Thị Hậu người đã
tận tình chỉ bảo tôi trong suốt quá trình thực hiện khóa luận.
Tôi cũng xin chân thành cảm ơn các thấy cô giáo của trường Đại Học Công
Nghệ, những người đã tận tình chỉ bảo dạy dỗ và trang bị cho tôi những kiến thức quý
báu trong suốt 4 năm học trong trường.
Tôi cũng muốn gửi lời cảm ơn tới những bạn trong lớp K51CD những người đã
đồng hành cùng tôi trong suốt những năm tháng ở giảng đường đại học. Các bạn cũng
luôn động viên và giúp đỡ tôi rất nhiều trong thời gian tôi làm khóa luận.
Cuối cùng, tôi cũng muốn gửi lời cảm ơn vô hạn đến gia đình và các bạn của tôi
những người luôn ở bên động viên tôi để tôi có thể hoàn thành tốt khóa luận này.
Hà Nội, ngày 17 tháng 5 năm 2010
Sinh Viên
Đỗ Thị Nương
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
ii
Tóm tắt nội dung
Dữ liệu microarrays là những bước đột phá mới nhất trong sinh học phân tử.
Nó cho phép kiểm tra mô tả gene của khoảng mười nghìn gene đồng thời.
Kết quả của những thí nghiệm sử dụng công nghệ microarray này sẽ được đem
phân tích ở mức thấp và cho ra một tập dữ liệu gọi là dữ liệu gene micrarray. Dữ liệu
này sẽ được sử dụng cho việc phân tích mức cao hay còn gọi là phân tích cụm (Cluster
analysis). Phân cụm gene tức là nhóm những gene thành những cụm với những đặc
tính tương đồng. Mới xuất hiện từ đầu những năm 1990 đến nay đã và đang có rất
nhiều phòng thí nghiệm, công trình khoa học nghiên cứu về vấn đề phân cụm cho dữ
liệu gene micoarray và vấn đề này ngày càng được quan tâm đầu tư nhiều hơn, bởi vì
những ứng dụng vô cùng to lớn của kết quả nghiên cứu vấn đề này trong nhiều lĩnh
vực như: y học là “chuẩn đoán và điều trị bệnh, khoa học môi trường là “ xác định vi
sinh vật” ”, nông nghiệp….
Khóa luận này sẽ giúp chúng ta tìm hiểu về một số phương pháp phân cụm cho
dữ liệu gene microarray bao gồm “Hierarchical”, “Kmeans”, “SOM”, “PAM” và
phương pháp phân cụm mới dựa trên khoảng cách “intra-cluster”. Đánh giá ưu nhược
điểm của các phương pháp phân cụm này và cuối cùng là phát triển một chương trình
có chức năng “phân cụm”cho “dữ liệu microarray gene” mà sử dụng phương pháp
phân cụm “tối ưu hơn cả”.
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.
iii
Mục lục
Lời cảm ơn...........................................................................................................................i
Tóm tắt nội dung ...............................................................................................................ii
Mục lục...............................................................................................................................iii
Danh mục hình vẽ bảng biểu ..........................................................................................iv
Mở đầu ................................................................................................................................5
Chương 1: Giới thiệu bài toán phân cụm cho dữ liệu gene microarray...................7
1.1. Bài toán phân cụm nói chung ...............................................................................7
1.1.1. Khái niệm........................................................................................................7
1.1.2. Các kiểu phân cụm khác nhau.......................................................................7
1.1.3. Những loại cụm khác nhau ............................................................................8
1.2. Phân cụm cho dữ liệu gene microarray...............................................................9
1.2.1. Giới thiệu công nghệ DNA microarray.........................................................9
1.2.2. Thí nghiệm microarray...................................................................................9
1.3. Ứng dụng bài toán phân cụm cho dữ liệu gene microarray..............................13
Chương 2: Một số phương pháp phân cụm cho dữ liệu gene microarray .............14
2.1. Cơ sở toán học .....................................................................................................14
2.1.1. Biểu diễn dữ liệu gene microarraay ............................................................14
2.1.2. Vector mô tả .................................................................................................14
2.1.3. Ma trận mô tả gene.......................................................................................14
2.1.4. Khoảng cách hay sự tương đồng .................................................................15
2.2. Một số phương pháp phân cụm ..........................................................................17
2.2.1. Phân cụm Hierarchical.................................................................................17
2.2.2. K-Means Clustering (KMC)........................................................................19
2.2.3. Self-Organizing Maps(SOMs).....................................................................20
2.2.4. Principal Components Analysis-(PCA) ......................................................21
2.3. Phương pháp phân cụm intra-cluster ....................................................................22
Chương 3: Đề xuất hướng giải quyết của bài toán phân cụm cho dữ liệu gene
microarray........................................................................................................................24
3.1. Phương pháp phân cụm.......................................................................................24
3.1.1. Lý do chọn K-means .......................................................................................24
3.1.2. Lý do chọn “intra-cluster” ..............................................................................24
3.2. Một số phương pháp khắc phục nhược điểm của k-means...............................25
3.2.1. Lọc dữ liệu....................................................................................................25
3.2.2. K-medians.....................................................................................................25
3.2.3. Xữ lý dữ liệu khuyết: ...................................................................................25
3.2.4. Tìm giải pháp tối ưu “toàn cục” ..................................................................26
3.2.5. Việc xác định số cụm k................................................................................26
Chương 4: Phát triển ứng dụng cho bài toán phân cụm dữ liệu gene microarray
............................................................................................................................................27
Generated by Foxit PDF Creator © Foxit Software
http://www.foxitsoftware.com For evaluation only.