Russell Howes and Dr. Sean Warnick, Computer Science Department

Network structure–the presence and absence of ‘connections’ among different variables in a dynamical system–is important in the identification and control of complex systems. Discovering structure from data can be difficult, and many current identification methods either concern themselves only with dynamic behavior (response of the system to an input), or try to infer structure without dynamics.

In this work we concern ourselves with linear, time-invariant (LTI) systems of equations with partial state measurement (some of the variables are visible output while others are not). The dynamical structure function of an LTI system is a matrix of strictly proper, rational transfer functions, each of which measures the net effect of one observed state or input on another observed state. This net effect is a combination of direct effects between the two states, and other indirect effects that are not influenced by any other observed state. A zero term in the dynamical structure function matrix means no relation between the corresponding states or inputs.

Decoupledness

One area of interest in my research has been the topic of sparsity and decoupledness. Sparsity in this context refers to the fewest possible number of connections (nonzero terms) one can have for a network with a given transfer function. Decoupledness means no connections exist between observed states, only from inputs to observed states. Decoupledness is a bit more interesting in this context as it seems to be a commonly assumed condition in network reconstruction.

We have determined that a single-input, strictly proper rational transfer function has a completely decoupled minimal realization if and only if each term in the transfer function has a unique pole. The proof introduces a construction of a ‘decoupled canonical form’ for such systems. The condition is sufficient but not necessary for systems with multiple inputs.

There is still a good deal of unsolved work relating to this problem. I am currently working on extending our sparsity results to systems with more than one input, and possibly relaxing the sparsity condition to block-sparsity (groups of states may affect each other, but states from one group do not affect states from any other group).

Reconstruction of Biological Networks

Many methods that exist for reconstructing biological networks take into account assumptions of sparsity, decoupledness, or already known (or guessed) relationships among states of the network. These assumptions can sacrifice accuracy of the reconstructed system.

Input-output data alone is insufficient to reconstruct a network with hidden states, even if a system is linear and time-invariant. We previously characterized precisely the additional information needed to obtain network structure without making other assumptions. In biological systems, this information can be obtained through a series of typical experiments, called gene silencing and gene overexpression experiements.

We can simulate these experiments in LTI networks by introducing an extra, hidden state with a high degradation constant and a large effect on the state to be modified (negative effect for silencing, positive for overexpression). Assuming nothing is known about the internal structure of the system (relations among the visible states) such experiments are designed to fix the effects of inputs on the hidden states. This provides a transfer function which has been modified in a known way (see Figure 1). As explained in the previous paper, with enough experiments the dynamical structure can be solved uniquely.

The ‘additional information needed’ to obtain the dynamical structure of an LTI network is equivalent to performing p silencing or overexpression experiments, one on each of the observed states. If a particular state cannot be modified, structure can still be obtained by performing two additional experiments on the remaining states. I have developed an algorithm that takes input-output data from the original system and the modified systems, and yields this dynamical structure.

I am currently implementing the identification algorithm in MATLAB, readying it for our next project. Over the next few months I, with several other students in the lab, will be testing this algorithm and comparing its efficiency with that of several other methods–sparsity and LMI mthods–common in biological network identification. We have already generated a program to randomly create networks and input-output data for those networks. We will compare the accuracy of the various methods in reconstructing the networks (false positives and false negatives.)

Figure 1: A sample network and the effects of the network when various states are silenced. (Note that the input u has no effect on the rest of the network when state 1 is removed.)

References

• J. Gonçalves, S. Warnick, R. Howes,“ Necessary and Sufficient Conditions for Dynamical
  Structure Reconstruction of LTI Networks,” IEEE Conference on Decision and Control (December 2007).