Khóa luận Nghiên cứu một số phương pháp phân cụm cho dữ liệu gene microarray
Generated by Foxit PDF Creator © Foxit Software
ĐẠ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
ĐẠ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
ii
Generated by Foxit PDF Creator © Foxit Software
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
i
Generated by Foxit PDF Creator © Foxit Software
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ả”.
ii
Generated by Foxit PDF Creator © Foxit Software
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
iii
Generated by Foxit PDF Creator © Foxit Software
4.1. Các chức năng của ứng dụng..............................................................................27
4.1.1.Mô hình tương tác giữa các module................................................................27
4.1.2. Tải, Lưu file, lọc, điều chỉnh dữ liệu và xử lý dữ liệu khuyết...................28
4.1.3. Phân cụm K-means.......................................................................................31
4.3. Định dạng dữ liệu vào, ra....................................................................................32
4.3.1. Dữ liệu tải vào ..............................................................................................32
4.3.2. Định dạng dữ liệu ra.....................................................................................33
4.4. Ngôn ngữ lập trình ..............................................................................................33
4.4.1. Một số ưu điểm của ngôn ngữ lập trình Java.............................................33
4.5. Môi trường phát triển ứng dụng .........................................................................35
Chương 5: Thực nghiệm và đánh giá...........................................................................36
5.1. Cài đặt ứng dụng “Gene Cluster”.......................................................................36
5.1.1. Cài đặt ứng dụng ..........................................................................................36
5.2.1. Mô tả các tập dữ liệu thực nghiệm..............................................................36
5.2.2. Thực nghiệm trên “Cluster 3.0” và “Gene Cluster”...................................37
5.3. Kết quả và đánh giá.............................................................................................38
5.3.1. Kết quả..........................................................................................................38
5.3.2. Đánh giá........................................................................................................40
Tổng kết ............................................................................................................................42
Tài liệu tham khảo...........................................................................................................43
Danh mục hình vẽ bảng biểu
Hình 1: Thí nghiệm microarray........................................................................................11
Hình 2: Minh họa việc tính dữ liệu mô tả gene...............................................................12
Hình 3: Ví dụ về vector mô tả gene trong log .................................................................14
Hình 4: Ví dụ về ma trận mô tả gene ...............................................................................15
Hình 5: Mô tả những phương pháp linkage khác nhau...................................................19
Hình 6 : Sơ đồ DFD mô tả sự tương tác dữ liệu và chức năng.......................................28
Hình 7: Giao diện cho menu của chương trình................................................................29
Hình 8: Giao diện cho chức năng filter data....................................................................29
Hình 9: Giao diện minh hoa cho chức năng adjust data. ................................................30
Hình 10: Giao diên chức năng xử lý dữ liệu khuyết. ......................................................31
Hình 11: Giao diện chính của chương trình phân cụm “Gene Cluster”.........................32
Hình 12 : Mô tả định dạng dữ liệu tải vào.......................................................................32
Hình 13: Mô hình thực thi của một chương trình bằng Java..........................................34
Hình 14: Hình ảnh phóng to của một số gene trong kết quả phân cụm K-means trên
“Cluster 3.0” ......................................................................................................................39
Hình 15: Hình ảnh phóng to của một số gene trong kết quả phân cụm K-means trên
“Gene Cluster” không sử dụng chức năng sử lý dữ liệu khuyết. ...................................39
Hình 15: Hình ảnh phóng to của một số gene trong kết quả phân cụm K-means trên
“Gene Cluster” sử dụng chức năng sử lý dữ liệu khuyết................................................40
Hình 16: Kết quả thời gian chạy Kmeans trên “dataset1” ..............................................40
iv
Generated by Foxit PDF Creator © Foxit Software
Mở đầu
Hầu hế những tế bào trong các cơ quan của sinh vật nhân thực-eukaryota đều
chứa những bổ xung đầy đủ của những gene mà tạo lên toàn bộ hệ gene của cơ quan
đó. Những gene này được biểu hiện một cách chọn lọc trong mỗi tế bào phụ thuộc vào
từng loại tế bào, từng loại mô, và những điều kiện cả bên trong lẫn bên ngoài tế bào.
Do sự phát triển của những kỹ thuật sinh học phân tử và tái tổ hợp gene mà đã đưa ra
một kết luận rằng những sự kiện quan trọng trong đời sống của một tế bào là được quy
định bởi những nhân tố mà làm thay đổi những miêu tả của các gene của chúng. Vì
vậy việc hiểu mô tả của các gene đã trở thành lĩnh vực quan trọng trong việc nghiên
cứu sinh học hiện đại. Hai câu hỏi chính đặt ra khi quản lý việc miêu tả của gene là:
Việc mô tả gene làm cách nào có thể phát hiện ra chức năng của tế bào và bệnh lý của
tế bào? Những câu hỏi này có thể được phân chia chi tiết như sau:
Mức độ mô tả của gene trong những tế bào và những trạng thái khác nhau thì
khác nhau như thế nào?
Những chức năng của các genes khác nhau là gì? Và những mô tả của những
gene này thay đổi như thể nào tương ứng với những thay đổi vật lý bên trong môi
trường của tế bào.
Mô tả gene bị tác động bởi những loại bệnh như thế nào? Những gene nào quy
định tính di truyền của các bệnh.
Những gene nào bị tác động trong quá trình điều trị bệnh.
Những thay đổi của những giá trị mô tả gene là gì trong theo chuỗi thời gian tiến
hành thí nghiệm.
Trước khi phát triển công nghệ DNA microarray đã có một số phương pháp được
sử dụng để phân tích những mẫu mô tả của những gene. Tuy nhiên những phương
pháp này đều có hạn chế là chỉ thực hiện được trên một số ít các mẫu gene vì vậy
không đem lại hiệu quả cao.
Khi có sự xuất hiện của công nghệ micoarray, nó đã đưa ra được bước chuyển
biến mạnh mẽ trong việc phân tích những mẫu mô tả của hàng chục nghìn gene một
cách nhanh chóng và hiệu quả. Để có thể trả lời một cách chính xác và thỏa đáng
những câu hỏi trên thì bài toán đặt ra là “ tìm các phương pháp để phân cụm cho dữ
liệu gene microarray một cách hiệu quả”.
Khóa luận này sẽ giúp tìm hiểu về một số phương pháp cụm cho phổ biến. Tìm
ra những ưu nhược điểm của những phương pháp này và nghiên cứu những giải pháp
khắc phục những ưu nhược điểm đó.
Ngoài phần MỞ ĐẦU và KẾT LUẬN, kết cấu của khoá luận bao gồm các
chương sau:
Chương 1: Giới thiệu bài toán phân cụm cho dữ liệu gene microarray.
Giới thiệu về công nghệ DNA microarray, Thí nghiệm microarray và ứng dụng.
Trình bày thí nghiệm sử dụng công nghệ DNA microarray sau đó là việc phân tích kết
5
Generated by Foxit PDF Creator © Foxit Software
quả của thí nghiệm này ở mức thấp và mức cao. Đưa ra một ứng dụng cụ thể sử dụng
công nghệ này.
Chương 2: Một số phương pháp phân cụm cho dữ liệu gene microarray.
Tìm hiểu một số phương pháp phân cụm phổ biển. Đánh giá những ưu nhược
điểm, tìm hiểu và đưa ra những hướng tiếp cận mới để khắc phục một số nhược điểm
của các phương pháp này. Trình bày một ứng dụng thực tế của việc phân cụm cho dữ
liệu gene microarray.
Chương 3: Hướng giải quyết của bài toán phân cụm cho dữ liệu gene
microarray.
Chương này sẽ đưa ra phương pháp phân cụm được chọn để cài đặt và một số
phương pháp khắc phục nhược điểm của phương pháp này.
Chương 4: Phát triển ứng dụng phân cụm cho dữ liệu gene microarray.
Chương 5: “Thực nghiệm, đánh giá và kết luận”.
Thực nghiệm trên phần mềm phân cụm trên một số tập dữ liệu và đánh giá kết
quả.
6
Generated by Foxit PDF Creator © Foxit Software
Chương 1: Giới thiệu bài toán phân cụm cho dữ
liệu gene microarray
1.1. Bài toán phân cụm nói chung
Trước khi thảo luận việc phân cụm cho dữ liệu gene microarray ta sẽ đi tìm hiểu
về khái niệm phân cụm nói chung. Đầu tiên, ta sẽ đi định nghĩa về phân tích cụm,
chứng minh vì sao nó khó và giải thích mối quan hệ của nó với các kỹ thuật nhóm dữ
liệu khác. Sau đó chúng ta sẽ đi khai thác 2 chủ đề quan trọng: (1) những cách nhóm
một tập các đối tượng thành một tập những cụm và (2) những loại cụm.
1.1.1.Khái niệm
Phân cụm là nhóm những đối tượng dựa trên thông tin mà tìm thấy trong dữ liệu
miêu tả đối tượng và những mối quan hệ của chúng. Mục đích của việc phân cụm là để
đạt được những đối tượng trong cùng một cụm là giống nhau và khác với những đối
tượng của cụm khác. Tính tương đồng trong một nhóm càng nhiều và sự khác nhau
giữa những nhóm càng lớn thì các cụm càng phân biệt nhau hơn.[12]
Việc đưa ra cụm tốt nhất còn phụ thuộc vào bản chất của dữ liệu và kết quả mong
muốn.
Phân tích cụm là liên quan đến những kỹ thuật mà để phân chia những đối tượng
thành nhóm. Ví dụ, phân cụm có thể được xem như là một dạng của phân lớp ở đó nó
tạo ra việc gán nhãn cho những đối tượng những cái nhãn lớp(cụm). Tuy nhiên nó dẫn
xuất những nhãn này chỉ từ dữ liệu của các đối tượng. Trái lại, việc phân lớp còn được
xem như là phân lớp có quan sát; ví dụ, những đối tượng mới, chưa được gán nhãn sẽ
được gán cho một nhãn lớp sử dụng một mô hình được phát triển từ những đối tượng
mà đã biết trước nhãn lớp của chúng. Vì lý do này phân cụm đôi khi được biết đến như
phân lớp không có quan sát.
Cũng như vậy, trong khi những thuật ngữ phân mảnh và phân vùng đôi khi được
sử dụng với nghĩa tương tự như phân cụm, những thuật ngữ này thường được sử dụng
cho những tiếp cận bên ngoài phạm vi truyền thông của việc phân tích cụm. Ví dụ,
việc phân vùng thường được sử dụng liên quan đến kỹ thuật phân chia những đồ thị
thành những đồ thị con và không liên quan nhiều đến việc phân cụm. Phân mảnh
thường chỉ đến việc phân chia dữ liệu thành những nhóm sử dụng những kỹ thuật đơn
giản ví dụ những hình ảnh có được phân chia thành những mảnh chỉ dựa trên cường độ
điểm ảnh và mầu sắc hay con người có thể được chia thành những nhóm dựa trên thu
nhập của họ. Tuy nhiên cũng có một vài công việc liên quan đên phân vùng đồ thị và
phân mảnh thị trường là liên quan đến phân cụm.
1.1.2.Các kiểu phân cụm khác nhau
Trong phân trước tôi đã trình bày định nghĩa phân cụm, phần này sẽ trình bày về
các kiểu phân cụm khác nhau:
Phân cụm Cấu trúc với Phân vùng (Hierarchical vs Partitional) [12]
7
Generated by Foxit PDF Creator © Foxit Software
Kiểu phân cụm được thảo luận nhiều nhất trong số những kiểu phân cụm là tập
những cụm được “lồng nhau” hay “không lồng nhau” hay theo một thuật ngữ truyền
thống hơn là “cấu trúc” hay “phân vùng”. Phân cụm phân vùng đơn giản là phân chia
tập những đối tượng dữ liệu thành những tập con (những cụm) không gối trồng lên
nhau như là mỗi đối tượng dữ liệu chỉ ở một tập con.
Nếu chúng ta cho phép những cụm có những cụm con thì chúng ta sẽ thu được
phân cụm cấu trúc, chúng là một tập những cụm lồng nhau mà có thể được tổ chức
như một cây. Mỗi nút (cụm-cluster) trên cây ngoại trừ nút lá là hợp của những con
(những cụm con) của nó, và gốc của cây là những cụm mà chứa tất cả những đối
tượng.
Phân cụm mức đỉnh (exclusive), gối chồng (overlapping) và mờ (fuzzy)[12]
Phân cụm “mức đỉnh”: Gán mỗi đối tượng tới một cụm đơn.
Có rất nhiều trường hợp mà một đối tướng có thể phù hợp cho nhiều hơn một
cụm, những trường hợp này được gọi là non-exclusive. Theo một nghĩa chung nhất
overlapping hay non-exclusive thường được sử dụng để chỉ đến một đối tượng mà
đồng thời có thể thuộc nhiều hơn một cụm. Phân cụm non-exclusive một đối tượng là
ở giữa 2 hay nhiều hơn cụm và có thể được gán cho bất kỳ cụm nào trong số những
cụm này.
Trong phân cụm fuzzing mỗi đối tượng phụ thuộc vào mỗi cụm với ‘trọng số
thành viên ‘ nằm giữa 0 và 1 là 0 tức là tuyệt đối không phụ thuộc, 1 tức là tuyệt đối
phụ thuộc. Theo nghĩa khác, những cụm này được xem như là những tập ‘mờ’ hay
fuzzy. ( Theo toán học những tập mờ là tập mà một đối tượng phụ thuộc vào bất kỳ tập
nào với trọng lượng nằm giữa 0 và 1. Trong phân cụm mờ chúng ta thường cho thêm
ràng buộc tổng trọng lượng của mỗi đối tượng phải bằng 1. Trong thực tế, phân cụm
mờ thường được chuyển thành phân cụm mức đỉnh bằng việc gán mỗi đối tượng tới
cụm mà trọng lượng thành viên của nó là cao nhất.
Phân cụm một phần với đầy đủ(complete vs patial)[12]: Việc phân cụm đầy đủ
gán mỗi đối tượng tới cụm còn phân cụm một phần thì không . Động lực cho phân
cụm một phần là một vài đối tượng trong tập dữ liệu có thể không thuộc vào những
nhóm hoàn toàn xác định. Tức là đôi khi những đối tượng trong tập dữ liệu có thể có
biểu diễn khác đi.
1.1.3.Những loại cụm khác nhau
Mục tiêu của phân cụm là tìm ra những cụm hữu ích tức là phù hợp với mục đích
của việc phân tích dữ liệu. Dưới đây sẽ trình bày một số loại cụm tuy nhiên nó cũng
chỉ hiệu quả cho một số loại dữ liệu.
Phân chia rõ ràng (Well-Separated)[12] Cụm là một tập các đối tượng mà
những đối tượng trong cùng một cụm giống nhau hơn bất kỳ những đối tượng trong
cụm khác.
Dựa trên mẫu(Prototype – Based)[12] Một cụm mà tập những đối tượng trong
đó mỗi đối tượng trong một cụm gần với “mẫu” của cụm đó hơn là gần với mẫu của
cụm khác. Với dữ liệu có thuộc tính liên tục “mẫu” của cụm thường là “trọng tâm” hay
8
Generated by Foxit PDF Creator © Foxit Software
“centroid” của cụm, ví dụ, là trung bình của tất cả các điểm trong cụm. Tuy nhiên một
vài trường hợp “trọng tâm” là không hợp lý như là khi dữ liệu có những thuộc tính
“xác thực” vì vậy mẫu thường là “medoid” là điểm đại diện nhất cho cụm. Ví dụ trong
nhiều kiểu dữ liệu mẫu thường là điểm trung tâm nhất của cụm, ta gọi những loại cụm
này là “cụm dựa trên trung tâm” hay “center-based clusters”. Những cụm dạng này
thường có hình cầu.
Dựa trên đồ thị (Graph-Based)[12] Nếu dữ liệu được biểu diễn như một đồ thị
nơi mà những nút là những đối tượng và những liên kết biểu diễn những kết nối giữa
những đối tượng do vậy một cụm có thể được định nghĩa là một thành phần được kết
nối; ví dụ một nhóm những đối tượng mà được kết nối tới những đối tượng khác trong
nhóm nhưng không được kết nối tới những đối tượng khác nằm ngoài nhóm.
Dựa trên mật độ (Desity-Based)[12] Một cụm là một miền đối tượng có mật độ
cao được bao quanh bởi miền đối tượng có mật độ thấp.
Chia sẻ thuộc tính (Shared-Property)[12] Cụm là một tập những đối tượng mà
chia sẻ một vài thuộc tính chung những thuộc tính chung này được dẫn xuất từ toàn bộ
tập các điểm.
1.2. Phân cụm cho dữ liệu gene microarray
1.2.1.Giới thiệu công nghệ DNA microarray
Khái niệm công nghệ DNA microaray
Công nghệ microarray là công nghệ “highthroughput” (“highthroughput là những
thí nghiệm sử dụng những phương pháp nghiên cứu về bộ di truyền, protein, quá trình
sao chép, chuyển hóa) để xác định những genes một loại tế bào hay 1 cơ quan. Việc đo
mức độ mô tả của gene trong những điều kiện biến đổi cung cấp cho các nhà sinh học
hiểu rõ hơn về chức năng của gene và có những ứng dụng rộng rãi trong lĩnh vực khoa
học.
Ví dụ, microarrays cho phép so sánh mô tả gene giữa những tế bào ung thư và tế
bào thường.
Công nghệ này còn được biết với các tên như: DNA microarrays, DNA arrays,
DNA chips, và gene chips.
1.2.2.Thí nghiệm microarray
Về cơ bản, thí nghiệm với microarray gồm 4 bước:
Chuẩn bị microarray.
Chuẩn bị mẫu, tiến hành lai.
Phân tích thông tin mức thấp
Phân tích dữ liệu mức cao.
Bước 1: Chuẩn bị microarray
Có rất nhiều phương pháp để sản xuất microarray khác nhau. Thông thường
những microarrays được chuẩn bị trên một tấm nền bằng kính, ni lông hoặc thạch anh.
9
Generated by Foxit PDF Creator © Foxit Software
Bước quan trọng trong tiến trình này đó là việc lựa chọn những chuỗi DNA để đặt lên
tấm nền kình và kỹ thuật trộn những chuỗi DNA này lên trên tấm nền đã chuẩn bị tại
những “chấm” còn được gọi là những “spot”, mỗi chấm đại diện cho một gene nhất
định. Đường kính của mỗi spot khoảng 80 µm đến 150 µm và mỗi mảng có khoảng
trên 80 000 spot.[13]
Trong kỹ thuật DNA array, người ta cố định các axit nucleic có trình tự xác định
(mẫu dò) trên giá thể (mảng) thích hợp theo thứ tự. Kích thước vật lý các chiều của
mỗi mảng này là khoảng 1 inch thậm chí nhỏ hơn. Axit nucleic cần nghiên cứu (đích)
được đánh dấu sau đó lai với mẫu dò trên mảng. Ở những điều kiện lý tưởng, các axit
nucleic có trình tự bổ sung bắt cặp chính xác với nhau. Hơn nữa dưới các điều kiện
này, cường độ phát hiện tín hiệu tỷ lệ trực tiếp với lượng mẫu dò nên có thể định lượng
các loại axit nucleic trong mẫu ban đầu [10]. Những spot này được ấn định lên trên
microarray bằng robot với các kỹ thuật in “quang hoạt” hoặc in “kim”.[10]
Bước 2: Chuẩn bị mẫu, tiến hành lai
Trong khóa luận này ta sẽ nghiên cứu thí nghiệm microarray sử dụng mảng chứa
mẫu dò cDNA.
Hầu hết những thí nghiệm microarray sử dụng mảng loại này đều so sánh mô tả
gene từ 2 mẫu, một mẫu gọi là mẫu “ đích” (hay mẫu thí nghiệm), mẫu kia gọi là mẫu
“điều kiển”.
Những nhà nghiên cứu có cơ sở dữ liệu của trên 40,000 gene được sử dụng để
làm mẫu dò đặt lên trên các microarrays.
Khi một gene được kích hoạt, máy tế bào bắt đầu sao một số đoạn nhất định của
gene đó. Sản phẩm kết quả gọi là RNA thông tin mà là thành phần chính cho việc tạo
ra protein. RNA thông tin này được tạo ra bởi tế bào bổ xung vì vậy nó sẽ được lai với
phần gốc của DNA mà nó được sao từ DNA này.
Để xác định gene nào “được bật” gene nào “bị tắt” trong một tế bào cho trước,
đầu tiên, người nghiên cứu phải thu thập những phân tử RNA thông tin có mặt trong tế
bào đó. Sau đó người nghiên cứu sẽ gán nhãn chó mỗi RNA thông tin bằng thuốc
nhuộm huỳnh quang thường sử dụng thuốc nhuộm huỳnh quang Cy3 và Cy5. RNA
thông tin mà có mặt trong tế bào này , sau đó sẽ được lai với những DNA bổ xung của
nó trên microarray. [15] Xem hình 2. Sau khi thực hiện việc lai hóa một số mRNA có
thể được bao trong một spot khi nó tạo thành những cặp cơ sở (base pair) với cDNA
trên microarray. Một số không được bao trong spot.
10
Generated by Foxit PDF Creator © Foxit Software
Low-level analysis
Cy5
Cy3
radio
High-level analysis
microarray gene data
Hình 1: Thí nghiệm microarray
Bước 3: Phân tích dữ liệu mức thấp-Quá trình lượng hóa hình ảnh
Sau quá trình lai hoá, nhà nghiên cứu gạt đi những mRNA không được bao trong
một spot phải sử dụng một máy quét đặc biệt để dò tìm những mRNA nào được bao
trong một spot bằng cách đo tỉ lệ huỳnh quang trên microarray. Điều này thực hiện
được là do thuốc nhuộm huỳnh quang được gán cho mỗi mRNA giúp cho số lượng
mẫu được bao trong một spot được đo bởi mức độ huỳnh quang phát ra khi được kích
thích bởi máy laser.[15]
Kết quả của thí nghiệm microarray được biểu diễn như một vector, mỗi thành
phần là một spot. Giá trị của 1 thành phần của vector là tỉ lệ của “độ dư” RNA thông
tin được đánh giá trong 2 mẫu. Với mỗi spot cho trước, nếu RNA thông tin từ mẫu mà
được gán nhãn sử dụng Cy3 có “độ dư” thì spot đó sẽ chuyển thành mầu xanh. Nếu
RNA thông tin từ mẫu mà được gán nhãn sử dụng Cy5 có “độ dư” thì spot đó sẽ
chuyển thành mầu đỏ. Nếu cả hai mẫu có “độ dư” bằng nhau thì spot sẽ chuyển thành
màu vàng. Nếu không có mẫu nào biểu hiện thì spot sẽ có màu đen. Dữ liệu hình ảnh
thu được này được gọi là dữ liệu thô. Để đạt được thông tin về mức độ mô tả gene thì
dữ liệu hình ảnh này cần phải được phân tích bao gồm: xác định mỗi spot trên mảng
sau đó đo và so sánh cường độ của mỗi spot với giá mang. Đây chính là quá trình
lượng hóa hình ảnh. Sau quá trình lượng hóa hình ảnh ta thu được dữ liệu mô tả gene.
11
Generated by Foxit PDF Creator © Foxit Software
Kết quả của quá trình lượng hóa hình ảnh ta thu được tập dữ liệu được gọi là dữ liệu
gene microarray
Hình 2: Minh họa việc tính dữ liệu mô tả gene.
Đã có rất nhiều phần mềm chuyên dụng được sử dụng cho mục đích này như:
ScanAlyze (Eisen 1999), GenePix (Axon 1999), ScanArray Express (GSI 1999).[7]
Bước 4: Phân tích dữ liệu mức cao
Phân tích các tập dữ gene microarray lớn là một lĩnh vực mới mà cũng có một
vài thách thức hay khóa khăn riêng của nó. Những cách tiếp cận khai phá dữ liệu
thông thường được chia làm 2 loại: “supervised” và “unsupervised”.
Phân tích có giám sát (supervised)
Phân tích “supervised” sử dụng những thông tin thêm vào. Phân tích
“supervised” bao gồm việc chọn từ toàn bộ tập dữ liệu một tập ‘thử’ và một tập ‘kiểm
tra’ và cũng bao gồm chỉ thị của những bộ phân loại, những chỉ thị này sẽ gán những
mô tả gene cho những lớp đã được định nghĩa trước. Khi bộ phân loại đã thử trên tập
‘thử’ và đã kiểm tra trên tập ‘kiểm tra’, sau đó nó có thể được áp dụng cho dữ liệu
chưa được phân loại.[13]
Phân tích không có giám sát (unsupervised)
Việc phân tích theo cách này là phù hợp khi không có tri thức trước về dữ liệu.
Tiếp cận duy nhất có thể là để nghiên cứu sự tương đồng giữa những mẫu hay những
thí nghiệm khác nhau. Quá trình phân tích này được gọi là học không giám sát-
unsupervised learning vì không có câu trả lời mong muốn được biết cho bất kì gene
hay thí nghiệm nào. Quá trình phân tích chỉ nhóm những thực thể giống nhau cùng
nhau. Việc phân tích có thể được làm trên gene, các điểm thời gian, các mẫu, trong các
chuỗi thời gian. Giải thuật phân cụm sẽ xem tất cả dữ liệu đầu vào nhưg là tập n số hay
vector n-chiều.[14]
Các phương pháp phân cụm Hierarchical, K-means, SOM là ví dụ điển hình của
việc phân tích dữ liệu gene microarray sử dụng cách tiếp cận phân cụm
“unsupervised”.
Vậy phân cụm cho dữ liệu gene microarray chính là phân tích “unsupervised”.
Việc phân cụm này sẽ nhóm những gene hay những thí nghiệm có mô tả tương đồng
cùng nhau.
12
Generated by Foxit PDF Creator © Foxit Software
1.3. Ứng dụng bài toán phân cụm cho dữ liệu gene microarray
Bài toán phân cụm cho dữ liệu gene microarray có rất nhiều ứng dụng trong
nhiều lĩnh vực của đời sống như: y học, sinh học, nông nghiệp, môi trường….
Việc phân cụm cho dữ liệu gene microarray giúp cho việc nhóm những gene
dưới những điều kiện hay ở những mẫu khác nhau mà có “mô tả tương đồng” vào
thành một nhóm. Điều này có ứng dụng quan trong trong y học đó là phân biệt các tế
bào với nhau (tế bào bệnh với tế bào thường). Một ví dụ điển hình cho ứng dụng này là
việc phân biệt những loại ung thư vú. Sử dụng việc phân tích dữ liệu microarray gene
các nhà nghiên cứu có thể phân biệt được khối ung thư vú gây ra tính di truyền của
bệnh và những khối ung thư vú mà không gây ra tính di truyền của bệnh.
Ngoài ra, Với việc phân cụm cho dữ liệu microarray gene còn giúp các nhà
nghiên cứu phát hiện ra những gene mới là những gene mà thường không thuộc vào
cụm nào trong số các gene thí nghiệm đây là một phát hiện rất quan trọng trong sinh
học.
13
Generated by Foxit PDF Creator © Foxit Software
Chương 2: Một số phương pháp phân cụm cho
dữ liệu gene microarray
Chương này trình bày về các phương pháp hay các giải thuật phân cụm sử dụng
các tiếp cận phân cụm không có giám sát (unsupervised). Các phương pháp phân cụm
sẽ được trình bày đó là: Hierarchical, K-means, SOM, PAM và một phương pháp phân
cụm mới dựa trên khoảng cách “intra-cluster”. Trước tiên ta sẽ đi được giới thiệu về
cơ sở toán học để nghiên cứu các phương pháp phân cụm này.
2.1. Cơ sở toán học
2.1.1.Biểu diễn dữ liệu gene microarraay
Dữ liệu mô tả gene thường được biểu diễn dưới dạng số thập phân.
Giá trị của dữ liệu mô tả gene có thể được biểu diễn thông qua logarit cơ số 2 của
giá trị đó
Lợi thế: Những mô tả trong logarit –log là dễ làm việc hơn những mô tả chính
quy.
2.1.2.Vector mô tả
Mô tả của 1 gene có thể được biểu diễn thông qua hàng loạt những thí nghiệm
khác nhau. Dãy những giá trị này được biến đến là vector mô tả gene.[2]
Hình 3: Ví dụ về vector mô tả gene trong log
2.1.3.Ma trận mô tả gene
Do chúng ta có thể nghiên cứu hàng nghìn gene trong hàng loạt những thí
nghiệm ở những điều kiện khác nhau. Kết quả là dữ liệu gene microarray tạo ra có thể
được biểu diễn như ma trận mô tả gene.[2]
14
Generated by Foxit PDF Creator © Foxit Software
Hình 4: Ví dụ về ma trận mô tả gene
2.1.4.Khoảng cách hay sự tương đồng
Khi ta thực hiện phân cụm cho những thực thể biểu diễn trong tập dữ liệu gene
microarray tức là nhóm những thực thể mà tương đồng lại với nhau vì vậy chúng ta
cần đo tính tương đồng hay ngược lại là đo khoảng cách của các thực thể đó. Tức là ta
sẽ cần đo khoảng cách của các vector mô tả của các thực thể đó.
Khoảng cách
Tính tương đồng
Việc phân cụm sẽ phụ thuộc vào ma trận khoảng cách được lựa chọn
Ma trận khoảng cách (Distance Matrix): Một số phương pháp đo khoảng
cách giữa 2 vector mô tả gene.
Khoảng cách dựa trên tương quan Pearson[8]
Ma trận tương đồng được sử dụng phổ biến nhất là dựa trên tương quan Pearson.
Tương quan Pearson giữa hai tập dữ liệu X={x1, x2,…, xn} và Y={y1, y2,…, yn} được
định nghĩa là:
Với x tb là giá trung bình của những giá trị x, và σx là độ lệch chuẩn của những
giá trị này. Công thức này được sử dụng nếu bạn lựa chọn tùy trọn
Correlation(Centered) trong Cluster. Nếu bạn lựa chọn tùy trọn
Correlation(Uncentered) thì công thức sau được sử dụng:
15
Generated by Foxit PDF Creator © Foxit Software
Trong trường hợp này ta giả định mean của các x là 0.
Cluster còn cung cấp 2 ma trận tương đồng là trị tuyệt đối của 2 hàm tương quan
trong 2 công thức trên là Absolute Correlation(Centered) và Absolute
Correlation(Uncentered) 2 ma trận này xem 2 đối tượng có những mẫu mô tả đối lập
nhau là giống nhau; Hệ số tương quan Pearson xem những gene đối lập nhau là rất
cách xa nhau.
Đo khoảng cách Non-parametric[8]
Spearman rank correlation và Kendall’s τ là 2 ma trận mà dựa trên hệ số tương
quan của Pearson.
Spearman rank correlation áp dụng trên 2 vector dữ liệu mà là hạng của những
giá trị dữ liệu trong 2 vector này.
Ví dụ: cho 2 vector:
x={2.3, 6.7. 4.5, 20.8} và y={2.1, 5.9, 4.4, 4.2} ta tính được r=0.2344
ta sẽ tính trên tập các hạng của 2 vector này là:
x={1, 3,2, 4} và y={1,4,3,2} thì ta tính được rspearman=0.4.
Tương quan Spearman được sử dụng như một thống kê kiểm tra cho sự độc lập
giữa x và y.
Kendall’s τ thì sử dụng quan hệ về thứ tự của x và y để tính sự tương quan. Nó
xem xét 2 vector dữ liệu (2 gene) như cặp những điểm (xi, yi) và (xj, yj) và chúng ta
gọi một cặp là phù hợp nếu:
xi <
xi >
xj và yi < yj hay
xj và yi > yj
và là không phù hợp nếu:
xi <xj và yi >yj hay
xi > xj và yi < yj
Ta có thể biểu diễn ví dụ bởi bảng:
16
Generated by Foxit PDF Creator © Foxit Software
Từ bảng ta tính được số cặp phù hợp nc=4 và số cặp không phù hợp nd=2.
Từ đó ta tính Kendall’s τ theo công thức: τ=2(nc- nd ) / n(n-1) trong trường hợp
này τ=0.33. Chúng ta cũng có thể sử dụng tương quan Kendall’s để kiểm tra sự độc
lập giữa x và y.
Đo khoảng cách dựa trên khoảng cách Euclidean[8]
Theo công thức:
Khoảng cách City-block hay Manhattan[8]
Là giống với khoảng cách Euclidean khoảng cách d được tính theo công thức:
Chú ý:
Với những dữ liệu x, y có giá trị missing value thì ta bỏ qua những giá trị này và
chỉ tính hệ sô tương quan trên những giá trị có nghĩa.
Tính toán ma trận khoảng cách là bước đầu tiên trong phân cụm hierachical với
những ma trận tương quan thì khoảng cách d=1.0-corelation(hệ số tương quan). Việc
tính toán này sẽ tốn thời gian ngoại trừ phân cụm single-linkage hierarchical vì có giải
thuật với độ phức tạp tuyến tính.
2.2. Một số phương pháp phân cụm
Khóa luận này sẽ giới thiệu 4 phương pháp phân cụm truyền thống là: phân cụm
hierarchical, phân cụm K-means, SOM, và PAM
2.2.1.Phân cụm Hierarchical
Là phương pháp phân cụm “ tích tụ” (agglomerative) nối những gene giống nhau
vào cùng một nhóm. Tiến trình lặp tiếp tục với việc nối những nhóm kết quả dựa trên
tính tương đồng của chúng cho đến khi các nhóm được được kết nối trong một cây cấu
trúc.[2]
Giải thuật:
o
Bước 1: Tính khoảng cách giữa các gene tạo thành ma trận khoảng cách
(distance matrix). Tìm những khoảng cách nhỏ nhất. Nếu có một vài cặp có tính
tương đồng như nhau, sử dụng quy tắc được xác định trước để quyết định lựa
chọn cái nào.
17
Generated by Foxit PDF Creator © Foxit Software
o
Bước 2: Hợp nhất 2 cụm được lựa chọn để tạo ra những cụm mới mà ban
đầu chứa ít nhất 2 đối tượng. Tính toán khoảng cách của tất cả những cụm mới
và những cụm khác.
o
o
o
Bước 3: Lặp lại bước 1 và 2 cho đến khi chỉ còn một cụm.
Bước 4: Vẽ một cây trình diễn kết quả.
Bước 5: Trong khi khởi tạo cấu trúc, ta phải quyết định những cụm nào
lên được nối. Khoảng cách hay tính tương đồng giữa những cụm phải được
tính. Những quy tắc mà quản lý việc tính toán này là những phương pháp liên
kết-Linkage Methods.
Có 4 phương pháp liên kết phổ biến là:[8]
Centroid Linkage
Một vector được gán cho mỗi đối tượng giả (hay mỗi cụm-bao gồm một hay
nhiều đối tượng thật ) vector này sẽ được sử dụng để tính toán khoảng cách của đối
tượng giả này với tất cả những đối tượng còn lại hoặc đối tượng giả sử dụng ma trận
tương đồng được sử dụng để tính toán ma trận tương đồng ban đầu. Vector này là
trung bình của tất cả những vector của những đối tượng thực sự (đối tượng ở đây là
gene hay arrays) chứa trong đối tượng giả. Trong phương pháp này việc tính trung
bình của những vector bên trong sẽ bỏ qua những giá trị missing values, vì vậy vector
của đối tượng giả chỉ chứa missing value nêu tất cả những đối tượng trong nó chứa giá
trị missing value ở cột hay hàng tương ứng.
Single Linkage: Khoảng cách giữa 2 đối tượng(cụm) x, y là khoảng cách nhỏ
nhất giữa những phần tử của x với những phần tử của y.
Ví dụ: xét 2 tập đối tượng x bao gồm các phần tử xi i=1-n, y bao gồm các phần tử
ỵ j=1-m thì:
Dxy=min(d(xi,yj)) for all i = 1 to n and j = 1 to m.
Average Linkage: Khoảng cách giữa 2 đối tượng x, y là khoảng cách trung bình
giữa những phần tử của x với những phần tử của y.
DAB = 1/(nm) ∑∑( d(xi, yi) ) for all i = 1 to n and j = 1 to m.
Complete Linkage: Khoảng cách giữa 2 đối tượng x, y là khoảng cách lớn nhất
giữa những phần tử của x với những phần tử của y.
Ví dụ: xét 2 tập đối tượng x bao gồm các phần tử xi i=1-n, y bao gồm các phần tử
ỵ j=1-m thì:
Dxy=max(d(xi,yj)) for all i = 1 to n and j = 1 to m.
18
Generated by Foxit PDF Creator © Foxit Software
Hình 5: Mô tả những phương pháp linkage khác nhau
Kết luận:
Việc lựa chọn những phương pháp linkage nào để phân cụm có ảnh hưởng lớn
đến độ phức tạp và hiệu năng của việc phân cụm. Single hay complete linkage yêu cầu
ít tính toán hơn. Tuy nhiên single linkage thường tạo ra những cụm trải dài trông
không đẹp mắt. Centroid và average linkage tạo ra những kết quả mà sự phù hợp về
những cụm được tạo ra và biểu diễn cấu trúc của dữ liệu phù hợp hơn. Tuy nhiên
những phương pháp này lại yêu cầu tính toán phức tạp hơn. Dựa trên kinh nghiệm
trước nay, thì average và complete linkage là những phương pháp linkage được ưa
chuộng hơn cả cho việc phân tích dữ liệu gene microarray.
Ưu nhược điểm của giải thuật phân cụm Hierarchical
o Kết quả phân cụm trực quan do được biểu diễn dưới dạng cây.
o Không cần xác định tham số đầu vào (ví dụ số cụm như trong K-means)
Nhược điểm
o Không hiệu quả với tập dữ liệu lớn
o Không làm việc tốt với tập dữ liệu có dữ liệu khuyết.
o Nhậy cảm với những “điểm kỳ dị” hay “outlier”.
2.2.2.K-Means Clustering (KMC)
Giải thuật này là giải thuật đươc sử dụng rộng rãi bởi vì việc cài đặt của giải
thuật này khá đơn giản. Giải thuật này yêu cầu đầu vào là số cụm k cận được định
trước bởi người dùng.[2]
Giải thuật :
o Bước 1: Xác định trước số cụm k- number of clusters(k)
o Bước 2: Gán ngẫu nhiên các gene tới những cụm này.
o Bước 3: Tính toán mean or median của những cụm khởi tạo.
o Bước 4: Lựa chọn một gene và di chuyển nó tới cụm mà giá trị của gene gần
với mean của cụm đó nhất.
19
Generated by Foxit PDF Creator © Foxit Software
o Bước 5: Nếu gene được di chuyển sang cụm mới, tính toán lại mean cho các
cụm.
o Bước 6: Lặp lại bước 4,5 cho tới khi các gene không thể di chuyển được nữa
hay số bước lặp được xác định trước bởi người sử dụng(number of runs) đã
hết.
Chú ý k-means
o k-means là tính mean của các đối tượng trong một cụm. Mean là trung bình
trên tất cả các đối tượng trên một cụm cho mỗi chiều phân biệt.
o Có một đề nghị rằng: Khi ta lựa chọn k-means ta lên sử dụng khoảng cách
Euclidean. Là do sử dụng khoảng cách Euclidean sẽ có độ phức tạp tính
toán thấp giúp cho K-means có thể áp dụng tốt cho những tập dữ liệu lớn.
Ưu nhược điểm của giải thuật phân cụm K-means
o Giải thuật phân cụm K-means là một trong những giải thuật đơn giản
nhất và nhanh nhất.
o Làm việc tốt với cả tập dữ liệu lớn.
Nhược điểm
o Kết quả của giải thuật phân cụm k-means có thể thay đổi theo các lần
chạy bởi vì việc khởi tạo những cụm ban đầu là ngẫu nhiên. Kết quả là
những người nghiên cứu phải đánh giá chất lượng của những kiểu cụm
đạt được. Vì vậy mà phương pháp này thường kết thúc ở giải pháp tối ưu
“cục bộ”.
o Số cụm k phải được xác định trước bởi người dùng.
o Nhậy cảm với những “điểm kỳ dị” (“outliers”) (outliers là những điểm
mà không phụ thuộc vào cụm nào) những outlier này có thể bóp méo
centroid của cụm và phá hủy việc phân cụm.
o Giải thuật làm việc không hiệu quả với những tập dữ liệu có “dữ liệu
khuyết” hay “missing value”.
2.2.3.Self-Organizing Maps(SOMs)
Giải thuật này phân các đối tượng thành k cụm (k do người dùng chọn) mỗi cụm
(gồm nhiều gene) được xem như các node được sắp xếp trong lưới 2 chiều. Mỗi node
tương ứng với một cụm[1]
Việc làm này cho phép thể hiện sự giống nhau giữa các cụm.
Giải thuật:
Khởi tạo các nodes ở những vị trí ngẫu nhiên trong lưới 2 chiều rồi lặp lại các
bước sau:
o Chọn ngẫu nhiên một điểm dữ liệu ( gene) ta gọi điểm dữ liệu này là x.
20
Generated by Foxit PDF Creator © Foxit Software
o Di chuyển những nodes về phía x, những nodes mà gần x nhất
o Giảm số lần di chuyển qua số lần lặp(số lần lặp thường là một tham số
mà người dùng xác định khi sử dụng ứng dụng của giải thuật).
Ưu nhược điểm của giải thuật phân cụm SOM
o Ổn định với cả tập dữ liệu lớn
Nhược điểm:
o Thời gian chay chậm hơn K-means
o Phải xác định trước 2 tham số của “lưới”.
o Không làm việc tốt với tập dữ liệu có dữ liệu khuyết (missing data)
2.2.4.Principal Components Analysis-(PCA)
Được so sánh với giải thuật kmeans, PAM có những đặc tính sau:
Nó hoạt động dựa trên ma trận không tương đồng của tập dữ liệu cho trước.
Nó tối giản tổng khoảng cách không tương đồng thay vì tổng khoảng cách
Euclidean.
Nó cung cấp một hiển thị đồ họa, cho phép người dùng chọn số những cụm tối
ưu.
Giải thuật PAM đầu tiên tính k đối tượng đại diện, được gọi là các medoids. Một
medoid được định nghĩa là đối tượng của một cụm, mà tính không tương đồng trung
bình của nó tới các đối tượng trong cụm là nhỏ nhất. Sau khi tìm được tập các
medoids, mỗi đối tượng của tập dữ liệu được gán tới medoid gần nhất. Ví dụ, đối
tượng i được đặt vào cụm v khi medoid mi gần hơn bất kỳ medoid mw khác: d(i, mi)<=
d(i, mw) với w=1,…,k.
Những đối tượng đại diện cần làm nhỏ nhất “hàm mục tiêu”, hàm đối tượng là
tổng khoảng cách không tương đồng của tất cả những đối tượng tới medoid gần nhất
của chúng.
Giải thuật:
Bước khởi tạo: Bước này lựa chọn tuần tự những đối tượng đại diện, được dùng
như những medoids ban đầu.
Bước tráo đổi: Nếu “hàm mục tiêu” có thể giảm bằng việc tráo đổi một đối tượng
được lựa chọn với một đối tượng không được lựa chọn, thì việc tráo đổi được thực
hiện. Việc làm này tiếp tục cho tới khi “hàm mục tiêu” không thể giảm được nữa.
Ưu nhược điểm của thuật phân cụm PAM
Ưu điểm :
o PAM là hiệu quả cho việc phân tích những tập dữ liệu có nhiều biến đổi
hay dữ liệu có nhiều “điểm kỳ dị”.
Nhược điểm :
21
Generated by Foxit PDF Creator © Foxit Software
o Không làm việc tốt với tập dữ liệu có dữ liệu khuyết (missing data).
o Không hiệu quả với tập dữ liệu lớn.
2.3. Phương pháp phân cụm intra-cluster
Qua quá trình tìm hiểu các phương pháp để khắc phục một số nhược điểm của 4
phương pháp phân cụm trên tôi đã tìm thấy một phương pháp đó là phương pháp phân
cụm dựa trên khoảng cách “intra-cluster” và tôi cũng đã quyết định tìm hiểu sâu hơn
để cài đặt phương pháp này trong ứng dụng phân cụm của mình.[1]
Phương pháp này xét dữ liệu mô tả gene được biểu diễn dưới dạng ma trận gồm
n hàng (tương ứng với các gene) và m cột (tương ứng với các thí nghiệm). Trong đó sử
dụng các ký hiệu:
Gi biểu diễn gene thứ i với i=1,…,n.
Ej biểu diễn thí nghiệm thứ j với j=1,…,m.
Xij biểu diễn giá trị mô tả gene của gene thứ i ở thí nghiệm j.
Tóm tắt giải thuật:
o Tính toán “giá trị ngưỡng”-“threshold” cho các cột (hay các thí nghiệm).
o Xem mỗi gene là một “trung tâm cụm”-“cluster-center”, “những thành viên
cụm”-“cluster-members” sẽ được tính dựa trên một giá trị mà ta đặt là
“count”(giá trị cao này sẽ được định nghĩa sau”.
o Cuối cùng, những cụm tốt nhất được xác định dựa trên sự giống nhau giữa
“những thành viên cụm” của một cụm.
Sau đây là ta sẽ đi chi tiết vào các bước trong giải thuật:
Tính giá trị “ngưỡng”-“threshold”:
o Đầu tiên tính giá trị “ngưỡng” của các cột trong ma trận dữ liệu,
o Tìm giá trị lớn nhất và nhỏ nhất của mỗi cột sau đó tính “độ lệch” của 2
giá trị này.
o Giá trị “ngưỡng” được tính theo công thức sau:
o Thj=0.05*{(Xij)max-(Xij)min} với i=1,….n (n là số gene hay số hàng trong
ma trận dữ liệu) và j=1,…m (m là số “mẫu”hay “thí nghiệm” hay số cột
trong ma trận dữ liệu).
Xác định “những thành viên cụm”
Tại mỗi thời điểm ta xem mỗi gene là một “trung tâm cụm”(“cluster-
centre”) và xét xem trong số n-1 gene còn lại gene nào thuộc vào cụm của gene
đang xét này. Ví dụ, xét gene số 1, đầu tiên chúng ta đưa ra độ lệnh vệ giá trị
của thí nghiệm đầu tiên ứng với G1 và G2, và xem xét nó có lằm trong giá trị
“ngưỡng” của thí nghiệm 1 hay không, tức là X11 –X12 <Th1 hay không. Nếu
điều kiện đó thỏa mãn, thì E1 được cho là một “thí nghiệm tương đồng” với G1
và G2. Việc làm trên được tiếp tục cho m-1 thí nghiệm còn lại. Nếu số “thí
nghiệm tương đồng” là lớn hơn 0.75 thì G2 được coi là thành viên của cụm có
22
Generated by Foxit PDF Creator © Foxit Software
G1 là “trung tâm cụm”. Tiếp theo, chúng ta tiếp tục với những gene tiếp theo,
trong trường hợp ví dụ này là G1 và G3.
Sau khi hoàn thành việc so sánh giữa G1 và tất cả những gene khác. Chúng
ta lập lại toàn bộ tiến trình trên cho n-1 gene còn lại mà lần lượt coi các gene là
“trung tâm cụm”.
Những cụm với số lượng gene lớn nhất được chọn và ta tiếp tục thực hiện
bước tiếp theo của giải thuật.
Tính toán sự giống nhau giữa các thành viên của cụm:
Với mỗi cụm, tính toán khoảng cách Euclidean giữa 2 thành viên bất kỳ của
cụm:
(X Xbj )2
D=
với j=1,…,m; a và b là 2 thành viên của cụm. Việc này
aj
j
được thực hiện trên tất cả những cặp thành viên có thể của cụm đó.
Tiếp theo, những khoảng cách này được cộng vào để đưa ra tổng khoảng
cách của cụm đó:
Tổng khoảng cách= D với k là số thành viên của cụm.
k
Cuối cùng chúng ta tính “trung bình” của “tổng khoảng cách” của cụm đó
trên tổng số cặp gene mà chúng ta đã xét. “Trung bình” này được gọi là “ khoảng
cách intra-cluster trung bình” của một cụm.
Các cụm sẽ được sắp xếp theo thứ tự tăng dần của “khoảng cách intra-
cluster trung bình”. Những cụm tốt nhất được chọn là những cụm mà có giá trị
khoảng cách này nhỏ nhất.
Ưu nhược điểm của giải thuật phân cụm dựa trên khoảng cách “intra-
cluster”
Ưu điểm:
o Đơn giản để cài đặt.
o Không phụ thuộc vào tham số đầu vào.
o Giải thuật có khả năng đạt được tối ưu toàn cục cao.
Nhược điểm:
o Khó khăn khi những thành viên của cụm biến đổi và chọn những cụm nào là tốt
nhất.
23
Generated by Foxit PDF Creator © Foxit Software
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
Hiện tại có rất nhiều phần mềm có chức năng phân cụm cho dữ liệu gene, một ví
dụ điển hình cho một phần mềm có chức năng phân cụm cho dữ liệu gene mà sử dụng
4 phương pháp phân cụm: Hierarchical, Kmeans, SOM, PAM đó là “Cluster 3.0”i
Như trong chương trước tôi đã trình bày về các phương pháp phân cụm, giải
thuật của từng phương pháp và một số ưu nhược điểm của các phương pháp.
Dựa vào việc nghiên cứu trong báo cáo này cũng như theo hướng phát triển của
phần mềm phân cụm “Cluster 3.0” tôi đã xây dựng một chương trình có chức năng
phân cụm cho dữ liệu gene microarray là “Gene Cluster” mà sẽ khắc phục một số
nhược điểm của Cluster 3.0 ví dụ:
Vấn đề chức năng: “Gene Cluster” có thêm chức năng “xử lý dữ liệu khuyết” mà
sẽ giúp cho kết quả phân cụm được chính xác hơn.
Ngoài ra, ứng dụng của “Gene Cluster” của tôi cũng cài đặt một phương pháp
phân cụm mới dựa trên khoảng cách “intra-cluster” mà khắc phục được một số nhược
điểm quan trọng của 4 phương pháp đã trình bày ở trên như: Cho kết quả tốt với cả tập
dữ liệu có dữ liệu khuyết. Không cần phải xác định trước tham số đầu vào.
3.1. Phương pháp phân cụm
Căn cứ vào những nghiên cứu trên tôi đã quyết định chọn phương pháp phân
cụm k-means và “intra-cluster” để xây dựng phần mềm.
3.1.1. Lý do chọn K-means
Lý do quan trọng nhất khi chọn giải thuật k-means đó là tính đơn giản của giải
thuật vì vậy nó dễ dàng để cài đặt hơn.
Ngoài ra giải thuật K-means cài hiệu quả với tập dữ liệu lớn.
Thêm vào đó tôi cũng đã tìm hiểu một số phương pháp để khắc phục một số
nhược điểm của phương pháp phân cụm k-means (tôi sẽ giới thiệu phần này ở phần
tiếp theo)
3.1.2. Lý do chọn “intra-cluster”
Như đã trình bày một số phương pháp phân cụm ở trên có một vài nhược điểm như
phụ thuộc vào tham số đầu vào mà thường rất khó để xác định bởi người dùng, không
làm việc hiệu quả với tập dữ liệu có dữ liệu “trội”, hay có lúc không đạt được tối ưu
toàn cục…. Vì vậy tôi quyết định chọ một phương pháp phân cụm mới dựa vào
khoảng cách “intra-cluster” mà giải quyết được một số lớn các nhược điểm của các
giải thuật phân cụm đã nghiên cứu ngoài ra nó còn đơn giản để cài đặt.[6]
i Cluster 3.0 là phần mềm có chức năng phân cụm cho dữ liệu microarray gene. Phận mềm này đầu tiên được
phát triển bởi Michael Eisen, 1998. Phần mềm này cài đặt sử dụng 4 phương pháp phân cụm: Hierarchical, K-
means, SOM và PAM.[8]
24
Generated by Foxit PDF Creator © Foxit Software
3.2. Một số phương pháp khắc phục nhược điểm của k-means
3.2.1.Lọc dữ liệu
Lọc dữ liệu giúp cho việc loại bỏ những “điểm kỳ dị” trong tập dữ liệu ban đầu
để cho ra một kết quả phân cụm đúng đắn hơn. Việc lọc dữ liệu được thực hiện tùy
theo mục đích hay kết quả phân cụm mong muốn dựa theo một số tiêu chí như sau:[8]
% Present >=X. Điều kiện này bỏ đi những gene mà có những giá trị missing
values lớn hơn (100-X) phần trăm của những cột.
SD (Gene Vector) >=X. Điều kiện này bỏ đi những gene mà có độ lệch chuẩn về
giá trị nhỏ hơn X.
At least X observations with abs(Val) >=Y. Điều kiện này bỏ đi những gene
không có ít nhất X giá trị với giá trị tuyệt đối lớn hơn Y.
MaxVal-MinVal >=X.
3.2.2.K-medians
Để khắc phục việc dữ liệu có những đối tượng có “phần trội” thì thay vì tính
“mean” trong giải thuật k-means ta sẽ tính median cho mỗi cụm. Median là median
cho tất cả những đối tượng trên mỗi chiều.
3.2.3.Xữ lý dữ liệu khuyết:
Những giá trị khuyết xảy ra vì một vài lý do khác nhau, bao gồm: độ phân giải
không đủ, hỏng hình ảnh, hay đơn giản là bẩn hoặc những vết sước trên mặt kính.
Chúng cũng có thể là do lỗi hệ thống của những phương pháp robot tạo ra chúng.
Trong khóa luận này tôi sẽ trình bày 2 phương pháp xử lý dữ liệu khuyết phổ
biến
K người hàng xóm gần nhất (K nearest neighbor-KNN)
Trung bình hàng (Row average)
K người hàng xóm gần nhất (K nearest neighbor-KNN)
Giải thuật:
o
Phương pháp dựa trên KNN chọn những gene với mô tả giống với gene
mà ta quan tâm để xử lý giá trị khuyết. Nếu ta xét gene A có 1 giá trị khuyết
trong thí nghiệm 1 phương pháp này sẽ tìm k gene mà có biểu diễn giá trị trong
thí nghiệm 1 với mô tả giống với gene A nhất trong những thí nghiệm từ 2 đến
N với N là tổng số thí nghiệm. Giá trị trung bình từ k gene gần nhất trong thí
nghiệm 1 sau đó được sử dụng để tính giá trị khuyết cho gene A ở thí nghiệm 1.
o
Trong phương pháp này công thức để tính khoảng cách giữa các gene sử
dụng khoảng cách Euclidean sẽ mang lại tính chính xác nhất. Có điều cần lưu ý
việc sử dụng khoảng cách Euclidean thường nhậy cảm với “điểm kỳ dị”. Tuy
25
Generated by Foxit PDF Creator © Foxit Software
nhiên người ta cũng tìm được cách khắc phục phần trội này là sử dụng dịch
chuyển dữ liệu sang không gian log.[10]
Trung bình hàng
Trung bình hàng giả sử rằng mô tả của gene trong 1 thí nghiệm là giống với mô
tả của nó trong các thí nghiệm khác vì vậy xét trương hợp khi gene A có dữ liệu bị
khuyết ở thí nghiệm một thì giá trị bị khuyết này sẽ được thay bằng giá trị trung bình
của các biểu diễn giá trị của gene A trong các thí nghiệm từ 2 đến N. Tuy nhiên việc
giả sử này thường không đúng vì vậy phương pháp tính trung bình hành thường không
mang lại hiệu quả hay tính đúng đắn như phương pháp KNN.[11]
3.2.4.Tìm giải pháp tối ưu “toàn cục”
Để tìm giải pháp tối ưu cho giải thuật phân cụm k-means thì người ta sử dụng
thêm môt tham số đầu vào nữa là số lần chạy của giải thuật n. Mỗi lần chạy lại cụm
khởi tạo sẽ khác nhau. Tổng khoảng cách của các đối tượng với “trung tâm” hay
“center” của cụm là được lưu lại sau mỗi lần chạy lại và giải pháp với tổng này nhỏ
nhất sẽ được trả về là giải pháp tối ưu nhất trong các lần chạy. [8]
Chú ý:
o Số lần chạy lại giải thuật n phụ thuộc vào số đối tượng trong tập dữ liệu ban
đầu.
o Nếu giải pháp tối ưu được tìm thấy nhiều lần thì việc còn một giải pháp tốt
hơn giải pháp vừa tìm là rất hiếm.
o Nếu giải pháp tối ưu chỉ được tìm thấy một lần thì có thể sẽ có giải pháp khác
tốt hơn (tức có tổng khoảng cách bên trong cụm nhỏ hơn).
3.2.5.Việc xác định số cụm k
Hiện tại vẫn chưa có phương pháp hiệu quả nào để xác định trước số cụm k. Tuy
nhiên có một phương pháp hay được dùng là tùy theo tập dữ liệu mà chọn nhiều giá trị
của k sau đó đánh giá kết quả phân cụm (dùng một giải thuật đánh giá) của những giá
trị k khác nhau.
26
Generated by Foxit PDF Creator © Foxit Software
Chương 4: Phát triển ứng dụng cho bài toán
phân cụm dữ liệu gene microarray
Trong những chương trước tôi đã trình bày về vấn đề phân cụm cho dữ liệu gene
microarray, các phương pháp phân cụm cho dữ liệu gene microarray và hướng giải
quyết cho bài toán phân cụm. Như đã trình bày, tôi sẽ chọn phương pháp phân cụm k-
means để cài đặt trong ứng dụng của mình. Trong chương này sẽ trình bày chi tiết về
việc phát triển chương trình ứng dụng “Gene Cluster”.
Ứng dụng “Gene Cluster” là chương trình mà tôi phát triển dựa trên mã nguồn
mở của phần mềm “Cluster 3.0” trong đó tôi có một số cải tiến thêm về giao diện cũng
như về chức năng.
4.1. Các chức năng của ứng dụng
Đầu tiên ứng dụng này cho phép người dùng tải tập dữ liệu vào (tập dữ liệu vào
này thường được lưu ở file text). Sau khi tải xong ta thu được tập dữ liệu mà được biểu
diễn dưới dạng các ma trận hay mảng ví dụ như ma trận dữ liệu mô tả gene, mảng
chứa tên gene, ma trận đánh dấu dữ liệu khuyết,…. Người dùng có thể chọn chức năng
lọc dữ liệu (Filter Data) để lọc đi những dữ liệu theo các tiêu chí người dùng chọn. Dữ
liệu sau khi được lọc có thể qua chức năng điều chỉnh (Adjust Data) để giúp người
dùng điều chỉnh lại tập dữ liệu thu được cho dễ dàng cho việc thực hiện chức năng
phân cụm tiếp theo. Tập dữ liệu sau khi thu được sẽ được dùng làm đầu vào cho chức
năng phân cụm K-means và Intra-Cluster Distance. Người dùng có thể chọn chức năng
lưu file để lưu lại tập dữ liệu hiện tại dưới dạng file text.
4.1.1.Mô hình tương tác giữa các module
27
Generated by Foxit PDF Creator © Foxit Software
Tập dữ liệu 1
1
3
Tải dữ liệu
Lọc dữ liệu
Tập dữ liệu 2
ữ liệu 1
Kết quả
2
Kết quả phân cụm
Lưu file
Tập dữ liệu 3
4
Tập dữ liệu 5
Xử lý dữ liệu
khuyết
6
K-means
5
Tập dữ liệu 4
Tập dữ liệu 3
Điều chỉnh dữ
liệu
Hình 6 : Sơ đồ DFD mô tả sự tương tác dữ liệu và chức năng.
Các tập dữ liệu ở đây là tập dữ liệu thu được sau khi qua các chức năng bao
gồm các ma trận mô tả gene, ma trận đánh dấu dữ liệu khuyết, mảng chứa định danh
các gene, tên các gene và một số mảng phụ khác.
Sau đây tôi sẽ giới thiệu chi tiết về các chức năng trong chương trình “Gene
Cluster”.
4.1.2.Tải, Lưu file, lọc, điều chỉnh dữ liệu và xử lý dữ liệu khuyết
Tải file và lưu file
Bạn có thể tải dữ liệu cần phân tích bằng việc chọn biểu tượng load file trong
menu File. Và lưu lại tập dữ liệu dưới dạng file text bằng cách click vào biểu tượng
Save file trong menu file.
28
Tải về để xem bản đầy đủ
46 trang
18/04/2025
60
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Nghiên cứu một số phương pháp phân cụm cho dữ liệu gene microarray", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_nghien_cuu_mot_so_phuong_phap_phan_cum_cho_du_lieu.pdf
