Gene-Expression Analysis I – Clustering (CSE 443)

Machine Learning Foundations for Gene-Expression Analysis

• Definition of Learning
  • A computer program learns from experience E with respect to task class T and performance measure P if its performance at T (as measured by P) improves with E.
  • Typical gene-expression–related tasks (T):
  • Classification, Regression, Transcription / Translation prediction, Structured Output prediction, Anomaly Detection, Synthesis, Imputation, Denoising.
  • Common performance measures (P): accuracy, adjusted-rand-index (ARI), mean-absolute-error (MAE), $R^2$, peak-signal-to-noise-ratio (PSNR), etc.
  • Forms of experience (E) in bioinformatics: nucleotide/protein sequences, 3-D structures, physico-chemical properties, gene-count tables, etc.

Measuring Gene Expression

• Motivation: To understand phenotype via the abundance of functional proteins. Because direct protein quantification is hard (location, modification, incomplete proteome), mRNA levels are used as a proxy.
• Two mainstream technologies:
  • Expression Microarrays
  • Short DNA probes are immobilized on a solid surface ("gene chip").
  • Cellular RNA → reverse-transcribed into cDNA.
  • cDNA is washed over the chip; hybridization events cause fluorescence.
  • Limitations:
    • Cannot distinguish mRNA isoforms.
    • Works only for known transcripts (cannot discover novel genes).
    • Saturation leads to reduced dynamic range for highly expressed genes.
    • Analog signal → lower digital resolution.
  • RNA-Seq
  • Total RNA isolated from cell/tissue.
  • Reverse-transcriptase (RT) converts RNA → cDNA.
  • High-throughput sequencer reads cDNA fragments.
  • Digital counts ⇒ wider dynamic range, nucleotide-level resolution, isoform detection.
• Single-Cell RNA-Seq (scRNA-seq)
  • Individual cells (e.g., from tumor) isolated and sequenced.
  • Generates a cell × gene count matrix.
  • Enables comparison of gene-expression profiles at single-cell granularity.
  • Visualization often via PCA/UMAP; clusters may correspond to cell types or states.

Expression Data Matrix & Exploratory Goals

• After any of the above assays we obtain an $n \times m$ matrix $E$:
  • $n$ = number of genes, $m$ = checkpoints/conditions/time-points/cells.
  • Entry $E_{i,j}$ = expression level of gene $i$ at condition $j$.
• Row $i$ (vector of length $m$) = expression vector of gene $i$.
• Observations from raw vectors:
  • Genes with similar vectors → possibly co-regulated (same transcription factor).
  • Similarity allows function inference for un-annotated genes via "guilt by association".
  • Biomedical usages: pre- vs post-drug treatment, tumor vs normal tissue, etc.
• Two general data-mining goals:
  • Classification: derive features that assign instances to known classes.
  • Clustering: discover hidden groupings without prior labels.

Desiderata for Good Clustering

• Homogeneity: points within a cluster are close (low intra-cluster distance).
• Separation: points from different clusters are far apart (high inter-cluster distance).

k-Means Clustering as an Optimization Problem

• Re-framing: choose $k$ centers (prototypes) $C = {c<em>1,\dots,c</em>k}$ minimizing average squared distance.
• Distance of a point to centers:
  $d(v,C) = \min<em>{c</em>i \in C} \; \lVert v - c<em>i \rVert</em>2$
• Squared-Error Distortion:
  $\text{distortion}(\text{Data},C) = \frac1n \sum_{p\in\text{Data}} d(p,C)^2$
• k-Means problem: find $C$ minimizing the above.

Lloyd’s Algorithm (classic k-Means)

1. Randomly initialize $k$ centers.
2. Until convergence:
   • Assignment step (Centers→Clusters): assign each point to nearest center.
   • Update step (Clusters→Centers): recompute each center as the centroid (mean) of its assigned points.

• Drawbacks & assumptions:
  • May converge to local minima; sensitive to initialization.
  • Must pre-specify $k$.
  • Implicitly assumes roughly spherical, equal-sized clusters.
  • Poor with outliers/noise; computationally heavy in high-dimensional data; handles only continuous attributes.

Better Initialization: k-Means++

• Procedure:
  1. Choose first center uniformly at random from data.
  2. For each subsequent center, pick a data point with probability proportional to $d(\text{point},\text{Centers})^2$.
  3. Repeat until $k$ centers selected; then run Lloyd.
