CIS Department Talk - June 6th, 2008

The Department of Computer and Information Science Present

Speakers:	Jengnan Tzeng,Genomics Research Center, Academia Sinica, Taipei, Taiwan; Henry Horng-Shing Lu, Institute of Statistics, National Chiao Tung University, Hsinchu, Taiwan;Wen-Hsiung Li1, Department of Ecology and Evolution, University of Chicago
Topic:	Multidimensional scaling for large genomic data sets
Date:	June 6th, 2008, 1:00 PM
Place:	John Mulcahy Hall, Room 312

Background Multi-dimensional scaling (MDS) is aimed to represent high dimensional data in a low dimensional space with preservation of the similarities between data points. This reduction in dimensionality is crucial for analyzing and revealing the genuine structure hidden in the data. For noisy data, dimension reduction can effectively reduce the effect of noise on the embedded structure. For large data set, dimension reduction can effectively reduce information retrieval complexity. Thus, MDS techniques are used in many applications of data mining and gene network research. However, although there have been a number of studies that applied MDS techniques to genomics research, the number of analyzed data points was restricted by the high computational complexity of MDS. In general, a non-metric MDS method is faster than a metric MDS, but it does not preserve the true relationships. The computational complexity of most metric MDS methods is over O(N^2), so that it is difficult to process a data set of a large number of genes N, such as in the case of whole genome microarray data.

Results We developed a new rapid metric MDS method with a low computational complexity, making metric MDS applicable for large data sets. Computer simulation showed that the new method of split-and-combine MDS (SC-MDS) is fast, accurate and efficient. Our empirical studies using microarray data on the yeast cell cycle showed that the performance of K-means in the reduced dimensional space is similar to or slightly better than that of K-means in the original space, but about three times faster to obtain the clustering results. Our clustering results using SC-MDS are more stable than those in the original space. Hence, the proposed SC-MDS is useful for analyzing whole genome data.

Conclusions Our new method reduces the computational complexity from O(N^3) to O(N) when the dimension of the feature space is far less than the number of genes N, and it successfully reconstructs the low dimensional representation as does the classical MDS. Its performance depends on the grouping method and the minimal number of the intersection points between groups. Feasible methods for grouping methods are suggested; each group must contain both neighboring and far apart data points. Our method can represent high dimensional large data set in a low dimensional space not only efficiently but also effectively.

Bio:
Henry Horng-Shing Lu received his Ph.D. and M.S. degrees in Statistics from Cornell University, NY, USA, in 1994 and 1990, respectively, and his B.S. degree in electric engineering from National Taiwan University, Taiwan, ROC, in 1986. He is a Professor in the Institute of Statistics, National Chiao Tung University, Hsinchu, Taiwan, ROC. He has been a visiting scholar at UCLA, Harvard University and University of Chicago. His research interests include statistics, medical images, and bioinformatics. He and collaborators have more than 30 journal papers published or accepted, including Journal of the American Statistical Association, Journal of Multivariate Analysis, Statistica Sinica, Journal of Computational and Graphical Statistics, IEEE Transactions on Reliability/Image Processing/Medical Imaging, Pattern Recognition, Ultrasound in Medicine and Biology, Trends in Genetics, Proceedings of the National Academy of Sciences of the United States of America, Journal of Computational Biology, Bioinformatics, BMC Bioinformatics and so forth.

For More Information Contact: Frank Hsu (Dept of Computer and Information Sciences) Email: hsu@trill.cis.fordham.edu