A Global Structural EM Algorithm for a Model of Cancer Progression

Ali Tofigh, Erik Sjölund, Mattias Höglund, Jens LagergrenNeurIPS 2011 · OpenReview

The Challenge of Modeling Cancer Progression

Understanding the sequence of genetic mutations—or aberrations—in cancer is crucial for accurate diagnosis and targeted treatment. However, modeling this progression presents significant challenges. First, cancer evolution is biologically complex; it rarely follows a single linear path, often exhibiting branching or converging evolutionary trajectories. Second, clinical data is notoriously noisy, frequently containing false positives (detecting a mutation that isn't present) and false negatives (missing a mutation that is).

Earlier mathematical models, such as standard Oncogenetic Trees (OTs), were "monotonic." They assumed a strict dependency where a child mutation could never occur unless its parent mutation had already taken place. Furthermore, they lacked a robust, formal mechanism to handle observation errors. While some researchers attempted to use mixtures of trees or more complex networks, these approaches often resulted in computationally intractable problems where finding the optimal model was nearly impossible.

Introducing Hidden-variable Oncogenetic Trees (HOTs)

To address these limitations, the authors introduce Hidden-variable Oncogenetic Trees (HOTs). The core innovation of this probabilistic model is the decoupling of the "true" biological state of the tumor from the observed clinical data:

  • Hidden Variables ($Z$): These represent the ground truth—whether the cancer progression has actually reached a specific genetic milestone.
  • Observable Variables ($X$): These represent the actual collected data, which may be flawed due to experimental noise or observational errors.

By explicitly modeling false positives and false negatives, the HOT model can effectively "see through" the noise in cytogenetic data that would otherwise confound a standard Oncogenetic Tree.

Example of a single tree structure modeling cancer progression pathways.

A "Global" Structural EM Algorithm

To train the HOT model, the researchers developed a novel Structural Expectation-Maximization (EM) algorithm. In standard EM algorithms, the Maximization step (M-step) typically only guarantees a slight improvement to the model, often getting stuck in local optima.

The authors' approach is uniquely "global." It leverages Edmonds’s optimal branching algorithm to find the absolute best tree structure that maximizes the expected complete log-likelihood of the data at every single iteration. This is particularly important because, unlike simple Maximum Spanning Tree (MST) algorithms, HOTs recognize that the relationship between mutations is directed and asymmetric. Edmonds's algorithm, designed specifically for directed arborescences, is the mathematically appropriate tool for this task.

Expanding to HOT-Mixtures

Cancer is rarely a monolithic disease; a single dataset might contain tumors evolving along entirely different primary pathways. To account for this, the authors extended their framework to HOT-mixtures. This allows the model to represent multiple distinct pathways of progression simultaneously within the same dataset, assigning a probability weight to each distinct tree.

A HOT-mixture model representing multiple distinct pathways of progression, each with an associated weight.

Experimental Validation and Results

The researchers rigorously evaluated their approach using both synthetic and real-world clinical data.

  • Synthetic Data: They generated random HOTs with varying numbers of vertices (10, 25, and 40) to test the algorithm's robustness. The HOT algorithm significantly outperformed Mtreemix (a popular existing tool) in recovering known structures, especially as the number of mutations or the level of data noise increased.
  • Biological Validation: The team applied the algorithm to the Mitelman Database, specifically analyzing cytogenetic data from 512 Colon Cancer (CC) tumors and 998 Kidney Cancer (RCC) tumors. Impressively, the algorithm automatically recovered progression pathways for RCC that perfectly mirrored established biological models previously identified by human experts through manual statistical analysis.
  • Computational Efficiency: Despite its global optimization guarantees, the algorithm runs in $O(|D| \cdot n^2)$ time (where $D$ is the dataset size and $n$ is the number of mutations). This makes it highly computationally feasible for modern datasets.

Limitations and Future Directions

While single HOTs perform exceptionally well on current datasets, the authors note a practical limitation regarding HOT-mixtures. Modeling multiple pathways simultaneously requires significantly larger datasets to achieve high accuracy—sizes that the authors expect will only become commonplace with tomorrow's more cost-efficient, high-throughput sequencing technologies.

Additionally, there are technical parameter constraints. For mathematical tractability during the EM derivation, the authors had to carefully distinguish between "free" and "global" parameters, sometimes forcing a trade-off between model flexibility and computational ease. Moving forward, the team aims to apply these robust, error-tolerant methods to emerging high-throughput mutational data, further illuminating the complex pathways of cancer evolution.

Summary updated

Abstract

Cancer has complex patterns of progression that include converging as well as diverging progressional pathways. Vogelstein's path model of colon cancer was a pioneering contribution to cancer research. Since then, several attempts have been made at obtaining mathematical models of cancer progression, devising learning algorithms, and applying these to cross-sectional data. Beerenwinkel {\em et al.} provided, what they coined, EM-like algorithms for Oncogenetic Trees (OTs) and mixtures of such. Given the small size of current and future data sets, it is important to minimize the number of parameters of a model. For this reason, we too focus on tree-based models and introduce Hidden-variable Oncogenetic Trees (HOTs). In contrast to OTs, HOTs allow for errors in the data and thereby provide more realistic modeling. We also design global structural EM algorithms for learning HOTs and mixtures of HOTs (HOT-mixtures). The algorithms are global in the sense that, during the M-step, they find a structure that yields a global maximum of the expected complete log-likelihood rather than merely one that improves it. The algorithm for single HOTs performs very well on reasonable-sized data sets, while that for HOT-mixtures requires data sets of sizes obtainable only with tomorrow's more cost-efficient technologies.
BibTeX
@inproceedings{tofigh2011global,
  author = {Ali Tofigh and Erik Sjölund and Mattias Höglund and Jens Lagergren},
  title = {{A Global Structural EM Algorithm for a Model of Cancer Progression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2011},
  url = {https://openreview.net/forum?id=rk-jn_Z_bB},
}

Loading related content...

Figure