Boolean Function Generation for Complex Systems

Tamon Stephen


Description:Complex systems are often controlled by many boolean (binary) variables, whose values are either "true" or "false". We would like to characterize how these variables affect a particular behaviour of the system, which itself is boolean. Suppose the behaviour is monotone in the sense that, given a setting of the variables that permits the behaviour, if additional variables are set to "true" the behaviour is still permitted. Then this behaviour is a monotone boolean function of the variables. Such a function is characterized uniquely by both the minimal sets of variables permitting the behaviour and the minimal sets of variables inhibiting the behaviour. This situation is common in complex systems, such as those that comprise computational biology. As an example, a metabolic network can be characterized in its metabolites and reactions. In a steady state many of these reactions operate simultaneously. When some of these reactions are knocked out, various behaviours of the system will be blocked. We then have a boolean function which can be described either through elementary modes, i.e. minimal sets of reactions supporting the behaviour, or minimal cut sets blocking the behaviour. Our goal is to develop efficient algorithms to enumerate these minimal sets, and to understand them both theoretically and computationally. We proceed from an oracle that evaluates the function. In the metabolic networks example mentioned above, this can be implemented as a simple linear program based on the stoichiometric matrix that records the number of metabolites produced and consumed by each reaction. We are motivated in part by the novel algorithm of Fredman and Khachiyan which generates these forms with a surprisingly good worst-case complexity, but is not well understood in practice. These ideas also have an interesting connection to fundamental questions in computational geometry on describing polyhedra.