Dependency networks

Sep 23^rd 2021

BMI 826-23 Computational Network Biology�Fall 2021

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Plan for this section

• Overview of network inference (Sep 21^st)
• Bayesian networks (Sep 21^st, Sep 23rd)
• Dependency networks (Sep 23^rd)
• Integrative inference of gene regulatory networks (Sep 28^th, Sep 30^th)
• Inference of regulatory networks from single cell datasets (Oct 5^th)

​

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.

​

​

Goals for today

• Dependency networks
• GENIE3: GEne Network Inference with Ensemble of trees
• 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”.

Learning dependency networks

B_j

• Let B_j denote the Markov Blanket of a variable X_j.
• X_-j denotes all variables other than X_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
• 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)
• Inferelator (Bonneau et al, Genome Biology 2005)
• Can handle time course and single time point data
• Non-linear regression is done using a logistic transform
• Handles linear and non-linear regression

Goals for today

• Dependency networks
• GENIE3: GEne Network Inference with Ensemble of trees
• 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

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
• If we split on X₄, then we will have a new neighbor.

​

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
• If we split on X₄, then we will have a new neighbor.

​

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
• 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 then 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
• Evaluation of expression-based network inference methods

Evaluating the network

• Assessing confidence
• Area under the precision recall curve
• F-score
• Do modules or target sets of genes 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

44

44

Expression data

Final inferred�network

Output

Input

Bootstrap/stability selection

45

45

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

Some comments about expression-based network inference methods

• We have seen multiple types of algorithms to learn these networks
• Per-gene methods (learn regulators for individual genes)
• Sparse candidate, GENIE3, ARACNE, CLR
• Per-module methods
• Module networks: learn regulators for sets of genes/modules
• Other implementations of module networks exist
• LIRNET: Learning a Prior on Regulatory Potential from eQTL Data (Su In Lee et al, Plos genetics 2009, http://www.plosgenetics.org/article/info%3Adoi%2F10.1371%2Fjournal.pgen.1000358)
• LeMoNe: Learning Module Networks (Michoel et al 2007, http://www.biomedcentral.com/1471-2105/8/S2/S5)
• Methods that combine per-gene and per-module (MERLIN)
• Methods differ in
• how they quantify dependence between genes
• Higher-order or pairwise
• Focus on structure or structure & parameters
• Expression alone is not enough to infer the structure of the network
• Integrative approaches that combine expression with other types of data are likely more successful (next lectures)

References

• Markowetz, Florian and Rainer Spang. "Inferring cellular networks-a review.." BMC bioinformatics 8 Suppl 6 (2007): S5+.
• N. Friedman, M. Linial, I. Nachman, and D. Pe'er, "Using bayesian networks to analyze expression data," Journal of Computational Biology, vol. 7, no. 3-4, pp. 601-620, Aug. 2000. [Online]. Available: http://dx.doi.org/10.1089/106652700750050961
• Dependency Networks for Inference, Collaborative Filtering and Data visualization Heckerman, Chickering, Meek, Rounthwaite, Kadie 2000
• Inferring Regulatory Networks from Expression Data Using Tree-Based Methods Van Anh Huynh-Thu, Alexandre Irrthum, Louis Wehenkel, Pierre Geurts, Plos One 2010
• D. Marbach et al., "Wisdom of crowds for robust gene network inference," Nature Methods, vol. 9, no. 8, pp. 796-804, Jul. 2012. [Online]. Available: http://dx.doi.org/10.1038/nmeth.
• R. De Smet and K. Marchal, "Advantages and limitations of current network inference methods." Nature reviews. Microbiology, vol. 8, no. 10, pp. 717-729, Oct. 2010. [Online]. Available: http://dx.doi.org/10.1038/nrmicro2419