Biomedical Engineering Reference
In-Depth Information
At the same time, biologists may have prior knowledge of the GRN, gained
through observations of gene expression or pathway information. These observations
provide insight into the GRN state and, in turn, the gene regulation function. Such
observations can be complete or partial, and may curated from different sources or
databases.
The problem then is how to determine the gene function and create a complete and
functional GRN model that matches the predictor set and gene expression observa-
tions. Assuming a Boolean network model [
2
] for the GRN, the gene expression for
a single gene is a binary value (expressed or not expressed) and the gene regulation
function is represented as a Boolean logic function. For each time step, all genes are
assumed to update at the same time, and the value of all genes at a particular time
step represents a state in the GRN at that time step. In this discussion, we present an
efficient approach to assign a logic function to each gene, given a predictor set, such
that the gene expression observation are matched.
In this work, which was first reported in [
3
], we leverage mathematical tools from
the field of logic synthesis in digital circuit design. Logic synthesis techniques have
been recently applied to genomics in [
4
], [
5
], [
6
], [
7
], [
8
]. In order to determine gene
function, [
4
] uses Karnaugh maps (K-maps) to explicitly generate two-level logic
functions based on pathway information for a Boolean network.
In this chapter, we develop a general Boolean satisfiability (SAT) based implicit
method to select logic functions and generate BNs that match a predictor set and gene
expression observations. In our method, all possible logic functions are implicitly
explored for each gene, based on the predictor set, with a multiplexer (MUX) select-
ing one of these functions for each gene. The resulting logical circuit is duplicated,
and each copy is assigned one of the observed gene expression observations. All
copies (now represented as a SAT formula) are then solved in parallel by sharing
the MUX selectors among the copies, and using a SAT-solver to select a function
for each gene, and generate a BN that satisfies all input observations. Where more
than one valid selection exists, our method generates a family of satisfying Boolean
networks.
3.2
Previous Work
One commonly used representation scheme for GRNs is the Boolean network
(BN) [
2
]. In this model, genes are binary valued (expressed or not expressed), and
can act on (regulate) other genes. Regulation is represented using Boolean functions.
In the BN, each gene takes its inputs (the values of its regulatory genes) and produces
a new output value according to its Boolean function. All genes in the BN update
synchronously, and the values of the genes at a given point of time represent the state
of the BN at that time. In reality, gene expression is continuous; however a discrete
model like BN is preferred because many genes exhibit switch-like behavior [
9
] and
