Biology Reference
In-Depth Information
Chapter 16
A Novel Clustering Approach: Global Optimum Search with
Enhanced Positioning
Meng Piao Tan
Department of Chemical Engineering
Princeton University
Princeton, NJ 08544-5263, USA
E-mail address: mtan@princeton.edu
Christodoulos A. Floudas
Department of Chemical Engineering
Princeton University
Princeton, NJ 08544-5263, USA
Tel: (609) 258-4595
E-mail address: floudas@titan.princeton.edu
Cluster analysis of genome-wide expression data from DNA microarray hy-
bridization studies is a useful tool for identifying biologically relevant gene
groupings. It is hence important to apply a rigorous yet intuitive clustering algo-
rithm to uncover these genomic relationships. In this study, we describe a novel
clustering algorithm framework based on a variant of the Generalized Benders
Decomposition, denoted as the Global Optimum Search [2, 19, 21, 23, 51] which
includes a procedure to determine the optimal number of clusters to be used. The
approach involves a pre-clustering of data points to define an initial number of
clusters and the iterative solution of a Linear Programming problem (the primal
problem) and a Mixed-Integer Linear Programming problem (the master prob-
lem), that are derived from a Mixed Integer Nonlinear Programming problem
formulation. Badly-placed data points are removed to form new clusters, thus
ensuring tight groupings amongst the data points and incrementing the number of
clusters until the optimum number is reached. We apply the proposed clustering
algorithm to experimental DNA microarray data centered on the Ras signaling
pathway in the yeast Saccharomyces Cerevisiae and compare the results to that
obtained with some commonly-used clustering algorithms. Our algorithm comes
up favorably against these algorithms in the aspects of intra-cluster similarity and
Author to whom all correspondence should be addressed
307
Search WWH ::




Custom Search