Brief paper

Robust dynamical network structure reconstruction☆

One of the fundamental interests in systems biology is the discovery of the specific biochemical mechanisms that explain the observed behaviour of a particular biological system. In particular, we consider the problem of reconstructing the network structure from input and partially measured output data of a dynamical system, and in turn uncovering the underlying mechanisms responsible for the observed behaviour. The biological network reconstruction problem challenges come from the necessity to deal with noisy and partial measurements (in particular, the number of hidden/unobservable nodes and their position in the network is unknown) taken from a nonlinear and stochastic dynamical network.

There are several tools in the literature to infer causal network structures. These tools are mainly rooted in three fields: Bayesian inference (Dojer et al., 2006, Yu et al., 2004), information theory (ARACNe Basso et al., 2005, Butte and Kohane, 2000, Faith et al., 2007) and ODE methods (inferelator Bansal and di Bernardo, 2007, Bonneau et al., 2006, di Bernardo et al., 2005, Gardner et al., 2003, Sontag, 2008). Details on these and other methods can be found in several reviews of the field such as Bansal, Belcastro, Ambesi-Impiombato, and Bernardo (2007), Cantone et al. (2009), De Smet and Marchal (2010), Hecker, Lambeck, Toepfer, Someren, and Guthke (2009) and Koyuturk (2010). The vast majority of network reconstruction methods produce estimates of network structure regardless of the informativity of the underlying data. In particular, most methods produce estimates of network structure even in cases with data from only a few experiments. Such data may not contain enough information to enable the accurate reconstruction of the actual network, thus the obtained network estimates can be arbitrarily different from the true network structure (Cantone et al., 2009). To compensate for the lack of information in data, most methods have heuristics that try to “guess” at the remaining information, either by specifying prior distributions or by appealing to a priori beliefs about the nature of real biological networks, such as looking for the sparsest network. Nevertheless, these heuristics bias the results and lead to incorrect estimates of the network structure.

In contrast, our approach has been to identify the conditions when data is sufficiently informative to enable accurate network reconstruction. The results indicate that even in an ideal situation, when the underlying network is linear and time-invariant (LTI) and the measurements are noise-free, network reconstruction is impossible without additional information (Gonçalves & Warnick, 2008). Surprisingly, this information gap is not due to a lack of data, or a deficiency in the number of experiments, but rather it occurs because system states are only partially observed; the information gap is present in all data sets except those that satisfy certain experimental conditions. Our analysis identified a particular experimental protocol that satisfies these necessary conditions to ensure that data will be sufficiently informative to enable network reconstruction. This protocol suggests the following.

1.

A network composed of $p$ measured species demands $p$ experiments.

2.

Each experiment requires a distinct input that independently controls a measured species, i.e. experimental input $i$ must affect measured species $i$ and no other measured species except, possibly, indirectly through measured species $i$.

The work in Gonçalves and Warnick (2008), however, did not take into account the realistic scenario that typically systems are nonlinear and data are noisy. This paper extends and details earlier results in Gonçalves and Warnick (2009) by developing an effective method to reconstruct networks in the presence of noise and nonlinearities, assuming that the conditions for network reconstruction presented above in (1) and (2) have been met. Steady-state (resp. time-series) data can be used to reconstruct the Boolean (resp. dynamical) network structure of the system.

The paper is organised as follows. After a motivating example showing that input–output data alone does not enable network reconstruction, Section 2 reviews dynamical structure functions and gives fundamental results concerning their usefulness in the network reconstruction problem. Section 3 presents the main results of the paper regarding robust network reconstruction from input–output data subject to noise and nonlinearities. Finally, we conclude the paper with biologically inspired examples in Section 4.

Notation. For a matrix $A\in {\mathbb{C}}^{M\times N},A_{ij}\in \mathbb{C}$ denotes the element in the $i$th row and $j$th column while $A_j\in {\mathbb{C}}^{M\times 1}$ denotes its $j$th column. For a column vector $\alpha ,\alpha \left[i\right]$ denotes its $i$th element. We define $e_r^T=[0,\dots ,0,1_{r^{th}},0,\dots ,0]\in {\mathbb{R}}^{1\times N}$. $I$ denotes the identity matrix. When it is clear from the context, we omit the explicit dependence of transfer functions on the Laplace variable $s$, e.g. we write $G$ instead of $G\left(s\right)$.

Motivating example. Consider the transfer function $G\left(s\right)=\frac{1}{s+3}\left[\begin{array}{c}\hfill \frac{1}{s+1}\hfill \\ \hfill \frac{1}{s+2}\hfill \end{array}\right]$ obtained from data (partial observations) using system identification tools. For simplicity, assume that $G\left(s\right)$ accurately represents the input–output relation of the original system. This transfer function is consistent with two state-space realisations $\dot{x}=Ax+Bu,y=Cx$ given by $A_1=\left[\begin{array}{ccc}\hfill -1& \hfill 0& \hfill 1\\ \hfill 0& \hfill -2& \hfill 1\\ \hfill 0& \hfill 0& \hfill -3\end{array}\right]\text{,}{A}_2=\left[\begin{array}{ccc}\hfill -2& \hfill -1& \hfill 1\\ \hfill -1& \hfill -3& \hfill 1\\ \hfill 0& \hfill -1& \hfill -1\end{array}\right]\text{,}$$B_1=B_2={\left[001\right]}^T$, and $C_1=C_2=\left[I0\right]\in {\mathbb{R}}^{2\times 3}$ (i.e., the third state is hidden/non-observable). Note that both realisations are minimal and correspond to very different network structures as seen in Fig. 1. This demonstrates that even in the idealised setting (LTI system, no noise and perfect system identification), network reconstruction in the presence of hidden/unobservable states is not possible without additional information about the system.