Dependency networks

Sep 22^nd 2022

BMI/CS 775 Computational Network Biology�Fall 2022

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Plan for this section

• Representing molecular networks as probabilistic models (Sep 13^th)
• Learning directed graphical models: Bayesian networks and variations (Sep 13^th,15^th, 20^th)
• Dependency networks (Sep 22^nd)
• Undirected models and variations (Sep 27^th)
• Recent advances in graph learning (Sep 29^th)
• single cell RNA-seq network inference
• Learning directed models of causality

​

2

Readings

• Huynh-Thu, Vân A., Alexandre Irrthum, Louis Wehenkel, and Pierre Geurts. 2010. “Inferring Regulatory Networks from Expression Data Using Tree-Based Methods.” PLOS ONE 5 (9): e12776+. https://doi.org/10.1371/journal.pone.0012776.
• Greenfield, Alex, Christoph Hafemeister, and Richard Bonneau. 2013. “Robust Data-Driven Incorporation of Prior Knowledge into the Inference of Dynamic Regulatory Networks.” Bioinformatics (Oxford, England) 29 (8): 1060–1067. https://doi.org/10.1093/bioinformatics/btt099.

​

​

​

Let’s start out a bit abstractly

4

…

…

• How can we infer what the graph might be?

​

• What assumptions do we need to make?

​

• What will such a graph capture?

Nodes

Node measurements

Suppose we had a large matrix with nodes of an unobserved graph as rows

and the measurements of node activity as columns.

Goals for today

• Dependency networks
• GENIE3: GEne Network Inference with Ensemble of trees
• Dependency networks with priors
• Evaluation of expression-based network inference methods

Recall the different types of probabilistic graphs

• In each graph type we can assert different conditional independencies
• Correlation networks
• Markov networks
• Gaussian Graphical models
• Dependency networks
• Bayesian networks

​

Dependency network

• A type of probabilistic graphical model
• Approximate Markov networks
• Are much easier to learn from data
• As in Bayesian networks has
• Graph structure
• Parameters
• Unlike Bayesian network
• Can have cyclic dependencies
• Computing a joint probability is harder
• It is approximated with a “pseudo” likelihood.

Dependency Networks for Inference, Collaborative Filtering and Data visualization

Heckerman, Chickering, Meek, Rounthwaite, Kadie 2000

Original motivation of dependency networks

• Introduced by Heckerman, Chickering, Meek, et al 2000
• Often, Bayesian networks can get confusing
• Learned Bayesian networks represent correlation or predictive relationships
• But the directionality of the edges are mistakenly interpreted as causal connections
• (Consistent) Dependency networks were introduced to distinguish between these cases

Dependency network vs Bayesian network

Dependency Networks for Inference, Collaborative Filtering and Data visualization

Heckerman, Chickering, Meek, Rounthwaite, Kadie 2000

​

Bayesian network

Dependency network

Often times, the Bayesian network on the left is read as if “Age” determines “Income”. However, all this model is capturing is that “Age” is predictive of “Income”.

Markov blanket

• Let X be the set of all random variables
• Let B_j denote the Markov Blanket of a variable X_j.
• X_-j denotes all variables in X other than X_j
• Markov blanket of X_j ,B_j,is the subset of X that makes X_j independent of all other variables

​

​

​

• B_j captures all the information about X_j

​

Learning dependency networks

B_j

• Given B_j, X_j is independent of all other variables, X_-j

​

​

• B_j can be estimated by finding the set of variables that best predict X_j
• This requires us to specify the form of P(X_j|B_j)

f_j=P(X_j|B_j)

Entails estimating the Markov blanket of each random variable

X_j

Different representations of f_j=P(X_j|B_j)

• If X_j is continuous
• f_j can be a linear function
• f_j can be a regression tree
• f_j can be an ensemble of trees
• E.g. random forests

​

• If X_j is discrete
• f_j can be a conditional probability table
• f_j can be a conditional probability tree

​

Popular dependency networks implementations

