Research Spotlight

Boolean Function Generation for Complex Systems

This project is about algorithms for generating the minimal operating and failure modes of a complex system controlled by many boolean (true-false) variables. This is a fundamental algorithmic question that has unexpected theoretical properties and is poorly understood computationally. However, these "boolean functions" arise naturally in models of complex systems, notably in computational biology.
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.

The goal of the project is to develop efficient algorithms to enumerate these minimal sets, and to understand them both theoretically and computationally. The project is 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.

About the Project Leader: Dr. Tamon Stephen is an assistant professor in the Department of Mathematics of Simon Fraser University. He completed his Ph.D. thesis “The Distribution of Values in Combinatorial Optimization Problems” under the direction of Alexander Barvinok at the University of Mitchigan in 2002. Dr. Stephen was a postdoc at the Institute of for Mathematics and its Applications at the University of Minnesota. Dr. Stephen works in the field of operations research. His research focus is in combinatorial optimization, both at a theoretical level and in practice (computationally). In his own words,``I like projects that touch on different areas and disciplines, and my research has ventured into algorithms, combinatorics, discrete geometry and computational biology." Dr. Stephen is a member of the Centre for Operations Research and Decision Sciences at SFU, the Operations Research Group at SFU, and the Discrete Math Group at SFU.