Gene expression data classification using locally linear discriminant embedding

Bo Li, Chun-Hou Zheng, De-Shuang Huang, Lei Zhang, Kyungsook HanComputers in Biology and Medicine 2010 · DOI

TL;DR

This paper introduces Locally Linear Discriminant Embedding (LLDE), a novel manifold learning technique for classifying gene expression data. LLDE effectively addresses the high dimensionality and limited sample size inherent in microarray data by simultaneously minimizing reconstruction error and maximizing class separability, leading to improved classification accuracy compared to existing methods.

What Problem Does This Paper Address?

Gene expression data, often generated by DNA microarrays, presents a significant challenge for traditional classification methods. This data is characterized by a massive number of variables (genes) but a relatively small number of observations (samples or patients). This "high-dimensional, small-sample size" (HDSS) problem makes it difficult to extract meaningful patterns and accurately classify samples, for instance, to distinguish between different types of tumors for personalized therapy. While feature selection and extraction methods exist, linear approaches often fail to capture the complex, non-linear relationships within the data. Manifold learning offers a promising avenue by assuming that high-dimensional data lies on a lower-dimensional manifold, but existing supervised manifold learning methods can be complex to implement or may not fully leverage class information for optimal discrimination.

Methods

The core contribution of this paper is the Locally Linear Discriminant Embedding (LLDE) algorithm. LLDE builds upon the principles of Locally Linear Embedding (LLE), a popular manifold learning technique that preserves local neighborhood structures. However, standard LLE has limitations, including the "out-of-sample" problem and its inability to directly use class labels, which can hinder classification accuracy.

LLDE addresses these issues by:

  • Incorporating Class Information: Unlike standard LLE, LLDE explicitly uses class labels to guide the embedding process. It aims to make samples from the same class closer together in the embedded space while pushing samples from different classes further apart.
  • Introducing Discriminant Embedding: The algorithm modifies the objective function of LLE to include a term that maximizes the margin between classes. This is achieved through a Modified Maximizing Margin Criterion (MMMC), which seeks to optimize the projection by considering both within-class scatter and between-class scatter.
  • Linear Approximation and Optimization: To overcome the out-of-sample problem and simplify computation, LLDE employs a linear approximation of the embedding. It then formulates a constrained multi-object optimization problem that minimizes reconstruction error and maximizes the class margin, solved using generalized eigenvalue decomposition.
  • Translation and Rescaling: LLDE also incorporates a vector translation and distance rescaling model to further enhance class separability.

Datasets

The paper evaluates LLDE on four publicly available two-class gene expression datasets:

  • Acute leukemia data
  • High-grade glioma data
  • Prostate cancer data
  • Breast cancer data

Additionally, for multi-class experiments, two datasets were used:

  • A multi-class Leukemia dataset (distinguishing between ALL_B, ALL_T, and AML)
  • A central nervous system tumors dataset (comprising medulloblastomas, malignant gliomas, rhabdoids, and normals)

The datasets were split into training and testing sets, and experiments were repeated with 20 random splits to ensure robust evaluation.

Key Insights and Ideas

  • Manifold Learning for Gene Expression is Promising: The paper strongly advocates for manifold learning as a powerful tool for analyzing gene expression data, positing that this data likely resides on a complex, non-linear manifold influenced by numerous biological factors.
  • Supervised Manifold Learning is Crucial for Classification: Simply reducing dimensionality without considering class labels (as in unsupervised LLE) is insufficient for effective tumor classification. LLDE's strength lies in its ability to leverage class information to create a more discriminative embedding.
  • Balancing Reconstruction and Discrimination: The core innovation of LLDE is its ability to simultaneously preserve local data structure (via LLE principles) and enhance class separability (via MMMC). This dual objective is key to its superior performance.
  • LLDE Outperforms Traditional Methods: The experimental results consistently show LLDE achieving higher classification accuracies with lower standard deviations compared to established methods like PCA, PLS, and even supervised LLE (SLLE).

Key Results

  • Improved Classification Accuracy: LLDE consistently achieved the highest mean classification accuracies across the tested datasets, often by a significant margin. For example, on the Acute leukemia dataset, LLDE+K-NN achieved 95.59% accuracy, outperforming PCA+K-NN (80.29%) and SLLE+K-NN (92.65%).
  • Reduced Variance: LLDE also demonstrated lower standard deviations in accuracy across multiple runs, indicating a more stable and reliable performance.
  • Effective in Multi-Class Settings: The method showed strong performance in multi-class classification experiments, further validating its robustness.
  • Competitive Dimensionality Reduction: LLDE typically required a low number of dimensions (features) to achieve its high accuracy, suggesting efficient feature extraction.
  • Random Forest Performance: When used with a Random Forest classifier, LLDE also yielded competitive results, highlighting its versatility.

Limitations and Future Work

  • Gene Selection: The authors acknowledge that LLDE, while excellent for classification, does not directly identify important genes. Future work could explore methods to extract key genes from the LLDE embedding or develop new algorithms that combine discriminant manifold learning with biomarker discovery.
  • Rescaling Coefficient Impact: While the paper mentions testing the effect of the rescaling coefficient, the results indicated it had "few impacts" on recognition rate, suggesting it might be less critical than other aspects of the algorithm. Further investigation into its role could be beneficial.
  • Computational Cost: While LLDE aims to reduce computational cost compared to some other methods, the paper doesn't provide explicit comparisons of computational efficiency. This could be an area for future analysis.
  • Exploring New Algorithms: The authors express optimism about the potential of manifold learning in bioinformatics and suggest investigating new algorithms for biomarker discovery, building on the success of LLDE in tumor diagnosis.

Summary updated

BibTeX
@article{li2010gene,
  author = {Bo Li and Chun-Hou Zheng and De-Shuang Huang and Lei Zhang and Kyungsook Han},
  title = {{Gene expression data classification using locally linear discriminant embedding}},
  journal = {Computers in Biology and Medicine},
  year = {2010},
  doi = {10.1016/j.compbiomed.2010.08.003},
}
Figure