• Learned by solving a set of linear regression problems
• TIGRESS (Haury et al, 2010)
• Uses a constraint to learn a “sparse” Markov blanket
• Uses “stability selection” to estimate confidence of edges
• Inferelator (Bonneau et al, Genome Biology 2005)
• Can handle time course and single time point data
• Handles linear and non-linear regression
• Learned by solving a set of non-linear regression problems
• Non-linearity captured by Regression Tree (Heckerman et al, 2000)
• GENIE3: Non-linearity captured by Random forest (Huynh-Thu et al, 2010)

Goals for today

• Dependency networks
• GENIE3: GEne Network Inference with Ensemble of trees
• Dependency networks with priors
• Evaluation of expression-based network inference methods

Expression data matrix

p Genes

…

…

N Experiments/Time points

Observations (expression levels) of all variables in sample i, x⁽ⁱ⁾

Observations of variable X_j in all N experiments

GENIE3: GEne Network Inference with Ensemble of trees

• Solves a set of regression problems
• One per random variable
• Minimizes the prediction error per variable X_j

​

​

• Uses an Ensemble of regression trees to represent f_j
• Models non-linear dependencies
• Outputs a directed cyclic graph with a confidence of each edge
• Directionality means “good predictor”
• Focus on a ranking over edges rather than graph structure and parameters
• Rank is determined by confidence

Inferring Regulatory Networks from Expression Data Using Tree-Based Methods Van Anh Huynh-Thu, Alexandre Irrthum, Louis Wehenkel, Pierre Geurts, Plos One 2010

A very simple regression tree for two variables

X₂

X₃

e₁

e₂

X₂ > e₁

X₂ > e₂

YES

NO

NO

YES

X₃

The tree specifies X₃ as a function of X₂

Interior nodes

Leaf nodes

Prediction of X_j using a single tree

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction is the mean at each leaf node

Prediction of X_j using a single tree

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction is the mean at each leaf node

Prediction of X_j using a single tree

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction is the mean at each leaf node

Prediction of X_j using a single tree

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction is the mean at each leaf node

Prediction of X_j using a single tree

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction is the mean at each leaf node

Algorithm for learning a regression tree

• Input: dataset D, variable X_j, candidate predictors X_-j of X_j
• Output: Tree T
• Initialize T to a leaf node, estimated from all samples of X_j. Assign all samples to leaf node

Algorithm for learning a regression tree

Quantifying a split on the tree

The set of samples in the left node

The set of samples in the right node

S_left and S_right are sets of samples obtained by testing X_i for a particular split s

One iteration of regression tree learning

• Let X={X₁,X₂,X₃,X₄}
• Assume we are searching for the neighbors of X₃ and it already has two neighbors X₁ and X₂

X_1, X_2, X₄ will all be considered as candidate splits using the examples at each current leaf node

One iteration of regression tree learning

• If we split on X₄, then we will have a new neighbor.

​

Convergence criteria

• Minimum number of examples at a leaf node
• Depth of a tree
• Error tolerance

An Ensemble of trees

• A single tree is prone to “overfitting”
• Instead of learning a single tree, ensemble models make use of a collection of trees

​

Prediction using an Ensemble of Trees

​

​

​

​

​

​

​

​

​

​

……

tree₁

tree_T

x_-j

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction using an Ensemble of Trees

……

tree₁

tree_T

x_-j

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction using an Ensemble of Trees

​

​

​

​

​

​

​

​

​

​

……

tree₁

tree_T

x_-j

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction using an Ensemble of Trees

……

tree₁

tree_T

x_-j

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Prediction using an Ensemble of Trees

​

​

​

​

​

​

​

​

​

• Prediction is

​

……

tree₁

tree_T

x_-j

x_-j

Taken from ICCV09 tutorial by Kim, Shotton and Stenger: http://www.iis.ee.ic.ac.uk/~tkkim/iccv09_tutorial

Expression data matrix for GENIE3

p Genes

N Experiments/Time points etc

Observations (expression levels) of all variables in sample i

