%0 Journal Article
%T Detecting controlling nodes of boolean regulatory networks
%A Steffen Schober
%A David Kracht
%A Reinhard Heckel
%A Martin Bossert
%J EURASIP Journal on Bioinformatics and Systems Biology
%D 2011
%I BioMed Central
%R 10.1186/1687-4153-2011-6
%X The reconstruction of genetic regulatory networks using (possibly noisy) expression data is a contemporary problem in systems biology. Modern measurement methods, for example, the so-called microarrays, allow measuring the expression levels of thousands of genes under particular conditions. A major problem is to predict the structure of the underlying regulatory network. The overall goal is to understand the processes in cells, for example, how cells execute and control operations required for the functions performed by the cell. In the Boolean model, this implies that based on a given set of observed state-transition pairs (samples), the Boolean functions attached to each node need to be identified. In general, this problem is quite hard, due to the large number of possible Boolean functions. First results for the noiseless case appeared 1998 in the work of Liang et al. [1]. Their Reverse Engineering Algorithm (REVEAL) tries in a first step to find the controlling nodes of each node by estimating the mutual information between possible variables and the regulatory function's output. After the inputs have been identified, the truth table of the Boolean functions can be determined from the samples. If the number of variables for each function is at maximum K, the REVEAL algorithm considers any of the    (    K n   )  combinations of variables, where n is the number of nodes in the network.The numerical results in [1] suggest that it is possible to identify a Boolean network using a small number of samples. Akutsu et al. [2] gave an analytical and constructive proof that it is possible to identify the network using only  O  (  log n  ) samples with high probability. For constant values of K, the given algorithm, BOOL, has time complexity  O  (    n   K + 1   £¿ m  ) where m is the number of samples. Later it was shown that a similar algorithm also works in the presence of (low-levela) noise [3]. These algorithms are based on exhaustive search in two ways. First, they s
%U http://bsb.eurasipjournals.com/content/2011/1/6