iterative Random Forests to discover predictive and stable high-order interactions

Sumanta Basu, Karl Kumbier, James B. Brown, Bin Yu

Abstract

Genomics has revolutionized biology, enabling the interrogation of whole transcriptomes, genome-wide binding sites for proteins, and many other molecular processes. However, individual genomic assays measure elements that interact in vivo as components of larger molecular machines. Understanding how these high-order interactions drive gene expression presents a substantial statistical challenge. Building on Random Forests (RF), Random Intersection Trees (RITs), and through extensive, biologically inspired simulations, we developed the iterative Random Forest algorithm (iRF). iRF trains a feature-weighted ensemble of decision trees to detect stable, high-order interactions with same order of computational cost as RF. We demonstrate the utility of iRF for high-order interaction discovery in two prediction problems: enhancer activity in the early Drosophila embryo and alternative splicing of primary transcripts in human derived cell lines. In Drosophila, among the 20 pairwise transcription factor interactions iRF identifies as stable (returned in more than half of bootstrap replicates), 80% have been previously reported as physical interactions. Moreover, novel third-order interactions, e.g. between Zelda (Zld), Giant (Gt), and Twist (Twi), suggest high-order relationships that are candidates for follow-up experiments. In human-derived cells, iRF re-discovered a central role of H3K36me3 in chromatin-mediated splicing regulation, and identified novel 5th and 6th order interactions, indicative of multi-valent nucleosomes with specific roles in splicing regulation. By decoupling the order of interactions from the computational cost of identification, iRF opens new avenues of inquiry into the molecular mechanisms underlying genome biology.

Introduction

In the field of genomics, biological processes are rarely driven by a single protein or gene acting in isolation. Instead, they are governed by "molecular machines"—complex assemblies where multiple transcription factors (TFs) and histone modifications interact. Statistically, identifying these interactions is a significant challenge. Most traditional methods focus on pairwise relationships, but biological reality often involves high-order interactions (e.g., 5-way or 6-way combinations). A brute-force search for such interactions leads to a "combinatorial explosion," making it computationally infeasible. Furthermore, genomic data is notoriously noisy, making it difficult to distinguish true biological interactions from random correlations. The iterative Random Forest (iRF) algorithm was developed to provide a computationally scalable and statistically stable method for discovering these complex relationships.

The iRF Algorithm

The iRF algorithm identifies stable, high-order interactions with a computational cost comparable to a standard Random Forest. It consists of three main stages:

  1. Iterative Feature Weighting: The algorithm starts by training a standard Random Forest. It calculates the "Gini importance" of each feature and uses these values to weight features in the next iteration. This process "zooms in" on the most relevant features, performing a soft dimensionality reduction that encourages the model to use a consistent set of important features.
  2. Generalized Random Intersection Trees (RIT): To find interactions without an exhaustive search, iRF examines the decision paths already built by the Random Forest. It uses the RIT algorithm to identify sets of features that frequently co-occur on paths leading to specific predictions. This approach decouples the order of the interaction from the computational cost.
  3. Stability Bagging: To ensure that discovered interactions are reproducible and not artifacts of a specific data sample, iRF uses an outer layer of bootstrapping. It runs the entire process multiple times on different subsets of the data and assigns a "stability score" based on how often an interaction is recovered.
The iRF workflow: (1) Iterative re-weighting of RF, (2) Generalized RIT on decision paths, and (3) Bagged stability scores.

Experimental Validation

The authors validated iRF using biologically inspired simulations and real-world genomic datasets from Drosophila and human cell lines. In simulations, iRF successfully recovered known "ground truth" interactions of up to 8th order.

In the Drosophila enhancer activity study, iRF identified 20 pairwise transcription factor interactions as stable. Remarkably, 80% of these had been previously documented as physical interactions in the literature. Beyond pairwise interactions, iRF identified a stable 3rd-order interaction involving the factors Zelda (Zld), Giant (Gt), and Twist (Twi), suggesting complex regulatory logic.

In human-derived cells, iRF was used to predict alternative splicing. It re-discovered the central role of H3K36me3 and identified novel 5th and 6th-order interactions involving RNA Pol II and various histone marks. This suggests a highly complex, multi-valent "chromatin code" for splicing regulation where many marks act in concert.

Stability scores for discovered interactions in Drosophila. Red dots indicate order-2 interactions, while blue dots indicate order-3.

Discussion and Impact

A core philosophy of this work is the "Stability Principle": for a scientific result to be meaningful, it must be stable to small perturbations in the data. iRF bakes this directly into the algorithm via bagging, providing a robust framework for hypothesis generation in "Big P, Small N" scenarios common in genomics.

Unlike previous benchmarks like Rulefit3, which grow exponentially in complexity as they look for higher-order interactions, iRF’s computational cost grows linearly with the number of features. By identifying biological "AND" gates—where a process only activates if multiple specific factors are present—iRF opens new avenues for understanding the molecular mechanisms underlying genome biology. Future work may refine the algorithm by moving toward "local" importance measures to find interactions specific to rare cell types or conditions.

Summary updated

Abstract

Abstract Genomics has revolutionized biology, enabling the interrogation of whole transcriptomes, genome-wide binding sites for proteins, and many other molecular processes. However, individual genomic assays measure elements that interact in vivo as components of larger molecular machines. Understanding how these high-order interactions drive gene expression presents a substantial statistical challenge. Building on Random Forests (RF), Random Intersection Trees (RITs), and through extensive, biologically inspired simulations, we developed the iterative Random Forest algorithm (iRF). iRF trains a feature-weighted ensemble of decision trees to detect stable, high-order interactions with same order of computational cost as RF. We demonstrate the utility of iRF for high-order interaction discovery in two prediction problems: enhancer activity in the early Drosophila embryo and alternative splicing of primary transcripts in human derived cell lines. In Drosophila , among the 20 pairwise transcription factor interactions iRF identifies as stable (returned in more than half of bootstrap replicates), 80% have been previously reported as physical interactions. Moreover, novel third-order interactions, e.g. between Zelda (Zld), Giant (Gt), and Twist (Twi), suggest high-order relationships that are candidates for follow-up experiments. In human-derived cells, iRF re-discovered a central role of H3K36me3 in chromatin-mediated splicing regulation, and identified novel 5th and 6th order interactions, indicative of multi-valent nucleosomes with specific roles in splicing regulation. By decoupling the order of interactions from the computational cost of identification, iRF opens new avenues of inquiry into the molecular mechanisms underlying genome biology.
BibTeX
@inproceedings{basu2018iterative,
  author = {Sumanta Basu and Karl Kumbier and James B. Brown and Bin Yu},
  title = {{iterative Random Forests to discover predictive and stable high-order interactions}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2018},
  doi = {10.1073/pnas.1711236115},
}
Figure