Observations of X_j in all m experiments

GENIE3 will use the transpose of this data matrix

N Experiments

p Genes

Observations (expression levels) of all variables in sample i

GENIE3 algorithm sketch

Figure from Huynh-Thu et al., 2010

Predictor ranking

GENIE3 algorithm sketch

• For each X_j, generate learning samples of input/output pairs
• LS_j={(x_-j^k,x_j^k), k=1..N}
• On each LS_j learn f_j to predict the value of X_j
• f_j is an ensemble of regression trees
• Estimate importance w_ij for all genes i ≠ j
• w_ij quantifies the confidence of the edge between X_i and X_j
• Associated with the decrease in variance of X_j when X_i is included in f_j
• Generate a global ranking of edges based on each w_ij

Learning f_j in GENIE3

• Uses two types of Ensembles to represent the f_j:
• Random forest or Extra Trees
• Learning the Random forest
• Generate M=1000 bootstrap samples and learn 1000 trees, one from each sample
• At each node to be split, search for best split among K randomly selected variables
• K was set to p-1 or (p-1)^1/2, where p is the number of regulators/parents
• Learning the Extra-Trees
• Learn 1000 trees
• Each tree is built from the original learning sample
• At each node, the best split is determined among K random splits, each split determined by randomly selecting one input (without replacement) and a threshold

​

​

​

​

​

Computing the importance weight of a predictor

• Importance is computed at each interior node
• Remember each predictor can show up multiple times as interior nodes
• For an interior node, importance is given by the reduction in variance when splitting on that node

Interior node

Set of data samples that reach this node

#S: Size of the set S

Var(S): variance of the output variable x_j in set S

S_t: subset of S when a test at N is true

S_f: subset of S when a test at N is false

Computing the importance weight of a predictor

• For a single tree the overall importance is a sum over all points in the tree where this node is used to split
• For an ensemble the importance is averaged over all trees
• To avoid bias towards highly variable genes, normalize the expression genes to all have unit variance

Goals for today

• Dependency networks
• GENIE3: GEne Network Inference with Ensemble of trees
• Dependency networks with priors
• Evaluation of expression-based network inference methods

Classes of methods for incorporating priors

• Parameter prior based approaches
• Inferelator (Greenfield et al., Bioinformatics 2013)
• Lirnet (Lee et al., Plos computational biology 2009)
• Structure prior based approaches
• Dynamic Bayesian network (Hill et al., Bioinformatics, 2012, Werhli et al., 2007)
• Physical module networks (Novershtern et al., Bioinformatics 2011)
• MERLIN-P (Siahpirani et al.,2016)

​

​

Overview of the Inferelator algorithm

• Based on linear regression models
• Handles time series and steady state data
• Prior is incorporated at the edge weight using two strategies
• Modified Elastic Net
• Bayesian Best Subset Regression

​

Greenfield et al. 2013, Bonneau et al. 2007

Modeling the relationship between regulator and target in Inferelator

• Time series

​

​

​

• Steady state

Network inference: Estimate coefficients

Number of genes

Number of samples

Two approaches to integrate prior graph structure

• Modified Elastic Net (MEN)
• Regularized regression-based framework

​

• Bayesian Best Subset Regression (BBSR)
• Probabilistic framework with exhaustive search on regulator sets

Regularized regression

• The regularized regression framework can be generally described as follows:

Depending upon f we may have different types of regularized regression frameworks

Regularization term

Regularized regression

• takes the form of some norm of
• L1 norm

​

​

• L2 norm

​

​

• Elastic net (Zou & Hastie 2005)

​

​

Elastic net regression

• Elastic net regression objective for the i^th gene

​

​

​

• Which can be equivalently written as

Minimize

Subject to

Estimate via cross validation

L1 norm

L2 norm

Modified Elastic Net (MEN)

• The modification to Elastic net

​

Set this <1 so that if there is a prior edge between x_p->y_i, the regression coefficient will be penalized less

Inferelator workflow

GENIE3 vs Inferelator

GENIE3

