Transcriptional regulation play an important role in every cellular decision. Gaining an understanding of the dynamics that govern how a cell will respond to diverse environmental cues is di cult using intuition alone. We introduce logic-based regulation models based on state-of-the-art work on statistical relational learning, to show that network hypotheses can be generated from existing gene expression data for use by experimental biologists.
Transcriptional regulation refers to how proteins control gene expression in the cell. Many major cellular decisions involve changes in transcriptional regulation. Thus, gaining insight into transcriptional regulation is important not just for understanding the fundamental biological processes, but also will have deep practical consequences in elds such as the medical sciences. With the advent of high-throughput technologies and advanced measurement techniques molecular biologists and biochemists are rapidly identifying components of transcriptional networks and determining their biochemical activities. Unfortunately, understanding these complex multicomponent networks that govern how a cell will respond to diverse environmental cues is di cult using intuition alone.
In this work, we aim at building probabilistic logical models thatwould uncover the structure and dynamics of such networks and how they regulate their targets.
Despite the challenge of inferring genetic regulatory networks from gene
expression data, various computational models have been developed for regulatory
network analysis. Examples include approaches based on logical gates [
Our main contribution is in introducing a model that combines the two
approaches. Our approach is based on the probabilistic logic programming
language ProbLog [
Given time-series gene expression data, we want to choose the probability
parameters that best describe the data. Our approach is to reduce this problem
to an optimization problem, and use a gradient ascent algorithm to estimate
a local solution [
Related Work Logic-based modeling is seen as an approach lying midway
between the complexity and precision of di erential equations on one hand and
data-driven regression approaches on the other[
Despite the di culty of deciphering genetic regulatory networks from
microarray data, numerous approaches to the task have been quite successful.
Friedman et al. [
The methods above can represent the dependence between interacting genes,
but they cannot capture causal relationships. In our previous work [
Recently, there has been interest in combining logical and probabilistic
representations within the framework of Statistical Relational Learning [
Given the example in Fig 1, ProbLog allows one to answer several queries, such as what is the most likely path between two nodes, and what is the total probability that there is a path between two nodes. The algorithm takes advantage of independence between probabilistic facts.
Note that computing the probability is not simply the sum if di erent paths have a common edge. As an example, consider P r(ae). The path abde shares the edge de with acde, and the edge ab with abe. Summing these three paths would count two edges twice.
Kimmig and de Raedt proposed an e ective solution to this problem. The idea is that probability can be computed as a sum if the paths do not share edges. This can be obtained by selecting an edge (or fact), and splitting into the case where the edge is true and the case where the edge is false. The process can be repeated recursively until we run out of facts to split. Kimmig and de Raedt's key observation is that this idea is indeed the same one that is used to construct binary decision diagrams (BDDs): the total probability can be obtained by generating a BDD from the proofs.
Binary decision diagrams provide a very e cient implementation for
probability computation over small and medium graphs. Unfortunately, they do not
scale to larger graphs with thousands of nodes. In this case, ProbLog
implementations rely on approximated solutions, either Monte Carlo methods or often by
approximating the total probability by the probability of the best k queries [
We obtained time-series gene expression data from Lee et al. [
Our experiments aim for a more detailed picture of the learned network by using the temporal nature of the data. The output generated is a weighted, directed gene network, but nodes are connected as a gated network: { AND: two promoter genes need to be active in order to activate a gene, as shown in the graph. We also show the ProbLog code for the temporal model: active(G3,T1,Z) :next_step(T0,T1), and(G1,G2,G3), active(E,T0,G1), active(E,T0,G2). { OR: either promoter gene needs to be active in order to activate a gene, as shown in the graph. We also show the corresponding ProbLog code for the temporal model.
active(G3,T1,Z) :next_step(T0,T1), or(G1,G2,G3), active(E,T0,G1). active(G3,T1,Z) :next_step(T0,T1), or(G1,G2,G3), active(E,T0,G2). { XOR: one promoter gene needs to be active and one repressor gene needs to be inactive in order to activate a gene, as shown in the graph. active(G3,T1,Z) :next_step(T0,T1), xor(G1,G2,G3), active(E,T0,G1), not_active(E,T0,G2).
This is the only case where we allow the possibility of negative regulation. { SINGLE: a unique promoter gene regulates the target gene. active(G2,T1,Z) :next_step(T0,T1), single(G1,G2), active(E,T0,G1).
We use two di erent forms of temporal data: expression level (E), and variation ( ). We experimented with three di erent approaches: (1) Level in uences variation (LV). (2) Variation in uences variation (VV). (3) Level in uences level (LL).
One important advantage of the approach is that it allows us to implement soft constraints on the probability distribution. These constraints are implemented by saying that satisfying some rule must have probability 1 or 0. In our experiments, we implement constraints saying that a gene must be explained by a single rule. Two example constraints for OR are of the form: The next constraint says that there must be a single set of parents for a gene de ned with the LV _ rule: !
Et(G1) _ Et(G2) )
^ Et(G3) _ Et(G4) ) t+1(G) t+1(G)
G1 = G3 ^ G2 = G4 :( Et(G1) _ Et(G2) ) )
Et(G3)
^ Et(G4) ) t+1(G) t+1(G)
The second constraint ensures that we cannot use two rules of di erent types at the same time: In practice, we must be careful not to ood the system with soft constraints. In our experiment we implemented one joint soft constraint per gene. 4
Learning regulatory networks from gene expression is a hard problem. Data is noisy and relationships between genes highly complex. We present a statistical relational approach to modeling pathways. Our approach allows us to design a coarser and a more ne grained model, based on probabilistic gates.
We plan to continue improving the model quality and experiment with new data. Speci cally, we would like to experiment with implementing a regression based approach, as it ts our framework naturally. Last, but not least, we would like to investigate how to reduce the number of parameters in the model by exploiting strong correlations between gene expression.
This work is nanced by the ERDF European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) FCOMP-01-0124-FEDER-010074 and by National Funds through the FCT Fundac~ao para a Ci^encia e a Tecnologia (Portuguese Foundation for Science and Technology) within project HORUS (PTDC/EIA-EIA/100897/2008) and by the US 760 Department of Energy (DOE) Great Lakes Bioenergy Research Center (DOE BER 761 O ce of Science DE-FC02-07ER64494).