• Benefit: lowers chance of extremely poor local minima.

Hard vs Soft Assignment

• k-Means performs hard assignment (point → single cluster).
• Mid-points between clusters handled poorly ⇒ motivates soft/k-probabilistic clustering.

EM Algorithm for Soft k-Means (Gaussian Mixture intuition)

• Iterate two phases:
  • E-step (Centers→Soft Clusters): compute responsibility matrix $\text{HiddenMatrix}_{i,j}$ = degree to which center $i$ explains point $j$.
  • Can be based on inverse-square law or on Gibbs partition function with stiffness $\beta$:
    $\text{HiddenMatrix}<em>{i,j}=\frac{e^{-\beta \lVert x</em>j-c<em>i \rVert^2}}{\sum</em>{l=1}^{k} e^{-\beta \lVert x<em>j-c</em>l \rVert^2}}$
  • M-step (Soft Clusters→Centers): update each center to weighted mean:
    $c<em>i = \frac{\sum</em>{j=1}^{n} \text{HiddenMatrix}<em>{i,j} \; x</em>j}{\sum<em>{j=1}^{n} \text{HiddenMatrix}</em>{i,j}}$
• Example (1-D): 5 points $(-3,-2,0,2,3)$, 2 centers ${-2.5,2.5}$.
  • With $\beta=1$, responsibilities yield updated centers $c<em>1\approx -1.955$, $c</em>2\approx 1.955$ (almost symmetric).
• Advantages: handles ambiguity; outputs membership probabilities; closer to Gaussian-mixture expectation-maximization.

Hierarchical Clustering

• Goal: build a dendrogram that successively merges closest clusters; no need to pre-specify $k$.
• Distance matrix preparation: compute pairwise distances between all gene expression vectors (Euclidean, correlation, etc.). Small distance ⇒ similar expression ⇒ potential functional relation.

Agglomerative Algorithm (bottom-up)

HIERARCHICALCLUSTERING(D, n):
  Clusters ← {n singleton clusters}
  T ← graph with n isolated nodes
  while |Clusters| > 1:
    (C_i, C_j) ← two closest clusters in D
    C_new ← C_i ∪ C_j
    add C_new as node in T; connect to C_i and C_j
    update D: remove rows/cols of C_i, C_j; add row/col for C_new
  root T at the final cluster and return T

• Distance update between a new cluster $C<em>{new}$ and existing cluster $C$ can follow linkage criteria: single, complete, average, Ward, etc. (Lecture focuses on abstract placeholder $D(C</em>{new},C)$.)
• Dendrogram cuts: horizontal cut yields flat clustering at desired granularity; multiple illustrated cuts show alternative groupings.
• Example distance matrices shown in slides illustrate iterative merging:
  • Start with 10 genes (labels 81-89, 810).
  • Observe smallest distances (e.g., genes 83 & 85) merging first.
  • Later merges produce composite clusters {83,85,88}, {82,84}, etc., until single root.

Comparative Summary of Clustering Methods

• k-Means / Lloyd:
  • Pros: simple, scalable to large data, intuitive centers.
  • Cons: assumes convex, similar-size clusters; sensitive to outliers and dimension; hard assignments.
• Soft k-Means / EM:
  • Pros: probabilistic memberships; smoother boundaries.
  • Cons: more computation; still assumes elliptical clusters if Gaussian kernels; parameter $\beta$ tuning.
• Hierarchical:
  • Pros: no need for $k$; dendrogram provides multi-scale view; flexible linkage.
  • Cons: $O(n^2)$ memory/time; once merged cannot be undone; sensitive to noise and choice of linkage.

Practical & Ethical Considerations

• Choice of clustering influences downstream biological inference (e.g., drug target discovery, cancer subtype classification). Wrong assumptions can mislead experiments.
• Data privacy for patient-derived expression profiles must be safeguarded.
• Reproducibility: store preprocessing steps (normalization, batch correction) alongside clustering code.

Connections & Further Reading

• Techniques build on foundational statistics (least-squares, maximum-likelihood) and physics (Boltzmann distribution for responsibilities).
• Chapter 8 of "Bioinformatics Algorithms: An Active Learning Approach (Vol 2)" provides extended tasks and exercises.
• Later lectures will integrate clustering output with pathway analysis, dimensionality reduction, and network inference.