Microarray data analysis with PCA in a DBMS

ABSTRACT

Microarray data sets contain expression levels of thousands of genes. The statistical analysis of such data sets is typically performed outside a DBMS with statistical packages or mathematical libraries. In this work, we focus on analyzing them inside the DBMS. This is a difficult problem because microarray data sets have high dimensionality, but small size. First, due to DBMS limitations on a maximum number of columns per table, the data set has to be pivoted and transformed before analysis. More importantly, the correlation matrix on tens of thousands of genes has millions of values. While most high dimensional data sets can be analyzed with the classical PCA method, small, but high dimensional, data sets can only be analyzed with Singular Value Decomposition (SVD). We adapt the Householder tridiagonalization and QR factorization numerical methods to solve SVD inside the DBMS. Since these mathematical methods require many matrix operations, which are hard to express in SQL, query optimizations and efficient UDFs are developed to get good performance. Our proposed techniques achieve processing times comparable with those from the R package, a well-known statistical tool. We experimentally show our methods scale well with high dimensionality.

REFERENCES

• 1: John A. Berger , Sampsa Hautaniemi , Sanjit K. Mitra , Jaakko Astola, Jointly Analyzing Gene Expression and Copy Number Data in Breast Cancer Using Data Reduction Models, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.1, p.2, January 2006 [doi>10.1109/TCBB.2006.10]
• 2: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 3: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 4: K. A. Do, G. J. McLachlan, R. Bean, and S. Wen. Application of gene shaving and mixture models to cluster microarray gene expression data. Cancer Informatics, 2:25--43, 2006.
• 5: T. Hastie, R. Tibshirani, A. Eisen, R. Levy, L. Staudt, D. Chan, and P. Brown. Gene shaving as a method for identifying distinct sets of genes with similar expression patterns. Genome Biology 2000, 1, 2000.
• 6: T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer, New York, 1st edition, 2001.
• 7: Erwin Kreyszig, Advanced Engineering Mathematics: Maple Computer Guide, John Wiley & Sons, Inc., New York, NY, 2000
• 8: L. Liu, D. M. Hawkins, S. Ghosh, and S. S. Young. Robust singular value decomposition analysis of microarray data. In Proceedings of the National Academy of Sciences of the United States of America, pages 13167--13172, 2003.
• 9: Ying Liu , Shamkant B. Navathe , Jorge Civera , Venu Dasigi , Ashwin Ram , Brian J. Ciliax , Ray Dingledine, Text Mining Biomedical Literature for Discovering Gene-to-Gene Relationships: A Comparative Study of Algorithms, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.1, p.62-76, January 2005 [doi>10.1109/TCBB.2005.14]
• 10: Geoffrey J. McLachlan, Kim-Anh Do, and Christophe Ambroise. Analyzing Microarray Gene Expression Data. John Wiley and Sons, New Jersey, 2004.
• 11: Kuan-ming Lin , Jaewoo Kang, Exploiting inter-gene information for microarray data integration, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244032]
• 12: Vinay Nadimpally , Mohammed J. Zaki, A novel approach to determine normal variation in gene expression data, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980975]
• 13: See-Kiong Ng , Zexuan Zhu , Yew-Soon Ong, Whole-genome functional classification of genes by latent semantic analysis on microarray data, Proceedings of the second conference on Asia-Pacific bioinformatics, p.123-129, January 01, 2004, Dunedin, New Zealand
• 14: Carlos Ordonez, Building statistical models and scoring with UDFs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247599]
• 15: Carlos Ordonez , Javier García-García, Vector and matrix operations programmed with UDFs in a relational DBMS, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183687]
• 16: Huseyin Polat , Wenliang Du, SVD-based collaborative filtering with privacy, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066860]
• 17: Li Shen , Eng Chong Tan, Dimension Reduction-Based Penalized Logistic Regression for Cancer Classification Using Microarray Data, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.2, p.166-175, April 2005 [doi>10.1109/TCBB.2005.22]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition

General Terms:
Algorithms, Performance

Keywords:
dbms, gene, pca, sql