MULTI-K: accurate classification of microarray subtypes using ensemble k-means clustering.
BACKGROUND
Uncovering subtypes of disease from microarray samples has important clinical implications such as survival time and sensitivity of individual patients to specific therapies. Unsupervised clustering methods have been used to classify this type of data. However, most existing methods focus on clusters with compact shapes and do not reflect the geometric complexity of the high dimensional microarray clusters, which limits their performance.


RESULTS
We present a cluster-number-based ensemble clustering algorithm, called MULTI-K, for microarray sample classification, which demonstrates remarkable accuracy. The method amalgamates multiple k-means runs by varying the number of clusters and identifies clusters that manifest the most robust co-memberships of elements. In addition to the original algorithm, we newly devised the entropy-plot to control the separation of singletons or small clusters. MULTI-K, unlike the simple k-means or other widely used methods, was able to capture clusters with complex and high-dimensional structures accurately. MULTI-K outperformed other methods including a recently developed ensemble clustering algorithm in tests with five simulated and eight real gene-expression data sets.


CONCLUSIONS
The geometric complexity of clusters should be taken into account for accurate classification of microarray data, and ensemble clustering applied to the number of clusters tackles the problem very well. The C++ code and the data sets tested are available from the authors.
Kim
Eun-Youn
EY
National Institute for Mathematical Sciences (NIMS), Yuseong, Daejeon 305-340, Republic of Korea. eunykim@nims.re.kr
Kim
Seon-Young
SY
Ashlock
Daniel
D
Nam
Dougu
D
D016000:Cluster Analysis; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D010363:Pattern Recognition, Automated; D012984:Software
Proc Natl Acad Sci U S A. 2005 Dec 27;102(52):19075-80
16365291
Bioinformatics. 2003 Jun 12;19(9):1090-9
12801869
Proc Natl Acad Sci U S A. 2003 Jul 8;100(14):8418-23
12829800
Science. 2000 Dec 22;290(5500):2319-23
11125149
Bioinformatics. 2007 Nov 1;23(21):2888-96
17872912
Pac Symp Biocomput. 2002;:6-17
11928511
Science. 1999 Oct 15;286(5439):531-7
10521349
Nat Clin Pract Oncol. 2006 Nov;3(11):621-32
17080180
Bioinformatics. 2003;19 Suppl 1:i205-11
12855459
Bioinformatics. 2005 Aug 1;21(15):3201-12
15914541
Nature. 2000 Feb 3;403(6769):503-11
10676951
N Engl J Med. 2002 Jun 20;346(25):1937-47
12075054
Bioinformatics. 2002 Nov;18(11):1462-9
12424117
Bioinformatics. 2006 Aug 15;22(16):1988-97
16766561
Nature. 2000 Aug 17;406(6797):747-52
10963602
Cancer Cell. 2002 Mar;1(2):133-43
12086872
Bioinformatics. 2006 Jul 15;22(14):1717-22
16672258
Proc Natl Acad Sci U S A. 2001 Dec 18;98(26):15149-54
11742071
Genome Biol. 2002 Jun 25;3(7):RESEARCH0036
12184810
Bioinformatics. 2005 Jul 15;21(14):3114-21
15879455
Genome Biol. 2004;5(11):R94
15535870
BMC Bioinformatics. 2003 Sep 6;4:36
12959646
Bioinformatics. 2002 Sep;18(9):1194-206
12217911
Bioinformatics. 2005 Mar 1;21(5):650-9
15388519
Proc Natl Acad Sci U S A. 1998 Dec 8;95(25):14863-8
9843981
Multivariate Behav Res. 1986 Oct 1;21(4):441-58
26828221
Bioinformatics. 2002 Mar;18(3):413-22
11934740
Bioinformatics. 2007 Dec 1;23(23):3225-31
17977884
Mol Biol Cell. 1998 Dec;9(12):3273-97
9843569
Bioinformatics. 2005 May 1;21(9):1927-34
15647300
IEEE Trans Pattern Anal Mach Intell. 2006 Nov;28(11):1798-808
17063684