An association analysis approach to biclustering

Gaurav Pandey, Gowtham Atluri, Michael S. Steinbach, Chad L. Myers, Vipin KumarKDD 2009 · DOI

TL;DR

This paper introduces RAP, a novel framework for discovering "range support" patterns in real-valued data, which effectively identifies coherent biclusters (groups of genes with similar expression patterns across a subset of conditions). RAP addresses limitations of existing biclustering methods by enabling exhaustive discovery and reducing information loss from data transformations, showing promise in uncovering biologically relevant functional modules in microarray data.

What Problem Does This Paper Address?

Discovering "biclusters" – subsets of genes that exhibit coherent expression patterns across a subset of experimental conditions – is crucial in fields like biology, particularly for analyzing microarray data. Existing biclustering algorithms often struggle to exhaustively search the vast space of possible biclusters, leading to missed patterns, especially smaller ones. Furthermore, many association analysis techniques, while good at exhaustive pattern discovery, are limited to binary or categorical data, forcing real-valued data into less informative formats like discretization or binarization. This paper tackles the challenge of finding coherent biclusters in real-valued data exhaustively and efficiently, without losing critical information.

Methods

The core of this paper is the RAP (RAnge support Pattern) framework. It introduces a new range support measure designed for real-valued data. This measure considers not only the range of values for a set of items (genes) within a transaction (condition) but also the sign of these values. A transaction contributes to the range support of a pattern only if all item values within that pattern are either positive or negative, and their variation falls within a user-defined threshold (controlled by parameters $\alpha$ and $\delta$). This range support measure is proven to be anti-monotonic, a crucial property that allows it to be used within an Apriori-like algorithm for exhaustive pattern discovery. The framework efficiently searches for patterns by representing itemsets in a prefix tree and outputs closed itemsets to avoid redundancy.

Datasets

The primary dataset used for evaluation is the S. cerevisiae (yeast) microarray data set from Hughes et al. [19]. This dataset consists of gene expression levels across various conditions and is a standard benchmark for biclustering research. The authors specifically used a subset of 4684 genes × 300 conditions, as the remaining genes were not associated with any functional classes.

Key Insights and Ideas

  • Range and Sign Coherence: The novel range support measure is a key innovation, capturing both the magnitude (range) and direction (sign) of gene expression, which is critical for biological interpretation.
  • Exhaustive Discovery: Unlike many heuristic biclustering algorithms, RAP's anti-monotonicity allows for a complete search of the pattern space, ensuring no potentially interesting patterns are missed.
  • Reduced Information Loss: By directly working with real-valued data, RAP avoids the information loss inherent in discretization or binarization methods.
  • Complementarity to Existing Methods: RAP doesn't aim to replace existing biclustering algorithms but rather to complement them, offering a different perspective and uncovering patterns that might be hidden in larger biclusters found by other methods.
  • Enrichment of Small Functional Classes: RAP patterns show a strong ability to identify functionally enriched groups of genes, particularly those belonging to smaller, more specific Gene Ontology (GO) biological process classes, which are often more biologically significant.

Key Results

  • Coherence (MSE): RAP patterns consistently exhibited the lowest Mean Squared Error (MSE) scores among the evaluated algorithms (RAP, CC, ISA), indicating a higher degree of coherence in constant row/column models.
  • Functional Enrichment:
    • RAP patterns were significantly better enriched with small functional classes (1-30 members) compared to ISA and CC biclusters, especially at strict p-value thresholds (e.g., $1 \times 10^{-5}$).
  • While ISA biclusters performed better with larger functional classes (likely due to their larger size), RAP excelled at identifying functionally coherent groups within smaller, more specific biological processes.
  • Efficiency: The RAP framework demonstrated comparable runtimes to ISA and significantly outperformed CC, which took over a day to compute its biclusters, making RAP a practical choice for large datasets.
  • Novel Pattern Discovery: The paper provides examples where RAP discovered finer-grained patterns and functional enrichments that were either missed or embedded within larger, less specific biclusters by ISA.

Limitations and Future Work

The authors acknowledge several limitations and propose future directions:

  • Pattern Size: The strict range support thresholds might split larger patterns into smaller ones. Concepts like "colossal patterns" could be explored to merge core patterns.
  • Item Coverage: The exhaustive search can be computationally intensive. Techniques like length-varying support and support envelopes could improve coverage.
  • Scalability: Further optimization of data structures and algorithms, potentially drawing from methods like the TAPER algorithm, could enhance scalability.
  • Extending Bicluster Types: Future work includes extending RAP to discover other types of biclusters, such as those with constant additive/multiplicative models or coherent evolutions.
  • Pre-processing Impact: Investigating the effect of various pre-processing steps (normalization, sparsification, denoising) on RAP's performance is suggested.
  • Hybrid Approaches: Comparing RAP with methods that use binarized versions of real-valued data and developing hybrid approaches are also proposed.

Summary updated

BibTeX
@inproceedings{pandey2009association,
  author = {Gaurav Pandey and Gowtham Atluri and Michael S. Steinbach and Chad L. Myers and Vipin Kumar},
  title = {{An association analysis approach to biclustering}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2009},
  doi = {10.1145/1557019.1557095},
}
Figure