In order to understand complex biological networks and pathways, we need to investigate global structures instead of individual behaviors since there are interactions and associations between genes. Due to the invention of high throughput technology, genome-wide expression profiles can be measured simultaneously 
. However, it is still a great challenge to identify complex biological networks from genome-wide data because the number of gene interactions is huge 
. In recent years, there has been a significant progress in research concerning genetic network models and network reconstruction problems.
Clustering and dimension reduction are important methods for grouping genes that have similar expression profiles 
. In the framework of clustering, it is important to define the degree of similarity between genes. By the method of clustering, we can group genes that have similar expressions. However, we still cannot find the causal relationship between genes. Hence, apart from the relationship of similarity, we will also have to consider another causal relationship between genes.
There have been many methods proposed in the literature to tackle the problem of genetic regulatory network reconstruction. For instance, the steady state approach have been used to model gene regulatory networks 
. In addition, the Bayesian network model is an important technique that has been studied extensively in the past two decades 
. A Bayesian network is a directed acyclic graph (DAG) comprised of two components. The first component is comprised of nodes that correspond to a set of variables and a set of directed edges between variables with Markov properties. The second component describes a conditional distribution for each variable given its parents in the graph. Recently, Bayesian network models have been applied to analyze microarray expression and biological data 
. However, Bayesian network algorithms have limitations when dealing with large-scale gene regulatory networks because of their complex modeling structure 
. Although algorithms for reconstructing Bayesian networks have already been developed 
, the algorithms’ computational costs remain a concern for the searching of all potential network structures on the genome-wide expression data.
Therefore, we are considering a simpler model: Boolean networks, which have been studied extensively in a variety of contexts. Boolean networks 
can effectively explain the dynamic behaviors of living systems. Moreover, for large-scale gene regulatory networks, Kim et al. 
have used Boolean network with chi-square test on the yeast cell cycle microarray gene expression data sets. The chaos and attractors of Boolean network are also discussed widely from the aspect of power spectrum 
. Recently, Boolean network also have been used as a discrete model for the lac
Boolean networks were originally introduced by Kauffman, and received attention in the studies of gene regulatory networks because of their simple structures 
. In a Boolean network model, nodes represent the gene expression states. The status of a gene is quantized to one of the two states: on or off, representing a gene as active or inactive respectively. The wiring of rules between nodes in the graph represents a functional link between genes and determines the expressions of target genes after giving a series of input genes. Under the structure of Boolean networks, the target gene is determined by a set of genes with specific rules. For each gene, if the indegree (i.e., the number of input genes to each gene) is bounded by a constant
pairs of state transition are necessary and sufficient to reconstruct the original network with
. However, Boolean networks have been criticized for their deterministic nature. The assumption that every affected gene would be expressed immediately at the next time step may be unsound.
Another point of view of constructing genetic network is to focus on the indication the pairwise relationships between genes. Most of the works is to find the gene-pairs with similarity relationship 
. The similarity of a gene-pair represents the two genes with the same expression or opposite expression. In 2005, Li and Lu proposed directed acyclic Boolean network and the statistical reconstruction method of SPAN to infer the pair wise relations of every element 
. The proposed method can reconstruct Boolean networks from noisy array data by assigning an s-p-score for every pair of genes. In the study, they proposed another relationship between two genes: relationship of prerequisite under the Boolean network model. If gene
is a prerequisite for gene
, then the “on” status of gene
is necessary for the “on” status of gene
. Boolean implication network, with the similar aspect, investigated all Boolean implication between pairs of gene for large scale genome microarray datasets 
. Following the model, Wang et al.
proposed a two step counting approach for constructing biological pathways with Boolean network. However, most of these methods only consider pair wise relationship in order to decrease the time complexity. Therefore, if the structure of network is a combination of a set of genes to affect another gene, the algorithms will lose some information and rules in the genetic network reconstruction.
In this study, we will consider a much more generalized model by combining the structure of the above two models. If a Boolean function with one or several genes is a prerequisite for a target gene, then the induction of the Boolean function with input genes is necessary for the expression of the target gene. Hence, the target will be influenced by the Boolean function with several input genes. However, the induction of the Boolean function may not activate the target gene immediately, but at a future time. Therefore, the target gene may not have been influenced right now and we will treat these relationships as time delay affection. In this study, we will infuse these additional relationships for more generalized systems.
Boolean networks were introduced by Kauffman (1969) forty years ago to represent genetic regulatory networks. First, we will review the definition of a Boolean network. A Boolean network
is a directed graph consisting of two components: a set of nodes
that corresponds to genes, and a list of Boolean functions
that corresponds to the rule of interaction and combination of several genes. For every node
, its expression is simplified to two levels: on and off, representing a gene as active or inactive. For every Boolean function
specified input nodes
are assigned to the node
in the graph and represent the rules of regulatory mechanisms between genes. The expression of a gene is determined by the expression of the gene directly affecting it with a Boolean function. Therefore, the state of each node
is determined by the Boolean function
For each node
, the gene expression state at time
is assumed to take either 0 (not-expressed) or 1 (expressed) and is expressed as
. In a Boolean network, every gene expression profile at time
is completely determined by the expression profile of a set of genes
and the corresponding Boolean function
. That is, we can write
For convenience, we converted the Boolean network
to the wiring diagram
(See ) 
. For each node
are the input nodes assigned to
. Then we construct an additional node
and connected the edge from
. That is, the set of
represents the gene expression profile at time
and the set of
corresponds to the gene expression profile at time
. Hence we can treat the set of
as the input values and the set of
as the corresponding output values. Therefore, the output values of
are determined by
Boolean network G(V,F), wiring diagram G′(V′,F′) and its input/output.
The Structure of Time Delay Boolean Network
In the previous subsection, we found that given the values of the node (
) at time
, the expressions at time
will be updated immediately by specific Boolean function (
). That is, for every gene
, if the expression profile of a set of genes
and the corresponding Boolean function
is observed, the gene expression of
is determined by
. However, in real genetic regulatory situations, the deterministic system has been criticized due to the existence of misclassification error and noise. In addition, some of the gene expression may result in time delay when the gene is influenced by one or several input genes. That is, the induction of Boolean function may not activate the target gene immediately, but in the future. Hence, it would have been much more flexible to use a non-deterministic network system. In this subsection, we will consider two relationships between the Boolean function and the target gene instead of the deterministic relation.
First, we will introduce the structure of time delay Boolean networks. Suppose there are
in a Boolean network. For any elements
with specific Boolean function
, we have two kinds of pair wise relationship: prerequisite and similarity. We say that a Boolean function
is the prerequisite for the target gene
, if the on-status of Boolean function at time t is necessary for the on-status of gene
. This relationship is denoted by
. In other words, if the Boolean function
is not active at time
will be inactive at time
. If it does not cause confusion, we will omit the notation of
and input genes as denoted by
. Moreover, for every gene
, we use
as its dual (from 0 to 1, or from 1 to 0) in this paper. Therefore, for any Boolean function and target gene with a prerequisite relationship there are a total of two possible relationships:
. In this model, we do not consider the situation of a dual of Boolean function prerequisite to the target gene, that is
. Since for any Boolean function whose dual is a prerequisite to the target gene, there must exist another Boolean function that is a prerequisite to the target gene. For instance, if
. Therefore, for the prerequisite relationship, we only consider the Boolean function that is a prerequisite to target gene and the dual of target gene.
The other type of relationship between Boolean function and target gene is similarity. We say that the Boolean function
and target gene
are similar if the status of the Boolean function and the status of the target gene are in the same expression, and we denoted this by fi~vi
. In the same way, we do not consider the situation of Boolean function similar to the dual of target gene such as fi~
in this study. Since if there is one Boolean function that is similar to the dual of target gene, there must exist another Boolean function that is similar to the target gene.
In the diagram, if a Boolean function
is a prerequisite to
, we draw a directed arrow from the vertex
is similar to
, we use an undirected line to connect
In the model of time delay Boolean network we proposed, the output of the gene expression is not completely determined by the input state and Boolean function. The output expression may have more than one possible result in the time delay Boolean network. We illustrate the above construction by an example in . It has three elements, one similarity and two prerequisite relationships. The possible outputs for every input state are listed in the right part of the graph. If we knew the network structure, some of the inputs would have more than one possible output expression in the time delay Boolean network.
One example of time delay Boolean network and its input/output.