A simple and exact Laplacian clustering of complex networking phenomena: Application to gene expression profiles

doi:10.1073/pnas.0708598105

A simple and exact Laplacian clustering of complex networking phenomena: Application to gene expression profiles

*Department of Statistics,
^†National Research Laboratory for Computational Proteomics and Biophysics, Department of Physics, and
^‡Interdisciplinary Research Program of Bioinformatics, Pusan National University, Busan 609-735, Korea

Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved January 25, 2008 (received for review September 11, 2007)

Abstract

Unraveling of the unified networking characteristics of complex networking phenomena is of great interest yet a formidable task. There is currently no simple strategy with a rigorous framework. Using an analogy to the exact algebraic property for a transition matrix of a master equation in statistical physics, we propose a method based on a Laplacian matrix for the discovery and prediction of new classes in the unsupervised complex networking phenomena where the class of each sample is completely unknown. Using this proposed Laplacian approach, we can simultaneously discover different classes and determine the identity of each class. Through an illustrative test of the Laplacian approach applied to real datasets of gene expression profiles, leukemia data [Golub TR, et al. (1999) Science 286:531–537], and lymphoma data [Alizadeh AA, et al. (2000) Nature 403:503–511], we demonstrate that this approach is accurate and robust with a mathematical and physical realization. It offers a general framework for characterizing any kind of complex networking phenomenon in broad areas irrespective of whether they are supervised or unsupervised.

Footnotes

^§To whom correspondence should be addressed. E-mail: chang{at}random.phys.pusan.ac.kr
Author contributions: C.K. and M.C. contributed equally to this work; C.K., M.C., and I.C. designed research; C.K., M.C., M.K., and I.C. performed research; C.K. and M.C. contributed new reagents/analytic tools; C.K., M.C., M.K., and I.C. analyzed data; and C.K. and I.C. wrote the paper.
The authors declare no conflict of interest.
This article is a PNAS Direct Submission.
This article contains supporting information online at www.pnas.org/cgi/content/full/0708598105/DC1.