• Non-linear regression model
• Ensemble of trees: Random Forests/Extra Trees

​

Inferelator

• Linear regression model
• Ensemble of linear regression models
• Incorporates prior information

Goals for today

• Dependency networks
• GENIE3: GEne Network Inference with Ensemble of trees
• Dependency networks with priors
• Evaluation of expression-based network inference methods

Evaluating the network

• Assessing confidence
• Area under the precision recall curve
• F-score
• Do gene modules participate in coherent function?
• Can the network predict expression in a new condition?

Assessing confidence in the learned network

• Typically the number of training samples is not sufficient to reliably determine the “right” network
• One can however estimate the confidence of specific features of the network
• Graph features f(G)
• Examples of f(G)
• An edge between two random variables
• Order relations: Is X, Y’s ancestor?

How to assess confidence in graph features?

• What we want is P(f(G)|D), which is

​

​

• But it is not feasible to compute this sum

​

• Instead we will use a “bootstrap” procedure

​

Bootstrap to assess graph feature confidence

• For i=1 to m
• Construct dataset D_i by sampling with replacement N samples from dataset D, where N is the size of the original D
• Learn a graphical model {G_i,Θ_i}
• For each feature of interest f, calculate confidence

Bootstrap/stability selection

57

57

Expression data

Final inferred�network

Output

Input

Bootstrap/stability selection

58

58

Expression data

Final inferred�network

Output

Input

Does the bootstrap confidence represent real relationships?

• Compare the confidence distribution to that obtained from randomized data
• Shuffle the columns of each row (gene) separately
• Repeat the bootstrap procedure

​

genes

Experimental conditions

Slide credit Prof. Mark Craven

Bootstrap-based confidence differs between real and random data

f

f

Random

Real

Friedman et al 2000

Example of a high confidence sub-network

One learned Bayesian network

Bootstrapped confidence Bayesian network: highlights a subnetwork associated with yeast mating pathway. Colors indicate genes with known functions.

Nir Friedman, Science 2004

Area under the precision recall curve (AUPR)

• Assume we know what the “right” network is
• One can use Precision-Recall curves to evaluate the predicted network
• Area under the PR curve (AUPR) curve quantifies performance

​

Precision=

# of correct edges

# of predicted edges

Recall=

# of correct edges

# of true edges

F-score

• Assume we know what the “right” network is
• Suppose your predicted network has a N edges.
• Selected based on sorting edges by confidence/strength of interaction and getting the top X edges

​

Precision (P) =

# of correct edges

# of predicted edges

Recall (R)=

# of correct edges

# of true edges

F-score=

2*P*R

P+ R

Experimental datasets to assess network structure for gene regulatory networks

• Sequence specific motifs

​

​

​

• ChIP-chip and ChIP-seq

​

​

​

​

• Factor knockout followed by whole-transcriptome profiling

​

Siahpirani et al., 2016

AUPR based performance comparison

Results are for E. coli transcriptional regulatory network

DREAM: Dialogue for reverse engineeting assessments and methods

Community effort to assess regulatory network inference

DREAM 5 challenge

Previous challenges: 2006, 2007, 2008, 2009, 2010

Marbach et al. 2012, Nature Methods

Where do different methods rank?

Marbach et al., 2012

Community

Random

These approaches were mostly per-gene

What happens when one adds noisy priors?

Low and high in BBSR and MEN means less dense or more dense

High noise regime

Do priors help?

Siahpirani & Roy, Nucleic Acids Res, Volume 45, Issue 4, 28 February 2017, Page e21, https://doi.org/10.1093/nar/gkw963

Evaluation on the yeast regulatory network

Take away points

• Dependency networks learn graph structures by solving a set of regression problems
• Easier to learn than Bayesian network, but harder to reason with joint probabilities
• In practice perform better than Bayesian networks
• Common Dependency network inference algorithms
• GENIE3
• Inferelator
• Dependency networks + priors
• Inferelator: Modified Elastic Net
• MERLIN-P
• Addition of priors was beneficial in yeast