Finding large average submatrices in high dimensional data

Abstract

The search for sample-variable associations is an important problem in the exploratory analysis of high dimensional data. Biclustering methods search for sample-variable associations in the form of distinguished submatrices of the data matrix. (The rows and columns of a submatrix need not be contiguous.) In this paper we propose and evaluate a statistically motivated biclustering procedure (LAS) that finds large average submatrices within a given real-valued data matrix. The procedure operates in an iterative-residual fashion, and is driven by a Bonferroni-based significance score that effectively trades off between submatrix size and average value. We examine the performance and potential utility of LAS, and compare it with a number of existing methods, through an extensive three-part validation study using two gene expression datasets. The validation study examines quantitative properties of biclusters, biological and clinical assessments using auxiliary information, and classification of disease subtypes using bicluster membership. In addition, we carry out a simulation study to assess the effectiveness and noise sensitivity of the LAS search procedure. These results suggest that LAS is an effective exploratory tool for the discovery of biologically relevant structures in high dimensional data. Software is available at https://genome.unc.edu/las/.

Published in at http://dx.doi.org/10.1214/09-AOAS239 the Annals of Applied Statistics (http://www.imstat.org/aoas/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Coupled Two-Way Clustering Analysis of Gene Microarray Data
• A tutorial introduction to the minimum description length principle
• Finding large average submatrices in high dimensional data

Cited by in corpus (40)

• Finding large average submatrices in high dimensional data
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• On combinatorial testing problems
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Convex Biclustering
• Finding One Community in a Sparse Graph
• Computational Barriers to Estimation from Low-Degree Polynomials
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• A testing based extraction algorithm for identifying significant communities in networks
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Semidefinite Programs for Exact Recovery of a Hidden Community
• Submatrix localization via message passing
• The Overlap Gap Property in Principal Submatrix Recovery
• Universality of Computational Lower Bounds for Submatrix Detection
• Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
• Information Limits for Recovering a Hidden Community
• Energy Landscape for large average submatrix detection problems in Gaussian random matrices
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Statistical mechanics of the maximum-average submatrix problem
• Finding a Large Submatrix of a Gaussian Random Matrix
• Lattice partition recovery with dyadic CART
• Statistical Limits of Convex Relaxations
• Biclustering with Alternating K-Means
• On the maximal size of Large-Average and ANOVA-fit Submatrices in a Gaussian Random Matrix
• A Multiscale Scan Statistic for Adaptive Submatrix Localization
• Distribution-Free, Size Adaptive Submatrix Detection with Acceleration
• BIDEAL: A Toolbox for Bicluster Analysis -- Generation, Visualization and Validation
• A Review on Analysis and Visualization Methods for Biclustering
• Distribution-free Detection of a Submatrix
• Latent Association Mining in Binary Data
• Exploring the genetic patterns of complex diseases via the integrative genome-wide approach
• Exploring Common and Individual Characteristics of Students via Matrix Recovering
• A New Algorithm for Convex Biclustering and Its Extension to the Compositional Data
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules
• A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering
• Exact and Heuristic Algorithms for Constrained Biclustering